PKow

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

$\displaystyle f(x)=0$

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

$\displaystyle x\,=\,\phi (x).$

Następnie, startując z pewnego przybliżenia początkowego $\displaystyle x_{0}$, konstruujemy ciąg kolejnych przybliżeń $\displaystyle x_{k}$ według wzoru

$\displaystyle x_{k}\,=\,\phi (x_{k-1}),\qquad k\geq 1.$

Twierdzenie Banacha, o zbieżności iteracji prostej

Niech $\displaystyle D_{0}$ będzie domkniętym podzbiorem dziedziny $\displaystyle D$,

$\displaystyle {\overline {D}}_{0}\,=\,D_{0}\subset D,$

w którym $\displaystyle \phi$ jest odwzorowaniem zwężającym. To znaczy, $\displaystyle \phi (D_{0})\subset D_{0}$, oraz istnieje stała $\displaystyle 0\leq L<1$ taka, że

$\displaystyle \|\phi (x)-\phi (y)\|\,\leq \,L\,\|x-y\|,\qquad \forall x,y\in D_{0}.$

Wtedy równanie

$\displaystyle x\,=\,\phi (x).$

ma dokładnie jedno rozwiązanie $\displaystyle x^{*}$, oraz

$\displaystyle x^{*}\,=\,\lim _{k\to \infty }x_{k},$

dla dowolnego przybliżenia początkowego $\displaystyle x_{0}\in D_{0}$.

Dowód

Wobec

${\begin{matrix}\|x_{k}-x_{k-1}\|&=&\|\phi (x_{k-1})-\phi (x_{k-2})\|&\leq &L\|x_{k-1}-x_{k-2}\|\\\ &\leq &\cdots \;&\leq &\;L^{k-1}\|x_{1}-x_{0}\|,\end{matrix}}$

dla $\displaystyle k\geq s$ 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 $\displaystyle \{x_{k}\}_{k}$ jest więc ciągiem Cauchy'ego. Stąd istnieje granica $\displaystyle {\vec {\alpha }}=\lim _{k\to \infty }x_{k}$, która należy do $\displaystyle D_{0}$, wobec domkniętości tego zbioru. Ponieważ lipschitzowskość $\displaystyle \phi$ implikuje jej ciągłość, mamy też

$\displaystyle \phi ({\vec {\alpha }})\,=\,\phi {\Big (}\lim _{k\to \infty }x_{k}{\Big )}\,=\,\lim _{k\to \infty }\phi (x_{k})\,=\,\lim _{k\to \infty }x_{k}\,=\,{\vec {\alpha }},$

tzn. $\displaystyle {\vec {\alpha }}$ jest punktem stałym odwzorowania $\displaystyle \phi$. Dla jednoznaczności zauważmy, że jeśliby istniał drugi, różny od $\displaystyle {\vec {\alpha }}$, punkt stały $\displaystyle {\vec {\beta }}$, to mielibyśmy

$\displaystyle \|{\vec {\alpha }}-{\vec {\beta }}\|\,=\,\|\phi ({\vec {\alpha }})-\phi ({\vec {\beta }})\|\,\leq \,L\,\|{\vec {\alpha }}-{\vec {\beta }}\|.$

Stąd $\displaystyle 1<L$, co jest sprzeczne z założeniem, że

$\displaystyle \phi$ jest zwężająca.

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 $\displaystyle L$, tzn.

$\displaystyle \|x_{k}-x^{*}\|\,\leq \,L^{k}\,\|x_{0}-x^{*}\|.$

Przykład

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

$\displaystyle x\,=\,\cos(x),\qquad {\mbox{dla}}\qquad x\in D=R.$

W tym przypadku $\displaystyle \phi (x)=\cos(x)$. Zauważamy, że w przedziale $\displaystyle [0,1]$ funkcja $\displaystyle \phi$ jest zwężająca ze stałą

$\displaystyle L\,=\,\max _{0\leq x\leq 1}|\cos '(x)|\,=\,\sin(1)\,<\,1.$

Stąd istnieje dokładnie jedno rozwiązanie naszego równania w przedziale $\displaystyle [0,1]$. 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 $\displaystyle x_{0}\in [0,1]$.

Zaletą iteracji prostych jest fakt, że zbieżność nie zależy od wymiaru $\displaystyle n$ zadania, ale tylko od stałej Lipschitza $\displaystyle L$ (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 $\displaystyle \phi$ jest zwężająca na całym zbiorze $\displaystyle D$, tzn. $\displaystyle D_{0}=D$. Jeśli ponadto $\displaystyle D$ ma skończoną średnicę $\displaystyle {\mbox{diam}}(D)$, to dla osiągnięcia $\displaystyle \epsilon$-aproksymacji zera funkcji $\displaystyle f$ wystarczy wykonać

$\displaystyle k\,=\,k(\epsilon )\,=\,{\Big \lceil }{\frac {\log(\|x_{0}-x^{*}\|/\epsilon )}{\log(1/L)}}{\Big \rceil }\,=\,{\Big \lceil }{\frac {\log({\mbox{diam}}(D)/\epsilon )}{\log(1/L)}}{\Big \rceil }$

iteracji, niezależnie od $\displaystyle x_{0}$. 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 $\displaystyle \exp(x)$ dla dużych $\displaystyle x$!

Wskazówka

Rzecz w tym, że dla dużych $\displaystyle x$, trzeba wziąć bardzo dużo wyrazów w szeregu Taylora. Czy można tak wykombinować, by w rezultacie wziąć ich mniej?

Rozwiązanie

Bez zmieniejszenia ogólności, załóżmy, że $\displaystyle x\geq 0$.

Jeśli $\displaystyle x=k+t$, gdzie $\displaystyle t\in [0,1)$, a $\displaystyle k$ jest całkowite, to oczywiście

$\displaystyle e^{x}=e^{k+t}=e^{k}e^{t}=e^{k}\exp(t).$

Tak więc zadanie redukuje się do wyznaczenia $\displaystyle \exp(t)$ dla małego $\displaystyle t$ oraz do co najwyżej $\displaystyle k$ dodatkowych mnożeń potrzebnych do wyznaczenia całkowitej potęgi $\displaystyle e^{k}$ (ile mnożeń naprawdę wystarczy?). Pamiętaj, przyjęliśmy, że znamy reprezentację numeryczną liczby $\displaystyle e$.

 [Wersja B]
function [y, N] = expb(x, epsilon)
k = floor(x); t = x - k; 
[y, N] = expa(t, epsilon); 
for i = 1:k
 	y *= e;
end
N += (k+2);
end

Wersja B