img033 (41)

38

= !'P ^x(k) = !*p ^a(k) = !^im h)-    (³ ■¹¹)

^v kl oo ^v 7 k/oo ^v 7 k / co ^v

Ponieważ

/(«(*))< ⁰ i /(%))> O    (3.12)

oraz funkcja_/(-) jest ciągła, więc

O > Hm/(a_W) = /(x_(a)))= Hm/(%))> O ,    (3.13)

A/oo    ^v    A: /co ^v

skąd wynika, żeyfx(<x>)) ⁼ 0. Punkt graniczny X(_K) jest zatem pierwiastkiem danego równania (3.1). W przedziale (a, b) mogą być oczywiście zawarte jeszcze inne pierwiastki równania.

Otrzymuje się następujący zwarty opis konstrukcji ciągu (*(*))*=! ₂,— kolejnych przybliżeń w metodzie bisekcji:

^a(G)'-=^a’ ^b(o)^:=bl    (3 -14)

dla k= 0,1,2, •••,

*(£+1)^:= («(*)+fy))/²;    (3.i5)

jeżeli

sign f[x(k+i))= sign/(a_W), to a_(yt+1) = x_(i+1) i ń(_t+1) = ń_((t);    (3.16)

jeżeli

sign/(x₍*₊₁))=-sigri/(a_W), to    = a(_k) i &(_t+1) = X(_t+1).    (3.17)

Obliczenia zostają zakończone, jeżeliy(%+i)) ⁼ O lub jeżeli spełnione są nierówności (3.8) i (3.9). Otrzymany punkt X(*+i) jest przyjmowany jako rozwiązanie danego równania (3.1) w zadanym przedziale \a, b\. W przypadku ogólnym jest to rozwiązanie przybliżone.

Realizacja algorytmu może być powtórzona dla nowego przedziału początkowego w celu wyznaczenia następnego pierwiastka danego równania (3.1).

Szybkość zbieżności algorytmu połowienia jest liniowa. Wynika to z oszacowania

|*(M-l4bo-4    =    (3-18)

gdzie x* jest pierwiastkiem danego równania (3.1) będącym granicą otrzymanego z obliczeń ciągu {x^)_{k=l l} ... kolejnych przybliżeń. Oszacowania tego w ogólnym przypadku nie

można już poprawić.

Uogólnienie metody bisekcji na przypadek wielowymiarowy, dla układów równań, nastręcza duże trudności [7], Algorytm metody ulega znacznej komplikacji i zajmuje w czasie obliczeń dużo miejsca w pamięci komputera. Metoda pozostaje przy tym zbieżna liniowo, a więc raczej wolno.

Algorytm bisekcji aczkolwiek wolno zbieżny ma jednak istotną cechę zbieżności globalnej przy spełnieniu odpowiednich założeń odnośnie funkcji /(•) występującej w danym równaniu (układzie równań) i założeń odnośnie do przedziału, w którym poszukiwany jest pierwiastek równania (układu równań). Dlatego też metoda połowienia jest wykorzystywana w celu otrzymania dobrego przybliżenia początkowego pierwiastka (dla jego lokalizacji) i na ogół w połączeniu z inną, lokalnie, ale za to szybciej zbieżną metodą.