Formelsamling för Numeriska metoder, grundkurs

|\Delta x|=|\tilde{x}-x|,\qquad |\delta x|=\frac{|\tilde{x}-x|}{|x|}

Vad gör formeln?: Mäter felet i en approximation både i absoluta tal och i förhållande till storleken.
När får den användas?: Det exakta värdet betecknas x och approximationen x̃; det relativa felet kräver att x inte är noll.

Enodas sammanfattning

Felfortplantningsformeln

E_y \approx \sum_{i=1}^{n}\left|\frac{\partial f}{\partial x_i}\right| E_{x_i}

Vad gör formeln?: Felgränsen i resultatet är summan av varje indatafels bidrag, viktat med hur känsligt resultatet är för den storheten.
När får den användas?: Felen i indata är små och funktionen är deriverbar i den aktuella punkten.

Enodas sammanfattning

Noggrannhetsordning

E(h)\approx Ch^{p},\qquad \frac{E(h)}{E(h/2)}\approx 2^{p}

Vad gör formeln?: Beskriver hur snabbt diskretiseringsfelet krymper när steglängden halveras.
När får den användas?: Steglängden är så liten att den ledande feltermen dominerar, men inte så liten att avrundningsfel tar över.

Enodas sammanfattning

Konvergensordning för en iteration

|e_{n+1}|\approx C|e_n|^{p},\qquad e_n=x_n-\alpha

Vad gör formeln?: Beskriver hur snabbt felet i en iterationsföljd minskar från ett steg till nästa.
När får den användas?: Gäller lokalt nära roten α och för tillräckligt stora iterationsnummer.

Enodas sammanfattning

Felskattning ur successiva approximationer

E(h)\approx|F(h)-F(h/2)|

Vad gör formeln?: Skattar felet i en approximation med skillnaden till nästa förfining, när det exakta värdet saknas.
När får den användas?: Kräver att metoden konvergerar och att den finare approximationen är klart noggrannare än den grövre.

Enodas sammanfattning

Antal korrekta decimaler

|\tilde{x}-x|\le\tfrac{1}{2}\cdot 10^{-d}

Vad gör formeln?: Översätter en felgräns till hur många decimaler som kan anges med säkerhet.
När får den användas?: Gäller när felgränsen avser avrundning till d decimaler i det aktuella talet.

Enodas sammanfattning

Linjära ekvationssystem

LU-faktorisering

A=LU,\qquad Ly=b,\quad Ux=y

Vad gör formeln?: Delar upp systemmatrisen i triangulära faktorer så att lösningen fås ur två billiga substitutioner.
När får den användas?: Faktoriseringen finns för en inverterbar matris, vid behov efter radbyten genom pivotering.

Enodas sammanfattning

Beräkningskomplexitet för Gausseliminering

N\approx\frac{2n^{3}}{3},\qquad \frac{t(n_2)}{t(n_1)}\approx\left(\frac{n_2}{n_1}\right)^{3}

Vad gör formeln?: Arbetet växer med kuben på antalet obekanta, så en fördubblad problemstorlek kostar ungefär åtta gånger mer.
När får den användas?: Gäller en full matris utan särskild struktur, där n är antalet obekanta och n är stort.

Enodas sammanfattning

Beräkningskomplexitet för triangulära system

N\approx n^{2},\qquad \frac{t(n_2)}{t(n_1)}\approx\left(\frac{n_2}{n_1}\right)^{2}

Vad gör formeln?: Substitution i ett triangulärt system kostar kvadratiskt, alltså en potens mindre än elimineringen.
När får den användas?: Systemet är redan triangulärt och löses med framåt- eller bakåtsubstitution.

Enodas sammanfattning

Maxnorm för vektor och matris

\|x\|_\infty=\max_i|x_i|,\qquad \|A\|_\infty=\max_i\sum_{j}|a_{ij}|

Vad gör formeln?: Mäter storleken på en vektor som dess största komponent och på en matris som den största radsumman.
När får den användas?: Matrisnormen är den norm som induceras av vektorns maxnorm, alltså den största absoluta radsumman.

Enodas sammanfattning

Konditionstal

\kappa(A)=\|A\|\,\|A^{-1}\|

Vad gör formeln?: Mäter hur känslig lösningen till ett linjärt system är för störningar i indata.
När får den användas?: A är inverterbar och samma norm används för båda faktorerna; konditionstalet är alltid minst ett.

Enodas sammanfattning

