Methode van Newton-Raphson
De methode van Newton-Raphson, ook bekend als de methode van Newton of kortweg Newton-Raphson, is een iteratiemethode uit de numerieke wiskunde om de nulpunten te bepalen van een differentieerbare functie, zoals van een polynoom of een transcendente functie. De methode is naar Isaac Newton genoemd, 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 ( n + 1 ) {\displaystyle (n+1)} -ste iteratie is evenredig met het kwadraat van de fout na de n {\displaystyle 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.
-ste iteratie is 
-de iteratie. De methode construeert in elke volgende stap een volgende benadering met behulp van de eerste De regula falsi convergeert trager dan de methode van Newton-Raphson, maar is stabieler. In de praktijk worden meer stabiele en snellere numerieke methoden dan de methode van Newton-Raphson 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.
Geschiedenis
Isaac Newton schreef in de periode 1664-1671 het werk Methodus fluxionum et serierum infinitarum, Latijn voor: De methode van afgeleiden en oneindige rijen en beschreef daarin een nieuw algoritme voor het oplossen van veeltermvergelijkingen aan de hand van het voorbeeld y 3 − 2 y − 5 = 0 {\displaystyle y^{3}-2y-5=0} .
.
Joseph Raphson beschreef het rekenproces in 1690 in het werk Analysis Aequationum universalis en illustreerde het met de algemene derdegraadsvergelijking, waar hij de onderstaande iteratieregel vond.
De abstracte vorm van deze werkwijze
x n + 1 = x n − f ( x n ) f ′ ( x n ) {\displaystyle x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})}}}
met gebruik van de afgeleide is van Thomas Simpson.
Definitie
De methode van Newton-Raphson benadert een nulpunt van een differentieerbare functie f {\displaystyle f} , uitgaande van de startwaarde x 0 {\displaystyle x_{0}} , iteratief door de recursieve betrekking:
x n + 1 = x n − f ( x n ) f ′ ( x n ) {\displaystyle x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})}}}
, uitgaande van de startwaarde
x
0
{\displaystyle x_{0}}
, iteratief door de Verklaring
De functie f ( x ) {\displaystyle f(x)} heeft een nulpunt voor x = α {\displaystyle x=\alpha } , dus f ( α ) = 0 {\displaystyle f(\alpha )=0} . Noem h n = α − x n {\displaystyle h_{n}=\alpha -x_{n}} het verschil tussen het nulpunt α {\displaystyle \alpha } en de benadering x n {\displaystyle x_{n}} , zodat
f ( x n + h n ) = f ( α ) = 0 {\displaystyle f(x_{n}+h_{n})=f(\alpha )=0}
heeft een nulpunt voor
x
=
α
{\displaystyle x=\alpha }
, dus
f
(
α
)
=
0
{\displaystyle f(\alpha )=0}
. Noem
h
n
=
α
−
x
n
{\displaystyle h_{n}=\alpha -x_{n}}
het verschil tussen het nulpunt
α
{\displaystyle \alpha }
en de benadering
x
n
{\displaystyle x_{n}}
, zodat
De stelling van Taylor geeft een benadering van f {\displaystyle f} in de omgeving van x n {\displaystyle x_{n}} :
0 = f ( α ) = f ( x n + h n ) = f ( x n ) + h f ′ ( x n ) + … {\displaystyle 0=f(\alpha )=f(x_{n}+h_{n})=f(x_{n})+hf'(x_{n})+\ldots }
Onder verwaarlozing van de termen van tweede orde krijgt men een benadering van h n {\displaystyle h_{n}} :
h n ≈ − f ( x n ) f ′ ( x n ) {\displaystyle h_{n}\approx -{\frac {f(x_{n})}{f'(x_{n})}}\quad } de afgeleide f ′ ( x n ) {\displaystyle f'(x_{n})} wordt ongelijk aan nul verondersteld
:
de afgeleide
f
′
(
x
n
)
{\displaystyle f'(x_{n})}
wordt ongelijk aan nul verondersteld
Een betere benadering voor het nulpunt is dan:
x n + 1 = x n + h n = x n − f ( x n ) f ′ ( x n ) {\displaystyle x_{n+1}=x_{n}+h_{n}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})}}}
Samen met de startwaarde x 0 {\displaystyle x_{0}} geeft dit een recursieve procedure voor het benaderen van het nulpunt α {\displaystyle \alpha } .
Merk op dat x n + 1 {\displaystyle x_{n+1}} het snijpunt met de x {\displaystyle x} -as is van de raaklijn aan de grafiek van f {\displaystyle f} in het punt x n {\displaystyle x_{n}} , gegeven door de formule
y = ( x − x n ) f ′ ( x n ) + f ( x n ) {\displaystyle y=(x-x_{n})f'(x_{n})+f(x_{n})}
het 
-as is van de 
Voorbeelden
Video
- Kies een punt x 0 {\displaystyle x_{0}} op de x {\displaystyle x} -as nabij het nulpunt α {\displaystyle \alpha }
- Construeer een loodrechte op de x {\displaystyle x} -as, door x 0 {\displaystyle x_{0}} ;
- Construeer de raaklijn door f ( x 0 ) {\displaystyle f(x_{0})} aan de kromme f ( x ) {\displaystyle f(x)} ;
- De nieuwe benadering x 1 {\displaystyle x_{1}} wordt gegeven door het snijpunt van de raaklijn met de x {\displaystyle x} -as.
aan de kromme
f
(
x
)
{\displaystyle f(x)}
wordt gegeven door het snijpunt van de raaklijn met de
x
{\displaystyle x}
Cosinus
Nulpuntsbepaling van f ( x ) = cos ( x ) {\displaystyle f(x)=\cos(x)} , met als startwaarde x 0 = 1 {\displaystyle x_{0}=1} . De recursieformule is:
x n + 1 = x n − cos ( x n ) − sin ( x n ) = x n + cot ( x n ) {\displaystyle x_{n+1}=x_{n}-{\frac {\cos(x_{n})}{-\sin(x_{n})}}=x_{n}+\cot(x_{n})}
, met als startwaarde
x
0
=
1
{\displaystyle x_{0}=1}
. De recursieformule is:
en het gezochte nulpunt is
x = π 2 = 1,570 796327 {\displaystyle x={\frac {\pi }{2}}=1{,}570796327}
Iteratie resulteert in:
x 0 = 1 {\displaystyle x_{0}=1} x 1 = 1,000 000000 + cot ( 1,000 000000 ) = 1,642 092616 {\displaystyle x_{1}=1{,}000000000+\cot(1{,}000000000)=1{,}642092616\quad } fout: 7,1×10−2 x 2 = 1,642 092616 + cot ( 1,642 092616 ) = 1,570 675277 {\displaystyle x_{2}=1{,}642092616+\cot(1{,}642092616)=1{,}570675277\quad } fout: 1,2×10−4 x 3 = 1,570 675277 + cot ( 1,570 675277 ) = 1,570 796327 {\displaystyle x_{3}=1{,}570675277+\cot(1{,}570675277)=1{,}570796327\quad } fout: 5,9×10−13
fout: 7,1×10−2
x
2
=
1,642
092616
+
cot
(
1,642
092616
)
=
1,570
675277
{\displaystyle x_{2}=1{,}642092616+\cot(1{,}642092616)=1{,}570675277\quad }
fout: 1,2×10−4
x
3
=
1,570
675277
+
cot
(
1,570
675277
)
=
1,570
796327
{\displaystyle x_{3}=1{,}570675277+\cot(1{,}570675277)=1{,}570796327\quad }
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 n {\displaystyle n} niet-lineaire algebraïsche vergelijkingen in n {\displaystyle 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 {\displaystyle n} -dimensionale ruimte. 1 / f ′ ( x n ) {\displaystyle 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 {\displaystyle f} zijn er allerlei varianten op deze methode, waarbij de afgeleiden hetzij exact worden berekend, hetzij uit opeenvolgende iteratieslagen worden benaderd.
wordt dan vervangen door de inverse Newton
De functie die Isaac Newton als voorbeeld gebruikte was f ( x ) = x 3 − 2 x − 5 {\displaystyle f(x)=x^{3}-2x-5} . Men kan raden dat het punt x = 2 {\displaystyle x=2} een eerste benadering voor een nulpunt van f ( x ) {\displaystyle f(x)} is. Newton maakte de veronderstelling dat x = 2 + a {\displaystyle x=2+a} met een a {\displaystyle a} waarvan wordt aangenomen dat deze klein is en vult deze in de vergelijking in:
x 3 = ( 2 + a ) 3 = 8 + 12 a + 6 a 2 + a 3 {\displaystyle x^{3}=(2+a)^{3}=8+12a+6a^{2}+a^{3}} 2 x = 2 ( 2 + a ) = 4 + 2 a {\displaystyle 2x=2(2+a)=4+2a}
. Men kan raden dat het punt
x
=
2
{\displaystyle x=2}
een eerste benadering voor een nulpunt van
f
(
x
)
{\displaystyle f(x)}
met een
a
{\displaystyle a}
waarvan wordt aangenomen dat deze klein is en vult deze in de vergelijking in:
2
x
=
2
(
2
+
a
)
=
4
+
2
a
{\displaystyle 2x=2(2+a)=4+2a}
zodat
0 = x 3 − 2 x − 5 = − 1 + 10 a + 6 a 2 + a 3 {\displaystyle 0=x^{3}-2x-5=-1+10a+6a^{2}+a^{3}}
Omdat a {\displaystyle a} wordt verondersteld klein te zijn, worden de termen met a 2 {\displaystyle a^{2}} en a 3 {\displaystyle a^{3}} genegeerd, waarna
10 a − 1 ≈ 0 {\displaystyle 10a-1\approx 0} , dus a ≈ 0 , 1 {\displaystyle a\approx 0{,}1}
en
a
3
{\displaystyle a^{3}}
genegeerd, waarna
, dus
a
≈
0
,
1
{\displaystyle a\approx 0{,}1}
overblijft als betere benadering.
Dit kan worden herhaald door a = 0 , 1 + b {\displaystyle a=0{,}1+b} te stellen en in te vullen in de vergelijking voor a {\displaystyle a} .
a 3 = ( 0 , 1 + b ) 3 = 0,001 + 0 , 03 b + 0 , 3 b 2 + b 3 {\displaystyle a^{3}=(0{,}1+b)^{3}=0{,}001+0{,}03b+0{,}3b^{2}+b^{3}} a 2 = ( 0 , 1 + b ) 2 = 0 , 01 + 0 , 2 b + b 2 {\displaystyle a^{2}=(0{,}1+b)^{2}=0{,}01+0{,}2b+b^{2}}
te stellen en in te vullen in de vergelijking voor
a
{\displaystyle a}
a
2
=
(
0
,
1
+
b
)
2
=
0
,
01
+
0
,
2
b
+
b
2
{\displaystyle a^{2}=(0{,}1+b)^{2}=0{,}01+0{,}2b+b^{2}}
zodat
0 = − 1 + 10 a + 6 a 2 + a 3 = 0,061 + 11 , 23 b + 6 , 3 b 2 + b 3 {\displaystyle 0=-1+10a+6a^{2}+a^{3}=0{,}061+11{,}23b+6{,}3b^{2}+b^{3}}
Weer worden de termen van hogere orde weggelaten, waarna:
b ≈ − 0,061 / 11 , 23 = − 0,005 4 … {\displaystyle b\approx -0{,}061/11{,}23=-0{,}0054\ldots }