Sayısal Analiz: İkiye Bölme (Bisection) Metodu

İkiye bölme ya da yarılama metodu (İngilizcesiyle bisection ya da binary search), en basit ve kaba sayısal (nümerik) analiz metotlarından biridir. Aslında sadeliği, sayısal analizin doğasının anlaşılması için oldukça şahane bir imkan sunar. Fakat bu kadar basit olması, ona bazı dezavantajlar getirdiği için çoğunlukla tercih edilmez.

İkiye bölme metodu, tam olarak adının da anlattığı işlemi uygular. Bir f(x) fonksiyonu alınsın. Bu fonksiyon [a,b] kapalı aralığında sürekli ve a ile b sayıları reel sayılar kümesinin birer elemanı olsun. Eğer bu aralıkta f(a).f(b)<0 oluyorsa, Bolzano teoreminin bize söylediği üzere bu aralıkta bu fonksiyonun en az bir kökü bulunur. Kökün bulunduğunu garantiledikten sonra tek yapılması gereken, f(a).f(b)<0 koşulunu, aralığı ikiye bölmeye devam ederek sağlamaktır.

Örneğin, f(x)=x2-2 fonksiyonu için [1,2] kapalı aralığında kökü arayalım. f(1) negatif, f(2) pozitif bir değere sahiptir. Fonksiyon bu aralıkta işaret değiştirdiğine ve sürekli olduğuna göre, bu aralıkta bir yerde en az bir kök değerim bulunur. İkiye bölme işlemi uygulanır ve 1 ile 2 noktalarının tam orta noktası olan 1.5 değeri incelenir. f(1.5) değeri pozitif bir değerdir. Yani eski durumumda f(1).f(2)<0 idi, şimdi ben bunun aslında f(1).f(1.5)<0 olduğunu biliyorum. Bu durumda köküm 1.5 ile 2 arasında değildir ve bu aralığı incelememe gerek yoktur.

Bundan sonra 1 ile 1.5 noktalarının tam orta noktası olan 1.25 değeri için işareti inceliyorum. f(1.25) değeri negatif bir değer çıkıyor. f(1.5) değeri de pozitifti. Öyleyse f(1.25).f(1.5)<0 olduğuna göre kök, 1.25 ile 1.5 değeri arasında bir yerdedir. İşlem bu şekilde sürüp gidiyor ve her adımda köke daha çok yaklaşıyorsunuz. Oldukça basit ve kaba bir metot, fakat pratikte gayet güzel çalışıyor ve nümerik analizin mantığı anlamakta müthiş bir örnek.

Avantajları ve Dezavantajları

İkiye bölme (bisection) metodunun avantajları, daima yakınsaması ve hatanın kontrol edilebilmesidir. Hatası daima (b-a)/2(n+1) değerinden küçüktür. Burada b ve a sınır koşulları, n ise yapılan işlemin tekrar sayısıdır. Dolayısıyla belirli bir aralıkta, n kadar tekrar sonra yaptığınız işlemin ne kadar hassaslıkla doğru sonuç verdiğini bilebilirsiniz. Bu çok önemlidir, çünkü gerçek değeri bilmiyorsunuz ve bir takım işlemler uyguluyorsunuz, sonucunda gerçek değere ne kadar yakınsınız? Bu kritik soruya, ikiye bölme metodu cevap verebiliyor, bu önemli bir özellik.

Dezavantajlarından biri, yakınsama hızının yavaş olması. Çok kaba denmesinin sebebi budur. İlk akla gelen şey, orta noktayı alıp, buradan çıkarım yapmaktır. Oysaki daha akıllıca metotlarda çok daha hızlı yakınsama yapılabilir. Bir diğer dezavantajı x2 gibi fonksiyonlarda, fonksiyon işaret değiştirmediğinden kökü bulamamasıdır. Bir diğer yandan, 1/x gibi fonksiyonlardaki tekillik (singülerlik), ikiye bölme metodu için yanıltıcı olabilir. Fonksiyon bir değerde negatif, bir değerde pozitif olmasına rağmen, bu ikisinin arasında sonsuza gitmektedir.

İkiye Bölme Metodunun Anlatımı

İkiye Bölme Metodunun Hatası ve İspatı

İkiye Bölme Metodu Örnek Soru Çözümü

Ögetay Kayalı

Referanslar
1. Turgut Öziş, Ege Üniversitesi Matematik Bölümü, Nümerik Analiz ders notları
2. <https://mat.iitm.ac.in/home/sryedida/public_html/caimna/transcendental/bracketing%20methods/bisection/bisection.html>
3. <http://www.mathcs.emory.edu/~cheung/Courses/170/Syllabus/07/bisection.html>

Ögetay Kayalı

Astronom. Özel ilgi alanı teorik kozmoloji, özellikle Einstein'ın görelilik kuramının modifiye edilmesi (modified gravity) üzerine uğraşıyor. Bunların yanında ender bulduğu zaman aralıklarında kafasına esince programlama, 3B modelleme, makineler, tasarım, fotoğrafçılık, resim ve satranç ile de ilgileniyor.

Ögetay Kayalı 120 makale yazdıÖgetay Kayalı tarafından yazılan tüm makaleleri gör