Bisection

Denklem:
Hata Payı:
Aralık:
Hassasiyet:
	0

Bu yazımda bir reel kök bulma algoritması olan bisection(türkçesi ikiye ayırma) algoritmasını anlatacağım. Standart bisection algoritmasından sonra da, bu algoritmadan daha fazla yararlanmanızı sağlayacak ufak bir algoritma daha ekleyeceğim. Kısa bir özet geçip kafanızda kabaca şekillendirdikten sonra, pseudocode eşliğinde detaylı olarak anlatacağım. Yukarıda, algoritmanın javascript ile yazmış olduğum hali mevcut. Denklem kısmına denklemin katsayılarını uygun şekilde(örneğin, x^3 + 2x^2 + 6x + 5 için 1,2,6,5) girip, gerekli aralığı ve parametreleri belirledikten sonra hesapla butonuna tıkladığınızda, bulunan reel kökleri butonun yanında görebilirsiniz.

Bisection algoritması, kaçıncı dereceden olursa olsun, bir homojen denklemin, belirli bir aralıktaki reel kökünü(o aralıkta varsa) bulmaya yarar. Örnek vererek açıklayayım. Şimdi ikinci dereceden bir denklem düşünün. x^2 + 6x + 5 = 0 olsun mesela. Bu denklemin grafiğini gözünüzde canlandırın. X eksenini iki noktada kesen parabolik bir eğri. Biz x ekseni üzerinde iki nokta seçip, bu noktaların arasındaki değerlerle ilgileniyoruz. Eğer 0'dan geçtiği noktalardan biri, seçtiğimiz aralıktaysa, bu aralığı daralta daralta 0'dan geçtiği noktaya ulaşabiliriz.

Adım adım çözeceğim şimdi bu algoritmayı, yukarıdaki denklem üzerinde. Örneğin -4 ile 0 arasını seçtik. -4 sol, 0 sağ sınırımız. Sol sınırı denkleme yazarsak, değeri -3, sağ sınırı yazarsak değeri 5 oluyor. Grafik -3'ten 5'e giderken 0'dan geçmek zorunda. Demek ki bu aralıkta denklemin bir kökü var. Şimdi algoritmaya geçelim.

Sağ ve sol sınırın orta noktasını buluyoruz.
-4 ve 0, orta noktası toplamlarının yarısı, yani (-4+0)/2 = -2

Denklemin bu orta noktadaki değerini hesaplıyoruz.
(-2)^2 + 6(-2) +5 = -3

Sağ ve sol sınır fonksiyon değerleri arasından, bu değerle aynı işaretli olan değer hangisiyse, o sınır yerine bu orta noktayı koyuyoruz
Orta noktanın değerinin işareti (-)
Sol sınır -4, değeri -3, işareti (-)
Sağ sınır 0, değeri 5, işareti (+)
Sol sınırın yerine -2 geçecek

Orta noktanın denklem hesaplandığındaki değeri 0 olana kadar bu adımlar tekrar edilecek. Bir kez daha tekrar edelim.

Sol sınır -2, sağ sınır 0.
Orta nokta (-2+0)/2 = -1
Orta noktanın değeri (-1)^2 + 6(-1) +5 = 0

0'a ulaştığımız için burada kesiyoruz.

Algoritmayı iyice kavradığınızı düşünüyorum. Pseudocode'a geçmeden önce değinmek istediğim birkaç nokta var.

Birincisi, bu algoritma ile değeri tam 0 olan bir kök bulmak çoğu zaman imkansızdır. Katrilyonda 1 hata payınız bile olsa, program bunu kabul etmeyecek, tam 0 bulana kadar dönmeye çalışacaktır. Bu yüzden çok çok küçük, örneğin 0.000000000001 gibi bir hata payımız olduğunu programa söyleyeceğiz. Bu değer benim testlerime göre optimum değer. Bu 0 zaten hiç koymayalım demeyin, emin olun fark ediyor.

İkincisi, yukarıda sınırları denklemde yerine yazıp değer bulmak için de bir algoritmaya ihtiyaç duyacaksınız. Bu algoritmayı, yine pseudocode ile fonksiyon şeklinde yazacağım.

Son olarak da şunu söyleyeyim, bu algoritma, seçtiğiniz alanda birden fazla kök varsa düzgün çalışmayabilir. Ancak korkmayın, yazının başında bahsettiğim o küçük algoritma, aralığı çok küçük parçalara bölüp teker teker işlem yapmaktadır. Dolayısıyla bu sorunu kısmen de olsa halledip, gayet hızlı bir şekilde denklemin bütün reel köklerini size çıkaracaktır.

Şimdi programın son halini pseudocode ile size sunuyorum. Denklemin katsayılarını soldan sağa, liste, dizi vb. şeklinde programa veriyoruz. Sınır değerlerimiz de 2 elemanlı bir dizi diye düşünün.

Girişler:

denklem = [1, 6, 5]
hata_payı = 0.000000000001
aralık = [-50, 50]
hassasiyet = 0.1

Pseudocode:

fonksiyon hesapla(katsayılar, sayı):
    derece = katsayılar.boyut - 1  // terim sayısının 1 eksiği, denklemin derecesini verir
    toplam = 0
    döngü i = 0'dan (derece-1)'e kadar:
        toplam = toplam + sayı^(derece - i) * katsayılar[i]
    toplamın değerini ver

n = aralık[0]
şart n < aralık[1] sağlandığı sürece:
    a = n
    b = n + hassaslık
    sonsuz döngü:
        değer_a = hesapla(katsayılar, a)
        değer_b = hesapla(katsayılar, b)
        eğer değer_a * değer_b > 0 ise:  // işaretleri aynı ise
            döngüyü kır
        değilse:
            c = (a + b) / 2
            değer_c = hesapla(katsayılar, c)
            eğer değer_c < hata_payı ve değer_c > -hata_payı ise:
                yazdır c, " değerinde kök bulundu."
                döngüyü kır
            değilse:
                eğer değer_c * değer_a > 0 ise:
                    a = c
                değilse, eğer değer_c * değer_b > 0 ise:
                    b = c
                değilse:
                    döngüyü kır
    n = n + hassaslık

Biraz göz atarsanız kolayca anlayabilir, programlayabilirsiniz. Programı telefonumda python ile yazıp çalıştırdım, bir iki denememin sonucunu sizinle paylaşayım.

Gördüğünüz gibi, size yaklaşık olarak ne kadar vakit aldığını göstermek için zamanlama algoritması ekledim. Umarım faydalı olabilmişimdir. Kusurlarım mutlaka vardır, soru ve görüşlerinizi iletirseniz çok memnun olurum.

Editör olduğum yazılım sitesindeki yazının linki.