Numerische Modellierung der Diffusion

SW6: Finite-Differenzen Methode FDM

Datei:DFW6ogg audio1.ogg

Die Finite Differenzen Methode ist neben dem Finite Volumen Verfahren und dem Finite Elementen Verfahren eine der bekanntesten numerischen Diskretisierungsverfahren für partielle Differentialgleichungen.

Gitter-basierte Verfahren

Diese drei Verfahren gehören zu den Gitter-basierten Verfahren, die die unbekannte Funktion $u(x,t)$ auf endlich vielen Gitterpunkten $P_{i,j}=(x_i,y_j),i=1,\dots N_x,j=1,\dots N_y$ approximieren.

Differenzenquotient

In FDM werden die Ableitungen der gesuchten Funktion durch Differenzenquotienten ersetzt.
Im folgenden wird die Hereitung der Differenzenquotienten für eine Funktion einer Veränderlichen demonstriert.

Taylorpolynom

Approximation von ln(x) durch Taylorpolynome der Grade 1, 2, 3 bzw. 10 um die Entwicklungsstelle 1. Die Polynome konvergieren nur im Intervall (0, 2]. Der Konvergenzradius ist also 1. Author: Georg Johann

Die Taylorentwicklung der Funktion $f:ℝ\to ℝ$ im Punkt $x+h$ um den Entwicklungspunkt $x$

$f(x+h)=\sum _{k=0}^{\mathrm{\infty }}\frac{f^{(k)}(x)}{k!}(h{)}^k=f(x)+f^{\prime }(x).h+f^{″}(x)\frac{h^2}{2!}+f^{‴}(x).\frac{h^3}{3!}+\dots$ .

Die Differenzenquotienten ergeben sich als Approximation der Ableitungen von $f$ nach dem Abbruch der Taylorreihe.

Erster Differenzenquotient

Datei:DFW6ogg audio2.ogg

Sei Funktion $f$ hinreichend oft differenzierbar. Aus der Taylorformel mit dem Lagrangeschem Restglied

$\begin{array}{ccc}f(x+h)& =& f(x)+h{f}^{\prime }(x)+f^{″}(x)\frac{h^2}{2}+f^{‴}(\theta )\frac{h^3}{3!}\end{array}$

mit $\theta \in (x,x+h)$. Damit ergibt sich

• für den ersten (vorwärts-) Differenzenquotient
  

$D_h^{+}f(x):=\frac{f(x+h)-f(x)}{h}=f^{\prime }(x)+f^{″}(x)\frac{h}{2}+f^{‴}({\theta }_1)\frac{h^2}{6},{\theta }_1\in (x,x+h)$,

• für den ersten (rückwärts-) Differenzenquotient mit Anwendung von $-h$ anstatt von $h$ in der obigen Taylorformel
  

$D_h^{-}f(x):=\frac{f(x)-f(x-h)}{h}=f^{\prime }(x)-f^{″}(x)\frac{h}{2}+f^{‴}({\theta }_2)\frac{h^2}{6},{\theta }_2\in (x-h,x)$,

• für den ersten zentralen Differenzenquotient durch aus der Summe $\frac{1}{2}(D^{+}f(x)+D^{-}f(x))$,
  

$D_{h}f(x):=\frac{f(x+h)-f(x-h)}{2h}=f^{\prime }(x)+(f^{‴}({\theta }_1)+f^{‴}({\theta }_2))\frac{h^2}{12},{\theta }_1,{\theta }_2\in (x,x\pm h)$

Güte der Approximation

Alle drei erste Differenzenquotienten approximieren die erste Ableitung:
$D_h^{\pm }f(x),D_{h}f(x)\approx f^{\prime }(x)$ für $h\to 0$ falls $f$ hinreichend oft differenzierbar auf einem Intervall $[a,b]$ ist mit $x,x\pm h\in [a,b]$.

Lemma 1:

Ist $f\in C^2[a,b]$, dann gilt für alle $x\in [h,b-h]$:
   $|D_h^{\pm }f(x)-f^{\prime }(x)|\le \frac{h}{2}{C}_1$ wobei $C_1:=\underset{x\in [a,b]}{\max }|f^{″}(x)|$.
Ist $f\in C^3[a,b]$, dann gilt  für alle $x\in [h,b-h]$:
   $|D_{h}f(x)-f^{\prime }(x)|\le \frac{h^2}{6}{C}_2$ wobei $C_2=\underset{x\in [a,b]}{\max }|f^{‴}(x)|$. 

Beweis: Aus den Gleichungen für erste Differenzenquotienten $◻$.

Zweiter Differenzenquotient

Datei:DFW6ogg audio3.ogg
Der zweite Differenzenquotient approximert die zweite Ableitung $D^{2}f(x)\approx f^{″}(x)$ an der Stelle $x$, falls $f$ hinreichend oft differenzierbar ist.

Die Formel für $D^{2}f(x)$ ergibt sich aus der Differenz der ersten Differenzenquotienten $D_h^{+}f(x)-D_h^{-}f(x)$ mithilfe der Taylorentwicklung bis zur vierten Ableitung:

$D_h^{2}f(x):=\frac{f(x+h)-2f(x)+f(x-h)}{h^2}=f^{″}(x)+(f^{(IV)}({\theta }_1)+f^{(IV)}({\theta }_2))\frac{h^2}{4!}.$

Bemerkung

Die Formel für den zweiten Differenzenquotient $D_h^{2}f(x)$ kann auch durch sukzessive Anwendung des ersten zentralen Differenzenquotienten mit halber Schrittweite $D_{h/2}f(x)$ hergeleitet werden,
$D_{h/2}(D_{h/2}f(x))=D_{h/2}\left(\frac{f(x+h/2)-f(x-h/2)}{h}\right)=\frac{1}{h}(\frac{f(x+h)-f(x)}{h}-\frac{f(x)-f(x-h)}{h})\equiv D_h^{2}f(x)$.

Güte der Approximation

Lemma 2:

Ist $f\in C^4[a,b]$, dann gilt für alle $x\in [h,b-h]$
  $|D_h^{2}f(x)-f^{″}(x)|\le \frac{h^2}{12}{C}_3$ wobei $C_3:=\underset{x\in [a,b]}{\max }|f^{(IV)}(x)|$.

Beweis: Aus der Gleichung für zweiten Differenzenquotient. Der Term $(f^{(IV)}({\theta }_1)+f^{(IV)}({\theta }_2))\frac{h^2}{24}$ im Ausdruck für $D_h^{2}f(x)$ trägt zum Approximationsfehler bei $◻$.

Zusammenfassung

Datei:DFW6ogg audio3.2.ogg

Die Fehler der Differenzenquotienten kann man mithilfe des Landau-Symbols beschreiben:
$D_{h}f(x)=f^{\prime }(x)+𝒪\mathcal{(}{𝒽}^2\mathcal{)}$,
$D_h^{\pm }f(x)=f^{\prime }(x)+𝒪\mathcal{(}𝒽\mathcal{)}$,
$D_h^{2}f(x)=f^{″}(x)+𝒪\mathcal{(}{𝒽}^2\mathcal{)}$.

Differenzenquotienten höherer Ordnung

Für die Approximation Ableitungen höherer Ordnung siehe Höhere Differenzenquotienten.

Randwertproblem

Datei:DFW6ogg audio4.ogg Randwertproblem für Diffusionsgleichung beschreibt ein Diffusionsproblem auf einem beschränkten Gebiet $D\subset {ℝ}^n$. Hierbei wird das Verhalten der unbekannten Funktion am Rand des Gebietes $\partial D$ durch eine Bedingung festgelegt. Wir behandeln zuerst die stationäre Poissongleichung. $$-\mathrm{\Delta }u(x)=f(x).$$

Dirichlet Randwertproblem

Ist die gesuchte Funktion $u$ am Rand $\partial D$ durch eine gegebene Funktion festgelegt $g$, erfüllt $u$ die sog.
Dirichlet Randbedingung:

$-\mathrm{\Delta }u(x)=f(x)x\in D$

$u(x)=g(x)x\in \partial D.$

Neumann Randwertproblem

Datei:Video Richtungsableitung.webm Sind die Richtungsableitungen der Funktion $u$ in der Richtung des äußeren Normalenvektor gegeben, erfüllt $u$ die sog.
Neumann Randbedingung:

$-\mathrm{\Delta }u(x)=f(x)x\in D$

$\frac{\partial u(x)}{\partial \overrightarrow{n}}\equiv \mathrm{\nabla }u\cdot \overrightarrow{n}=g(x)x\in \partial D.$

Numerische Diskretisierung des Randwertproblems

Datei:DFW6ogg audio4.2.ogg

Dirichletproblem auf dem Intervall (1D)

Sei $x\in [a,b]\subset ℝ$. Gesucht werden Näherungen für die Funktionswerte von $[a,b]$ auf dem äquidistanten Gitter

$\{x_i=a+ih,i=1,\dots ,n\in \mathbb{N}\}\subset [a,b],h=\frac{b-a}{n+1}$

die Werte $u(a),u(b)$ sind durch die Dirichlet-Randbedingungen (Werte am linken und rechten Rand) bekannt.

Diskretisierung durch Differenzenquotient

In diesem Fall handelt es sich um gewöhnliche Differentialgleichung. Die zweiten Ableitungen werden mit Hilfe des zweiten Differenzenquotienten diskretisiert:

