Newton Raphson-metoden

Newton-Raphson metoden (også kjent som Newtons metode) er ein numerisk metode for å finne nullpunkt for ein funksjon, dvs. å løysa likninga f(x) = 0

Metoden begynner med at vi gjettar på ein verdi x0, som er nær* nullpunktet. Deretter finn vi ein betre verdi x1ved å rekna ut
newtonformel1
Denne prosessen kan vi gjenta så mange ganger vi treng. For kvar verdi xn, så er den neste gitt ved
 Newtonformel2

* Vi skal sjå litt meir på kva "nær" betyr nedanfor.

Geometrisk forklaring

Figuren under viser korleis iterasjonssteget i prosessen fungerer, dvs korleis vi går frå xn til neste x-verdi xn+1:

Vi tegnar inn tangenten til f(x) i punktet x = xn. Linja har stigningstal lik a = f'(xn). Men stigningstalet er også forholdet mellom høyden og bredden i den grøne trekanten, dvs.
 f'(xn) = f(xn) / (xn - xn+1).
Når vi ordnar på denne likninga får vi formelen vår:

Newtonformel2

Vi har no funne eit punkt xn+1 som er nærmare nullpunktet enn xn var, og vi kan fortsetja prosedyren.

Eksempel

La oss sjå på på funksjonen f(x) = x3 -2x +2. (sjå figur under) Vi deriverer og får f'(x) = 3x2 -2. Hvis vi no gjettar på talet x0 =  -1, så treng vi å rekna ut f(-1) = 3, og f'(x) = 1. Då gir formelen oss x1 = -1 - 3/1 = -4.
Deretter får vi sekvensen (avrunda til tre desimaler)  x2 = -2.826, x3 = -2.147, x4 = -1.842, x5 = -1.773, x6 = -1.769,og då er vi allerede omtrent på nullpunktet. Du kan studera dette eksempelet nærmare sjøl.

Vi fant altså svaret (med tre desimalers nøyaktighet) etter bare seks steg, og det viser at metoden konvergerer raskt. Spørsmålet er om den alltid konvergerer?

newtonmetoden eksempel

For å svara på det, kan vi sjå kva som skjer når vi gjettar på x0 = 1,  i staden for -1. Vi får : x1 = 0, x2 = 1, x3 = 0, osv. Som vi forstår: denne sekvensen vil alternera mellom 0 og 1 i det uendelige. Det vil sei at svaret er nei: metoden konvergerer ikkje alltid mot nullpunktet. Hvis vi startar i nærheten av punkta x = 0 eller x = 1, kan vi også bli dradd inn mot disse punkta og til slutt havna i same syklusen som over. Prøv feks x =1.1

Funksjonen har eit lokalt maksimum i x = -0.8165, og eit lokalt minimum i x = -0.8165. Hvis vi tilfeldigvis gjettar på eit slik stasjonært punkt, veit vi at den deriverte er lik null- (f'(x) = 0). Då vil metoden også feila, fordi vi prøver å dela på null. Hvis vi gjettar på x-verdiar i mellom disse punkta, vil tangenten ha negativt stigningstal, og havnar vi lenger ute på x-aksen. Dette kan noken gonger gå bra likevel fordi den neste iterasjonen vil bringa oss nærmare, men som regel vil det feila.

Generelt er det vanskelig å bevisa kor nær ein må vera for at Newton-metoden skal finna nullpunktet. I eksempelet vårt bør ein i alle fall vera til venstre for det lokale toppunktet x = -0.8165.