Metoda iteracije

Napišimo jednadžbu (3.1) u obliku

$$x = \varphi(x)$$ (3.4)

Riješiti jednadžbu sada znači naći takav $s \in [a,b]$ da vrijedi $\varphi(s)=s.$ Geometrijski to znači da tražimo presjek grafa funkcije $\varphi$ i pravca $y=x.$

Imamo sljedeći algoritam

Algoritam 2   (Metoda iteracije) Izaberemo $x_0 \in [a,b],$ i računamo niz $x_n,$ za $n=1,2,3,\ldots{}$ po formuli

$$x_n = \varphi(x_{n-1}).$$ (3.5)

Ako je $x_k = \varphi(x_{k})$ za neki $k,$ onda je $s=x_k.$ U protivnom nastavljamo računanje daljnih članova niza.

Imamo sljedeći program za metodu iteracije

Mathematica program 2   (Metoda iteracije)

 
varphi[t_]=; (* funkcija *) 
x=;          (* pocetna aproksimacija *) 
n=0; 
   While[ 
   N[f[x]]!=x, 
   x=varphi[x]; 
   n=n+1; 
   If[n>100,Break[]]; (* prekid procesa nakon 100 iteracija *) 
   Print[N[x]] 
   ]

Ovaj algoritam dobro opisuje sljedeća slika.

Može se dogoditi da niz aproksimacija dobiven ovim postupkom ne konvergira k rješenju, kao na sljedećoj slici.

Niz može konvergirati k rješenju, kao na sljedećoj slici.

Evo još nekoliko slika, koje pokazuju različito ponašanje iteracijskog niza.

Iz ovih slika, i do sada rečenog, jasno je da moraju biti ispunjeni neki dodatni uvjeti da bi se dogodilo da iteracijski niz konvergira k rješenju. Sljedeći teorem daje takve uvjete.

Teorem 23   Neka je

1. $\varphi:[a,b]\rightarrow{}\mathbb{R}$ funkcija klase $C^1$ na $[a,b],$
2. $\varphi(x)\in{}[a,b]$ za svaki $x\in{}[a,b],$
3. $\left\vert\varphi'(x)\right\vert\leqslant{}L<1,\hspace{1cm}\forall x\in{}[a,b].$

Tada za proizvoljan $x_0\in{}[a,b]$ niz $(x_n)$ definiran algoritmom (3.5) konvergira k jedinstvenom rješenju jednadžbe $x=\varphi(x).$

Dokaz. Dokažimo najprije da postoji barem jedno rješenje. Stavimo $g(x)=x-\varphi(x).$ Prema uvjetima teorema, $g(a)\leqslant{}0,$ i $g(b)\geqslant{}0.$ Budući da je $g$ neprekidna funkcija na segmentu $[a,b],$ slijedi da postoji bar jedan $s \in [a,b]$ takav da je $g(s)=0,$ tj. $s-\varphi(s)=0,$ dakle $s$ je rješenje.
Dokažimo sada da ne postoji više od jednog rješenja. Pretpostavimo da su $s_1$ i $s_2$ dva međusobno različita rješenja. Tada, prema Lagrangeovom teoremu srednje vrijednosti, postoji $\sigma$ između $s_1$ i $s_2$ takav da vrijedi

$$\varphi(s_1)-\varphi(s_2) = \varphi'(\sigma{})\,(s_1 - s_2).$$

Odatle

$$\vert s_1-s_2\vert = \vert\varphi(s_1)-\varphi(s_2)\vert = \left\... ...vert\,\vert s_1-s_2\vert \leqslant{}L\,\vert s_1-s_2\vert < \vert s_1-s_2\vert.$$

što je kontradikcija. Dakle problem ima jedno i samo jedno rješenje $s.$
Preostaje dokazati da za bilo koju početnu aproksimaciju $x_0 \in [a,b]$ niz $(x_n)$ konvergira k rješenju $s.$ Imamo (opet po Lagrangeu)

$$\vert x_n - s\vert = \vert\varphi(x_{n-1}) - s\vert = \vert\varph... ... \vert\varphi'(\xi)\,(x_{n-1} - s)\vert \leqslant{} L\,\vert x_{n-1} - s\vert.$$

Odatle

$$\vert x_n - s\vert \leqslant{} L\,\vert x_{n-1} - s\vert \leqslan... ...\vert x_{n-2} - s\vert \leqslant{} \ldots \leqslant{} L^n\,\vert x_0 - s\vert.$$

Budući da je $0\leqslant{}L<1,$ slijedi

$$\lim_{n\rightarrow{}\infty} L^n = 0,$$

pa je prema tome

$$\lim_{n\rightarrow{}\infty} \vert x_n - s\vert = 0,$$

tj.

$$\lim_{n\rightarrow{}\infty} x_n = s.$$

$\heartsuit{}$

Apriornu ocjenu greške dobivamo na sljedeći način. Iz