$D_h^{2}u(x_i)=\frac{u_{i+1}-2u_i+u_{i-1}}{h^2}\approx u^{″}(x_i)$ für jedes $i=1,\dots n$.
Hier bezeichnet $u_i:=u(x_i)$.

Lineares Gleichungssystem

Nach der Anwendung der obigen Formel für jedes $i=1,\dots n$ unter der Beachtung der Randbedingungen $u_0=u(a),u_{n+1}=u(b)$ in den Formeln für $D_h^{2}u(x_1),D_h^{2}u(x_n)$ für den Vektor den unbekannten Werte ${\overrightarrow{u}}_h:=(u_1,\dots u_n{)}^T$ ein lineares Gleichungsystem $$A_h{\overrightarrow{u}}_h={\overrightarrow{f}}_h,$$ mit einer tridiagonaler Systemmatrix $A_h$, und dem Vektor der rechten Seite ${\overrightarrow{f}}_h$,

Systemmatrix und rechte Seite

$A_h=\frac{-1}{h^2}.\left(\begin{array}{ccccc}-2& 1& 0& \dots & 0\\ 1& -2& 1& & ⋮\\ ⋮& \ddots & \ddots & \ddots & \\ 0& & \dots & 1& -2\end{array}\right),\left(\begin{array}{c}{f}_1+\frac{u_0}{h^2}\\ f_2\\ ⋮\\ f_{n-1}\\ f_n+\frac{u_{n+1}}{h^2}.\end{array}\right)$,

siehe dieses Beispiel.

SW7: Bemerkung: Lösbarkeit des linearen Gleichungssystems

Die Systemmatrix $A_h,h>0$ ist regulär und damit invertierbar, symmetrisch und positiv definit. Der Lösungsvektor (numerische Lösung) ${\overrightarrow{u}}_h$ lässt sich durch direkte Methoden für Gleichungssysteme wie Gauß-Eliminierung, oder LU und Choleski-Zerlegung bestimmen.

Außerdem kann man im Falle der streng diagonal-dominanten Matrizen iterative Verfahren wie Jacobi und Gauß-Seidel Verfahren anwenden, siehe Übersicht der Lösungsverfahren für lineare Gleichungssysteme.

SW7: Neumannproblem auf dem Intervall (1D)

Gegeben seien die Randbedingungen für die Ableitungen in den Normalrichtungen $-1,1$:
$$-u^{\prime }(a)=\alpha ,u^{\prime }(b)=\beta .$$

Um die Ableitungen in den Randpunkten zu approximieren, führen wir neue Unbekannte $u_0:=u(a),u_{n+1}:=u(b)$ ein.

Datei:DFW7ogg audio1.ogg

Approximation erster Ordnung

Verwendet man einseitige Differenzenquotienen für die Approximation der Ableitung an den Rändern,

• den vorwärts -Differenzenquotient $D_h^{+}u(a)=\frac{u_1-u_0}{h}=u^{\prime }(a)+𝒪(h)$
• den rückwärts -Differenzenquotient $D_h^{-}u(b)=\frac{u_{n+1}-u_n}{h}=u^{\prime }(b)+𝒪(h)$

erhält man für die neuen Unbekannte $u_0,u_{n+1}$ die 0-te und die $n+1$- te Gleichung,
$u_0=u_1+h\alpha +𝒪(h^2)$,
$u_{n+1}=u_n+h\beta +𝒪(h^2)$.

Aufgabe Stellen Sie die Systemmatrix ${\tilde{A}}_h$ und den Vektor der rechten Seite für diese Approximation der Neumann Randbedingung auf. Ist diese Matrix regulär?

Die Genauigkeit des Approximationsschemas gegeben durch das obere lineare Gleichungssystems ist durch diese Approximation der Ableitungen am Rand des Intervalls reduziert auf die erste Ordnung, der vernachlässigte Fehler ist insgesamt von der Größenordnung $𝒪(h)$.

Approximation zweiter Ordnung

Datei:DFW7ogg audio2.ogg

Um die Approximationsgüte der zweiten Differenzquotienten für die Approximation von $u^{″}(x)$ im Inneren des Intervalls $𝒪(h^2)$, auch für die Randbedingungen zu erhalten, verwendet man den ersten zentralen Differenzenquotient:

$D_{h}u(a)=\frac{u_1-u_{-1}}{2h}=u^{\prime }(a)+𝒪(h^2)$

$D_{h}u(b)=\frac{u_{n+2}-u_n}{2h}=u^{\prime }(b)+𝒪(h^2)$.

Damit man das lineare Gleichungssystem nicht wieder um neue Gleichungen für $u_{-1},u_{n+2}$ ergänzen muss, eliminiert man diese Variablen mithilfe der Randbedingungen. Man erhält aus obigen Gleichungen für $D_h$ folgende Gleichungen für $u_{-1},u_{n+2}$:

$u_{-1}=u(a-h)=u_1-2h{u}^{\prime }(a)+𝒪(h^3)=u_1+2h\alpha +𝒪(h^3)$,

$u_{n+2}=u(b+h)=u_n+2h{u}^{\prime }(b)+𝒪(h^3)=u_n+2h\beta +𝒪(h^3)$.

Ersetzt man $u_{-1},u_{n+2}$ in den Gleichungen für den zweiten Differenzenquotient $D_h^{2}u(x_0),D_h^{2}u(x_{n+1})$ aus obigen Gleichungen, erhält man anstelle der ersten und letzter Gleichung des linearen Systems:
$\frac{2u_1-2u_0}{h^2}=-2\alpha /h+𝒪(h),\frac{2u_n-2u_{n+1}}{h^2}=-2\beta /h+𝒪(h).$

Basierend auf der Approximation der ersten Ableitungen an den Rändern durch ersten zentralen Differenzenquotient erhält man auf diese Weise insgesamt die Approximation zweiter Ordnung.

Bemerkung: Dass die ersten zwei Gleichungen die Approximation mit einem Fehler insgesamt von der Größenordnung $𝒪(h^2)$ darstellen, sieht man nach der Multiplikation der obigen zwei Gleichungen mit $h/2$.

Aufgabe: Stellen Sie die Systemmatrix ${\tilde{A}}_h$ und den Vektor der rechten Seite für diese Approximation der Neumann Randbedingung auf.

Bemerkung zur Lösbarkeit des linearen Systems für Neumann-Problem

Datei:DFW7ogg audio3.ogg

Die Systemmatrix ${\tilde{A}}_h\in {ℝ}^{(n+2)\times (n+2)}$ ergänzt um die neuen Zeilen/Spalten für die Approximation der Neumann Randbedingung ist singulär, denn es gilt ${\tilde{A}}_h\mathrm{𝟏}=\mathrm{𝟎}$ wobei $\mathrm{𝟏}=(1,1,\dots ,1),\mathrm{𝟎}=(0,0,\dots ,0).$.

Man kann zeigen (Gauß Eliminierung) $Rang({\tilde{A}}_h)=n+1,$.

Damit ist die Lösung dieses linearen System nicht eindeutig.
Dies korrespondiert auch mit der Theorie dieser Differentalgleichung und dem Erhaltungsgesetz:

Nicht-Eindeutigkeit und die notwendige Bedingung für Neumann-Problem

• Wenn die Funktion $u(x)$ eine Lösung des Neumannproblems ist, dann ist diese Lösung nicht eindeutig, auch $u(x)+c$ für jede beliebige Konstante ist eine Lösung.

Die Ableitungen am Rand bestimmen die Steigung der gesuchten Funktion, aber nicht deren Wert. Durch das Festlegen eines Wertes der gesuchten Funktion, z.B. $u_0=u(a)$ wird die Lösung eindeutig.

• existiert eine Lösung des Neumann Randwertproblems, dann muss diese nach der Integration erfüllen:
  

$\underset{a}{\overset{b}{\int }}{u}^{″}(x)dx=u^{\prime }(b)-u^{\prime }(a)=\alpha +\beta =\underset{a}{\overset{b}{\int }}f(x)dx$
bzw. (mehrdimensional, Anwendung von Satz von Stokes, siehe ):
$\underset{D}{\int }\mathrm{\Delta }u(x)dx=\underset{\partial D}{\int }\mathrm{\nabla }u\cdot \overrightarrow{n}dSx=\underset{\partial D}{\int }gdSx=\underset{d}{\int }f(x)dx$,
also müssen die Flüsse über den Rand $\alpha$ und $\beta$ , bzw. $g$ mit dem Quellström $f$ im folgenden Sinne korrespondieren:
Im stationären Zustand balanciert der Materialfluss durch die Ränder die Materialquelle im Inneren.

Dirichletproblem in 2 Raumdimensionen

Datei:DFW7ogg audio4.ogg

Sei u die gesuchte Funktion definiert auf einem Rechteck D:
$u:{ℝ}^2\to ℝ,𝐱=(x,y)\in D:=[a,b]\times [c,d]$. Wir betrachten das Dirichlet-Randwertproblem mit homogenen Randbedingungen:

$$\begin{array}{cc}-\mathrm{\Delta }u(x)& =f(x)\text{in }D\subset {ℝ}^2,\\ u& =0\text{auf}\partial D\end{array}$$

Punktegitter

Der einfachste Fall ist die Verwendung eines äquidistanten Gitters

