TMA4212: Numerisk løsning av differensialligninger med differansemetoder
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
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:
$\lVert x \rVert \geq 0,\>\forall x \in X,\> \lVert x \rVert = 0 \iff x = 0$ $\lVert ax \rVert = \lvert a \rvert \lVert x \rVert,\>\forall a \in \C\>(\R), \forall x \in X$ $\lVert x + y \rVert \leq \lVert x \rVert + \lVert y \rVert$
Eksempler på vektorrom, for
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:
- De tre kravene for vektornormer.
$\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
Stor-$\O$ notasjon
Stor-
Tilsvarende kan vi se på stor-
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 \lvert g(x) \rvert, \forall x; \lvert x - x_o \rvert < \delta$$
Definisjonen sier med andre ord at vi kan alltids finne en konstant
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
hvor
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
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:
Vi diskretiserer domenet, ved å la
Eksplisitt for de 3 første stegene:
De tilsvarende analytiske verdiene for systemet er
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 | |
Bakoverdifferens | |
Sentraldifferens | |
Middelverdi |
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
Sentraldifferense i annen | |
Middelverdi i annen |
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:
For en partiell differensiallikning
Eksplisitte og implisitte metoder
Eksplisitte metoder
Eksplisitte metoder er metoder som er avhengig bare av de forige tidsstegene for å regne ut neste tidssteg. Dette betyr at utregningen av det neste tidssteget kan gjøres eksplisitt med en lineær kombinasjon av de tidligere tidsstegene. Ta for eksempel liknigen
Vi kan her altså regne ut neste tidssteg direkte ved å bruke resultater fra de tidligere tidsstegene.
Implisitte metoder
Vi kan derimot diskretisere "rundt" et tidssteg
Her har vi et nytt problem, i at vi på venstresiden har en differanse i tidssteg
Avbruddsfeil (Truncation error)
Avbruddsfeil defineres som feilen introdusert ved å "brekke av" en uendelig sum ved et endelig steg. Ta for eksempel taylorrekken ovenfor
Om vi her approksimerer
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:
Vi estimerer
Vi ekspanderer
merk her at
Så vi har nå funnet et utrykk som likner på den originale differensiallikningen, med en avbruddsfeil, nemlig
Bruker vi notasjonen
Konsistens
En differanseapproksimasjon er konsistent hvis
$\tau_n^m \to 0$ for alle$n, m$ når$k, h \to 0$ .
Konsistens er ett av kravene for
Stabilitet
Uformelt beskriver stabilitet hvorvidt en differansemetode vil holde seg innenfor et begrenset område, i løpet av estimeringsprosessen for et gitt system. Kontrapositivt vil en ustabil metode kunne "eksplodere", oppføre seg sporadisk og aldri tilnærme seg en løsning. Eventuelt kan vi si at stabilitet betyr at en differansemetode ikke vil øke feil fra steg til steg i approksimasjonen.
La
En differanseapproksimasjon
$P_{kh}u$ er stabil i en region$\Lambda$ hvis det finnes et heltall$J$ slik at for enhver positiv tid$T$ , så er det en konstant$C_T$ slik at
$$\lVert u^n \rVert_k \leq C_T \sum_{j=1}^J \lVert u^j \rVert_k$$ for enhver$0 \leq nk \leq T$ ,$(k, h) \in \Lambda$ .
Definisjonen forteller oss at vi ved et punkt
Definisjonen er dessverre vanskelig å anvende, og vi bruker som regel andre verktøy for å vise stabilitet.
En-stegs metoder
La oss se på en generell en-stegs differanseapproksimasjon
La
$U^{n+1} = CU^n + q^n$ være en differanseapproksimasjon for en PDE i$[0,1] \times [0, T]$ . Denne er stabil hvis det finnes en konstant$L$ uavhengig av$l$ og$k$ slik at for enhver vektor$w^0$ og sekvensen$w^{n+1} = Cw^n$ så har vi
$$ \lVert w^n \rVert \leq L \lVert w^0 \rVert,\> 0 \leq nk \leq T$$
Om vi lar
La
$U^{n+1} = CU^n + q^n$ være en differanseapproksimasjon for en PDE i$[0,1] \times [0, T]$ . Denne er stabil hvis det finnes en$L$ slik at
$$\lVert C^n \rVert \leq L,0 \leq nk \leq T$$
Vi kan formilde kravet for stabilitet noe:
La
$U^{n+1} = CU^n + q^n$ være en differanseapproksimasjon for en PDE i$[0,1] \times [0, T]$ . Denne er stabil hvis det finnes en$\mu$ uavhengig av$k$ og$h$ slik at
$$\lVert C \rVert \leq 1 + \mu k$$
Til slutt er følgende et krav for stabilitet (men er ikke alltid tilstrekkelig for å garantere stabilitet):
La
$U^{n+1} = CU^n + q^n$ være en differanseapproksimasjon for en PDE i$[0,1] \times [0, T]$ . Om den er stabil, finnes det en$\nu \geq 0$ uavhengig av$k$ og$h$ slik at
$$\rho(C) \leq 1 + \nu k$$
Da mange av metodene vi jobber med er en-stegs metoder, er definisjonene og kravene ovenfor nyttige.
Von-Neumann stabilitet
Metoden som ofte brukes til å (av)vise stabilitet, er Von-Neumann analyse. Metoden kan kort beskrives ved følgende steg:
- Erstatt alle
$u_n^m$ i differanseapproksimasjonen med$g^n e^{im\theta}$ . - Manipuler til et utrykk for
$g$ . - Bruk en av de følgende teoremene for å (av)vise stabilitet.
Funksjonen
En ett-stegs differanseapproksimasjon er stabil i en region
$\Lambda$ hvis og bare hvis det finnes en konstant$\mu$ (uavhengig av$\theta$ ,$k$ og$h$ , slik at
$$\lvert g(\theta, k, h) \rvert \leq 1 + \mu k$$
Om
En ett-stegs differanseapproksimasjon er stabil i en region
$\Lambda$ hvis og bare hvis det finnes en konstant$\mu$ (uavhengig av$\theta$ ,$k$ og$h$ , slik at
$$\lvert g(\theta) \rvert \leq 1$$
Konvergens
Det store spørsmålet vi er ute etter når vi anvender en numerisk metode for å løse en gitt PDE, er om metoden vår konvergerer. Med andre ord er vi interessert i å vite om den approksimerte løsningen vår tilnærmer seg den analytiske løsnigen.
Etter en runde med en numeriske metode, har vi en approksimert løsning
når
Lax' ekvivalensteorem
En differanseapproksimasjon er konvergent hvis og bare hvis den er både stabil og konsistent.