01 Temmuz 2011

Yarılama Algoritması

Nümerik analiz konusunda en temel kök bulma yöntemlerinden olan bisection(yarılama) metodunun algoritması ile başlamak istiyorum. Eğer yazacak zaman olursa kod versiyonunu ve diğer metodları da teker teker yapmak isterim.. Şimdi algoritmayı yazıp biraz da açıklayalım.

gir a,b,M,d,z
u <- f(a) 
v <- f(b) 
e <- b-a 
çıktı a,b,u,v
eğer ( sign(u) = sign (v) ) ise dur
döngü k=1 -> M
 e <- e/2 
 c <- a+e 
 w <- f(c) 
 çıktı z,c,w,e
 eğer (|e|< d veya |w|< z) ise dur
 eğer (sign(w) != sign(u)) ise
  b <- c 
  v <- w  
 aksi halde
  a <- c 
  u <- w  
 yap
döngü bitir

 Açıklamasına gelince. Öncelikle fonksiyonun kökünün hangi aralıkta bulunduğunu düşünüyorsak o aralığın bir noktasını a diğer noktasını b şeklinde bilgisayara giriyoruz. Daha sonra kaç kere yarıya bölmemiz gerektiğini yani hassasiyeti ayarlamak için M değeri giriyoruz. Daha sonra çıkış koşulları olarak d ve z'yi giriyoruz. (bunu son kısımda değerlendirelim)

 f fonksiyonumuzun a noktasındaki değeri u, b noktasındaki değeri de v olarak ve b ile a arasını (ikiye bölünecek alan) e ile tanımladık.

 Tüm bu verileri ekrana yazdırdık ve u'nun ve v'nin signumlarının yani işaretlerinin aynı olup olmadığını kontrol ettik. eğer aynı ise olay bitmiştir demektir. Burada dikkat edilmesi gereken nokta ilk belirlediğimiz a ve b değerleri gerçekten köke yakın olmalıdır ki sorun olmasın..

 Sonra M kere döndürülecek biçimde döngü içinde her seferinde aradaki fark olan e ikiye bölünür (döngü değişimi) a ile e(ikiye bölünmüş e) toplanarak c elde edilir ve c'nin fonksiyondaki değeri de w'ye aktarılır.. Tekrar k, c, w , e ekrana yazdılır.

 Daha sonra değineceğiz dediğimiz noktaya geldik. e yani yarıya bölünmüş sayı belirli bir d sayısından küçükse ya da fonksiyonun c'deki değeri olan w, z'den küçükse daha fazla deneme yapmamıza gerek olmadığından çıkılır.

 Sonra w(c'nin fonksiyondaki değeri) ve u(fonksiyonun a'daki değeri-ek: aslında b'deki değeri de alınırdı ama sorgunun içi değişirdi)'nun işaretleri aynı değilse c'yi b'ye, w'yi de v'ye taşırız. (buradaki mantık a daki değer yarıya bölüp bulduğumuz c'deki değerle aynı işaretli değilse olayı) tam tersi durumda ise c'yi a ya eşitleyip w'yi de u ya eşitleriz ve döngümüzün tekrar başına geçeriz..