$\{(x_i,y_j),i=1,\dots n,j=1,\dots m\}$
mit konstanter Gittergröße h:
$h=x_i-x_{i-1}=y_j-y_{j-1}=\frac{b-a}{n+1}=\frac{d-c}{m+1},i=1,\dots n,j=1,\dots m$

Man bezeichne die Approximationen der Lösung in den Gitterpunkten $(x_i,y_j):$

$u_{i,j}:\approx u(x_i,y_j),i=1,\dots n,j=1,\dots m.$

Differenzenquotienten in 2D

Datei:DFW7ogg audio4.2.ogg

Die zweiten Differenzenquotienten $D_{h,x}^{2}u(x_i,y_j),D_{h,y}^{2}u(x_i,y_j)$ approximieren die zweiten partiellen Ableitungen jeweils in den Richtungen x und y:

$\frac{{\partial }^{2}u(x_i,y_j)}{\partial x^2}\approx D_{h,x}^{2}u(x_i,y_j):=\frac{u(x_{i+1},y_j)-2u(x_i,y_j)+u(x_{i-1},y_j)}{h^2}=\frac{u_{i+1,j}-2u_{i,j}+u_{i-1,j}}{h^2}$,
$\frac{{\partial }^{2}u(x_i,y_j)}{\partial y^2}\approx D_{h,y}^{2}u(x_i,y_j):=\frac{u(x_i,y_{j+1})-2u(x_i,y_j)+u(x_i,y_{j-1})}{h^2}=\frac{u_{i,j+1}-2u_{i,j}+u_{i,j-1}}{h^2}$
in jedem Gitterpunkt $(x_i,y_j)$.

Approximationsschema

Wir erhalten schließlich das Approximationsschema:
$$\mathrm{\Delta }u(x_i,y_j)\approx \frac{u_{i+1,j}+u_{i,j+1}-4u_{i,j}+u_{i-1,j}+u_{i,j-1}}{h^2},i=1,\dots n,j=1,\dots m.$$

Randwerte

In den Randgitterpunkten $(x_0,\cdot ),(x_{n+1},\cdot ),(\cdot ,y_0),(\cdot ,y_{m+1})$ werden die Werte von $u$ nach der Dirichlet-Randbedingung folgend ersetzt:

$u(x_0,y_j)=u(x_{n+1},y_j)=0,j=1,\dots m$,

$u(x_i,y_0)=u(x_i,y_{m+1})=0,i=1,\dots n$.

Assemblierung

Datei:DFW7ogg audio4.3.ogg

Die unbekannten Approximationen der Lösung in den Gitterpunkten$(x_i,y_j),u_{i,j}\approx u(x_i,y_j),i=1,\dots n,j=1,\dots m,$ werden in einen langen Vektor eingeordnet, dabei werden diese Werte in einer bestimmter Reihenfolge in den Vektor aufgestellt.

Beispiel:
Zuerst sammelt man die Unbekannten in der ersten Zeile des Gitters ($y_1$ist fest) in den Gitterpunkten von links nach rechts, $x_1\to x_n$, dann in der zweite Zeile u.s.w.

Die Approximationswerte $u_{i,j}$ sind in dem unbekannten Vektor ${\overrightarrow{u}}_h$ dann wie folgt geordnet,

$${\overrightarrow{u}}_h=(u_{1,1},u_{2,1},\dots u_{n,1}|\dots |u_{1,m},\dots u_{n,m}{)}^T.$$

In der selben Reihenfolge wird auch der Vektor der rechten Seite aufgestellt,$${\overrightarrow{f}}_h=(f_{1,1},f_{2,1},\dots f_{n,1}|\dots |f_{1,m},\dots f_{n,m}{)}^T,f_{i,j}:=f(x_i,y_j).$$

Lineares Gleichungssystem

Nach der oben beschriebener numerischen Diskretisierung und Assemblierung des unbekannten Vektors ergibt sich ein lineares Gleichungssystem $A_h{\overrightarrow{u}}_h={\overrightarrow{f}}_h$ mit Blocktridiagonaler Matrix $A_h\in {ℝ}^{n.m\times n.m}$

$A_h=\frac{-1}{h^2}\left(\begin{array}{ccccc}B& I& & \dots & 0\\ I& B& I& & ⋮\\ ⋮& \ddots & \ddots & \ddots & \\ 0& & \dots & I& B\end{array}\right)$ mit Diagonalblock $B=\left(\begin{array}{ccccc}-4& 1& 0& \dots & 0\\ 1& -4& 1& \dots & 0\\ ⋮& \ddots & \ddots & \ddots & 1\\ 0& \dots & 0& 1& -4\end{array}\right),B\in {ℝ}^{n\times n}$
und der Einheitsmatrix $I=E_n\in {ℝ}^{n\times n}$ auf der Nebendiagonale.

Inhomogene Randbedingungen

Datei:DFW7ogg audio4.4.ogg

Sind die Randwerte der gesuchten Funktion unterschiedlich von Null, $u{|}_{\partial D}=g\ne 0$, tragen die bekannte Randwerte der gesuchten Funktion zum Vektor der rechten Seite ${\overrightarrow{f}}_h$ bei.

Aufgabe: Seien Funktionen $C(y),D(y),A(x),B(x)$ gegeben und die Randwerte der gesuchten Funktion am $\partial D,D=[a,b]\times [c,d]$ wie folgt festgelegt:

• Linker/rechter Rand

$u(x_0,y)=u(a,y)=C(y),$
$u(x_{n+1},y)=u(b,y)=D(y),$

• unterer/oberer Rand

$u(x,y_0)=u(x,c)=A(x),$
$u(x,y_{m+1})=u(x,d)=B(x).$
Wie verändert sich der Vektor der rechten Seite ${\overrightarrow{f}}_h$ für diese Randbedingungen ?

Neumann-Problem in 2 Raumdimensionen

Datei:DFW7ogg audio5.ogg

Im Neumann-Problem mit äquidistanten Punktegitter wird die Anwendung der zweidimensionaler Differenzenquotienten in dasselbe Stern-Approximationsschema resultieren wie bei Dirichlet-Problem, lediglich wird die Behandlung den Randbedingungen zu veränderter Struktur einiger Blöcke der tridiagonaler Matrix nach der Aufstellung des linearen Gleichungssystem führen.

Neumann-Randbedingungen auf dem Rechteck

Seien die Ableitungen der unbekannten Funktion in den Randpunkten des Rechtecks gegeben:

• linker Rand: $\frac{\partial u}{\partial \overrightarrow{n}}(x_0,y_j)=\alpha ,\overrightarrow{n}=(-1,0{)}^T,$
• rechter Rand: $\frac{\partial u}{\partial \overrightarrow{n}}(x_{n+1},y_j)=\beta ,\overrightarrow{n}=(1,0{)}^T,j=1,\dots m,$
• unterer Rand: $\frac{\partial u}{\partial \overrightarrow{n}}(x_i,y_0)=\gamma ,\overrightarrow{n}=(0,-1{)}^T,$
• oberer Rand: $\frac{\partial u}{\partial \overrightarrow{n}}(x_i,y_{m+1})=\delta ,\overrightarrow{n}=(0,1{)}^T,i=1,\dots n,$

wobei $\frac{\partial u}{\partial \overrightarrow{n}}\equiv \mathrm{\nabla }u\cdot \overrightarrow{n}=\frac{\partial u}{\partial x}{n}_1+\frac{\partial u}{\partial y}{n}_2.$

Speziell $\frac{\partial u}{\partial \overrightarrow{n}}=\pm \frac{\partial u}{\partial x}$ oder $\pm \frac{\partial u}{\partial y}$ am Rand eines Rechtecks.

Approximation erster Ordnung

Datei:DFW7ogg audio5.2.ogg

Bei der Anwendung der einseitigen Differenzenquotienten, analog wie 1-dimensionalem Fall muss der Vektor den Unbekannten ${\overrightarrow{u}}_h$ um die Randwerte $u_{0,j},u_{n+1,j},u_{i,0},u_{i,m+1}$ erweitert werden, diese werden zur Bildung der Differenzenquotienten verwendet:

• linker Rand: den vorwärts -Differenzenquotient $D_{h,x}^{+}u(x_0,y_j)=\frac{u_{1,j}-u_{0,j}}{h}\approx \frac{\partial u}{\partial x}(x_0,y_j))\equiv -\alpha$
• rechter Rand: den rückwärts -Differenzenquotient $D_{h,x}^{-}u(x_{n+1},y_j)=\frac{u_{n+1,j}-u_{n,j}}{h}\approx \frac{\partial u}{\partial x}(x_{n+1},y_j)\equiv \beta ,j=1,\dots m$
• unterer Rand: den vorwärts -Differenzenquotient $D_{h,y}^{+}u(x_i,y_0)=\frac{u_{i,1}-u_{i,0}}{h}\approx \frac{\partial u}{\partial y}(x_i,y_0))\equiv -\gamma$
• oberer Rand: den rückwärts -Differenzenquotient $D_{h,y}^{-}u(x_i,y_{m+1})=\frac{u_{i,m+1}-u_{i,m}}{h}\approx \frac{\partial u}{\partial y}(x_i,y_{m+1}))\equiv \delta ,i=1,\dots n.$
  

(Hier wurde direkt die obige Neumann-Randbedingung für ein Rechteckgebiet $D=[a,b]\times [c,d]$ eingesetzt.)

Lineares Gleichungssystem