$$\vert x_{n+1}-x_n\vert=\vert\varphi(x_n)-\varphi(x_{n-1})\vert = ... ...rt\varphi'(\sigma{})\,(x_{n}-x_{n-1})\vert \leqslant{}L\,\vert x_n-x_{n-1}\vert$$

slijedi

$$\vert x_{n+1}-x_n\vert \leqslant{}L\,\vert x_n-x_{n-1}\vert \leqslant{}L^2\,\vert x_{n-1}-x_{n-2}\vert$$

$$\leqslant{}L^3\,\vert x_{n-2}-x_{n-3}\vert \leqslant{}\ldots\leqslant{}L^n\,\vert x_1-x_0\vert.$$

Za proizvoljni prirodni broj $m>n,$ imamo

$$\vert x_m-x_n\vert\leqslant{}\vert x_m-x_{m-1}\vert+\vert x_{m-1}-x_{m-2}\vert+\cdots +\vert x_{n+1}-x_n\vert.$$

Ako gornju nejednakost primijenimo na svaki od članova na desnoj strani, slijedi

$$\vert x_m-x_n\vert\leqslant{}\left(L^{m-1}+L^{m-2}+\cdots +L^n\right)\vert x_{1}-x_0\vert.$$

Zbog $0\leqslant L<1,$

$$L^{m-1}+L^{m-2}+\cdots +L^n=L^n\left(1+L+L^2+\cdots +L^{m-n-1}\right)$$

$$\leqslant{}L^n\left(1+L+L^2+\cdots\right)=L^n\,\frac{1}{1-L},$$

po formuli za sumu geometrijskog reda. Tako je

$$\vert x_m-x_n\vert\leqslant{}L^n\,\frac{1}{1-L}\,\vert x_1-x_0\vert.$$

Desna strana ove nejednakosti ne ovisi o $m,$ pa prema tome

$$\lim_{m\rightarrow{}\infty{}}\vert x_m-x_n\vert=\vert s-x_n\vert \leqslant{} \frac{L^n}{1-L}\,\vert x_1-x_0\vert.$$

Dakle apriorna ocjena greške $n$-te aproksimacije je

$$\vert x_n-s\vert\leqslant \frac{L^n}{1-L}\,\vert x_1-x_0\vert.$$ (3.6)

Aposteriorna ocjena greške je ocjena koja se računa pomoću dobivenih aproksimacija. U ovom slučaju ona je

$$\left\vert x_k - s\right\vert \leqslant{} \frac{L}{1-L}\left\vert x_k - x_{k-1}\right\vert.$$ (3.7)

Doista,

$$\left\vert x_k - x_{k+p}\right\vert = \left\vert x_k - x_{k+1} + x_{k+1} - x_{k+2} + \cdots{} + x_{k+p-1} - x_{k+p}\right\vert$$

$$\leqslant{} \left\vert x_k - x_{k+1}\right\vert + \left\vert x_{k+1} - x_{k+2}\right\vert + \cdots{} + \left\vert x_{k+p-1} - x_{k+p}\right\vert$$

$$\leqslant{} L\,\left\vert x_{k-1} - x_k\right\vert + L^2\,\left\... ...x_{k-1} - x_k\right\vert + \cdots{} + L^p\,\left\vert x_{k-1} - x_k\right\vert$$

$$= \left(L + L^2 + \cdots{} + L^p\right)\,\left\vert x_{k-1} - x_k\right\vert = L\,\frac{1 - L^p}{1 - L}\,\left\vert x_{k-1} - x_k\right\vert.$$

$$\lim_{p\rightarrow{}\infty{}} \left\vert x_k - x_{k+p}\right\vert = \left\vert x_k - s\right\vert.$$

$$\lim_{p\rightarrow{}\infty{}} L\,\frac{1 - L^p}{1 - L}\,\left\vert x_{k-1} - x_k\right\vert = \frac{L}{1-L}\left\vert x_k - x_{k-1}\right\vert.$$

Tako je

$$\left\vert x_k - s\right\vert \leqslant{} \frac{L}{1-L}\left\vert x_k - x_{k-1}\right\vert.$$

Primjer 3.3   Riješiti metodom iteracije jednadžbu u primjeru 3.1.

Rješenje. Jednadžbu

$$x^3 - x + 1 = 0$$

možemo prepisati u obliku

$$x = \sqrt[3]{x-1}.$$

Tako je

$$\varphi(x) = \sqrt[3]{x-1},\qquad \varphi'(x) = {\frac{1}{3\,{{\left( x-1 \right) }^{{\frac{2}{3}}}}}}$$

Rješenje postoji na segmentu $[-2,-1]$ (v. primjer 3.1). $\varphi'$ je pozitivna, pa funkcija $\varphi$ raste. Njezine vrijednosti na rubovima su

$$\varphi(-2) = \sqrt[3]{-3} = -\sqrt[3]{3} \in [-2,-1],\quad \varphi(-1) = \sqrt[3]{-2} = -\sqrt[3]{2} \in [-2,-1].$$

