Newtonova metoda

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

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

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

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

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

tj.

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

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

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

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

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

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

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

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

pa je

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

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

Iz (3.9) slijedi da je

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

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

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

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

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

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

i (3.9) slijedi

$$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)$$

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

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

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

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

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

odnosno

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

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

mora biti

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

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

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

Newtonova metoda daje

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

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

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

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

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

Izlazi da se $b$ mora nalaziti između

$$\frac{1 - \sqrt{1 - a\,c}}{c} ,$$   i$$\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

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

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

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

Tada je

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

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