Theorie und Numerik von Erhaltungsgleichungen

Dieses Buch steht im Regal Mathematik.

Erhaltungssätze

Erhaltungssätze sind physikalische Gesetze, die aussagen, dass eine bestimmte Größe, die Erhaltungsgröße, in einem abgeschlossenen System konstant ist, also erhalten bleibt. Sie spielen eine zentrale Rolle in vielen Bereichen der Physik. Neben starker experimenteller Absicherung lassen sie sich nach dem Noether-Theorem mit bestimmten grundlegenden Symmetrien in Verbindung bringen und sind somit auch theoretisch stark fundiert. Etwa gehört zur Energieerhaltung die Translationsinvarianz physikalischer Aussagen in der Zeit. Beispiele sind

1. Energieerhaltung
2. Impulserhaltung
3. Drehimpulserhaltung
4. Erhaltung von elektrischer Ladung

Kein echter Erhaltungssatz ist die Massenerhaltung. Diese gilt nur bei nichtrelativistischen Geschwindigkeiten; bei hohen Geschwindigkeiten muss die spezielle Relativitätstheorie in Betracht gezogen werden. Die berühmte Formel

$E=mc^{2}$

wird in der Physik als Teil der Energieerhaltung betrachtet: Masse ist dann eine spezielle Form der Erhaltungsgröße „totale Energie“. Ebenso ergeben sich bei zerfallenden Atomkernen nach dem Zerfall kleinere Massensummen der Tochterteilchen.

Keine Erhaltungsgrößen sind beispielsweise Druck, Temperatur oder elektrische Spannung.

Erhaltungsgleichungen

Die mathematische Formulierung eines Erhaltungssatzes wird als Erhaltungsgleichung bezeichnet. Hier werden wir uns mit Strömungsmechanik beschäftigen. Eine der großen wissenschaftlichen Leistungen des 19. Jahrhunderts war die Erkenntnis, dass sich Strömungen durch Kopplung der Erhaltungsgleichungen für Masse, Energie und Impuls, zusammen mit einer Zustandsgleichung, komplett beschreiben lassen. Ausgangspunkt ist dabei die integrale Form. Wir betrachten als Beispiel die Massenerhaltung. Gegeben sei ein Volumen $\Omega$. Die darin enthaltene Masse $M$ ist dann gegeben durch das Integral der Dichte $\rho$ über $\Omega$:

$M=\int _{\Omega }\rho d\Omega .$

Aussage des Erhaltungssatzes der Masse ist, dass Masse nicht zerstört oder erschaffen wird. Änderungen der Masse M im Volumen $\Omega$ mit der Zeit sind also Resultat von Massentransport über den Rand von $\Omega$. Dies lässt sich formulieren als

$M_{t}={\frac {d}{dt}}\int _{\Omega }\rho d\Omega =-\int _{\partial \Omega }f\cdot ndS,$

wobei $f$ die Massenflussdichte beschreibt. Diese lässt sich präzisieren als $f=\rho v$, wobei $v$ die Geschwindigkeit eines kleinen Massenvolumens beschreibt. Damit ergibt sich

$M_{t}={\frac {d}{dt}}\int _{\Omega }\rho d\Omega =-\int _{\partial \Omega }\rho v\cdot ndS.$

Zu beachten ist hierbei, dass dabei außer der Integrierbarkeit von $\rho$ und $\rho v$ keine Voraussetzungen an die Funktionen $\rho$ und $v$ oder an das Volumen $\Omega$ gestellt wurden. Eine zweite wichtige Form einer Erhaltungsgleichung ist die differentielle Form. Dazu wird die letzte Gleichung mittels des Integralsatzes von Gauß umgeformt:

${\frac {d}{dt}}\int _{\Omega }\rho d\Omega +\int _{\Omega }\nabla \cdot \rho vd\Omega =0.$

Ist das Volumen $\Omega$ nicht zeitabhängig, lässt sich Zeitdifferentiation und Integration vertauschen. Da die Aussage für beliebige Volumina gilt, ergibt sich die differentielle Form der Massenerhaltung

$\rho _{t}+\nabla \cdot \rho v=0.$

Allgemeiner haben Erhaltungsgleichungen die Form

$u_{t}+\nabla \cdot f(u,\nabla u)=0$

oder, wenn zusätzlich Volumenkräfte modelliert werden müssen,

$u_{t}+\nabla \cdot f(u,\nabla u)=g(u).$

Letztere Form wird im Englischen auch als Balance law bezeichnet (deutsch: Bilanzgleichung).

Eine dritte wichtige Form der Erhaltungsgleichung ist die schwache Form. Dazu multiplizieren wir die differentielle Form (hier für den eindimensionalen Fall) mit glatten Testfunktionen $\phi \in C_{0}^{1}(\mathbb {R} \times \mathbb {R} )$, also aus dem Raum der stetig differenzierbaren Funktionen mit kompaktem Träger. Integration liefert

$\int _{0}^{\infty }\int _{-\infty }^{\infty }[\phi u_{t}+\phi f(u)_{x}]dxdt=0.$

Partielle Integration ergibt aufgrund des kompakten Trägers von $\phi$

$\int _{0}^{\infty }\int _{-\infty }^{\infty }[\phi _{t}u+\phi _{x}f(u)]dxdt=-\int _{-\infty }^{\infty }\phi (x,0)u(x,0)dx.$

Eine Funktion $u(x,t)$ wird dann schwache Lösung der Erhaltungsgleichung genannt, wenn die obige Gleichung für alle $\phi \in C_{0}^{1}(\mathbb {R} \times \mathbb {R} ^{+})$ erfüllt ist.

Beispiele für Erhaltungsgleichungen

Das wichtigste Beispiel der Strömungsmechanik ist das System der Navier-Stokes-Gleichungen

$\partial _{t}\rho +\nabla \cdot {\textbf {m}}=0,$

$\partial _{t}m_{i}+\sum _{j=1}^{3}\partial _{x_{j}}(m_{i}v_{j}+p\delta _{ij})=\sum _{j=1}^{3}\partial _{x_{j}}S_{ij},\qquad i=1,2,3$

$\partial _{t}\rho E+\nabla \cdot (H{\textbf {m}})=\sum _{j=1}^{3}\partial _{x_{j}}\left(\sum _{i=1}^{3}S_{ij}v_{i}-W_{j}\right)+q.$

Als Vereinfachung ergeben sich bei Vernachlässigung der Terme 2. Ordnung die Euler-Gleichungen, bei denen die Flüsse $f$ nicht von $\nabla u$ abhängen, also ein System erster Ordnung:

$\partial _{t}\rho +\nabla \cdot {\textbf {m}}=0,$

$\partial _{t}m_{i}+\sum _{j=1}^{3}\partial _{x_{j}}(m_{i}v_{j}+p\delta _{ij})=0,\qquad i=1,2,3$

$\partial _{t}\rho E+\nabla \cdot (H{\textbf {m}})=0.$

Analysis von Erhaltungsgleichungen

Erhaltungsgleichungen in differentieller Form sind partielle Differentialgleichungen (PDEs) und lassen sich somit mit deren Maschinerie analysieren. Dazu ist es notwendig, verschiedene Typen von PDEs auseinanderzuhalten. Zunächst bezeichnet man als Ordnung einer PDE den höchsten Grad der auftretenden Ableitungen. Man spricht von einem System, wenn $u$ ein Vektor ist, ansonsten von einer skalaren Gleichung. Sind $f$ und $g$ linear heißt die Gleichung linear, ansonsten nichtlinear. Die Navier-Stokes-Gleichungen sind also ein nichtlineares System zweiter Ordnung, die Euler-Gleichung ein nichtlineares System erster Ordnung. Eine Gleichung heißt instationär, wenn sie eine Zeitabhängigkeit enthält und stationär, wenn das nicht der Fall ist. Sie heißt mehrdimensional, wenn es mehrere Ortsvariablen gibt.

Schließlich teilt man die Gleichungen noch in hyperbolisch, elliptisch, parabolisch und gemischte Formen ein. Grob kann man sagen, dass diese sich durch die Arten der erlaubten Randbedingungen unterscheiden.

• Elliptische Gleichungen erlauben nur Randbedingungen, keine Anfangsbedingungen. Damit gibt es für elliptische Gleichungen keine Variable, die man einer Zeit zuordnen könnte; Sie entsprechen stationären Zuständen und Störungen der Nebenbedingungen machen sich sofort in der gesamten Lösung bemerkbar.

• Parabolische Gleichungen erlauben Anfangs- und Randbedingungen. Sie haben eine Zeitabhängigkeit, Störungen der Nebenbedingungen können sich sofort in der kompletten Lösung bemerkbar machen. Ferner haben parabolische Gleichungen eine Glättungseigenschaft: Sind die Anfangsdaten zum Zeitpunkt Null endlich oft stetig differenzierbar, ist es möglich, dass die Lösung für Zeiten größer Null unendlich oft stetig differenzierbar ist.

• Hyperbolische Gleichungen erlauben ebenfalls Anfangs- und Randbedingungen. Sie haben eine Zeitabhängigkeit, Störungen der Nebenbedingungen breiten sich mit endlicher Geschwindigkeit in ausgezeichnete Richtungen aus. Im Gegensatz zu parabolischen Gleichungen, die Anfangsdaten glätten, können hier auch bei beliebig glatten Anfangsdaten unstetige Lösungen auftreten.

Wir werden hier vor allem hyperbolische Erhaltungsgleichungen betrachten und nebenbei noch parabolische. Aus Gründen der Einfachheit untersuchen wir zunächst ausschließlich eindimensionale Probleme. Dieses Vorgehensweise ist deswegen sinnvoll, weil ein numerisches Verfahren, das schon im eindimensionalen nicht funktioniert, in mehreren Dimensionen erst recht nicht funktioniert. Zunächst betrachten wir die skalare nichtlineare hyperbolische Erhaltungsgleichung mit $f(u)\in C^{1}(\mathbb {R} )$:

$u_{t}+f(u)_{x}=0$ auf dem Gebiet $\mathbb {R} \times \mathbb {R} ^{+}$ und

$u(x,0)=u_{0}(x)$ auf $\mathbb {R} .$

Entropielösungen

Nichtlineare hyperbolische Erhaltungsgleichungen lassen in der Regel mehrere Lösungen zu. Da Erhaltungsgleichungen physikalische Gesetze beschreiben sollen, ist es sinnvoll, aus diesen mit einer Zusatzbedingung jene Lösungen herauszuziehen, die physikalisch sinnvoll sind. Hierbei hat sich die Entropiebedingung als nützlich erwiesen. Nach dem zweiten Hauptsatz der Thermodynamik ist die Gesamtentropie eines Systems nichtsinkend. Ferner steigt die Entropie eines Gases, wenn man sich über einen physikalischen Schock bewegt. Dies führt zur Entropiebedingung

$\int _{x_{1}}^{x_{2}}\eta (u(x,t_{2}))dx\leq \int _{x_{1}}^{x_{2}}\eta (u(x,t_{1}))dx+\int _{t_{1}}^{t_{2}}\psi (u(x_{1},t))dt-\int _{t_{1}}^{t_{2}}\psi (u(x_{2},t))dt.$

$\eta (u)$ ist die sogenannte Entropiefunktion und $\psi (u)$ der Entropiefluss. An dieses Entropie-Entropiefluss-Paar stellt man die Bedingung, dass $\eta$ glatt und konvex ist, $\psi$ glatt und ferner die Beziehung

$\psi '(u)=\eta '(u)f'(u)$

gilt. Dann nennt man eine Lösung, die die obige Ungleichung erfüllt, Entropielösung der Erhaltungsgleichung. Analog kann man eine schwache Form herleiten:

$\int _{0}^{\infty }\int _{-\infty }^{\infty }[\phi _{t}\eta (u)+\phi _{x}\psi (u)]dxdt+\int _{-\infty }^{\infty }\phi (x,0)\eta (u(x,0))dx\geq 0.$

Eine schwache Lösung, die die obige Gleichung für alle zulässigen Entropiepaare erfüllt, heißt schwache Entropielösung der Erhaltungsgleichung. Diese Lösung ist dann sogar eindeutig und hängt in der $L_{1}$-Norm stetig von den Anfangsdaten ab!