Nach der Einordnung der unbekannter Werte in den Lösungsvektor wie obenbeschrieben (siehe Assemblierung ) ergibt sich wie zuvor eine erweiterte Blocktridiagonale Systemmatrix ${\tilde{A}}_h\in {ℝ}^{(n+2)(m+2)\times (n+2)(m+2)}$:

• erweitert um die 0-te und m+1-te Blockzeile für die Approximation der Ableitung nach y in den Gitterpunkten am oberem und unterem Rand,
• die Blöcke der Matrix: $B,I,0$ sind um die 0-te und n+1-te Zeile für die Approximation der Ableitung nach x in den Gitterpunkten am linkem und rechtem Rand erweitert, der Block $B$ ist mit der Approximationsmatrix ${\tilde{A}}_h$ des Neumann-Problem in einer Raumdimension identisch.

Aufgabe: Stellen Sie die Systemmatrix ${\tilde{A}}_h$ und die rechte Seite des linearen System des Approximationschemas für den oben definerten Neumann-Randwertproblem auf dem Rechteck D auf.

SW 8: Konvergenz und Stabilität

Wir untersuchen, unter welcher Vorausstetzungen und mit welcher Approximationsgüte
die numerische Lösung für das Randwertproblem für Poissongleichung, $u_i$ (in 1D), ggf. $u_{i,j}$ (auf dem Recheteck in 2D), repräsentiert durch den Vektor ${\overrightarrow{u}}_h$

zu der exakten Lösung in den Gitterpunkten $u(x_i)$, ggf. $u(x_i,y_j)$ konvergiert.

Im folgenden bezeichnen wir mit $\overrightarrow{u}$ den Vektor der Restriktion der Funktion der exakten Lösung an die Gitterpunkte $x_{i}i=1,\dots N$, ggf $(x_i,y_j)i=1,\dots N,j=1,\dots M$ (nach der Assemblierung).

Konvergenz der numerischen Lösung

Datei:DFW8ogg audio1.ogg

Wir untersuchen den Unterschied der exakten und der numerischen Lösung in einer geeigneter Vektornorm auf ${ℝ}^N$, wobei im Folgenden N die Gesamtanzahl der Gitterpunkte bezeichnet (in vereinfachter Indexierung der Gitterpunkte).

$\Vert \overrightarrow{u}-{\overrightarrow{u}}_h\Vert ,\overrightarrow{u}=(u(x_1),\dots u(x_N){)}^T,{\overrightarrow{u}}_h=(u_1,\dots u_N{)}^T,u_i\approx u(x_i).$

Im folgenden werden wir zeigen, dass die Konvergenz $\Vert \overrightarrow{u}-{\overrightarrow{u}}_h\Vert \to 0$ für Gittergröße $h\to 0$ von

• den Eigenschaften der Systemmatrix $A_h$
• der Approximationsgüte des Approximationschema (der Differenzenquotienten)

abhängig ist.

Voraussetzungen der Konvergenz

Datei:DFW8ogg audio2.ogg

Sei Matrix $A_h$ invertierbar und ${\overrightarrow{u}}_h$ die Lösung des linearen Systems $A_h{\overrightarrow{u}}_h={\overrightarrow{f}}_h=:\overrightarrow{f}=(f(x_1),\dots ,(x_N){)}^T$.

Unter Anwendung der Verträglichkeit der Matrixnorm folgt

$\Vert \overrightarrow{u}-{\overrightarrow{u}}_h\Vert =\Vert A_h^{-1}{A}_h\overrightarrow{u}-A_h^{-1}\overrightarrow{f}\Vert =\Vert A_h^{-1}(A_h\overrightarrow{u}-\overrightarrow{f})\Vert \le \Vert |A_h^{-1}\Vert |.\Vert A_h\overrightarrow{u}-\overrightarrow{f}\Vert ,$

wobei $\Vert |\cdot \Vert |$ die Vektornorm-induzierte (natürliche) Matrixnorm bezeichnet.

Folglich ist die Konvergenz $\Vert \overrightarrow{u}-{\overrightarrow{u}}_h\Vert \to 0$ gegeben falls

1. die Norm von $A_h^{-1}$ gleichmäßig (bez. $h$) beschränkt ist: $\Vert |A_h^{-1}\Vert |\le r,r\in ℝ$ - (Stabilität)
2. $\Vert A_h\overrightarrow{u}-\overrightarrow{f}\Vert \to 0$, für $h\to 0$, d.h., das Approximationsschema $A_h{\overrightarrow{u}}_h=\overrightarrow{f}$ ist mit dem Originalproblem, $-\mathrm{\Delta }\overrightarrow{u}=\overrightarrow{f}$ veträglich (Konsistenz).

Der zweite Punkt beschreibt, dass Restriktion der exakten Lösung auf die Gitterpunkte das Approximationschema annäherungsweise erfüllt.

Definition der Konsistenz

Datei:DFW8ogg audio3.ogg

Wir setzen voraus, dass die Funktion der rechten Seite $f$ stetig ist.

Definition: (Konsistenzordnung)
Das Finite Differenzenverfahren für die Poisson Randwertaufgabe hat bezüglich einer Vektornorm in ${ℝ}^N$ die Konsistenzordnung $p$ wenn für jede hinreichend oft stetig differenzierbare Lösung $\overrightarrow{u}$ des Originalproblems ein $C\in {ℝ}_{+}$ existiert

$\Vert A_h\overrightarrow{u}-\overrightarrow{f}\Vert =\Vert A_h\overrightarrow{u}+\mathrm{\Delta }\overrightarrow{u}\Vert \le C.h^p$

Konsistenz elliptischer Randwertprobleme

Datei:DFW8ogg audio3.2.ogg

Den Begriff der Konsistenz, Stabilität und schließlich der Beweis der Konvergenz für das FDM- Verfahren kann man auf elliptische Randwertprobleme mit elliptischen Differenzialoperator $L:u\to L(u)$ für die Funktion $u$ ausbreiten.

Elliptisches Randwertproblem

Vorausgesetzt $f,c:D\to ℝ,b:D\to {ℝ}^n,$ stetige Funktionen auf ${ℝ}^n$ sind gegeben und $c\ge 0$.

$L(u):=-\mathrm{\Delta }u(x)+b(x)\cdot \mathrm{\nabla }u(x)+c(x)u(x)=f(x),x\in D\subset {ℝ}^n,$

$u(x)=0,x\in \partial D$

Approximationschema des elliptischen Operators

Das entsprechende Approximationsschema $L_h(u)$ zum Differenzialoperator $L(u)$ enthält im Fall vom Rechteckgebiet $D\in {ℝ}^2$ das Stern-Approximationsschema für das Laplace Operator anhand der zweiten Differenzenquotienten $D_h^2$ (Matrix $A_h$) und ein weiteres Beitrag durch die Approximation des Gradienten $\mathrm{\nabla }u=({\partial }_{x_1}u,\dots ,{\partial }_{x_n}u{)}^T$ mit einseitigen, oder zentralen Differenzenquotienten $D_h^{\pm },D_h$, siehe erste Differenzenquotient.
Die Konsistenzdefinition für den elliptischen Operator lautet:

$\Vert L_h\overrightarrow{u}-\overrightarrow{f}\Vert =\Vert L_h\overrightarrow{u}-L(\overrightarrow{u})\Vert \le C.h^p.$

Satz: Konsistenz des FDM Verfahren

Datei:DFW8ogg audio3.3.ogg

Sei $u\in C^4(D)$ die exakte Lösung des obigen elliptischen Randwertproblems $L(u)=f$ mit homogenen Randbedingungen. 

Dann hat das Finite-Differenzen-Verfahren mit dem Approximationsschema $L_h$
i) die Konsistenzordnung $p=1$ unter der Anwendung von einseitigen Differenzenquotienten $D_h^{\pm }$
ii) die Konsistenzordnung $p=2$ unter der Anwendung von zentralen Differenzenquotienten $D_h$
für den Term $\mathrm{\nabla }u$. $\diamond$

Beweis: basiert auf der Approximationsgüte der ersten und der zweiten Differenzenquotienten (Lemma 1 und 2). Für das Approximationsschema $A_h$ ergibt sich daraus $A_h\overrightarrow{u}=-\mathrm{\Delta }\overrightarrow{u}+𝒪(h^2)$, für das Approximationsschema $L_h$ dagegen entweder $L_h\overrightarrow{u}=L(\overrightarrow{u})+𝒪(h^2)+𝒪(h)=L(\overrightarrow{u})+𝒪(h)$ oder $L_h\overrightarrow{u}=L(\overrightarrow{u})+𝒪(h^2)$ $◻$.

Folgerungen

Datei:DFW8ogg audio3.4.ogg

1. Im Fall $b=c=0,D\in {ℝ}^2-$ Rechteckgebiet, erhalten wir die Randwertaufgabe für Poissongleichung mit homogenen Dirichletrandbedingungen. In diesem Fall ist das Approximationsschema $L_h=A_h$ von der Konsistenzordnung $p=2$.
   
2. Im Fall dass $D\in ℝ$ ein geschlossenes Intervall ist, erhalten wir aus Lemma 2 in der Maximum-Vektornorm $\Vert \cdot {\Vert }_{\mathrm{\infty }}$ für $\overrightarrow{u},\overrightarrow{f}\in {ℝ}^N$ konkret

