Methode van Newton-Raphson

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

De methode van Newton-Raphson, ook bekend als de methode van Newton, is een numerieke iteratiemethode om de nulpunten te bepalen van een differentieerbare functie, zoals een polynoom of een transcendente functie. Het algoritme convergeert onder gunstige omstandigheden vrij snel, namelijk kwadratisch: de fout na de n+1-de iteratie is evenredig met het kwadraat van de fout na de n-de iteratie. De methode construeert in elke volgende stap een volgende benadering met behulp van de eerste afgeleide en de functiewaarde in de huidige benadering van het nulpunt. De methode is niet altijd stabiel.

In de praktijk worden meer stabiele en snellere numerieke methoden gebruikt om de nulpunten van functies te bepalen, zoals de methode van Edmond Halley, die een uitbreiding is van de methode van Newton. De meeste methoden gebruiken tweede (en hogere) afgeleiden en een polynoom van een tweede (of hogere) graad om de nulpunten van een functie te bepalen.

Definitie[bewerken]

Algoritme van Newton-Raphson.PNG

Gegeven een functie f(x) en zijn afgeleide f'(x); we zoeken het nulpunt van die functie, startend vanaf een initiële waarde x0, dan benadert xn het nulpunt:

x_1=x_0-\frac{f(x_0)}{f'(x_0)} en verder algemeen:
x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}.

Afleiding[bewerken]

We definiëren de functie f(x), die een nulpunt heeft voor x=α : f(α)=0. Onze initiële iteratieterm noemen we x0, h is het verschil tussen α en x0, zodat

f(x_0+h)=f(\alpha)=0

We zoeken nu de verschilterm h. We gebruiken de stelling van Taylor, die een benadering van de functie f in de omgeving van x geeft:

\! 0=f(\alpha)=f(x_0+h) = f(x_0)+h f'(x_0)+...

We verwaarlozen de termen van tweede orde, en willen de grootte van de correctieterm op x_0, h, te weten komen:

h=-\frac{f(x_0)}{f'(x_0)} (de afgeleide f'(x_0) wordt niet nul verondersteld).

Onze betere schatting voor het nulpunt, x1, is dan x0 aangepast met h:

x_1=x_0+h=x_0-\frac{f(x_0)}{f'(x_0)}.

Dit kunnen we herhalen, de volgende stap is (x1 werd hierboven bepaald):

x_2=x_1+h=x_1-\frac{f(x_1)}{f'(x_1)},

en algemeen:

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

Meetkundige interpretatie[bewerken]

NewtonIteration Ani.gif
  1. Kies een punt x0 op de x-as nabij het nulpunt α;
  2. Construeer een loodrechte op de x-as, door x0;
  3. Construeer de raaklijn door f(x0) aan de kromme f(x);
  4. De nieuwe benadering x1 wordt gegeven door het snijpunt van de raaklijn met de x-as.

Voorbeeld[bewerken]

Nulpuntsbepaling van f(x)=cos(x); de initiële waarde is x0=1:

x_{n+1}=x_n-\frac{\cos(x_n)}{-\sin(x_n)}=x_n+\cot(x_n). het gezochte nulpunt is dan x=\frac{\pi}{2}=1,570796327

Dat resulteert in:

x0= 1
x1= 1,642092616; fout: 7,1e-2
x2= 1,570675277; fout: 1,2e-4
x3= 1,570796327; fout: 5,9e-13

Reeds na drie iteraties wordt een benadering verkregen die zelden te wensen overlaat. Let erop dat de exponent bij iedere iteratiestap ongeveer verdubbelt, dit is een kenmerk van kwadratische convergentie.

De methode is ook goed bruikbaar voor :

  • stelsels van n niet-lineaire algebraïsche vergelijkingen in n onbekenden. In dat geval moeten de scalaire veranderlijken vervangen worden door matrices. In plaats van de afgeleide komt de Jacobiaan.
  • het vinden van extremen van een scalaire functie in een n-dimensionale ruimte;

\frac{1}{f'(x_n)} wordt dan vervangen door de inverse Hessiaan. Afhankelijk van de beschikbaarheid van analytische uitdrukkingen van de eerste en tweede afgeleiden van f zijn er allerlei varianten op deze methode, waarbij de afgeleiden hetzij exact berekend, hetzij benaderd worden uit opeenvolgende iteratieslagen.