Numerikk

Numeriske metoder brukes dersom man har et problem som ikke lar seg løse på eksakt vis.

Innholdsfortegnelse:
Ligningsløsere
Numerisk integrasjon

I anvendelser av matematikk har man ofte bruk for å løse ligninger som ikke kan løses analytisk. Et klassisk eksempel er \(x=\cos x\).

Fikspunktiterasjon

Hvis vi har en ligning på formen \(x=g(x)\), vil iterasjonen \[x_{n+1}=g(x_{n})\] under visse omstendigheter konvergere til korrekt løsning.

Newtons metode
Hvis vi har en ligning på formen \(f(x)=0\), vil iterasjonen \[x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}.\] under visse omstendigheter konvergere til korrekt løsning.

Et ordentlig bevis for konvergens av fikspunktiterasjonen
Det er mulig å sette opp tilstrekkelige kriterier for fikspunktiterasjonens konvergens med teknikkene vi lærer i Matte 1.

Noen ganger er det ikke mulig å finne en antiderivert av integranden uttrykt ved kjente funksjoner; for eksempel er det ikke mulig å finne en formel for \(\int \sin(x^2) dx\). Det lar seg likevel gjøre å finne nøyaktige og effektive numeriske metoder for å approksimere \(\int_{a}^{b} \sin(x^2) dx\).

De tre numeriske metodene som følger bruker alle samme strategi. Gitt en funksjon \(f\) på et intervall \([a,b]\), del intervallet \([a,b]\) opp i \(n\) delintervall av lik lengde \(h=\frac{b-a}{n}\) og approksimèr \(f\) på hvert delintervall med en enklere funksjon. Forskjellen på de tre metodene er hva slags funksjoner de bruker til å approksimere \(f\) med på delintervallene.

Trapesmetoden:
Vi approksimerer \(f\) ved lineær interpolasjon på hvert delintervall. Dette gir et trapes på hvert delintervall, og arealformelen for trapes gir

\[\int_a^b f(x)\mathrm{d}x \simeq T_n = h\left(\frac{f(x_0)+f(x_1)}{2}+\ldots+\frac{f(x_{n-1})+f(x_n)}{2}\right)=h\left(\frac{f(x_0)}{2}+\sum_{i=1}^{n-1}f(x_i) +\frac{f(x_n)}{2}\right).\]

Midtpunktmetoden:
På hvert delintervall \([x_{i-1},x_i]\) lar vi \(f((x_{i-1}+x_i)/2)\) approksimere \(f\), og får

\[\int_a^b f(x)\mathrm{d}x \simeq M_n = h\left( f(m_1)+f(m_2)+\cdots+f(m_n) \right).\] Legg merke til at tilnærmingen gitt av midtpunktregelen er riemannsummen med \(\Delta x_i = h\) og seleksjonspunktet er \(s_i = m_i\), midtpunktet på intervall nummer \(i\).

Teorem
Dersom \(f\) er to ganger kontinuerlig deriverbar på \([a, b]\) og det gjelder \(\left|f''(x) \right| \leq K\) for alle \(x \in [a, b]\), så kan feilen til trapesmetoden og midpunktmetoden estimeres som \[\left| \int_a^b f(x) \,\mathrm{d}x - T_n \right| \leq \frac{K (b-a)}{12} h^2 = \frac{K (b-a)^3}{12 n^2}, \] \[\left| \int_a^b f(x) \,\mathrm{d}x - M_n \right| \leq \frac{K (b-a)}{24} h^2 = \frac{K (b-a)^3}{24 n^2}. \]

Simpsons metode:
Denne metoden krever at tallet på delintervall er gitt som partallet \(2n\). Vi kan da slå sammen to og to intervall og få et større delintervall av lengde \(2h\) med \(3\) kjente funksjonsverdier på hvert av de sammenslåtte delintervallene. På hvert delintervall approksimerer vi da \(f\) med den unike kvadratiske funksjonen som går igjennom dissse tre punktene. Dette gir Simpsons regel

\[\int_a^b f(x)\mathrm{d}x \simeq S_{2n} = \frac{h}{3}\left( f(x_0)+4f(x_1)+2f(x_2)+4f(x_3)+\cdots+ 2f(x_{2n-2})+ 4f(x_{2n-1})+f(x_{2n}) \right),\] der odde indekser har koeffisient \(4\), partallsindekser har koeffisient \(2\), og endepuntene har koeffisient \(1\).

Teorem
Dersom \(f\) er fire ganger kontinuerlig deriverbar på \([a, b]\) og \(\left|f^{(4)}(x) \right| \leq K\) for alle \(x \in [a, b]\), så kan feilen til Simpsons metode estimeres som \[\left| \int_a^b f(x) \mathrm{d}x - S_{2n} \right| \leq \frac{K (b-a)}{180} h^4. \]