Numerik von Differentialgleichungen

Georg Simbrunner

10. Marz 2015

Inhaltsverzeichnis

1 Klassifikation von Differentialgleichungen und Problemtypen 21.1 Hamiltonische Systeme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21.2 Molekuldynamik . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31.3 Elektrische Netzwerke . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

2 Theoretische Grundlagen 52.1 Existenz und Eindeutigkeit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52.2 Kondition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

3 Verfahren fur Anfangswertprobleme-Einschrittverfahren 103.1 Explizites Eulerverfahren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103.2 Implizites Eulerverfahren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103.3 Verfahren basierend auf numerischer Integration . . . . . . . . . . . . . . . . . . 113.4 Allgemeines zu Einschrittverfahren . . . . . . . . . . . . . . . . . . . . . . . . . . 12

4 Fehleranalysis 13

5 Stabilitat der Verfahren 145.1 Konsistenzfehlerabschatzung beim expliziten Eulerverfahren . . . . . . . . . . . . 145.2 Konsistenzfehler beim verbesserten Euler-Verfahren . . . . . . . . . . . . . . . . . 155.3 Stabilitat des Eulerverfahrens . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155.4 Konvergenz des expliziten Eulerverfahrens . . . . . . . . . . . . . . . . . . . . . . 16

6 Runge-Kutta-Verfahren 176.1 Allgemeines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176.2 Das Runge-Kutta-Verfahren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176.3 Wurzelbaume . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

7 Automatische Schrittweitensteuerung 22

8 Stabilitat von Runge-Kutta-Verfahren 258.1 Lineare DGL mit konstanten Koeffizienten . . . . . . . . . . . . . . . . . . . . . . 258.2 Stabilitat von nichtlinearen Differentialgleichungen . . . . . . . . . . . . . . . . . 298.3 B-stabile Verfahren hoherer Ordnung . . . . . . . . . . . . . . . . . . . . . . . . . 31

9 Symplektische Verfahren fur Hamiltonische Systeme 339.1 Spezielle Verfahren fur Hamiltonische Systeme . . . . . . . . . . . . . . . . . . . 36

1

10 Symplektische Abbildungen 3710.1 Das symplektische Eulerverfahren (KO 1) . . . . . . . . . . . . . . . . . . . . . . 3810.2 Das Stormer-Verlet-Verfahren (KO 2) . . . . . . . . . . . . . . . . . . . . . . . . 39

11 DAEs: Differential-algebraische Gleichungen 4111.1 Numerische Verfahren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

11.1.1 Reduktion auf gewohnliche Differentialgleichungen . . . . . . . . . . . . . 4211.1.2 Symplektische Verfahren fur Hamiltonische DAEs . . . . . . . . . . . . . . 43

12 Mehrschrittverfahren 44

1 Klassifikation von Differentialgleichungen und Problemtypen

1.1 Hamiltonische Systeme

Klasse von Mechanikproblem mit Position und Impuls. Dabei ist q ∈ Rn die Position, p ∈ Rnder Impuls. Aus Impuls und Position kann man die Energie definieren, wobei die Energie durcheine Hamiltonfunktion beschrieben wird.

H(p, q) = V (q) + T (p) (1.1)

V (q) ist die potentielle Energie, T (p) die kinetische Energie. Dies fuhrt zu den HamiltonischenBewegungsgleichungen

q =∂H

∂p(1.2a)

p = −∂H∂q

(1.2b)

Beispiel Feder p = mq

H(p, q) =h

2q2 +

1

2mp2

q =∂H

∂p=

p

m

p = −∂H∂q

= −kq

Es gilt automatisch Energieerhaltung:

d

dtH(p(t), q(t)) =

∂H

∂p

∂p

∂t+∂H

∂q

∂q

∂t=∂H

∂p

(−∂H∂q

)+∂H

∂q

∂H

∂p= 0 (1.3)

Beispiel Fadenpendel/Bsp3 1. UE In der Ubung zu rechnen. Hamiltonisches System hin-schreiben, Positionsvektor durch Winkel α in verallgemeinerten Koordinaten beschrieben (Po-larkoordinaten).

q = α

p = ml2α

2

Abbildung 1: Fadenpendel

Der Impuls ist durch die Winkelgeschwindigkeit berechenbar. Die Hamiltonfunktion ist

H(p, q) = −mgl cos(α)︸ ︷︷ ︸V (α)

+1

2ml2p2︸ ︷︷ ︸

T (p)

Dann hat man mit Hamiltonformalismus sofort 2 Differentialgleichungen da stehen. Man konnteauch mehrere gekoppelte Pendel betrachten. Man konnte die Masse auch durch KartesischeKoordinaten beschreiben und fordern, dass der Abstand der Masse zum Aufhangungspunktkonstant bleibt (DAE-Formulierung).

Wir suchen die Bahn

(x(t)y(t)

)mit der Nebenbedingung x2(t) + y2(t) = l2. Wir fuhren eine

zusatzliche Unbekannte F (Kraft, die im Faden liegt/Spannkraft) ein. Gesucht sind x(t), y(t), F (t)

x = − x

mlF (1.4a)

y = −g − y

mlF (1.4b)

0 = x2(t)− y2(t)− l2 (1.4c)

Die dritte Gleichung 1.4c ist eine algebraische Gleichung. Wir haben somit ein System von Dif-ferentialgleichungen mit algebraischer Nebenbedingung (differential-algebraic equation/DAE).Diese stellen in der Numerik eine eigene Problemklasse dar. Dies entspricht bei der Optimierungmit Nebenbedingung dem Lagrange-Parameter.

1.2 Molekuldynamik

Atome werden als klassische Teilchen mit Position q und Impuls p beschrieben. Dies wird z.B.bei der Faltung von Proteinen verwendet.

H(p, q) =1

2

∑i

1

mi|pi|2︸ ︷︷ ︸

T (p)

+V (q) (1.5)

V (q) = VB + VQ + VV V (1.6)

3

Das Potential ergibt sich dabei aus quantenmechanischen Korrekturen VV V (Van-der-Vaals-WW), dem elektrischen Potential VQ und der Bindungsenergie VB (rij ist dabei der Optimal-abstand):

VB =∑i,ji<j

1

2bij(|qi − qj | − r∗ij

)2(1.7a)

VQ =∑i,ji<j

1

ε

QiQj‖qi − qj‖

(1.7b)

VV V =∑i,ji<j

Aij‖qi − qj‖12

− Bij‖qi − qj‖6

(1.7c)

Das will man fur sehr viele Teilchen (z.B. 109) rechnen, VB und VV V wirken lokal, die Coulomb-krafte VQ wirken weit und daher fur alle Paare, was auf einen O(n2)-Algorithmus fuhrt. Diesmuss man naherungsweise durchfuhren (Multipol-Approximation).

1.3 Elektrische Netzwerke

Abbildung 2: Kirchhoff-Stromkreis

Es gilt das Ohmsche Gesetz U = R · I. Die Spannung U ist eine Potentialdifferenz. An jedemKnoten haben wir ein Potential, unsere Potentiale V1, V2, V3. Eines davon konnen wir beliebigwahlen (beliebige Eichung), z.B. V1 = 0. In jedem Knoten ist die Summe der Strome gleich 0(∑

i Ii = 0). Es ergibt sich

I1 = I2 + I3

1

R1(V3 − V2) =

1

R2(V2 − V1) +

1

R3(V2 − V1)

U = V3 − V1 ⇒ V3 = U

In jedem Knoten kann man das Potential V2 ausrechnen. Wir mussen nur ein lineares Glei-chungssystem losen.

4

Wir betrachten nun einen Kondensator mit Kapazitat C. Dieser speichert Ladung Q mit

Q = C · U (1.8a)

I =dQ

dt(1.8b)

I = CdU

dt(1.8c)

Damit ergibt sich fur den Stromkreis

I =1

R(U − V2) = C

d

dt(V2 − V1)

d

dtV2 =

1

RC(U − V2)

Abbildung 3: Kondensatorstromkreis

Mit der Anfangsbedingung V(0)

2 − V (0)1 = 0 kann man losen:

V2(t) = U(1− e−tRC )

Dies kann man auch fur gekoppelte Gleichungen losen, was sehr schwierig werden kann. His-torische Gerate mit diskreten Bauteilen funktionierten so, große Schaltkreise von integriertenBauteilen 106 Komponenten kann man diese Gleichungen verwenden, diskretisiert man die Netz-werke und kommt wieder auf ahnliche Gleichungen.

2 Theoretische Grundlagen

2.1 Existenz und Eindeutigkeit

Definition 2.1 (Anfangswertproblem). Gesucht ist ein y ∈ C1(I,Rn) das

y′(t) = f(t, y(t)) ∀t ∈ I (2.1)

y(t0) = y0 (2.2)

lost, I ist ein Intervall, f die rechte Seite und t die”

Zeit“. Der Definitionsbereich von f heißt

”erweiterter Zustandsraum“ oder

”erweiterter Phasenraum“ Ω ⊂ R× Rn

5

Abbildung 4: Existenzintervall

Wie weit man fortsetzen kann, sagt der Satz von Peano unter schwachen Voraussetzungen, eskann Blow-Up-Phanomene geben oder es kann f bis zum Rand von Ω definiert sein.Fur autonome Systeme, d.h. f(t, y(t)) = f(y(t)) heißt Ω0 ⊂ Rn Zustandsraum oder Phasen-raum.

Definition 2.2 (Evolution). Sei (t0, y0) ∈ Ω, y(·) die Losung vom AWP, so ist die Evolutionφt,t0 : Rn → Rn die Funktion

φt,t0 : y0 7→ y(t) (2.3)

φt,t = id sowie φs,tφt,t0 = φs,t0 und φt0,tφt,t0 = id.

Bei autonomen Differentialgleichungen gilt:

φt,t0 = φt−τ,t0−τ (2.4)

Es reicht daher eine einparametrige Familie φt := φt,0 anzugeben. Dieses φt heißt Phasenfluss.Diese Familie von Funktionen bildet eine Gruppe.

Zur Existenz und Eindeutigkeit:

Satz 2.3 (Satz von Peano). Fur f ∈ C(Ω,Rn) erhalt man die Existenz einer Losung bis zumRand ∂Ω.

Beweis. Beweisidee: Es konnen 3 Falle auftreten

1. Losung existiert fur t→∞

2. Losung existiert fur t < t+ und limt→t+ ‖y(t)‖ =∞ (Blow-Up-Phanomen)

3. Losung endet am endlichen Rand ∂Ω

Die Existenz einer Losung fur t→∞ wird oft gezeigt durch Ausschluss von (2) und (3), daherfolgt die Existenz der Losung fur t ∈ R.

Falls F zusatzlich Lipschitzstetig im 2. Argument ist, konnen starkere Aussagen getroffen wer-den.

6

Satz 2.4 (Picard-Lindelof). Sei f ∈ C(Ω,Rn) und in einer Umgebung U von (t0, y0) Lipschitz-stetig im 2. Argument, d.h. ‖f(t, y(t)) − f(t, z(t))‖ ≤ L‖y(t) − z(t)‖ ∀(t, y), (t, z) ∈ U , dannexistiert eine eindeutige Losung y(t) in einer Umgebung U.

Beweis. Wir nehmen an, dass f uberall Lipschitz im 2. Argument ist (beweistechnische Verein-fachung), d.h. auf U = [t0, T ]× Rn. Das AWP lautet

y′(t) = f(t, y(t)) ∧ y(t0) = y0 ∀t ∈ [t0, T ] (2.5a)

y(t) = y0 +

∫ t

t0

f(s, y(s))ds (2.5b)

Wir zeigen die Existenz und Eindeutigkeit daher fur die Integralgleichung. Wir definieren daherden Integraloperator

T : C(I,Rn)→ C(I,Rn) (2.6a)

[T (y)](t) := y0 +

∫ t

t0

f(s, y(s))ds (2.6b)

Damit kann man die Integralgleichung in Fixpunktform hinschreiben mit y = T (y). Falls flipschitzstetig mit Konstante L < 1 ist, kann der Banachsche Fixpunktsatz angewendet werden

‖T (y)− T (z)‖∼ ≤ LT ‖y(t)− z(t)‖∼ (2.7)

mit LT auf einem vollstandigen Raum (bzgl. der Norm ‖ · ‖∼), liefert der Fixpunktsatz genaueine Losung. Definiere die Norm

‖y(t)‖∼ = maxt∈[t0,T ]

e−L(t−t0)‖y(t)‖2

(2.8)

so liefert der Banachsche Fixpunktsatz eine eindeutige Losung. Da fur t ∈ [t0, T ] der Faktore−L(t−t0) ist unsere Norm aquivalent zur Supremumsnorm (Maximumsnorm) und C(I,Rn) istdamit vollstandig bezuglich ‖ · ‖∼.

‖T (y)− T (z)‖∼ = maxt∈[t0,T ]

