İkiye bölme yöntemi - Bisection method

Başlangıç ​​aralığında [a 1 ;b 1 ] uygulanan ikiye bölme yönteminin birkaç adımı . Daha büyük kırmızı nokta, işlevin köküdür.

Gelen matematik , ikiye bölme yöntemi a, kök bulma yöntemi için de geçerlidir sürekli fonksiyonlar için tek bir ters işaretli iki değeri bildiği için. Yöntem sürekli oluşur ortadan ayırıcı aralığı bu değerler tarafından belirlenir ve daha sonra fonksiyonu içermelidir, bu nedenle işareti değiştirir, ve burada alt-aralığın seçilmesi kök . Çok basit ve sağlam bir yöntemdir, ancak aynı zamanda nispeten yavaştır. Bu nedenle, daha sonra daha hızlı yakınsak yöntemler için bir başlangıç ​​noktası olarak kullanılan bir çözüme kabaca bir yaklaşım elde etmek için sıklıkla kullanılır. Yöntem aynı zamanda aralıklı yarıya bölme yöntemi, ikili arama yöntemi veya dikotomi yöntemi olarak da adlandırılır .

İçin polinomların , daha özenli yöntemler arayla bir kökün varlığını test etmek için var ( işaretlerin Descartes'ın kuralı , Sturm teoremi , Budan teoremi ). Bir polinomun tüm gerçek köklerini bulmak için ikiye bölme yöntemini verimli algoritmalara genişletmeye izin verirler; bkz. Gerçek kök izolasyonu .

yöntem

Yöntem sayısal denklem çözme için uygulanabilir f ( x için) = 0 , gerçek değişken x , f a, sürekli bir fonksiyon bir aralık [üzerinde tanımlanan birb ] ve burada f ( a ) ve f ( b ) ters işaretlere sahip olduğu . Bu durumda a ve b'nin bir kökü parantez içine aldığı söylenir, çünkü ara değer teoremi ile sürekli f fonksiyonunun ( a , b ) aralığında en az bir kökü olması gerekir .

Her adımda yöntem, aralığın orta noktası c = ( a + b ) / 2'yi ve o noktadaki f ( c ) fonksiyonunun değerini hesaplayarak aralığı iki parçaya/yarıya böler . Sürece c kendisi bir (çok olası değildir, ancak olası) kök sadece iki olasılık şimdi vardır: ya f ( a ) ve f ( c ) karşısında işaretlere sahip ve bir kök veya paranteze alan f ( c ) ve f ( b ) zıt işaretlere sahip ve bir kök parantezine sahip. Yöntem, bir sonraki adımda kullanılacak yeni aralık olarak parantez olması garanti edilen alt aralığı seçer. Bu şekilde, sıfır f içeren bir aralığın genişliği her adımda %50 oranında azaltılır. Aralık yeterince küçük olana kadar işleme devam edilir.

Açıkça, f ( a ) ve f ( c ) zıt işaretlere sahipse, yöntem c'yi b için yeni değer olarak ayarlar ve f ( b ) ve f ( c ) zıt işaretlere sahipse, yöntem c'yi yeni olarak ayarlar bir . ( f ( c )=0 ise, çözüm olarak c alınabilir ve süreç durur.) Her iki durumda da, yeni f ( a ) ve f ( b ) zıt işaretlere sahiptir, dolayısıyla yöntem bu daha küçük aralığa uygulanabilir. .

Yineleme görevleri

Yöntemin girdisi, sürekli bir f fonksiyonu , bir aralık [ a , b ] ve f ( a ) ve f ( b ) fonksiyon değerleridir . İşlev değerleri zıt işaretlidir (aralık içinde en az bir sıfır geçişi vardır). Her yineleme şu adımları gerçekleştirir:

  1. Aralığın orta noktası olan c'yi hesaplayın , c = bir + b/2.
  2. F ( c ) orta noktasındaki fonksiyon değerini hesaplayın .
  3. Yakınsama tatmin ediciyse (yani, c - a yeterince küçükse veya | f ( c )| yeterince küçükse), c döndürün ve yinelemeyi durdurun.
  4. f ( c ) işaretini inceleyin ve ( a , f ( a )) veya ( b , f ( b )) ile ( c , f ( c )) değiştirin, böylece yeni aralıkta sıfır geçişi olur.

Yöntemi bir bilgisayarda uygularken, sonlu hassasiyetle ilgili sorunlar olabilir, bu nedenle genellikle ek yakınsama testleri veya yineleme sayısı için sınırlar vardır. f sürekli olmasına rağmen , sonlu kesinlik bir fonksiyon değerinin sıfır olmasını engelleyebilir. Örneğin, f ( x ) = x − π düşünün ; x'in sıfırı veren sonlu bir temsili asla olmayacak . Ek olarak, a ve b arasındaki fark , kayan nokta kesinliği ile sınırlıdır; yani, a ve b arasındaki fark azaldıkça, bir noktada [ ab ] öğesinin orta noktası a veya b öğesinin (kayan nokta kesinliği dahilinde) sayısal olarak aynı olacaktır .

algoritma

Yöntem, sözde kodda aşağıdaki gibi yazılabilir :

INPUT: Function f, 
       endpoint values a, b, 
       tolerance TOL, 
       maximum iterations NMAX
CONDITIONS: a < b, 
            either f(a) < 0 and f(b) > 0 or f(a) > 0 and f(b) < 0
OUTPUT: value which differs from a root of f(x) = 0 by less than TOL
 
N ← 1
while NNMAX do // limit iterations to prevent infinite loop
    c ← (a + b)/2 // new midpoint
    if f(c) = 0 or (ba)/2 < TOL then // solution found
        Output(c)
        Stop
    end if
    NN + 1 // increment step counter
    if sign(f(c)) = sign(f(a)) then ac else bc // new interval
end while
Output("Method failed.") // max number of steps exceeded

Örnek: Bir polinomun kökünü bulma

Polinomun kökünü bulmak için ikiye bölme yönteminin kullanıldığını varsayalım.

İlk olarak, iki sayı ve öyle bulunmalı ve zıt işaretlere sahip olmalıdır. Yukarıdaki fonksiyon için ve bu kriteri şu şekilde karşılayın:

ve

Fonksiyon sürekli olduğu için [1, 2] aralığında bir kök olmalıdır.

İlk yinelemede, kökü parantez içine alan aralığın bitiş noktaları ve dir , dolayısıyla orta nokta

Orta noktadaki fonksiyon değeri . Çünkü negatiftir, bunu sağlamak için bir sonraki yineleme için ile değiştirilir ve zıt işaretlere sahiptir. Bu devam ettikçe, arasındaki aralık ve fonksiyonun kökü üzerinde yakınsak, giderek küçülecektir. Aşağıdaki tabloda bunun gerçekleştiğini görün.

yineleme
1 1 2 1.5 -0,125
2 1.5 2 1.75 1.6093750
3 1.5 1.75 1.625 0.6660156
4 1.5 1.625 1.5625 0.2521973
5 1.5 1.5625 1.5312500 0.0591125
6 1.5 1.5312500 1.5156250 -0.0340538
7 1.5156250 1.5312500 1.5234375 0.0122504
8 1.5156250 1.5234375 1.5195313 -0.0109712
9 1.5195313 1.5234375 1.5214844 0.0006222
10 1.5195313 1.5214844 1.5205078 −0,0051789
11 1.5205078 1.5214844 1.5209961 -0,0022794
12 1.5209961 1.5214844 1.5212402 -0.0008289
13 1.5212402 1.5214844 1.5213623 -0.0001034
14 1.5213623 1.5214844 1.5214233 0.0002594
15 1.5213623 1.5214233 1.5213928 0.0000780

13 tekrardan sonra, yaklaşık 1.521'e yakınsama olduğu ortaya çıkıyor: polinom için bir kök.

analiz

Yöntem, bir kök yakınsaması garantili f ise f a, sürekli bir fonksiyon aralığı [ile bir , b ] ve f ( a ) ve f ( b ) ters işaretlere sahip olduğu. Mutlak hata yöntemi böylece her adımda ikiye bölünür doğrusal yakınsar . Spesifik olarak, eğer c 1 =bir + b/2ilk aralığın orta noktası, ve c , n de aralığın orta noktası , n inci aşaması, daha sonra farkı , c , n ve bir çözelti C ile sınırlanmış

Bu formül, ikiye bölme yönteminin belirli bir tolerans dahilinde bir köke yakınsaması gereken yineleme sayısı üzerindeki bir üst sınırı önceden belirlemek için kullanılabilir. Gerekli bir tolerans ε (yani, en fazla ε olması garanti edilen bir hata) elde etmek için gereken yineleme sayısı n ,

Burada başlangıç ​​parantez boyutu ve gerekli parantez boyutu İkiye bölme yöntemini kullanmanın ana motivasyonu, sürekli fonksiyonlar kümesi üzerinden, en kötü durumda mutlak bir değeri olan c çözümüne bir c n tahmini üretmeyi başka hiçbir yöntemin garanti edememesidir. n 1/2 yinelemeden daha az hata . Bu aynı zamanda f fonksiyonu ve fonksiyonun kökün komşuluğundaki davranışı ile ilgili birkaç yaygın varsayım altında da geçerlidir.

Bununla birlikte, ikiye bölme yöntemi, mutlak hata kriterleri altında en kötü durum performansına göre optimal olmasına rağmen, asimptotik performansın yanı sıra standart varsayımlar altındaki ortalama performansa göre optimalin altındadır . Kesen yöntemi , Ridders yöntemi veya Brent yöntemi (diğerlerinin yanı sıra) gibi ikiye bölme yönteminin popüler alternatifleri , köke daha yüksek yakınsama sıraları elde etmek için en kötü durum performansını takas ettikleri için tipik olarak daha iyi performans gösterir . Ve, ITP Yöntemi ile en kötü durum performansından ödün vermeden daha yüksek bir yakınsama sırası ile ikiye bölme yönteminde katı bir iyileştirme elde edilebilir .


Ayrıca bakınız

Referanslar

daha fazla okuma

Dış bağlantılar