TMA4212: Numerisk løsning av differensialligninger med differansemetoder
$\newcommand{\C}{\mathbb{C}}$
$\newcommand{\R}{\mathbb{R}}$
$\newcommand{\O}{\mathcal{O}}$
# Introduksjon
## Gershgorin's teorem
> La $A = (a_{ik}) \in \C^{n\times n}$ være en kvadratisk matrise. Definer $$S = \bigcup_{j} \left\{ z \in \C: \lvert z - a_{jj} \rvert \leq \sum_{k \neq j} \lvert a_{jk} \rvert \right\},$$
> til å være unionen av sirklene sentrert rundt de diagonale elementene i $A$, med radius lik summen av absoluttverdien til de resterende elementene, respektivt på hver rad. Da inneholder $S$ alle egenverdiene til $A$.
## Spektralradius
> La $A = (a_{ik}) \in \C^{n\times n}$ være en kvadratisk matrise. **Spektralradiusen** til $A$ er definert som egenverdien til $A$ med størst absoluttverdi: $$\rho(A) = \max(\{\lambda_1, \lambda_2,\ldots,\lambda_n\}).$$
## Vektornormer
Vektorrom kan utstyres med en *norm*. Uformelt kan vi si at en slik norm gir oss en metode for å måle elementer av vektorrommet. Naturlig nok, er den velkjente lengdeformelen $\mathrm{\lVert x \rVert} = \sqrt{x_1^2 + x_2^2 + \ldots + x_n^2}$ en norm over $\R^n$.
> La $X$ være et vektorrom. En **vektornorm** er en avbildning $\lVert \cdot \rVert: X \to \C\>(\R)$, slik at følgende krav er tilfredstilt:
>
> 1. $\lVert x \rVert \geq 0,\>\forall x \in X,\> \lVert x \rVert = 0 \iff x = 0$
> 2. $\lVert ax \rVert = \lvert a \rvert \lVert x \rVert,\>\forall a \in \C\>(\R), \forall x \in X$
> 3. $\lVert x + y \rVert \leq \lVert x \rVert + \lVert y \rVert$
Eksempler på vektorrom, for $x = [x_1, x_2,\ldots,x_n], X = \C^n$.
$$
\begin{align}
\lVert x \rVert_1 &= \sum_i \lvert x_i \rvert \\
\lVert x \rVert_2 &= \sqrt{\sum_i \lvert x_i\rvert ^2} \\
\lVert x \rVert_p &= \left(\sum_i \lvert x_i\rvert^p\right)^{\frac 1p} \\
\lVert x \rVert_{max} &= \max_{1 \leq i \leq n} \lvert x_i \rvert
\end{align}
$$
## Matrisenormer
Matriserom kan utstyres med normer på samme måter som vektorrom.
> La $K^{m \times n}$ være et matriserom. En **matrisenorm** er en avbildning $\lVert \cdot \rVert: K \to \C\>(\R)$, slik at følgende krav er tilfredstilt:
>
> 1. De tre kravene for vektornormer.
> 2. $\lVert A\cdot B \rVert \leq \lVert A \rVert \cdot \lVert B \rVert$, hvis matrisemultiplikasjon er definert for $A,B \in K^{m \times n}$.
Eksempler på matrisenormer, for $A = (a_{ik}), K = C^{m \times n}$:
$$
\begin{align}
\lVert A \rVert_1 &= \max_{1 \leq k \leq n} \sum_{i=1}^n \lvert a_ik \rvert \\
\lVert A \rVert_2 &= \sqrt{\rho(A^TA)} \\
\lVert A \rVert_{\infty} &= \max_{1 \leq i \leq n} \sum_{k=1}^n \lvert a_ik \rvert \\
\lVert A \rVert_{\mathrm{frobenius}} &= \left(\sum_{i=1}^n \sum_{j=1}^n \lvert a_ij\rvert^2\right)^{\frac 12}
\end{align}
$$
## Stor-$\O$ notasjon
Stor-$\O$ notasjon brukes til å beskrive en øvre grense for hvordan en funksjon oppfører seg nær en grense. Ta for eksempel $f(x) = x^2$. Vi sier at $f(x) = \O(x^3),\> x \to \infty$, siden $x^3$ vokser fortere enn $x^2$ når $x$ øker mot uendelig. Merk at dette ikke betyr at $x^2 < x^3\>\forall x$. Siden vi her snakker om øvre grenser, er det klart at $f(x)$ har mange stor-$\O$ ekvivalenser: $f(x) = \O(x^4), f(x) = \O(2^x), f(x) = \O(x^2)$.
Tilsvarende kan vi se på stor-$\O$ notasjon ved grensen $0$. Ta igjen $f(x) = \O(x^2)$. Her er $f(x) = \O(x), f(x) = \O(x^2)$, men ikke $f(x) = \O(x^3)$, da $x^2$ er (mye) større enn $x^3$ når $x$ nærmer seg $0$ (ovenifra). Denne måten å beskrive hvor fort en funksjon "nærmer seg null" ved hjelp av polynomene $x^n,\>n \in \mathbb{Z}^+$ er hyppig brukt i numerisk matematikk.
> La $f, g$ være to funksjoner $f, g:C \to C$. Da er $f(x) = \O(g(x))$ i grensen mot $x_0 \in R \cup \infty$ hvis det finnes $M, \delta > 0$ slik at
>
> $$ \lvert f(x) \rvert \leq M g(x), \forall x; \lvert x - x_o \rvert < \delta$$
Definisjonen sier med andre ord at vi kan alltids finne en konstant $M$ slik at funksjonen $f$ vil være øvrig bundet av $g$ ganget med $M$, tilstrekkelig nærme grensen vår.
> La $f$ være en funksjon $f:C\to C$. La $f(x) = \O(x^p)$ mot en grensen $x_0 \in R \cup \infty$(typisk 0). Vi sier da at $f$ er av **orden p**.
## Taylorrekker
La $f(x)$ være en kontinuerlig $n+1$-deriverbar funksjon på et intervall $I$. Da har vi for $x+h \in I$:
$$
f(x+h) = f(x) + h f'(x) + h^2 \frac{f''(x)}{2!} + h^3 \frac{f'''(x)}{3!} + \dots + h^n \frac{f^{(n)}(x)}{n!} + R_n
$$
hvor $R_n = h^{n+1}\frac{f^{(n+1)}(x + \theta h)}{(n+1)!},\>\theta \in [0, 1]$. Eventuelt kan vi si at $R_n = \O(h^{n+1})$.
# Diskretisering og differanseoperatorer
## Grunnleggende metode
Vi ønsker å løse (partielle) differensiallikninger. Det lar seg ikke alltid gjøre så enkelt analytisk. Istedet for den analytiske tilnærmingen, ønsker vi dermed å anvende numeriske metoder for å estimere løsningen.
Vi begynner med definisjonen av den deriverte:
$$
f'(x) = \lim_{h\to\0} \frac{f(x+h) - f(x)}{h}
$$
Det er tydelig at vi kan estimere $f'(x)$ ved å sette inn en verdi for $h$. Estimatet vil forbedres ved å gjøre $h$ så liten som nødvendig. Så hvor stor er egentlig feilen her? Ser vi på taylorrekken rundt $f(x+h)$ får vi
$$
f(x+h) = f(x) + h f'(x) + \O(h^2) \implies f'(x) = \frac{f(x+h) - f(x)}{h} + \O(h)
$$
Vi har med andre ord en tilnærming i *første orden av h* til den deriverte. Vi har nå en formel vi kan bruke til å iterativt regne ut differensiallikninger av første orden. Ta eksempelvis:
$$
u'(x) - 3 = 5u(x),\>u(0) = 10,\> x \in [0, 3]
$$
Vi *diskretiserer* domenet, ved å la $h=0.1$. Vi kan nå regne ut $u(x)$ ved å "hoppe" steg med lengde $h$:
$$
\begin{align}
u'(x) - 3 =& 5u(x) \\
\frac{u(x+h) - u(x)}{h} - 3 =& 5u(x) \\
u(x+h) - u(x) =& h(5u(x) + 3) \\
u(x+h) =& u(x) + h(5u(x) + 3) \\
\end{align}
$$
Eksplisitt for de 3 første stegene:
$$
\begin{align}
u(0.1) =& u(0) + 0.1\cdot(5\cdot u(0) + 3) = 15.3 \\
u(0.2) =& u(0.1) + 0.1\cdot(5\cdot u(0.1) + 3) = 23.25 \\
u(0.3) =& u(0.2) + 0.1\cdot(5\cdot u(0.2) + 3) = 35.175 \\
\end{align}
$$
De tilsvarende analytiske verdiene for systemet er $16.88$, $28.21$, og $46.91$.
## Differanseoperatorer
Det er flere måter å approksimere den deriverte på. Og da vi etterhvert har lyst til å arbeide med deriverte av høyere grad, trenger vi å introdusere flere differanseoperatorer:
### Deriverte av første grad
|| Forkunnskaoverdifferens || $\Delta u(x) = u(x+h) - u(x)$ ||
|| Bakoverdifferens || $\nabla u(x) = u(x) - u(x-h)$ ||
|| Sentraldifferens || $\delta u(x) = u(x+h/2) - u(x - h/2)$ ||
|| Middelverdi || $\mu u(x) = \frac{1}{2}(u(x + h/2) + u(x - h/2))$ ||
Disse kan da kombineres perå interessante måter til å approksimere deriverte. Eksempelvis er det vanlig å approksimere andrederiverte ved å anvende sentraldifferense to ganger:### Differanseoeriverte av andre grad
$$ \delta^2 u(x) = \delta(u(x+h/2) - u(x - h/2)) = u(x+h) - u(x) - (u(x) - u(x-h)) = u(x+h) - 2u(x) - u(x-h)$$
|| Sentraldifferense i annen || $u(x+h) - 2u(x) + u(x-h)$ ||
|| Middelverdi i annen || $\frac 14 (u(x+h) + 2u(x) + u(x-h)$ ||
# Konsistens
# Stabilitet
# Konvergens
# Diskretisering av den én-dimensjonale Poissonlikningen
# Diskretisering av varmeledningslikningen
# Elliperatorer
# Enkle grenseverdiproblemer
# Varmelikningen
# Elliptiske differensialtisike likninger# Hyperbolske differensiallikninger
erbolske likninger