3.5 Newtons metode

Hva gjør kalkulatoren når du trykker på rottegnet?

Tast $\sqrt{2}$ på kalkulatoren, og svaret $1{,}41421356\ldots$ kommer momentant. Men stopp og tenk: hvordan? Det finnes ingen krets i maskinen som «vet» kvadratrøtter. Det finnes heller ingen formel å slå opp i -- $\sqrt{2}$ er irrasjonal, sifrene tar aldri slutt. Likevel leverer kalkulatoren et titalls korrekte desimaler på et millisekund.

Det samme mysteriet lurer i ligningene algebraen ikke rår på. $x^5 - 3x + 1 = 0$ har ingen løsningsformel -- det er bevist at femtegradsligninger generelt ikke kan løses med rottegn. $\cos x = x$ blander trigonometri og polynom på en måte ingen omskriving løser opp. $e^x = 3x$ likeså. Men løsningene finnes: grafene krysser hverandre, det ser du med det blotte øye. Spørsmålet er hvordan vi fanger dem.

Svaret, som driver både kalkulatoren din og tallknusingen i moderne ingeniørkunst, er en idé fra Isaac Newton: gjett, og la tangenten forbedre gjetningen. Står du på grafen til $f$ og vil ned til nullpunktet, så følg tangenten -- den peker omtrent dit grafen skal, og der den krysser $x$-aksen, står du nesten alltid nærmere svaret enn der du startet. Gjenta, og presisjonen eksploderer: antall riktige desimaler dobles i hvert steg.

I dette kapittelet utleder du iterasjonsformelen fra tangentligningen, ser metoden knuse både $\sqrt{2}$ og $\cos x = x$ -- og lærer når den feiler, hvorfor, og hva du gjør da.

Tangenten som veiviser

Oppgaven er alltid den samme: finn et nullpunkt for $f$, altså en løsning av $f(x) = 0$. (Har du en ligning på annen form, som $\cos x = x$, flytter du først alt over på én side: $f(x) = \cos x - x$.)

Metoden starter med en gjetning $x_0$ et sted i nærheten av løsningen -- en grafskisse eller litt prøving gir deg den. Så kommer kjernen: stå i punktet $(x_0, f(x_0))$ på grafen og legg tangenten der. Grafen selv bukter seg, men tangenten er en rett linje -- og en rett linje vet vi nøyaktig hvor krysser $x$-aksen. Det krysningspunktet er den nye og bedre gjetningen $x_1$. Gjenta fra $x_1$, og du får $x_2$, enda nærmere. Hvert steg bytter den vanskelige kurven ut med sin enkleste stedfortreder.

Formelen følger av regnestykket du allerede kan. Tangenten i $(x_n, f(x_n))$ har ligning

$$y - f(x_n) = f'(x_n)(x - x_n)$$

Vi vil vite hvor den treffer $x$-aksen, så vi setter $y = 0$ og løser for $x$: $-f(x_n) = f'(x_n)(x - x_n)$, som gir $\displaystyle x = x_n - \frac{f(x_n)}{f'(x_n)}$. Dermed:

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

Les den som en korreksjon: fra $x_n$ trekker vi feilen $f(x_n)$ målt i tangentens målestokk $f'(x_n)$. Er funksjonsverdien stor og stigningen slak, må vi flytte oss langt; er verdien liten og stigningen bratt, er vi nesten framme og justerer bare ørlite. Det er hele Newtons metode -- en gjetning og en derivert, om og om igjen.

Metoden i aksjon -- og den kvadratiske magien

Tilbake til kalkulatorens hemmelighet. $\sqrt{2}$ er nullpunktet til $f(x) = x^2 - 2$, med $f'(x) = 2x$. Formelen blir

$$x_{n+1} = x_n - \frac{x_n^2 - 2}{2x_n} = \frac{x_n}{2} + \frac{1}{x_n}$$

-- som er det samme som gjennomsnittet av $x_n$ og $\displaystyle \frac{2}{x_n}$: en gjetning og det tallet den bommer mot, midlet sammen. Start med $x_0 = 1$: da gir formelen $\displaystyle x_1 = \frac{1}{2} + 1 = 1{,}5$, deretter $\displaystyle x_2 = \frac{1{,}5}{2} + \frac{1}{1{,}5} \approx 1{,}4167$, så $x_3 \approx 1{,}4142$. Tre steg, fire korrekte desimaler. (Babylonerne brukte faktisk akkurat denne oppskriften for 4000 år siden -- Newton ga dem bare den deriverte som forklaring.)

