next up previous contents
Next: Modifikacije Newtonove metode Up: Rješavanje jednadžbi Previous: Metoda iteracije   Contents


Newtonova metoda

Neka je $ f:[a,b]\rightarrow{}R$ klase $ C^2$ na $ [a,b].$ Želimo riješiti jednadžbu

$\displaystyle f(x) = 0.$

Netwonova metoda, koja se često zove Newton-Raphsonova metoda ili metoda tangente, sastoji se u sljedećem. Pretpostavimo da nam je poznata $ n$-ta aproksimacija $ x_n$ rješenja $ s$ i da želimo naći $ n+1$-vu aproksimaciju $ x_{n+1}.$ Taylorova formula za funkciju $ f$ za $ n=1$ u točki $ x_n$ glasi

$\displaystyle f(x) = f(x_n) + f'(x_n)\,(x-x_n) + \frac{f''(c_x)}{2!}(x-x_n)^2.$

Stavimo $ x=x_{n+1}.$ Imamo

$\displaystyle f(x_{n+1}) = f(x_n) + f'(x_n)\,(x_{n+1}-x_n) +
\frac{f''(c_x)}{2!}(x_{n+1}-x_n)^2.$

Pretpostavimo da je $ x_{n+1}$ toliko blizu rješenju da $ f(x_{n+1})$ možemo zanemariti, i da je $ x_{n+1}-x_n$ tako malo da $ (x_{n+1}-x_n)^2$ možemo također zanemariti. Ostaje

$\displaystyle f(x_n) + f'(x_n)\,(x_{n+1}-x_n) = 0,$ (3.7)

tj.

$\displaystyle x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}.$

Time smo dobili sljedeći algoritam.

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

$\displaystyle x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)},\hspace{1cm}n=1,2,3,\ldots\ .$ (3.8)

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

Objasnimo sada zašto se ova metoda zove još i metoda tangente. Jednadžba tangente na graf funkcije $ f$ u točki $ (x_n,f(x_n))$ je

$\displaystyle y = f(x_n) + f'(x_n)\,(x-x_n).$

Kad stavimo $ y=0,$ dobijemo njezino sjecište s osi

