next up previous contents
Next: Newtonova metoda Up: Rješavanje jednadžbi Previous: Metoda polovljenja   Contents


Metoda iteracije

Napišimo jednadžbu (3.1) u obliku

$\displaystyle x = \varphi(x)$ (3.3)

Riješiti jednadžbu sada znači naći takav $ s\in [a,b]$ da vrijedi $ \varphi(s)=s.$ 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

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

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

slike
Geometrijski to znači da tražimo presjek grafa funkcije i pravca $ y=x.$ Može se dogoditi da ne postoji rješenje, da postoji ali da ga ne možemo dostići ovom metodom, ili da postoji i da nam je dostupno. Da bi ova metoda funkcionirala, moraju brojevi $ x_1,x_2,x_3,\ldots{}$ biti u $ [a,b]$ za bilo koju početnu aproksimaciju. To će svakako biti ispunjeno, ako je $ \varphi([a,b])\subset [a,b].$ A kako je funkcija $ \varphi$ još i neprekidna, onda postoji bar jedna točka presjeka.

Teorem 21   Neka je
1.
$ \varphi:[a,b]\rightarrow{}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.4) 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,

$\displaystyle \vert s_1-s_2\vert = \vert\varphi(s_1)-\varphi(s_2)\vert
\leqslan...
...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$ niz $ (x_n)$ konvergira k rješenju $ s.$ Imamo

$\displaystyle \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

$\displaystyle \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

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

pa je prema tome

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

tj.

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

$ \heartsuit$

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

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

slijedi

$\displaystyle \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$

$\displaystyle \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

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

Iz gornje nejednakosti slijedi

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

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

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

po formuli za sumu geometrijskog reda. Tako je

$\displaystyle \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

$\displaystyle \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

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

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

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

Doista,

$\displaystyle \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
$

$\displaystyle \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$

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

$\displaystyle = \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.$

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

$\displaystyle \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

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


next up previous contents
Next: Newtonova metoda Up: Rješavanje jednadžbi Previous: Metoda polovljenja   Contents
Salih Suljagic
1999-01-27