e−L(t−t0)‖y0 +

∫ t

t0

f(s, y(s))ds−(y0 +

∫ t

t0

f(s, z(s))

)‖2

≤ maxt

e−L(t−t0)

∫ t

t0

‖f(s, y(s))− f(s, z(s))‖

≤ maxt

∫ t

t0

Le−L(t−t0)e−L(s−t0)‖y(t)− z(t)‖ds

≤ maxt

∫ t

t0

Le−L(t−s)ds︸ ︷︷ ︸≤1−e−L(t−t0)

maxse−L(s−t0)‖y(s)− z(s)‖︸ ︷︷ ︸

‖y−z‖∼

≤ (1− e−L(t−t0))︸ ︷︷ ︸LT<1

‖y − z‖∼

7

Abbildung 5: Illustration der Stabilitat

2.2 Kondition

Darunter versteht man die Verstarkung von Storungen in den Eingabedaten zu Storungen imErgebnis. Wir betrachten die Kondition bezuglich der Eingabedaten des AWP.

Satz 2.5. Es gelte Lipschitz-Bedingung ‖f(t, y)−f(t, z)‖ ≤ L‖y−z‖. Dann gilt fur y(t) = φt,t0y0

und z(t) = φt,t0z0

‖y(t)− z(t)‖ ≤ eL(t−t0)‖y(t)− z(t)‖∼ (2.9)

Als Vorbetrachtung zeigen wir das Lemma von Gronwall:

Lemma 2.6 (Gronwall). Seien u, v ∈ C([t0, t],R) und c ∈ R mit u ≥ 0, v ≥ 0, c ≥ 0. Es gelte

v(t) ≤ ct∫ t

t0

u(s)v(s)ds ∀t ∈ [t0, T ] (2.10)

dann gilt v(t) ≤ ce∫ tt0u(s)ds

.

Beweis. Sei c > 0, dann definiere

w(t) := c+

∫ t

t0

u(s)v(s)ds (2.11)

Dafur gilt v(t) ≤ w(t) und 0 < c ≤ w(t). Es gilt w′(t) = u(t)v(t) ≤ u(t)w(t). Da w > 0 gilt

w′(t)

w(t)= [log(w(t))]′ ≤ u(t) ∀t ∈ [t0, T ]

log(w(t))− log(w(t0)) ≤∫ t

t0

u(s)ds

Es gilt dann w(t) ≤ w(t0)e∫ tt0u(s)ds

und auch v(t) ≤ w(t) ≤ w(t0)e∫ tt0u(s)ds

. Fur c = 0 wahle ein

ε > 0 beliebig und v(t) ≤ ε+∫ tt0u(s)w(s)ds und es folgt aus dem 1. Beweisteil v(t) ≤ εe

∫ tt0u(s)ds

,mit ε→ 0 gilt v = 0.

Zum Beweis von Satz 2.5:

8

Beweis. Mit der Integralgleichung des AWP gilt

‖y(t)− z(t)‖ = ‖(y0 +

∫ t

t0

f(s, y(s))ds

)−(z0 +

∫ t

t0

f(s, z(s))ds

)‖

≤ ‖y0 − z0‖ +

∫ t

t0

L‖y(s)− z(s)‖ds ≤ ‖y0 − z0‖ +

∫ t

t0

u(s)v(s)ds

Mit dem Lemma von Gronwall (Lemma 2.6) gilt

‖y(t)− z(t)‖ ≤ ‖y0 − z0‖e∫ tt0Lds

= eL(t−t0)‖y0 − z0‖ (2.12)

Fur kleine Zeitintervalle (im Vergleich zu 1L) kann man den Verstarkungsfaktor eL(t−t0) als gut

konditioniert betrachten, nicht aber fur große Intervalle. Diese Abschatzung kann ohne weitereAnnahmen nicht verbessert werden, was folgendes Beispiel zeigen soll.

Beispiel 2.7. Es sei f(y) = ay und |f(y)− f(z)| ≤ |a| |y − z|. Fur y(t) = φt,t0y0 = eaty0 undz(t) = φt,t0z0 = eatz0 gilt |y(t)− z(t)| = eat |y0 − z0|. Fur a > 0 ist der Satz scharf. Fur a < 0gilt dies jedoch nicht, da fur |y(t)− z(t)| = eat |y0 − z(0)| e−Lt |y0 − z0|.

Eine solche Situation kann mit einer”einseitigen Lipschitzbedingung“ beschrieben werden.

f(y)− f(z)

y − z≤ α ∀y, z ∈ I y 6= z (2.13a)

f darf beliebig fallen, aber nur mit Anstieg α wachsen. Falls α = 0, ist f monoton fallend.Aquivalent dazu ist

[f(y)− f(z)](y − z) ≤ α(y − z)2 (2.13b)

Diese Definition ist auch fur Rn sinnvoll:

〈f(y)− f(z), y − z〉 ≤ α‖y − z‖22 (2.13c)

Satz 2.8. f erfulle die einseitige Lipschitzbedingung aus Formel 2.13c mit α ∈ R, dann gilt furdie entsprechenden Losungen

‖y(t)− z(t)‖ ≤ eα(t−t0)‖y0 − z0‖2 (2.14)

Beweis. Wir zeigen durch differenzieren dass die Funktion

e−α(t−t0)‖y(t)− z(t)‖2

monoton fallend ist:

d

dt

e−2α(t−t0)‖y(t)− z(t)‖22

= −2αe−2α(t−t0)‖y(t)− z(t)‖22 + e−2α(t−t0)2 〈 y′(t)− z′(t)︸ ︷︷ ︸

f(t,y(t))−f(t,z(t))

, y(t)− z(t)〉

≤ −2αe−2α(t−t0)‖y(t)− z(t)‖22 + e−2α(t−t0)2α ‖y(t)− z(t)‖22= 0

9

Fur α < 0 gilt

‖y(t)− z(t)‖ ≤ e−|α|(t−t0)‖y0 − z0‖, (2.15)

das heißt Differenzen in Anfangswerten fallen exponentiell.

Definition 2.9 (Stabilitat einer DGL). Eine Differentialgleichung heißt stabil, wenn

supt>t0‖y(t)− z(t)‖ ≤ c‖y0 − z0‖ (2.16)

Definition 2.10 (asymptotische Stabilitat einer DGL). Eine Differentialgleichung heißt asym-ptotisch stabil, wenn

limt→∞‖y(t)− z(t)‖ = 0 (2.17)

Falls eine Differentialgleichung nicht stabil ist, ist sie instabil.

Definition 2.11 (steife DGL). Eine DGL heißt steif, wenn die einseitige Lipschitzbedingungeine wesentlich bessere Abschatzung liefert als die ubliche Lipschitzbedingung.

Speziell gilt das fur implizite Methoden.

3 Verfahren fur Anfangswertprobleme-Einschrittverfahren

Einschrittverfahren sind Verfahren zur numerischen Losung von Anfangswertproblemen, alsoy′(t) = f(t, y(t)) und y(t0) = y0. Wir wahlen Gitterpunkte t0 < t1 < · · · < tn = T , dieIntervalllange betragt hj = tj+1 = tj . Man kann gleichmaßig unterteilen, wobei h = T−t0

n undtj = t0 + jh.Man kann auch die Ableitung y′ durch einen rechtsseitigen Differenzenquotienten ersetzen, d.h.

y′(tj) ≈y(tj+1)− y(tj)

hj≈ f(tj , y(tj))

y(tj+1) = y(tj) + hf(tj , y(tj))

3.1 Explizites Eulerverfahren

Das fuhrt zum expliziten Euler-Verfahren mit

y0 = y0 (3.1a)

yj+1 = yj + hf(tj , y(tj)) ∀j = 0, 1, . . . , n− 1 (3.1b)

Somit erhalten wir eine explizite Vorschrift zur Berechnung der yj .

3.2 Implizites Eulerverfahren

Wir verwenden den linksseitigen Differentenquotienten

y′(tj+1) ≈ y(tj+1)− y(tj)

hj≈ f(tj+1, y(tj+1))

Im impliziten Eulerverfahren mussen wir ein Gleichungssystem losen

yj+1 = yj + hf(tj+1, yj+1) (3.2)

I.A. muss die Unbekannte yj durch Losen eines nichtlinearen Gleichungssystems gefunden wer-den. Ein geeigneter Startwert fur das Newtonverfahren ist z.B. das yj , da sich die Losung furkleine h nur wenig andern wird.

10

Beispiel 3.1. Wir betrachten eine DGL mit dem expliziten und impliziten Eulerverfahreny(0) = y0 und y′ = ay. Die Losung ist y(t) = y0e

at. Im expliziten Eulerverfahren gilt mith = T

n

yj+1 = yj + hayj = (1 + ah)yj

yj = (1 + ah)jy0

yn = y0(1 + ha)n = y0

(1 +

aT

n

)nn→∞→ y0e

at

Falls a < 0 ist das Problem steif. Fur h > 2|a| , also (1 + ha) < −1 oszilliert die numerische

Losung (wir werden spater anhand der Stabilitatsanalyse des expliziten Euler sehen, dass wirdann nicht im Stabilitatsbereich des Verfahrens liegen). Erst fur |ha| < 1 gibt es keine kunstlicheOszillation. Wir wenden nun das implizite Eulerverfahren an:

yj+1 = yj + hayj+1

yj+1 =1

1− hayj =

1

(1− ha)jy0

Dieses Verfahren ist nicht fur alle h durchfuhrbar, jedoch fur hinreichend kleines durchfuhrbar.Fur a < 0 gilt |yj+1| < |yj |.

3.3 Verfahren basierend auf numerischer Integration

Wir betrachten das Intervall [tj , tj+1] und y(tj) = yj und y′(t) = f(t, y(t)) mit t ∈ [tj , tj+1].Dies lasst sich als aquivalente Integralgleichung formulieren:

y(t) = yj +

∫ t

tj

f(s, y(s))ds ∀t ∈ [tj , tj+1] (3.3)

Speziell gilt dies fur t = tj+1. Wir verwenden nun numerische Integration, wie z.B. die linksseitigeRechtecksregel ∫ b

af(s)ds ≈ (b− a)f(a) (3.4)

Somit gilt y(tj+1) ≈ yj+hf(tj , yj), was eine alternative Methode fur das explizite Eulerverfahrendarstellt. Fur die rechtsseitige Rechtecksregel y(tj+1) ≈ yj + hf(tj+1, y(tj+1)) erhalt man dasimplizite Eulerverfahren.Verwendet man die Trapezregel, so gilt∫ b

af(s)ds ≈ b− a

2(f(a)− f(b)) (3.5)

implizite Trapezmethode: Diese Uberlegung fuhrt zur impliziten Trapezmethode

y(tj+1) ≈ yj +h

2(f(tj , yj) + f(tj+1, yj+1)) (3.6a)

y(tj+1) := yj +h

2(f(tj , yj) + f(tj+1, yj+1)) (3.6b)

Lost man dieses Gleichungssystem, so ist dies genauer als die Eulerverfahren.

11

Abbildung 6: Illustration der Trapezregel

Explizite Trapezmethode: Bei der expliziten Trapezmethode bestimmt man sich zuerst eineNaherung yj+1 mit dem expliziten Eulerverfahren und iteriert dann

yj+1 = yj + hf(tj , yj) (3.7a)

yj+1 = yj +h

2[f(tj , yj) + f(tj+1, yj+1)] (3.7b)

Es gilt fur die Mittelpunktsregel der numerischen Integration:

∫ b

af(s)ds ≈ (b− a)f

(a+ b

2

)y(tj+1) ≈ yj + hf(tj+ 1

2, y(tj+ 1

2))

Das Verfahren benotigt Naherungen fur y(tj+ 12), dieses kann wieder mit dem expliziten Euler-

verfahren bestimmt werden.

verbessertes Eulerverfahren: Dies fuhrt zur expliziten Mittelpunktsmethode, die auch ver-bessertes Eulerverfahren genannt wird:

yj+ 12

= yj +h

2f(tj , yj) (3.8a)

yj+1 = yj + hf(tj+ 12, yj+ 1

2) (3.8b)

3.4 Allgemeines zu Einschrittverfahren

Das yj+1 wird aus yj bestimmt. Alle vorherigen Schritte werden von den Einschrittverfahrenignoriert. Dies fuhrt zur diskreten Evolution:

Definition 3.2 (Diskrete Evolution). Die Anfangswerte seien (tj , yj), so erhalt man yk zumZeitpunkt tk k ≥ j durch k− j Schritte des Verfahrens, dann sei die diskrete Evolution gegebendurch

ψtk,tj (yj) = yk (3.9)

Ein Schritt wird oft uber die Inkrementfunktion dargestellt

ψtj+1,tj (yj) = yj + hψ(tj , yj , h) (3.10)

12