Så den transcendente ligningen $\cos x = x$. Med $f(x) = \cos x - x$ og $f'(x) = -\sin x - 1$ blir formelen $\displaystyle x_{n+1} = x_n - \frac{\cos x_n - x_n}{-\sin x_n - 1}$. Grafisk inspeksjon antyder en løsning nær $0{,}5$, så vi starter der: $x_1 \approx 0{,}7552$, $x_2 \approx 0{,}7391$ -- og der er $f(x_2) \approx 0{,}00005$. To steg fra en grov gjetning til fem desimaler.

Legg merke til mønsteret i feilene: omtrent $0{,}24$, så $0{,}016$, så $0{,}00005$. Antall korrekte siffer dobles i hvert steg. Dette kalles kvadratisk konvergens, og det er metodens superkraft: 5--10 iterasjoner gir mer enn 10 desimaler. Til sammenligning gir naive metoder ett siffer per steg.

I praksis trenger vi et stoppkriterium -- maskinen kan jo ikke iterere evig. To vanlige valg: stopp når endringen $|x_{n+1} - x_n|$ er mindre enn en toleranse (f.eks. $10^{-6}$), eller når $|f(x_n)|$ er tilstrekkelig nær null.

Når tangenten lurer oss

Newtons metode er rask, men ikke ufeilbarlig -- og fellene er lærerike. Metoden fungerer godt når startverdien er nær løsningen, når $f'(x) \neq 0$ i området, og når $f$ oppfører seg pent. Bryter én av forutsetningene, kan det gå galt på tre måter: $f'(x_n) = 0$ gir divisjon med null (tangenten er vannrett og krysser aldri $x$-aksen), en dårlig startverdi kan sende iterasjonene på vidvanke, og har ligningen flere løsninger, kan du lande på «feil» en.

Det mest lærerike havariet: prøv $f(x) = x^{1/3}$, kubikkroten, med nullpunkt i $x = 0$. Med $\displaystyle f'(x) = \frac{1}{3}x^{-2/3}$ blir iterasjonsformelen

$$x_{n+1} = x_n - \frac{x_n^{1/3}}{\frac{1}{3}x_n^{-2/3}} = x_n - 3x_n = -2x_n$$

Hvert steg dobler avstanden og bytter fortegn: fra $x_0 = 1$ får vi $-2, 4, -8, 16, \ldots$ Iterasjonene divergerer -- spretter vekk fra nullpunktet de skulle finne. Synderen er den deriverte: nær $x = 0$ vokser $f'$ mot uendelig, grafen står loddrett, og tangentene peker lenger og lenger bort.

Hva gjør vi når Newton svikter? Den trofaste reserven er halveringsmetoden: finn $a$ og $b$ med fortegnskifte, $f(a) \cdot f(b) < 0$, og halver intervallet om og om igjen. Den er treg -- lineær konvergens, omtrent ett binærsiffer per steg -- men den feiler aldri så lenge fortegnskiftet finnes. Newtons metode er sprinteren som kan snuble; halveringsmetoden er turgåeren som alltid kommer fram.

Profesjonell praksis kombinerer dem: bruk halvering til et grovt estimat trygt innenfor, og slipp så Newton løs for å finpusse med kvadratisk fart. Slik får du både påliteligheten og hastigheten.

Fortellingen i et nøtteskall

Kalkulatorens rotmysterium er løst: bak tasten bor en iterasjon. Newtons metode finner nullpunkter for $f(x) = 0$ ved å la tangenten vise vei -- stå i $(x_n, f(x_n))$, følg tangenten til den krysser $x$-aksen, og kall krysningen $x_{n+1}$. Av tangentligningen med $y = 0$ ble formelen

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

Oppskriften: omform ligningen til $f(x) = 0$, finn $f'$, velg en god startverdi $x_0$ (gjerne fra en grafskisse), og iterer til stoppkriteriet slår inn -- $|x_{n+1} - x_n|$ eller $|f(x_n)|$ under toleransen.

Styrken er den kvadratiske konvergensen: antall korrekte siffer dobles per steg, slik vi så da $\sqrt{2}$ falt på tre iterasjoner fra $x_0 = 1$ ($1{,}5 \to 1{,}4167 \to 1{,}4142$) og $\cos x = x$ ga $0{,}7391$ på to steg fra $0{,}5$.

Svakhetene er like konkrete: $f'(x_n) = 0$ gir havari, dårlig startverdi kan gi divergens eller feil løsning, og kubikkroten $x^{1/3}$ viste totalhavariet $x_{n+1} = -2x_n$ -- tangenter som peker lenger og lenger bort. Reserven er halveringsmetoden: treg, men ufeilbarlig gitt et fortegnskifte. I praksis kombineres de -- halvering for trygghet, Newton for fart.

Metoden er også et gjensyn med kapittelets røde tråd: den deriverte som lokal, lineær stedfortreder for kurven. I neste kapittel snur vi på det -- og lar tallene tilnærme den deriverte selv.