Felförstärkning i linjära system

\frac{\|\Delta x\|}{\|x\|}\le\kappa(A)\,\frac{\|\Delta b\|}{\|b\|}

Vad gör formeln?: Begränsar det relativa felet i lösningen med konditionstalet gånger det relativa felet i högerledet.
När får den användas?: Störningen ligger i högerledet och systemmatrisen antas exakt; olikheten är en övre gräns, inte ett väntevärde.

Enodas sammanfattning

Ickelinjära ekvationer

Newton-Raphsons metod

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.

Enodas sammanfattning

Newtons metod för system

J(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.

Enodas sammanfattning

Sekantmetoden

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.

Enodas sammanfattning

Fixpunktsiteration

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.

Enodas sammanfattning

Fixpunktsiterationens konvergensvillkor

|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 α.

Enodas sammanfattning

Bisektionsmetodens felgräns

|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.

Enodas sammanfattning

Interpolation

Interpolationsvillkor och gradtal

p(x_i)=y_i,\quad i=0,\dots,n\qquad\Rightarrow\qquad \deg p\le n

Vad gör formeln?: Kopplar antalet datapunkter till interpolationspolynomets gradtal och storleken på ekvationssystemet.
När får den användas?: Punkterna har olika x-värden; då finns exakt ett polynom av grad högst n som uppfyller villkoren.

Enodas sammanfattning

Vandermondesystemet

\begin{pmatrix}1 & x_0 & \cdots & x_0^{n}\\ 1 & x_1 & \cdots & x_1^{n}\\ \vdots & \vdots & & \vdots\\ 1 & x_n & \cdots & x_n^{n}\end{pmatrix}\begin{pmatrix}c_0\\ c_1\\ \vdots\\ c_n\end{pmatrix}=\begin{pmatrix}y_0\\ y_1\\ \vdots\\ y_n\end{pmatrix}

Vad gör formeln?: Skriver interpolationsvillkoren i monombasen som ett linjärt system för polynomets koefficienter.
När får den användas?: Matrisen är inverterbar när x-värdena är parvis olika, men blir illakonditionerad för många punkter.

Enodas sammanfattning

Newtons interpolationsansats

p(x)=c_1+c_2(x-x_1)+c_3(x-x_1)(x-x_2)+\cdots

Vad gör formeln?: Bygger interpolationspolynomet stegvis så att koefficienterna kan lösas ut en i taget.
När får den användas?: Punkterna numreras i den ordning de sätts in; varje ny term försvinner i alla tidigare punkter.

Enodas sammanfattning

Linjär interpolation

p(x)=y_1+\frac{y_2-y_1}{x_2-x_1}(x-x_1)

Vad gör formeln?: Drar en rät linje mellan två mätpunkter och läser av värdet däremellan.
När får den användas?: Punkten x ligger mellan de två mätpunkterna; utanför intervallet blir det extrapolation.

Enodas sammanfattning

Modellanpassning med minstakvadratmetoden

Modellansats linjär i parametrarna

y(x)\approx\sum_{j=1}^{m}c_j\varphi_j(x),\qquad A_{ij}=\varphi_j(x_i),\qquad Ac\approx y

Vad gör formeln?: Bygger det överbestämda systemet genom att utvärdera modellens basfunktioner i mätpunkterna.
När får den användas?: Basfunktionerna är kända och parametrarna ingår linjärt; antalet mätpunkter överstiger antalet parametrar.

Enodas sammanfattning

Normalekvationerna

A^{T}A\widehat{c}=A^{T}y

Vad gör formeln?: Ger det kvadratiska system vars lösning minimerar residualens längd i ett överbestämt system.
När får den användas?: Kolumnerna i A är linjärt oberoende, vilket gör produkten inverterbar och minstakvadratlösningen entydig.

Enodas sammanfattning

Residualvektor och minstakvadratfel

r=y-A\widehat{c},\qquad \|r\|_2=\sqrt{\sum_{i}r_i^{2}}

Vad gör formeln?: Mäter avvikelsen mellan mätdata och anpassad modell, punkt för punkt och sammanfattat i en norm.
När får den användas?: Residualen beräknas med den anpassade parametervektorn och har en komponent per mätpunkt.

Enodas sammanfattning

Linjarisering av exponentiell modell

y=Ce^{kx}\quad\Longleftrightarrow\quad \ln y=\ln C+kx

Vad gör formeln?: Logaritmerar en exponentiell modell så att parametrarna ingår linjärt och kan anpassas med normalekvationerna.
När får den användas?: Kräver positiva mätvärden, eftersom logaritmen annars inte är definierad.

Enodas sammanfattning

Numerisk derivering och integration

Framåt- och bakåtdifferens

\begin{aligned} \frac{u_{i+1}-u_i}{h} &= u'(x_i) + O(h) \\ \frac{u_i-u_{i-1}}{h} &= u'(x_i) + O(h) \end{aligned}

Vad gör formeln?: Ensidiga första ordningens approximationer, särskilt användbara vid randen.
När får den användas?: u är minst två gånger kontinuerligt deriverbar lokalt.

Enodas sammanfattning

Centrala differenskvoten

f'(x)=\frac{f(x+h)-f(x-h)}{2h}+O(h^{2})

Vad gör formeln?: Skattar derivatan med en symmetrisk differens och har noggrannhetsordning två.
När får den användas?: Kräver funktionsvärden symmetriskt på båda sidor om punkten och att f är tillräckligt många gånger deriverbar.

Enodas sammanfattning

Central differens för andra derivatan

\frac{u_{i-1}-2u_i+u_{i+1}}{h^{2}} = u''(x_i) + O(h^{2})

Vad gör formeln?: Ger den tridiagonala kärnan i många diskretiserade randvärdesproblem.
När får den användas?: u har minst fyra kontinuerliga derivator lokalt och nätet är likformigt.

Enodas sammanfattning

Trapetsregeln

T(h)=\frac{h}{2}\left(f(x_0)+2\sum_{k=1}^{n-1}f(x_k)+f(x_n)\right)

Vad gör formeln?: Approximerar integralen med trapetser under den styckvis linjära interpolanten.
När får den användas?: Intervallet delas i n lika stora delintervall med steglängden h mellan punkterna.

Enodas sammanfattning

Trapetsregelns felterm

I-T(h)=-\frac{(b-a)h^{2}}{12}f''(\xi)=O(h^{2})

Vad gör formeln?: Visar att trapetsregelns fel är av andra ordningen och beror på funktionens krökning.
När får den användas?: f är två gånger kontinuerligt deriverbar på intervallet; ξ är en okänd punkt i intervallet.

Enodas sammanfattning

Richardsonextrapolation

\widehat{F}=\frac{2^{p}F(h/2)-F(h)}{2^{p}-1},\qquad \widehat{T}=\frac{4T(h/2)-T(h)}{3}

Vad gör formeln?: Kombinerar två skattningar med olika steglängd så att den ledande feltermen tar ut sig.
När får den användas?: Metoden har känd noggrannhetsordning p och steglängden halveras mellan de två skattningarna.

Enodas sammanfattning

Differentialekvationer

ODE till första ordningens system

y^{(n)}=F(t,y,\ldots,y^{(n-1)}),\quad x=(y,y',\ldots,y^{(n-1)})^T,\quad x'=\begin{pmatrix}x_2\\ \vdots\\ F(t,x)\end{pmatrix}

Vad gör formeln?: Skriver en ODE av ordning n som ett system med n ekvationer av första ordningen.
När får den användas?: Den högsta derivatan kan lösas ut.

Enodas sammanfattning

Framåt Euler

y_{n+1}=y_n+h f(t_n,y_n)

Vad gör formeln?: Explicit enstegsmetod av ordning ett.
När får den användas?: Steglängden h är vald så att metodens fel och stabilitet är acceptabla.

Enodas sammanfattning

Heuns metod

\begin{aligned} \tilde y_{n+1} &= y_n + h f(t_n,y_n) \\ y_{n+1} &= y_n + \frac{h}{2}\left[f(t_n,y_n) + f(t_{n+1},\tilde y_{n+1})\right] \end{aligned}

Vad gör formeln?: Heuns metod tar ett Euler-steg som prediktor och korrigerar sedan med medelvärdet av derivatorna i de två punkterna.
När får den användas?: Explicit tvåstegsmetod; funktionen måste kunna beräknas både i den kända punkten och i prediktorpunkten.

Enodas sammanfattning

Bakåt Euler

y_{n+1}=y_n+h f(t_{n+1},y_{n+1})

Vad gör formeln?: Implicit A-stabil enstegsmetod av ordning ett.
När får den användas?: Den implicita ekvationen för yₙ₊₁ kan lösas vid varje steg.

Enodas sammanfattning

Diskretisering av linjärt randvärdesproblem