Bei expliziten Verfahren kann die Inkrementfunktion explizit angegeben werden. So ist diese z.B.beim expliziten Eulerverfahren durch ψ(tj , yj , h) = f(tj , yj), beim verbesserten Eulerverfahrenψ(tj , yj , h) = f(tj+ 1

2, yj + h

2f(tj , yj)).

4 Fehleranalysis

Ziel: Man will eine Abschatzung des Diskretisierungsfehlers

ej = y(tj)− yj (4.1)

Das Verfahren habe Konvergenzordnung p, falls der Fehler der Norm ‖ej‖ = O(hp). Die Analysisbesteht aus 2 Teilen:

1. Abschatzen des Konsistenzfehlers (=lokaler Abschneidefehler)

δj = φtj+1,tj (y(tj))− ψtj+1,tj (y(tj)) (4.2)

Hierbei ist die Evolution φ die exakte Losung der DGL mit Anfangsbedingung, und ψ der1. Schritt des numerischen Verfahrens.

2. Stabilitat der diskreten Evolution

‖ψtj ,tk(yk)− ψtj ,tk(zk)‖ ≤ Ctj ,tkstab ‖yk − zk‖ (4.3)

Eine kleine Merkregel zum Anfang: Stabilitat und Konsistenz impliziert Konvergenz!

Satz 4.1 (Konvergenz). Es gilt

‖ej‖ ≤j−1∑k=0

‖δk‖Ctj ,tkstab (4.4)

Abbildung 7: Diskrete Hilfspfade des Satzes 4.1

Beweis. Wir starten von jedem exakten Losungspunkt numerische Verfahren und erhalten da-durch numerische

”Hilfspfade“. Neben dem diskreten Losungspfad yj = ψtj ,t0(y0) definieren wir

diskrete Hilfspfade

ykj = ψtj ,tk(y(tk)) (4.5)

13

Es gilt yj = y0j und yjj = y(tj). Nun konnen wir mittels einer Teleskopsumme und der Dreiecks-

ungleichung folgende Umformung machen:

‖y(tj)− yj‖ = ‖yjj − y0j ‖ = ‖

j−1∑k=0

(yk+1j − ykj )‖ ≤

j−1∑k=0

‖yk+1j − ykj ‖ (4.6)

Mit der diskreten Evolution ψ und der stetigen Evolution φ gilt

yk+1j − ykj = ψtj ,tk+1(y(tk+1))− ψtj ,tk(y(tk)) = ψtj ,tk+1(φtk+1,tk (y(tk)))− ψtj ,tk+1(ψtk+1,tk(y(tk)))

(4.7)

Hier verwendet man die Stabilitat und Konsistenz der diskreten Evolution

‖yk+1j − ykj ‖ ≤ C

tj ,tk+1

stab ‖φtk+1,tk (yk)− ψtk+1,tk(y(tk))‖ ≤ Ctj ,tk+1

stab ‖δk‖ (4.8)

5 Stabilitat der Verfahren

Abbildung 8: Konsistenzfehler

Man nennt δi den Konsistenzfehler, wobei δi = O(hp+1) Die Stabilitat betragt

‖ψtj ,tn(yh)− ψtj ,tn(zh)‖ ≤ ‖yh − zh‖ (5.1)

5.1 Konsistenzfehlerabschatzung beim expliziten Eulerverfahren

Wie bereits aus Formel 4.2 ersichtlich, gilt δj = φtj+1,tj (y(tj))−ψtj+1,tj (y(tj)). Wir wenden nuneine Taylor-Entwicklung auf den kontinuierlichen Fluss φt,tjy an. Es gilt:

y′(t) = f(t, y(t))

φtj+1,tjy ≈ y(tj+1) = y(tj + h) = y(tj)+hy′(tj) +O(h2) = y(tj) + hf(tj , yj) +O(h2)

Betrachtet man das explizite Euler-Verfahren in einem Schritt mit den Anfangsdaten (tj , y(tj)),so erhalt man

ψtj+1,tjy = yj+1 = y(tj) + hf(tj , y(tj))

14

Setzt man fur den Konsistenzfehler die Taylor-Approximation von φtj+1,tjy und ein, so gilt lautder Definition von δj

δj = φtj+1,tjy − ψtj+1,tjy = y(tj) + hf(tj , yj) +O(h2)− (y(tj) + hf(tj , yj)) = O(h2) (5.2)

5.2 Konsistenzfehler beim verbesserten Euler-Verfahren

Als nachstes Beispiel zur Berechnung des Konsistenzfehlers betrachten wir das verbesserte Euler-Verfahren. Es gilt mittels g := y′(t) = f(t, y(t)) = f(~h(t)) und ~h(t) := (t, y(t)) und p(t) =(g h)(t) mittels der Kettenregel:

y′(t) = f(t, y(t))

y′′(t) =d

dtf(t, y(t)) = 〈~∇hg(~h(t)), ∂t~h(t)〉 = ∂tf · 1 + ∂yf · ∂ty(t) = ft · 1 + fyf(t, y(t))

Somit gilt in Kurzschreibweise y′′(t) = ft + fy · f . Wendet man nun die Taylor-Entwicklung aufy(tj + h) an, so erhalt man mittels der obigen Zwischenresultate:

φtj+1,tjy = y(tj + h) ≈ y(tj) + hy′(tj) +h2

2y′′(tj) +O(h3) = y(Tj) + hf +

h2

2(ft + fyf) +O(h3)

Fur den diskreten Fluss muss man beide Schritte betrachten. Es gilt mittels der Inkrementfunk-tion ψ

yj+1 = yj + hψ(tj , yj , h)

ψ(tj , yj , h) = ψ(h) = f

(tj +

h

2, y(tj) +

h

2f(tj , y(tj))

)Wir entwickeln nun ψ(h) mittels Taylor bei h = 0:

ψ(h) =1

2ft +

1

2fyf

ψ(h) = ψ(0) + hψ′(0) +O(h2) = f +h

2ft +

h

2fyf +O(h2)

Damit ist der Konsistenzfehler des verbesserten Eulerverfahrens folgendermaßen gegeben:

yj+1 = yj + hψ(h) ≈ yj+hf +h2

2ft +

h2

2fyf +O(h3)

y(tj+1)− yj+1 = O(h3)

5.3 Stabilitat des Eulerverfahrens

Wir nehmen an, dass f(t, y(t)) lipschitzstetig im 2. Argument ist, d.h.

‖f(t, y)− f(t, z)‖ ≤ L‖y − z‖ ∀t ≥ t0 ∀y, z ∈ Rd (5.3)

15

Dann gilt:

‖ψtj+1,tj (yj)− ψtj+1,tj (zj)‖ ≤ ‖yj + hf(tj , yj)− (zj + hf(tj , zj))‖≤ ‖yj − zj‖ + h‖f(tj , yj)− f(tj , zj)‖≤ ‖yj − zj‖ + hL‖yj − zj‖= (1 + hL)‖yj − zj‖

Mit 1 + hL ≤ ehL erhalt man rekursiv

‖ψtk,tj (yj)− ψtk,tj (zj)‖ ≤k−j−1∏i=0

eL(tk−i−tk−i−1)‖yj − zj‖ ≤ eL(tk−tj)‖yj − zj‖

Somit gilt

Ctk,tjstab = eL(tk−tj) (5.4)

5.4 Konvergenz des expliziten Eulerverfahrens

Wir sehen an diesem Beispiel die Merkregel”Stabilitat+Konsistenz=Konvergenz“ vorgefuhrt.

Satz 5.1 (Konvergenz expliziter Euler). Die Konsistenzordnung des expliziten Euler-Verfahrensist von der Ordnung 1, d.h. ‖ej‖ = O(h).

Beweis. Wir wissen aus Formel 5.2, dass ‖δj‖ = O(h2). Somit gilt:

‖ej‖ ≤j−1∑k=0

Ctj ,tkstab ‖δk‖

5.4≤

j−1∑k=0

eL(tj−tk)‖δk‖

≤ eL(tj−t0)j−1∑k=0

‖δk‖︸ ︷︷ ︸O( 1

h)·O(h2)

= O(h)

Durch die Summation ging eine Ordnung der Konsistenz in h verloren. Dies fuhrt zu folgendemBegriff:

Definition 5.2 (Konsistenzordnung). Man spricht von Konsistenzordnung p, falls

‖δk‖ = O(hp+1) (5.5)

ist. Dies impliziert bei Stabilitat Konvergenzordnung p.

16

6 Runge-Kutta-Verfahren

6.1 Allgemeines

Die Runge-Kutta-Verfahren bilden eine sehr allgemeine Klasse von Einschrittverfahren. Aus-gangspunkt ist die Integralgleichung

y(tj+1) = y(tj) +

∫ tj+1

tj

f(s, y(s))ds

Wir konnen nun verschiedene numerische Quadraturverfahren zur Berechnung des Integralsverwenden, namlich insbesondere mit normierten Stutzstellen cj ∈ [0, 1] und normierten Inte-grationsgewichten bj fur j = 1, . . . , s. Somit gilt

y(tj+1) = y(tj) + h

s∑l=1

blf(tj + clh, y(tj + clh)) (6.1)

Da jedoch y(tj+clh) ebenfalls unbekannt ist, muss auch dieser Term nochmals durch numerischeIntegration angenahert werden:

y(tj + cih) = y(tj) +

∫ tj+cih

tj

f(s, y(s))ds ≈ y(tj) + hs∑l=1

ailf(tj + clh, y(tj + clh)) (6.2)

Die ail sind somit normierte Gewichte zur numerischen Berechnung von

∫ ci

0f(x)dx ≈

s∑l=1

ailf(cl)

Die Stutzstellen cl sind vorgegeben und konnen auch außerhalb des Intervalls [0, ci] liegen.

6.2 Das Runge-Kutta-Verfahren

Es gilt fur das Runge-Kutta-Verfahren:

yj,i = yj + hs∑l=1

ail f(tj + clh, yj,l)︸ ︷︷ ︸kl

i = 1, . . . , s (6.3)

yj+1 = yj + h

s∑l=1

blf(tj + clh, yi,l) = yj + h

s∑i=1

biki (6.4)

ki : = f(tj + cih, yj + h

s∑l=1

ailkl) (6.5)

Man verwendet nun Autonomisierung: Bei der Analysis vom verbesserten Eulerverfahrens tretenaufgrund der Kettenregel partielle Ableitungen auf. Bei Taylorentwicklungen hoherer Ordnun-gen entstehen sehr viele Terme. Wir konnen uns jedoch auf autonome DGlen beschranken, daeine nichtautonome DGl folgendermaßen umgeschrieben werden kann. Die DGL

y′(t) = f(t, y(t)) (6.6a)

y(t0) = y0 (6.6b)

17

kann durch die Erweiterung in eine autonome DGL umformuliert werden:

Y (t) =

(y(t)ty(t)

)(6.7)

Y ′ = F (Y ) =

(f(ty, y)

1

)(6.8)

Es gilt tY (t) = t als Losung von t′Y (t) = 1 und tY (t0) = t0.

Lemma 6.1. Falls das Runge-Kutta-Verfahren ci :=∑s

l=1 ail ∀i = 1, . . . , s erfullt, dann liefertes fur die Nichtautonome DGl und die autonomisierte DGl aquivalente numerische Ergebnisse.

Beweis. Es gilt fur alle Zwischenstufen tY = t, da

tyj,i = tyj + h

s∑l=1

ail1︸ ︷︷ ︸ci

= tyj + hci (6.9)

Wir beschranken uns daher im Folgenden auf autonomisierbare Runge-Kutta-Verfahren, d.h.wir setzen ci =

∑sl=1 ail voraus.

Wir brauchen zunachst die multivariate Taylorentwicklung. Es sei f ∈ Cn(Rd,Rm), die k-teAbleitung ergibt in der Tayorentwicklung einen Tensor k-ter Stufe. Anwendung von f (k) auf dieVektoren h1, . . . , hk ∈ Rd und es gilt mit k ≤ n:

fk(x) : Rd × · · · × Rd︸ ︷︷ ︸∏ki=1 Rd

→ Rm

f (k)(x)(h1, . . . , hk) =

d∑i1=1

· · ·d∑

ik=1

∂kf

∂xi1 . . . ∂xikh1,i1 . . . hk,ik (6.10)

Mittels der Taylorformel fur f ∈ Cp+1(Rd,Rm) und x ∈ Rd gilt mittels Restgliedabschatzung

f(x+ h) =

p∑n=0

1

n!f (n)(x)(h1, h2, . . . , hd) +O(‖h‖p+1) (6.11)

Wir verwenden nun die folgenden Abkurzungen f (n)(h1, . . . , hn) = f (n)(x)(h1, . . . , hd). Die Ord-nungebedingungen fur das Runge-Kutta-Verfahren mittels Taylor fur y(t+ h) lauten:

y′(t) = f(y(t)) (6.12a)

y′′(t) = f ′(y(t))y′(t) = f ′yf = f ′yf (6.12b)

