Hoppa till huvudinnehållet
Logga inSkapa konto
3. Ickelinjära ekvationer

Ickelinjära ekvationer

Lös skalära ekvationer och ekvationssystem iterativt med Newtons metod, sekantmetoden och fixpunktiteration.

Översikt

Kärnan i ickelinjära ekvationer

Newtons metod linjäriserar funktionen i varje iterationspunkt. För ett system blir linjäriseringen en Jacobian, och steget fås genom att lösa ett linjärt ekvationssystem.

J(xn) Δxn=−F(xn),xn+1=xn+ΔxnJ(x_n)\,\Delta x_n = -F(x_n),\qquad x_{n+1}=x_n+\Delta x_n

Exempel

Metod och kontroll

Varje iteration kan skrivas på fixpunktsform, och derivatans belopp i fixpunkten avgör om följden dras mot roten eller drivs bort från den.

∣g′(α)∣<1,∣en+1∣≈∣g′(α)∣ ∣en∣|g'(\alpha)|<1,\qquad |e_{n+1}|\approx|g'(\alpha)|\,|e_n|

Fördjupning

Vanliga fallgropar

Samma ekvation kan skrivas om till flera fixpunktsformer, och alla konvergerar inte. Newtons metod konvergerar snabbt nära roten men kan divergera från en dålig startgissning, och för system ska steget lösas ur systemet snarare än beräknas genom att invertera Jacobianen.

Formler i området

Newton-Raphsons metod

xn+1=xn−f(xn)f′(xn)x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}
Vad gör formeln?
Ersätter funktionen med sin tangent i varje punkt och tar tangentens nollställe som nästa approximation.
När får den användas?
f är deriverbar nära roten, derivatan är skild från noll i iterationspunkterna och startgissningen ligger tillräckligt nära.

Newtons metod för system

J(xn) Δxn=−F(xn),xn+1=xn+ΔxnJ(x_n)\,\Delta x_n = -F(x_n),\qquad x_{n+1}=x_n+\Delta x_n
Vad gör formeln?
För ett ekvationssystem ersätts divisionen med derivatan av att ett linjärt system med Jacobianen löses i varje steg.
När får den användas?
Jacobianen är inverterbar i iterationspunkten och startgissningen ligger nära lösningen.

Sekantmetoden

xn+1=xn−f(xn) xn−xn−1f(xn)−f(xn−1)x_{n+1}=x_n-f(x_n)\,\frac{x_n-x_{n-1}}{f(x_n)-f(x_{n-1})}
Vad gör formeln?
Byter Newtons tangent mot sekanten genom de två senaste punkterna och slipper därmed derivatan.
När får den användas?
Kräver två startvärden och att funktionsvärdena i dem är olika, så att nämnaren inte blir noll.

Fixpunktsiteration

xn+1=g(xn),α=g(α)x_{n+1}=g(x_n),\qquad \alpha=g(\alpha)
Vad gör formeln?
Skriver om ekvationen så att roten är en fixpunkt och itererar funktionen från en startgissning.
När får den användas?
Ekvationen skrivs om så att den sökta roten är en fixpunkt till iterationsfunktionen g.

Fixpunktsiterationens konvergensvillkor

∣g′(α)∣<1,∣en+1∣≈∣g′(α)∣ ∣en∣|g'(\alpha)|<1,\qquad |e_{n+1}|\approx|g'(\alpha)|\,|e_n|
Vad gör formeln?
Avgör om en fixpunktsform konvergerar och hur snabbt felet då minskar per steg.
När får den användas?
Villkoret är lokalt: det garanterar konvergens för startgissningar tillräckligt nära fixpunkten α.

Bisektionsmetodens felgräns

∣xn−α∣≤b−a2n,n≥log⁡2 ⁣(b−aε)|x_n-\alpha|\le\frac{b-a}{2^{n}},\qquad n\ge\log_{2}\!\left(\frac{b-a}{\varepsilon}\right)
Vad gör formeln?
Ger en garanterad felgräns efter n halveringar och antalet steg som krävs för en given tolerans.
När får den användas?
f är kontinuerlig på intervallet och byter tecken mellan ändpunkterna, så att en rot är innesluten.

Kan du använda ickelinjära ekvationer?

Lös en riktig tentauppgift från SF1547 med ledtrådar och lösningsförslag. Inget konto behövs.

Prova en uppgift