6.4 Rotsøking — Newtons metode, biseksjon og sekant

Et tall $r$ med $f(r)=0$. Ordene «rot», «nullpunkt» og «løsning av likningen $f(x)=0$» betyr det samme.

Sammenhengen med kap. 6.3: skriver du likningen om til $x=g(x)$, blir røttene til $f$ nøyaktig fikspunktene til $g$. Rotsøking og fikspunktiterasjon er to innganger til det samme problemet.

Standardføringen i denne sjangeren har to deler, og begge må med:

1. Eksistens: $f$ er kontinuerlig, og $f(a)$ og $f(b)$ har motsatt fortegn. Etter mellomverdisetningen finnes en rot i $(a,b)$.
2. Entydighet: $f'$ har fast fortegn (regn den ut og vis det), så $f$ er strengt monoton og kan krysse aksen høyst én gang.

Til sammen: nøyaktig én rot.

Merk at entydigheten ofte gjelder hele tallinja, ikke bare intervallet. Er $f'(x)=3x^{2}+2>0$ for alle $x$, har $f$ høyst én reell rot overhodet — og det er et sterkere og penere utsagn enn å begrense seg til $[a,b]$. Si det når det er sant.

Argumentet må kunnes og er det som oftest utelates.

$$x_{k+1}=x_k-\frac{f(x_k)}{f'(x_k)}.$$

Geometrisk: legg tangenten til grafen i punktet $\left(x_k,f(x_k)\right)$. Tangentlinja er

$$y=f(x_k)+f'(x_k)\left(x-x_k\right),$$

og setter du $y=0$ og løser for $x$, får du nettopp $x_{k+1}$. Newtons metode erstatter kurven med tangenten og finner tangentens nullpunkt.

Formelen står på det utdelte formelarket — tren oppslaget på å sette inn riktig $f$ og $f'$, og på å regne brøken i én operasjon på kalkulatoren.

Kravet er at $f'(x_k)\ne 0$. Er tangenten vannrett, treffer den aldri aksen, og metoden bryter sammen.

$$\left|x_{k+1}-r\right|\le C\left|x_k-r\right|^{2}.$$

Hvorfor. Newton er fikspunktiterasjon med $g(x)=x-\dfrac{f(x)}{f'(x)}$. Deriverer du med kvotientregelen, får du

$$g'(x)=1-\frac{f'(x)^{2}-f(x)f''(x)}{f'(x)^{2}}=\frac{f(x)f''(x)}{f'(x)^{2}}.$$

I roten er $f(r)=0$, altså $g'(r)=0$ — og en fikspunktiterasjon med $g'(r)=0$ konvergerer kvadratisk, slik du så i kap. 6.3.

I praksis: typiske feilfølger er $10^{-1}$, $10^{-2}$, $10^{-5}$, $10^{-10}$. Tre–fire iterasjoner holder nesten alltid, og det er derfor eksamensoppgaver bare ber om én eller to.

Forbeholdet: kvadratisk konvergens gjelder når $f'(r)\ne 0$ og startverdien er nær nok. Er ingen av delene oppfylt, kan metoden bli treg eller sprike.

Halveringsmetoden. Start med $[a,b]$ der $f(a)$ og $f(b)$ har motsatt fortegn. Gjenta:

1. Regn midtpunktet $m=\dfrac{a+b}{2}$ og $f(m)$.
2. Har $f(a)$ og $f(m)$ motsatt fortegn, ligger roten i $[a,m]$ — sett $b=m$.
3. Ellers ligger den i $[m,b]$ — sett $a=m$.

Etter hvert skritt er intervallet halvert, og roten ligger fortsatt inne i det. Metoden kan ikke svikte så lenge fortegnsskiftet er der ved start.

Prisen er at hvert skritt gir bare ett nytt binært siffer — omtrent 0,3 desimaler. Det er tregt, men helt forutsigbart.

$$\left|x_k-r\right|\le\frac{b-a}{2^{\,k+1}}.$$

Nøyer du deg med et endepunkt som svar, er grensen $\dfrac{b-a}{2^{k}}$.

Merk at grensen ikke avhenger av $f$ i det hele tatt. Den gjelder for enhver kontinuerlig funksjon med fortegnsskifte — det er hele styrken ved metoden.

$$\frac{b-a}{2^{\,k}}\le 2\,\text{tol}\quad\text{med midtpunktet som svar}\ \Longleftrightarrow\ k\ \ge\ \log_2\frac{b-a}{2\,\text{tol}}.$$

Rund oppover. Kommer du til $k\ge 8{,}97$, er svaret 9 skritt — ikke 8.

Regn logaritmen slik på en enkel kalkulator:

$$\log_2 X=\frac{\ln X}{\ln 2}.$$

Tellingen må kunnes — den står ikke på det utdelte formelarket, og den er den eneste formen biseksjonsoppgaven kommer i.

Tre situasjoner å kjenne igjen:

1. $f'(x_k)$ nær null. Tangenten er nesten vannrett, og $x_{k+1}$ kastes langt bort. Symptomet er et enormt sprang i iteratene.
2. Dårlig startverdi. Newton konvergerer bare lokalt. Fra feil sted kan følgen løpe mot en annen rot, eller ut mot uendelig.
3. Multippel rot. Er $f(r)=f'(r)=0$, faller konvergensen fra kvadratisk til lineær. For $f(x)=(x-1)^{2}$ blir Newton-iterasjonen $\displaystyle x_{k+1}=\frac{x_k+1}{2}$, som fra $x_0=1{,}5$ gir $1{,}25,\ 1{,}125,\ 1{,}0625,\dots$ — halvering per skritt, ikke dobling av siffer.

Botemidlet i alle tre tilfellene er det samme: bruk biseksjon til å komme trygt nær roten, og bytt til Newton etterpå.

Dette er «kjenne»-stoff — du skal kunne peke på symptomet, ikke analysere det.

$$\mathbf x_{k+1}=\mathbf x_k-J_F\left(\mathbf x_k\right)^{-1}F\left(\mathbf x_k\right).$$

Sammenlikn med skalarformen: $f(x_k)$ er blitt vektoren $F(\mathbf x_k)$, og $1/f'(x_k)$ er blitt den inverse Jacobi-matrisen. Ellers er alt likt.

Formelen står på det utdelte formelarket — tren oppslaget på å sette opp $J_F$ med riktige partielt deriverte i riktige posisjoner.

$$J_F=\begin{pmatrix}\dfrac{\partial F_1}{\partial x} & \dfrac{\partial F_1}{\partial y}\\[2ex] \dfrac{\partial F_2}{\partial x} & \dfrac{\partial F_2}{\partial y}\end{pmatrix}.$$

Husk plasseringen: rad $i$ hører til likning nummer $i$; kolonne $j$ hører til variabel nummer $j$. Å transponere den ved et uhell er en dokumentert feilkilde.

Kontroll: er $F_2$ uavhengig av $y$, skal hele posisjonen $(2,2)$ være null. Slike nuller er raske å sjekke.

$$J_F\left(\mathbf x_k\right)\,\Delta\mathbf x=F\left(\mathbf x_k\right),\qquad \mathbf x_{k+1}=\mathbf x_k-\Delta\mathbf x.$$

For hånd med to ukjente går begge veier like fort, og inversen av en $2\times2$-matrise er kort:

$$\begin{pmatrix}a&b\\ c&d\end{pmatrix}^{-1}=\frac{1}{ad-bc}\begin{pmatrix}d&-b\\ -c&a\end{pmatrix}.$$

Regn ut determinanten $ad-bc$ først og skriv den ned — er den null eller nær null, er systemet singulært, og Newton-skrittet er udefinert. Det er systemversjonen av «$f'(x_k)=0$».

For store systemer er inversjon både treg og numerisk uheldig; da brukes LU-faktorisering eller en iterativ metode. Se boksen om beredskapsstoff.

$$x_{k+1}=x_k-f(x_k)\,\frac{x_k-x_{k-1}}{f(x_k)-f(x_{k-1})}.$$

Geometrisk: i stedet for tangenten bruker du sekanten gjennom $\left(x_{k-1},f_{k-1}\right)$ og $\left(x_k,f_k\right)$, og finner der den krysser aksen.

Fordelen: du trenger ikke $f'$ i det hele tatt. Det er nyttig når $f$ bare finnes som en tabell eller en simulering.
Prisen: du trenger to startverdier, og konvergensen er litt tregere enn Newtons — ordenen er omtrent $1{,}618$ i stedet for 2.

Formelen står på det utdelte formelarket — tren oppslaget. Metoden har opptrådt i 1 av de 13 gjennomgåtte settene, og det settet er fra 2015. Hold den på kjenne-nivå: vit hva den er, og kunne bruke formelen hvis den kommer.

Numerikk-siden på det utdelte formelarket inneholder også metoder for lineære likningssystemer. Boka kaller dette sjanger S, og den er på vei ut av eksamen:

- LU-faktorisering (Doolittle): skriv $A=LU$ med $L$ nedre triangulær med 1-ere på diagonalen og $U$ øvre triangulær. Deretter løses $A\mathbf x=\mathbf b$ i to trinn: først $L\mathbf y=\mathbf b$ forlengs, så $U\mathbf x=\mathbf y$ baklengs. Belegg: 1 av 13 sett (8 %).
- Jacobi og Gauss–Seidel: iterative metoder der du løser likning $i$ for ukjent $i$ og gjentar. Jacobi bruker bare gamle verdier i hver runde; Gauss–Seidel bruker de nyeste med én gang og konvergerer derfor som regel raskere. Belegg: 2 av 13 sett (15 %).

Hvorfor de likevel er verdt fem minutter: de står på arket, formlene er korte, og dukker en slik oppgave opp, er den ren innsetting. Men de har ingen egen kapittelkjede i denne boka, og de er ikke verdt drilltid.

De henger dessuten sammen med dette kapitlet: løser du Newton-systemet i løkke 3 for et stort system, er det nettopp LU eller Gauss–Seidel du ville brukt i stedet for å invertere $J_F$.

Tallet $p$ i uttrykket $\left|x_{k+1}-r\right|\le C\left|x_k-r\right|^{p}$.

Tre vanlige måter å avgjøre når du er ferdig:

1. $\left|x_{k}-x_{k-1}\right|<\text{tol}$ — iteratene beveger seg lite. Vanligst, men kan lure deg ved svært flat konvergens.
2. $\left|f(x_k)\right|<\text{tol}$ — funksjonsverdien er nær null. Kan lure deg motsatt vei: er $f'$ liten nær roten, kan $|f|$ være bitte liten langt fra $r$.
3. Fast antall skritt fra en teoretisk telling — det er det biseksjon og fikspunkt bruker.

På eksamen brukes nesten alltid nummer 3, fordi antallet skal kunne regnes ut på forhånd. Men det er verdt å vite at nummer 1 og 2 kan svikte hver sin vei, og at et robust program sjekker begge.