Afleiding van de Newton-Raphson methode

Functie-iteratie: Newton-Raphson methode van nulpuntsbepaling

Afleiding van de Newton-Raphson methode

We laten zien hoe de zogenaamde Newton-Raphson methode voor nulpuntsbepaling van een 'nette' functie $f$ uit de theorie van iteratie-functies ontstaat.

Om te beginnen is de vergelijking

$f(x)=0$ equivalent met

$x+\alpha\cdot f(x)=x\quad\text{mits }\alpha\neq 0\tiny.$ In plaats van een nulpunt van de functie $f$ te bepalen, kunnen we net zo goed een dekpunt van de iteratie-functie

$g(x)=x+\alpha\cdot f(x)$ proberen te benaderen. Een dekpunt $s$ van $g$ is aantrekkend als $|g'(s)| <1$ en het liefst hebben we $|g'(s)|$ zo klein mogelijk. De beste convergentie treedt dus op bij de keuze van $\alpha$ waarvoor geldt

$1+\alpha\cdot f'(s)=0$ oftewel wanneer

$\alpha = -\frac{1}{f'(s)}\tiny.$

Probleem is natuurlijk dat het dekpunt $s$ van de iteratie-functie vooraf niet bekend is. Een tweede observatie is dat het ons vrij staat om in iedere iteratiestap een nieuwe $\alpha$ te kiezen, zeg $\alpha_n$ . Als de functie 'net' is, bijvoorbeeld een continue afgeleide heeft, dan zal bij een rij $x_0, x_1, x_2, \ldots$ die naar een dekpunt $s$ convergeert de rij $f'(x_0), f'(x_1), f'(x_2), \ldots$ naar $f'(s)$ convergeren. Dit motiveert onze keuze om in elke stap van de iteratie als geschikte $\alpha$ de afgeleide van $f$ in de op dat moment gevonden iterand te gebruiken via de formule

$\alpha_n=-\frac{1}{f'(x_n)}$ waarbij $x_n=g^n(x_0)$ .

We zijn zo uitgekomen bij de iteratieve formule voor de Newton-Raphson methode van nulpuntsbepaling.

Voor een functie $f$ met continue afgeleide kan een nulpunt bepaald worden door de iteratie

$x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}$ mits het startpunt $x_0$ voldoende dicht bij een dekpunt $s$ gekozen wordt en $f'(s)\neq 0$ .

De Newton-Raphson methode voor nulpuntsbepaling van een functie $f$ is dus niets anders dan de iteratie van de functie

$N(x)=x-\frac{f(x)}{f'(x)}$ met een startwaarde $x_0$ voldoende dicht in de buurt van een aantrekkend dekpunt $s$ met $f'(s)\neq 0$ . Er geldt:

$N(s)=s,\quad N'(s)=0, \quad N''(s)= \frac{f''(s)}{f'(s)}\tiny.$ (Ga de laatste gelijkheid zelf na.) Laten we nu eens het convergentiegedrag van de Newton-Raphson methode bestuderen. Laat $\epsilon_n=x_n-s$ de absolute afbreekfout zijn van de $n$ -de benadering van het dekpunt $s$ . Dus $x_n=s+\epsilon_n$ . Volgens de stelling van Taylor is er dan een $\xi$ tussen $s$ en $x_n$ zodanig dat

$N(x_n)=N(s)+N'(s)\cdot \epsilon_n+\tfrac{1}{2}\!N''(\xi)\cdot \epsilon_n^2$ Anders gezegd:

$x_{n+1}=s+\frac{f''(\xi)}{2f'(\xi)}\cdot \epsilon_n^2$ voor zekere $\xi$ tussen $s$ en $x_n$ . Met andere woorden

$\epsilon_{n+1}=\frac{f''(\xi)}{2f'(\xi)}\cdot \epsilon_n^2$ en de convergentie van de Newton-Raphson methode is onder de gegeven omstandigheden dus minstens kwadratisch.

We passen de Newton-Raphson methode toe op de functie $f(x)=x^2-2$ om $\sqrt{2}$ te benaderen, waarbij we starten in $x_0=1$ . Dan is de bijpassende iteratie-functie $N(x)$ gegeven door

$N(x)=x-\frac{f(x)}{f'(x)}=x-\frac{x^2-2}{2x}=\frac{x}{2}+\frac{1}{x}\tiny.$ De Newton-Raphson methode is nu niets ander dan de eerder besproken methode van Héron.

de Newton-Raphson methode voor de nulpuntsbepaling van een functie $f$ kan ook als volgt begrepen worden, We beginnen met een benadering $x_0$ van het nulpunt van $f$ . Bepaal de raaklijn aan de grafiek
van $f$ in het punt $\bigl(x_0, f(x_0)\bigr)$ . Veronderstel dat $f'(x_0)\neq 0$ , dan snijdt deze raaklijn de $x$ -as in een punt $\bigl(x_1,0\bigr)$ . Dit punt kunnen we uitrekenen: de vergelijking van de raaklijn is

$y=f'(x_0)\cdot (x-x_0) +f(x_0)$ De $x$ -coördinaat van snijpunt van deze lijn met de $x$ -as voldoet aan de vergelijking

$f'(x_0)\cdot (x-x_0) +f(x_0)=0$ en is dus gelijk aan

$x_0-\frac{f(x_0)}{f'(x_0)}$ Als volgende benadering van een nulpunt van $f$ nemen we

$x_1=x_0-\frac{f(x_0)}{f'(x_0)}$ en hierna herhalen we dit benaderingsproces. Onderstaande figuur illustreert de eerst twee stappen in dit iteratieproces.

Newton-Raphson methode