MN02

Z Studia Informatyczne
Wersja z dnia 17:07, 28 sie 2006 autorstwa Przykry (dyskusja | edycje)
(różn.) ← poprzednia wersja | przejdź do aktualnej wersji (różn.) | następna wersja → (różn.)
Przejdź do nawigacjiPrzejdź do wyszukiwania

Algorytm {Metoda bisekcji}



xl = a; xr = b;
x = (a+b)/2;  e = (b-a)/2;
while (e > <math>\displaystyle \epsilon</math>) 
{
	if (f(x)*f(xl) < 0)	
		xr = x;
	else
		xl = x;
	x = (xl+xr)/2; e = e/2;
} 

Z konstrukcji metody łatwo wynika, że po wykonaniu iteracji (czyli po obliczeniu wartości funkcji) otrzymujemy , które odległe jest od pewnego rozwiązania o co najwyżej

Metoda bisekcji jest więc zbieżna liniowo z ilorazem . Choć ta zbieżność nie jest imponująca, bisekcja ma kilka istotnych zalet. Oprócz jej prostoty, należy podkreślić fakt, że bisekcja jest w pewnym sensie uniwersalna. Jeśli tylko dysponujemy dwoma punktami i takimi, że przyjmuje w nich wartości przeciwnych znaków, to metoda bisekcji z pewnością znajdzie miejsce zerowe funkcji, choćby początkowa długość przedziału była bardzo duża: zbieżność metody bisekcji jest globalna. Co ważniejsze, dla zbieżności metody bisekcji wystarcza jedynie ciągłość funkcji. Poza tym możemy łatwo kontrolować błąd bezwzględny aproksymacji miejsca zerowego. Konsekwencją (Uzupelnic: blbis ) jest bowiem następujący wniosek.

Wniosek

Dla znalezienia zera z dokładnością , wystarczy obliczyć w metodzie bisekcji

wartości funkcji.

Zbieżność metody bisekcji dla ....

Dodajmy jeszcze, że bisekcja minimalizuje błąd najgorszy w klasie zdefiniowanej Uzupełnij: na początku tej sekcji, wśród wszystkich algorytmów korzystających z określonej liczby obliczeń wartości funkcji, zob. Uzupełnij: uwaga na końcu wykładu.

Uwaga

Metoda bisekcji jest optymalna w następującym sensie. Niech będzie dowolną metodą (algorytmem) aproksymującą zero funkcji z klasy zdefiniowanej w (Uzupelnic: dfkl ), korzystającą jedynie z obliczeń (informacji o) w punktach. Wtedy dla dowolnego istnieje funkcja mająca tylko jedno zero w i taka, że

Co więcej, można pokazać, że fakt ten zachodzi też w węższej klasie funkcji , które są dowolnie wiele razy różniczkowalne. Oczywiście, nie wyklucza to istnienia metod iteracyjnych (takich jak metoda Newtona), które dla są zbieżne szybciej niż liniowo.

Metoda iteracji prostej Banacha

Zupełnie inne, i jak się okaże --- przy odrobinie sprytu bardzo skuteczne --- podejście do wyznaczania miejsca zerowego jest oparte na metodzie Banacha.

Najpierw nasze równanie nieliniowe

przekształcamy (dobierając odpowiednią funkcję ) do równania równoważnego (tzn. mającego te same rozwiązania)

Następnie, startując z pewnego przybliżenia początkowego , konstruujemy ciąg kolejnych przybliżeń według wzoru

Twierdzenie Banacha, o zbieżności iteracji prostej

Niech  będzie domkniętym 

podzbiorem dziedziny ,

w którym jest odwzorowaniem zwężającym. To znaczy, , oraz istnieje stała taka, że

Wtedy równanie (Uzupelnic: rrw ) ma dokładnie jedno rozwiązanie , oraz

dla dowolnego przybliżenia początkowego .

Dowód

Wobec

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \displaystyle \aligned \| x_k- x_{k-1}\| &= \|\phi( x_{k-1})-\phi( x_{k-2})\| \,\le\,L\,\| x_{k-1}- x_{k-2}\| \\ &\le &\cdots\;\le\;L^{k-1}\| x_1- x_0\|, \endaligned}

dla mamy

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \displaystyle \aligned \| x_k- x_s\| &\le & \sum_{j=s+1}^k\| x_j- x_{j-1}\| \,\le\,\sum_{j=s+1}^k L^{j-1}\| x_1- x_0\| \\ &= L^s(1+L+\cdots+L^{k-s-1})\| x_1- x_0\| \,\le\,\frac{L^s}{1-L}\| x_1- x_0\|. \endaligned}

Ciąg jest więc ciągiem Cauchy'ego. Stąd istnieje granica , która należy do , wobec domkniętości tego zbioru. Ponieważ lipschitzowskość implikuje jej ciągłość, mamy też

tzn. jest punktem stałym odwzorowania . Dla jednoznaczności zauważmy, że jeśliby istniał drugi, różny od , punkt stały , to mielibyśmy

Stąd , co jest sprzeczne z założeniem, że

jest zwężająca. End of proof.gif