$\Vert A_h\overrightarrow{u}-\overrightarrow{f}{\Vert }_{\mathrm{\infty }}=\Vert A_h\overrightarrow{u}+{\overrightarrow{u}}^{″}{\Vert }_{\mathrm{\infty }}=\underset{i}{\max }|-D_h^{2}u(x_i)+u^{″}(x_i)|\le \frac{h^2}{12}\underset{x\in D}{\max }|u^{(IV)}(x)|=\frac{h^2}{12}\underset{x\in D}{\max }|f^{″}(x)|.$

Damit ist die Konstante $C$ aus der Definition der Konsistenz im eindimensionalen Fall $C=\frac{1}{12}\underset{x\in D}{\max }|f^{″}(x)|.$

Definition der Stabilität

Datei:DFW8ogg audio4.ogg

Definition: (Stabilität)
Das Finite-Differenzen-Verfahren für das elliptische Randwertproblem $L(u(x))=f(x),x\in D\subset {ℝ}^n,$ $u(x)=0,x\in \partial D$ heißt stabil (bezüglich einer Vektornorm $\Vert \cdot \Vert$),
wenn $C,h_0$ existieren, $C,h_0\in {ℝ}_{+}$, sodass die Matrix (Approximationsschema) $L_h$ invertierbar ist und es gilt $\Vert |L_h^{-1}\Vert |\le C$ für $0<h<h_0$.

Die Untersuchung der Stabilität anhand der Konstruktion der inversen Matrix $L_h^{-1}$ ist aufwändig. Deswegen wird die Stabilität anhand anderer Kriterien untersucht, der Monotonie Eigenschaften der Matrix $L_h$.

Bemerkung:

Die Stabilitätsbedingung garantiert auch die Beschränkheit der numerischen Lösung als Lösung des linearen Systems $L_h{\overrightarrow{u}}_h=\overrightarrow{f}$, denn $\Vert {\overrightarrow{u}}_h\Vert =\Vert L_h^{-1}\overrightarrow{f}\Vert \le \Vert |L_h^{-1}\Vert |.\Vert \overrightarrow{f}\Vert$ in einer Vektornorm. Hier $\Vert |L_h^{-1}\Vert |$ ist eine natürliche Matrixnorm.

Monotonie Eigenschaften

Datei:DFW8ogg audio5.ogg

Definiton (M-Matrix)

Eine reguläre Matrix $A\in {ℝ}^{N\times N}$ mit $a_{ij}\le 0$ für $i\ne j$

und $(A^{-1}{)}_{ij}\ge 0$, kurz $A^{-1}\ge 0$, heißt M-Matrix, oder Monotonie-Matrix.

Folgerung: Monotonie Eigenschaft

Für eine M-Matrix $A\in {ℝ}^{N\times N}$ und Vektoren $\overrightarrow{x},\overrightarrow{y}\in {ℝ}^N$gilt:

$\overrightarrow{x}\le \overrightarrow{y}⟹A^{-1}\overrightarrow{x}\le A^{-1}\overrightarrow{y}$

Beweis: Ist $x_j\le y_j\mathrm{\forall }j=1,\dots N⟹\sum _{j=1}^N(A^{-1}{)}_{ij}{x}_j\le \sum _{j=1}^N(A^{-1}{)}_{ij}{y}_j,$ da die Elemente $(A^{-1}{)}_{ij}\ge 0◻.$

SW9 Kriterien für M-Matrix

Datei:DFW8ogg audio5.2.ogg

In diesem Abschnitt werden die Kriterien für Tridiagonalmatrizen wie die Systemmatrix $A_h$ des Laplace-Approximationsschemas in 1D und die Matrix $L_h$ des elliptischen Randwertproblems in einer Raumdimension $x\in ℝ$ untersucht.

Satz: Monotonie tridiagonaler Matrizen

Jede irreduzibel diagonaldominante  Tridiagonalmatrix mit positiven Diagonalelementen und negativen Nebendiagonalelementen ist eine M-Matrix. $\diamond$

Beweis: siehe $◻$

Bemerkung:
Tridiagonale Matrizen sind irreduzibel falls alle Sub- und Superdiagonalelemente ungleich Null sind.

Folgerung 1

Die Matrix   $A_h$ des Laplace-Approximationsschemas in 1D für das Dirichlet Randwertproblem is eine M-Matrix.

Beweis:
$A_h$ ist tridiagonal, hat alle Sub- und Superdiagonalelementen ungleich Null und für erste und letzte Zeile gilt $|a_{i,i}|>|a_{i,i\pm 1}|$. Damit ist $A_h$ eine M-Matrix $◻$.

Folgerung 2

Datei:DFW8ogg audio5.3.ogg

Die Matrix   $L_h$ des elliptischen Randwertproblems in 1D unter der Verwendung des  ersten zentralen Differenzenquotienten $D_h$   für $u^{\prime }(x_i),i=1,\dots N$ ist  für 
$0<h<h_0\equiv \frac{2}{\underset{x\in D}{\max }|b(x)|}$   eine M-Matrix.

Beweis:

$L_h=\frac{1}{h^2}\left(\begin{array}{ccccc}{d}_1& s_1& 0& \dots & 0\\ r_2& d_2& s_2& & ⋮\\ ⋮& \ddots & \ddots & \ddots & \\ 0& & \dots & r_N& d_N\end{array}\right)$ ist tridiagonal, mit

$\begin{array}{c}{d}_i=2+h^{2}c(x_i),\\ r_i=-1-\frac{h}{2}b(x_i),\\ s_i=-1+\frac{h}{2}b(x_i).\end{array}$
Nach der Voraussetzung ist $|\frac{h}{2}b(x_i)|<1,i=1,\dots N$ und somit sind $r_i,s_i\ne 0$ und negativ.
$⟹L_h$ ist irreduzibel.
$L_h$ ist auch schwach-diagonaldominant:
$\frac{1}{h^2}(|r_i|+|s_i|)=\frac{2}{h^2}\le \frac{d_i}{h^2}$ für $c(x)\ge 0,i=2,\dots N-1,$ wobei für $i=1,N$ die strikte Ungleichung gilt $◻$.

Monotonie der Systemmatrix und die Stabilität

Datei:DFW8ogg audio6.ogg

Hier befassen wir ist mit der Frage wie aus der Monotonie Eigenschaft die Stabilität des Approximationsschemas folgt.

Die Beschränkheit der Matrix $L_h^{-1}$ untersuchen wir in der Maximumnorm $\Vert |\cdot \Vert {|}_{\mathrm{\infty }}$ (Zeilensummennorm), die von der Maximum-Vektornom $\Vert \cdot {\Vert }_{\mathrm{\infty }}$ induziert ist, siehe .

Hilfsproblem

Wir untersuchen folgendes Randwertproblem: gegeben sei $b\in C^2[0,1]$:

$-w^{″}(x)+b(x)w^{\prime }(x)=1,$

$w(0)=w(1)=0.$

Sei die Lösungsfunktion $w\in C^4[0,1]$.

Lemma 3:

Die Lösung $w$ des obigen Randwertproblem ist $w\ge 0\mathrm{\forall }x\in [0,1]$.

Beweis:
Angenommen $w\ne 0$ (Fall $w=0$ können wir ausschließen).

Wäre $w<0$ mindesten in einem Punkt, hätte $w$ ein lokales Minimum in einem $x_0\in (0,1)$. d.h.,
$w^{\prime }(x_0)=0$ und $w^{″}(x_0)\ge 0$.

Damit erhalten wir aus der obigen Differenzialgleichung $-w^{″}(x_0)+b(x_0)w^{\prime }(x_0)=-w^{″}(x_0)=1⟹w^{″}(x_0)\le 0$, was im Widerspruch zu der Bedingung des lokalen Minima steht. $◻$

Beschränkheit der Matrix $L_h^{-1}$

Datei:DFW8ogg audio6.2.ogg

Sei zusätzlich eine stetige nichtnegative Funktion $c\in C[0,1],c\ge 0$ gegeben.

Für den elliptischen Operator mit Funktion $b$ aus obigen Hilfsproblem gilt nach Lemma 3:

$L(w)=-w^{″}+b{w}^{\prime }+cw\ge 1,$

Aus dem Satz über die Konsistenz des Approximationsschema für elliptische Operatoren erhalten wir für das Approximationsschema $L_h$ zum Operator $L$ (unter Verwendung der zentralen Differenzenquotioenten) und für den Vektor $\overrightarrow{w}$ der Restriktion der Lösung $w$ auf die Gitterpunkte,

$\Vert L_h\overrightarrow{w}-L(\overrightarrow{w}){\Vert }_{\mathrm{\infty }}\le C.h^2.$

Aus dieser Abschätzung in Maximumnorm folgt, dass auch gilt $|(L_h\overrightarrow{w}-L(\overrightarrow{w}){)}_i|\le C{h}^2$ , wobei $i=1\dots ,N$ und schließlich

$L(\overrightarrow{w})+C{h}^2\mathrm{𝟏}\ge L_h\overrightarrow{w}\ge L(\overrightarrow{w})-C{h}^2\mathrm{𝟏},\mathrm{𝟏}=(1,\dots ,1{)}^T.$

Datei:DFW8ogg audio6.3.ogg

Da $L(w)\ge \mathrm{𝟏},$ s. oben, erhalten wir aus der rechen Ungleichung $L_h\overrightarrow{w}\ge \mathrm{𝟏}-C{h}^2\mathrm{𝟏}.$

Folglich gilt für ausreichend kleine $h<h_0$, $h_0$ aus Folgerung 2

