Methode van Newton-Raphson

Uit Wikipedia, de vrije encyclopedie
Naar navigatie springen Naar zoeken springen

De methode van Newton-Raphson, ook bekend als de methode van Newton of kortweg Newton-Raphson, is een numerieke iteratiemethode om de nulpunten te bepalen van een differentieerbare functie, zoals een polynoom of een transcendente functie. De methode is genoemd naar Isaac Newton, die de methode bedacht, en Joseph Raphson, die er een formele beschrijving van gaf. Het algoritme convergeert onder gunstige omstandigheden vrij snel, namelijk kwadratisch: de fout na de -ste iteratie is evenredig met het kwadraat van de fout na de -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

De methode van Newton-Raphson benadert een nulpunt van een differentieerbare functie , uitgaande van de startwaarde , iteratief door de recursieve betrekking:

Motivering[bewerken]

De functie heeft een nulpunt voor , dus . Noem het verschil tussen het nulpunt en de benadering , zodat

De stelling van Taylor geeft een benadering van in de omgeving van :

Onder verwaarlozing van de termen van tweede orde krijgt men een benadering van :

(de afgeleide wordt ongelijk aan nul verondersteld).

Een betere benadering voor het nulpunt is dan:

Samen met de startwaarde geeft dit een recursieve procedure voor het benaderen van het nulpunt .

Merk op dat het snijpunt met de x-as is van de raaklijn aan de grafiek van in het punt , gegeven door de formule

Meetkundige interpretatie[bewerken]

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

Geschiedenis[bewerken]

Isaac Newton schreef in de periode 1664-1671 het werk Methodus fluxionum et serierum infinitarum (Latijn voor: "De methode van afgeleiden en oneindige rijen"). Daarin verklaart hij een nieuw algoritme voor het oplossen van veeltermvergelijkingen aan de hand van het voorbeeld . Hiervoor kan men gemakkelijk raden dat het punt een eerste benadering is. Newton maakte de veronderstelling dat met een waarvan wordt aangenomen dat deze "klein" is, en vult deze in de vergelijking in:

zodat

Omdat verondersteld wordt "klein" zijn, worden de termen met en genegeerd, waarna

, dus

overblijft als betere benadering.

Deze procedure kan nu herhaald worden door te stellen en in te vullen in de de vergelijking voor .

zodat

Weer worden de termen van hogere orde weggelaten, waarna:

Joseph Raphson beschreef dit rekenproces formeel in 1690 in het werk Analysis Aequationum universalis, en illustreerde het formalisme met de algemene derdegraadsvergelijking, waar hij de onderstaande iteratieregel vond. [1]

De abstracte vorm van deze werkwijze

met gebruik van de afgeleide is van Thomas Simpson.

Voorbeeld[bewerken]

Nulpuntsbepaling van . met als startwaarde . De recursieformule is:

en het gezochte nulpunt is

Iteratie resulteert in:

; fout: 7,1×10−2
; fout: 1,2×10−4
; fout: 5,9×10−13

Reeds na drie iteraties wordt een benadering verkregen die al erg nauwkeurig is. Merk op dat de exponent van de fout bij iedere iteratiestap minstens verdubbelt; dit is een kenmerk van kwadratische convergentie.

De methode is ook goed bruikbaar voor:

  • stelsels van niet-lineaire algebraïsche vergelijkingen in 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 -dimensionale ruimte; wordt dan vervangen door de inverse hessiaan. Afhankelijk van de beschikbaarheid van analytische uitdrukkingen van de eerste en tweede afgeleiden van zijn er allerlei varianten op deze methode, waarbij de afgeleiden hetzij exact berekend, hetzij benaderd worden uit opeenvolgende iteratieslagen.

Zie ook[bewerken]


Referenties[bewerken]

  1. Xavier Gourdon: Newton’s method and high order iterations, kopie in postscript-bestand