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

$f(x)=0$

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

$x=\varphi (x).$

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

$x_k=\varphi (x_{k-1}),k\ge 1$

Twierdzenie Banacha, o zbieżności iteracji prostej

Niech $D_0$ będzie domkniętym podzbiorem dziedziny $D$,

${\bar{D}}_0=D_0\subset D,$

w którym $\varphi$ jest odwzorowaniem zwężającym. To znaczy, $\varphi (D_0)\subset D_0$, oraz istnieje stała $0\le L<1$ taka, że

$\Vert \varphi (x)-\varphi (y)\Vert \le L\Vert x-y\Vert ,\mathrm{\forall }x,y\in D_0.$

Wtedy równanie

$x=\varphi (x).$

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

$x^{*}=\underset{k\to \mathrm{\infty }}{\lim }{x}_k,$

dla dowolnego przybliżenia początkowego $x_0\in D_0$.

Dowód

Wobec

$\begin{array}{ccccc}\Vert x_k-x_{k-1}\Vert & =& \Vert \varphi (x_{k-1})-\varphi (x_{k-2})\Vert & \le & L\Vert x_{k-1}-x_{k-2}\Vert \\ & \le & \cdots & \le & L^{k-1}\Vert x_1-x_0\Vert ,\end{array}$

dla $k\ge 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 $\{x_k{\}}_k$ jest więc ciągiem Cauchy'ego. Stąd istnieje granica $\overrightarrow{\alpha }=\underset{k\to \mathrm{\infty }}{\lim }{x}_k$, która należy do $D_0$, wobec domkniętości tego zbioru. Ponieważ lipschitzowskość $\varphi$ implikuje jej ciągłość, mamy też

$\varphi (\overrightarrow{\alpha })=\varphi \left(\underset{k\to \mathrm{\infty }}{\lim }{x}_k\right)=\underset{k\to \mathrm{\infty }}{\lim }\varphi (x_k)=\underset{k\to \mathrm{\infty }}{\lim }{x}_k=\overrightarrow{\alpha }$,

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

$\Vert \overrightarrow{\alpha }-\overrightarrow{\beta }\Vert =\Vert \varphi (\overrightarrow{\alpha })-\varphi (\overrightarrow{\beta })\Vert \le L\Vert \overrightarrow{\alpha }-\overrightarrow{\beta }\Vert .$

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

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

$\Vert x_k-x^{*}\Vert \le L^k\Vert x_0-x^{*}\Vert$

Przykład

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

$x=\cos (x),\text{dla}x\in D=R.$

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

$L=\underset{0\le x\le 1}{\max }|{\cos }^{\prime }(x)|=\sin (1)<1$

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

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

$k=k(ϵ)=\lceil \frac{\log (\Vert x_0-x^{*}\Vert /ϵ)}{\log (1/L)}\rceil =\lceil \frac{\log (\text{diam}(D)/ϵ)}{\log (1/L)}\rceil$

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

Wskazówka

Rzecz w tym, że dla dużych $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 $x\ge 0$.

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

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

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