bisekcja.pdf

Bisekcja

Pierwsz¡ technik¡ bazuj¡c¡ na twierdzeniu o warto–ci –redniej jest algorytm

bisekcji . Za“ ó »my, »e dana jest funkcja f , ci¡g“a na[ a;b ], przy czym f ( a )i

f ( b )s¡ przeciwnych znak ó w. Zgodnie ze wspomnianym ju» twierdzeniem ist-

nieje liczba p2 ( a;b )taka, »e f ( p )=0. Dla uproszczenia przyjmujemy, »e w

danym przedziale pierwiastek ten jest jedynym. Metoda polega na powtarza-

j¡cym siƒ dzieleniu podprzedzia“ ó w na po“owy i wybieraniu w ka»dym kroku

tej po“ ó wki, kt ó ra zawiera pierwiastek. Warunek zako«czenia algorytmu:

f ( p )=0lub( b¡a )/2jest mniejsze od za“o»onej warto–ci.

Inne warunki zako«czenia:

1. jp N ¡p N¡ 1 j<" (zawodzi w przypadku, gdy p n = n P

k =1

k ;

wtedy lim

n!1 ( p n ¡p n¡ 1 )=0, ale p n !1 );

2. jp N ¡p N¡ 1 j

jp N j <" , p N 6 =0- najlepszy w sytuacji, kiedy nie posiadamy

dodatkowej wiedzy o funkcji f lub zerze p ;

3. jf ( p n ) j<" (r ó wnie» zawodny dla funkcji, kt ó rych warto–ci szybko ro-

sn¡).

Uwagi:

1. przy pisaniu programu warto na“o»y¢ g ó rne ograniczenie na liczbƒ ite-

racji - zapobiega to zapƒtleniu siƒ;

2. aby rozpocz¡¢ algorytm nale»y tak dobra¢ a i b , aby f ( a ) f ( b ) < 0.

Poniewa» przy ka»dej iteracji d“ugo–¢ przedzia“u zmniejszana jest dwu-

krotnie warto tak dobra¢ a i b , aby przedzia“[ a;b ]by“ mo»liwie naj-

mniejszy;

3. algorytm bisekcji jest bardzo powoli zbie»ny, a co wiƒcej, dobre przybli-

»enie po–rednie mo»e zosta¢ nieumy–lnie odrzucone. Jednak»e metoda

ta zawsze zbiega do rozwi¡zania i z tego powodu jest dobrym punktem

wyj–cia dla lepszych metod;

4. ci¡g p n kolejnych przybli»e« zera spe“nia nier ó wno–¢

jp n ¡pj· b¡a

2 n ;n¸ 1;

z nier ó wno–ci tej mo»emy wyznaczy¢ maksymaln¡ liczbƒ iteracji przy

»¡danej dok“adno–ci; z regu“y jest ona znacznie wiƒksza ni» rzeczywi–cie

potrzebna.