Kako $\varphi$ raste, $\varphi(x) \in [-2,-1]$ za svaki $x \in [-2,-1].$ Osim toga $\varphi'$ raste na $[-2,-1],$ pozitivna je, pa najveću vrijednost ima u $-1,$ i to

$$\varphi'(-1) = \frac{1}{3\,\sqrt[3]{4}} < \frac{1}{3}.$$

Ova diskusija pokazuje da su uvjeti teorema 23 ispunjeni, pa će iteracijski proces konvergirati bez obzira na to koji broj iz $[-2,-1]$ uzmemo kao početnu aproksimaciju. Ujedno nam ocjena

$$L=\max_{x \in [-2,-1]}\vert\varphi'(x)\vert\leqslant{}\varphi'(-1) \leqslant{}\frac{1}{3}$$

može poslužiti da bismo apriorno ocijenili grešku $k$-te aproksimacije.

Imamo na pr.

$$x_0 = -1, \qquad x_1 = \varphi(-1) = -\sqrt[3]{2} = -1.25992,$$

pa greška $k$-te aproksimacije nije veća od

$$\frac{\frac{1}{3^k}}{1-\frac{1}{3}}\,\vert x_1-x_0\vert = {\frac{{3^{1 - k}}}{2}}\,0.25992 = 0.38988\times 3^{-k}.$$

Ako želimo rješenje točno na pet decimala, izlazi da mora biti $k>12.349,$ dakle trinaesta aproksimacija daje traženu točnost. Pomoću programa 2 nalazimo da je

$$x_{13} = -1.32472.$$

Primjer 3.4   Riješiti zadatak u primjeru 3.2 metodom iteracije. Rješenje. Jednadžbu treba napisati u obliku

$$\lambda{} = \varphi(\lambda{}).$$

Ako stavimo

$$\lambda{} = \frac{1}{{\rm tg}\,\lambda{},}$$

onda je

$$\varphi(\lambda) = \frac{1}{{\rm tg}\,\lambda},$$

$$\varphi'(\lambda) = -\frac{1}{\sin^2 \lambda},$$

pa je

$$\vert\varphi'(\lambda)\vert \geq 1,$$   za svaki $$\lambda.$$

To ne odgovara uvjetima teorema 23. Jednadžbu možemo i drukčije napisati

$$\lambda{} = {\rm Arctg}\,\frac{1}{\lambda{}}.$$

Tada je

$$\varphi(\lambda) = {\rm Arctg}\,\frac{1}{\lambda},$$

$$\varphi'(\lambda) = -\frac{1}{1 + \lambda^2},$$

pa je

$$\vert\varphi'(\lambda)\vert \leq 1,$$   za svaki $$\lambda.$$

Specijalno, $\vert\varphi'(\lambda)\vert=1$ samo za $\lambda=0.$ Domena od $\varphi$ je $\mathbb{R}\setminus\{0\}.$ Budući da je $\varphi'(\lambda)<0,$ funkcija pada na svakom od intervala $\langle -\infty,0\rangle,$ $\langle{}0,\infty{}\rangle{}.$ Nas interesiraju samo pozitivna rješenja, pa nam je interesantan samo interval $\langle{}0,\infty{}\rangle{}.$ Na tom intervalu

$$\lim_{\lambda{}\rightarrow{}0+} {\rm... ...ad \lim_{\lambda{}\rightarrow{}\infty{}} {\rm Arctg}\, \frac{1}{\lambda{}} = 0.$$

Dakle $\varphi$ preslikava $\langle{}0,\infty{}\rangle{}$ na $\langle{}0,\frac{\pi}{2}\rangle{}.$ Također, ako je $\lambda=1,$ onda je

$${\rm Arctg}\,\frac{1}{\lambda} = {\rm Arctg}\,1 = \frac{\pi}{4} \approx 0.785.$$

Zatim, ako uzmemo $\lambda=\frac{\pi}{4},$ onda je

$${\rm Arctg}\,\frac{1}{\lambda} = {\rm Arctg}\,\frac{4}{\pi} = 0.905023 < 1,$$

pa $\varphi$ preslikava segment $[\frac{\pi}{4},1]$ u samog sebe. Apsolutna vrijednost derivacije je najveća na lijevom rubu, jer je tada nazivnik najmanji. Tako možemo staviti

$$L = \frac{1}{1+\left(\frac{\pi}{4}\right)^2} = \frac{16}{16+\pi^2} \leqslant{} \frac{16}{25} = 0.64.$$

To znači da će metoda iteracije konvergirati uzmemo li bilo koji broj iz segmenta $[\frac{\pi}{4},1]$ kao početnu aproksimaciju. Pomoću programa 2 nalazimo da je zaokruženo na šest decimala, uz $x_0=1,$

$$x_{21} = 0.860332,\quad x_{22} = 0.860334,\quad x_{23} = 0.860333,$$

$$x_{24} = 0.860334,\quad x_{25} = 0.860333,\quad x_{26} = 0.860334,$$

i dalje se ovaj broj ponavlja.^3.1