Die Lösung der verschwindenden Viskosität

Eine alternative Herangehensweise ist die Betrachtung der Gleichung

$u_{t}+f(u)_{x}=\epsilon u_{xx}$

für $\epsilon >0$. Diese Gleichung ist parabolisch und hat eine eindeutige Lösung $u_{\epsilon }$. Im Grenzwert $\epsilon \rightarrow 0$ ergibt sich die Lösung der verschwindenen Viskosität (vanishing viscosity solution). Diese erfüllt die Entropiebedingung.

Erste Aussagen zur Numerik

Dazu sei ein Gitter aus Gitterzellen $\Omega _{i}$ gegeben mit $\Omega _{i}=(x_{i-1},x_{i})$ und diskrete Zeitpunkte $t_{0},t_{1},\dots$. Die Schrittweiten beschreiben wir mit $\Delta x_{i}=x_{i}-x_{i-1}$ und $\Delta t_{i}=t_{i+1}-t_{i}$. Mit $u_{i}^{n}$ bezeichnen wir die numerische Approximation an die exakte Lösung $u(x,t_{n})$ auf $\Omega _{i}$.

Die zentrale physikalische Eigenschaft die Erhaltungsgleichungen modellieren, ist offensichtlich die Erhaltung. Das numerische Verfahren muss dies berücksichtigen, wenn Hoffnung bestehen soll, eine physikalisch sinnvolle Approximation zu berechnen. Wir werden dies später im Satz von Lax-Wendroff präzisieren, aber zunächst die Definition:

Definition: Konservatives Verfahren

Ein numerisches Verfahren zur Lösung der Erhaltungsgleichung $u_{t}+f(u)_{x}=0$ heißt konservativ, wenn es die Form

$u_{i}^{n+1}=u_{i}^{n}-{\frac {\Delta t_{n}}{\Delta x_{i}}}[F_{i+1/2}-F_{i-1/2}]$

hat. Die Funktion $F$ wird auch als numerische Flussfunktion bezeichnet. Hintergrund ist, dass die numerische Näherung an die Erhaltungsgröße gegeben ist durch

$\sum _{i=I}^{J}\Delta x_{i}u_{i}^{n+1}=\sum _{i=I}^{J}\Delta x_{i}u_{i}^{n}-\Delta t_{n}[F_{I}-F_{J}].$

Sind die Flüsse an den Randpunkten also physikalisch sinnvoll, erhält das numerische Verfahren die Erhaltungsgröße. Entscheidend für ein sinnvolles numerisches Verfahren ist die Wahl der Flüsse. Die Definition ist offensichtlich auch erfüllt, wenn wir die Nullfunktion als Fluss wählen, eine gute numerische Approximation ist davon aber nicht zu erwarten. Um dem abzuhelfen, braucht es eine Eigenschaft, die verlangt, dass unsere numerische Flussfunktion $F$ den physikalischen Fluss $f$ approximiert.

Definition: Konsistentes Verfahren

Eine Flussfunktion $F$ mit den Argumenten $u_{1}$, $u_{2}$ bis $u_{j}$ heißt konsistent, wenn die beiden folgenden Eigenschaften erfüllt sind:

1. $F(u_{1},\dots ,u_{j})=f(u)$
2. $F$ ist Lipschitz-stetig in allen Komponenten.

Ausgestattet mit diesen beiden Eigenschaften lässt sich bereits ein wichtiges Resultat beweisen.

Satz von Lax-Wendroff

Da nichtlineare Erhaltungsgleichungen in der Regel mehrere schwache Lösungen zulassen, ist die Frage der Konvergenz nicht einfach zu beantworten. Es kann sogar sein, dass ein numerisches Verfahren konvergiert, aber nicht gegen eine schwache Lösung der Erhaltungsgleichung. Mit diesem Problem beschäftigt sich der Satz von Lax-Wendroff.

Satz von Lax-Wendroff (Lax und Wendroff, 1960)

Gegeben sei eine Folge von Gittern mit festen Maschenweiten $\Delta x_{l}$ und $\Delta t_{l}$ mit $\Delta x_{l},\Delta t_{l}\rightarrow 0$ für $l\rightarrow \infty$. Gegeben sei ein konsistentes und konservatives numerisches Verfahren, die entsprechende numerische Lösung auf Gitter $l$ sei $U_{l}(x,t)$. Sei ferner die totale Variation von $U_{l}(x,t)$ beschränkt in dem Sinne, dass zu jedem $T$ ein $R>0$ existiert, so dass

$TV(U_{l}(\cdot ,t)):=\sup \sum _{j=1}^{N}|U_{l}(\xi _{j},t)-U_{l}(\xi _{j-1},t)|<R$ für alle $0\leq t<T,l=1,2,\ldots$

und das Supremum über alle Unterteilungen $(\xi )_{n}$ der reellen Achse genommen wird. Schliesslich konvergiere $U_{l}(x,t)$ gegen eine Funktion $u(x,t)$ in folgendem Sinne: Auf jeder beschränkten Menge $\Omega =[a,b]\times [0,T]$ gelte

$\int _{0}^{T}\int _{a}^{b}|U_{l}(x,t)-u(x,t)|dxdt\rightarrow 0$, für $l\rightarrow \infty .$

Dann ist $u(x,t)$ eine schwache Lösung der Erhaltungsgleichung.

Beweis

Zu zeigen ist, dass $u(x,t)$ die schwache Form der Erhaltungsgleichung erfüllt:

$\int _{0}^{\infty }\int _{-\infty }^{\infty }[\phi _{t}u+\phi _{x}f(u)]dxdt=-\int _{\infty }^{\infty }\phi (x,0)u(x,0)dx$ für alle $\phi \in C_{0}^{1}.$

Wir betrachten zunächst das feste Gitter $l$ und vernachlässigen zur Vereinfachung der Notation die zugehörigen Indizes. Die numerische Lösung $U_{l}(x,t)$ ist für alle $\Delta x$, $\Delta t$ gegeben durch die konservative Vorschrift

$u_{i}^{n+1}=u_{i}^{n}+{\frac {\Delta t}{\Delta x}}(F_{i+1/2}^{n}-F_{i-1/2}^{n}).$

Dies multiplizieren wir mit einer beliebigen Testfunktion $\phi$ und erhalten mit der Bezeichnung $\phi _{i}^{n}$ für die Einschränkung von $\phi$ auf die Zelle $i$ und das Zeitintervall $[t_{n},t_{n+1}]$:

$\phi _{i}^{n}u_{i}^{n+1}=\phi _{i}^{n}u_{i}^{n}+{\frac {\Delta t}{\Delta x}}\phi _{i}^{n}(F_{i+1/2}^{n}-F_{i-1/2}^{n}).$

Summieren wir die obige Formel über alle $i$ und $n\geq 0$ auf, ergibt sich

$\sum _{n=0}^{\infty }\sum _{i=-\infty }^{\infty }\phi _{i}^{n}(u_{i}^{n+1}-u_{i}^{n})=-{\frac {\Delta t}{\Delta x}}\sum _{n=0}^{\infty }\sum _{i=-\infty }^{\infty }\phi _{i}^{n}(F_{i+1/2}^{n}-F_{i-1/2}^{n}).$

Diese Summen schreiben wir nun so um, dass die Differenzen nun von Testfunktionen genommen werden. Hierbei ist zu beachten, dass die Summen nur formal unendlich sind, da die Testfunktionen einen kompakten Träger haben und damit für $|i|\geq i_{0}$ und für $n\geq n_{0}$ Null sind. Was wir also tun ist, Summen der Form $\sum _{i=1}^{m}a_{i}(b_{i}-b_{i-1})$ umzuschreiben als $a_{m}b_{m}-a_{1}b_{0}-\sum _{i=1}^{m-1}(a_{i+1}-a_{i})b_{i}$. Damit ergibt sich

$-\sum _{i=-\infty }^{\infty }\phi _{i}^{0}u_{i}^{0}-\sum _{n=1}^{\infty }\sum _{i=-\infty }^{\infty }(\phi _{i}^{n}-\phi _{i}^{n-1})u_{i}^{n}={\frac {\Delta t}{\Delta x}}\sum _{n=0}^{\infty }\sum _{i=-\infty }^{\infty }(\phi _{i+1}^{n}-\phi _{i}^{n})F_{i-1/2}^{n}$

und nach weiteren Umformungen

$\Delta t\Delta x\left[\sum _{n=1}^{\infty }\sum _{i=-\infty }^{\infty }\left({\frac {\phi _{i}^{n}-\phi _{i}^{n-1}}{\Delta t}}\right)u_{i}^{n}+\sum _{n=0}^{\infty }\sum _{i=-\infty }^{\infty }\left({\frac {\phi _{i+1}^{n}-\phi _{i}^{n}}{\Delta x}}\right)F_{i-1/2}^{n}\right]=-\Delta x\sum _{i=-\infty }^{\infty }\phi _{i}^{0}u_{i}^{0}.$

Diese Gleichung gilt auf jedem Gitter $l$. Wir betrachten nun den Grenzwert $l\rightarrow \infty$. Definieren wir Anfangsdaten beispielsweise derart, dass $u_{i}^{0}=1/\Delta x\int _{x_{i}-1/2}^{x_{i}+1/2}u(x,0)dx$, so konvergiert die rechte Seite aufgrund der Glattheit von $\phi$ und der Konvergenz von $U_{l}$ gegen $u$ gegen $-\int _{-\infty }^{\infty }\phi (x,0)u(x,0)dx$. Der erste Term in der Summe auf der linken Seite konvergiert ebenfalls wegen der Glattheit von $\phi$ und der Konvergenz von $U_{l}$ gegen $\int _{0}^{\infty }\int _{-\infty }^{\infty }\phi _{t}(x,t)u(x,t)dxdt$.

Der zweite Term in der Klammer enthält auch die Flussfunktion und ist deswegen etwas weniger glatt und schwieriger. Die Lipschitz-Stetigkeit von $F$, gemeinsam mit der beschränkten Variation von $U_{l}$ ist allerdings ausreichend, um die Konvergenz von $F$ gegen $f$ fast überall zu garantieren. Damit ergibt sich dann auch für diesen Term Konvergenz gegen das gewünschte Integral $\int _{0}^{\infty }\int _{-\infty }^{\infty }\phi _{x}(x,t)f(u(x,t))dxdt$ und damit der Beweis des Satzes.

Entropiebedingung

Das Problem des Satzes von Lax-Wendroff ist, dass die schwache Lösung der Erhaltungsgleichung nicht eindeutig sein muss und er macht keine Aussagen darüber, zu welcher dieser Lösungen man konvergiert. Noch genauer kann es sein, dass unterschiedliche Folgen von Gittern zu unterschiedlichen schwachen Lösungen konvergieren. Ebensowenig sagt er etwas über den Abschneidefehler aus, mit dem wir in Anbetracht von endlich großen Maschenweiten konfrontiert sind oder liefert überhaupt eine Konvergenzaussage. Für das erste Problem ist die Lösung die so genannte Entropiebedingung. Im kontinuierlichen Fall stellt diese eine eindeutige Lösung bereit und auch im diskreten Fall lässt sich eine Entropiebedingung angeben. Gegeben sei also ein Entropiepaar $\eta$, $\psi$ und dazu ein diskretes Analogon $\Phi$, das zu $\psi$ konsistent ist (im bekannten Sinne). Dann ist die diskrete Entropiebedingung:

$\eta (u_{i}^{n+1})\leq \eta (u_{i}^{n})-{\frac {\Delta t}{\Delta x}}(\Phi _{i+1/2}^{n}-\Phi _{i-1/2}^{n}).$

Erfüllt die numerische Flussfunktion diese Bedingung lässt sich der Beweis für den Satz von Lax-Wendroff in analoger Weise durchführen und zeigen, dass die Grenzfunktion dann die schwache Entropielösung ist.

Stabilität