y′′′(t) = f ′′y (y′, f) + f ′f ′y′ = f ′′(f, f) + f ′f ′f (6.12c)

yIV (t) = f ′′′(f, f, f) + 3f ′′(f ′f, f) + f ′(f ′′(f, f)) + f ′f ′f ′f (6.12d)

Bei der n-ten Ableitung hat man eine n-lineare Abbildung.

18

Es gilt wieder

y(t+ h) = y(t) + hf +h2

2f ′f +

h3

6[f ′′(f, f) + f ′f ′f ] +

h4

24yIV +O(h5) (6.13)

Die Terme f, f ′′(f ′(t), f) heißen elementare Differentiale. Nun zu einer Taylorentwicklung furdie Runge-Kutta-Methode

ki = f

(yj + h

s∑l=1

ailkl

)(6.14)

yj+1 = yj + hs∑l=1

hlkl (6.15)

Wir verwenden nun eine”bootstrap“-Technik, diese funktioniert auch bei nichtlinearen Funk-

tionen mit hinreichender Differenzierbarkeit, wie man sich mittels Taylorreihe leicht uberlegenkann (f(x+O(h)) = f(x) + c · hf ′(x) +O(h2) = f(x) +O(h) etc.).

ki = f(yj +O(h)) = f(yj) +O(h) (6.16)

Wir setzen ein

ki = f(yj + h∑l

ail(f(yi +O(h))))

= f(yj + h∑l

ailf(yj)) +O(h2)

= f(yj) + f ′(yj)(h∑

ailf(yi)) +O(h2)

= f(yj) + h∑l

ail︸ ︷︷ ︸ci

f ′f +O(h2)

= f(yj + h∑l

ail(f + hclf′f︸ ︷︷ ︸

kl+O(h2)

)) +O(h3)

= f(yj) + f ′yj (h∑l

ail(f + hclf′f))

+1

2f ′′(h

∑l

ail(f + hhclf′f), h

∑l

ail(f + hclf′f)) +O(h3)

= f(yj) + hcif′f + h2

[∑l

ailf′f ′f +

1

2c2i f′′(f, f)

]+O(h3)

Somit gilt

ki = f + hcif′f + h2

[∑l

ailclf′f ′f +

1

2c2i f′′(f, f)

]

+ h3[∑l,m

ailalmL−mf ′f ′f ′f +1

2

∑l

ailc2l f′f ′′(f, f)

+∑l

ciailclf′′(f ′f, f) +

1

6c3i f′′′(f, f, f)] +O(h4)

19

Es gilt

yi+1 = yj +s∑i=1

hbihi (6.17)

= yj +∑i

bif + h2∑

bicif′f + h3[...] + h4[...] +O(h5) (6.18)

h-Ordnung elem. Differential Bedingung

p=1 f∑bi = 1

p=2 f ′f∑bici = 1

2

p=3 f ′′(f, f)∑bic

2i = 1

3

p=3 f ′f ′f∑

il biailcl = 16

p=4 f ′′′(f, f, f)∑bic

3i = 1

4

p=4 f ′′(f ′f, f)∑

il biailcl = 18

p=4 f ′f ′′(f, f)∑

il biailc2i = 1

12

p=4 f ′f ′f ′f∑

i,l,m biailalmcm = 124

Suchen wir explizite, autonomisierbare Verfahren, so haben wir s(s−1)2 Parameter fur strikte

untere Dreiecksmatrizen A und s Parameter fur b. Die c-Parameter sind festgelegt mit ci =∑sl=1 ail.

Zur Beschreibung der Runge-Kutta-Verfahren eignen sich besonders so genannte Butcher-Tableaus,welche die aij , die bj sowie die cj mittels einer Matrix A ∈ Rs×s, und zwei Vektoren b ∈ Rs undc ∈ Rs im Schema von Tabelle 1 beschreibt.

c A

bT

Tabelle 1: Schema des Butchertableau

0 0

b1 = 1

Tabelle 2: Butchertableau fur p = 1 und s = 1

Es gilt c2 = a21 b1 + b2 = 1 und∑bici = c2b2 = 1

2 . Es gelten 2 Gleichungen fur 3 Unbekannte,das ergibt eine dreiparametrige Losungschar. So erhalt man fur c2 = 1 und b1 = b2 = 1

2 , wasdie explizite Trapezmethode ergibt, fur c2 = 1

2 und b1 = 0, b2 = 1 erhalt man das verbesserteEuler-VerfahrenWir haben somit in Tabelle 4 4 Gleichungen mit 6 Unbekannten. Das klassische Runge-Kutta-Verfahren (siehe Tabelle 5) verwendet p = 4, s = 4, c, b kommen aus der Simpson-Regel

∫ b

af(x)dx ≈ b− a

6[f(a) + 4f(

a+ b

2) + f(b)] (6.19)

6.3 Wurzelbaume

Aufstellen und Losen der Ordnungsbedingungen ist technisch aufwendig. Um dies mit Compu-teralgebra durchzufuhren, hat sich der Formalismus der Wurzelbaume durchgesetzt.Ein elementares Differential wird durch

20

0 0 0c2 = a21 a21 0

b1 b2

Tabelle 3: Fur s = 2 und p = 2 ergibt sich das obige Butcher-Tableau

0 0 0 0c2 = a21 a21 0 0

c3 = a31 + a22 a21 a32 0

b1 b2 b3

Tabelle 4: Butcher-Tableau fur s = 3 und p = 3

1. ungeordnete Tupel β

2. durch Raume reprasentiert

Die Funktion selbst entspricht dem leeren Tupel f ≡ β = ∅. Die n-te Ableitung, angewandt aufdie durch β1, . . . , βn dargestellten Differentiale entspricht dem Tupel [β1, . . . , βn]

f (n)(Diff1, . . . ,Diffn) ≡ β = [β1, . . . , βn] (6.20)

Beispiel 6.2. f (2)(f ′(f), f) ≡ β = [[],] oder f (3)(f ′′(f ′(f), f), f ′(f), f) ≡ β = [[[],], [], []].