$\displaystyle x=x_n-\frac{f(x_n)}{f'(x_n)}.$

Tako vidimo da je $ n+1$-va aproksimacija $ x_{n+1}$ dobivena kao sjecište tangente na graf $ \Gamma_f$ funkcije $ f$ u točki, čija je apscisa $ n$-ta aproksimacija rješenja, s osi $ x.$

slika

Teorem 22   Neka je $ f:[a,b]\rightarrow{}R$ klase $ C^2[a,b],$ i neka vrijedi
1.
$ f(a)\,f(b)<0,$
2.
$ f'(x)\neq 0$ za svaki $ x\in{}[a,b],$
3.
$ f''(x)\leqslant{}0$ ili $ f''(x)\geqslant{}0$ za svaki $ x\in{}[a,b],$
4.
ako je $ c$ ona rubna točka segmenta $ [a,b],$ u kojoj je $ \vert f'(x)\vert$ manji, onda je

$\displaystyle \left\vert\frac{f(c)}{f'(c)}\right\vert\leqslant{}b-a.$

Tada Newtonova metoda konvergira k rješenju jednadžbe $ f(x)=0$ za bilo koju početnu aproksimaciju $ x_0\in{}[a,b].$


Dokaz. Kombinirajući uvjete iz teorema, mogli bismo promatrati razne slučajeve, no može se pokazati da se svaki od njih, uzimajući $ -f$ umjesto $ f$ i/ili $ -x$ umjesto $ x,$ može svesti na slučaj

$\displaystyle f(a)<0,\hspace{1cm}f(b)>0,\hspace{1cm}f''(x)\leqslant{}0,\hspace{1cm}c=b.$

Iz 2. uvjeta i neprekidnosti funkcije $ f'$ slijedi $ f'(x)>0$ ili $ f'(x)<0$ za svaki $ x\in{}[a,b].$ Prema tome funkcija $ f$ na segmentu $ [a,b]$ raste ili pada. Kako je $ f(b)>f(a),$ funkcija $ f$ raste. Osim toga iz $ f''(x)\leqslant{}0$ slijedi da je $ f$ konkavna. Dakle graf funkcije $ f$ izgleda kao na slici
slika
Osim toga za proizvoljan $ \xi\in[a,b]$ vrijedi

$\displaystyle f(x) = f(\xi)+f'(\xi)\,(x-\xi)+\frac{f''(x_{\xi})}{2!}\,(x-\xi),\hspace{1cm}
\forall{}x\in[a,b],$

pa je

$\displaystyle f(x)\leqslant{}f(\xi)+f'(\xi)\,(x-\xi),\hspace{1cm}\forall{}x\in[a,b],$ (3.9)

tj. tangenta u bilo kojoj točki se nalazi iznad grafa funkcije $ f.$
Razmotrimo najprije slučaj $ a\leqslant{}x_0\leqslant{}s,$ gdje je $ s$ jedinstveno rješenje jednadžbe $ f(x)=0.$ Za takav $ x_0$ je $ f(x_0)\leqslant{}0,$ i $ f'(x_0)>0.$ Prema tome je

$\displaystyle x_1 = x_0-\frac{f(x_0)}{f'(x_0)} \geqslant{} x_0.$

Iz (3.9) slijedi da je

$\displaystyle f(x_0)+f'(x_0)\,(s-x_0)\geqslant{}f(s)=0,$

pa je $ x_0\leqslant{}x_1\leqslant{}s.$ Polazeći od $ x_1,$ na isti način možemo zaključiti da je $ x_1\leqslant{}x_2\leqslant{}s,$ odnosno $ x_0\leqslant{}x_1\leqslant{}x_2\leqslant{}s.$ Nastavljajući tako vidimo da je $ x_0\leqslant{}x_1\leqslant{}x_2\leqslant{}x_3\leqslant{}
\ldots \leqslant{}x_n\leqslant{}\ldots \leqslant{}s.$ Tako smo dobili rastući niz aproksimacija odozgo ograničen. Takav niz ima limes

$\displaystyle \lim_{n\rightarrow{}\infty{}} x_n = x^{\star} \leqslant{}s.$

Zbog neprekidnosti funkcije $ f$ i njezine derivacije $ f',$ imamo

$\displaystyle x^{\star} = \lim_{n\rightarrow{}\infty{}}
x_{n+1}=\lim_{n\rightar...
..._{n\rightarrow{}\infty{}} x_n)}
= x^{\star}-\frac{f(x^{\star})}{f'(x^{\star})}.$

Odatle slijedi $ f(x^{\star})=0,$ pa je tako $ x^{\star}=s.$
Neka je sada $ x_0>s.$ Za $ x_0=b$ imamo

$\displaystyle x_1(b) = b - \frac{f(b)}{f'(b)} = b - \left\vert\frac{f(b)}{f'(b)}\right\vert
\geqslant{} b - (b - a) \geqslant{} a.$

Ako je $ s<x_0\leqslant{}b,$ onda iz

$\displaystyle x_1 = x_0 - \frac{f(x_0)}{f'(x_0)},$

i (3.9) slijedi

$\displaystyle 0 = f(x_0)+f'(x_0)\,(x_1-x_0)\leqslant{}f(b) + f'(b)\,(x_0-b) +
f'(x_0)\,(x_1-x_0)$

$\displaystyle \leqslant{}f(b) + f'(b)\,(x_0-b) +
f'(b)\,(x_1-x_0) = f(b) + f'(b)\,(x_1-b).$

Prema tome tangenta u točki $ b$ prolazi iznad točke $ x_1,$ pa se njezino sjecište $ x_1(b)$ s osi $ x$ nalazi lijevo od $ x_1.$ Tako je

$\displaystyle a\leqslant{}x_1(b)\leqslant{}x_1\leqslant{}s.$

Sada smo u situaciji iz prvog dijela dokaza, pa dalje dokaz ide kao tamo. $ \heartsuit$

Primjer 3.1   Neka je $ k>1$ prirodan broj, i neka je $ c>0.$ Nađimo, pomoću Newtonove metode, približnu vrijednost pozitivnog $ k$-tog korijena iz $ c.$

Rješenje. Izračunati $ k$-ti korijen iz broja $ c$ znači riješiti po $ x$ jednadžbu

$\displaystyle x^k - c = 0.$

Ovdje je $ f(x)=x^k - c,$ pa Newtonova metoda daje

$\displaystyle x_{n+1} = x_n - \frac{x_n^k-c}{k\,x_{n}^{k-1}},$

odnosno

$\displaystyle x_{n+1} = \frac{1}{k}\,\left((k-1)\,x_n +
\frac{c}{x_n^{k-1}}\right).$

Što se tiče izbora početne aproksimacije $ x_0$ i konvergencije, primijetimo sljedeće. Za $ 0<a<\sqrt[k]{c}<b$ imamo $ f(a)f(b)<0.$ Zatim, zbog $ f'(x)=kx^{k-1},$ $ f''(x)=k(k-1)x^{k-2},$ za svaki $ x\in
[a,b]$ je $ f'(x)>0,$ i $ f''(x)>0.$ Na kraju, iz pozitivnosti funkcije $ f''$ slijedi rast funkcije $ f',$ pa je $ a$ onaj rub segmenta u kojem $ f'$ ima manju vrijednost. Da bi vrijedilo

$\displaystyle \left\vert\frac{f(a)}{f'(a)}\right\vert \leqslant{}b-a$

mora biti

$\displaystyle b\geqslant{}\frac{a\,\left(1-\frac{c}{a^k} + k \right)}{k}.$

Dakle za tako veliki $ b$ ispunjeni su svi uvjeti teorema 22. Kako $ b$ smijemo uzeti još veći, i kako $ a$ može biti bilo koji broj veći od $ 0,$ i manji od $ \sqrt[k]{c},$ slijedi da postupak konvergira za svaki $ x_0>0.$

U programskom paketu Mathematica se ovaj postupak programira vrlo jednostavno

Map[Nest[((k-1) # + c/#^(k-1))/k&,x0,#1]&,Range[p]]//N
gdje je p broj aproksimacija koje želimo, a broj x0 je početna aproksimacija. Naravno k je broj korijena koji se vadi.

Specijalno kad je $ k=2,$ imamo formulu za približno računanje drugog korijena

$\displaystyle x_{n+1} = \frac{1}{2}\,\left(x_n +
\frac{c}{x_n}\right).$

Primjer 3.2   Za dani pozitivan broj $ c$ naći približnu vrijednost njemu recipročnog broja bez dijeljenja.

Rješenje. To je isto kao približno riješiti jednadžbu

$\displaystyle f(x) = \frac{1}{x} - c = 0.$

Newtonova metoda daje

$\displaystyle x_{n+1} = x_n + \left( {\frac{1}{x_n} -c} \right) \,{x_n^2} =
x_n\,\left( 2 - c\,x_n \right).$

U ovoj formuli nema dijeljenja, i mi smo riješili zadatak, ako postoji interval u kojem možemo birati početnu aproksimaciju tako da ovaj postupak konvergira. Ispitajmo uvjete teorema 22 u ovom slučaju.

$\displaystyle f'(x) = -{x^{-2}} < 0,\hspace{1cm}f''(x) = 2\,x^{-3} > 0.$

Neka su sada $ a,b$ takvi da je $ a<c^{-1}<b.$ Time je uvjet $ f(a)f(b)<0$ ispunjen. Iz pozitivnosti $ f''$ slijedi da $ f'$ raste. No $ f'$ ima negativne vrijednosti, pa iz rasta $ f'$ slijedi da $ \vert f'\vert$ pada. Tako $ \vert f'\vert$ prima manju vrijednost u rubnoj točki $ b.$

$\displaystyle \left\vert\frac{f(b)}{f'(b)}\right\vert = b\,\left(b\,c -1 \right),$

pa $ b$ određujemo iz kvadratne nejednadžbe

$\displaystyle b\,\left(b\,c -1 \right) \leqslant{} b-a.$

Izlazi da se $ b$ mora nalaziti između

$\displaystyle \frac{1 - \sqrt{1 - a\,c}}{c} ,$   i$\displaystyle \hspace{1cm}\frac{1 + \sqrt{1 -
a\,c}}{c}.$

Budući da $ a>0$ možemo uzeti po volji malen, slijedi da se za $ b$ može uzeti bilo koji broj manji od $ 2c^{-1}.$ Tako se za početnu aproksimaciju može uzeti bilo koji $ x_0$ takav da je

$\displaystyle 0 < x_0 < 2\,c^{-1}.$

Ako želimo ocijeniti grešku, primijetimo da je Newtonova metoda zapravo metoda iteracije, ako stavimo

$\displaystyle \varphi(x) = x-\frac{f(x)}{f'(x)}.$

Tada je

$\displaystyle \varphi'(x) = 1-\frac{f'(x)}{f'(x)} + \frac{f(x)\,f''(x)}{f'(x)^2} =
\frac{f(x)\,f''(x)}{f'(x)^2}.$

Neka je

$\displaystyle \left\vert\frac{f(x)\,f''(x)}{f'(x)^2}\right\vert\leqslant L < 1,\hspace{1cm}\forall x\in
[a,b].$

Tada je apriorna ocjena greške dana formulom (3.5), a aposteriorna formulom (3.6).




next up previous contents
Next: Modifikacije Newtonove metode Up: Rješavanje jednadžbi Previous: Metoda iteracije   Contents
Salih Suljagic
1999-01-27