Wir haben nun Bedingungen an ein numerisches Verfahren an der Hand, die im Falle der Konvergenz die Konvergenz gegen eine physikalisch sinnvolle Lösung garantieren. Was fehlt, ist ein Konvergenzbeweis und dafür ist Stabilität des Verfahrens notwendig. Genauer liefert Konsistenz, dass der lokale Abschneidefehler $\tau _{n}$ bei verschwindender Zeitschrittweite gegen Null geht. Was zur Konvergenz noch fehlt ist dann eine Eigenschaft die besagt, dass sich die bereits gemachten Fehler nicht aufschaukeln. Dies bedeutet, dass der durch das numerische Verfahren produzierte Fehler bei gegebenen Schrittweiten $\Delta x$ und $\Delta t$ für $t\to \infty$ in der entsprechenden Norm beschränkt bleibt.

Zur numerischen Lösung $u^{n}$ zum Zeitpunkt $t^{n}$ gehöre der Fehler $E^{n}$. Das numerische Verfahren $N(u)$ liefert dann eine Näherung $u^{n+1}=N(u^{n})$ zum Zeitpunkt $t^{n+1}=t^{n}+\Delta t$ mit Fehler $E^{n+1}$. Also haben wir

${\begin{aligned}E^{n+1}&=u^{n+1}-u(x,t^{n+1})=N(u(x,t^{n})+E^{n})-u(x,t^{n+1})\\&=N(u(x,t^{n})+E^{n})-N(u(x,t^{n}))+N(u(x,t^{n}))-u(x,t^{n+1})\\&=[N(u(x,t^{n})+E^{n})-N(u(x,t^{n}))]-\Delta t\tau ^{n}.\end{aligned}}$

Der zweite Term ist der lokale Abschneidefehler und Stabilität ist die Eigenschaft, die den ersten Term kontrolliert. Wir betrachten zunächst Fall einer linearen Gleichung und dafür ein lineares numerisches Verfahren. Dann ist

$N(u(x,t^{n})+E^{n})-N(u(x,t^{n}))=N(E^{n})$

und es ist ausreichend die Wirkung des numerischen Verfahrens auf den Fehler $E^{n}$ zu betrachen. Bleibt der Fehler beschränkt, lässt sich Konvergenz zeigen (Äquivalenzsatz von Lax).

Von-Neumann-Stabilitätsanalyse

Wir betrachten zunächst Stabilität in der $L_{2}$-Norm. Die theoretische Rechtfertigung dieser Form der Stabilitätsanalyse basiert auf linearen räumlich periodischen Problemen, für die sich dann sehr starke Aussagen treffen lassen. Allerdings lässt sich die Technik auch sehr gut auf andere Probleme anwenden und liefert sehr gute praktische Ergebnisse, womit sie das Standardanalyseverfahren für Stabilität von numerischen Verfahren für zeitabhängige PDEs darstellt. Gegeben sei auf dem Intervall $[0,L]$ die Gleichung

$u_{t}+au_{x}=0$ mit $a\neq 0$.

mit periodischen Randbedingungen und die auf ganz $\mathbb {R}$ periodisch fortgesetzte Lösung $u$. Das numerische Verfahren definiert dann eine Evolution des Fehlers in der Zeit und lässt sich über eine Amplifikationsmatrix darstellen, deren Dimension allerdings mit kleiner werdender Maschenweite ansteigt. Die Idee ist nun, den periodischen Fehler zum Zeitpunkt $t^{n}$ im Diskretisierungspunkt $x_{i}=i\Delta x$ in eine Fourier-Reihe

$E_{i}^{n}=\sum _{-N}^{N}c_{j}^{n}e^{ij\Delta xI}$

zu entwickelt. Dies diagonalisiert die Amplifikationsmatrix und wir können dann die Entwicklung der einzelnen Fourierkoeffizienten in der Zeit analysieren. Nach der parsevalschen Ungleichung gilt $\|e_{i}\|_{L_{2}}=\|c_{j}\|_{L_{2}}$. Die $L_{2}$-Stabilitätsbedingung reduziert sich dann darauf, dass das numerischer Verfahren genau dann stabil ist, wenn der Spektralradius der Amplifikationsmatrix $\rho (G)$ betragsmäßig kleiner gleich eins ist.

Beispiel

Der einfachste Fall ist die lineare Advektionsgleichung

$u_{t}+au_{x}=0,$ mit $a\in \mathbb {R}$

In der Zeit nehmen wir das explizite Euler-Verfahren $u^{n+1}=u^{n}+\Delta t(au_{x})^{n}$ gekoppelt mit zentralen Differenzen auf einem äquidistanten Gitter im Raum. Der zweite Term wird also mittels

$au_{x}\approx {\frac {a}{2\Delta x}}(u_{i+1}^{n}-u_{i-1}^{n})$

approximiert. Insgesamt ergibt sich

${\frac {u_{i}^{n+1}-u_{i}^{n}}{\Delta t}}+{\frac {a}{2\Delta x}}(u_{i+1}^{n}-u_{i-1}^{n})=0,$

was auch die Entwicklung der Fehler definiert und auch jedes einzelnen Terms der Fourier-Reihenentwicklung. Betrachten wir den j-ten Summanden, so ergibt Einsetzen in die obige Formel und Division durch $e^{ij\Delta xI}$ mit $\phi =j\Delta x$:

$c_{j}^{n+1}-c_{j}^{n}+{\frac {a\Delta t}{2\Delta x}}c_{j}^{n}(e^{I\phi }-e^{-I\phi })=0.$

Die Amplifikationsmatrix ist nun gegeben durch

$G(\phi )={\frac {c_{j}^{n+1}}{c_{j}^{n}}}=1-I{\frac {a\Delta t}{\Delta x}}\sin \phi .$

Das Verfahren ist $L_{2}$-stabil, falls $|G|\leq 1$ für alle $\phi$, was hier nicht der Fall ist, da $|G|^{2}=1+\left({\frac {a\Delta t}{\Delta x}}\right)^{2}\sin ^{2}\phi .$ Damit ist das Verfahren unabhängig von der Wahl der Schrittweiten instabil. Dieses Verhalten beobachteten die Mitarbeiter des Manhattan-Projekts, was von Neumann zur Entwicklung der Stabilitätsanalyse führte. Wird im Raum das Upwind-Verfahren

$au_{x}\approx {\frac {a}{\Delta x}}(u_{i}^{n}-u_{i-1}^{n})$

benutzt, so ergibt sich die Courant-Friedrichs-Lewy-Bedingung

${\frac {a\Delta t}{\Delta x}}<1$,

also bedingte Stabilität. Im nichtlinearen Fall oder im Falle variabler Koeffizienten kann das Verfahren durch Linearisierung und Einfrieren der Koeffizienten angewandt werden. Allerdings liefert die Analyse im Allgemeinen Fall nur noch eine notwendige Bedingung für Stabilität, in Spezialfällen auch eine hinreichende. Unter Verwendung eines leicht anderen nichtäquivalenten Stabilitätsbegriffes wird manchmal eine andere Bedingung an Stabilität gestellt:

$\rho (G)\leq 1+c\Delta t$.

Ein allgemeines Verfahren zur vollständigen Stabilitätsanalyse nichtlinearer Gleichungen ist nicht bekannt.

TV-Stabilität

Im nichtlinearen Fall braucht man in der Regel nichtlineare numerische Verfahren und dann funktioniert die obige Fehlerdarstellung nicht. Ist das numerische Verfahren eine Kontraktion, also gilt

$\|N(P)-N(Q)\|\leq N\|P-Q\|,$

so ergibt sich immerhin

$\|E^{n+1}\|\leq \|N(u(x,t^{n})+E^{n})-N(u(x,t^{n}))\|+\Delta t\|\tau ^{n}\|\leq \|E^{n}\|+\Delta t\|\tau ^{n}\|,$

womit sich Stabilität zeigen lässt. Diese Eigenschaft gilt insbesondere für die später erwähnten monotonen Verfahren, die aber maximal erster Ordnung sind. Entsprechend brauchen wir einen besseren Stabilitätsbegriff, nämlich die TV-Stabilität, bei der es um Konvergenz in der $L_{1}$-Norm geht. Hintergrund ist, dass Mengen der Form

$\{v\in L_{1}:\;TV(v)\leq R$ und $\operatorname {supp} (v(\cdot ,t))\subset [-M,M]\forall t\in [0,T]\}$

in $L_{1}$ kompakt sind.

Definition TV-stabil

Wir nennen ein numerisches Verfahren nun TV-stabil, falls die numerischen Lösungen für alle $\Delta t<\Delta t_{0}$ in einer Menge der obigen Form sind mit M und R fix.

Hierzu gilt folgender Satz:

Satz

Gegeben sei ein konservatives numerisches Verfahren mit einem Lipschitz-stetigen numerischen Fluss und für die Anfangsdaten $u^{0}$ existiere ein $\Delta t_{0}$ und ein $R>0$, so dass für alle n und alle $\Delta t$ mit $\Delta t<\Delta t_{0}$ und $n\Delta t\leq T$ gelte:

$TV(u^{n})\leq R.$

Dann ist das numerische Verfahren TV-stabil.

Beweis

Siehe LeVeque, Seite 250.

Hiermit können wir nun ein Konvergenzresultat beweisen:

Satz

Die numerische Lösung U sei von einem TV-stabilen, konservativen und konsistenten numerischen Verfahren mit fester Zeitschrittweite $\Delta t$ generiert. Dann konvergiert die Lösung für $\Delta t\rightarrow 0$ in der $L_{1}$-Norm gegen eine schwache Lösung der Erhaltungsgleichung.

Beweis

Wir nehmen an, das die Aussage falsch wäre, es gäbe also eine Nullfolge $(\Delta t)_{j}$, so dass die zugehörige Folge von numerischen Lösungen nicht gegen eine schwache Lösung konvergiert. Da das Verfahren TV-stabil ist, liegt die Folge $u(\Delta t_{j})$ der numerischen Lösungen in einer in $L_{1}$ kompakten Menge und entsprechend existiert eine $L_{1}$-konvergente Teilfolge, die die Voraussetzungen des Satzes von Lax-Wendroff erfüllt. Diese konvergiert also gegen eine schwache Lösung der Erhaltungsgleichung.

Monotone Verfahren

Eine Eigenschaft der hier betrachteten Erhaltungsgleichungen ist, dass der Lösungsoperator invers monoton ist: gilt für zwei Anfangsdaten $u^{0}\geq v^{0}$, dann gilt für die entsprechenden Lösungen $u(t,\cdot )\geq v(t,\cdot )$. Ein konservatives Verfahren, das die entsprechende diskrete Eigenschaft hat, nennt man monoton. Genauer heisst das Verfahren monoton, falls für die numerische Lösung aus

$u_{j}^{n}\geq v_{j}^{n}$ für alle $j$ folgt, dass

$u_{j}^{n+1}\geq v_{j}^{n+1}$ für alle $j$

gilt. Dies ist äquivalent mit

${\frac {\partial H_{j}}{\partial u_{j+l}}}\geq 0$ für alle $l$,

wobei $H$ mittels $u_{j}^{n+1}=H_{j}(u^{n})$ definiert ist.

Monotone Verfahren haben den grossen Vorteil, dass sie umfassende Konvergenzaussagen erlauben. Harten, Hyman und Lax bewiesen 1976, dass monotone Verfahren im Falle der Konvergenz gegen die schwache Entropielösung konvergieren. 1980 bewiesen dann Crandall und Majda folgendes Resultat:

Satz

Die durch ein monotones Verfahren generierte Lösung konvergiert in $L_{1}$ gegen die schwache Entropielösung der Erhaltungsgleichung für $\Delta t$ gegen Null mit $\Delta t/\Delta x$ fix. Dieses Resultat gilt auch im mehrdimensionalen.

Kröner und Ohlberger bewiesen 2000 eine grundlegende Fehlerabschätzung für monotone Verfahren. Um 2000 wurde von verschiedenen Autoren folgendes mehrdimensionale Resultat erarbeitet, was es auf der einen Seite tatsächlich erlaubt, a priori Fehlerschätzer zu erarbeiten, aber auf der anderen Seite das große Problem monotoner Verfahren vor Augen führt.

Satz