$\frac{1}{2}\mathrm{𝟏}\le L_h\overrightarrow{w}.$

Da $L_h$ gleichzeitig eine M-Matrix ist, erhalten wir aus der Eigenschaft der Monotonie der Matrix $L_h$

$\frac{1}{2}{L}_h^{-1}\mathrm{𝟏}\le \overrightarrow{w}.$

Weil $L_h^{-1}$ nur nichtnegative Elemente enthält ist $\Vert |L_h^{-1}\Vert {|}_{\mathrm{\infty }}=\Vert L_h^{-1}\mathrm{𝟏}{\Vert }_{\mathrm{\infty }}$ und somit nach obiger Ungleichung $\Vert |L_h^{-1}\Vert {|}_{\mathrm{\infty }}\le 2\Vert \overrightarrow{w}{\Vert }_{\mathrm{\infty }}\le 2\underset{x\in [0,1]}{\max }|w|.$

Nach der Voraussetzung (für die zweite Konsistenzordnung) ist $w$ viermal stetig differenzierbar, also auch stetig und damit ist $\underset{x\in [0,1]}{\max }|w|$ beschränkt, folglich

$\Vert |L_h^{-1}\Vert {|}_{\mathrm{\infty }}\le K\in {ℝ}_{+}.$

Wir haben bewiesen:

Satz (Stabilität des Approximationschema $L_h$)

Sei $b\in C^2[0,1],c\in C[0,1],c\ge 0$.
Unter der Verwendung des zentralen Differenzenquotienten $D_{h}u(x)\approx u^{\prime }(x)$ ist das Finite-Differenzen-Verfahren $L_h{\overrightarrow{u}}_h=\overrightarrow{f}$  unter der Anwendung der Systemmatrix $L_h$ für elliptische Randwertprobleme stabil. $\diamond$

Hauptsatz: Zweite Konvergenzordnung des FDM-Verfahrens

Datei:DFW8ogg audio7.ogg

Sei $u\in C^4[0,1]$ die exakte Lösung des  elliptischen Randwertproblems,  $\overrightarrow{u}$ die Restriktion auf die Gitterpunkte und sei ${\overrightarrow{u}}_h$ die numerische Lösung, d.h. die Lösung von $L_h{\overrightarrow{u}}_h=\overrightarrow{f}:={\overrightarrow{f}}_h$, wobei $L_h$   das Approximationschema mit zentralen Differenzenquotienten $D_{h}u(x)\approx u^{\prime }(x)$ ist.
 

Dann gilt für eine hinreichend kleine Schrittweite $h$ die zweite Konvergenzordnung: $\Vert \overrightarrow{u}-{\overrightarrow{u}}_h{\Vert }_{\mathrm{\infty }}\le C{h}^2$ mit einer Konstante $C>0$. $\diamond$

Dieses Ergebniss lässt sich verallgemeinern auf Intervall [a,b]. Um die Konvergenz des FDM-Verfahrens auf einem Rechteck-Gebiet in 2D nachzuweisen, muss man lediglich die Monotonie-Eigenschaften der Blocktridiagonaler Systemmatrix untersuchen.

SW10: Numerische Diskretisierung der Reaktionsdiffusionsgleichung mit FDM

Im folgenden wir die numerische Diskretisierung des Reaktionsdiffusionsprozesses in der Populationsdynamik beschrieben.

$${\partial }_{t}u(x,t)-div(c(x)\mathrm{\nabla }u(x,t))=f(u(x,t)).$$

Hier beschreibt die unbekannte Funktion $u$ die Populationsdichte der (aktuell oder kummulierten) Infizierten Individuen, wobei der Reaktionsterm $f=f(u)$ die zeitliche Dynamik der aktuell oder der kummulierten Infizierten steuert. Der Reaktionsterm stellt den Zusammenhang der räumlichen Infektionsverbreitung als Diffusionsprozess und der dynamischen Kompartimentmodellen dar.

Alternativ kann $f=f(u)$ auch den unbeschränkten Epideme-Ausbruch modellieren, siehe unbeschränktes Wachstum.

Räumliche Semidiskretisierung für die Diffusiongleichung

Zuerst wird Neumann Randwertproblem für die zeitabhängige homogene Diffusionsgleichung auf einem Rechteckgebiet D betrachtet.

${\partial }_{t}u(x,t)-div(c(x)\mathrm{\nabla }u(x,t))=0,x\in D\subset {ℝ}^2,t\in (t_0,T),$

$\frac{\partial u(x)}{\partial \overrightarrow{n}}\equiv \mathrm{\nabla }u\cdot \overrightarrow{n}=g(x)x\in \partial D.$

Im folgenden nehmen wir an, dass der Diffusionskoeffizient ist konstant, $c(x)=c$. Somit erhalten wir die homogene Diffusionsgleichung in der Form ${\partial }_{t}u(x,t)-c\mathrm{\Delta }u(x,t)=0$.

System von gewöhnlichen Differentialgleichungen

Mithilfe der räumlichen Semidiskretisierung des Laplace Operators mit Finite-Differenzenverfahren unter Beachtung der homogenen Neumann Randbedingungen $\alpha =\beta =\gamma =\delta =0$ und Approximation der Richtungsableitungen erster Ordnung erhält man für ein festes $t\in (t_0,T)$ nach dem Stern-Approximationsschema

$-c\mathrm{\Delta }\overrightarrow{u}(t)\approx A_h{\overrightarrow{u}}_h$,

hierbei ist $\overrightarrow{u}(t)=(u(x_0,y_0,t),\dots ,u(x_{n+1},y_{m+1},t){)}^T$ der Vektor der Restriktionen der exakten Lösung an die Gitterpunkte $(x_i,y_j),i=0,\dots ,n+1,j=0,\dots ,m+1$ in Zeitpunkt $t$ und ${\overrightarrow{u}}_h(t)=(u_{0,0}(t),\dots ,u_{n+1,m+1}(t){)}^T$ der Vektor der numerischen Lösung in den Gitterpunkten in Zeitpunkt $t$.

Die Matrix des Approximationsschema für Neumann Randbedingungen hat die Form:

$A_h=\frac{-c}{h^2}\left(\begin{array}{ccccc}-hI& hI& & \dots & 0\\ \tilde{I}& B& \tilde{I}& & ⋮\\ ⋮& \ddots & \ddots & \ddots & \\ 0& & \dots & hI& -hI\end{array}\right),$

wobei $B=\left(\begin{array}{ccccc}-h& h& 0& \dots & 0\\ 1& -4& 1& \dots & 0\\ ⋮& \ddots & \ddots & \ddots & \\ 0& \dots & 1& -4& 1& \\ 0& \dots & 0& h& -h\end{array}\right),\tilde{I}=\left(\begin{array}{ccccc}0& & \dots & & 0\\ 0& 1& 0& \dots & 0\\ ⋮& \ddots & \ddots & \ddots & ⋮\\ 0& \dots & 0& 1& 0\\ 0& & \dots & & 0\end{array}\right)\tilde{I},B\in {ℝ}^{(n+2)\times (n+2)},$
und der Einheitsmatrix $I=E_n\in {ℝ}^{(n+2)\times (n+2)}$.

Schließlich ergibt sich nach der räumlichen Semidiskretisierung folgendes System der gewöhnlichen Differentialgleichungen:

$\frac{d}{dt}{\overrightarrow{u}}_h(t)=-A_h{\overrightarrow{u}}_h(t)$,

Der Vektor der numerischen Lösung ${\overrightarrow{u}}_h$ wird hier als Funktion von Zeit betrachtet.

Räumliche Semidiskretisierung für die Reaktionsdiffusiongleichung

Diskretisierung des Reaktionsterms, Gesamtinfizierte

Der Reaktionsterm $f(u(x,y,t))$ an den Gitterpunkten wird Mithilfe der Restriktionen der exakten Lösung $\overrightarrow{u}(t)$formuliert, für die kumulierte Infizierte (Logistisches Wachstum):

$f(\overrightarrow{u}(t))\approx F({\overrightarrow{u}}_h(t)):=\frac{c}{\overrightarrow{B}}*{\overrightarrow{u}}_h(t)*(\overrightarrow{B}-{\overrightarrow{u}}_h(t))\equiv c\left(\begin{array}{c}\frac{u_{0,0}}{B_{0,0}}(B_{0,0}-u_{0,0})\\ ⋮\\ \frac{u_{n+1,m+1}}{B_{n+1,m+1}}(B_{n+1,m+1}-u_{n+1,m+1})\end{array}\right)(t),$

wobei Vektor $\overrightarrow{B}=(B_{0,0},\dots ,B_{n+1,m+1}{)}^T$ der nach der Assemblierung aus der Matrix der Bevölkerungsdichte $(B{)}_{i,j}=B(x_i,y_j)$ entstanden ist und $*$ ist komponentenweise Multiplikation.

Bemerkung: die logistische Infektionsrate $k:=\frac{c}{\overrightarrow{B}}$, vergleiche Modifiziertes SIR Modell berechnet sich als Rate der Infektionsverbreitung bei einer Kontaktrate: Wahrscheinlichkeit des Kontakts eines Infizierten mit einem Anfälligen.

Diskretisierung des Reaktionsterms, aktuell Infizierte