Man kommt so zu einer Darstellung uber Wurzelbaume (siehe Abbildung 9). Die Blatter imWurzelbaum entsprechen f , die Knoten den f (n)(...) und die Wurzel entspricht dem elementarenDifferential.Die Ordnung von β (i.Z. #β) ist #β = 1 fur β = , d.h. f .

Definition 6.3 (Ordnung eines Wurzelbaums). Fur die Ordnung gilt rekursiv #β = 1 + #β1 +· · ·+ #βn.

Definition 6.4 (Faktorielle eines Wurzelbaums). Fur ein ungeordnetes Tupel [β1, . . . βn] ist dieFakultat β: β! = 1 fur β = , sowie β! = #β · (β1!) . . . (βn!) fur β = [β1, . . . , βn].

Aβ ist eine Matrix, (Aβ)i = 1 fur β = . (Aβ)i = (AAβ1)i . . . (AAβn)i

Satz 6.5 (Butcher). Ein autonomisierbares Runge-Kutta-Verfahren ist konsistent von Ordnungp genau dann wenn

bTAβ =1

β!(6.21)

fur alle Wurzelbaume β der Ordnung ≤ p erfullt ist.

Beweis. Siehe [2, Satz 4.24/S.160]

Satz 6.6 (Konsistenzfehler von impliziten Runge-Kutta-Methoden). Es gelte r ≤ 2s:

s∑i=1

bick−1i =

1

kk = 1, . . . , r (6.22)

s∑i=1

ajick−1i =

ckjk

k = 1, . . . , s (6.23)

Dann ist das Runge-Kutta-Verfahren von der Ordnung r

21

0 0 0 0 012

12 0 0 0

12 0 1

2 0 01 0 0 1 0

16

13

13

16

Tabelle 5: Das Butcher-Tableau fur das klassische vierstufige RK-Verfahren s = 4 und p = 4.

Beweis. Beweis spater bzw. [2, Lemma 6.37/S.270]. Der Beweis wird motiviert durch die nu-merische Integration ∫ b

af(s)ds ≈

s∑i=1

bif(ci) (6.24)∫ 1

0xk−1dx =

1

k

!=∑i

bick−1i k = 1, . . . , r (6.25)

d.h. die Integrationsformel ist exakt fur Monome bis Ordnung r = 1 und∫ ci

0f(s)ds ≈

s∑i=1

ajif(ci) (6.26)

∫ cj

0xk−1 =

ckjk

!=

s∑j=1

ajick−1i k = 1, . . . s (6.27)

Optimal hierfur ware die Gauß-Integrationsformel (c, b), dann ware r = 2s. Gauß-Integrationin einem Punkt ist genau die Mittelpunktsmethode

12

12

1

Tabelle 6: Gauß-Integration der Stufe 1, diese ist die Mittelpunktsregel.

7 Automatische Schrittweitensteuerung

Idee: Es gibt eine Vorgabe ε, so dass

|y(T )− yn| ≤ ε(T − t0) (7.1)

Finde hj , sodass die Fehlerschranke erfullt ist, aber sie soll auch nicht viel besser sein (wegenEffizienz!). Bisher haben wir a priori-Fehlerabschatzung betrieben.

‖ej‖ ≤∑k

‖δk‖Ctj ,tj+1

stab (7.2)

‖ej‖ ≤ C(f)hp (7.3)

Die Konstante hangt von f ab, z.B. ‖fn+1‖∞. Diese Methode ist gut fur asymptotische Feh-lerabschatzungen. Nun machen wir Fehlerabschatzungen a posteriori. Wir starten nun exakteEvolutionen von den numerischen Pfaden.

22

Abbildung 9: Wurzelbaume mit elementaren Differenzialen aus [2, S. 158]

‖ej‖ ≤j∑

k=1

‖δk‖Ctj ,tj+1

stab

23

Es geht nun darum die lokalen Fehler wirklich abzuschatzen. Der Fehler ‖ej‖ kann damit (grob)abgeschatzt werden. Um Gesamtfehler ε(T − t0) zu erhalten, soll in jedem Schritt ein Fehlervon εh gemacht werden. Man muss sich die Kondition des Ausgangsproblems immer uberlegen.Wir nehmen an, dass die Stabilitatskonstante gut, z.B. 1 ist, z.B. aus der einseitigen Lipschitz-Bedingung.2 Moglichkeiten δj zu schatzen

1. h-Verfeinerung (rechne gleichzeitig auch mit halber Schrittweite)

yj+1 = ψtj+h,tjy(j)

yj+1 = ψtj+h,tj+h2ψtj+

h2,tjy(j)

2. Erhohung von p

ad Verfeinerung von h: Die Konsistenzordnung der Verfahren muss bekannt sein:

φtj+h,tj (yj)− yj+1 = c(tj)hp+1 +O(hp+2)

φtj+h,tj (yj)− yj + 1 = 2c(tj)

(h

2

)p+1

+O(hp+2)

δ = φtj+h,tj (yj)− ˆyj+1 =1

2p − 1(yj+1 − yj)︸ ︷︷ ︸

Fehlerschatzer

+O(hp+2)

ad Erhohung von p: Verwende 2 RK-Verfahren hoherer Ordnung

yj+1 = ψtj+h,tj (yj) Ordnung p

yj+1 = ψtj+h,tj (yj) Ordnung p+1

δ = φtj+h,tj (yj)− yj+1 ≈ yj+1 − yj

Billig berechenbar wird dies durch eingebettete RK-Methoden. Gleiche A und c, unterschiedlicheb (z.B. Dormand-Prince 4 und 5):

c A

b1b2

Der Fehler wird vom schlechteren Verfahren geschatzt. Besser ist es mit dem genaueren Verfah-ren ψ weiterzurechnen.

Schrittweitensteuerung: Es gilt h = hj , man schatzt den Fehler s(h) aus dem letzten Schrittmit einer der beiden Methoden. Falls

s(h)

εh≤ 1 (7.4)

ist der Schritt OK, sonst bleibt man bei tj stehen und wiederholt den Schritt ab tj mit kleinerem

hj . Das Ziel: s(hneu)εhneu

= 1, d.h. der Fehler soll optimal sein. Wir mussen die Konvergenzordnungdes Verfahrens kennen

s(h) ≈ chp+1 (7.5)

c ≈ s(h)

hp+1(7.6)

24

Wir wissen auch s(hneu) ≈ chp+1neu . Daraus folgt

hneu = h p

√hε

s(h)(7.7)

In der Fehleranalysis wollten wir zuerst einen kleinen Konsistenzfehler haben und sind mitTaylorentwicklung lokal bei der Losung geblieben, nun wollen wir die Stabilitat untersuchen.

8 Stabilitat von Runge-Kutta-Verfahren

Wir werden 2 Techniken betrachten, die Stabilitatsfunktion (funktioniert fur lineare DGL mitkonstanten Koeffizienten) und im 2. Teil betrachten wir auch nichtlineare DGL, die asymptotischstabil sind.

8.1 Lineare DGL mit konstanten Koeffizienten

Wir betrachten y′ = Ay mit y(0) = y0. Wir sind am Fortpflanzen des Fehlers in der Anfangsbe-dingung interessiert. Wir haben y′ = Ay+ f(t) und y(0) = 0 und z′ = Az+ f(t) und z(0) = z0.Fur den Fehler e(t) = z(t)− y(t) gilt

e′(t) = Ae (8.1)

e(0) = y0 − z0 = e0 (8.2)

Daher mussen wir nur das homogene System betrachten. Wir nehmen an A sei diagonalisierbar,d.h. A = T−1ΛT mit Λ = diag(ti). Wir machen eine Variablentransformation

Ty′ = ΛTy (8.3)

Ty(0) = Ty0 (8.4)

y = λy (8.5)

Wir erhalten dadurch d skalare entkoppelte DGL y′i = λiyi. Dadurch ergibt sich als Losung

y(t) = T−1y(t) ==

d∑i=1

vieλitT︸ ︷︷ ︸

=:eAt

y0 vi := T−1ei (8.6)

Falls A nicht diagonalisierbar ist, muss man mit Jordan-Blocken arbeiten. Dabei erhalt man einPolynom.

Beispiel 8.1. (y′1y′2

)=

(λ 10 λ

)(y1

y2

)(8.7)

Als Losung ergibt sich (y1

y2

)= a

(eλt

0

)+ b

(teλt

eλt

)(8.8)

25

Aus diesem Beispiel motivieren sich folgende Begriffe: Eine Dgl ist

1. asymptotisch stabil, falls Re(λ) < 0 fur alle Eigenwerte

2. stabil, falls Re(λ) ≤ 0 und Jordanindex 1 fur λ mit Realteil 0

Stabilitat heißt, dass die Differenz e(t) beschrankt ist fur t→∞.

Die Stabilitatsfunktion von Einschrittverfahren

Definition 8.2 (Matrixfunktion). Sei A = T−1ΛT mit Λ = diag(λi). Sei g : C→ C. Dann istdie Matrixfunktion g : Cn×n → Cn×n definiert als g : A→ T−1diag(g(λi))T . Die Matrixfunktionstimmt mit der ublichen Matrixrechnung uberein.

Beispiel 8.3. Sei g(z) =∑p

i=0 aizi ein Polynom, so ist

p∑i=1

aiAi =

p∑i=0

ai(T−1ΛT )i =

p∑i=0

aiT−1ΛiT

= T−1diag(

p∑i=0

aiλij)T = g(A)

Wir wollen nun die diskrete Evolution als Matrixfunktion darstellen.

yj+1 = g(hA)yj (8.9)

g, die Stabilitatsfunktion, kommt hierbei aus den konkreten numerischen Verfahren, A aus derlinearen Differentialgleichung.

Beispiel 8.4 (Explizites Eulerverfahren).

yj+1 = yj + hAyj = (I + hA)yj = g(hA)yj (8.10)

Wobei g(z) = 1 + z

Beispiel 8.5 (Implizites Eulerverfahren).

yj+1 = yj + hAyj+1 (8.11)

yj+1 = (1− hA)−1yj (8.12)

Wobei g(z) = 11−z .

Beispiel 8.6 (Implizite Trapezregel).

yj+1 = yj +h

2(Ayj +Ayj+1) (8.13)

(I − h

2)yj+1 = (1 +

h

2A)yj (8.14)

Wobei

g(z) =1 + z

2

1− z2

(8.15)

.

26

Lemma 8.7. Die Stabilitatsfunktion g eines s-stufigen (impliziten) Runge-Kutta-Verfahren(b, A) ist durch

g(z) = 1 + zbT (I − zA)−1~e (8.16)

gegeben, wobei ~e = (1, . . . , 1)T ∈ Rs. Die rationale Funktion kann eindeutig in der Form

g(z) =P (z)

Q(z)(8.17)

in teilerfremden, durch P (0) = Q(0) = 1 normierten Polynomen P,Q ∈ Ps dargestellt werden

Beweis. Siehe UE5-Bsp20 oder [2, Lemma 6.30/S. 260].

Bei expliziten RK-Verfahren erhalt man ein Polynom als Stabilitatsfunktion, bei implizitenVerfahren erhalt man rationale Funktionen p(z)

q(z) mit p ≤ s und g ≤ s. Die Taylorentwicklung

von g(z) und ez stimmen mindestens bis zur Konsistenzordnung des Verfahrens uberein.

Satz 8.8. Es gilt

‖yj+1‖ ≤ maxλ∈σ(A)

|g(hλ)| ‖yj‖ (8.18)

mit ‖y‖ := ‖Ty‖2Beweis.

‖yj+1‖ = ‖Tyj+1‖2 = ‖Tg(hA)yj‖2 = ‖TT−1diag(hλi)Tyj‖2≤ max

λi∈σ(A)|g(hA)| ‖Tyi‖2

Definition 8.9 (Stabilitatsbereich S eines Einschrittverfahrens). S := z ∈ C : |g(z)| ≤ 1.Falls σ(hA) ⊂ S gilt, dann bleibt die (asymptotische) Stabilitat erhalten (d.h. ‖yj+1‖ ≤ ‖yj‖ ≤· · · ≤ ‖y0‖).

Beispiel 8.10. Die Stabilitat des expliziten Eulerverfahren ist y(z) = 1 + z, dieser ist daherder Einheitskreis um den Mittelpunkt −1. Beim impliziten Eulerverfahren gilt g(z) = 1

1−z , d.h.

alles außer einem Einheitskreis um 1 ist stabil, bei der impliziten Trapezregel gilt g(z) =1+ z

21− z

2,

d.h. alles links von der y-Achse ist stabil.

Definition 8.11 (A-Stabilitat). Ein Verfahren heißt A-stabil, falls

C− = z ∈ C : Re(z) ≤ 0 ⊂ S (8.19)

gilt.

Die linke Halbebene der Eigenwerte von A soll im Stabilitatsbereich liegen.Fur A-stabile Verfahren vererbt sich die (asymptotische) Stabilitat ins Diskrete (unabhangigvon h). Impliziter Euler und implizite Trapezmethode sind A-stabil, der explizite Euler nicht.Daher konnen wir auch mit großeren Schrittweiten mit ersteren rechnen, mit expliziten Eulererst, wenn das Spektrum hA im Einheitskreis um −1 liegt.Was passiert fur hλ → −∞, wobei h fix? Beim impliziten Euler geht die exakte Losung sehrschnell gegen 0, da yj+1 = 1

1−hλyj . Schnell fallende Losungen werden daher qualitativ gut

approximiert. Bei der Trapezmethode gilt yj+1 =1+hλ

2

1−hλ2

yj → −yj . Daher werden schnell fallende

Losungen durch Oszillationen dargestellt, bleiben aber beschrankt.

27

(a) Stabilitatsbereich (blau): Gauß2und Implizite Trapezregel

(b) Stabilitatsbereich: KlassischerRunge-Kutta (blau) und Verfahrenvon Heun (rot)

(c) Stabilitatsbereich (blau):2-stufiges Gauß-Radau-Verfahren

(d) Stabilitatsbereich (blau): Impli-ziter Euler

(e) Stabilitatsbereich (blau): Expli-ziter Euler

(f) Stabilitatsbereich (blau): Ver-besserter Euler

Definition 8.12 (L-Stabilitat). Ein Verfahren heißt L-stabil, falls es A-stabil ist und limz→∞ g(z)→0. Damit werden schnelle Losungen (hλ→ −∞) gedampft.

Schnell fallende Losungen sollen somit auch numerisch eine schnell abfallende Losung ergebenDas Implizite Euler-Verfahren ist somit L-stabil, die Trapezmethode nicht, da der Limes ihrerStabilitatsfunktion gegen -1 geht.

Lemma 8.13. Ist fur ein Runge-Kutta-Verfahren (b, A) die Matrix A regular und der Zeilen-vektor bT identisch mit einer Zeile der Matrix A, so gilt g(∞) = 0.

Beweis. Da A nichtsingular ist, gilt nach Lemma 8.7

g(∞) = limz→∞

1 + zbT (I − zA)−1︸ ︷︷ ︸→ 1zA−1

~e = 1− bTA−1~e

Ist bT die j-te Zeile der Matrix A, so gilt bT = eTj A, wobei ej der j-te Einheitsvektor ist. Dahergilt

g(∞) = 1− eTj AA−1~e = 1− eTj ~e = 0

28

c1

1 b1 b2b1 b2

Tabelle 7: Zum Ubungsbeispiel 16. Besonders gut sind sind diese mit b1 und b2 im Butcher-Schema, aber es gibt eine einparametrige Schar von Losungen.

Ad UE16: Konsistenzordnung 3 kann man erreichen, siehe Tabelle 7.

Lemma 8.14 (Isometrieerhaltung). Sei A schiefsymmetrisch (A = −AT ). Dann gilt fur Losungenvon y′ = Ay Isometrie, d.h. ‖y(t)‖2 = ‖y(t0)‖2

Beweis.

d

dt‖y(t)‖22 =

d

dtyT y = (y′)T y + y(y′)T = (Ay)T y + y(Ay)T = yTAT︸ ︷︷ ︸

−yTA

y + yTAy = 0 (8.20)

Die Evolution φt : y0 → y(t) ist daher eine Isometrie.

Lemma 8.15. Alle Eigenwerte einer schiefsymmetrischen Matrix A ∈ Rd×d sind rein imaginar,eine schiefsymmetrische Matrix ist mit einer unitaren Matrix T (d.h. THT = I) diagonalisier-bar.

Beweis. iA ist hermitesch ((iA)H = iA), d.h. (iA) hat reelle Eigenwerte und ist nach demSpektralsatz unitar diagonalisierbar.

Lemma 8.16. Es sei |g(z)| = 1 ∀z ∈ iR. Dann ist auch die diskrete Evolution eine Isometrie.

Beweis. A = TΛTH mit Λ = diag(λi) λi ∈ iR und T ist unitar. Dann gilt mittels |g(hλi)| = 1:

‖yj+1‖2 = ‖g(hA)yj‖2 = ‖Tdiag(hλi)THyj‖2

= ‖diag(g(hλi))THyj‖2 = ‖THyj‖2 = ‖yj‖2

Bei der Trapezmethode ist z.B. die Stabilitatsfunktion genau 1 auf der imaginaren Achse, d.h. esgilt Isometrieerhaltung. L-Stabilitat (|g(z)| → 0 fur |z| → ∞) und Isometrieerhaltung (|g(z)| =1) schließen sich gegenseitig aus.

8.2 Stabilitat von nichtlinearen Differentialgleichungen

Definition 8.17 (dissipative Differentialgleichung). f : Rd → Rd heißt dissipativ, falls

〈f(y)− f(z), y − z〉 ≤ 0 ∀y, z (8.21)

gilt, d.h. die einseitige Lipschitzbedingung mit α = 0. Dissipative DGL sind stabil.

Es gilt fur dissipative Differentialgleichungen:

d

dt‖y(t)− z(t)‖22 = 2〈f(y)− f(z), y − z〉 ≤ 0⇒ ‖y(t)− z(t)‖2 ≤ ‖y0 − z0‖2 (8.22)

Oft tritt dies bei technischen Systemen auf, dass Energie in Warme dissipiert wird (z.B. imelektrischen Widerstand). Wir suchen nun numerische Verfahren, die diese Eigenschaft erben:

29

Definition 8.18 (B-Stabilitat). Ein Verfahren heißt B-stabil, wenn folgende Eigenschaft gilt(fur f hinreichend glatt und dissipativ, vgl. [2, S. 282]):

‖yj+1 − zj+1‖ ≤ ‖yj − zj‖ (8.23)

Diese Eigenschaft auf lineare Gleichungen angewandt ist genau die A-Stabilitat. Ist ein VerfahrenB-stabil, impliziert dies, dass das Verfahren A-stabil ist.

Beispiel 8.19. Das implizite Eulerverfahren ist B-stabil.

yj+1 = yj + hf(yj+1)

zj+1 = zj + hf(zj+1)

‖yj+1 − zj+1‖ = 〈yj+1 − zj+1, h(f(yj+1) − f(zj+1) + (zj − yj))〉 = 〈yj+1 − zj+1, yj − zj〉 +h〈f(yj+1)− f(zj+1), yj − zj〉 ≤ ‖yj+1 − zj+1‖2‖yj − zj‖2

Die Implizite MP-Regel ist B-stabil

yj+1 = yj + hf

(yj + yj+1

2

)Falls f linear ist, dann ist dies aquivalent zur Trapezmethode:

yj+1 = yj +h

2(f(yj) + f(yj+1))

Die Trapezmethode ist aber NICHT B-stabil.Isometrieerhaltung im nichtlinearen FallFalls 〈f(y)−f(z), y−z〉 = 0 ∀y, z, dann gilt ‖y(t)−z(t)‖2 = ‖y0−z0‖2. Die Isometrieerhaltungwird von der Mittelpunktsmethode geerbt.

‖yj+1 − zj+1‖22 − ‖yj − zj‖22 = 2〈yj + yj+1

2− zj + zj+1

2, f

(yj + yj+1

2

)− f

(zj + zj+1

2

)〉 = 0

Abbildung 10: Zusammenfassung wichtiger Stabilitatskonzepte [2, S. 249]

30

Abbildung 11: Die Ableitung des Kollokationspolynoms ist in den Kollokationspunkten exakt.

8.3 B-stabile Verfahren hoherer Ordnung

Wir interpretieren dazu das Runge-Kutta-Verfahren als Kollokationsverfahren.Bestimme dazu u ∈ Ps Es gelte

u(tj) = yj (8.24a)

u′(tj + cih) = f(u(tj + cih)) i = 1, . . . , s (8.24b)

ψtj+1,tjy = yj+1 = u(tj+1) (8.24c)

Wir behaupten dies ist ein Runge-Kutta-Verfahren, aber nicht jedes Kollokationsverfahren istein RK-Verfahren!

Satz 8.20. Das obige Kollokationsverfahren ist ein RK-Verfahren.

Beweis. Wir sehen u′ ∈ Ps−1. Wir stellen nun u′ als Lagrange-Interpolationspolynom in c1 dar.

u′(tj + θh) =

s∑l=1

u′(tj + clh)Ll(θ) θ ∈ [0, 1) (8.25)

mit Lagrange-Basispolynomen Li(cj) = δij . Damit gilt, unter Ausnutzung von s = tj + hθ undsomit ds = hdθ im 2. Schritt:

u(tj + cih) = u(tj) +

∫ tj+cih

tj

u′(s)ds = yj + h

∫ ci

0u′(tj + θh)dθ

= yj + h

∫ ci

0

s∑l=1

u′(tj + clh)Ll(θ)dθ

= yj + h

s∑l=1

∫ ci

0Ll(θ)dθ︸ ︷︷ ︸ail

u′(tj + clh)︸ ︷︷ ︸=f(u(tj+clh))

= yj + hs∑l=1

ailf(u(tj + cih))

Somit kommt man auf

yj+1 = yj +

∫ tj+1

tj

u′(s)ds = yj + h

s∑l=1

∫ 1

0Ll(θ)dθu

′(t+ clh) = yj + h

s∑l=1

blf(u(tj + hcl))

31

mit bl :=∫ 1

0 Ll(θ)dθ und ail :=∫ ci

0 Ll(θ)dθ. RK-Methoden sind somit Kollokationsverfahren.Wir benotigen die cl, die ail und bl ergeben sich. Gute Wahl: cl als Gauß-Integrationspunkte,diese erhalt man numerisch z.B. durch Losen eines Eigenwertproblems mittels des Satzes vonGolub-Welsh, siehe [1, Satz 6.6/S. 201].

Satz 8.21. Kollokationsmethoden mit Gauß-Integrationspunkten sind B-stabil.

Beweis. Seien yj , zj gegeben. Es gilt u(tj) = yj , u′(tj + cih) = f(u(tj + cih)) und yj+1 = u(tj+1)

und v(tj) = zj , v′(tj + cih) = f(v(tj + cih)) und zj+1 = v(tj+1).

Wir zeigen, dass ‖yj+1 − zj+1‖2 ≤ ‖yj − zj‖2 fur f dissipativ. Wir definieren

q(θ) = ‖u(tj + θh)− v(tj + θh)‖22 ∈ P2s θ ∈ [0, 1]

q(0) = ‖yj − zj‖2, q(1) = ‖yj+1 − zj+1‖2

Es gilt q ∈ P2s Weiters gilt

q′(θ) = 2h〈u′(tj + θh)− v′(tj + θh), u(tj + θh)− v(tj + θh)〉

Fur θ = cj gelten die Kollokationsgleichungen, d.h.

q′(ci) = 2h〈u′(tj + cih)︸ ︷︷ ︸f(u(tj+cih))

− v′(tj + cih)︸ ︷︷ ︸f(v(tj+cih))

, u(tj + cih)− v(tj + cih)〉 ≤ 0

Die letzte Ungleichung gilt fur dissipatives f . Dann gilt

‖yj+1 − zj+1‖22 = q(1) = q(0) +

∫ 1

0q′(θ)dθ

Da q′ ∈ P2s−1 und Gauß-Integration mit s Stutzstellen fur P2s−1 exakt ist, gilt

‖yj+1 − zj+1‖22 = q(0) + h

s∑l=1

bl︸︷︷︸>0

q′(cl)︸ ︷︷ ︸≤0

≤ q(0) = ‖yj − zj‖22

Bemerkung: Gauß-Verfahren sind Verallgemeinerungen von Mittelpunktsmethode. Sie sind auchisometrieerhaltend. Gauß-Radau-Integrationsformeln haben optimale Ordnung 2s− 2 unter derNebenbedingung, dass cs = 1 ist. Diese sind eine Verallgemeinerung vom impliziten Eulerver-fahren und sind ebenfalls B-stabil (und damit auch A-stabil). Sie sind zudem auch L-stabil. DieStutzstellen sind dabei die Nullstellen von Jacobi-Polynomen.

Definition 8.22 (Gauß-Verfahren). Ist eine Quadraturformel∫ 1

0φ(t)dt ≈

s∑i=1

biφ(ci) (8.26)

exakt fur Polynome des hochstmoglichen Grades 2s − 1, so sind die Stutzstellen ci nach derTheorie der Gaußquadratur eindeutig dijenigen der Gauß-Legendre-Quadratur fur die Gewichts-funktion ω ≡ 1 gegeben. Dabei sind

0 < c1 < · · · < cs < 1 (8.27)

die Nullstellen der (auf das Intervall [0, 1] bezogenen) Legendre-Polynome Ps. Fur f ∈ C2s(Ω,Rd)gilt fur ein s-stufiges Gaußverfahren Konsistenzordnung 2s.

32

Definition 8.23 (Radau-Verfahren). Wir sind nun auf der Suche nach einem L-stabilen Ver-fahren, dessen Konsistenzordnung annahernd so gut ist wie das des Gauß-Verfahrens. Wahlenwir cs = 1, so erhalten wir mittels der in Satz 8.20 motivierten Identitaten

aij : =

∫ ci

0Lj(θ)dθ i, j ∈ 1, . . . , s (8.28)

bj : =

∫ 1

0Lj(θ)dθ j ∈ 1, . . . , s (8.29)

und somit

asj =

∫ cs

0Lj(θ)dθ =

∫ 1

0Lj(θ)dθ = bj j ∈ 1, . . . , s (8.30)

wodurch der Vektor bT mit der letzten Zeile der Matrix A identisch ist. Wahlt man nun dierestlichen Stutzstellen c1, . . . , cs−1 so, dass A nichtsingular ist, so gilt nach Lemma 8.13, dassdas Radau-Verfahren L-stabil ist. Die Konsistenzordnung betragt fur f ∈ C2s−1(Ω,Rd) 2s − 1(vgl. dazu [2, S. 279f]).

Lemma 8.24. Gauß-Radau-Kollokationsverfahren sind B-stabil und L-stabil.

Beweis. Siehe UE5-Bsp23 bzw. [2, Satz 6.51/S. 283] fur die B-Stabilitat (Beweis zeigt B-Stabilitat fur Gauß-Verfahren und Gauß-Radau-Verfahren, Gauß-Verfahren sind daher ebenfallsB-stabil) und fur die L-Stabilitat siehe Lemma 8.13, da bei den Radau-Verfahren die letzte Zeileder A-Matrix mit bT ubereinstimmt.

9 Symplektische Verfahren fur Hamiltonische Systeme

Gegeben ist eine Hamilton-Funktion H : Rd × Rd → R, welche ublicherweise die Energie inmechanischen Systemen beschreibt.Gesucht sind p : R→ Rd und q : R→ Rd mit

p′ = −∂H∂q

p(0) = p0 (9.1a)

q′ =∂H

∂pq(0) = q0 (9.1b)

Definition 9.1. H heißt seperabel, falls

H(p, q) = T (q) + V (q) (9.2)

Oft ist H quadratisch

H(p, q) =1

2pTM−1p+

1

2qTKq (9.3)

Beispiel 9.2 (Masse-Feder-Schwinger). Die Hamiltonfunktion der Feder lautet

H(p, q) =1

2mp2 +

k

2q2

Wir konnen auch eine Federkaskade betrachten. Fur jede Masse mi mit Federkonstante ki erhaltman die Auslenkung qi und den Impuls pi der i. Masse mi.

33

T =

d∑i=1

1

2mip2i =

1

2pTM−1p

wobei M =diag(mi). Fur V erhalt man

V (q) =

d∑i=1

ki2

(qi − qi−1)2 =1

2qTKq q0 = 0

Die Matrix K sieht folgendermaßen aus:

K =

k1 + k2 −k2 0−k2 k2 + k3 −k3

0 −k3 k3

(9.4)

Wir nennen M die Massenmatrix und K die Steifigkeitsmatrix. Wir erhalten nun die Hamilton-funktion

H(p, q) =1

2pTM−1p+

1

2qTKq

q′ =∂H

∂p= M−1p

p′ = −∂H∂q

= −Kq

(Kq)i = ki(qi − qi1)− ki+1(qi+1 − qi)

qi − qi−1 beschreibt die Dehnung der Feder i, (Kq)i beschreibt die Kraft aus Masse i.

Abbildung 12: Federausleger aus Beispiel 9.2

Mit einem Verbindungsgraphen kann man dies anschreiben E1 = (A, 1) etc. Der kinetischenEnergie T (p) und der pot. Energie V (q) entspricht mit li als der Lage der Ruhelage der i-tenFeder

T (p) =N∑i=1

1

2mi‖pi‖22

V (q) =

N∑i=1

ki2

(‖qE1,1 − qE2,1‖2 − li)2

34

Beispiel 9.3 (Elastische Strukturen). Wie schwingt ein Pleuel in einem Motor, gesucht ist dieAuslenkung als Funktion von Ort und Zeit und fuhrt auf eine partielle Differentialgleichung.Mittels FEM erhalt man durch Zerlegung des Gebiets und man erhalt eine pot. und kinetischeEnergie ahnlich zum Pendel.

Wir betrachten wieder quadratische Hamiltonische Systeme mut K,M SPD und p′ = −Kq undq′ = M−1p. Wichtig ist, dass man K und M simultan diagonalisieren kann.

Lemma 9.4 (Simultane Diagonalisierung). M sei SPD und K symmetrisch. Dann existierteine Basistransformation T (Achtung: T T heißt einfach T transponiert!), so dass

T TMT = I (9.5)

T TKT = K = diag(ki) (9.6)

Falls K SPD, dann ist ki > 0.

Beweis. Wir machen eine Cholesky-Zerlegung M = LLT . Somit gilt L−1K(L−1)T ist sym-metrisch, somit ist diese Matrix nach dem Spektralsatz diagonalisierbar. Wir fuhren nun dieSchreibweise L−T := (L−1)T ein.

L−1KL−T = T KT T (9.7)

mit T orthogonal, K diagonal. Mit T := L−T T gilt T TKT = T TL−1KL−T T = T T (T KT T )T =K, da T orthogonal.Es gilt auch T TMT = TL−1(LLT )L−T T = T T T = I.

Wir fuhren nun mit diesen T eine Basistrafo durch: q = T q und p = T−T p = (T−1)T p. Dannfolgt p′ = T−T p′ = −KTq und somit p = −T TKTq = −Kq.

Mit q′ = M−1p gilt T q′ = M−1T−T p und q′ = T−1M−1T−T p = pWir konnen daher oBdA annehmen, dass q und p diagonal. Somit gilt:

p′ = −kqq′ = p

Dieses zerfallt in 2x2 Systeme

p′i = −kiqiq′i = pi

Die Losung ist qi = A sin(ωt) + B cos(ωt) und qi = A sin(ωt) − B cos(ωt) mit ω =√ki. Die

betrachteten Verfahren sind invariant gegenuber der Transformation T , d.h. der Transformationder numerischen Losung ist nun Losung der transformierten Gleichung. Es reicht daher die 2x2-Systeme p′i = −ω2

i qi und q′i = pi zu betrachten bzw. mit p′i = −ωqi und q′i = ωpi

(p′

q′

)=

(0 −ωω 0

)(pq

)Mit explizitem Euler gilt

35

(pn+1

qn+1

)=

(pnqn

)+ h

(−ωpnωqn

)=

(1 −ωh−ωh 1

)︸ ︷︷ ︸

S

(pnqn

)

und somit yn = Sny0 Die Eigenwerte von S entscheiden ob die Losung stabil ist. λ1,2(S) =1± iωh, somit ist |λ1,2| > 1, d.h. die Losung schwingt auf! Bei implizitem Euler gilt

(pn+1

qn+1

)=

(1 −ωh−ωh 1

)−1(pnqn

)und somit |λ1,2| < 1, d.h. die Losung schwingt ab. Bei der Trapezmethode ist |λ1,2| = 1. DiesesVerhalten ist bereits von skalaren Gleichungen bekannt.

9.1 Spezielle Verfahren fur Hamiltonische Systeme

Das symplektische Eulerverfahren:

pn+1 = pn − knqn (9.8)

qn+1 = qn + hωpn+1 (9.9)

Dies ist ein explizites (Euler)-Verfahren (bei seperabler Hamilton-Funktion). Das obige Verfah-ren ist kein Runge-Kutta-Verfahren, sondern ist ein zusammengesetztes RK-Verfahren.Symplektisches Eulerverfahren fur Ausgangsproblem

pn+1 = pn − hkqnqn+1 = qn + hM−1pn+1

2x2-System:

(pn+1

qn+1

)=

(1 0hω 1

)(1 −ωh0 1

)(pnqn

)=

(1 −hωhω 1− (hω)2

)(pnqn

)Daraus folgt λ1 · λ2 = detS = 1 − (ωh)2 + (ωh)2 = 1, falls λi komplex, gilt λ1 = λ∗2, |λi| = 1.Es gilt sogar

λ1,2 = 1− (hω)2

2±

√(1− (hω)2

2

)2

− 1

Die Wurzel ist negativ fur |hω| < 2. Fur hω < 2 gilt |λ1,2| = 1, d.h. wir erhalten komplexkonjugierte Paare am Einheitskreis.

Lemma 9.5. Das symplektische Eulerverfahren hat genau Konsistenzordnung 1, das Stormer-Verlet-Verfahren mindestens Konsistenzordnung 2.

Beweis. Siehe UE6-Bsp 25.

36

10 Symplektische Abbildungen

Definition 10.1 (Symplektische Matrix). Eine Matrix A ∈ R2n×2n heißt symplektisch, wennfur diese die Beziehung ATJA = J gilt, wobei J die symplektische Einheitsmatrix

J :=

(0 In−In 0

)∈ R2n×2n (10.1)

bezeichnet.

Definition 10.2. Eine Funktion g : R2n → R2n heißt symplektisch, falls fur alle y gilt dass furg′ : y 7→ Ay A ∈ R2n×2n eine symplektische Matrix ist.

Lemma 10.3. Symplektische Funktionen g : Ω→ R2n fur Ω ⊆ R2n sind flachenerhaltend.

Beweis. Sei g : R2n → R2n und sei nach Voraussetzung g′ : R2n → R2n : x 7→ Ax, wobei A einesymplektische Matrix ist. Dann gilt nach Definition 10.1 sofort

ATJA = J (10.2)

det(AT ) det(J) det(A) = |det(A)|2 det(J)!

= det J (10.3)

Daraus folgt unmittelbar |det(A)| = 1, d.h. det(A) = ±1. Daher gilt nach dem Transformati-onssatz (siehe [3, Satz 9.62/Satz 9.75]) fur die Flache des Gebiets

λ2n(g(Ω))

∫g(Ω)

1dλ2n =

∫Ω|det(g)|︸ ︷︷ ︸

1

dλ2n =

∫Ω

1dλ2n = λ2n(Ω) (10.4)

Wir betrachten nun die Hamiltonische DGl

(p′

q′

)=

(−∂H

∂q∂H∂p

)=

(0 −II 0

)(∂H∂p∂H∂q

)= −J∇H (10.5)

mit y =

(pq

). Daraus folgt y′ = −J∇H(y).

Satz 10.4 (von Poincare). Sei H ∈ C2. Dann ist der Fluss φt : y0 7→ y(t) fur jedes t ≥ t0 einesymplektische Abbildung.

Beweis. Wir definieren

ψ(t) =dy(t)

dy0

und zeigen ψ ist eine symplektische Matrix.

d

dtψ =

d

dt

dy

dy0=

d

dy0

dy

dt=

d

dy0[−J∇H(y)]

= −J∇2H(y)dy

dy0︸︷︷︸=ψ

= −J∇2Hψ

37

d.h. ψ zerfallt selbst in die Dgl ψ′ = −J∇2Hψ mit der Anfangsbedingung ψ(0) = dy(0)dy0

= I.Dann gilt:

d

dtψTJψ = ψ′TJψ + ψTJψ′ = (−J∇2Hψ)TJψ + ψTJ(−J∇2Hψ)

= ψT∇2H − JTJ︸︷︷︸+I

ψ − ψT JJ︸︷︷︸−I

∇2Hψ = 0

Damit ist

ψT (t)Jψ(t) = ψ(0)Jψ(0) +

∫ t

0

d

dτψTJψdτ = IJI = J (10.6)

d.h. die Matrix ist symplektisch. Dies wird oft als Drehimpulserhaltung interpretiert (aber nichtEnergieerhaltung!).

Abbildung 13: Isometrieerhaltung als Flacheninhalt erhaltende Funktion in der Zeit, entsprichtDrehimpulserhaltung.

10.1 Das symplektische Eulerverfahren (KO 1)

pj+1 = pj − h∇qH(pi+1, qj) (10.7)

qj+1 = qj + h∇pH(pj+1, qj) (10.8)

Das Verfahren ist implizit fur p und explizit fur q. Falls H seperabel ist, d.h. H(p, q) = V (q) +T (p), dann ist das Verfahren explizit.

pj+1 = pj − h∇jV (qj) (10.9)

qj+1 = qj + h∇pT (pj+1) (10.10)

Das adjungierte symplektische Eulerverfahren ist

qj+1 = qj + h∇pH(pj , qj+1) (10.11)

pj+1 = pj − h∇qH(pj , qj+1) (10.12)

Dieses ist implizit fur q, explizit in p. Es ist nicht uberraschend, dass das Verfahren in beideRichtungen funktioniert. Man kann auch beide Verfahren abwechseln. Dies fuhrt zu folgendemVerfahren:

38

10.2 Das Stormer-Verlet-Verfahren (KO 2)

Das Stormer-Verlet-Verfahren ist eine Kombination vom symplektischen EV und seinem adjun-gierten EV.

pj+ 12

= pj −h

2∇qH(pj+ 1

2, qj) (10.13a)

qj+ 12

= qj +h

2∇pH(pj+ 1

2, qj) (10.13b)

qj+1 = qj+1 +h

2∇pH(pj+ 1

2, qj+1) (10.13c)

pj+1 = pj+ 12− h

2∇qH(pj+ 1

2, qj+1) (10.13d)

Die ersten Gleichung ist implizit fur pj+ 12, die zweite explizit fur qj . Die dritte Gleichung ist

explizit fur pj+ 12

und die vierte implizit fur qj+1.

Fur seperable H konnen 10.13b und 10.13c kombiniert werden, da ∂H∂p = ∂T

∂p (pj+ 12) und ∂H

∂q =∂V∂q (qj):

pj+ 12

= pj −h

2∇qV (qi) (10.14a)

qj+1 = qj + h∇pT (pj+ 12) (10.14b)

pj+1 = pj+ 12− h

2∇qV (qj+1) (10.14c)

Abbildung 14: Funktionsweise der symplektischen Verfahren

Weiters kann der letzte Teilschritt mit dem ersten Teilschritt des nachsten Zeitintervalles ver-bunden werden.

pj+ 12

= pj− 12− h∇qV (qi) (10.15a)

qj+1 = qj + h∇pT (qj+ 12) (10.15b)

Umgeformt ergeben die obigen Gleichungen

pj+ 12− pj− 1

2

h= ∇qV (qj) (10.16a)

qj+1 − qjh

= ∇pT (qj+ 12) (10.16b)

39

Dies entspricht dem zentralen Differenzenquotienten. Dieses Verfahren nennt man auch”leapfrog“-

Verfahren (Bockspring-Verfahren).

Abbildung 15: Schematik des Leapfrog-Verfahrens.

Das symplektische Eulerverfahren hat Konsistenzordnung 1, das Stormer-Verlet-Verfahren hatKonsistenzordnung 2. Dies ist eine Ubung fur seperable Hamiltonfunktionen (UE6, Bsp 26).

Lemma 10.5. Das symplektische Eulerverfahren ist symplektisch, d.h. (pj , qj) 7→ (pj+1, qj+1)ist symplektisch.

Beweis.

pj+1 = pj − hHq(pj+1, qj) (10.17)

qj+1 = qj + hHp(pj+1, qj) (10.18)

Wir mussen zeigend(pj+1,qj+1)d(pj ,qj)

ist symplektisch. Es gilt(∂pj+1

∂pj

∂pj+1

∂qj∂qj+1

∂pj

∂qj+1

∂qj

)=

(I − hHqp

∂pj+1

∂pj−hHqp

∂pj+1

∂qj− hHqq

hHpp∂pj+1

∂p1I + hHpp

∂pj+1

∂q + hHpq

)(10.19)

(I + hHqp 0−hHqp I

)︸ ︷︷ ︸

M1

(∂pj+1

∂pj

∂pj+1

∂qj∂qj+1

∂pj

∂qj+1

∂qj

)=

(I −hHqq0 I + hHpq

)︸ ︷︷ ︸

M2

(10.20)

Nachrechnen: M−11 M2 ist symplektisch (nachrechnen durch Brute-Force, siehe UE6, Bsp 27).

Somit ist das Verfahren als Zusammensetzung symplektischer Verfahren symplektisch.

Satz 10.6. Sei H(p, q) = V (q) + 12pTM−1p mit V analytisch. M sei SPD und sei λ :=

supq ‖M−12∇2VM−

12 ‖. Dann gilt fur das Stormer-Verlet-Verfahren

|H(pj , qj)−H(p0, q0)| ≤ Ch2 + c2e− 1hλ t (10.21)

Beweis. Meier-Lubich-Wanner: Geometric-Numerical-Integration (2002).

Ubung: Fur quadratische Hamiltons H(p, q) = 12qTKq+ 1

2pTM−1p. Fur die modifizierte Energie

des Verfahrens

H(p, q) = H(p, q) + h2qTKM−1p (10.22)

bleibt beim symplektischen Fall exakt erhalten. Wenn man sehr viele Unbekannte hat, rechnetman lieber mit expliziten Verfahren, z.B. bei elektromagnetischen Feldern, wo man oft eineMillion Unbekannte hat. Hier bietet sich das Leap-Frog-Verfahren an.

40

11 DAEs: Differential-algebraische Gleichungen

Explizite Form: gegeben sind

f : [0, T ]× Rn × Rm → Rn y0 ∈ Rn (11.1)

g : [0, T ]× Rn × Rm → Rm (11.2)

Gesucht ist:

y : [0, T ]→ Rn

z : [0, T ]→ Rm

y′(t) = f(t, y(t), z(t))

0 = g(t, y(t), z(t))

y(0) = y0

g(...) = 0 ist eine algebraische Nebenbedingung.

Beispiel 11.1 (Hamiltonisches System mit Nebenbedingung-Fadenpendel). Fadenpendel mitFadenlange l. Es gilt

H(p, q) =1

2m|p|2 +mgq

|q| = l⇔g(q) = |q| − l

Modellierung uber einen Strafterm (Penalisierung), der Stab wird durch eine sehr steife Federersetzt.

Hs(p, q) = H(p, q) +k

2|g(q)|2

Wir haben nun statt einem Faden eine Feder in der Gleichung, wir wollen anschließend jedochk gegen unendlich gehen lassen. Es gilt

(qs)′ =∂Hs

∂p=∂H

∂p=

p

m

(ps)′ = −∂Hs

∂q= −∂H

∂q− k

(∂g

∂q

)Tg

Wir fuhren nun eine neue Variable λ := kg ∈ Rm ein. Es gilt nun

(qs)′ =∂H

∂p

(ps)′ = −∂H∂q

+

(∂g

∂q

)Tλ

∂g

∂q=

∂g1∂q1

· · · ∂g1∂qn

.... . .

...∂gm∂q1

· · · ∂gm∂qn

−1

kλ = g(q)

41

Jetzt kann 1k = 0 gesetzt werden und wir haben nun eine DAE in expliziter Form (s.o.). Wir

betrachten das Federpendel mit g(q) = |q| − l. Es gilt(∂g∂q

)T= q|q| (einfach Ableiten, ist aus

∇ |~q| ersichtlich).

q′ =1

mp′ (11.3)

p′ =

(0−mg

)+

q

|q|λ (11.4)

0 = |q| − l (11.5)

11.1 Numerische Verfahren

Implizite Zeitintegration, z.B. mit implizitem Euler:

yj+1 − yjh

= f(tj+1, yj+1, zj+1) (11.6a)

0 = g(tj+1, yj+1, zj+1) (11.6b)

Explizite Verfahren sind fur DAEs nicht geeignet (Grenzwert von steifen DGlen). Wir musstendie Schrittweite fur k →∞ immer mehr verfeinern bei den expliziten Verfahren.Besonders gut eignen sich die Radau-Verfahren (mit Stutzstelle cj = 1). Diese erfullen g(tj+1, yj+1, zj+1) =0. Allerdings fuhren die Radau-Verfahren bei System, welche die Energie erhalten zu Dampfungen.

11.1.1 Reduktion auf gewohnliche Differentialgleichungen

Es gilt:

y′(t) = f(t, y(t), z(t)) (11.7a)

0 = g(t, y(t), z(t)) (11.7b)

Wir differenzieren g(·) = 0:

∂g

∂t+∂g

∂y

dy

dt+∂g

∂z

dz

dt= 0

Falls gz regular ist, dann gilt

z′ = −(gz)−1(gt + gyy

′(t))

Wir erhalten eine DGl fur

y′ = f

z′ = −(gz)−1(gt + gyf)(

y′

z′

)=

(f

−(gz)−1(gt + gyf)

)mit den Anfangsbedingungen so, dass g(t, y0, z0) = 0. Falls gz singular ist, kann weiteres Diffe-renzieren helfen. Dies fuhrt zum Index einer DAE, welcher angibt, wie oft differenziert werdenmuss, um eine ODE zu erhalten. Falls gz regular ist, ware der Index 1.

42

Beispiel 11.2 (Hamiltonisches System mit Nebenbedingung). Es gilt

q′ =∂H

∂p(11.8a)

p′ = −∂H∂q

+

(∂g

∂q

)Tλ (11.8b)

g(q(t)) = 0 (11.8c)

Einmaliges Differenzieren reicht noch nicht:

d

dtg(q(t)) =

∂g

∂qq′ =

∂g

∂q

∂H

∂p= 0

Wir mussen daher ein zweites Mal differenzieren:

d

dt(gq, Hp) =

∂

∂q(gq, Hp)q

′ +∂

∂p(qq, Hp)p

′

(11.8)=

∂

∂q(gq, Hp)Hp + gqHpp(−Hq + gTq λ)

= · · ·+ gqHppgTq λ = 0

Falls gqHppgTq regular, kann λ eliminiert werden. Wir erhalten daher eine ODE fur p und q.

In den 80er und 90er Jahren war dies eine sehr beliebte Methode.

11.1.2 Symplektische Verfahren fur Hamiltonische DAEs

Ein symplektisches Verfahren fur hamiltonische DAEs ist der sogenannte Rattle-Algorithmus.Gegeben sei (pn, qn) und gesucht sei (pn+1, qn+1).Teil 1:

pn+ 12

= pn −h

2(Hq(pn+ 1

2, qn)− gq(qn)λn) (11.9a)

qn+1 = qn +h

2(Hp(pn+ 1

2, qn) +Hp(pn+ 1

2, qn+1)) (11.9b)

0 = g(qn+1) (11.9c)

Teil 2:

pn+1 = pn+ 12− h

2(Hq(pn+ 1

2, qn+1) + gq(qn+1)µn) (11.10a)

0 = gq(qn+1)Hp(pn+1, qn+1) (11.10b)

Dieses Verfahren ist eine Verallgemeinerung des Stormer-Verlet-Verfahrens und ist auch sym-plektisch. Teil 1: g(qn+1) = 0Teil 2: ∂g

∂q q = 0

ad Ubung:

y′ = f1(y) + f2(y) (11.11)

yj+ 12

= φf1h (yj) (11.12)

yj+1 = φf2h (yj+ 12) (11.13)

Anwendung: Kopplung von Navier-Stokes-Gleichungen, bei dem man nichtlinearen Teil undlinearen Teil trennt.

43

12 Mehrschrittverfahren

Der neue Wert bei Mehrschrittverfahren hangt nun von der”Geschichte“ ab. Es gilt

yj+k = ψ(yj , . . . , yj+k−1) (12.1)

Dies definiert ein k-Schritt-Verfahren. Normalerweise hat man mehr Struktur vorausgesetzt,z.B. ein lineares MSV:

k∑l=0

alyj+l = h

k∑l=0

blf(tj+l, yj+l) (12.2)

Beispiel 12.1 (Adams-Verfahren). Es gilt ak = 1, ak−1 = −1, ak = 0 und somit

yj+k = yj+k−1 + hk∑l=0

Blf(tj+l, yj+l)

Fur bk = 0 erhalt man ein explizites Verfahren (Adams-Bashforth), sonst mit bl 6= 0 ein impli-zites Verfahren (Adams-Moulton).

Motivation uber numerische Integrationk = 2:

yj+2 = yj+1 +

∫ tj+2

tj+1

f(s, y(s))ds

≈ yj+1 + h(b0f(tj , yj) + b1f(tj+1, yj+1))

Wir bestimmten die Koeffizienten b0, b1 so, dass

b0f(0) + b1f(1) =

∫ 2

1f(s)ds ∀f ∈ P1

Daraus folgt b1 = 32 und b0 = −1

2 . Dies fuhrt zum Adams-Bashford-Verfahren

yj+2 = yj+1 + h

[−1

2f(tj , yj) +

3

2f(tj+1, yj+1)

]Das Adam-Moulton-Verfahren fur k = 2 lautet

2∑l=0

blf(l) =

∫ 2

1f(s)ds ∀f ∈ P2

Daraus folgt b0 = − 112 , b1 = 8

12 , b2 = 512 und somit

yj+2 = yj+1 +h

12(−f(yj) + 8f(yj+1) + 5f(yj+2))

Die Konsistenzbedingung fur allgemeine lineare MSV lautet

k∑l=0

alyj+l = h

k∑l=0

blf(yj+l) (12.3)

44

Oben haben wir die Gleichungen schon autonomisiert, dies stellt aber kein Problem dar. DerKonsistenzfehler berechnet sich durch Einsetzen der wahren Losung in das Verfahren:

L(t, h, y) =

k∑l=0

aly(t+ lh)− hk∑l=0

bl f(y(t+ lh))︸ ︷︷ ︸y′(t+lh)

(12.4)

Konsistenzordnung p ist erfullt, wenn L(t, h, y) = O(hp+1). Man kann nun eine Taylorentwick-lung von L in h an der Stelle t durchfuhren:

L(t, h, y) =k∑l=0

al

p∑j=0

1

j!hjljy(j)(t)− h

k∑l=0

bl

p−1∑j=0

1

j!hjljy(j+1)(t) +O(hp+1)

=k∑l=0

al1

0!h0y +

p∑j=1

1

j!hjy(j)

k∑l=0

allj −

p∑j=1

hj1

(j − 1)!

k∑l=0

bllj−1

=

(k∑l=0

al

)y(t) +

p∑j=1

hjy(j) 1

j!

(k∑l=0

allj − j

k∑l=0

bllj−1

)︸ ︷︷ ︸

=0

+O(hp+1)

Die Forderung an die Konsistenzordnung p ist, dass der Ausdruck in der Klammer 0 wird.

Lemma 12.2. Ein lineares MSV hat Konsistenzordnung p, falls

k∑l=0

al = 0 (12.5)

k∑l=0

allj − jbllj−1 = 0 ∀j = 1, . . . , p (12.6)

Beweis. Die Skalierung ist frei wahlbar, da dies homogene Gleichungen in a und b sind, somitz.B. ak = 1. Mit einem k-Schritt-Verfahren hat man 2k + 2 Koeffizienten, Ordnung p hat(p+ 1) + 1 (Skalierung/Gleichungen), d.h. p = 2k ist erreichbar.

Beispiel 12.3. Explizites Verfahren fur k = 2:

a0 = −5 b0 = 2

a1 = 4 b1 = 4

a2 = 1 b2 = 0

Die Koeffizienten in Tabelle 12.3 erfullen die Ordnungsbedingungen bis p = 3. Es gilt

yj+2 = 5yj − 4yj+1 + h(2f(yj) + 4f(yj+1))

Wir setzen fur f = 0 ein:

yj+2 − 5yj + 4yj+1 = 0

Mit dem Ansatz yj = zj gilt

zj(z2 + 4z − 5) = 0

45

somit ergibt sich aus der quadratischen Gleichung z1 = 1, z2 = −5. yj hat damit die Form

yj = A1zj1 +A2z

j2 = A1 +A2(−5)j

A1, A2 ergeben sich aus den Startwerten von y0, y1, wir sehen sofort das Problem: Falls A2 6= 0ist die numerische Losung wegen Instabilitat schlecht, da yj ≈ A2(−5)j.

Dies ist ein neues Stabilitatsproblem, das nur bei Mehrschrittverfahren auftritt. Mit der Ver-kleinerung von h konnen wir uns nicht mehr helfen. Je kleiner h, um so schneller wachst yj ,somit sind instabile MSV auch instabil fur h → 0. Um stabile MSV zu erhalten, muss dieNull-Stabilitat erfullt sein:

Definition 12.4 (Nullstabilitat). Von der Nullstabilitat eines MSV spricht man genau dann,wenn alle Nullstellen des char. Polynoms

g(z) =k∑l=0

alzl (12.7)

erfullen, dass |zj | < 1 oder |zj | = 1, falls die Nullstelle einfach ist.

Dies ist i.A. nicht leicht zu uberprufen fur beliebige Koeffizienten-Tabellen. Mit unserem Adams-Verfahren von vorher mit ak = 1, ak−1 = −1, al = 0 sonst geht dies aber, da gilt zk − zk−1 = 0und somit zk−1(z − 1) = 0. Wir erhalten die einfache Nullstelle z = 1 und die (k − 1)-facheNullstelle z = 0, daher ist das Verfahren 0-stabil.Vererbung asymptotischer Stabilitat

• Lineare DGl: y′ = Ay

• Eigenwertzerlegung ⇒ y′ = λy

Die numerische Losung erfullt

k∑l=0

alyj+l = h

k∑l=0

bl λyj+l︸ ︷︷ ︸f(yj+l)

k∑l=0

(al − hλbl)yj+l = 0

Die Losung lautet

yj =

k∑i=0

Aizji

mit zi als Nullstellen von

k∑l=0

(al − hλbl)zl = 0

Der Stabilitatsbereich des Verfahrens:

S = hλ ∈ C : ∀Nullstellen von (t) erfullen |zj | < 1 ∨ |zj | = 1 und Nullstelle einfach

46

A-stabiles Verfahren: C− ⊂ S0-stabiles Verfahren: 0 ∈ SMan wunscht sich naturlich A-stabile Verfahren, aber man mochte zumindest erreichen, dassein Sektor ner negativen Halbebene im Stabilitatsbereich liegt. Dies fuhrt zu A(α)-stabilenVerfahren, wo ein Sektor mit Winkel 2α im Stabilitatsbereich liegt.BDF (Backward Differentiation Formula)-VerfahrenSei bk = 1 und bl = 0 sonst. Es gilt

k∑l=0

alyj+l = hbk f(yj+k)︸ ︷︷ ︸≈y′j+k

1

hbk

k∑l=0

alyj+l ≈ y′(tj+k)

Wegen dieser Naherung fur y′(tj+k) kommt der Name des Verfahrens.

Beispiel 12.5. Sei k = 0. Wir verwenden das Lagrange-Interpolationspolynom

P2 = y0(t− 1)(t− 2)

(0− 1)(0− 2)+ y1

(t− 0)(t− 2)

(1− 0)(1− 2)+ y2

(t− 0)(t− 1)

(2− 0)(2− 1)

P ′2(2) =1

2y0 − 2y1 +

3

2y2

Somit gilt

1

2yj − 2yj+1 +

3

2yj+2 = hf(yj+2)

Alternativ hatten wir die Bedingungsgleichungen fur die Ordnungbedingungen hernehmen konnen.

BDF-Verfahren bis k = 7 sind A(α)-stabil.Vorteile von MSV:

• relativ einfach hohere Ordnung bei impliziten Verfahren und auch bei expliziten Verfahren.Bei impliziten hat man z.B. ein lineares GLS mit Dimension d (Anzahl der Freiheitsgrade)und nicht n · d.

Nachteile von MSV:

• Adaptive Schrittweitensteuerung schwierig zu implementieren, nicht wirklich geeignet dafur

• benotigt Startwerte y0, . . . , yk−1 und nicht nur einen, muss sich diese z.B. uber Runge-Kutta-Verfahren besorgen

Literatur

[1] Winfried Auzinger and Dirk Praetorius. Numerische Mathematik. Skriptum, 2011.

[2] Peter Deuflhard and Folkmar Bornemann. Numerische Mathematik 2. Gewohnliche Diffe-rentialgleichungen. Walter de Gruyter Verlag, Berlin, 3. auflage edition, 2008.

[3] Norbert Kusolitsch. Maß- und Wahrscheinlichkeitstheorie. Springer-Verlag, Wien, 1. auflageedition, 2011.

47