Newtonova metoda

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

$$f(x) = 0.$$

Newtonova metoda, koja se često zove Newton-Raphsonova metoda ili metoda tangente, sastoji se u tome da se $n+1$-va aproksimacija $x_{n+1}$ odredi kao sjecište tangente na graf funkcije $f$ u točki s apscisom $x_n$ s osi $x.$

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,$ a to je $n+1$-va aproksimacija $x_{n+1}.$ Dakle

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

Odatle slijedi

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

Mathematica program 3   (Newtonova metoda)

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

Primjer 3.5   Newtonovom metodom riješiti jednadžbu iz primjera 3.1.

Rješenje. Pomoću programa 3 s početnom aproksimacijom $x_0=-1$ dobivamo

$$x_1 = -1.5,\quad x_2 = -1.34783,\quad x_3 = -1.3252,\quad x_4 = -1.32472,\quad x_5 = -1.32472,$$

$$x_6 = -1.32472,\quad x_7 = -1.32472,\quad x_8 = -1.32472,\quad x_9 = -1.32472,\quad x_{10} = -1.32472$$

i to je sve, jer se nakon 10 iteracija postiže strojna točnost. To pokazuje da Newtonova metoda iteracije u ovom slučaju vrlo brzo konvergira.

Primjer 3.6   Riješiti problem iz primjera 3.2 Newtonovom metodom.

Rješenje. Pomoću programa 3 s početnom aproksimacijom $x_0=1$ dobivamo

$$x_1 = 0.874047,\quad x_2 = 0.8604,\quad x_3 = 0.860334,\quad x_4 = 0.860334.$$

Program je napravljen tako da ponavlja iteracije 100 puta ili završava postupak kad postigne strojnu točnost. Ovo pokazuje da je u ovom primjeru strojna točnost postignuta već u četvrtoj aproksimaciji.

S druge strane ako s istim programom (Newtonovom metodom) pokušamo riješiti jednadžbu

$$(x-1)^{21} = 0,$$

počevši s $x_0=0,$ dobivamo $x_{100}=0.992396.$ S sruge strane jasno je da je rješenje $s = 1.$ To pokazuje da konvergencija nije uvijek tako brza kao u prethodnim primjerima. Dapače, ako pokušamo na isti način riješiti jednadžbu

$${\rm Arctg}\,x = 0$$

počevši s $x_0=2,$ dobivamo redom $x_1=-3.53574,$ $x_2=13.951,$ $x_3=-279.344,$ $x_4=122017,$ $x_5=-2.3386\times 10^{10},$ itd. Aproksimacije se sve više udaljavaju od rješenja koje je očito $x=0.$ Sljedeći teorem je jedan od mnogih koji daju dovoljne uvjete da Newtonova metoda konvergira. Uvjerite se da su uvjeti teorema ispunjeni za primjer 3.5 na segmentu $[-2,-1].$

Teorem 24   Neka je $f:[a,b]\rightarrow{}\mathbb{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],$ tj. funkcija je konkavna ili konveksna na $[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 jedinstvenom 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 može svesti na slučaj

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

uzimajući $-f$ umjesto $f$ i/ili $-x$ umjesto $x.$ 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

Dapače, iz $f'(x)>0$ slijedi da $f$ strogo raste, pa je rješenje jedinstveno. 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\righta... ...{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.7   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,$ $f'(x)=k\,x^{k - 1},$ 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(\frac{c}{a^k} + k -1\right)}{k}.$$

Dakle za tako veliki $b$ ispunjeni su svi uvjeti teorema 24. 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

Mathematica program 4   ($k$-ti korijen)

 
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 jednostavnu i vrlo efikasnu formulu za približno računanje drugog korijena

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

Uvjerite se na primjerima kako je formula za računanje drugog korijena efikasna.

Primjer 3.8   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 24 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.6), a aposteriorna formulom (3.7).

Primjer 3.9   Naći $L$ u slučaju približnog računanja drugog korijena po formuli (3.10).

Rješenje. Treba naći približnu vrijednost od $\sqrt{c}.$ Neka je

$$n^2 \leqslant{} c < (n+1)^2,\qquad n \in N$$

Prirodno je početnu aproksimaciju uzeti u segmentu $[n,n+1].$ Tada je

$$L \leqslant{} \max{}\left\vert\frac{f(x)\,f''(x)}{f'(x)^2}\right\vert, \quad \forall{}x \in [n,n+1].$$

U ovom slučaju je

$$f(x) = x^2 - c,\quad f'(x) = 2\,x,\quad f''(x) = 2,$$

pa je

$$L \leqslant{} \max_{x \in [n,n+1]}\left\vert\frac{x^2-c}{4\,x^2}\... ...ght\vert \leqslant{} \frac{1}{4}\,\left\vert 1 - \frac{n}{(n+1)^2}\right\vert.$$

Odavde se vidi da je uvijek $L<\frac{1}{4}.$