Im Falle der räumlichen Modellierung der Dichte der aktuellen Infizierten $u_I$ in Wechselwirkung mit Susceptibles $u_S$ nach dem Prinzip des SIR-Kompartimentmodells werden drei einander gekopelte Reaktionsdiffusionsgleichungen für die Dichtefunktionen $u_I,u_S,u_R$ gelöst.

$${\partial }_t{u}_S(x,t)-div(c(x)\mathrm{\nabla }{u}_S(x,t))=f_S(u_S(x,t),u_I(x,t)).$$ $${\partial }_t{u}_I(x,t)-div(c(x)\mathrm{\nabla }{u}_I(x,t))=f_I(u_S(x,t),u_I(x,t)).$$ $${\partial }_t{u}_R(x,t)-div(c(x)\mathrm{\nabla }{u}_R(x,t))=f_R(u_I(x,t)).$$

Diese partielle Differentialgleichungen werden durch die reche Seiten $f_S,f_I,f_S$ gekoppelt. Die entsprechende Reaktionsterme $f_S(u_S,u_I),f_I(u_S,u_I)$ und $f_R(u_I)$ werden an den Gitterpunkten ausgewertet:

$f_S(\overrightarrow{u}(t))\approx F_S({\overrightarrow{u}}_h(t)):=-\frac{c}{\overrightarrow{B}}*{\overrightarrow{u_I}}_h(t)*{\overrightarrow{u_S}}_h(t)$

$f_I(\overrightarrow{u}(t))\approx F_I({\overrightarrow{u}}_h(t)):=\frac{c}{\overrightarrow{B}}*{\overrightarrow{u_I}}_h(t)*{\overrightarrow{u_S}}_h(t)-w{\overrightarrow{u_I}}_h(t),$

$f_R(\overrightarrow{u}(t))\approx F_R({\overrightarrow{u}}_h(t)):=w{\overrightarrow{u_I}}_h(t),$

wobei $w$ die Wechselrate zwischen den Infizierten und Genesenen ist.

Da die erste und zweite partielle Differentialgleichung für $u_I,u_S$ nicht von $u_R$ abhängig ist, kann man diese zwei Gleichungen separat lösen und $u_R$ dann im Nachgang berechnen.)

System von gewöhnlichen Differentialgleichungen

Nach der Zunahme des diskretisierten Reaktionstern $F({\overrightarrow{u}}_h(t))$ zum System von gewöhnlichen Differentialgleichungen des räumlich diskretisierten Neumann Randwertproblems für die Diffusion ergibt sich folgendes System der gewöhnlichen Differentialgleichungen (GDGL) für die Reaktionsdiffusionsgleichung:

$\frac{d}{dt}{\overrightarrow{u}}_h(t)=-A_h{\overrightarrow{u}}_h(t)+F({\overrightarrow{u}}_h(t))$

mit einem linearen Anteil $-A_h{\overrightarrow{u}}_h(t)$ und einem nichtlinearen Anteil $F({\overrightarrow{u}}_h(t))$.

Dieses GDGL System, ergänzt um die Anfangsbedingung gegeben durch eine bekannte Funktion $u^0(x,y)$

$\overrightarrow{u}(t_0)={\overrightarrow{u}}_h(t_0)={\overrightarrow{u}}^0=(u^0(x_0,y_0),\dots ,u^0(x_{n+1},y_{m+1}){)}^T$

definiert ein Anfangswertproblem für Reaktionsdiffusionsgleichung.

Zeitdiskretisierung der Reaktion-Diffusionsgleichung

Unter der Zeitdiskretisierung versteht man ein approximatives Vorgehen zur Bestimmung der Lösung eines Anfangswertproblems in diskreten Zeitpunkten. Der Zeitintervall $(t_0,T)$ wird auf äquidistante Teilintervalle $(t_k,t_{k+1})$ der Länge $\mathrm{\Delta }t=t_{k+1}-t_k,k=0,1,\dots K,T=t_0+K\mathrm{\Delta }t$ geteilt.

Das einfachste numerische Verfahren, das Euler- oder Polygonzugverfahren entsteht durch das Ersetzten der Zeitableitung $\frac{d{\overrightarrow{u}}_h}{dt}$ mit Vorwärts- oder Rückwardsdifferenzenquotienten

$D_{\mathrm{\Delta }t}^{\pm }{\overrightarrow{u}}_h(t)=\frac{{\overrightarrow{u}}_h(t\pm \mathrm{\Delta }t)-{\overrightarrow{u}}_h(t)}{\mathrm{\Delta }t}\approx \frac{d{\overrightarrow{u}}_h(t)}{dt}$.

Dieses Verfahren hat die Konvergenzordnung 1, siehe Approximationsgüte der Differenzenquotienten.

Nach dem Anwenden des ersten Differenzenquotientes im obigen System von GDL ergeben sich folgende Approximationsschemas erster Ordnung:

Zeitdiskretisierung mit explizitem Eulerverfahren

Unter Verwendung von $D_{\mathrm{\Delta }t}^{+}$ erhält man die Berechnungsformel

${\overrightarrow{u}}_h(t_{k+1})={\overrightarrow{u}}_h(t_k)+\mathrm{\Delta }t(-A_h{\overrightarrow{u}}_h(t_k)+F({\overrightarrow{u}}_h(t_k))),k=0,1,\dots K,T=t_0+K\mathrm{\Delta }t.$

mit dem Startvektor $u^0(x,y)$

${\overrightarrow{u}}_h(t_0)={\overrightarrow{u}}^0=(u^0(x_0,y_0),\dots ,u^0(x_{n+1},y_{m+1}){)}^T$

Die numerische Lösung in einem neuen Zeitschritt ${\overrightarrow{u}}_h(t_{k+1})$ erhält man iterativ durch Einsetzen der Lösung aus dem vorherigen Zeitschritt ${\overrightarrow{u}}_h(t_k)$ in die rechte Seite der obigen Formel. Dieses Verfahren hat beschränkten Bereich der zulässigen Schrittweiten $\mathrm{\Delta }t$ im Hinblick auf die Stabilität der numerischen Lösung, die Schrittweite $\mathrm{\Delta }t$ muss aus diesem Grund ausreichend klein gewählt werden, ansonsten kann die numerische Lösung nach wenigen Schritten instabil werden und 'explodieren'.

Zeitdiskretisierung mit implizitem Eulerverfahren

Unter Verwendung von $D_{\mathrm{\Delta }t}^{-}$ erhält man die implizite Berechnungsformel

${\overrightarrow{u}}_h(t_{k+1})={\overrightarrow{u}}_h(t_k)+\mathrm{\Delta }t(-A_h{\overrightarrow{u}}_h(t_{k+1})+F({\overrightarrow{u}}_h(t_{k+1}))),k=0,1,\dots K,T=t_0+K\mathrm{\Delta }t.$

mit dem Startvektor $u^0(x,y)$

${\overrightarrow{u}}_h(t_0)={\overrightarrow{u}}^0=(u^0(x_0,y_0),\dots ,u^0(x_{n+1},y_{m+1}){)}^T$

Die numerische Lösung im neuen Zeitschritt ${\overrightarrow{u}}_h(t_{k+1})$ erhält man nach dem Lösen des obigen Systems von nichlinearen Gleichungen für ${\overrightarrow{u}}_h(t_{k+1})$ und benötigt weitere numerische Approximationsverfahren für nichtlineare Gleichungssysteme. Dieses Verfahren hat gute Stabilitätseigenschaften in Hinblick auf die Schrittweite $\mathrm{\Delta }t$ (es ist A-stabil), die Schrittweite $\mathrm{\Delta }t$ ist stabilitätsbedingt nicht beschränkt.

Weitere Zeitdiskretisierungsverfahren für gewöhnliche Differentialgleichungen

Sei eine gewöhnliche Differentialgleichung oder ein System von DGL gegeben allgemein als

$\dot{𝐲}(t)=f(t,𝐲(t)),𝐲:ℝ\to {ℝ}^d,d=1,2,,\dots .$

Unter Verwendung des zentralen Differenzenquotienten $D_{\mathrm{\Delta }t/2}$ erhält man
die explizite Mittelpunktregel (verbessertes Eulerverfahren) zweiter Ordnug:

${𝐲}_{k+1}={𝐲}_k+\mathrm{\Delta }t(f(t_{k+1/2},{𝐲}_{k+1/2})),{𝐲}_{k+1/2}={𝐲}_k+\frac{\mathrm{\Delta }t}{2}f(t_k,{𝐲}_k)$.

Ein weiteres Verfahren zweiter Ordnung ist die Trapezregel (Newmark scheme):

${𝐲}_{k+1}={𝐲}_k+\frac{\mathrm{\Delta }t}{2}(f(t_k,{𝐲}_k)+f(t_{k+1},{𝐲}_{k+1}))$.

Für weitere Diskretisierungsverfahren für die Anfangswertprobleme ggf. höherer Konvergenzordnungen siehe Runge-Kutta und Mehrschrittverfahren.

Animation

Inhomogene Populationsdichte in unserem Beispiel, angepasst von Monitor Einwohnerzahl 2011

In folgender Animation wurde die Reaktionsdiffusiongleichung für kummulierte Infizierte mit explizitem Eulerverfahren auf einem Gebet von 15 x 18 km berechnet.

Animation der Epidemieausbreitung mit geographisch differenzierter Populationsdichte, Anzahl der Gesammtinfizierten pro Rasterzelle (220mx220m), konstanter Diffusionskoeffizient c=0.1, Infektionsrate 0.3.