Sei $u_{0}(x)$ in $BV(\mathbb {R} ^{d})$ und $u(x,t)$ eine schwache Entropielösung der Erhaltungsgleichung. Sei $U$ eine durch ein monotones numerisches Verfahren mit dem expliziten Eulerverfahren als Zeitintegration generierte numerische Lösung, mit einem in bestimmter Weise beschränkten Zeitschritt. Sei $K$ eine bestimmte Teilmenge von $\mathbb {R} ^{d}\times \mathbb {R} ^{+}$. Dann existiert eine Konstante $C>0$, so dass

$\|u-U\|_{L_{1}(K)}\leq Ch^{1/4}.$

Im eindimensionalen Fall gilt die Aussage mit $h^{1/2}$, diese Konvergenzrate ist optimal.

Numerisch beobachtet man häufig in O(h)-Verhalten, nichtsdestotrotz ist diese Konvergenzrate zu niedrig. Der Grund für die niedrige Rate liegt in der Eigenschaft der Monotonie. Diese ist sehr weitgehend, was die starken Konvergenzaussagen erst erlaubt, allerdings auch eine extrem starke Einschränkung an die Verfahren darstellt. Ein monotones Verfahren hat nebenbei noch die folgenden Eigenschaften:

1. Die $l_{1}$-Norm der numerischen Lösung ist mit der Zeit nichtsteigend ($l_{1}$-kontraktiv).
2. Damit gilt auch: Die Totale Variation ist nicht steigend (TVD).
3. Und daraus folgt: Monotonie der Lösung bleibt erhalten (Monotonieerhaltend).

Diese Eigenschaften bilden eine Hierarchie von Verfahrensklassen, die echte Teilmengen bilden. Es liegt also auf der Hand, die Anforderungen an das Verfahren abzuschwächen, um eine höhere Konvergenzordnung zu erzielen.

Monotonieerhaltende Verfahren

Die Lösung $u(x,t)$ einer skalaren hyperbolischen Erhaltungsgleichung hat die Eigenschaft, dass aus Monotonie der Anfangsdaten Monotonie der Funktionen $u(x,\cdot )$ für alle Zeiten folgt. Das diskrete Analogon davon sind die monotonieerhaltenden Verfahren, die bei monotonen Anfangsdaten $(u_{j}^{0})_{j}$ monotone Näherungslösungen $(u_{j}^{n})_{j}$ für alle $n$ liefern.

Godunow bewies in den 1950er Jahren, dass lineare Einschrittverfahren zweiter Ordnung für die lineare Advektionsgleichung nur in uninteressanten Spezialfällen monotonieerhaltend sein können. Später wurde die Aussage von anderen auch für lineare Mehrschrittverfahren bewiesen. Wir zeigen den Beweis von Godunow.

Jedes lineare Einschrittverfahren lässt sich in der Form

$u_{j}^{n+1}=\sum _{m}\gamma _{m}u_{j+m}^{n}$

