$\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: $$

$$ 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 || Foroverdifferens || $\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 på interessante måter til å approksimere deriverte. Eksempelvis er det vanlig å approksimere andrederiverte ved å anvende sentraldifferense to ganger: ### Deriverte 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)$ || Som regel (i dette kurset) er det sentraldifferansen i annen som blir anvendt til approksimering av annen-deriverte. ## Notasjon Vi bruker fremover følgende notasjon for deriverte og differanser: $$ \begin{align} \frac{\partial u}{\partial x} &= u_x \\ \frac{\partial u}{\partial t} &= u_t \\ u(mh) &= u_m \\ u(mh+h) &= u_{m+1} \\ u(mh, nk) &= u_m^n \\ u(mh+h, nk+k) &= u_{m+1}^{n+1} \\ \end{align} $$ For en partiell differensiallikning $Pu = f$, hvor $P$ er en lineær kombinasjon av n'te-deriverte; denoterer vi en bestemt differanseapproksimasjon til $u$ ved $P_k u$(én variabel) eller $P_{kh} u$(to variable). # Avbruddsfeil (Truncation error) Avbruddsfeil defineres som feilen introdusert ved å "brekke av" en uendelig sum ved et endelig steg. Ta for eksempel taylorrekken ovenfor $$ 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. $$ Om vi her approksimerer $f(x+h)$ved å bruke de $n$ første leddene, får vi en avbruddsfeil $\tau = R_n = \O(x^{n+1})$. Vi får som regel en avbruddsfeil ved å bruke differansemetoder på en differensiallikning, som er avhengig av hvilke differenaseoperatorer vi bruker til å estimere de deriverte. Ta for eksempel, som før: $$ u_x - 3 - 5u(x) = 0 $$

$$ \begin{align}

Så vi har nå funnet et utrykk som likner på den originale differensiallikningen, med en avbruddsfeil, nemlig $\frac{h}{2}u_{xx} + \O(h^2)$. Bruker vi notasjonen $P_{kh}$ for differanseapproksimasjoner, kan vi definere avbruddsfeilen $$\tau_n^m = Pu - P_{kh}$$ # Konsistens > En differanseapproksimasjon er konsistent hvis > > $\tau_n^m \to 0$ for alle $n, m$ når $k, h \to 0$. # Stabilitet # Konvergens # Diskretisering av den én-dimensjonale Poissonlikningen # Diskretisering av varmeledningslikningen # Elliptisike likninger # Hyberbolske likninger