Animation mit konstantem Diffusionskoeffizient $c=0.1$ und inhomogener Populationsdichte $B(x,y)$ mit $\underset{x\in D}{\max }B(x)=800/[k{m}^2]$, siehe Bevölkerungsdichte Deutschland 2011.

Raumdiskretisierung des regionaldifferenzierten Diffusionskoffizienten

Um die räumlichen Epidemieausbreitung regional zu differenzieren, nehmen wir an, dass der Diffusionskoeffizient von der Populationsdichte abhängig ist, siehe nicht-konstanter Diffusionkoeffizient

$c(x,y)=\tilde{c}(B(x,y))$.

Für diesen Fall muss Diffusionsmatrix (das Approximationsschema) $A_h$ entsprechend angepasst werden, hierbei werden anstatt eines konstanten Faktors $c/h^2$ vor der Matrix entsprechende Gitterwerte der Funktion $c(x,y)$ in der Matrix $A_h$ figurieren.

Diskretisierung der Randbedingungen

Die homogene Neumann-Randbedingung in diesem Fall lautet:

$\frac{\partial (cu)}{\partial \overrightarrow{n}}\equiv c(x,y)\mathrm{\nabla }u(x,y)\cdot \overrightarrow{n}$.

Mit Anwendung der einseitigen Differenzenquotienten und der Bezeichnung $c(x_i,y_j)=:c_{i,j}$ erhält man

• am linken und rechten Rand des Rechtecks:

$c_{0,j}\frac{u_{1,j}-u_{0,j}}{h}.(-1)=0,c_{n+1,j}\frac{u_{n+1,j}-u_{n,j}}{h}.(1)=0,j=0,1,\dots m+1$,

• am unteren und oberen Rand des Rechtecks:

$c_{i,0}\frac{u_{i,1}-u_{i,0}}{h}.(-1)=0,c_{i,m+1}\frac{u_{i,m+1}-u_{i,m}}{h}.(1)=0,i=0,1,\dots n+1$.

Diskretisierung des Diffusionsterms

Das Approximationsschema für den Diffusionsterm

$div(c(x,y)\mathrm{\nabla }u(x,y))={\partial }_x(c(x,y){\partial }_{x}u(x,y))+{\partial }_y(c(x,y){\partial }_{y}u(x,y))$

kann mit zweifacher Anwendung des zentralen Differenzenquotienten im obigen Ausdruck in den inneren Gitterpunkten $(x_i,y_j),i=1,\dots n,j=1,\dots m$ hergeleitet werden:

$div(c(x,y)\mathrm{\nabla }u(x,y))\approx D_{h/2,x}(c(x_i,y_j)D_{h/2,x}u(x_i,y_j))+D_{h/2,y}(c(x_i,y_j)D_{h/2,y}u(x_i,y_j))$ .

Herleitung des zweiten Differenzenquotienten bez. x:

$D_{h/2,x}(c(x_i,y_j)D_{h/2,x}u(x_i,y_j))=D_{h/2,x}\left(c_{i,j}\frac{u_{i+1/2,j}-u_{i-1/2,j}}{h}\right)$,

$=\frac{1}{h}(\frac{c_{i+1/2,j}{u}_{i+1,j}-c_{i-1/2,j}{u}_{i,j}}{h}-\frac{c_{i+1/2,j}{u}_{i,j}-c_{i-1/2,j}{u}_{i-1,j}}{h})=\frac{1}{h^2}(u_{i+1,j}{c}_{i+1/2,j}-u_{i,j}(c_{i-1/2,j}+c_{i+1/2,j})+u_{i-1,j}{c}_{i-1/2,j})$,

hier bezeichnet $u_{i+1/2,j}:=u(x_i+h/2)$ die Werte der Funktion zwischen den Gitterpunkten $(x_i,y_j),(x_{i+1},y_j)$.

Analog kann man für den zweiten Differenzenquotienten bez. y zeigen:

$D_{h/2,y}(c(x_i,y_j)D_{h/2,y}u(x_i,y_j))=\frac{1}{h^2}(u_{i,j+1}{c}_{i,j+1/2}-u_{i,j}(c_{i,j-1/2}+c_{i,j+1/2})+u_{i,j-1}{c}_{i,j-1/2})$.

Insgesamt gilt für den Diffusionsterm:

• $div(c(x,y)\mathrm{\nabla }u(x,y))\approx \frac{1}{h^2}(u_{i+1,j}{c}_{i+1/2,j}+u_{i,j+1}{c}_{i,j+1/2}-u_{i,j}(c_{i-1/2,j}+c_{i+1/2,j}+c_{i,j-1/2}+c_{i,j+1/2})+u_{i-1,j}{c}_{i-1/2,j}+u_{i,j-1}{c}_{i,j-1/2}).$

Approximationsschema

Unter der Anwendung der Approximation der Randbedingungen und des Diffusionsterms erhalten wir folgende Systemmatrix

$A_h=\frac{-1}{h^2}\left(\begin{array}{ccccc}-h{I}_0& h{I}_0& & \dots & 0\\ {\tilde{I}}_{\ell ,1}& B_1& {\tilde{I}}_{r,1}& & ⋮\\ ⋮& \ddots & \ddots & \ddots & \\ 0& & \dots & h{I}_{m+1}& -h{I}_{m+1}\end{array}\right),$

wobei

$I_0=diag({\overrightarrow{c}}_0),I_{m+1}=diag({\overrightarrow{c}}_{m+1}),{\overrightarrow{c}}_0=(c_{0,0},\dots ,c_{n+1,0}),{\overrightarrow{c}}_{m+1}=(c_{0,m+1},\dots ,c_{n+1,m+1}),$

$B_j=\left(\begin{array}{ccccc}-h{c}_{0,j}& h{c}_{0,j}& 0& \dots & 0\\ c_{1/2,j}& -(c_{\frac{1}{2},j}+c_{\frac{3}{2},j}+c_{1,j+\frac{1}{2}}+c_{1,j-\frac{1}{2}})& c_{3/2,j}& \dots & 0\\ ⋮& \ddots & \ddots & \ddots & \\ 0& \dots & c_{n-1/2,j}& -(c_{n-\frac{1}{2},j}+c_{n+\frac{1}{2},j}+c_{n,j+\frac{1}{2}}+c_{n,j-\frac{1}{2}})& c_{n+1/2,j}& \\ 0& \dots & 0& h{c}_{n+1,j}& -h{c}_{n+1,j}\end{array}\right),$

${\tilde{I}}_{\ell ,j}=\left(\begin{array}{ccccc}0& & \dots & & 0\\ 0& c_{1,j-\frac{1}{2}}& 0& \dots & 0\\ ⋮& \ddots & \ddots & \ddots & ⋮\\ 0& \dots & 0& c_{n,j-\frac{1}{2}}& 0\\ 0& & \dots & & 0\end{array}\right),{\tilde{I}}_{r,j}=\left(\begin{array}{ccccc}0& & \dots & & 0\\ 0& c_{1,j+\frac{1}{2}}& 0& \dots & 0\\ ⋮& \ddots & \ddots & \ddots & ⋮\\ 0& \dots & 0& c_{n,j+\frac{1}{2}}& 0\\ 0& & \dots & & 0\end{array}\right),j=1,\dots m,{\tilde{I}}_{\ell /r,j},B_j\in {ℝ}^{(n+2)\times (n+2)}$ und $I_0,I_{m+1}=\in {ℝ}^{(n+2)\times (n+2)}$.

Bemerkung

In den obigen Matrizen kann man die Zwischenwerte der Funktion c durch die Mittelwerte ersetzen:

$c_{i\pm \frac{1}{2},j}\approx \frac{1}{2}(c_{i\pm 1,j}+c_{i,j}),$

$c_{i,j\pm \frac{1}{2}}\approx \frac{1}{2}(c_{i,j\pm 1}+c_{i,j}).$

In diesem Fall braucht man für den raumabhängigen Diffusionsokeffizient nur die Matrix der Werte an den Gitterpunkten $c_{i,j}$ speichern.

Für stückweise lineare Funktion $c$ sind die obigen Mittelwerte identisch mit den Zwischenwerten, d.h in den obigen Formeln für $c_{i\pm \frac{1}{2},j},c_{i,j\pm \frac{1}{2}}$ gilt Gleichheit '='.

Im Fall einer allgemeinen Funktion ist die Approximation durch die Mittelwerte von zweiter Ordnung, was nach der Addition der Taylorpolynome für $c(x_i\pm \frac{h}{2},y_j),$ bzw. $c(x_i,y_j\pm \frac{h}{2})$ folgt.

Seiteninformation

Dieser Wiki2Reveal Foliensatz wurde für den Lerneinheit Kurs:Räumliche Modellbildung' erstellt der Link für die Wiki2Reveal-Folien wurde mit dem Wiki2Reveal-Linkgenerator erstellt.

• Die Seite wurde als Dokumententyp PanDocElectron-SLIDE erstellt.

• siehe auch weitere Informationen zu Wiki2Reveal und unter Wiki2Reveal-Linkgenerator.

Literatur

• Wikiversity Beitrag zur Modellierung von COVID-19
• Wikipedia Artikel Taylorreihe
• Wikipedia Artikel zu Finiten-Differenzen-Methode
• Numerische Verfahren für Randwertaufgaben Technische Universität Hamburg-Harburg, Lehrmaterial