PKow

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Flash

<flash>file=Test19.swf|width=750|height=530</flash> http://osilek.mimuw.edu.pl/images/2/29/Test19.swf

Metoda iteracji prostej Banacha

&#0025; 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

ma dokładnie jedno rozwiązanie , oraz

dla dowolnego przybliżenia początkowego .

Dowód

Wobec

dla mamy

Parser nie mógł rozpoznać (nieznana funkcja „\begin{matrix}”): {\displaystyle \begin{matrix} \| 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\|. \end{matrix}}

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

Z powyższych rozważań otrzymujemy natychmiastowy wniosek dotyczący zbieżności iteracji prostych.

Wniosek

Przy założeniach Uzupe�nij: twierdzenia Banacha, metoda iteracji prostych jest zbieżna co najmniej liniowo z ilorazem , tzn.

Przykład

Dla ilustracji, rozpatrzmy natępujące proste równanie skalarne:

W tym przypadku . Zauważamy, że w przedziale funkcja jest zwężająca ze stałą

Stąd istnieje dokładnie jedno rozwiązanie naszego równania w przedziale . Rozwiązanie to może być aproksymowane z dowolnie małym błędem przy pomocy iteracji prostych, startując z dowolnego przybliżenia początkowego .

Zaletą iteracji prostych jest fakt, że zbieżność nie zależy od wymiaru zadania, ale tylko od stałej Lipschitza (jednak w praktyce czasem sama stała Lipschitza może zależeć od wymiaru zadania...). Metoda Banacha ma szczególne zastosowanie w przypadku, gdy funkcja jest zwężająca na całym zbiorze , tzn. . Jeśli ponadto ma skończoną średnicę , to dla osiągnięcia -aproksymacji zera funkcji wystarczy wykonać

iteracji, niezależnie od . Metody zbieżne dla dowolnego przybliżenia początkowego, nazywamy zbieżnymi globalnie. Obie przedstawione dotychczas metody: bisekcji i Banacha, przy rozsądnych założeniach, są zbieżne globalnie.

Okazuje się, że metoda iteracji prostej może być --- w bardzo szczególnych przypadkach --- zbieżna szybciej niż liniowo. Z taką sytuacją będziemy mieli, gdy korzystać będziemy z metody Newtona.

Wyznaczanie wektorów i wartości własnych

Przykład Moj przykład

Tekst

Algorytm Nie robiący nic


 Leż
Wersja A
Wersja B
Wersja A
Wersja B

Ćwiczenie: Ciag dalszy

Spróbuj obniżyć koszt wyznaczania dla dużych !

Wskazówka
Rozwiązanie