schreiben (das Verfahren ist eine lineare Abbildung von $(u_{j}^{n})_{j}$ auf $(u_{j}^{n+1})_{j}$. Zunächst ein Hilfssatz

Satz

Das obige Verfahren ist genau dann monotonieerhaltend, wenn

$\gamma _{m}\geq 0$ für alle $m$.

Beweis

ObdA sei $n=0$ und $(u_{j}^{n})_{j}$ nichtfallend.

Hinrichtung: Sei das Verfahren monotonieerhaltend, aber es existiere ein p mit $\gamma _{p}<0.$ Wir wählen nun Anfangsdaten:

$u_{j}^{0}=0$, $j\leq 0$ und $u_{j}^{0}=1$, $j>0.$

Dann ist $u_{1-p}^{1}-u_{-p}^{1}=\gamma _{p}<0$ und damit $(u_{j}^{1})_{j}$ nicht nichtfallend, was einen Widerspruch ergibt.

Rückrichtung: Seien alle $\gamma _{m}\geq 0$. Dann ist für alle j:

$u_{j}^{1}-u_{j-1}^{1}=\sum _{m}\gamma _{m}(u_{j+m}^{0}-u_{j+m-1}^{0})\geq 0.$

also ist das Verfahren monotonieerhaltend.

Satz von Godunow

Wir können nun den Satz von Godunow beweisen:

Lineare Einschrittverfahren zweiter Ordnung für die lineare Advektionsgleichung können nicht monotonieerhaltend sein, es sei denn $|c|\Delta t/\Delta x\in \mathbb {N} .$

Beweis

Sei $u(0,x)=\left({\frac {x}{\Delta x}}-{\frac {1}{2}}\right)^{2}-{\frac {1}{4}}$ und die entsprechenden numerischen Anfangsdaten $u_{j}^{0}=\left(j-{\frac {1}{2}}\right)^{2}-{\frac {1}{4}}$. Die exakte Lösung ist ein Polynom zweiten Grades und ergibt sich durch Advektion der Anfangsdaten:

$u(x,t)=\left({\frac {x-ct}{\Delta x}}-{\frac {1}{2}}\right)^{2}-{\frac {1}{4}}.$

In Godunows Sinne bedeutet, dass ein Verfahren zweiter Ordnung diese Lösung exakt reproduziert, es muss also gelten:

$u_{j}^{1}=\sum _{m}\gamma _{m}\left[\left(j+m-{\frac {1}{2}}\right)^{2}-{\frac {1}{4}}\right]=\left(j-c\Delta t/\Delta x-{\frac {1}{2}}\right)^{2}-{\frac {1}{4}}.$

Nehmen wir an, das Verfahren sei Monotonieerhaltend, also $\gamma _{m}\geq 0.$ Wegen $\left(j+m-{\frac {1}{2}}\right)^{2}-{\frac {1}{4}}\geq 0$ folgt

$\left(j-c\Delta t/\Delta x-{\frac {1}{2}}\right)^{2}-{\frac {1}{4}}\geq 0$ für alle $j$.

Für $c\Delta t/\Delta x\in \mathbb {N}$ und größer Null wählen wir nun $j$ mit $j>c\Delta t/\Delta x>j-1$. Dann gilt

$\left(j-c\Delta t/\Delta x-{\frac {1}{2}}\right)^{2}-{\frac {1}{4}}=(j-c\Delta t/\Delta x)(j-c\Delta t/\Delta x-1)<0$

und damit ein Widerspruch.

Ein etwas stärkerer Beweis stammt von Roe aus dem Jahr 1986, siehe Wesseling, Seite 346 für eine Skizze. Der Satz gilt ebenfalls für lineare Mehrschrittverfahren. Die Aussage ist also: Lineare Verfahren können nicht zweite Ordnung erreichen und um hohe Ordnung zu erreichen sind nichtlineare Verfahren unabdingbar. Hier haben sich insbesondere die TVD-Verfahren als nützlich erwiesen.

TVD-Verfahren

Ein numerisches Verfahren hat die TVD-Eigenschaft (von Total Variation Diminishing), wenn für alle $n$

$TV(u^{n+1})\leq TV(u^{n})$

gilt. Diese Eigenschaft gilt analog für die kontinuierliche Lösung und so ist es sinnvoll, dies auch vom numerischen Verfahren zu verlangen. Ist die totale Variation zum Anfangszeitpunkt beschränkt, so ist sie das bei einem TVD-Verfahren auch für alle späteren Zeitpunkte. Damit gilt nach den bereits gebrachten Aussagen zur TV-Stabilität: Konservative Verfahren mit Lipschitz-stetigem Fluss die die TVD-Eigenschaft haben sind TV-stabil und damit konvergent gegen eine schwache Lösung der Erhaltungsgleichung.

Die TVD-Eigenschaft stellt eine Bedingung an die kombinierte Raum-Zeit-Diskretisierung dar. Hierzu gibt es nützliche Sätze von Harten:

Satz

Gegeben sei das explizite Drei-Punkt-Verfahren

$u_{j}^{n+1}=u_{j}^{n}+a_{j}(u_{j+1}^{n}-u_{j}^{n})+b_{j}(u_{j-1}^{n}-u_{j}^{n}),$

wobei $a_{j}$ und $b_{j}$ von $u^{n}$ abhängen. Wenn die Koeffizienten für alle $j$ die Bedingung $a_{j}\geq 0$, $b_{j}\geq 0$ und $a_{j}+b_{j+1}\leq 1$ erfüllen, ist das Verfahren TVD.

Beweis

Wir betrachten

$u_{j+1}^{n+1}-u_{j}^{n+1}=b_{j}(u_{j}^{n}-u_{j-1}^{n})+(1-b_{j+1}-a_{j})(u_{j+1}^{n}-u_{j}^{n})+a_{j+1}(u_{j+2}^{n}-u_{j+1}^{n}).$

Nach Voraussetzung ist dann

$|u_{j+1}^{n+1}-u_{j}^{n+1}|\leq b_{j}|u_{j}^{n}-u_{j-1}^{n}|+(1-b_{j+1}-a_{j})|u_{j+1}^{n}-u_{j}^{n}|+a_{j+1}|u_{j+2}^{n}-u_{j+1}^{n}|.$

Summation über $j$ ergibt genau die totale Variation zum Zeitpunkt $t_{n+1}$:

$TV(u^{n+1})=\sum _{j}|u_{j+1}^{n+1}-u_{j}^{n+1}|\leq \sum _{j}(b_{j+1}+1-b_{j+1}-a_{j}+a_{j})|u_{j+1}^{n}-u_{j}^{n}|=TV(u^{n})$

und damit die Aussage des Satzes.

Hierbei ist anzumerken, dass die Bedingung $a_{j}+b_{j+1}\leq 1$ eine Art CFL-Bedingung ist, damit gibt es also keinen Wiederspruch zur Konvergenz des Verfahrens. Für implizite Verfahren ergibt sich die Aussage

Satz

Gegeben sei das implizite Drei-Punkt-Verfahren

$u_{j}^{n+1}=u_{j}^{n}+a_{j}(u_{j+1}^{n}-u_{j}^{n})+b_{j}(u_{j-1}^{n}-u_{j}^{n})+c_{j}(u_{j-1}^{n+1}-u_{j}^{n+1})+d_{j}(u_{j-1}^{n+1}-u_{j}^{n+1}).$

wobei $a_{j}$ und $b_{j}$ von $u^{n}$ abhängen, während $c_{j}$ und $d_{j}$ von $u^{n+1}$ abhängen. Wenn die Koeffizienten die Bedingung $a_{j}\geq 0,b_{j}\geq 0,a_{j}+b_{j}\leq 1,d_{j}\leq 0$ und $-\infty <C\leq c_{j}$ erfüllen, ist das Verfahren TVD.

Der Beweis teilt das Verfahren in seinen expliziten und den impliziten Anteil auf und nutzt für den expliziten Anteil die vorherige Aussage. Die zusätzlichen Bedingungen sind also dazu da, die totale Variation des impliziten Anteils ausreichend zu beschränken.

Beide Sätze lassen sich auf breitere Diskretisierungssterne erweitern. Ferner kann der explizite Satz genutzt werden, um Bedingungen an TVD-Runge-Kutta-Verfahren zu ermitteln und solche zu konstruieren. Dazu später mehr.

Wir wissen aufgrund des Satzes von Godunow, dass lineare monotonieerhaltende Verfahren nicht von zweiter Ordnung sein können, und zwar global. Entsprechend sucht man den Ausweg über nichtlineare Verfahren. Leider stellt sich heraus, dass auch diese Grenzen haben: Osher bewies 1984, dass TVD-Verfahren an glatten Extrema zu erster Ordnung degenerieren und Goodman und LeVeque bewiesen 1985, dass ein TVD-Verfahren in mehreren Dimensionen maximal erste Ordnung haben kann. Nichtsdestotrotz sind TVD-Verfahren, die höhere Ordnung über Limiter oder über ENO-Konstruktionen erzielen, sehr nützliche Hilfsmittel.

Jameson-Schmidt-Turkel-Verfahren (JST-scheme), Teil 1

Neben den erwähnten Limitern und ENO-Verfahren besteht eine andere Möglichkeit darin, die instabile zentrale Diskretisierung als Ausgangspunkt zu nehmen und über nichtlineare Zusatzterme zu stabilisieren. Jameson, Schmidt und Turkel entwickelten hierzu das nach ihnen benannte JST-Verfahren, zum Einsatz in nichtlinearen Mehrgitterverfahren, da Limiter in diesem Kontext die Konvergenz verlangsamen können. Betrachten wir das semidiskrete Verfahren

$\partial _{t}u_{j}+{\frac {1}{\Delta x}}[F(u)-d]_{j-1/2}^{j+1/2}=0$

mit $F(u_{j+1/2})={\frac {1}{2}}(f(u_{j})+f(u_{j+1}))$. Der Term künstlicher Dissipation wird definiert mittels

$d_{j+1/2}=\epsilon _{j+1/2}^{(2)}(u_{j+1}-u_{j})-\epsilon _{j+1/2}^{(4)}(u_{j+2}-3u_{j+1}+3u_{j}-u_{j-1}).$

Der Koeffizient $\epsilon _{j+1/2}^{(2)}$ wird dabei so konstruiert, dass er in Regionen mit glatter Lösung von der Ordnung $\Delta x^{2}$ ist, während $\epsilon _{j+1/2}^{(4)}$ dort O(1) ist, so dass beide Terme dort von der Ordnung $\Delta x^{3}$ sind, womit sich in glatten Regionen eine niedrige Diffusion ergibt. In der Nähe eines Schocks sollte $\epsilon _{j+1/2}^{(2)}\approx 1$ sein und damit das Verfahren erster Ordnung.

Das originale JST-Verfahren war nicht TVD, funktionierte aber gut in der Praxis, seitdem wurde es erheblich verbessert. Zunächst ein Einschub.

Positive Verfahren/LED-Verfahren

Wie bereits erwähnt sind TVD-Verfahren in mehreren Dimensionen maximal erster Ordnung, es ist also zu überlegen, ob man die TVD-Eigenschaft noch einmal relaxiert oder eine zumindest im eindimensionalen äquivalente Eigenschaft sucht. Dies führt auf positive Verfahren (Spekreijse 1987), beziehungsweise Local extremum diminishing schemes (LED, Jameson). Sei also das semidiskrete Verfahren

$\partial _{t}u_{j}+\sum _{k\neq j}c_{jk}(u_{k}-u_{j})=0$

gegeben. Befindet sich im $u_{j}$ ein lokales Maximum, so ist damit $u_{k}-u_{j}\leq 0$. Dann gilt $\partial _{t}u_{j}\leq 0$ und damit, dass ein lokales Maximum nicht weiter wächst, wenn alle $c_{jk}\geq 0$. Dies gilt offensichtlich auch im mehrdimensionalen, für unstrukturierte Gitter und für lokale Minima. Ein Verfahren mit der ersten Eigenschaft heisst LED, ein Verfahren mit der zweiten positiv. Manchmal redet man statt LED auch von einem diskreten Maximumsprinzip. In 1-D folgt aus der LED-Eigenschaft die TVD-Eigenschaft (Tadmor 1988), nicht aber im mehrdimensionalen. Spekrijse nutzte positive Verfahren, um mehrdimensionale MUSCL-Verfahren zweiter Ordnung zu konstruieren, ein Konvergenzbeweis im mehrdimensionalen steht aber noch aus.

Für das JST-Verfahren gilt folgender Satz:

Satz

Es gelte immer dann, wenn $u_{j+1}$ oder $u_{j}$ ein lokales Extremum ist, für die Koeffizienten des JST-Verfahrens:

$\epsilon _{j+1/2}^{(2)}\geq {\frac {1}{4}}|a_{j+1/2}|$ und $\epsilon _{j+1/2}^{(4)}=0,$

wobei der Koeffizient $a_{j+1/2}$ gegeben sei durch

${\frac {f(u_{j+1})-f(u_{j})}{u_{j+1}-u_{j}}}$ für $u_{j+1}\neq u_{j}$ und

$\partial _{u}f|u_{j}$ für $u_{j+1}=u_{j}$.

Dann ist das Verfahren LED.

Beweis

Sei $v_{j}$ ein Maximum und damit die Koeffizienten $\epsilon _{j-1/2}^{(4)}$ und $\epsilon _{j+1/2}^{(4)}$ Null. Dann ergibt sich das semidiskrete Verfahren zu

$\partial _{t}u_{j}-(\epsilon _{j+1/2}^{(2)}-{\frac {1}{2}}a_{j+1/2})(u_{j+1}-u_{j})+(\epsilon _{j-1/2}^{(2)}+{\frac {1}{2}}a_{j-1/2})(u_{j}-u_{j-1})=0$

und damit, dass alle Koeffizienten positiv sind.

Damit wissen wir, wie die Koeffizienten $\epsilon ^{(2)}$ und $\epsilon ^{(4)}$ zu konstruieren sind.

JST-Verfahren, Teil 2

Das JST-Verfahren wurde im Laufe der Jahrzehnte immer wieder angepasst, die aktuelle Version ist folgende, bei der die Koeffizienten definiert werden als:

$\epsilon _{j+1/2}^{(2)}=\alpha _{j+1/2}Q_{j+1/2}$ und $\epsilon _{j+1/2}^{(4)}={\frac {1}{2}}\alpha _{j+1/2}(1-Q_{j+1/2})$

An einem Extremum sollte $Q$ also Eins sein. Dazu sei

$Q_{j}=R(u_{j+1}-u_{j},u_{j}-u_{j-1})$ und $Q_{j+1/2}=\max(Q_{j},Q_{j+1})$

mit

$R(x,y)=\left\{{\begin{matrix}|{\frac {x-y}{|x|+|y|}}|^{q}&{\mbox{falls }}x\neq 0{\mbox{ oder }}y\neq 0\\0&{\mbox{falls }}x=y=0\end{matrix}}\right.$

$q$ ist dabei eine positive ganze Zahl. Wenn $x$ und $y$ entgegengesetzte Vorzeichen haben (entspricht einem Extremum), ist $R(x,y)=1$, ansonsten kleiner.

Systeme von Gleichungen

Bisher haben wir ausschliesslich skalare Gleichungen betrachtet, manchmal in mehreren Dimensionen. Nun sind die meisten praxisrelevanten Gleichungen Systeme, die Frage ist also, welche Aussagen noch übrig bleiben. Zunächst gilt der Satz von Lax-Wendroff weiterhin. Schon schwieriger wird es bei der Entropiebedingung, diese muss man bei Systemen auf so genannte genuinely nonlinear systems einschränken, was in etwa einer Konvexitätsbedingung an die Flussfunktion entspricht. Damit ist noch keine Konvergenz des numerischen Verfahrens gezeigt, was der Situation im kontinuierlichen entspricht. Ausser für Spezialfälle (starke Einschränkungen an die Anfangsdaten oder das System) gibt es keine Aussagen zu Lösungen für nichtlineare Systeme.

Für Konvergenz des numerischen Verfahren brauchen wir Stabilität und wir wollen die Probleme an der totalen Variation erläutern. Für lineare Systeme ist es möglich die totale Variation so zu definieren, dass das diagonalisierte System betrachtet wird und dann die totale Variation die Summe der totalen Variationen der einzelnen Lösungskomponenten. In jeder einzelnen Komponente ist die skalare Theorie anwendbar und damit auch die gesamte totale Variation nichtsteigend.

Für nichtlineare Systeme funktioniert das nicht mehr, da sich die Diagonalisierungsmatrizen mit der Lösung ändern. In der Tat kann die totale Variation schon für die kontinuierliche Lösung ansteigend sein. Ein Beispiel sind zwei kollidierende Schockwellen bei den Euler-Gleichungen, die nach der Kollision zwei auseinanderlaufende Schockwellen unter Erhöhung der totalen Variation erzeugen. Gerade bei den Euler-Gleichungen in mehreren Dimensionen tritt noch das Problem auf, dass ein Eigenwert mehrfach vorkommt, bei der Erweiterung der MHD-Gleichung ist dann sogar die schwache Entropielösung des Riemann-Problems nicht mehr eindeutig. Einer der wenigen Konvergenzbeweise für nichtlineare Systeme ist Glimm's Random Choice Method.

Zeitintegration

Wir betrachten ab jetzt die semidiskrete Gleichung

$U_{t}+F(U)=0,$

wobei $U$ ein Gittervektor ist und $F(u)$ aus der räumlichen Diskretisierung stammt. Es handelt sich also um ein nichtlineares System gewöhnlicher Differentialgleichungen, die mit einer der vielen Verfahren für Anfangswertprobleme gelöst werden können.

TVD-Runge-Kutta-Verfahren

Eine Frage ist, unter welchen Bedingungen die Zeitdiskretisierung die TVD-Eigenschaft der räumlichen Diskretisierung erhält bzw. wann das Gesamtverfahren TVD ist. Wir hatten bereits Bedingungen an Verfahren bei Nutzung des expliziten Euler-Verfahrens hergeleitet. Diese Technik kann genutzt werden, um zu zeigen, dass das Heun-Verfahren die TVD-Eigenschaft erhält. Dieses ist ein Runge-Kutta-Verfahren 2. Ordnung der Form:

1. $U^{*}=U^{n}+\Delta tF(U^{n}),$
2. $U^{n+1}=U^{n}+{\frac {\Delta t}{2}}[F(U^{n})+F(u^{*})].$

Dies lässt sich als Folge zweier Schritte des expliziten Euler-Verfahrens schreiben:

1. $U^{*}=U^{n}+\Delta tF(U^{n}),$
2. $U{**}^{=}U^{*}+\Delta tF(U^{*}),$
3. $U^{n+1}={\frac {1}{2}}[U^{n}+U^{**}].$

Wenn nun das Verfahren, dass durch $F(U)$ TVD ist (etwa die Bedingungen des Satzes von Harten für das explizite Euler-Verfahren erfüllt), sind die einzelnen Schritte TVD und es gilt

$TV(U^{**})\leq TV(U^{*})\leq TV(U^{n})$

und damit

$TV(U^{n+1})\leq {\frac {1}{2}}TV(U^{n})+{\frac {1}{2}}TV(U^{**})\leq TV(U^{n}),$

das Gesamtverfahren ist dann also TVD und hat dasselbe Stabilitätsgebiet. Dieses ist sogar bei dritter Ordnung möglich (Shu und Osher 1988):

1. $U^{*}=U^{n}+\Delta tF(U^{n}),$
2. $U^{**}={\frac {3}{4}}U^{n}+{\frac {1}{4}}U^{*}+{\frac {\Delta t}{4}}F(U^{*}),$
3. $U^{n+1}={\frac {1}{3}}U^{n}+{\frac {2}{3}}U^{**}+{\frac {2\Delta t}{3}}F(U^{**}).$

Strong stability preserving methods

Allgemeiner heißt ein Verfahren strong stability preserving (SSP), wenn es genau wie das explizite Euler-Verfahren in der $L_{\infty }$-Norm stabil ist, also

$\|U^{n+1}\|_{\infty }\leq \|U^{n}\|_{\infty }$

unter einer CFL-artigen Stabilitätsbedindung. Gottlieb, Shu und Tadmor bewiesen 2001, dass in der Klasse der SSP-Runge-Kutta-Verfahren $m$-ter Ordnung mit $m$ Stufen keine im Vergleich zum expliziten Euler relaxierte Stabilitätsbedingung möglich ist. Das Verfahren von Heun und das genannte Verfahren 3. Ordnung sind in dieser Hinsicht also optimal.

Stationäre Rechnungen, explizite Zeitintegration

Bei stationären Rechnungen ist es nicht von Belang, wie die Zwischenergebnisse aussehen sondern nur, ob die numerische Näherung an die stationäre Lösung sinnvoll ist, entsprechend kann dann auf die TVD-Eigenschaft der Zeitintegration verzichtet werden. Eine zweite Idee ist es, die konvektiven und die diffusiven Terme mit unterschiedlichen Verfahren zu behandeln. Zunächst betrachten wir explizite Zeitintegration. Die Idee ist es, die Koeffizienten der Runge-Kutta-Verfahren so zu wählen, dass das Stabilitätsgebiet maximal wird. Jameson schlägt folgendes Verfahren vor. Die rechte Seite wird aufgespalten in den konvektiven und den diffusiven Anteil

$F(U)=Q(U)+D(U)$.

Dann wird das Runge-Kutta-Verfahren definiert mittels

$u^{(0)}=u^{n}.$

$u^{(k)}=u^{n}-\alpha _{k}\Delta t(Q^{(k-1)}+D^{(k-1)})$, für $k=1,m$

$u^{n+1}=u^{(m)}.$

Hierbei ist $Q^{(0)}=Q(u^{n})$, $D^{(0)}=D(u^{n})$ und ferner $Q^{(k)}=Q(u^{(k)})$ sowie $D^{(k)}=\beta _{k}D(u^{(k)})+(1-\beta _{k})D(u^{(k-1)}).$

Die Koeffizienten $\alpha _{k}$ für den konvektiven Anteil werden nun so gewählt, dass das Stabilitätsgebiet entlang der imaginären Achse vergrößert wird. Für ein 5-stufiges Schema schlägt Jameson folgendes vor:

$\alpha _{1}={\frac {1}{4}},\alpha _{2}={\frac {1}{6}},\alpha _{3}={\frac {3}{8}},\alpha _{4}={\frac {1}{2}},\alpha _{5}=1$

Die Koeffizienten $\beta _{k}$ für den diffusiven Anteil werden so gewählt, dass das Stabilitätsgebiet entlang der negativen reellen Achse vergrößert wird. Für ein 5-stufiges Schema schlägt Jameson folgendes vor:

$\beta _{1}=1,\beta _{2}=0,\beta _{3}=0{,}56,\beta _{4}=0,\beta _{5}=0{,}44$.

Im Vergleich zum klassischen Runge-Kutta-Verfahren ist das Stabilitätsgebiet auf der negativen reellen Achse etwa dreimal so groß.

Implizite Verfahren

Als zweite Klasse wollen wir hier noch implizite Verfahren erwähnen, die dann zum Einsatz kommen können, wenn explizite Verfahren aufgrund ihres Stabilitätsgebiets einen zu kleinen Zeitschritt haben. In der numerischen Strömungsmechanik sind die betrachteten Gleichungen in der Regel sehr steif, interessant sind also solche Verfahren, ein möglichst großes Stabilitätsgebiet haben. Das ist für A-stabile Verfahren erfüllt und so sind BDF-2, die implizite Mittelpunktsregel und das Crank-Nicholson-Verfahren sehr beliebt. Diese Verfahren sind alle zweiter Ordnung, was nach der Zweite Dahlquist-Barriere auch das Optimum für A-stabile lineare Mehrschritt-Verfahren ist. Bei Verfahren höherer Ordnung gibt es im wesentlichen zwei Ansätze. Entweder werden BDF-Verfahren höherer Ordnung genommen, in der Hoffnung, dass die Exlusion der imaginären Achse nicht so schlimm ist. Sowohl BFD-3 als auch BDF-4 wurden erfolgreich eingesetzt.

Die zweite Möglichkeit ist, implizite Runge-Kutta-Verfahren zu nutzen. Diese können grundsätzlich A-stabil sein, allerdings ist es dann erforderlich, ein nichtlineares Gleichungssystem in jeder Stufe zu lösen. Bijl et al (2002) haben so genannte ESDIRK-Verfahren genutzt und gezeigt, dass diese Verfahren kompetitiv sind und besser als die vergleichbaren BDF-Verfahren sein können.

Gemein ist allen Verfahren, dass nichtlineare Gleichungssysteme gelöst werden müssen.

Nichtlineare Gleichungssystemlöser

Zur Lösung von Systemen nichtlinearer Gleichungssysteme wurden zahlreiche Gleichungssystemlöser entwickelt. Wir werden hier die Löser betrachten, die zur numerischen Lösung der Euler- und Navier-Stokes-Gleichungen eingesetzt werden.

Newton-Verfahren

Das Newton-Verfahren (auch Newton-Raphson-Verfahren, aber auch Simpson trug wesentlich zur Entwicklung bei) löst Nullstellengleichungen $F(x)=0$ und beruht auf einer Linearisierung der Funktion $F(x)$. Die Iterationsvorschrift ist gegeben durch

$x_{k+1}=x_{k}-J(x_{k})^{-1}F(x_{k}),$

wobei $J(x_{k})$ die Jacobi-Matrix von $F$ an der Stelle $x_{k}$ ist. Da die Inverse in der Regel nicht zur Verfügung steht, wird diese Iteration in zwei Schritten durchgeführt, nämlich der Lösung eines linearen Gleichungssystems und dem Lösungsupdate:

1. Löse $J(x_{k})\Delta x_{k}=-F(x_{k})$
2. Berechne $x_{k+1}=x_{k}+\Delta x_{k}$

Das Newton-Verfahren konvergiert lokal quadratisch. Die konkrete Form des Jacobi-Matrix hängt insbesondere vom Zeitintegrationsverfahren ab und wie dieses formuliert ist. Betrachten wir das $\Theta$-Verfahren ($\Theta \in [0,1]$):

$u^{n+1}=u^{n}+\Delta t((1-\Theta )f(u^{n+1})+\Theta f(u^{n})).$

Nach einer Finite-Volumen-Diskretisierung erhalten wir für das komplette System auf dem gesamten Rechengitter

$\Omega U^{n+1}=\Omega U^{n}+\Delta t((1-\Theta )F(U^{n+1})+\Theta F(U^{n})),$

wobei $\Omega$ die Diagonalmatrix bezeichnet, bei der auf der Diagonalen die entsprechenden Volumina zu finden sind. Dies lässt sich auf verschiedene Weisen in eine Nullstellengleichung für den Vektor der Unbekannten $U=U^{n+1}$ umformen:

$\Omega U^{n+1}+\Omega U^{n}-\Delta t((1-\Theta )F(U^{n+1})+\Theta F(U^{n}))=0.$

Die Struktur der Jacobi-Matrix ist (auch für andere Zeitintegrationsverfahren) immer die, dass sie aus der Summe der Ableitung des Vektors $U$ und der Ableitung der numerischen Flussfunktion besteht, wobei die Faktoren $\Delta t$ und $\Omega$ nur bei einem der Terme auftauchen. Es ergibt sich dann für das lineare Gleichungssystem in diesem Fall

$A\Delta u=[\Omega \partial U-\Delta t(1-\Theta )\partial F(U)]\Delta u.$

Hierbei hat man noch die Auswahl, in welchem Variablensatz man das Newton-Verfahren durchführen will (konservative oder primitive Variablen etwa). Bei konservativen Variablen ist $\partial U$ eine Diagonalmatrix, dafür sind die Ableitungen der numerischen Flussfunktion in primitiven Variablen häufig etwas einfacher.

Die obige Matrix ist aufgrund der Eigenschaften von $F(U)$ unsymmetrisch, indefinit, keine M-Matrix, für hinreichend große $\Delta t$ schlecht konditioniert. Sie ist eine Blockmatrix, wobei die Größe der Blöcke der Anzahl der Variablen des Systems der Strömungsgleichungen entspricht (je nach Raumdimension 3-5).

Die Aussage der lokal quadratischen Konvergenz gilt für den Fall, wo die Ableitung exakt ausgerechnet wurde und das lineare Gleichungssystem in jedem Schritt exakt berechnet wird. Wird auf eins oder beides verzichtet, so heißt das Verfahren inexakt und verliert man die quadratische Konvergenz, dafür kann die benötigte Rechenzeit drastisch reduziert werden. Erstes Beispiel ist das vereinfachte Newton-Verfahren, bei dem die Ableitung nur im ersten Schritt exakt berechnet wird. Dieses Verfahren kann immerhin superlineare konvergieren. Bei inexakten Newton-Verfahren ist eine quantitative Konvergenzaussage schwierig, grob gilt, je schlechter approximiert wird, desto schlechter ist das Konvergenzverhalten. Wichtigster Faktor ist die Geschwindigkeit, mit der die linearen Gleichungssysteme auf befriedigende Genauigkeit gelöst werden können.

Newton-Krylow-Verfahren

Die Variante, bei der das lineare Gleichungssystem mittels eine Krylow-Unterraum-Verfahrens gelöst werden, nennt man Newton-Krylow-Verfahren. Aufgrund der Eigenschaften der Systemmatrix kommen nicht alle Verfahren in Frage, sondern nur solche für allgemeine Systeme, insbesondere GMRES und BiCGSTAB. Nach praktischer Erfahrung ist BiCGSTAB hier die bessere Wahl (Meister, Vömel 2001).

Matrixfreie Verfahren

Krylow-Unterraum-Verfahren haben die Eigenschaft, dass sie nie die Matrix $A$ explizit benötigen, sondern immer nur Matrix-Vektor-Produkte. Ist die Matrix, wie in diesem Fall eine Jacobi-Matrix, repräsentiert das Matrix-Vektor-Produkt eine Richtungsableitung und kann damit durch Funktionsauswertungen approximiert werden:

${\frac {\partial R(u^{*})}{\partial u}}x=\lim _{\epsilon \rightarrow 0}{\frac {R(u^{*}+\epsilon x)-R(u^{*})}{\epsilon }}\approx {\frac {R(u^{*}+\epsilon x)-R(u^{*})}{\epsilon }}$

für $\epsilon >0$. Das sich ergebende Verfahren braucht somit deutlich weniger Speicher und kann schneller sein als ein Verfahren bei dem die Matrix-Vektor-Produkte ausgerechnet werden. Als grundlegendes Krylow-Unterraum-Verfahren ist hier GMRES die beste Wahl. Dies liegt daran, dass hier letztlich eine Störung der Matrix vorliegt und damit der aufgespannte Krylow-Unterraum $\{z,Az,A^{2}z,\dots ,A^{n-1}z\}$ ebenfalls gestört wird. GMRES ist dabei aufgrund seiner Minimierungseigenschaft robuster als etwa BiCGSTAB gegen solche Störungen: In jedem Schritt wird die Norm $\|Ax-b\|_{2}$ über den aufgespannten Krylow-Unterraum minimiert, GMRES liefert also immer in jedem Schritt etwas sinnvolles.

In unserem konkreten Fall ergibt sich:

$R(U)=\Omega U+\Omega U^{n}-\Delta t((1-\Theta )F(U)+\Theta F(U^{n}))$

und damit

${\frac {\partial R(u^{*})}{\partial u}}x\approx \Omega \epsilon x-{\frac {\Delta t(1-\Theta )}{\epsilon }}F(u^{*})-F(u^{*}+\epsilon v).$

Pro Matrix-Vektor-Multiplikation muss also eine weitere Auswertung der rechten Seite erfolgen, da $F(u^{*})$ während eines Newton-Schritts konstant ist.

Vorkonditionierung

Entscheidender als die Wahl des Krylow-Unterraum-Verfahrens ist die Wahl der Vorkonditionierung. Unterschieden wird zwischen Links- und Rechtsvorkonditionierung (und beidseitiger):

$P^{-1}Ax=P^{-1}b$

entspricht Linksvorkonditionierung und

$AP^{-1}y=b$, $x=P^{-1}y$

Rechtsvorkonditionierung. Es geht darum, einen Vorkonditionierer zu finden, der

1. In der Anwendung wenig kostet.
2. Die inverse von A gut approximiert.

Jedes lineare iterative Verfahren ist als Vorkonditionierer geeignet, da eine Anwendung eines iterativen Verfahrens einer Approximation von $A^{-1}$ entspricht. Für Strömungsprobleme haben sich hier die unvollständige LU-Zerlegung (ILU), bei der die Matrix A selbst approximiert wird und das symmetrische Gauß-Seidel-Verfahren (SGS, $A^{-1}\approx (D+L)D^{-1}(D+R)$) etabliert. SGS ist im supersonischen Bereich extrem gut, da dann die Matrix fast tridiagonal wird und SGS damit ein exakter Löser wäre. Im Bereich kleiner Machzahlen ist dies nicht der Fall und die Performance sinkt. Ferner hat sich herausgestellt, dass Rechtsvorkonditionierung effektiver ist als Linksvorkonditionierung.

Rechtsvorkonditioniertes GMRES

GMRES basiert darauf, mit Hilfe der Arnoldi-Prozedur eine orthogonale Basis des Krylow-Unterraums zu berechnen und dann über das Minimierungsproblem die Lösung auszurechnen. GMRES rechnet im Krylow-Unterraum $\{r_{0},AP^{-1}r_{0},\dots ,(AP^{-1})^{m-1}r_{0}\}$ und wendet bei der Berechnung der Lösung einmalig den Vorkonditionier nochmal an:

Gegeben $x_{0}\in \mathbb {R} ^{n}$, initialisiere $H\in \mathbb {R} ^{(m+1)\times m}$ mit Nullen.

Führe dann den Arnoldi-Prozess durch:

1. Berechne $r_{0}=b-Ax_{0}$. If $r_{0}=0$, then END. $v_{1}={\frac {r_{0}}{\|r_{0}\|_{2}}}$. $\beta =\|r_{0}\|_{2}$.
2. For $j=1,\dots ,m$

   Berechne $z_{j}=P^{-1}v_{j}$.

   Berechne $w_{j}=Az_{j}$

   For $i=1,\dots ,j$ do $h_{ij}=v_{i}^{T}w_{j}$

   $w_{j}=w_{j}-\sum _{i=1}^{j}h_{ij}v_{i}$

   Berechne $h_{j+1,j}=\|w_{j}\|_{2}$ und $v_{j+1}=w/h_{j+1,j}.$

   Berechne die Norm der Näherungslösung über $y_{j}=\operatorname {argmin} _{y}\|\beta e_{1}-H_{j}y\|$. Ist diese kleine genug, STOP.

3. Definiere $V_{m}=[v_{1},\dots ,v_{m}]$.

Berechne anschliessend die Näherungslösung:

$x_{m}=x_{0}+P^{-1}V_{m}y_{m}$ mit $y_{m}$ wie oben. Wenn vorgesehen: RESTART, sonst ENDE.

Im letzten Schritt wird die Lösung als Linearkombination der vorkonditionierten Arnoldi-Basisvektoren $z_{i}=M^{-1}v_{i}$ berechnet.

FGMRES

Eine weitere Variante sind Vorkonditionierer, die sich mit jedem Schritt ändern, dazu gehören insbesondere nichtlineare Mehrgitterverfahren. Dazu ist es nötig, das Krylow-Unterraum-Verfahren etwas anzupassen: Oben haben wir die Vektoren $z_{i}$ nach ihrer Berechnung nicht weiter abspeichern müssen. Es reichte, die $v_{i}$ und den Vorkonditionierer abzuspeichern. Dies ändert sich bei varieblen Vorkonditionierern, bei denen $z_{i}=P_{i}^{-1}v_{i}$ gilt. Eine Möglichkeit so vorzugehen bietet FGMRES (flexible GMRES) (Saad 1993).

Gegeben $x_{0}\in \mathbb {R} ^{n}$, initialisiere $H\in \mathbb {R} ^{(m+1)\times m}$ mit Nullen.

Führe dann den Arnoldi-Prozess durch:

1. Berechne $r_{0}=b-Ax_{0}$. If $r_{0}=0$, then END. $v_{1}={\frac {r_{0}}{\|r_{0}\|_{2}}}$. $\beta =\|r_{0}\|_{2}$.
2. For $j=1,\dots ,m$

   Berechne $z_{j}=P_{j}^{-1}v_{j}$.

   Berechne $w_{j}=Az_{j}$

   For $i=1,\dots ,j$ do $h_{ij}=v_{i}^{T}w_{j}$

   $w_{j}=w_{j}-\sum _{i=1}^{j}h_{ij}v_{i}$

   Berechne $h_{j+1,j}=\|w_{j}\|_{2}$ und $v_{j+1}=w/h_{j+1,j}.$

   Berechne die Norm der Näherungslösung über $y_{j}=\operatorname {argmin} _{y}\|\beta e_{1}-H_{j}y\|$. Ist diese kleine genug, STOP.

3. Definiere $Z_{m}=[z_{1},\dots ,z_{m}]$.

Berechne anschliessend die Näherungslösung:

$x_{m}=x_{0}+Z_{m}y_{m}$ mit $y_{m}$ wie oben. Wenn vorgesehen: RESTART, sonst ENDE.

Der Zusatzaufwand ist hier das Abspeichern der Vektoren $z_{i}$ (die $v_{i}$) müssen eh gespeichert werden). Dafür ist es nun möglich, flexible Vorkondonditionierer einzusetzen. Eine andere Möglichkeit ist GMRES-R von van der Vorst und Vuik, 1994.

Mehrgitter-Verfahren

Die wesentliche Alternative zu Newton-Verfahren sind Mehrgitter-Verfahren. Die schnellsten Verfahren zur Berechnung der stationären Euler-Gleichungen stammen aus dieser Klasse. Die Grundidee ist, eine Hierarchie von gröber werdenden Gittern aufzubauen und diese zu nutzen, um eine Approximation des unbekannten Fehlers einer Anfangsnäherung der Lösung zu berechnen.

Lineare Mehrgitter-Verfahren

Zunächst sei auf dem feinsten Gitter ein lineares Gleichungssystem $A_{l}x=b_{l}$ mit regulärer Matrix $A_{l}\in \mathbb {R} ^{n\times n}$ gegeben. Eine Iteration des Mehrgitter-Verfahrens sieht dann folgendermaßen aus:

$MG(x_{l},b_{l},l)$

if $(l=0)$, $x_{l}=A_{l}^{-1}b_{l}$ (Löse exakt auf gröbstem Gitter)

else

$x_{l}=S_{l}^{\nu _{1}}(x_{l},b_{l})$ (Vorglättung)

$r_{l-1}=R_{l-1,l}(b_{l}-A_{l}x_{l})$ (Restriktion)

$v_{l-1}=0$

Für $(j=0;\;j<\gamma ;\;j++)$ $MG(v_{l-1},r_{l-1},l-1)$ (Berechnung der Grobgitterkorrektur)

$x_{l}=x_{l}+P_{l,l-1}v_{l-1}$ (Prolongation der Grobgitterkorrektur)

$x_{l}=S_{l}^{\nu _{2}}(x_{l},b_{l})$ (Nachglättung)

end if

End

Was ein sinnvoller Glätter $S_{l}$ ist, hängt von der zu lösenden partiellen Differentialgleichung ab. Für viele sind Gauß-Seidel- oder Jacobi-Relaxation geeignet. Da niederfrequente Fehleranteile auf feinen Gittern hochfrequenten Fehleranteilen auf gröberen Gittern entsprechen, ergibt sich mit der Residuumsgleichung

$A_{l-1}e=A_{l-1}(x_{l-1}-x^{*})=A_{l-1}x_{l-1}-b_{l-1}=r_{l-1}$

ein Problem mit ähnlicher Struktur wie das Ursprungsproblem, allerdings mit kleinerer Dimension. Dies wird rekursiv bis zum gröbsten Gitter wiederholt ($\gamma =1$ entspricht einem V-Zyklus, $\gamma =2$ einem W-Zyklus), wo das Gleichungssystem direkt gelöst werden kann.

V-Zyklus

W-Zyklus

Der berechnete Fehler wird dann sukzessive mittels Prolongation P auf die feineren Gitter rückprolongiert und die ursprüngliche Näherung der Lösung korrigiert. Dies funktioniert bei einem linearen Problem $Ax=b$ mit Lösung $x^{*}$, da dann der Fehler $e=x^{k}-x^{*}$ der Näherungslösung $x^{k}$ über die Residuumsgleichung $Ae=r=Ax^{k}-b$ berechnet werden kann. Es folgt noch Nachglättung.

Für viele elliptische und parabolische Gleichungen gibt es umfassende Konvergenztheorie zu linearen Mehrgitterverfahren. Dies ist bei den Euler- und Navier-Stokes-Gleichungen nicht der Fall, sie finden aber manchmal als Vorkonditionierer oder als Löser in Newton-Verfahren Verwendung.

Full Approximation Scheme

Auf ein nichtlineares Problem $L(u)=f$ lässt sich das obige Vorgehen nicht direkt übertragen, da die Residuumsgleichung $L(e)=r$ gar nicht lösbar sein muss. Deswegen löst man da auf dem groben Gitter statt dessen $L(u+e)=L(u)+r$, was im linearen Fall äquivalent wäre. Es ergibt sich dann

$MG({\tilde {u}}_{l},u_{l},f_{l},l)$

if $(l=0)$, $u_{l}=L_{l}^{-1}f_{l}$

else

$u_{l}=S_{l}^{\nu _{1}}(u_{l},f_{l})$

$r_{l}=f_{l}-L_{l}u_{l}$

Wähle ${\tilde {u}}_{l-1}$ und $s_{l-1}$

$f_{l-1}=L_{l-1}({\tilde {u}}_{l-1})+s_{l-1}R_{l-1,l}r_{l}$

Für $(j=0;\;j<\gamma ;\;j++)$ $MG({\tilde {u}}_{l-1},u_{l-1},f_{l-1},l-1)$

$u_{l}=u_{l}+(1/s_{l-1})P_{l-1,l}(u_{l-1}-{\tilde {u}}_{l-1})$

$u_{l}=S_{l}^{\nu _{2}}(u_{l},f_{l})$

end if

End

${\tilde {u}}_{l}$ beschreibt dabei eine Approximation an die Lösung und $s_{l}$ wird so klein gewählt, dass das entsprechende nichtlineare Gleichungssystem lösbar ist. $s=1$ entspricht dem Full Approximation Scheme (FAS) von Achi Brandt (1977). In Hackbusch (81, 82) und seinem Buch Multigrid Methods and Applications (85) findet sich eine ausführlichere Beschreibung von Auswahlmöglichkeiten.

Nichtlineares Mehrgitterverfahren von Jameson & al

Eine weitere Variante wurde von Jameson und Turkel im Laufe von Jahrzehnten für die stationären Euler-Gleichungen entwickelt. Dabei wird auf Nachglättung verzichtet ($\nu _{2}=0$) und als Vorglätter wird ein Schritt mit dem oben erwähnten speziellen Runge-Kutta-Verfahrens gemacht, das nämlich neben einem grossen Stabilitätsgebiet noch Glättungseigenschaften hat. Da die Restriktion auf ein gröberes Gitter führt, ist es dort möglich, den Zeitschritt deutlich zu erhöhen und so sehr rasche Konvergenz zum stationären Zustand zu erzielen. Dazu wird das Runge-Kutta-Verfahren umformuliert als

$U_{l}^{(1)}=U_{l}^{(0)}-\alpha _{1}\Delta t_{l}[F_{l}^{(0)}+C_{l}]$

$\dots$

$U_{l}^{(q+1)}=U_{l}^{(0)}-\alpha _{q+1}\Delta t_{l}[F_{l}^{(q)}+C_{l}].$

Dabei ist $C_{l}=R_{l+1,l}F_{l+1}(U_{l+1})-F_{l}(U_{l}^{(0)})$.

Als Zyklus wird ein 4- oder 5-Gitter-W-Zyklus gewählt. Die Konvergenz wird dabei durch weitere Maßnahmen noch beschleunigt. Zunächst indem nicht in jeder Zelle mit demselben Zeitschritt gerechnet wird, sondern mit einer global gültigen CFL-Zahl, mittels derer dann der lokale Zeitschritt ausgerechnet wird (local time stepping). Allgemeiner haben Lee, Turkel, Roe und Van Leer nichtlineare Vorkonditionierer entwickelt, mit denen die Zeitableitung multipliziert wird.

Als zweites wird Residuenglättung genutzt (Jameson, Baker 1984), was den Glättungseffekt erhöht. Dazu werden in jeder Stufe des Runge-Kutta-Verfahrens die Flüsse $F(U)$ vor der Aufdatierung von $U^{(k)}$ durch ${\bar {F}}(U)$ ersetzt, wobei ${\bar {F}}(U)$ durch die folgende Gleichung mit $\epsilon$ klein gegeben ist:

$-\epsilon {\bar {F}}_{j-1}^{(k)}+(1+2\epsilon ){\bar {F}}_{j}^{(k)}-\epsilon {\bar {F}}_{j+1}^{(k)}=F(U)_{j}^{(k)}.$

Diese Gleichung lässt sich leicht lösen und erhält den stationären Zustand, ist aber für die Berechnung instationärer Probleme komplett ungeeignet.

Es ist möglich, mit diesem Verfahren stationäre Lösungen der Euler-Gleichungen für Tragflächenumströmungen mit drei bis fünf W-Zyklen zu berechnen (Jameson, Caughey 2001). Die stationären Navier-Stokes-Gleichungen sind schwieriger zu lösen, je nach Problem sind 30 bis 100 Schritte notwendig.

Dual Timestepping

Das Problem bei dem oben beschriebenen Mehrgitter-Verfahren ist, dass ein Großteil der Beschleunigungstechniken nur für stationäre Gleichungen funktioniert. Um die Technik auf instationäre Probleme zu übertragen wird das Dual Time Stepping Verfahren genutzt (Jameson 91). Gegeben sei dazu die Semidiskrete instationäre Gleichung

$U_{t}+F(U)=0.$

Wird diese mittels eines impliziten Verfahrens integriert, ergibt sich ein nichtlineares Gleichungssystem

$F^{*}(U)=0,$

wobei $F^{*}$ von der konkreten Wahl der Zeitintegration abhängt. Wird dazu eine zusätzliche Zeitableitung addiert in Dualzeit, ergibt sich das modifizierte Problem

${\frac {\partial U}{\partial t^{*}}}+F^{*}(U)=0.$

Die Lösung des eigentlichen Problems ist dann die Lösung des letzten Problems wenn die duale Zeitableitung verschwindet, also der stationäre Zustand in Dualzeit erreicht ist. Dafür wird das oben erwähnte Mehrgitterverfahren angewandt. Aufgrund der zusätzlichen Terme wird dabei das Spektrum des Operators $F^{*}$ etwas verschoben, was die Konvergenz negativ beeinflusst. Im Fall der RANS-Gleichungen sind 50 bis 250 Iterationen notwendig.

Konvergenztheorie im hyperbolischen

Eine Konvergenztheorie im hyperbolischen Fall ist für keines der Verfahren bekannt. Ein wesentliches Problem sind Schocks. Durch die Kopplung auf dem groben Gittern werden Informationen von beiden Seiten des Schocks theoretisch nach Prolongation über das komplette Gitter verteilt. Dies erschwert die theoretische Analyse bisher entscheidend.

Fluid-Struktur-Interaktion

Als letztes betrachten wir ein Thema, bei dem hyperbolische Erhaltungsgleichungen nur eine Nebenrolle spielen, nämlich gekoppelte Systeme von partiellen Differentialgleichungen, bei denen eine die Strömung eines Fluids beschreibt und eine zweite eine Struktur. Das meistuntersuchte Problem ist dabei die Kombination, bei der Fluid und Struktur über Kräfte interagieren, handelt es sich um Luft, spricht man von Aeroelastizität. Das Fluid verformt also durch mechanische Kräfte das Fluid, was wiederum Kräfte in der Struktur bewirkt. Diese können sich in nichtlinearer Weise aufschaukeln. Beispiele sind

• Flattern von Flugzeugtragflächen oder
• der Zusammensturz der Tacoma-Narrows-Brücke.

Eine andere Form ist die thermomechanische Kopplung, bei der an der Struktur aufgrund von Hitze plastische Verformungen zu befürchten sind oder hervorgerufen werden sollen. Beispiele sind

• der Wiedereintritt von Raumfahrzeugen in die Atmosphäre, bei denen die erhitzte Atmosphäre das Gefährt erhitzt,
• thermische Belastungen in Motoren und Triebwerken oder
• Abkühlungsprozesse mittels Gasen bei Stahlumformung.

Modellierung

Gegeben sind zwei partielle Differentialgleichungen auf verschiedenen Gebieten $\Omega _{1}$ und $\Omega _{2}$. Dazu seien Kopplungsbedingungen gegeben für die Menge $\Omega _{1}\cap \Omega _{2}$. Konkreter haben wir ein System für das Fluid

${\frac {d}{dt}}x_{1}=f(x_{1},x_{2})$

und eines für die Struktur

${\frac {d}{dt}}x_{2}=g(x_{1},x_{2}).$

Die Variablensätze 1 und 2 sind dabei den verschiedenen Gebieten zugeordnet und die Kopplungsbedingung ist in den einzelnen Abbildungen enthalten. Zum Beispiel könnte f den Navier-Stokes- oder Euler-Gleichungen entsprechen und g der Wärmeleitungsgleichung in einer Struktur. Kopplungsbedingung wäre dann, dass auf dem gemeinsamen Rand die Temperatur T und der Wärmefluss q übereinstimmen. Dies ist ein erstes nützliches Modellproblem vor der echten thermomechanischen Kopplung.

Kopplungsverfahren

Grundsätzlich wird zwischen zwei Lösungsansätzen unterschieden: monolithischen, bei denen das gekoppelte System als ein Gleichungssystem gelöst wird, und partitionierten, bei denen bestehende Lösungsverfahren zur Lösung der Einzelsysteme eingesetzt werden. Wesentlicher Vorteil der letzteren Ansätze ist, dass bestehende Löser für die jeweiligen Probleme verwendet werden können, was den Entwicklungsaufwand drastisch reduziert. Für gekoppelte Probleme existiert dagegen in der Regel nichts, so dass die Implementierung eines monolithischen Verfahrens sehr hohen Aufwand bedeuten kann. Wir werden uns hier auf partitionierte Verfahren beschränken.

Die Einzelsysteme seien also mit dem jeweiligen Verfahren im Raum diskretisiert, wobei wir der Einfachheit halber die Notation für $x_{1}$ und $x_{2}$ beibehalten:

${\frac {d}{dt}}x_{1}=F(x_{1},x_{2}),$

${\frac {d}{dt}}x_{2}=G(x_{1},x_{2}).$

Lose Kopplung

Einfachster Fall ist nun die lose oder schwache Kopplung. Gegeben sei für die jeweiligen Systeme ein Zeitintegrationsverfahren $\Phi _{i}$, was aus der Lösung $x_{i}^{n}$ zum Zeitpunkt $t_{n}$ die Lösung $x_{i}^{n+1}$ zum Zeitpunkt $t_{n+1}$ generiert. Die erste Möglichkeit ist dann folgender Algorithmus, der parallel ausgeführt werden kann:

$x_{1}^{n+1}=\Phi _{1}(x_{1}^{n},x_{2}^{n}),$

$x_{2}^{n+1}=\Phi _{2}(x_{1}^{n},x_{2}^{n}).$

Eine üblichere Variante, die nur sequentiell funktioniert, ist:

$x_{1}^{n+1}=\Phi _{1}(x_{1}^{n},x_{2}^{n}),$

$x_{2}^{n+1}=\Phi _{2}(x_{1}^{n+1},x_{2}^{n}).$

Beide Kopplungsverfahren sind maximal erster Ordnung in der Zeit und explixit, so dass sich erhebliche Zeitschritteinschränkungen ergeben können. Beide Varianten kann man innerhalb eines Zeitschritts iterieren, um die Genauigkeit zu erhöhen.

Einschub Thermische Kopplung

Wir betrachten nun konkret die Kopplung der Navier-Stokes-Gleichungen mit der Wärmeleitungsgleichung. Im diskreten Fall ist es nicht möglich, in Struktur und Fluid sowohl Temperatur als auch Wärmefluss am Rand vorzuschreiben, da dies für keine der Gleichungen sinnvolle Randbedingungen ergibt. Es gibt also die Möglichkeit, dem Fluid und der Struktur Temperatur oder Wärmefluss vorzuschreiben.

Die eine Möglichkeit bedeutet: Die Wärmeleitungsgleichung hat als Randbedingung eine Temperaturvorgabe und gibt dem Fluid einen Wärmefluss, während die Strömung als Randbedingung einen Wärmefluss erhält und eine Randtemperatur an die Struktur zurückgibt. Laut Giles 1997 ist dieses Verfahren instabil.

Deswegen erhält die Strömung am Rand Temperaturdaten und die Struktur einen Wärmefluss.

Starke Kopplung

Schwache Kopplung hat verschiedene Probleme: Geringe Ordnung, möglicherweise starke Zeitschrittbeschränkungen und schließlich erfüllt das Verfahren keine zusätzlichen Bedingungen wie Energieerhaltung. Eine Lösung ist eine implizite Herangehensweise, wobei dann die Frage ist, wie ein partitioniertes Lösungsverfahren aussieht. Folgende Formulierung bietet sich an (siehe beispielsweise Mathies, Steindorf 2002):

$x_{1}^{n+1}=\Phi _{1}(x_{1}^{n+1},x_{2}^{n+1}),$

$x_{2}^{n+1}=\Phi _{2}(x_{1}^{n+1},x_{2}^{n+1}).$

Ein Newton-Schritt für dieses System wäre dann:

${\begin{pmatrix}I-D_{x_{1}}\Phi _{1}&-D_{x_{2}}\Phi _{1}\\-D_{x_{1}}\Phi _{2}&I-D_{x_{2}}\Phi _{2}\end{pmatrix}}{\begin{pmatrix}\Delta x_{1}\\\Delta x_{2}\end{pmatrix}}=-{\begin{pmatrix}x_{1}-\Phi _{1}(x_{1},x_{2})\\x_{2}-\Phi _{2}(x_{1},x_{2})\end{pmatrix}}.$

Nun liegen die entsprechenden partiellen Ableitungen nicht vor. Diese können allerdings entweder durch eine matrixfreie Technik in einem Krylov-Unterraum-Verfahren wie oben bereitgestellt werden oder durch Newton-Schritte im lokalen Verfahren.

Literatur

Als Literatur ist zu empfehlen:

• C. Hirsch: Numerical computation of internal and external flows, 2 Bände, 1988, Wiley & Sons, New York. Dieses Buch beschreibt umfassend den Stand der Wissenschaft zum damaligen Zeitpunkt.
• Randall J. LeVeque: Numerical Methods for Conservation Laws: Lectures in Mathematics, 1992, Birkhäuser Verlag. Dies ist ein recht kurzes Buch, das aus einer Vorlesung LeVeques an der ETH Zürich entstanden ist und stellt die vermutlich beste Einführung in das Thema dar.
• Randall J. LeVeque: Finite Volume Methods for Hyperbolic Problems, 2002, Cambridge Texts in Applied Mathematics, ISBN 0-521-00924-3. Zehn Jahre später das ganze nochmal, aber in ausführlich.
• P. Wesseling: Principles of Computational Fluid Dynamics, 2000, Springer Verlag. Wesseling geht sehr gewissenhaft vor und behandelt Strömungsmechanik und Verfahren für inkompressible und kompressible Strömungen.

Zusammenfassung des Projekts

„Theorie und Numerik von Erhaltungsgleichungen“ ist nach Einschätzung seiner Autoren zu 90 % fertig

• Zielgruppe: Studierende der Mathematik, Physik oder des Maschinenbaus ab dem 5. Semester mit grundlegenden Kenntnissen in Numerik.
• Lernziele: Grundlegende theoretische Aussagen zu Erhaltungungsgleichungen und der zugehörigen Numerik mit Schwerpunkt nichtlinearer Gleichungen der Strömungsmechanik. Darüberhinaus grundlegendes Wissen zu Finite-Volumen-Verfahren und nichtlinearen Lösungsverfahren.
• Buchpatenschaft / Ansprechperson: Benutzer:P. Birken
• Sind Co-Autoren gegenwärtig erwünscht? Nein, aber die Korrektur von Tippfehlern oder Anmerkungen zu Fehlern auf der Diskussionsseite ist erwünscht.

Diese Seite hat mittlerweile eine Größe erreicht, die es als geeignet erscheinen lässt, sie in mehrere einzelne Seiten zu zerlegen. In welche Teile diese Seite zerlegt werden könnte, kann auf der Diskussionsseite besprochen werden. Wie man es macht, steht im Wikibooks-Lehrbuch im Abschnitt Buch in Kapitel untergliedern.