Newtons metode
Newtons metode (også kendt som Newton-Rhapson metoden) er en numerisk metode til at bestemme rødder for differentiable funktioner.
På denne side introducerer vi først idéen bag Newtons metode og viser hvordan den fortolkes geometrisk. Derefter gennemgår vi fremgangsmåden til anvendelsen af Newtons metode trinvist og illustrerer det med et eksempel. Afsnittene geometrisk fortolkning, fremgangsmåde og eksempel kan læses uafhængigt af hinanden, så hvis du foretrækker at læse i en anden rækkefølge, kan du sagtens gøre det. Til sidst diskutere vi nogle tilfælde, hvor metoden kan fejle.
Hvad er Newtons metode?
I nogle tilfælde kan vi bestemme funktioners rødder (også kaldet nulpunkter) ved at løse ligninger på formen f(x)=0 og finde præcis løsninger. For mange funktioner er det enten ikke muligt eller for kompliceret at finde en sådan løsning ved hjælp af de metoder, vi kender. I sådanne tilfælde kan vi i stedet anvende en numerisk metode til at løse ligningen. Når vi anvender en numerisk metode, foretager vi en trinvis procedure og finder approksimerede (tilnærmede) løsninger, dvs. løsninger, der er meget tæt på den eksakte (præcise) løsning men som ikke er helt identisk. En god numerisk metode skal gerne komme tættere og tættere på den eksakte løsning i hvert trin.
Vi kan altså bruge Newtons metode til at finde tilnærmelser til rødderne for differentiable funktioner. Fremgangsmåden for Newtons metode er en algoritme, hvor vi laver den samme beregning igen og igen - hele tiden baseret på resultatet fra den forrige beregning. Hvis vi kender \(x_n\), kan vi næsten altid beregne \(x_{n+1}\) ved hjælp af følgende udtryk (vi får problemer, hvis \(f'(x_n) = 0\)):
\[ x_{n+1}=x_{n}-\frac{f(x_{n})}{f'(x_{n})} \]
Her kan n være tallene 0, 1, 2, 3, 4, ... osv., og n angiver på den måde, hvor mange beregninger, der er tidligere er lavet i algoritmen.
Hvornår bruger man Newtons metode?
Før vi beskriver, hvordan metoden virker, så lad os tænke over, hvad vi ønsker at bruge den til.
Mange vigtige tal - såsom $\sqrt{2}$ eller $\pi$ - kan ikke skrives nøjagtigt i decimalform.
Vi ved ofte, hvordan sådanne tal er defineret, men når vi vil regne med dem, har vi brug for gode approksimationer. Selvfølgelig kan vi aldrig beregne alle decimaler, men i praksis har vi som regel kun brug for et bestemt antal decimaler.
Når vi derfor siger, at vi kan “beregne” et tal $r$, mener vi, at vi for ethvert antal decimaler $k$ kan fremstille et rationelt tal, hvis første $k$ decimaler stemmer overens med dem for $r$. En god numerisk metode bør derfor give os en række approksimationer, hvor hvert nye bud på $r$ er mere præcist end den forrige.
Vi kan skelne mellem tre meget tæt beslægtede tilfælde, hvor vi kan bruge Newtons metode:
- Vi har en funktion og vil gerne bestemme funktionens rødder. Det kunne f.eks. være vi havde funktionen \(f(x)= x^2-2\) og gerne vil finde rødderne. Det er det samme, som at løse ligningen \(f(x)=0\).
- Vi har en ligning, vi gerne vil løse. Her kan vi omskrive ligningen og bruge den til at definere en funktionsforskrift, som gør det muligt at skrive ligningen på formen \(f(x)=0\). Hvis vi f.eks. har ligningen \(x^2=2\), kan vi definere funktionen \(f(x)= x^2-2\), hvor løsningerne til ligningen \(f(x)=0\) også vil være løsninger til den oprindelige ligning.
- Vi vil gerne beregne et tal, f.eks. \(\sqrt{2}\). Her opskriver vi en ligning, hvor tallet er løsningen til ligningen, f.eks. er \(\sqrt{2}\) den positive løsning til ligningen \(x^2-2=0\). Igen definerer vi en funktionsforskrift og omskriver ligningen til formen \(f(x)=0\).
Uanset om vi starter med et tal, en ligning eller en funktion, er Newtons metode en pålidelig metode til at fremstille approksimationer af løsningen med så høj præcision, som vi ønsker.
Geometrisk fortolkning
Lad os forestille os, at vi har en differentiabel funktion \(f(x)\), hvor vi ønsker at bestemme en af funktionens rødder. Den rod, vi gerne vil finde, kalder vi for \(r\). Vi viser her, hvordan vi starter med at gætte på en værdi for roden (det vi kalder begyndelsesgættet, \(x_0\)), og hvordan vi kan komme tættere og tættere på roden \(r\) ved at tegne tangenter til \(f(x)\) og bruge tangenternes nulpunkter som approximationer (tilnærmelser) for roden \(r\).
Trin 0: Vi starter med begyndelsesgættet $x=x_0$.
Trin 1: Vi tegner tangenten til grafen for $f(x)$ i punktet $(x_0,f(x_0))$. Tangenten er givet ved tangentligningen
\[y=f'(x_0)\cdot (x-x_0) + f(x_0) \]
Vi kan finde tangentens rod ved at sætte y=0 og løse ligningen:
\begin{align*} f'(x_0)\cdot (x-x_0) + f(x_0) &= 0 \\ f'(x_0)\cdot (x-x_0) &= - f(x_0) \\ x-x_0 &= - \dfrac{f(x_0)}{f'(x_0)} \\ x&= x_0 - \dfrac{f(x_0)}{f'(x_0)} \\ \end{align*}
Vi definerer tangentens rod (skæringen mellem tangenten og $x$-aksen) som $x_1$, hvilket betyder, at $x_1$ er løsningen ligningen ovenfor. Derfor er $x_1$ givet ved følgende udtryk:
\[x_1 = x_0 - \dfrac{f(x_0)}{f'(x_0)} \]
Bemærk at \(x_1\) er en approksimation til løsningen for f(x)=0 og dermed også en approximation af \(r\).
Trin 2: Vi tager nu udgangspunkt i \(x_1\) og tegner tangenten til grafen for \(f(x)\) i punktet $(x_1,f(x_1))$. Igen kan vi opskrive ligningen for tangenten,
\[y=f'(x_1)\cdot (x-x_1) + f(x_1). \]
Igen kan vi sætte \(y=0\), løse ligningen for at finde tangentens rod og definere $x_2$ som tangentens rod. Det betyder, at $x_2$ er x-koordinaten til skæringspunktet mellem den nye tangent og $x$-aksen. $x_2$ er en ny (og formentlig bedre) approksimation til løsningen af \(f(x)=0\) og er givet ved udtrykket:
\[x_2 = x_1 - \dfrac{f(x_1)}{f'(x_1)} \]
Vi fortsætter med at tegne en tangent til grafen for $f(x)$ i punktet $(x_2,f(x_2))$, finde roden for den tangent, tegne en ny tangent, finde den nye tangent-rod osv.
Trin n: I det $n$-te trin tegner vi tangenten til grafen for $f(x)$ i punktet $(x_{n-1}, f(x_{n-1}))$ og definerer igen $x_n$ som skæringspunktet mellem tangenten og $x$-aksen.
Tangenten til grafen for $y=f(x)$ i punktet $(x_{n-1},f(x_{n-1}))$ er givet ved ligningen
$$y=f'(x_{n-1})(x-x_{n-1})+f(x_{n-1}).$$
$x_n$ er tangents skæringspunkt med $x$-aksen og derfor løsningen til ligningen
$$0=f'(x_{n-1})(x-x_{n-1})+f(x_{n-1}),$$
så vi har at
\[
x_n = x_{n-1}-\dfrac{f(x_{n-1})}{f'(x_{n-1})}.
\]
Fremgangsmåden for Newtons metode
Vi har en funktion $f(x)$, og ønsker at bruge Newtons metode til at bestemme en rod for en funktion, dvs. en værdi af x, hvor \(f(x)=0\).
Før metoden kan anvendes, skal man bestemme den afledte funktion $f'$. Det er vigtigt, at $f'$ er veldefineret og kontinuerlig i det område, hvor man forventer at finde roden. Hvis det i et af de følgende trin viser sig, at $f'(x_n)=0$, kan formlen ikke anvendes, og man må i stedet vælge et andet begyndelsesgæt og starte forfra.
Når vi kender $f$ og $f'$, kan vi begynde. Fremgangsmåden for Newtons metode er opdelt i trin i det følgende, hvor man gentager samme procedure. Det er det, vi kalder en algoritmisk fremgangsmåde.
Trin 0: Vælg et begyndelsesgæt, $x_0$
Som det første vælger vi et sted at starte, dvs. vi vælger et tal, som vi kalder $x_0$. Hvis du har en idé om, hvor roden $r$ nogenlunde befinder sig, er det en god idé at vælge $x_0$ i nærheden af $r$.
Trin 1: Beregn tallet $x_1$
Nu har vi $x_0$ og vi kan derfor beregne $x_1$.
\[
x_1=x_0-\frac{f(x_0)}{f'(x_0)}.
\]
Vurdér, om dette gæt er tilstrækkeligt godt. Hvis ja, kan man stoppe her; hvis ikke, fortsætter man til næste trin og gentager proceduren.
Trin 2: Beregn tallet $x_2$
Nu har vi $x_1$ og vi kan derfor beregne $x_2$.
\[
x_2=x_1-\frac{f(x_1)}{f'(x_1)}.
\]
Vurdér igen, om resultatet er tilstrækkeligt godt, eller om man skal fortsætte.
$\ldots$
Trin n: Beregn tallet $x_n$
Vi fortsætter proceduren ligesom med $x_1$ og $x_2$. Hver gang vi har fundet et tal, kan vi bestemme det næste. Vi kan sige, at hvis man kender $x_{n-1}$, kan man bestemme $x_n$, hvor $n$ kan være 1, 2, 3, 4, ... osv.
Vi skriver det således:
\begin{equation} \label{rec_eq}
x_n=x_{n-1}-\frac{f(x_{n-1})}{f'(x_{n-1})}.
\end{equation}
Efter hvert trin, dvs. hver gang man beregner en ny $x_n$, vurderer man, om resultatet er godt nok. Hvis det er godt nok, stopper man og ellers fortsætter man med $x_{n+1}$.
\[ x_{n+1}=x_{n}-\frac{f(x_{n})}{f'(x_{n})} \]
Hvornår er resultatet "godt nok"?
Hvad der menes med “godt nok”, afhænger af situationen. I praksis stopper man ofte, når ændringen fra ét trin til det næste bliver meget lille, eller når værdien $f(x_n)$ er meget tæt på nul. Typisk vælger man et stopkriterium på forhånd, der afgør hvor lille ændringen eller værdien af \(f(x_n\) skal være. På den måde fortsætter man kun, så længe hvert nyt trin giver en mærkbar forbedring.
Det er også almindeligt at sætte en øvre grænse for, hvor mange trin man vil udføre. På den måde undgår man, at beregningen fortsætter i det uendelige, hvis metoden af en eller anden grund ikke giver et tilfredsstillende resultat.
Eksempel på anvendelse af Newtons metode
Antag, at vi vil beregne den positive løsning $\varphi$ til ligningen
\[
x^2 - x - 1 = 0
\]
ved hjælp af Newtons metode. Ved at løse andengradsligningen som vi kender det, får vi $\varphi \approx 1.61803398875\ldots.$
I dette eksempel ser vi, hvordan vi kommer tættere og tættere på det resultat for hvert trin i Newtons metode.
Vi vælger at stoppe beregningen, når den absolutte forskel mellem to på hinanden følgende trin er mindre end $0\text{,}00001$, dvs.
\[
|x_{n+1}-x_n|<0\text{,}00001.
\]
Det første, vi gør, er at omskrive ligningen, så vi får en funktionsforskrift. Hvis vi definerer funktionen $f$ som
\[ f(x) = x^2 - x - 1 \]
svarer rødderne for $f$ til løsningerne af ligningen $x^2 - x - 1 = 0$. Da vi er interesserede i at finde den positive løsning til ligningen, er vi altså interesserede i at finde den positive rod til $f$.
Nu beregner vi $f'$:
\[ f'(x)=(x^2)'-(x)'-(1)'=2x-1 \]
Vi indsætter forskrifterne for $f$ og $f'$ i udtrykket for $x_{n+1}$:
\[ x_{n+1}=x_n-\dfrac{f(x_n)}{f'(x_n)}
= x_n - \dfrac{x_n^2 - x_n - 1}{2x_n - 1} \]
Udtrykket kan reduceres ved at sætte på fællesnævner og samle i én brøk.
\begin{align*} x_{n+1} &= x_n - \dfrac{x_n^2 - x_n - 1}{2x_n - 1} =\dfrac{x_n \cdot (2x_n - 1)}{2x_n - 1} - \dfrac{x_n^2 - x_n - 1}{2x_n - 1} \\ &= \dfrac{x_n \cdot (2x_n - 1) - (x_n^2 - x_n - 1)}{2x_n - 1} \\ &= \dfrac{2x_n^2 - x_2 - x_n^2 + x_n +1}{2x_n - 1} \\ &= \dfrac{x_n^2 + 1}{2x_n - 1}. \end{align*}
Nu kender vi $f$, $f'$ og har et udtryk for $x_{n+1}$, så nu kan vi begynde med trin 0:
Trin 0: Vælg begyndelsesgæt, $x_0$
Vi vælger $x_0 = 2$ som begyndelsesgæt.
Dette valg er rimeligt, da $f(1)=1^2-1-1=-1$ og $f(3)=3^2-3-1=5$, og da den afledte $f'(x)=2x-1$ er positiv på intervallet $[1,3]$, er funktionen voksende på dette interval. Dermed ligger tallet $\varphi$, hvor $f$ antager værdien $0$, et sted mellem $1$ og $3$.
Trin 1:
Vi beregner \(x_1\) ved at indsætte \(x_0 = 2 \) i udtrykket for \(x_1\):
\[
x_1=\dfrac{x_0^2 + 1}{2x_0 - 1}
= \dfrac{2^2 + 1}{2 \cdot 2 - 1}
=\dfrac{5}{3}\approx \mathbf{1\text{,}6}6666666667\ldots
\]
Det ses ovenfor, at 1,6 er markeret med fed. Det er for at illustrere, at vi disse cifre er identiske med løsningen til andengradsligningen. Du kan altså på den måde følge med i, hvordan vi nærmer os løsningen med flere og flere cifre i hvert trin.
Vi vurderer nu, om ændringen fra forrige trin er tilstrækkeligt lille:
\[
|x_1-x_0|=\left|\dfrac{5}{3}-2\right|=\dfrac{1}{3}\approx 0\text{,}33 >0\text{,}00001.
\]
Forskellen på \(x_1\) og \(x_0\) er altså større end 0,00001, så vi fortsætter til trin 2.
Trin 2:
Vi beregner \(x_2\) ved at indsætte \(x_1 = \frac{5}{3} \) i udtrykket for \(x_2\):
\[
x_2=\dfrac{x_1^2 + 1}{2x_1 - 1}
= \dfrac{\left(\frac{5}{3}\right)^2 +1}{2 \cdot \frac{5}{3} - 1}
=\dfrac{34}{21}\approx \mathbf{1\text{,}61}904761905\ldots
\]
Igen er stopkriteriet ikke opfyldt, da
\[
|x_2-x_1|
=\left|\dfrac{34}{21}-\dfrac{5}{3}\right|
=\dfrac{1}{21} \approx 0\text{,}048 >0\text{,}00001,
\]
og vi fortsætter med næste trin.
Trin 3:
Vi beregner \(x_3\) ved at indsætte \(x_2 = \frac{34}{21} \) i udtrykket for \(x_3\):
\[
x_3=\dfrac{x_2^2 + 1}{2x_2 - 1}
= \dfrac{\left(\frac{34}{21}\right)^2 +1}{2 \cdot \frac{34}{21} - 1}
=\dfrac{1597}{987}\approx \mathbf{1\text{,}61803}444782\ldots
\]
Vi undersøger ændringen på de to seneste trin, dvs. forskellen på \(x_2\) og \(x_3\).
\[
|x_3-x_2|
=\left|\dfrac{1597}{987}-\dfrac{34}{21}\right|
\approx 0\text{,}000874 >0\text{,}00001,
\]
Ændringen er altså stadig større end $0\text{,}00001$, og vi udfører endnu et trin.
Trin 4:
Vi beregner \(x_4\) ved at indsætte \(x_3 = \frac{1597}{987} \) i udtrykket for \(x_4\):
\[
x_4=\dfrac{x_3^2 + 1}{2x_3 - 1}
= \dfrac{\left(\frac{1597}{987}\right)^2 +1}{2 \cdot \frac{1597}{987} - 1}
=\dfrac{3524578}{2178309}
\approx \mathbf{1\text{,}61803398875}\ldots
\]
Her er stopkriteriet opfyldt, da
\[
|x_4-x_3|
=\left|\dfrac{3524578}{2178309}-\dfrac{1597}{987}\right|
= \approx 0\text{,}000000544<0\text{,}00001,
\]
og vi afslutter beregningen.
Tallet $\varphi$ er kendt som det gyldne snit. Det er ikke blot et af de vigtigste tal i matematikken, men forekommer også i naturen, kunsten og i dagligdags design, hvor det påvirker, hvad vi opfatter som æstetisk tiltalende. Man kunne sagtens afsætte et helt kapitel — eller endda en hel bog — til det gyldne snit, men her stopper vi, da det ligger uden for emnet for denne tekst.
Når metoden går galt
I visse tilfælde kan Newtons metode fejle eller opføre sig uforudsigeligt for bestemte valg af begyndelsespunkt. I det følgenden vil vi gennemgå nogle af de mest almindelige grunde.
Valg af begyndelsespunkt
Algoritmen afhænger stærkt af valget af begyndelsespunkt. I eksemplet med det gyldne snit ville vi for eksempel, hvis vi valgte $x_0=-2$, ende med en approksimation af den anden (negative) rod af polynomiet $f(x)=x^2-x-1$. Hvis vi startede med $x_0=1/2$, kunne vi slet ikke fortsætte, da $f'(1/2)=0$.
Man kan tænke på det sådan, at valget af begyndelsesgæt har stor betydning for, hvilken rod man ender med at finde. Begyndelsesgæt, som ligger nogenlunde samme sted, fører ofte til den samme rod, mens gæt, der ligger længere fra hinanden, kan give helt forskellige resultater. For det gyldne snit er opdelingen enkel: starter vi med $x_0<1/2$, får vi den negative rod, starter vi med $x_0>1/2$, får vi den positive rod, og for $x_0=1/2$ virker metoden slet ikke.
Generelt kan denne opdeling være meget kompliceret, og i numerisk analyse arbejder man derfor med smarte måder at vælge et godt begyndelsesgæt på.
Ved “naive” håndberegninger er det ofte nok at vælge et begyndelsesgæt tæt på den ønskede rod og eventuelt prøve flere startpunkter for at sikre, at man ender med samme resultat, og være klar til at starte forfra, hvis noget går galt, som vist i eksemplerne nedenfor.
Punkter hvor funktionen ikke er defineret
Nogle gange kan Newtons metode føre til et punkt, hvor funktionen $f(x)$ ikke er defineret.
Antag, at vi vil bruge Newtons metode til at finde roden af
\[
f(x)=\ln(x)-1
\]
(det vil sige tallet $e$).
Hvis vi vælger $x_0=8$, får vi et negativt tal i første trin:
\[
x_1=8-\frac{\ln(8)-1}{1/8}=16-8\ln(8)<0.
\]
Den logaritmiske funktion $\ln(x)$ er kun defineret for positive værdier af $x$, og algoritmen kan derfor ikke fortsætte. Med et begyndelsespunkt tættere på roden, for eksempel $x_0=3$, virker Newtons metode derimod fint.
Små eller forsvindende afledte
I udtrykket for at finde den næste approximation, divideres der med $f'(x_n)$. Det betyder, at hvis $f'(x_n)=0$, stopper metoden. Hvis $f'(x_n)$ blot er meget lille, kan næste trin springe langt væk fra den ønskede rod, så approximationen ikke bliver bedre end den forrige, men derimod meget dårligere.
Som eksempel kan vi se på polynomiet $f(x)=-x^3+3x+1$, som har tre rødder:
$$r_1\approx -1\text{,}532\ldots, \quad r_2\approx -0\text{,}347\ldots, \quad r_3\approx 1\text{,}879\ldots.$$
Antag, at vi vil finde $r_2$. Hvis vi starter med $x_0=0\text{,}8$, kan det umiddelbart virke fornuftigt, men som vist i figuren nedenfor ender $x_1$ langt fra både $x_0$ og roden $r_2$, og punkterne $x_2, x_3, \ldots, x_n, \ldots$ kommer i stedet tættere og tættere på den forkerte rod, nemlig $r_1$.
Hvis man starter længere væk fra det punkt, hvor $f'(x)=0$, undgås dette problem.
Et sjovt eksempel: Periodisk kredsløb
De værdier, som algoritmen i Newtons metode frembringer, kan også ende med at gentage sig og dermed aldrig nærme sig en fast værdi. Hvis vi tager $f(x)=x^3-2x+2$ og $x_0=0$, kan man tjekke, at $x_1=1$ og $x_2=0$. Vi får altså værdierne $0,1,0,1,\ldots$, som blot skifter frem og tilbage og aldrig falder til ro.
