Embed Size (px)
Citation preview
nationales Forschungszentrum in der Helmholtz-Gemeinschaft
Institut für Angewandte und Numerische Mathematik
KIT - Universität des Landes Baden-Württemberg undnationales Forschungszentrum in der Helmholtz-Gemeinschaft www.kit.edu
Numerische Methoden für DifferentialgleichungenSkript zur Vorlesung im Wintersemester 2009/2010
Christian Wieners
Version vom 11. Juli 2011
Inhaltsverzeichnis
Einführung 1
1 Existenz und Eindeutigkeit der Lösung von Anfangswertaufgaben 5
2 Explizite Einschrittverfahren 132.1 Explizite Runge-Kutta-Verfahren . . . . . . . . . . . . . . . . . . . . . . 132.2 Qualitätskontrolle bei Einschrittverfahren . . . . . . . . . . . . . . . . . 22
3 Lineare Mehrschrittverfahren 28
4 Steife Differentialgleichungen 464.1 Lineare Stabilitätsanalyse . . . . . . . . . . . . . . . . . . . . . . . . . . 504.2 L-Stabilität . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 544.3 Reversible Verfahren . . . . . . . . . . . . . . . . . . . . . . . . . . . . 564.4 B-Stabilität . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
5 Randwertaufgaben (RWA) 68
Diese Vorlesung behandelt numerische Verfahren zur Behendlung von Anfangswert- undRandwertaufgaben in einer Raumdimension von gewöhnlichen Differentialgleichungen.Neben der Konstruktion der Verfahren wird im Wesentlichen die Konvergenzanalyse be-trachtet. Das Skript soll auch als Grundlage für weiterführende Vorlesungen zur numeri-schen Behandlung partieller Differentialgleichungen dienen.Der gesamte Stoff wurde aus Standard-Lehrbüchern zusammengestellt; die wesentlichenQuellen sind unten angegeben.Das Skript wurde von Herrn Johannes Ernesti erstellt. Ich danke ihm für die mühevolleTEX-Arbeit, und den vielen Studenten, die bei der Fehler-Korrektur geholfen haben.
Literatur
Deuflhard/Bornemann: Numerische Mathematik II, de Gruyter 2002Hanke-Bourgois: Grundlagen der Numerischen Mathematik, Teubner 2003Hairer/Nørsett/Wanner: Solving Ordinary Differential Equations I: Nonstiff Problems, Sprin-ger 2000Hairer/Nørsett/Wanner: Solving Ordinary Differential Equations II: Stiff and DifferentialAlgebraic Problems, Springer 2000
Einführung
Im ersten Teil der Vorlesung werden Anfangswertaufgabe (kurz AWA) untersucht. Sie istdurch eine Funktion F ∈ C([t0, t0 + T ] × RM ,RM) und einem Anfangswert u0 ∈ RM
gegeben. Dann suchen wir eine Lösung u ∈ C1([t0, t0 + T ],RM)
u(t) = F (t, u(t)) t ∈ (t0, t0 + T ),
u(t0) = u0.
Zur Einführung betrachten wir verschiedene Algorithmen für ein Problem mit bekannterLösung. Daher beginnen wir mit der Betrachtung von einigen elementare Integrationsver-fahren für Anfangswertaufgaben für eine skalare lineare Differentialgleichung.
Beispiel (Radioaktiver Zerfall)Die Konzentration c(t) eines radioaktiven Stoffes für t ∈ [0, T ] erfüllt die Anfangswert-aufgabe
c(t) = −λc(t),c(0) = c0.
Dabei ist λ > 0 die Zerfallsrate und c0 > 0 die Anfangskonzentration.In diesem einfachen Beispiel kann man die Lösung explizit angeben:
c(t) = c0 · e−λt
Anwendung: Bei der Radiokarbonmethode wird in einer organischen Substanz die Kon-zentration des Kohlenstoffisotops 14
6C bestimmt und daraus auf den Todeszeitpunkt desOrganismus geschlossen.Die Halbwertszeit von 14
6C wurde experimentell ermittelt und beträgt ca. 5730 Jahre. Da-mit gilt λ = ln(2)
5730, d.h.
c(5730) =c0
2= c0 · e−5730λ.
Wir betrachten die diskrete Approximation auf einem äquidistanten Gitter ∆ = t0, . . . , tNmit tn = nτ . Dabei sei τ = T
Ndie Schrittweite. (Schreibe auch τN = τ und tN,n = tn).
Die Gitterfunktion cN : ∆ → R, tn 7→ cN(tn) = cnN lässt sich zu einem Polygonzug(linearer Spline) fortsetzen
cN(t) = cn−1N +
1
τN(t− tn−1)(cnN − cn−1
N ), t ∈ [tn−1, tn]
cN(t) =1
τN(cnN − cn−1
N ), t ∈ (tn−1, tn).
cN ist für tn ∈ ∆ nicht differenzierbar, aber cN ist Lipschitz-stetig, also existiert dieverallgemeinerte mengenwertige Ableitung
∂cN(tn) = conv
1
τ(cnN − cn−1
N ),1
τ(cn+1N − cnN)
.
Wir betrachten drei Möglichkeiten, die Ableitung c(tn) zu approximieren:
1
a) rechter Differenzenquotient 1τ(cn+1N − cnN),
b) linker Differenzenquotient 1τ(cnN − cn−1
N ),
c) zentraler Differenzenquotient 12τ
(cn+1N − cn−1
N ).
LemmaSei u ∈ C3([0, T ]), t ∈ (0, T ), h > 0 mit t− h, t+ h ∈ [0, T ]. Dann gelten
a) 1h(u(t+ h)− u(t)) = u(t) +O(h),
b) 1h(u(t)− u(t− h)) = u(t) +O(h),
c) 12h
(u(t+ h)− u(t− h)) = u(t) +O(h2).
Beweis für c). Die Taylorentwicklung liefert für ein s ∈ (t, t+ h) und ein s ∈ (t− h, t)
u(t+ h) = u(t) + u(t)h+1
2u(t)h2 +
1
6
...u(s)h3,
u(t− h) = u(t)− u(t)h+1
2u(t)h2 − 1
6
...u(s)h3.
Damit gilt durch Subtraktion der Gleichungen
u(t+ h)− u(t− h) = 2hu(t) +O(h3).
Wir setzen den Differenzenquotienten in c(t) = −λc(t) ein:
a) Explizites Eulerverfahren
1
τ(cn+1N − cnN) = −λcnN ⇒ cn+1
N = cnN − τλcnN = (1− τλ)n+1c0
b) Implizites Eulerverfahren
1
τ(cnN − cn−1
N ) = −λcnN ⇒ (1 + τλ)cnN = cn−1N ⇒ cnN = (1 + τλ)−nc0
c) Explizites Mittelpunktverfahren
1
2τ(cn+1N − cn−1
N ) = −λcnN ⇒ cn+1N = cn−1
N − 2τλcnN n = 1, . . . , N − 1
(Setze c1N := c0 − τλc0.)
2
Lösungsformel für die Dreitermrekursion Wir betrachten den Ansatz cnN = zn. Dannfolgt zn+1 = zn−1 − 2τλzn und es gilt für z 6= 0 : z2 = 1− 2τλz.Damit folgt z1/2 = −τλ± α, wobei α =
√τ 2λ2 + 1. Das führt zu
cnN = a1zn1 + a2z
n2 ,
also insbesondere zu
c0 = a1 + a2 ,
c1N = a1z1 + a2z2 .
Daraus lassen sich a1 und a2 bestimmen:
c0 − τλc0 = (a1 + a2)(−τλ) + (a1 − a2)α , alsoa1 = c0
1+α2α, a2 = c0
−1+α2α
.
Diskussion
1) Konvergenz für τ = TN→ 0 (bzw. N →∞) an der Stelle t = T = tN .
a) Explizites Eulerverfahren
limN→∞
cN(T ) = limN→∞
(1− T
Nλ
)Nc0 = c0e
−λT = c(T ),
b) Implizites Eulerverfahren
limN→∞
cN(T ) = limN→∞
(1 +
T
Nλ
)−Nc0 = c0
1
eλT= c(T ),
c) Explizites Mittelpunktverfahren
limN→∞
cN(T ) = c0 limN→∞
(1 + αN
2αNzN1 +
−1 + αN2αN
zN2
)= c0 lim
N→∞
(1− λ T
N
)N= c0e
−λT = c(T ),
da mit der Taylorentwicklung
αN =
√1 +
(T
N
)2
λ2 = 1 +1
2
T 2
N2λ2 + · · ·
gilt.
2) KonvergenzordnungDas Verfahren konvergiert mit der Ordnung p, wenn |c(t)− cN(t)| = O(τ p), d.h.
∃C > 0, τ0 > 0 : |c(t)− cN(t)| ≤ Cτ p, ∀τ < τ0.
3
a) Explizites Eulerverfahren
|c(T )− cN(T )| = c0
∣∣∣∣∣e−λT −(
1− Tλ
N
)N ∣∣∣∣∣= c0
∣∣∣1− λT +1
2(λT )2 − . . .
−
(1−N
(T
Nλ
)+N(N − 1)
2
(T
Nλ
)2
− . . .
)∣∣∣= c0
∣∣∣∣12λ2T2
N+ . . .
∣∣∣∣ = c0τ
∣∣∣∣12λ2T + . . .
∣∣∣∣ = O(τ)
b) Implizites Eulerverfahren |c(T )− cN(T )| = O(τ)
c) Explizites Mittelpunktverfahren |c(T )− cN(T )| = O(τ 2)
3) StabilitätEin numerisches Verfahren heißt stabil, wenn die diskrete Approximation einer be-schränkten Lösung des kontinuierlichen Problems ebenfalls beschränkt bleibt.
a) Explizites EulerverfahrenIm Fall τλ ≤ 2 gilt Stabilität:
|cnN | = |1− τλ|n|c0| ≤ |c0|
Im Fall τλ > 2 ist das Verfahren instabil:
|cnN | = |1− τλ|n|c0| → ∞ (n→∞)
b) Das implizite Eulerverfahren ist stabil:
|cnN | = |1 + τλ|−n|c0| → 0 (n→∞)
c) Explizites MittelpunktverfahrenFür festes τ und T →∞ gilt
limn→∞
|cn| = c01− α
2αlimn→∞
|z2|n =∞.
Also ist das Verfahren nur für festes T und kleines τ stabil.
4) KonsistenzUntersuchung des lokalen Fehlers in einem Zeitschritt.
Wir zeigen später, dass aus Konsistenz und Stabilität bereits Konvergenz folgt.
4
1 Existenz und Eindeutigkeit der Lösung von Anfangs-wertaufgaben
Gute Approximationen sind nur zu erwarten, wenn das kontinuierliche Problem eine ein-deutige Lösung besitzt, und wenn diese Lösung nicht zu empfindlich von den Daten ab-hängt (d.h. gut konditioniert ist).Eine Differentialgleichung (DGL) heißt sachgemäß gestellt, wenn die Lösung eindeutigist und stetig von den Daten abhängt.
Beispiel1) Die DGL u =
√1− u2 hat ohne Vorgabe der Anfangswerte die Lösungen
u(t) = sin(t+ c) (c ∈ R)
u(t) = ±1.
Betrachtet man verschiedene Anfangswerte, ergeben sich folgende Situationen:
a) u(0) = 0 liefert u(t) = sin(t) (eindeutig)
b) u(0) = 1 liefert u(t) = sin(t+ π
2
)oder u(t) = 1 (mehrdeutig)
c) u(0) = 2 ist nicht lösbar
2) Die DGL u = 1 + u2 mit Anfangswert u(0) = 0 hat die Lösung u(t) = tan(t) fürt ∈
(−π
2, π
2
). Die Lösung ist aber nicht in einem größeren Intervall I ⊃
(−π
2, π
2
)fortsetzbar. Wir haben keine Möglichkeit, das maximale Existenzinterval zu bestim-men, wenn wir die echte Lösung nicht kennen. Deshalb brauchen wir eine a-priori-Abschätzung, für welche t unsere Lösung sinnvoll ist.
3) Die DGL
u = 10
(u− t2
1 + t2
)+
2t
(1 + t2)2
hat für u(0) = u0 die Lösung
u(t) =t2
1 + t2+ u0e
10t.
Die Lösung dieser Differentialgleichung ist nicht stabil:Für u0 = 0 gilt limt→∞ u(t) = 1.Sobald u0 = ε 0 ist, folgt aber limt→∞ u(t) = −∞.Somit führen winzige Änderungen der Anfangswerte (selbst wenn sie nur von der Grö-ßenordnung der Rundungsfehler sind) in diesem Fall bereits zu beliebig großen Fehlernfür t 0.
Die folgende Theorie liefert uns Aussagen über Existenz, Eindeutigkeit und Qualität derLösung einer Anfangswertaufgabe, ohne dass wir sie dazu explizit berechnen müssen.
5
(1.1) DefinitionSeien t0 ∈ R, T > 0, G ⊂ RM ein Gebiet (offen und zusammenhängend), u0 ∈ G undf ∈ C([t0, t0 + T ]×G,RM) gegeben. Dann heißt u ∈ C1([t0, t0 + T ], G) mit
u(t) = f(t, u(t)) t ∈ (t0, t0 + T ),
u(t0) = u0.
Lösung der Anfangswertaufgabe (AWA) zu f und u0.
BezeichnungenFür z ∈ RM , u ∈ C([t0, t0 + T ],RM) und v ∈ C1([t0, t0 + T ],RM) verwenden wirfolgende Normen:
|z| =√zT z Euklidische Norm in RM
‖u‖∞ = maxt∈[t0,t0+T ]
|u(t)| Supremumsnorm
‖v‖C1 = max‖v‖∞, ‖v‖∞ C1-Norm
Mit ‖ · ‖∞ bzw. ‖ · ‖C1 ist C([t0, t0 + T ],RM) bzw. C1([t0, t0 + T ],RM) ein Banachraum.
(1.2) LemmaEs sind äquivalent:
a) u ∈ C1([t0, t0 + T ], G) löst (1.1).
b) u ∈ C([t0, t0 + T ], G) erfüllt
u(t) = u0 +
∫ t
t0
f(s, u(s))ds (t ∈ (t0, t0 + T )).
Beweis. “a)⇒ b)”: Sei u eine Lösung von (1.1). Dann gilt∫ t
t0
f(s, u(s))ds =
∫ t
t0
u(s)ds = u(s)∣∣tt0
= u(t)− u0.
“b)⇒ a)”: Sei u eine Lösung der Integralgleichung aus b) und setze
v(t) := u0 +
∫ t
t0
f(s, u(s))ds.
Dann ist v differenzierbar mit v(t) = f(t, u(t)) und v ist stetig, da f in t stetig ist. Außer-dem gilt nach Voraussetzung u ≡ v und deshalb löst u auch (1.1).
(1.3) LemmaZu f ∈ C([t0, t0 + T ]×G,RM), u0 ∈ G und r > 0 mit
Br(u0) :=z ∈ RM : |z − u0| ≤ r
⊂ G
setze
Mr := max|f(t, z)| : t ∈ [t0, t0 + T ], z ∈ Br(u0)
.
6
Dann gilt für jede Lösung u von (1.1) die a-priori-Schranke
|u(t)− u0| ≤ (t− t0)Mr ∀t ∈[t0, t0 + min
(T,
r
Mr
)].
Beweis. Für eine Lösung u von (1.1) setze d(t) := |u(t) − u0|. Damit ist d stetig und esgilt d(t0) = 0.Es können zwei Fälle auftreten: Entweder es gilt
1) d(t) < r für t ≤ T =: t oder
2) es existiert ein t ∈ [t0, t0 + T ] mit d(t) = r und d(t) < r für alle t < t.
In beiden Fällen gilt u([t0, t]) ⊂ Br(u0).Nun gilt nach (1.2)
d(t) =
∣∣∣∣u0 +
∫ t
t0
f(s, u(s))ds− u0
∣∣∣∣ ≤ ∫ t
t0
|f(s, u(s))|ds
≤∫ t
t0
|f(s, u(s))|︸ ︷︷ ︸≤Mr
ds ≤ (t− t0)Mr.
Im Fall d(t) = r gilt r = d(t) ≤ (t− t0)Mr und das liefert t ≥ t0 + rMr
.
Im Folgenden sei ohne Einschränkungen T ≤ t− t0. Dabei ist t von r und f abhängig.
(1.4) LemmaZu N ∈ N ist der Euler’sche Polygonzug uN ∈ C([t0, t0 + T ],RM) mit
uN(t) = uN(tN,n−1) + (t− tN,n−1)f(tN,n−1, uN(tN,n−1))
für tN,n = t0 + nτN , t ∈ [tN,n−1, tN,n], τN = TN
wohldefiniert und es gilt
|uN(t)− u0| ≤ (t− t0)Mr
Beweis. Der Beweis erfolgt analog zu (1.3).
(1.5) DefinitionEine Funktion v ∈ C([t0, t0 +T ],RM) ist Lipschitz-stetig (L-stetig), wenn L > 0 existiertmit
|v(s)− v(t)| ≤ L|s− t| ∀s, t ∈ [t0, t0 + T ].
Zusammen mit der Norm
‖v‖C0,1 := max
‖v‖∞, sup
t0≤s<t≤t0+T
|v(s)− v(t)||s− t|
bilden die Lipschitz-stetigen Funktionen den Banachraum
C0,1([t0, t0 + T ],RM) :=f ∈ C([t0, t0 + T ],RM) : f ist Lipschitz-stetig
.
7
(1.6) Folgerung (aus dem Satz von Arzelà-Ascoli)Jede beschränkte Folge (vN)N∈N ⊂ C0,1([t0, t0 + T ],RM) besitzt eine konvergente Teil-folge (vNk)k∈N ⊂ C([t0, t0 + T ],RM), d.h., es existiert ein v ∈ C([t0, t0 + T ],RM) mit
limk→∞‖vNk − v‖∞ = 0.
AnwendungDie Folge uN : N ∈ N aus (1.4) ist in C0,1([t0, t0 + T ],RM) beschränkt: Es gilt
‖uN‖C0,1 ≤ |u0|+ r +Mr .
Also existiert eine konvergente Teilfolge mit Grenzwert u ∈ C([t0, t0 +T ],RM) und es gilt|uN(t)− u0| ≤ r, also uN(t) ∈ Br(u0) ⊂ G.
(1.7) Satz (Peano)Der Euler’sche Polygonzug konvergiert gegen eine Lösung der Anfangswertaufgabe (1.1).
Beweis. Der Grenzwert u in (5) erfüllt die Anfangsbedingung u(t0) = u0. Wir müssennoch zeigen, dass der Grenzwert Lösung der Differentialgleichung ist.Als stetige Funktion ist f gleichmäßig stetig auf der kompakten Menge [t0, t0 + T ] ×Br(u0), d.h.
∀ε > 0 ∃δ > 0 : |f(t, z)− f(s, y)| ≤ ε für |z − y| ≤ δ, |t− s| ≤ δ.
Es existiert ein N ∈ N mit τN < δ, τNMr < δ, ‖uN − u‖∞ ≤ minε, δ. Dann gilt∣∣∣∣uN(t)− u0 −∫ t
t0
f(s, uN(s))ds
∣∣∣∣=
∣∣∣∣∣N∑n=1
∫ mint,tN,n
mint,tN,n−1
(f(tN,n−1, uN(tN,n−1))− f(s, uN(s))
)ds
∣∣∣∣∣≤ (t− t0)ε,
da |uN(tN,n−1)− uN(s)| ≤ (s− tN,n−1)Mr ≤ δ.Daraus folgt dann∣∣∣∣u(t)− u0 −
∫ t
t0
f(s, u(s))ds
∣∣∣∣≤ (t− t0)ε+
∣∣∣∣u(t)− uN(t)−∫ t
t0
(f(s, u(s))− f(s, uN(s))
)ds
∣∣∣∣≤ (t− t0)ε+ ε+ (t− t0)ε,
da |u(t)− uN(t)| ≤ ε und |u(s)− uN(s)| ≤ δ.Damit ist gezeigt, dass u die Integralgleichung (1.2) erfüllt und somit Lösung der AWAist. Ein analoges Argument zeigt nun, dass die gesamte Folge konvergiert.
Bemerkung1) Der Satz von Peano (1.7) garantiert keine Eindeutigkeit. Ein Beispiel dafür ist die
Anfangswertaufgabe u = 3u23 , u(0) = 0: Für jedes a ≥ 0 ist u(t) = max(t− a)3, 0
eine Lösungen der AWA.
8
2) Die Konvergenzgeschwindigkeit kann beliebig langsam sein.
(1.8) DefinitionEine Funktion f ∈ C([t0, t0 +T ]×G,RM) ist in der zweiten Komponente Lipschitz-stetigin G (erfüllt eine L-Bedingung), wenn ein L > 0 existiert mit
|f(t, y)− f(t, z)| ≤ L |y − z| ∀t ∈ [t0, t0 + T ], y, z ∈ G.
BeispielFür beschränktes G mit 0 ∈ G und α > 0 betrachte f(y) = |y|α. Dann erfüllt f genaudann eine Lipschitz-Bedingung, wenn α ≥ 1 gilt.
(1.9) LemmaSei f ∈ C1([t0, t0 + T ] × G,RM), G sei beschränkt und konvex. Dann erfüllt f eineL-Bedingung.
Beweis. Übungen.
(1.10) SatzSeien u, v ∈ C1([t0, t0 + T ], G) Lösungen von
u = f(t, u), v = f(t, v)
und f erfülle eine L-Bedingung. Dann gilt
|u(t)− v(t)| ≤ exp(L(t− t0))|u(t0)− v(t0)|.
Beweis. Für den Beweis wird das Growall-Lemma (1.12) benötigt (siehe unten).
(1.11) FolgerungWenn f eine L-Bedingung erfüllt, dann ist die Lösung der Anfangswertaufgabe (1.1) ein-deutig, denn für zwei Lösungen u und v ist |u(t0)− v(t0)| = 0.
BeispielDas Lorenz-System in R3
u = f(u) mit f(u) =
−10u1 + 10u2
28u1 − u2 − u1u2
u1u2 − 83u3
, u(0) =
100
ist ein “chaotisches” dynamisches System. Dabei heißt “chaotisch”, dass für große Zeitent ≥ t0 die Lösungen auch für nah beieinander liegende Anfangswerte völlig verschiedensind. Es gelten:
a) Es existiert ein r > 0 mit u(t) ∈ Br(u0) (∀t ≥ t0). Daher kann T > 0 beliebig großgewählt werden.
b) f erfüllt eine L-Bedingung in Br(u0). Also ist die Lösung für alle Zeiten eindeutig,aber nicht berechenbar, denn exp(Lt) ist für große t zu groß.
9
(1.12) Lemma (Gronwall)Seien d, a, b : [t0, t0 + T ] → R≥0 := s ∈ R : s ≥ 0 stückweise stetige Funktionen undsei b nicht fallend (d.h. b(t) ≥ b(s) für t ≥ s) mit
d(t) ≤ b(t) +
∫ t
t0
a(s)d(s)ds für alle t ∈ [t0, t0 + T ] .
Dann gilt
d(t) ≤ b(t) exp
(∫ t
t0
a(s)ds
)(∀t ∈ [t0, t0 + T ]).
Beweis. Definiere
µ(t) :=
∫ t
t0
a(s)d(s)ds, ν(t) := d(t)− µ(t).
Damit gilt nach Voraussetzung ν(t) ≤ b(t) und es folgen
µ(t) = a(t)d(t), a(t)ν(t) = a(t)(d(t)− µ(t)) = µ(t)− a(t)µ(t).
Also löst µ die Anfangswertaufgabe
µ(t) = a(t)(µ(t) + ν(t)), µ(t0) = 0.
Diese Anfangswertaufgabe hat die Lösung
µ(t) = eA(t)
∫ t
t0
a(s)ν(s)e−A(s)ds mit A(t) =
∫ t
t0
a(s)ds,
denn es gilt µ = Aµ+ eAaνe−A = aµ+ aν. Die Lösung ist eindeutig.Aus a(s) ≥ 0 und ν(s) ≤ b(s) ≤ b(t) für s ≤ t folgt
µ(t) ≤ eA(t)
∫ t
t0
a(s)b(t)e−A(s)ds = eA(t)b(t)[−e−A(s)
]s=ts=t0
= b(t)[eA(t) − 1
]und daraus schließlich
d(t) ≤ b(t) + µ(t) ≤ b(t)eA(t).
Damit ist das Gronwall-Lemma bewiesen.
Beweis von Satz (1.10). Setze d(t) := 12|u(t)− v(t)|2. Dann bleibt zu zeigen, dass
d(t) ≤ e2L(t−t0)d(t0)
gilt.
10
Da u, v die Anfangswertaufgabe (1.1) lösen, gelten u = f(t, u(t)) und v = f(t, v(t)) unddamit gilt für die Ableitung von d
d(t) =1
2
[(u(t)− v(t))T (u(t)− v(t)) + (u(t)− v(t))T (u(t)− v(t))
]= (f(t, u(t))− f(t, v(t)))T (u(t)− v(t))CS≤ |f(t, u(t))− f(t, v(t))| · |u(t)− v(t)|
L-Bed.≤ L|u(t)− v(t)|2 = 2Ld(t).
Damit folgt
d(t) ≤ d(t0) +
∫ t
t0
2Ld(s)ds.
Und daraus folgt schließlich mit b(t) := d(t0) und a(s) := 2L in (1.12)
d(t) ≤ d(t0) exp
(∫ t
t0
2Lds
)= d(t0)e2L(t−t0),
was zu zeigen war.
Auch im Folgenden gelte T ≤ rMr
.
(1.13) LemmaDer Integraloperator
F : C([t0, t0 + T ], Br(u0)) → C([t0, t0 + T ], Br(u0)),
v 7→ F (v)(t) = u0 +
∫ t
t0
f(s, v(s))ds
ist wohldefiniert.
Beweis. Wir müssen zeigen, dass die Funktion F (v) tatsächlich nach Br(u0) abbildet.Dies ist der Fall, denn es gilt |F (v)(t)− u0| ≤ (t− t0)Mr ≤ TMr ≤ r.
BemerkungMithilfe des Integraloperators aus (1.13) und Lemma (1.2) lässt sich die Anfangswertauf-gabe (1.1) als Fixpunktaufgabe formulieren:Eine Funktion u löst genau dann (1.1), wenn u = F (u) gilt, d.h. u ist ein Fixpunkt von F .
(1.14) Satz (Picard-Lindelöff)Die L-Bedingung (1.8) sei erfüllt. Dann existiert ein T > 0, sodass die “Picard-Folge”
v0 = u0, vk = F (vk−1) (k = 1, 2, . . . )
gegen die Lösung u von (1.1) konvergiert.
11
Beweis. Wir zeigen, dass F kontrahierend ist, denn dann folgt mit dem Banach’schenFixpunktsatz die Behauptung.Wähle dazu T mit TL < 1. Dann gilt für v, w ∈ C([t0, t0 + T ], Br(u0))
‖F (v)− F (w)‖∞ = maxt∈[t0,t0+T ]
∣∣∣∣∫ t
t0
(f(s, v(s))− f(s, w(s))
)ds
∣∣∣∣≤
∫ t0+T
t0
|f(s, v(s))− f(s, w(s))|ds
≤∫ t0+T
t0
L|v(s)− w(s)|ds ≤ ‖v − w‖∞(TL).
Das war zu zeigen.
BemerkungDie Lösung kann bis T = r
Mrfortgesetzt werden, indem der Satz mehrfach hintereinander
angewendet wird.
Beispiel (Reaktionskinetik)Betrachte die Konzentrationen ui von Stoffen Xi mit Reaktionsraten ki:
X1k1−→ X2 Stoffabbau
X2 +X3k2−→ X1 +X3 Stoffumwandlung mit Katalysator X3
2X2k3−→ X3.
Das führt zu der Differentialgleichung
u1 = −k1u1 + k2u3u2
u2 = k1u1 − k2u3u2 − 2k3u2
u3 = 2k3u2.
12
2 Explizite Einschrittverfahren
2.1 Explizite Runge-Kutta-Verfahren(2.1) DefinitionZur Funktion f ∈ C([t0, t0 + T ]×G,RM) definieren wir einen Fluss
φ : D ⊂ [t0, t0 + T ]× R≥0 ×G → G
φ(t, τ, z) := v(t+ τ),
wobei v ∈ C([t, t+ τ ], G) Lösung der Anfangswertaufgabe
v = f(s, v), s ∈ (t, t+ τ)
v(t) = z
ist.Dabei ist D die Menge der Werte (t, τ, z), für die φ wohldefiniert ist.
Im Folgenden setzen wir voraus, dass f eine L-Bedingung erfüllt. Dann ist der Fluss ein-deutig in einer Umgebung von t0×0×G ⊂ [t0, t0 +T ]×R≥0×G definiert, da nach(1.11) die Anfangswertaufgabe in diesem Fall eine eindeutige Lösung (zumindest für einkleines Zeitintervall) besitzt.
(2.2) DefinitionEin explizites Einschrittverfahren wird durch die Verfahrensfunktion
ψ : [t0, t0 + T ]× R≥0 ×G→ RM
definiert. Sie bestimmt den diskreten Fluss
φτ (t, τ, z) = z + τψ(t, τ, z).
Zu Schrittweiten τn = tn − tn−1 und u0 ∈ G definiere
un = un−1 + τnψ(tn−1, τn, un−1) = φτ (tn−1, τn, u
n−1).
Setze außerdem |τ | := maxn=1,...,N |τn|.
BeispielA) Explizites Euler-Verfahren
ψ(t, τ, z) = f(t, z).
B) Verfahren von Heun
k1 = f(t, z)
k2 = f(t+ τ, z + τk1)
ψ(t, τ, z) =1
2k1 +
1
2k2.
13
C) Klassisches Runge-Kutta-Verfahren
k1 = f(t, z)
k2 = f(t+
τ
2, z +
τ
2k1
)k3 = f
(t+
τ
2, z +
τ
2k2
)k4 = f(t+ τ, z + τk3)
ψ(t, τ, z) =1
6k1 +
1
3k2 +
1
3k3 +
1
6k4.
BemerkungIm Spezialfall f(t, z) = f(t) gilt
u(tn)− u(tn−1) =
∫ tn
tn−1
f(t)dt
≈
τnf(tn−1), Expl. Euler A)
τn
(12
(f(tn−1) + f(tn)
))Trapezregel B)
τn16
(f(tn−1) + 4f
(tn−1+tn
2
)+ f(tn)
)Simpson-Regel C)
(2.3) DefinitionWir definieren
a) den globalen Fehler für eine Lösung u von (1.1) und eine Lösung un von (2.2) durch
en := u(tn)− un;
b) den lokalen Diskretisierungsfehler einer Lösung u von (1.1) durch
gn =1
τn
(u(tn)− u(tn−1)
)− ψ(tn−1, τn, u(tn−1)).
Bemerkunga) Der globale Fehler hängt von der Lösung im Interval [t0, tn] ab.
b) Der lokale Diskretisierungsfehler misst den Unterschied von der Tangente an die Lö-sung zur Approximation mit der Verfahrensfunktion. Es gilt
gn = g(tn−1, τn, u(tn−1)) mit
g(t, τ, z) =1
τ(φ(t, τ, z)− z)− 1
τ(φτ (t, τ, z)− z).
(2.4) DefinitionEin Einzelschrittverfahren heißt
a) konsistent, wenn für alle t ∈ [t0, t0 + T ], z ∈ G
limτ→0
g(t, τ, z) = 0,
14
b) konsistent von der Ordnung p, wenn
|g(t, τ, z)| = O(τ p),
c) konvergent, wenn
limτ→0
maxn|u(tn)− un| = 0,
d) konvergent von der Ordnung p, wenn
maxn|u(tn)− un| = O(|τ |p).
Dabei wird angenommen, dass die Lösung u hinreichend glatt ist.
BeispielA) Sei u zweimal stetig differenzierbar. Dann gilt:
Die Konsistenzordnung des expliziten Euler-Verfahrens ist p = 1:
gn =1
τ(u(tn)− u(tn−1))− f(tn−1, u(tn−1))
=1
τ
∫ tn
tn−1
(f(t, u(t))− f(tn−1, u(tn−1))
)dt
=1
τ
∫ tn
tn−1
(u(t)− u(tn−1)
)dt =
1
τ
∫ tn
tn−1
(∫ t
tn−1
u(s)ds
)dt
≤ 1
τ‖u‖∞
∫ tn
tn−1
(∫ t
tn−1
ds
)dt =
τ
2‖u‖∞.
B) Die Konsistenzordnung des Verfahrens von Heun ist p = 2.
C) Das klassische Runge-Kutta-Verfahren hat Konsistenzordnung p = 4.
(2.5) Hilfssatz (Diskretes Gronwall-Lemma)Seien δn > 0, ηn, zn ≥ 0 (n = 0, . . . , N ) mit zn ≤ (1 + δn)zn−1 + ηn (n = 1, . . . , N ).
Dann gilt
zn ≤ z0 exp(∆n) +Mn
(exp(∆n)− 1
),
wobei
∆n =n∑k=1
δk, Mn = maxk=1,...,n
ηkδk.
15
Beweis. Wir führen einen Induktionsbeweis über n.n = 1: Es gilt wegen exp(x)− 1 ≥ x
z1 ≤ (1 + δ1)z0 + η1 ≤ exp(∆1)z0 + δ1M1
≤ z0 exp(∆1) +M1
(exp(∆1)− 1
).
n− 1 7→ n:
zn ≤ (1 + δn)zn−1 + ηn
≤ (1 + δn)(z0 exp(∆n−1) +Mn−1
(exp(∆n−1)− 1
))+ δn
ηnδn
≤ exp(δn) exp(∆n−1)z0 +Mn
((1 + δn)
(exp(∆n−1)− 1
)+ δn
)≤ exp(∆n)z0 +Mn
(exp(∆n)− 1
)Damit folgt die Behauptung.
(2.6) SatzWenn ein Λ > 0 existiert mit
|ψ(t, τ, z)− ψ(t, τ, y)| ≤ Λ|z − y| , y, z ∈ G, t0 ≤ t ≤ t0 + T, 0 ≤ τ ≤ maxk=1,...,n
τk ,
dann gilt
|u(tn)− un| ≤ |u(t0)− u0| exp(Λ(tn − t0)) + maxk=1,...,n
|gk|exp(Λ(tn − t0))− 1
Λ.
Beweis. Es gilt
en = u(tn)− un
= en−1 + u(tn)− u(tn−1)− un + un−1
= en−1 + τn1
τn
(u(tn)− u(tn−1)
)− τnψ(tn−1, τn, u
n−1)
= en−1 + τn
[1
τn
(u(tn)− u(tn−1)
)− ψ(tn−1, τn, u(tn−1))
+ψ(tn−1, τn, u(tn−1))− ψ(tn−1, τn, un−1)
]= en−1 + τng
n + τn(ψ(tn−1, τn, u(tn−1))− ψ(tn−1, τn, u
n−1)).
Da ψ eine L-Bedingung erfüllt, folgt nun
|en| ≤ |en−1|+ τn|gn|+ τnΛ|en−1| = (1 + τnΛ)|en−1|+ τn|gn|.
Setze δn := τnΛ, zn := |en| und ηn := τn|gn| in (2.5). Dann folgt
|en| ≤ |e0| exp(Λ(tn − t0)) + maxk=1,...,n
|gk| 1Λ
(exp(Λ(tn − t0))− 1
).
16
AnwendungBei fester Schrittweite τ gelte |gn| ≤ Cτ p und e0 = 0. Dann folgt
|en| ≤ Cτ p(
exp(TΛ)− 1
Λ
)= Cτ p = O(τ p),
|e1| ≤ Cτ p(
exp(τ1Λ)− 1
Λ
)≤ Cτ p
(τ1Λ + 1
2(τ1Λ)2 + . . .
Λ
)= O(τ p+1).
Das bedeutet, dass die Konsistenzordnung bei Betrachtung eines einzelnen Schrittes umeine Größenordnung besser ist als bei mehreren Schritten.
(2.7) FolgerungEin Verfahren der Konsistenzordnung p ist konvergent von der Ordnung p (falls der An-fangsfehler u0 − u(t0) ebenfalls von der Ordnung p ist).
BemerkungFür das explizite Euler-Verfahren gilt Λ = L.
(2.8) DefinitionEin allgemeines (explizites) Runge-Kutta-Verfahren mit S Stufen wird durch
Stützstellen c ∈ RS (explizit c1 = 0),
Gewichte b ∈ RS
S∑i=1
bi = 1,
Koeffizienten A ∈ RS,S (explizit asr = 0 für s ≤ r)
und
ks := f
(t+ csτ, z + τ
S∑r=1
asrkr
),
ψ(t, τ, z) :=S∑s=1
bsks
definiert (für explizite Verfahren gilt ks = f
(t+ csτ, z + τ
s−1∑r=1
asrkr
), s = 1, ..., S).
BezeichnungenZur Beschreibung von Runge-Kutta-Verfahren verwenden wir das Butcher-Schema:
c AbT
Im expliziten Fall sieht das Schema folgendermaßen aus
0 0
c2 a21. . .
...... . . . . . .
cS aS1 . . . aS,S−1 0b1 . . . . . . . . . . bS
17
BemerkungDie Stützstellen cs und die Gewichte bs definieren eine Quadratur in [0, 1].
BeispielA) Explizites Euler-Verfahren (S = 1, p = 1)
0 01
B) Verfahren von Heun (S = 2, p = 2)
0 01 1 0
12
12
C) Klassisches Runge-Kutta-Verfahren (S = 4)
0 012
12
012
0 12
01 0 0 1 0
16
26
26
16
(2.9) Lemmaa) Ein explizites Runge-Kutta-Verfahren ist genau dann konsistent, wenn
∑Ss=1 bs = 1
gilt.
b) Wenn ein explizites Runge-Kutta-Verfahren die Konsistenzordnung p hat, gilt S ≥ p.
Beweis. zu a): Es gilt
limτn→0
gn = u(tn)− ψ(tn, 0, u(tn)) = u(tn)−S∑s=1
bsf(tn, u(tn))
= u(tn)
(1−
S∑s=1
bs
).
Damit gilt limτn→0
gn = 0 genau dann, wenn∑S
s=1 bs = 1 erfüllt ist.
zu b) Betrachte f(t, z) = z. Dann gilt
k1 = z,
k2 = z + τa21z,
k3 = z + τa31z + τa32(z + τa21z) =[1 + τ(a31 + a32) + τ 2a32a21
]z.
Induktiv zeigt man
S∑s=1
bsks = PS−1(τ)z, PS−1 ∈ PS−1.
18
Betrachte nun die Anfangswertaufgabe u = u, u(0) = 1 mit der expliziten Lösung u(t) =exp(t). Dann folgt
gn =1
τn
(exp(tn)− exp(tn−1)
)− PS−1(τn) exp(tn−1)
=
[1
τn
(exp(τn)− 1
)− PS−1(τn)
]exp(tn−1)
=
[∞∑k=1
τ k−1n
k!− PS−1(τn)
]exp(tn−1).
Also ist O(τSn ) optimal.
BemerkungFür die maximale Konsistenzordnung p von expliziten Runge-Kutta-Verfahren mit S Stufengilt
p 1 2 3 4 5 6 8 10S 1 2 3 4 6 7 11 18
AutonomisierungEine Anfangswertaufgabe
u = f(t, u), u(t0) = u0
ist äquivalent zu der Aufgabe
y = f(y), y(t0) = y0,
wobei y(t) =
(u(t)t
)∈ RM+1, f(y) =
(f(t, u(t))
1
)und y0 =
(u0
t0
)gelten.
Beachte, dass f nicht mehr explizit von t abhängt. Solche Anfangswertaufgaben heißenautonom.
Zu einem Runge-Kutta-Verfahren sei ψ die Verfahrensfunktion zu f und ψ die Verfahrens-funktion zu f .
(2.10) LemmaEin Runge-Kutta-Verfahren (mit bs 6= 0) erfüllt genau dann
(ψ(t, τ, z)
1
)= ψ
(t, τ,
(zt
)),
wenn es konsistent ist und wenn cs =∑S
r=1 asr für s = 1, . . . , S gilt.
(Invarianz gegen Autonomisierung)
19
Beweis. Es gilt ks = f(t+ csτ, z + τ
∑Sr=1 asrkr
)und damit
(ksΘs
)= f
((zt
)+ τ
S∑r=1
asr
(krΘr
))
=
(f(t+ τ
∑Sr=1 asrΘr, z + τ
∑Sr=1 asrkr
)1
)
Nun folgen Θs = 1 und(∑S
s=1 bsks1
)=∑S
s=1 bs
(ks1
)und damit folgen cs =
∑Sr=1 asr
und ks = ks.
Im Folgenden gelte stets cs =∑S
r=1 asr.
(2.11) SatzEin Runge-Kutta-Verfahren ist genau dann konsistent von der Ordnung
p = 1, wennS∑s=1
bs = 1, (1)
p = 2, wenn zusätzlichS∑s=1
bscs =1
2, (2)
p = 3, wenn zusätzlichS∑s=1
bsc2s =
1
3, (3)
∑r,s
bsasrcr =1
6, (4)
p = 4, wenn zusätzlichS∑s=1
bsc3s =
1
4, (5)
∑r,s
bscsasrcr =1
8, (6)
∑r,s
bsasrc2r =
1
12, (7)
∑r,s,t
bsasrartct =1
24. (8)
Beweis für p = 2. Es sei ohne Einschränkungen die Differentialgleichung autonom, alsou = f(u). Dann gilt
u(t) =d
dtf(u(t)) = f ′(u(t))u(t) = f ′(u(t))f(u(t)) =: f ′f
20
und für z = u(t) gelten
ks = f
(z + τ
∑r
asrkr
)= f(z) + τf ′(z)
∑r
asrkr +O(τ 2)
= f + τf ′∑r
asrf +O(τ 2) und
g =1
τ
(u(t+ τ)− u(t)
)−∑s
bsks
= f +1
2f ′fτ −
∑s
bs
(f + τf ′
∑r
asrf
)+O(τ 2).
Setze cs :=∑
r asr. Dann folgt schließlich
g = O(τ 2) ⇔ f
(1−
∑s
bs
)= 0 und f ′f
(1
2−∑s
bscs
)= 0.
Beispiel (Klassisches Runge-Kutta-Verfahren)Es gilt c1 = 0, c2 = c3 = 1
2, c4 = 1, b1 = 1
6, b2 = b3 = 2
6, b4 = 1
6. Damit sind sofort
(1), (2), (3), (5) in (2.11) erfüllt. Ferner folgt aus (4) und (6)
(4) : b3a32c2 + b4(a42c2 + a43c3) =1
6,
(6) : b3c3a32c2 + b4c4(a42c2 + a43c3) =1
8
und damit a32 = 12
und a42c2 + a43c3 = 12. Da nach (8) die Gleichung b4a43a32c2 = 1
24
gilt, folgt a43 = 1 und damit a42 = 0. Schließlich ergibt sich wegen∑S
r=1 asr = cs nocha41 = 0.
(2.12) LemmaWenn f eine L-Bedingung erfüllt, dann erfüllt die Verfahrensfunktion ψ eines explizitenRunge-Kutta-Verfahrens eine Λ-Bedingung.
Beweis. Setze ks := f (z + τ∑
r asrkr) und ks := f(z + τ
∑r asrkr
). Dann folgt
|ψ(t, τ, z)− ψ(t, τ, z)| =
∣∣∣∣∣S∑s=1
bsks −S∑s=1
bsks
∣∣∣∣∣ ≤S∑s=1
|bs||ks − ks|.
Außerdem gilt
|k1 − k1| = |f(z)− f(z)| ≤ L|z − z|,|k2 − k2| = |f(z + τa21k1)− f(z + τa21k1)| ≤ L|z + τa21k1 − (z + τa21k1)|
≤ L(1 + τ |a21|L)|z − z|.
Durch sukzessives Fortführen erhält man dann für alle s = 1, . . . , S und τ ∈ (0, τ0)
|ks − ks| ≤ L(1 + ‖A‖∞τ0L+ ‖A‖2
∞τ20L
2 + . . .)︸ ︷︷ ︸
=C
|z − z|.
woraus mit Λ := C∑
s |bs| die Behauptung folgt.
21
2.2 Qualitätskontrolle bei Einschrittverfahren
Der lokale Diskretisierungsfehler lässt sich durch Vergleich von zwei Verfahrensfunktio-nen ψ, ψ mit verschiedener Ordnung abschätzen.Betrachte dazu zwei Verfahren mit
g(t, τ, z) =1
τ
(φ(t, τ, z)− z
)− ψ(t, τ, z) = O(τ p),
g(t, τ, z) =1
τ
(φ(t, τ, z)− z
)− ψ(t, τ, z) = O(τ p−1).
Damit folgt
g(t, τ, z) = ψ(t, τ, z)− ψ(t, τ, z) +O(τ p).
Ziel ist es, die Schrittweite so zu wählen, dass der lokale Diskretisierungsfehler unterhalbeiner vorgegebenen Toleranz bleibt.
(2.13) Definition (Eingebettete Runge-Kutta-Verfahren)Ein eingebettetes Runge-Kutta-Verfahren definiert zwei Verfahrensfunktionen ψ und ψ mit
c AbT
bT
ks = f(t+ τcs, z + τ
∑s−1r=1 asrkr
)ψ(t, τ, z) =
∑Ss=1 bsks, ψ(t, τ, z) =
∑Ss=1 bsks.
Dabei wird der Diskretisierungsfehler durch
η = ψ(t, τ, z)− ψ(t, τ, z) =S∑s=1
(bs − bs)ks
geschätzt.
BeispielFehlberg-Trick: k5 aus Schritt n ist k1 aus Schritt n+ 1.
012
12
12
0 12
1 0 0 11 1
626
26
16
16
26
26
16
016
26
26
0 16
η = ψ(t, τ, z)− ψ(t, τ, z) =1
6(k4 − k5)
Allgemein kann man bei konstanter Schrittweite und komplexem f den Rechenaufwandreduzieren, indem man das Verfahren so konstruiert, dass im Folgeschritt möglichst vieleAuswertungen von f wiederverwendet werden können.
22
AlgorithmusS0) Wähle ε > 0, τ > 0, θ ∈ (0, 1), M > 0, τ > τ > 0.
Setze t := t0, u := u0, k1 = f(t, u).
S1) Setze
k2 := f(t+
τ
2, u+
τ
2k1
)k3 := f
(t+
τ
2, u+
τ
2k2
)k4 := f (t+ τ, u+ τk3)
k5 := f(t+ τ, u+
τ
6(k1 + 2k2 + 2k3 + k4)
)η :=
1
6(k4 − k5)
S2) Falls |η| < ε, setze t := t+ τ , u := u+ τ6(k1 + 2k2 + 2k3 + k4), k1 := k5.
S3) Falls t ≥ t0 + T oder |u| > M : STOP
S4) Setze τ := θ 3
√ε|η|τ .
Falls τ > τ setze τ := τ und falls τ < τ , setze τ := τ (oder STOP).
Gehe zu S1).
Zur Schrittweitenvorhersage
Sei |ηn| = |ψ(tn−1, τn, un−1)− ψ(tn−1, τn, u
n−1)| = |gn − gn| = Cτ p−1n +O(τ p).
Damit folgt C ≈ |ηn|τp−1n
.
Wähle τn+1 so, dass im nächsten Schritt |ηn+1| ≈ ε = Cτ p−1n+1 ≈
|ηn|τp−1n
τ p−1n+1 gilt. Daraus
ergibt sich die neue Schrittweite τn+1 ≈ τn p−1
√ε|ηn| .
BemerkungEs gilt für η(t, τ, z) = ψ(t, τ, z)− ψ(t, τ, z):
η(t, τ, z)
g(t, τ, z)=Cτ p−1 +O(τ p)
Cτ p−1−→ 1 (τ → 0),
d.h. der Fehlerschätzer ist asymptotisch exakt.
Fehlerschätzer durch Extrapolation
Vergleiche un = un−1 + τnψ(tn−1, τn, un−1) mit dem Ergebnis mit halber Schrittweite:
un−12 = un−1 +
τn2ψ(tn−1,
τn2, un−1
)un = un−
12 +
τn2ψ(tn−1 +
τn2,τn2, un−
12
)η = un − un. (p = 1)
23
Extrapolationsverfahren
Für glatte Funktionen a : R→ RM mit
a(τ) = a(0) + ap(τ)τ p + ap+1(τ)τ p+1 + · · ·+O(τ p+k)
sei a(τ) für τ > 0 berechenbar, nicht aber a(0).
Berechne a(τj) für τ0 > τ1 > · · · > τk > 0 und ein Polynom P ∈ Pp+k mit P (τj) = a(τj),(ddt
)jP (0) = 0, j = 1, . . . , p− 1 (Hermiteinterpolation). Dann gilt
P (0) = a(0) +O(τ p+k).
BeispielEs sei k = 1, τ0 = τ und τ1 = τ
2. Dann gilt
a(τ) = a(0) + ap(τ)τ p +O(τ p+1)
a(τ
2
)= a(0) + ap
(τ2
)(τ2
)p+O(τ p+1).
Man rechnet nach1
a(0) =1
2p − 1
(2pa(τ
2
)− a(τ)
)+O(τ p+1).
Anwendung (Numerische Differentiation)Wir betrachten a(τ) = 1
τ(f(t + τ) − f(t)) mit a(0) = f ′(t). Sei nun zunächst f ∈ C3.
Dann gilt
a(τ) =1
τ
(f(t) + f ′(t)τ +
1
2f ′′(t)τ 2 +O(τ 3)− f(t)
)= f ′(t) +
1
2τf ′′(t) +O(τ 2).
Also folgt wegen p = 1 und obiger Formel für a(0)
f ′(t) = 2a(τ
2
)− a(τ) +O(τ 2)
=1
τ
(4f(t+
τ
2
)− 3f(t)− f(t+ τ)
)+O(τ 2).
Für f ∈ C5 folgt entsprechend mit a(τ) = 12τ
(f(t+ τ)− f(t− τ)
)und a(0) = f ′(t)
f ′(t) =1
6τ
(4f(t+
τ
2
)− 4f
(t− τ
2
)+ f(t+ τ)− f(t− τ)
)+O(τ 4).
Also kann man das Problem der Auslöschung bei der Approximation von Ableitungendurch Taylor-Entwicklungen (teilweise) umgehen.
1Vgl. Romberg-Quadratur aus Numerik I.
24
BezeichnungenWir verwenden folgende Schreibweisen:
Df = f ′ (Jacobimatrix)
Df(t, z) =(D1f(t, z)︸ ︷︷ ︸∈RM,1
|D2f(t, z)︸ ︷︷ ︸∈RM,M
)(2.14) LemmaSei f ∈ Ck([t0, t0 +T ]×G,RM) und u ∈ C1([t0, t0 +T ], G) eine Lösung von u = f(t, u).Dann gilt u ∈ Ck+1([t0, t0 + T ], G).
Beweis. Es gilt formal
u(t) =d
dtf(t, u(t)) = D1f(t, u(t)) +D2f(t, u(t))u(t) =: F2(t, u(t), u(t))
...u(t) =
d
dtF2(t, u(t), u(t))
= D1F2(t, u(t), u(t)) +D2F2(t, u(t), u(t))u(t) +D3F2(t, u(t), u(t))u(t)
=: F3(t, u(t), u(t), u(t))
usw.
Nun wird die Existenz der(ddt
)iu(t) induktiv durch die Stetigkeit der Fi gezeigt.
(2.15) SatzEs sei f ∈ C([t0, t0 + T ] × G,RM) glatt und u ∈ C1([t0, t0 + T ], G) eine Lösung derAnfangswertaufgabe (1.1)
u = f(t, u), u(t0) = u0.
Sei außerdem ψ eine Verfahrensfunktion der Konsistenzordnung p. Zu τ ∈ (0, τ0) definiereauf dem Gitter ∆τ := t0 + nτ : n ∈ N0, nτ ≤ T für t ∈ ∆τ
uτ (t0) := u0,
uτ (t+ τ) := uτ (t) + τψ(t, τ, uτ (t)).
Dann existieren glatte Funktionen ap, . . . , ap+k ∈ C1([t0, t0 + T ],RM), sodass
uτ (t) = u(t) + ap(t)τp + ap+1(t)τ p+1 + · · ·+O(τ p+k)
für alle t ∈ ∆τ , τ ∈ (0, τ0) und alle k ∈ N0 gilt.
Beweis für skalare Gleichungen und das explizite Euler-Verfahren. In diesem Fall giltM =1, p = 1, k = 1, und ψ(t, τ, z) = f(t, z). Wähle τ ∈ (0, τ0) fest und setze tn = t0 + nτ .Dann gilt für den lokalen Diskretisierungsfehler
gn =1
τ
(u(tn)− u(tn−1)
)− f(tn−1, u(tn−1))
=1
τ
(u(tn−1)τ +
1
2u(tn−1)τ 2 +O(τ 3)
)− u(tn−1)
=1
2u(tn−1)τ +O(τ 2).
25
Dann folgt für den globalen Fehler
en = u(tn)− uτ (tn) = en−1 + u(tn)− u(tn−1)− τf(tn−1, uτ (tn−1))
= en−1 + τgn + τ(f(tn−1, u(tn−1))− f(tn−1, uτ (tn−1))
)= en−1 +
1
2τ 2u(tn−1) + τD2f(tn−1, u(tn−1))en−1 +O(τ 3) +O(τ |en−1|2).
Nun gilt für en := 1τen
en = en−1 + τ
(D2f(tn−1, u(tn−1))en−1 − 1
2u(tn−1)
)+ τ 2Rn−1,
wobei Rn−1 = O(1 + |en−1|) = O(1).Definiere nun ap ∈ C1([t0, t0 + T ],RM) als Lösung der Anfangswertaufgabe
ap(t) =[D2f(t, u(t))
]ap(t)−
1
2u(t),
ap(t0) = 0.
Damit folgt en = en−1 + τ 2ap(tn−1) + τ 3Rn−1 und daraus mit e0 = 0
en =n∑k=1
(ek − ek−1)
= τn∑k=1
τ ap(tk−1) + τ 2
n∑k=1
τRk−1
= τap(tn) +O(τ 2)‖ap‖∞ +O(τ 2)T maxk|Rk|
= τap(tn) +O(τ 2)
Damit gilt die Behauptung.
BemerkungDie Entwicklung konvergiert für festes k und τ → 0, aber im Allgemeinen nicht für festest, τ und k →∞.
Anwendung (Neville-Schema)Zu ψ und k ≥ 1 definiere φkτ (t, τ, z) := zk mit z0 = z, zj = zj−1 + τ
kψ(t+ j−1
kτ, τ
k, zj−1
)(j = 1, . . . , k). Dann gilt
a) un = 12p−1
(2pφ2
τ (t, τ, un−1) − φτ (t, τ, un−1)
)definiert ein Verfahren mit der Ordnung
p+ 1.
b) ηn = 1τ
12p−1
(φ2τ (t, τ, u
n−1) − φτ (t, τ, un−1)
)definiert einen Fehlerschätzer mit gn =
ηn +O(τ p+1).
26
Algorithmus (Extrapoliertes Euler-Verfahren)S0) Wähle ε > 0, τ > 0, k ≥ 0 und setze u := u0 und t := t0.
S1) Berechne für k = 1
U00 = φτ (t, τ, z)
U10 = φ2τ (t, τ, z) U11 = 2U10 − U00.
S2) Berechne η = 1τ
12k−1
(Uk,k−1 − Uk−1,k−1).
Wenn |η| < ε oder k = k, setze u := Ukk und t := t+ τ und gehe zu S1).
S3) Setze k := k + 1 und berechne
Uk0 = φ2k
τ (t, τ, z),
Ukj =1
2k+1−j − 1(Uk,j−1 − Uk−1,j−1) (j = 1, . . . , k).
Gehe zu S2).
27
3 Lineare Mehrschrittverfahren(3.1) DefinitionEs sei ∆ = tn = t0 + nτ, n = 0, . . . , N ein äquidistantes Gitter in [t0, t0 + T ] mitSchrittweite τ = T
Nund seien u0, . . . , uk−1 Näherungen für die Lösung der Anfangswert-
aufgabe
u(t) = f(t, u(t)), u(t0) = u0
zu den Zeitpunkten t0, . . . , tk−1.Dann definiert ein lineares Mehrschrittverfahren un, n = k, . . . , N rekursiv durch
k∑i=0
αk−iun−i = τ
k∑i=0
βk−ifn−i
mit f j = f(tj, uj). Das Verfahren ist durch die Koeffizienten α0, . . . , αk und β0, . . . , βk
bestimmt.Es gelte im Folgenden ohne Einschränkungen αk = 1.
BemerkungFür βk = 0 ist das Verfahren explizit, ansonsten implizit.
Beispiela) Adams-Bashforth-Verfahren (explizit)
Auf [tn−1, tn] ist die Lösung der Anfangswertaufgabe (1.1) äquivalent zu
u(tn) = u(tn−1) +
∫ tn
tn−1
f(t, u(t))dt.
Die Idee des Verfahrens ist es, f(t, u(t)) in [tn−1, tn] durch ein Polynom P ∈ Pk−1 zuapproximieren, wobei P (tn−i) = fn−i für i = 1, . . . , k gelten soll. Wählt man für dieDarstellung von P die Lagrange-Basis, also
P (t) =k∑i=1
fn−iLi(t), Li(t) =k∏
j=1,j 6=i
t− tn−jtn−i − tn−j
,
so folgt nach Ersetzen von f(t, u(t)) durch das Interpolationspolynom P
un = un−1 +
∫ tn
tn−1
P (t)dt
= un−1 +
∫ tn
tn−1
k∑i=1
fn−iLi(t)dt
= un−1 +k∑i=1
fn−i(∫ tn
tn−1
Li(t)dt
)︸ ︷︷ ︸
=:τβk−i
.
28
Also gilt
αk = 1, αk−1 = −1, αk−i = 0, i > 1, βk = 0.
Für i = 1, ..., k gilt
τβk−i =
∫ tn
tn−1
Li(t)dt = τ
∫ 1
0
Li(tn−1 + sτ)ds
= τ
∫ 1
0
k∏j=1,j 6=i
tn−1 + sτ − tn−jtn−i − tn−j
ds
= τ
∫ 1
0
k∏j=1,j 6=i
(n− 1 + s− (n− j))τ(n− i− (n− j))τ
ds = τ
∫ 1
0
k∏j=1,j 6=i
s− 1 + j
j − ids︸ ︷︷ ︸
=βk−i
.
Im Fall k = 1 ergibt sich beispielsweise un = un−1+τfn−1 (explizites Euler-Verfahren)und im Fall k = 4 gilt
un = un−1 +τ
24(55fn−1 − 59fn−2 + 37fn−3 − 9fn−4).
b) Adams-Moulton-Verfahren (implizit)
Approximiere f(t, u(t)) in [tn−1, tn] durch P ∈ Pk mit P (tn−i) = fn−i, i = 0, . . . , k.Dann folgt
ak = 1, ak−1 = −1, ak−i = 0, i > 1,
βk−i =
∫ 1
0
k∏j=0,j 6=i
s− 1 + j
j − ids, i = 0, . . . , k.
Für k = 0 erhält man un = un−1 + τfn (implizites Euler-Verfahren) und für k = 3 gilt
un = un−1 +τ
24(9fn + 19fn−1 − 5fn−2 + fn−3).
c) Nyström-Verfahren (explizit)
Approximiere f(t, u(t)) in [tn−2, tn] durch P ∈ Pk−1 mit P (tn−i) = fn−i, i = 1, . . . , k.Dann folgt
ak = 1, ak−1 = 0, ak−2 = −1, ak−i = 0, i > 2, βk = 0,
βk−i =
∫ 2
0
k∏j=1j 6=i
s− 2 + j
j − ids, i = 1, . . . k.
Im Fall k = 1 ergibt sich un = un−2 + 2τfn−1 (explizite Mittelpunktsregel).
29
d) Backward-Differentiation-Formulas (BDF) (implizit)
Diesmal wird u (und nicht f ) in [tn−k, tn] durch ein Polynom P ∈ Pk mit P (tn−i) =un−i, i = 0, . . . , k approximiert. Mit der Lagrange-Basis lässt sich P dann folgender-maßen darstellen
P (t) =k∑i=0
un−iLi(t).
Nun fordert man zusätzlich P (tn) = fn, d.h.
k∑i=0
un−iτLi(tn) = τfn.
Damit folgt
βk = 1, αk−i = τLi(tn), i = 0, . . . , k, βk−i = 0, i > 0.
Für k = 1 ergibt sich un = un−1 + τfn (implizites Euler-Verfahren) und im Fall k = 2gilt
3
2un − 2un−1 +
1
2un−2 = τfn.
Alternative Herleitung
Zu u = f(t, u) und tj = t0 + jτ definiere
f j := f(tj, u(tj)) = f [tj] und für j > i
f [ti, . . . , tj] :=1
tj − ti(f [ti+1, . . . , tj]− f [ti, . . . , tj−1]
).
Setze
∇0f j := f j, ∇kf j := ∇k−1f j −∇k−1f j−1 (k ∈ N).
In der Übung wurde gezeigt, dass dann auf einem äquidistanten Gitter
∇kf j = k!τ kf [tj−k, . . . , tj]
gilt.
Beispiela) Adams-Bashforth
Approximiere f(t, u(t)) durch
P (t) = fn−1 + f [tn−2, tn−1](t− tn−1)
+ · · ·+ f [tn−k, . . . , tn−1](t− tn−1) · · · (t− tn−k+1),
30
d.h. P (tj) = f j , j = n− k, . . . , n− 1. Dann gilt für s ∈ [0, 1]
P (tn−1 + sτ) = ∇0fn−1 + s∇1fn−1 +s(s+ 1)
2∇2fn−1 + · · ·
=k−1∑i=0
(−1)i(−si
)∇ifn−1,
wobei(s0
)= 1 und
(si
)=∏i
j=1s−(j−1)
j.
Dann folgt
un = un−1 +
∫ tn
tn−1
P (t)dt = un−1 + τ
∫ 1
0
P (tn−1 + τs)ds
= un−1 + τ
k−1∑i=0
γi∇ifn−i mit γi = (−1)i∫ 1
0
(−si
)ds.
b) Adams-Moulton
un = un−1 + τk−1∑i=0
γi∇ifn mit γi = (−1)i∫ 1
0
(1− si
)ds.
c) Backward-Differentiation-Formulas
Approximiere u in [tn−k, tn] durch
P (tn + sτ) =k∑i=0
(−1)i(−si
)∇iun,
d.h. P (tj) = uj für j = n− k, . . . , n. Es gilt
d
ds(−1)i
(−si
)∣∣∣∣s=0
=
0, i = 0,1i, i > 0
und damit folgt
P (tn) =1
τ
k∑i=1
1
i∇iun
und somit
k∑i=1
1
i∇iun = τfn.
Für k = 2 ergibt sich
1 · (un − un−1) +1
2(un − 2un−1 + un−2) =
3
2un − 2un−1 +
1
2un−2 = τfn .
31
(3.2) LemmaFalls f eine Lipschitz-Bedingung mit L erfüllt und τL|βk| < 1 gilt, dann konvergiert zujedem Startwert un,0 die Iteration
αk︸︷︷︸=1
un,j = −k∑i=1
αk−iun−i + τβkf(tn, u
n,j−1) + τ
k∑i=1
βk−ifn−i
für j →∞ gegen die Lösung un des Mehrschrittverfahrens.
Beweis. Für explizite Verfahren folgt mit βk = 0 sofort un = un,1.Sei also βk 6= 0. Dann gilt
|un,j+1 − un,j| = |τβkf(tn, un,j)− τβkf(tn, u
n,j−1)| ≤ τ |βk|L︸ ︷︷ ︸<1
|un,j − un,j−1|.
Mit dem Banach’schen Fixpunktsatz folgen dann die Konvergenz und die Eindeutigkeitder Lösung.
(3.3) DefinitionZu u ∈ C1([t0, t0 + T ], G) definieren wir den lokalen Diskretisierungsfehler durch
gn(u) =1
τ
k∑i=0
αk−iu(tn−i)−k∑i=0
βk−iu(tn−i).
Häufig schreiben wir gn anstelle von gn(u).
(3.4) LemmaSei u eine analytische Funktion2. Dann gilt
gn(u) =1
τ
∞∑j=0
Cjτj
(d
dt
)ju(tn−k),
wobei
C0 =k∑i=0
αi, Cj =1
j!
k∑i=0
ijαi −1
(j − 1)!
k∑i=0
ij−1βi, j > 0.
Beweis. Wir betrachten die Taylor-Entwicklung von u um den Entwicklungspunkt tn−k.Dann gilt
u(tn−i) =∞∑j=0
1
j!
(d
dt
)ju(tn−k) (k − i)jτ j︸ ︷︷ ︸
=(tn−i−tn−k)j
u(tn−i) =∞∑j=1
1
(j − 1)!
(d
dt
)ju(tn−k)(k − i)j−1τ j−1.
2 Eine analytische Funktion lässt sich lokal durch eine konvergente Potenzreihe darstellen.
32
Damit folgt
gn(u) =1
τ
k∑i=0
αk−iu(tn−i)−k∑i=0
βk−iu(tn−i)
=1
τ
(k∑i=0
αk−i
)u(tn−k) +
1
τ
∞∑j=1
([k∑i=0
αk−i1
j!
(d
dt
)ju(tn−k)(k − i)jτ j
]
−
[τ
k∑i=0
βk−i1
(j − 1)!
(d
dt
)ju(tn−k)(k − i)j−1τ j−1
])
=1
τ
(k∑i=0
αi
)u(tn−k) +
1
τ
∞∑j=1
[(1
j!
k∑i=0
αk−i(k − i)j
− 1
(j − 1)!
k∑i=0
βk−i(k − i)j−1
)τ j(d
dt
)ju(tn−k)
]
=1
τC0τ
0
(d
dt
)0
u(tn−k) +1
τ
∞∑j=1
Cjτj
(d
dt
)ju(tn−k)
=1
τ
∞∑j=0
Cjτj
(d
dt
)ju(tn−k).
Somit gilt die Behauptung.
(3.5) DefinitionEin Mehrschrittverfahren heißt konsistent von der Ordnung p, falls
C0 = C1 = · · · = Cp = 0 und Cp+1 6= 0.
Cp+1 heißt Fehlerkonstante.
BemerkungFür ein lineares Mehrschrittverfahren der Ordnung p und P ∈ Pp gilt nach (3.4)
gn(P ) =1
τ
p∑j=0
Cjτj
(d
dt
)jP (tn−k) +
1
τ
∞∑j=p+1
Cjτj
(d
dt
)jP (tn−k)︸ ︷︷ ︸
=0
= 0.
(3.6) LemmaEin lineares Mehrschrittverfahren ist konsistent von der Ordnung p, wenn der lokale Dis-kretisierungsfehler für Polynome vom Grad p verschwindet, d.h. gn(P ) = 0 für P ∈ Pp.
Beweis. Wir zeigen |gn(u)| = O(τ p) für hinreichend glatte Lösungen u.Dazu betrachten wir die Taylor-Entwicklung von u an der Stelle tn−k
u(t) =
p∑j=0
1
j!
(d
dt
)ju(tn−k)(t− tn−k)j +R(t) = P (t)︸︷︷︸
∈Pp
+R(t)
33
mit Restglied in der Integraldarstellung
R(t) =1
p!
∫ t
tn−k
(t− s)p(d
dt
)p+1
u(s) ds.
Verschwinde nun gn für alle Polynome P ∈ Pp. Dann folgt
|gn(u)| =
∣∣∣∣∣ 1
τ
k∑i=0
αk−iP (tn−i)−k∑i=0
βk−iP (tn−i)︸ ︷︷ ︸=gn für u=P∈PP , verschwindet also
+1
τ
k∑i=0
αk−iR(tn−i)−k∑i=0
βk−iR(tn−i)
∣∣∣∣∣=
∣∣∣∣∣1τk∑i=0
αk−iR(tn−i)−k∑i=0
βk−iR(tn−i)
∣∣∣∣∣≤ 1
p!
∥∥∥∥∥(d
dt
)p+1
u
∥∥∥∥∥∞
(1
τ
k∑i=0
|αk−i|∫ tn−i
tn−k
(tn−i − s)pds︸ ︷︷ ︸=O(τp+1)︸ ︷︷ ︸
=O(τp)
+k∑i=0
|βk−i| (tn−i − tn−k)p︸ ︷︷ ︸=O(τp)
)
= O(τ p).
Also gilt die Behauptung.
BeispielDas Adams-Bashforth-Verfahren mit k Schritten hat die Konsistenzordnung p = k.
BemerkungKonsistenz alleine genügt nicht.Betrachte dazu un = −4un−1 + 5un−2 + τ(4fn−1 + 2fn−2).Dann folgt C0 = C1 = C2 = C3 = 0, C4 = 1
6. Wähle f(t, z) = −z ∈ R. Somit folgt
un = −4un−1 + 5un−2 − τ(4un−1 + 2un−2) bzw.un + (4 + 4τ)un−1 + (−5 + 2τ)un−2 = 0.
Wir lösen die Dreitermrekursion mit dem Ansatz un = zn. Das führt zu
z2 + (4 + 4τ)z + (−5 + 2τ) = 0 ⇒ z1/2 = −2− 2τ ± 3
√1 +
2
3τ +
4
9τ 2.
Damit gilt un = d1zn1 + d2z
n2 für feste d1, d2 ∈ C und es folgt (falls d2 6= 0)
limτ→0|uN | = |d2||(−5)n| → ∞ (n→∞).
34
Lineare Stabilitätsanalyse
Betrachte die lineare Differentialgleichung
u = ωu, u(0) = 1
mit der analytischen Lösung u(t) = exp(ωt).Wir beobachten, dass |u(t)| ≤ 1 für alle Zeiten t gilt, falls Reω ≤ 0.Wir fordern deshalb, dass sich diese Eigenschaften auf das Mehrschrittverfahren übertra-gen sollen, also
k∑i=0
αk−iun−i = τω
k∑i=0
βk−iun−i,
d.h. un löst die Differenzengleichung
k∑i=0
(αk−i − τωβk−i
)un−i = 0, (n = k, k + 1, . . . ).
Es stellt sich die Frage, wann diese Lösungen beschränkt sind.
(3.7) SatzEs sei χ ein Polynom vom Grad k mit Kooeffizienten αk und Nullstellen λν , d.h.
χ(λ) =k∑i=0
αiλi =
r∏ν=1
(λ− λν)mν , λν 6= λµ (ν 6= µ),r∑
ν=1
mν = k.
Dann hat jede Lösung (zn)n∈N0 der linearen Differenzengleichung
k∑i=0
αk−izn−i = 0, (n = k, k + 1, . . . )
die Form
zn =r∑
ν=1
mν−1∑j=0
cν,jn!
(n− j)!λnν .
Dabei sind die Koeffizienten eindeutig durch z0, . . . , zk−1 bestimmt.
Beweis. Die Lösungsmenge bildet einen Vektorraum. Wir zeigen nun, dass die Folge
yn =n!
(n− j)!λnν , (1 ≤ ν ≤ r, 0 ≤ j < mν)
für festes ν und j eine Lösung ist.Der Beweis wird induktiv geführt, wobei an dieser Stelle exemplarisch nur die Fälle j = 0und j = 1 betrachtet werden.
35
Für j = 0 gilt χ(λν) = 0. Damit folgt
k∑i=0
αk−iyn−i =k∑i=0
αk−iλn−iν = λn−kν χ(λν) = 0.
Und für j = 1 gilt χ(λν) = χ′(λν) = 0, womit folgt
k∑i=0
αk−iyn−i =k∑i=0
αk−i(n− i)λn−iν = λn−kν
k∑i=0
αk−i(n− i)λk−iν
= λn−kν
k∑i=0
αk−i(n− k)λk−iν + λn−kν
k∑i=0
αk−i(k − i)λk−iν
= λn−kν
k∑i=0
αk−i(n− k)λk−iν + λn−k+1ν
k−1∑i=0
αk−i(k − i)λk−i−1ν
= λn−kν (n− k)χ(λν) + λn−k+1ν χ′(λν) = 0.
Außerdem lässt sich zeigen, dass diese Lösungen linear unabhängig sind. Damit bilden sieeine Basis des Lösungsraums.
FolgerungFür |λν | > 1 gilt limn→∞ |λnν | = ∞. Und falls |λν | = 1 mit mν > 1 gilt, dann folgtlimn→∞ |nλnν | =∞.Also ist die Lösung zn in diesen beiden Fällen für n → ∞ unbeschränkt (falls die Koeffi-zienten cν,j nicht verschwinden).Wenn für ν gilt |λν | < 1 oder |λν | = 1 und mν = 1, dann ist
|zn| ≤∑|λν |<1
∑j
|cν,j||nmj ||λν |n +∑|λν |=1
|cν,j| <∞.
Somit ist die Lösung in diesem Fall beschränkt.
(3.8) DefinitionWir definieren das charakteristische Polynom zu einem Mehrschrittverfahren durch
χ(λ) =k∑i=0
αiλi.
(3.9) DefinitionEin Mehrschrittverfahren heißt stabil (0-stabil), wenn für alle Nullstellen λν des charak-teristischen Polynoms |λν | ≤ 1 gilt und alle Nullstellen mit |λν | = 1 einfach3 sind.
BemerkungWenn ein Mehrschrittverfahren nicht stabil ist, dann ist die Lösung für τ → 0 immer (bisauf Trivialfälle) unbeschränkt.
3D.h. aus χ(λν) = 0 und |λν | = 1 folgt χ′(λν) 6= 0.
36
BeispielWir betrachten die Stabilität von einigen Mehrschrittverfahren.
a) Für die Adams-Verfahren gilt
χ(λ) = λk − λk−1 = λk−1(λ− 1).
Also ist das Verfahren stabil.
b) Das Nyström-Verfahren ist ebenfalls stabil, denn es gilt
χ(λ) = λk − λk−2 = λk−2(λ− 1)(λ+ 1).
c) Für k = 2 sind die Backward-Differentiation-Formulas wegen
χ(λ) =3
2λ2 − 2λ+
1
2=
1
2(3λ− 1)(λ− 1)
stabil. Falls k > 5 gilt, ist das Verfahren allerdings nicht stabil. Für variable Schritt-weite muss jeweils die Stabilität geprüft werden.
(3.10) LemmaSei A ∈ Rk,k eine Matrix mit Spektralradius ρ = ρ(A) = maxµ∈σ(A) |µ| und für jedenEigenwert λν ∈ σ(A) mit |λν | = ρ sei die algebraische Vielfachheit gleich der geometri-schen Vielfachheit.
Dann existiert ein symmetrische, positiv definite Matrix S ∈ Rk,k mit
|Az|S ≤ ρ|z|S, z ∈ Rk.
Dabei ist |z|S =√zTSz.
Beweis. Zu A ∈ Rk,k existiert eine invertierbare Transformation Q ∈ Ck,k mit
Q−1AQ = J =
J1
. . .Jr
(Jordan-Normalform),
Jν =
λν 1
. . . . . .. . . 1
λν
= λνImν +Nν ∈ Rmν ,mν , wobei
Nν =
0 1
. . . . . .. . . 1
0
∈ Rmν ,mν (ν = 1, . . . , r).
37
Gilt |λν | = ρ, so folgt mν = 1. Zu ε > 0 definiere E := diag(ε, ε2, ε3, . . . ). Dann folgt
E−1JE =
Jε1
. . .Jεr
mit Jεν =
λν ε
. . . . . .. . . ε
λν
= λνImν + εNν .
Und damit ergibt sich für die Spektralnorm ‖ · ‖2
‖E−1JE‖2 = max ‖Jεν‖2 ≤ max
max|λν |=ρ
|λν |, max|λν |<ρ
|λν |+ ε‖Nν‖2
.
Wähle nun ε > 0 so klein, dass |λν |+ ε‖Nν‖2 ≤ ρ für |λν | < ρ gilt und definiere
S = Q−TE−TE−1Q−1 = KTK für K := E−1Q−1.
Also ist S symmetrisch und positiv definit und es gilt
|Az|2S = zTATSAz = zTATQ−TE−TE−1Q−1Az
= zTQ−T (QTATQ−T )E−TE−1(Q−1AQ)Q−1z
= zTQ−TJTE−TE−1JQ−1z
= |E−1JQ−1z|22= |E−1JEE−1Q−1z|22 ≤ ‖E−1JE‖2
2|E−1Q−1z|22≤ ρ2|E−1Q−1z|22 = ρ2|z|2S,
was zu zeigen war.
(3.11) SatzSei u ∈ C1([t0, t0 +T ], G) Lösung der Anfangswertaufgabe (1.1), für f sei eine Lipschitz-Bedingung mit L > 0 erfüllt und sei τL|βk| < 1.Dann gilt für ein konsistentes und stabiles Mehrschrittverfahren
|un − u(tn)| ≤ K∗
[max
i=0,...,k−1|ui − u(ti)| exp
(L∗(tn − tk)
)+ max
i=k,...,n|gi|
exp(L∗(tn − tk)
)− 1
L∗
]
für n > k und Konstanten K∗, L∗ > 0.
Beweis für M = 1. Aus αk = 1 folgen
un = −k∑i=1
αk−iun−i + τ
k∑i=0
βk−ifn−i und
τgn = u(tn) +k∑i=1
αk−iu(tn−i)− τk∑i=0
βk−iu(tn−i).
38
Durch Subtraktion der beiden Gleichungen ergibt sich für den globalen Fehler
en = u(tn)− un = τgn −k∑i=1
αk−ien−i + τ
k∑i=0
βk−iqn−ien−i
mit qn = 1en
(u(tn)− fn
)für en 6= 0 und qn = 0 sonst. Nun gilt
|qn| = 1
|en||f(tn, u(tn))− f(tn, u
n)| ≤ 1
|en|L |u(tn)− un|︸ ︷︷ ︸
=|en|
= L
und es folgt
(1− τβkqn)en = −k∑i=1
αk−ien−i + τrn mit rn = gn +
k∑i=1
βk−iqn−ien−i.
Definiere nun en := (en, en−1, . . . , en−k+1)T ∈ Rk. Dann folgt Dnen = Aen−1 + τrn,
wobei Dn = diag(1− τ |βk||qn|, 1, . . . , 1) und
A =
−αk−1 −αk−2 . . . −α0
1 0 . . . 0. . . . . . ...
1 0
, rn =
rn0...0
, gn =
gn
0...0
, β =
βk−1...β0
.
Es gilt
det(λI − A) = λk +k∑i=1
αk−iλk−i = χ(λ).
Da das Verfahren nach Voraussetzung stabil ist, gilt nach Definition (3.9) für alle Nullstel-len λ von χ und damit für alle Eigenwerte λ von A
|λ| ≤ 1 und |λ| = 1⇒ λ ist einfache Nullstelle.
Aus der Stabilitätsbedingung folgt daher für den Spektralradius ρ(A) ≤ 1, und falls |λ| =1, ist die algebraische als auch die geometrische Vielfachheit 1. Damit folgt aus (3.10),dass ein symmetrisch positiv definite Matrix S ∈ Rk,k existiert mit |Az|S ≤ |z|S für allez ∈ Rk. Da auf Rk alle Normen äquivalent sind, existieren zusätzlich C ≥ 1 ≥ c > 0 mitc|z| ≤ |z|S ≤ C|z|.Außerdem gilt
‖Dn − Ik‖ = τ |βk||qn| ≤ τ |βk|L < 1
und daraus folgt mit der Neumann’schen Reihe, dass Dn = Ik − (Ik − Dn) invertierbarist, wobei
‖D−1n ‖ =
∥∥∥∥∥∑j≥0
(Ik −Dn)j
∥∥∥∥∥ ≤∑j≥0
(τ |βk|L
)j=
1
1− τ |βk|L.
39
Damit folgt
‖D−1n − Ik‖ ≤ ‖D−1
n ‖‖Ik −Dn‖ ≤τ |βk|L
1− τ |βk|L
und somit
‖D−1n ‖S ≤ ‖Ik‖S + ‖D−1
n − Ik‖S ≤ 1 + supz 6=0
|(D−1n − Ik)z|S|z|S
≤ 1 +C
csupz 6=0
|(D−1n − Ik)z||z|
= 1 +C
c‖D−1
n − Ik‖ ≤ 1 + τL0
mit L0 =C
c
|βk|L1− τ |βk|L
. Ferner gilt
|rn|S ≤ |gn|S + |rn − gn|S ≤ |gn|S + C|rn − gn|
≤ |gn|S + Ck∑i=1
|βk−i||qn−i||en−i|
≤ |gn|S + CL|β||en−1|
≤ |gn|S + L1|en−1|S mit L1 =C
cL|β|,
|en|S = |D−1n (Aen−1 + τrn)|S ≤ ‖D−1
n ‖S(|Aen−1|S + τ |rn|S
)≤ (1 + τL0)
(|en−1|S + τ
(|gn|S + L1|en−1|S
))≤ (1 + τL∗)|en−1|S + τ(1 + τL0)|gn|S.
Dabei ist L∗ = L0 + L1 + τL0L1.Nun folgt mit zn = |en|, δk = τL∗ und ηn = τ(1 + τL0)|gn|S in dem diskreten Gronwall-Lemma (2.5)
|en|S ≤ |ek−1| exp(L∗(n− k)τ
)+ (1 + τL0) max
j=k,...,n|gj|S
exp(L∗(n− k)τ
)− 1
L∗
und daraus ergibt sich für n = k, k + 1, . . .
|en| ≤ |en| ≤ 1
c|en|S
≤ C
c(1 + τL0)︸ ︷︷ ︸
=:K∗
[|en−1| exp
(L∗(tn − tk)
)+ max
j=k,...,n|gj|S
exp(L∗(n− k)τ
)− 1
L∗
]
mit K∗, L∗ > 0.
(3.12) FolgerungWenn das Mehrschrittverfahren konsistent von der Ordnung p ist und wenn u1, . . . , uk−1
mit einem Verfahren der Ordnung p− 1 berechnet wurden, dann gilt
|u(tn)− un| = O(τ p).
40
Beweis. Es gilt
exp(L∗τ)− 1
L∗=
1
L∗
∞∑k=1
(L∗)kτ k
k!= O(τ).
Somit folgt mit (3.11)
|un − u(tn)| ≤ O(τ p−1)O(τ) exp(L∗T ) +O(τ p)exp(L∗T )
L∗.
Damit folgt die Behauptung.
(3.13) Satz (Dahlquist-Schranken)Für ein stabiles Mehrschrittverfahren von der Ordnung p gilt
p ≤ k + 1 k ungerade,p ≤ k + 2 k gerade,
p ≤ k βk = 0 (explizit).
Beweis. Ohne Beweis.
Beispiel (k = 2)Wir wollen ein Verfahren mit k = 2 Stufen erzeugen, das mindestens konsistent von derOrdnung p = 3 ist.Da α2 = 1 gilt, wählen wir den Ansatz
un + α1un−1 + α0u
n−2 = τ(β2fn + β1f
n−1 + β0fn−2).
Für die Konsistenzforderung muss gelten 0 = C0 = 1 +α1 +α0. Definiere α = α0. Damitfolgt α1 = −1− α. Und somit gilt
un − (1 + α)un−1 + αun−2 = τ(β2fn + β1f
n−1 + β0fn−2).
Damit ist das charakteristische Polynom
χ(λ) = λ2 − (1 + α)λ+ α = (λ− 1)(λ− α).
Nach (3.9) muss −1 ≤ α < 1 gelten, damit das Verfahren stabil ist.Ferner gelten wegen der geforderten Konsistenzordnung
0 = C1 = α1 + 2− (β0 + β1 + β2),
0 = C2 =1
2(α1 + 4)− (β1 + 2β2),
0 = C3 =1
6(α1 + 8)− 1
2(β1 + 4β2).
Das führt zu
β0 = − 1
12(1 + 5α),
β1 =2
3(1− α),
β2 =1
12(5 + α).
41
Damit folgt
un − (1 + α)un−1 + αun−2 =τ
12
((5 + α)fn + 8(1− α)fn−1 − (1 + 5α)fn−2
)und nach ein paar Rechnungen erhält man
C4 =1
24(α1 + 16)− 1
6(β1 + 8β2) = − 1
24(1 + α)
C5 = − 1
360(17 + 13α).
Fordern wir, dass das Verfahren explizit sein soll, muss β2 = 0 gelten. Das erfordert aberα = −5 und somit ist das Verfahren nicht stabil.Fordern wir hingegen, dass das Verfahren mindestens von der Ordnung p = 4 sein soll,muss C4 = 0 gelten, womit α = −1 folgt. In diesem Fall ist das Verfahren stabil, undwegen C5 6= 0 ist die Ordnung p = 4. Damit ergibt sich das Verfahren
un = un−2 +τ
3(fn + 4fn−1 + fn−2) .
Es ist optimal, vgl. Satz 3.13. Die Quadratur entspricht der Simpson-Regel.
Prädiktor-Korrektor-Verfahren
Bei impliziten Verfahren muss im Allgemeinen eine nichtlineare Gleichung gelöst werden,um die nächste Approximation un zu berechnen. Um dies zu umgehen, berechnet man miteinem expliziten Verfahren, dem sogenannten Prädiktor, zunächst einen Schätzwert un,0
für un. Dieser Schätzwert wird dann anstelle von un zur Berechnung von fn herangezogen.Da das implizite Verfahren den geschätzten Wert für un korrigiert, wird es Korrektor ge-nannt.Es kann auch mehrfach korrigiert werden, indem der korrigierte Wert wieder in den Kor-rektor eingesetzt wird.Prädiktor mit explizitem Mehrschrittverfahren
un,0 = −k∑i=1
αk−iun−i + τ
k∑i=1
βk−ifn−i,
Korrektor mit implizitem Mehrschrittverfahren
un,j = −k∑i=1
αk−iun−i + τ
k∑i=1
βk−ifn−i + τ βkf(tn, u
n,j−1) j = 1, . . . , J.
(3.14) LemmaSei pC die Konsistenzordnung des Korrektors, pP die Ordnung des Prädiktors. Dann gilt
p = minpC , pP + J
für das Prädiktor-Korrektor-Verfahren.
42
Beweis. Ohne Beweis.
In der Praxis wird oft so lange korrigiert, bis |un,j − un,j−1| ≤ cτ p gilt.
Algorithmus (p = 4)S0) Wähle τ > 0, J > 0, seien T, u0 gegeben, und setze t = t0, f 0 := f(t0, u
0) undu := u0. Für k = 1, 2, 3 berechne Näherungen mit dem klassisches Runge-Kutta-Verfahren:
k1 := f(t, uk−1)
k2 := f(t+
τ
2, uk−1 +
τ
2k1
)k3 := f
(t+
τ
2, uk−1 +
τ
2k2
)k4 := f(t+ τ, uk−1 + τk3)
uk := uk−1 +τ
6(k1 + 2k2 + 2k3 + k4)
t := t+ τ
fk := f(t, uk) .
Setze u = u3.
S1) Setze
u := u+τ
24(55f 3 − 59f 2 + 37f 1 − 9f 0)
f 0 := f 1
f 1 := f 2
f 2 := f 3
t := t+ τ
(Vierstufiges explizites Prädiktor-Verfahren)
S2) Für j = 1, . . . , J setze
f 3 := f(t, u)
u := u+τ
24(9f 3 + 19f 2 − 5f 1 + f 0).
(Dreistufiges implizites Korrektorverfahren mit J-facher Korrektur)
S3) Falls t ≥ t0 + T : STOP.
S4) Gehe zu S1)
43
Fehlerschätzung
Für den lokalen Diskretisierungsfehler gilt nach (3.4) und (3.5)
gn = Cp+1τp
(d
dt
)p+1
u(tn) +O(τ p+1).
Prädiktor: Adams-Bashforth k = 4, p = 4, Cp5 = 251
720.
Korrektor: Adams-Moulton k = 3, p = 4, Cp5 = − 19
720.
Im Algorithmus werden unP und unC mit denselben un−i und fn−i (i = 1, . . . , k) berechnet.Damit folgt
un,P − un,C ≈ en,P − en,C ≈ τ(gn,P − gn,C) = (CP5 − CC
5 )τ 5
(d
dt
)5
u(tn) +O(τ 6)
⇒ gn,C ≈ 1
τ
CC5
CP5 − CC
5
(un,P − un,C),
also wählen wir den Fehlerschätzer
ηn =1
τ
∣∣∣∣ CC5
CP5 − CC
5
∣∣∣∣Schrittweitensteuerung
0) Wähle ε > 0, K ≥ 2k
1) Speichere immer un−i, fn−i (i = 1, . . . , K)
2) Falls |ηn| > ε, setze τ := τ2; berechne fehlende Werte fn−1, fn−3, . . . durch Inter-
polation.
3) Falls |ηn| ≤ 2−pε und falls genügend viele der alten Werte gespeichert sind, setzeτ := 2τ und verwende dann fn, fn−2, fn−4, . . .
Hohe Ordnung und Fehlerkontrolle
Extrapolationsverfahren:
u1 = u0 + τf(t0, u0)
un = un−2 + 2τf(tn−1, un−1).
Es existiert eine Fehlerentwicklung
un,τ = u(tn) + c2(tn)τ 2 + c4(tn)τ 4 + · · ·
44
Reversible Verfahren
Ein dynamisches System u = f(u) ist reversibel, d.h. es gilt
φ(t+ τ,−τ, φ(t, τ, z)
)= z.
Ein Einschrittverfahren heißt reversibel, wenn für den diskreten Fluss
φτ(t+ τ,−τ, φτ (t, τ, z)
)= z
gilt.
BeispielFür die implizite Trapezregel gilt
un = un−1 + τf
(t+
τ
2,1
2(un + un−1)
).
Damit folgt
un−1 = un − τf(
(t+ τ)− τ
2,1
2(un−1 + un)
).
Bemerkung1) Es gibt keine reversiblen expliziten Runge-Kutta-Verfahren.
2) Für reversible Verfahren ist die Fehlerentwicklung gerade
uτ (t) = u(t) + c2q(t)τ2q + c2q+2(t)τ 2q+2 + · · ·+O(τ 2q+2k).
Die explizite Mittelpunktsregel
u1 = u0 + τf(t0, u0)
un = un−2 + 2τf(tn−1, un−1), (n > 1)
Es gelten:
1) Die explizite Mittelpunktsregel ist reversibel (sie ist äquivalent zu einem reversiblenEinschrittverfahren für ein System).
2) Oszillationen in der Fehlerentwicklung lassen sich durch den Mittelwert
un =1
4(un−1 + 2un + un+1)
verhindern; auch für un existiert eine Fehlerentwicklung in τ 2.
3) Es existiert ein entsprechendes Extrapolationsverfahren.
45
4 Steife Differentialgleichungen
BeispielWir betrachten die lineare Differentialgleichung
u(t) = Au(t), u(0) = u0
mit A ∈ RM,M). Sie ist eindeutig lösbar, und es gilt
u(t) = exp(tA)u0 .
Dabei gilt exp(B) =∑∞
k=01k!Bk für B ∈ RM,M .
Vorsicht: Es gilt exp(A+B) = exp(A) exp(B) genau dann, wenn AB = BA.Aus der Analysis wissen wir:
1) Falls Reλ < 0 für alle λ ∈ σ(A), dann folgt limt→∞ u(t) = 0.
2) Falls Reλ ≤ 0 für alle λ ∈ σ(A) und falls für alle λ ∈ σ(A) mit |λ| = 0 die algebrai-sche Vielfachheit gleich der geometrischen Vielfachheit ist, dann gilt |u(t)| ≤ C füralle t ≥ 0.
BeispielBetrachte
u =
(0 10 0
)u, u(0) =
(01
).
Dann gelten σ(A) = 0 und
u(t) =
(t1
), u(t) =
(10
)=
(0 10 0
)(t1
).
Also folgt limt→∞ |u(t)| =∞.
Bei expliziten Runge-Kutta-Verfahren gilt für f(t, z) = Az
k1 = Az
k2 = A(z + τa21k1) = A(z + τa21Az) = (A+ τa21A2)z
...ks = P (A)z mit P ∈ Ps.
Das führt zu
un = z + τS∑i=1
biki = P (τA)un−1 = P (τA)nu0.
Es tritt limn→∞ un = 0 genau dann ein, wenn limn→∞ |P (τA)nu0| = 0 erfüllt ist. Da aber|P (t)| → ∞ für t → ∞ gilt, muss τ klein genug sein, um im Fall Reλ < 0 für alleλ ∈ σ(A) asymptotisch die richtige Lösung zu berechnen.
46
AnwendungWir betrachten die Wärmeleitungsgleichung als Beispiel für eine parabolische Anfangs-wertaufgabe: Bestimme u : [0,∞)× [a, b]→ R mit
∂
∂tu(t, x) = K
∂2
∂x2u(t, x), (t, x) ∈ [0,∞)× (a, b)
u(0, x) = g0(x), x ∈ (a, b) (Anfangswert)
u(t, a) = ga(t)
u(t, b) = gb(t)
t ∈ (0,∞) (Randwerte).
Dabei ist K > 0 der Wärmeleitkoeffizient.Zur Ortsdiskretisierung wählen wir ein äquidistantes Gitter
∆ := xm = a+mh : m = 0, . . . ,M mit h =b− aM
und approximieren ∂2
∂x2u(t, x) durch Differenzenquotienten
u(t, x+ h) = u(t, x) +∂
∂xu(t, x)h+
1
2
∂2
∂x2u(t, x)h2 +
1
6
∂3
∂x3u(t, x)h3 +O(h4),
u(t, x− h) = u(t, x)− ∂
∂xu(t, x)h+
1
2
∂2
∂x2u(t, x)h2 − 1
6
∂3
∂x3u(t, x)h3 +O(h4).
Addition der Gleichungen liefert
u(t, x− h)− 2u(t, x) + u(t, x+ h) =∂2
∂x2u(t, x)h2 +O(h4).
Also wird u(t, xm) durch folgende lineare Anfangswertaufgabe approximiert:
um = Kh−2(um−1 − 2um + um+1) m = 1, . . . ,M − 1,
um(0) = g0(xm),
u0(t) = ga(t),
uM(t) = gb(t).
Folglich gilt u = Au+ c mit A = −Kh2A0, wobei
A0 =
2 −1−1 2 −1
. . . . . . . . .−1 2 −1
−1 2
∈ RM−1,M−1 und c =K
h2
ga0...0gb
.
Aus den Übungen zu Numerik I kennen wir das Spektrum von A0:
σ(A0) =
λm = 4
(sin(mπ
2M
))2
: m = 1, . . . ,M − 1
.
47
Damit ergibt sich
limh→0
λ1
h2= π2 und lim
h→0λM−1 = 4,
und damit
σ(A) ⊂[−4K
h2, −Kπ2
].
Also gilt limt→∞ exp(tA) = 0.Im Spezialfall, dass ga und gb konstant sind, definiere
um :=b− xmb− a
ga +xm − ab− a
gb, m = 1, . . . ,M − 1.
Dann folgt Au = −c und somit gilt w = Aw für w = u− u, denn
w = u = Au+ c = Au− Au = Aw.
Damit folgt nun w(t) = exp(tA) und somit gilt nach Übungsaufgabe 21
|w(t)| ≤ exp(tλmax(A)
)|w(0)| → 0 für t→∞, da λmax(A) < 0.
Betrachte nun das explizite Euler-Verfahren
wn = wn−1 + τAwn−1 = (I + τA)wn−1 = (I + τA)nw0,
also
limn→∞
|wn| = 0 ⇔ σ(I + τA) ⊂ (−1, 1) ⇔∣∣∣∣1− 4K
h2τ
∣∣∣∣ < 1
⇔ τ4K
h2< 2 ⇔ τ <
h2
2K.
Also ist das Euler-Verfahren nur stabil für τ < h2
2K. Umgekehrt ist das Euler-Verfahren für
große τ sogar instabil, d.h. die numerische Lösung ist unbeschränkt, obwohl die kontinu-ierliche Lösung beschränkt bleibt.
Problem Es ist allgemein so, dass explizite Verfahren kleine Zeitschritte erzwingen, umnumerisch stabile Lösungen zu berechnen. Die erforderliche Schrittweite kann so kleinsein, dass das Verfahren für die Praxis unbrauchbar ist.Es gibt Differentialgleichungen, bei denen dieses Problem für jedes beliebige expliziteVerfahren auftritt. Die Klasse dieser Gleichungen nennt man steife Differentialgleichun-gen.
48
(4.1) Definition (Implizites Runge-Kutta-Verfahren)Ein implizites Runge-Kutta-Verfahren mit S Stufen ist durch ein Butcher-Schema
c AbT
c, b ∈ RS, A ∈ RS,S
definiert. Jeder Runge-Kutta-Schritt erfordert die Lösung des nichtlinearen Gleichungs-systems
ks = f
(t+ csτ, z + τ
S∑r=1
asrkr
), s = 1, ..., S .
Die Lösung (k1, ..., kS) definiert die Verfahrensfunktion
ψ(t, τ, z) =S∑s=1
bsks .
Bemerkunga) Für explizite Verfahren gilt asr = 0 für r ≥ s.
b) Für diagonal-implizite Verfahren gilt asr = 0 für r > s.
c) Für autonom invariante Verfahren gilt cs =∑S
r=1 asr.
d) Ein Verfahren mit br = aSr (r = 1, . . . , S) heißt steif genau.
e) Ein Verfahren mit diag(b)A + AT diag(b) + bbT positiv semidefinit und b > 0 heißtalgebraisch stabil.
Steif genaue und algebraisch stabile Verfahren werden später betrachtet.
Im Allgemeinen muss bei impliziten Verfahren ein nicht-lineares Gleichungssystem inRS·M gelöst werden, d.h. löse (z.B. durch Newton-Verfahren) die nichtlineare GleichungG(k) = 0 mit
G(k) =
k1 − f
(t+ c1τ, z + τ
∑Sr=1 a1rkr
)...
kS − f(t+ cSτ, z + τ
∑Sr=1 aSrkr
) .
Für diagonal-implzite Verfahren b) löse sukzessive für s = 1, . . . , S
Gs(ks) = ks − f
(t+ csτ, z + τ
s∑r=1
asrkr
)!= 0.
49
4.1 Lineare Stabilitätsanalyse
(4.2) DefinitionDie lineare Anfangswertaufgabe
u = Au, u(t0) = u0
heißt stabil, wenn für alle Anfangswerte u0 ∈ RM und ein C > 0
|u(t)| ≤ C|u0| ∀t ≥ 0
gilt, und asymptotisch stabil, wenn
limt→∞|u(t)| = 0.
(4.3) SatzFür lineare Anfangswertaufgaben hat ein Runge-Kutta-Verfahren die Form
un = R(τA)un−1 mit R(z) =P (z)
Q(z)= 1 + zbT (I − zA)−1e
und Polynomen P,Q ∈ PS , d.h. Q(τA)R(τA) = P (τA). Hierbei ist e = (1, ..., 1)T .Für explizite Verfahren ist R = P ∈ PS ein Polynom.Wenn das Verfahren die Ordnung p hat, dann gilt
R(z) =
p∑j=0
1
j!zj +O(zp+1)
(Padé-Approximation der Exponentialfunktion).
Beweis. Betrachte u = λu, u(0) = 1 = u0 und
u1 = u0 + τ
S∑s=1
bsks, ks = λ
(u0 + τ
S∑r=1
asrkr
).
Setze z := λτ und
d :=1
λ
k1...kS
, e :=
1...1
∈ RS.
Dann folgen u1 = 1 + zbTd und d = e+ zAd und damit4 d = (I − zA)−1e.Also gilt für R(z)
u1 = 1 + zbT (I − zA)−1e!= R(z) .
4Nach Numerik I konvergiert die Neumannsche Reihe∑k≥0(zA)
k für hinreichend kleines z, d.h., I−zAist invertierbar, und es gilt (I − zA)−1 =
∑k≥0(zA)
k.
50
Die Cramer’sche Regel ergibt mit (I − zA)d = e für die Komponenten von d
ds =Ps(z)
Q(z)mit Q(z) = det(I − zA) ∈ PS, Ps ∈ PS−1.
Damit folgt
R(z) =Q(z) + z
∑Ss=1 bsPs(z)
Q(z).
Ist das Verfahren explizit, so ist A eine strikte untere Dreiecksmatrix und damit nilpotent,denn AS = 0. Die Neumann’sche Reihe liefert für hinreichend kleines τ
(I − zA)−1 =S−1∑k=0
(zA)k ∈ PS−1.
Sei nun das Verfahren von der Ordnung p. Dann gilt
O(τ p) = g(t, τ, z) =1
τ
(exp(tA)z − z
)− 1
τ
(R(tA)z − z
)︸ ︷︷ ︸ψ(t,z,A)
=1
τ
(exp(tA)−R(tA)
)z.
Das ist äquivalent zu exp(tA) = R(tA) +O(τ p+1).
Beispiel (Implizite Trapezregel)Das Verfahren hat das Butcher-Schema
0 0 01 1
212
12
12
Also gilt k1 = λu0 und k2 = λ(u0 + τ
2k1 + τ
2k2
).
Daraus ergibt sich k2 =λ(1+ τ
2λ)
1− τ2λu0 und
u1 = u0 +τ
2(k1 + k2) = u0 +
τ
2λu0 +
τ
2
λ(1 + τ
2λ)
1− τ2λ
u0 = R(τλ)u0
mit R(z) = 1 + 12z + 1
2z
1+ 12z
1− 12z
=1+ z
2
1− z2
.
(4.4) DefinitionEin Runge-Kutta-Verfahren heißt A-stabil, wenn die linke Halbebene
C− := z ∈ C : Re(z) ≤ 0
im Stabilitätsgebiet
S := z ∈ C : |R(z)| ≤ 1
enthalten ist.
51
BemerkungEs gilt z ∈ C : | exp(z)| ≤ 1 = C−.
Beispiel1) Für das explizite Euler-Verfahren gilt R(z) = 1 + z und deshalb
|R(z)| ≤ 1 ⇐⇒ |z − (−1)| ≤ 1.
Also ist das Verfahren nicht A-stabil.
2) Für ein allgemeines explizites Runge-Kutta-Verfahren gilt R(z) = P (z), wobei P einnichtkonstantes Polynom ist. Somit folgt |P (z)| → ∞ für z →∞.Also sind explizite Runge-Kutta-Verfahren nicht A-stabil!
3) Für das implizite Euler-Verfahren gilt R(z) = 11−z , denn aus un = un−1 + τAun folgt
(I − τA)un = un−1. Also gilt un = R(τA)un−1 mit R(τA) = (I − τA)−1. Daher istdas Verfahren A-stabil, denn es gilt
|R(z)| =∣∣∣∣ 1
1− z
∣∣∣∣ ≤ 1 ⇐⇒ |z − 1| ≥ 1.
4) Für die implizite Trapezregel gilt R(z) = 2+z2−z und somit
|R(z)|2 = R(z)R(z) =2 + z
2− z2 + z
2− z=
4 + 4 Re z + |z|2
4− 4 Re z + |z|2≤ 1 ⇔ Re z ≤ 0.
Also gilt S = C−, und das Verfahren ist A-stabil.
5) Für die implizite Mittelpunktsregel gilt ebenfalls R(z) = 2+z2−z .
BemerkungFür lineare Anfangswertaufgaben sind implizite Trapezregel und implizite Mittelpunktsre-gel identisch, sie unterscheiden sich aber im nichtlinearen Fall.
BemerkungFür ein explizites konsistentes Runge-Kutta-Verfahren giltR(z) = 1+z+O(z2) und damitfolgen R′(0) = 1 und R(0) = 1. Also existiert ein ε > 0, sodass R(z) > 1 für z ∈ (0, ε)und R(z) < 1 für z ∈ (−ε, 0). Folglich gilt 0 ∈ ∂S.Daher definieren wir zu einer stabilen linearen Anfangswertaufgabe eine charakteristischeSchrittweite
τc = supτ > 0 : |R(τA)| ≤ 1 für alle τ ∈ (0, τ) ≥ 0.
BeispielA) Wärmeleitungsgleichung: τc = O(h2) für explizite Verfahren.
B) Betrachte u = Au mit A = ( 0 1−1 0 ) und σ(A) = ±i. Das Problem ist stabil, aber
nicht asymptotisch stabil.
1) Explizites Euler-Verfahren: R(z) = 1 + z. Damit folgt
τc = supτ > 0 : |R(±iτ)| ≤ 1 = 0.
52
2) Klassisches Runge-Kutta-Verfahren:
R(z) = 1 + z +1
2z2 +
1
6z3 +
1
24z4.
Somit folgt τc = 2√
2 ≈ 2.82 . . . . Das Verfahren ist also bei dieser Anfangswert-aufgabe stabil für τ < τc.
(4.5) SatzFür A-stabile Runge-Kutta-Verfahren gilt:Wenn die lineare Anfangswertaufgabe stabil ist,dann ist auch die numerische Lösung sta-bil, d.h.
|un| ≤ C|u0|
mit einem C > 0 gilt für alle Schrittweiten τ > 0.
Beweisidee. (i) A und R(τA) haben die gleichen Eigenvektoren und
λ ∈ σ(A) ⇐⇒ R(τλ) ∈ σ(R(τA)).
(ii) Es gilt wegen der A-Stabilität des Verfahrens für das Stabilitätsgebiet S
z ∈ C : Re z < 0 ⊂ intC− ⊂ λ ∈ C : |R(τλ)| < 1 = intS.
Damit folgt |R(τλ)| < 1 für Reλ < 0.
(iii) Aus |R(τλ)| = 1 folgt, dass die algebraische Vielfachheit des EigenwertsR(τλ) vonR(τA) gleich der geometrischen Vielfachheit ist.
(iv) Es gilt |R(τA)nu0| ≤ C|u0|. Also ist das Verfahren stabil.
Die Matrix-Exponentialfunktion(4.6) SatzSei R(z) = P (z)
Q(z)eine rationale Funktion zur Approximation der Exponentialfunktion von
der Ordnung p. Dann gilt
p ≤ gradP + gradQ.
Beweis. Angenommen es existieren P,Q mit gradP ≤ k und gradQ ≤ j mit k + j < p.Dann folgt
P (z)
Q(z)= exp(z) +O(zp+1) = exp(z) +O(zk+j+2)
und somit P (z)−Q(z) exp(z) = O(zk+j+2).Zeige mit Vollständiger Induktion: P = Q = 0.Wir führen den Induktionsbeweis über k.
53
(IA) Sei k = 0 und j beliebig. Also gilt P ∈ R und P exp(−z)+Q(z) = O(zj+2). Durch(j + 1)-maliges Ableiten nach z erhält man dann (−1)j+1P exp(−z) + 0 = O(z)und damit folgt P = 0. Dann giltQ(z) = O(zj+2), und aus gradQ ≤ j folgtQ = 0.
(IS) Wir schließen von k − 1 auf k.Aus P ′(z) +
(Q′(z) + Q(z)
)exp(z) = O(zk+j+1) folgen gradP ′ ≤ k − 1 und
grad(Q+Q′) ≤ j. Damit gilt nach Induktionsvoraussetzung P = 0 undQ+Q′ = O.Somit folgt schließlich Q = 0.
Bemerkung (Padé-Approximation)Für
Rpq(z) =
∑pj=0
(p+q−j)!p!(p+q)!(p−j)!
zj
j!∑pj=0
(p+q−j)!q!(p+q)!(q−j)!
(−z)jj!
.
gilt exp(z) = Rpq(z) +O(zp+q+1), z.B.
(p, q) R(z) Verfahren(1, 0) 1 + z explizites Euler-Verfahren(0, 1) 1
1−z implizites Euler-Verfahren(1, 1) 2+z
2−z implizite Mittelpunktsregel
Für ‖A‖1 ≤ 5 gilt ‖R13,13(A)− exp(A)‖1 ≤ eps ≈ 10−16.
Algorithmus (Berechnung von exp(A))S0) A := A− µI , µ = SpurA
S1) A := D−1AD, geeignete Diagonalskalierung
S2) A := 2−sA, s ∈ N, sodass ‖2−sA‖1 ≤ 5
S3) X = R13,13(A)
S4) X2 := X ·X , X4 = X2 ·X2, . . . , X2s = X2s−1 ·X2s−1
S5) X := exp(µ)DX2sD−1
4.2 L-Stabilität(4.7) DefinitionEin A-stabiles Runge-Kutta-Verfahren heißt L-stabil, wenn
R(∞) := lim|z|→∞
|R(z)| = 0
gilt.
54
Dabei ist R(∞) wohldefiniert, denn es ist
|R(z)| =
∣∣∣∣apzp + ap−1zp−1 + · · ·+ a0
bqzq + bq−1zq−1 + · · ·+ b0
∣∣∣∣=
∣∣∣∣ ap + ap−1z−1 + · · ·+ a0z
−p
bqzq−p + bq−1zq−p−1 + · · ·+ b0z−p
∣∣∣∣→
∞, p > q
0, p < q∣∣∣apbq ∣∣∣ , p = q
(|z| → ∞).
BemerkungFür asymptotisch stabile Anfangswertaufgaben gilt dann R(τA) → 0 für τ → ∞, d.h.der asymptotische Zustand lässt sich mit einem Zeitschritt berechnen.
BeispielA) Für das implizite Euler-Verfahren gilt R(z) = 1
1−z und damit folgt R(∞) = 0.
B) Es gilt für zwei Polynome P und Q mit gradP < gradQ
R(z) =P (z)
Q(z)→ 0 (|z| → ∞).
C) Für die implizite Mittelpunktsregel gilt R(z) = 2+z2−z und damit R(∞) = −1, also ist
das Verfahren nicht L-stabil.
(4.8) SatzSei (A, b, c) ein A-stabiles Runge-Kutta-Verfahren mit br = aSr für r = 1, . . . , S und seiA invertierbar.
Dann ist das Verfahren L-stabil.
Beweis. Es seien
eS =
0...01
, e =
1...1
, b = AT eS ∈ RS.
Dann gelten (eS)TA = (aS1, . . . , aSS) = bT , und aus Satz (4.3) folgt
R(z) = 1 + zbT (I − zA)−1e = 1 + bT(
1
zI −A
)−1
e
→ 1− bTA−1e = R(∞) (|z| → ∞).
Damit ergibt sich R(∞) = 1− (eS)TAA−1e = 1− (eS)T e = 0.
55
4.3 Reversible VerfahrenBemerkungEin dynamisches System heißt reversibel, falls
φ(t+ τ,−τ, φ(t, τ, z)
)= z ∀t ∈ [t0, t0 + T ], τ > 0, z ∈ G.
(4.9) DefinitionEin Runge-Kutta-Verfahren heißt reversibel, wenn
R(z)R(−z) = 1
für alle z ∈ C mit R(z) 6= 0 gilt.
Beispiel (Implizite Mittelpunktsregel)Die implizite Mittelpunktsregel hat das Butcher-Schema
12
12
1
Damit gelten
k1 = f(t+
τ
2, un−1 +
τ
2k1
)und un = un−1 + τk1,
also τk1 = un − un−1. Damit folgen
un = un−1 + τf
(t+
τ
2,1
2(un + un−1)
),
un−1 = un − τf(
(t+ τ)− τ
2,1
2(un + un−1)
).
Außerdem gilt
R(z) =2 + z
2− z.
Damit folgt R(z)R(−z) = 1.
(4.10) SatzFür A ∈ RM,M sind äquivalent:
a) Es gilt AT = −A (A schief-symmetrisch).
b) exp(tA) ist orthogonal5 für alle t ∈ R.
c) Für alle u0 ∈ RM und alle Lösungen von u = Au, u(0) = u0 gilt |u(t)| = |u0|(∀t ∈ R).
Beweis. Übungen.
5 A ∈ RM,M heißt orthogonal, wenn AAT = IM .
56
(4.11) SatzSei R(z) = 1 + z + O(z2) eine rationale Approximation der Exponentialfunktion mitreellen Koeffizienten und ohne Polstellen in C−.Dann sind äquivalent
a) S = C−.
b) |R(z)| = 1 für Re z = 0.
c) R ist reversibel, also R(z)R(−z) = 1 für alle z ∈ C.
Beweis. c)⇒ b): Aus Re(z) = 0 folgt −z = z und damit
1 = R(z)R(−z) = R(z)R(z) = R(z)R(z) = |R(z)|2.
b)⇒ c): Es gelte |R(z)| = 1 für alle z ∈ C mit Re(z) = 0. Die Funktion
g : C→ C, g(z) := R(z)R(−z)
ist meromorph6, ebenso ist g ≡ 1 meromorph. Außerdem gilt g = g auf iR. Also ist g ≡ gauf ganz C.a)⇒ b): Annahme: Es gelte |R(z)| < 1 für ein z ∈ C mit Re(z) = 0.Da R in einer Umgebung von z stetig ist, existiert dann auch ein z ∈ C mit Re(z) > 0und |R(z)| < 1, d.h. z 6∈ C− und z ∈ S, also S 6= C−. Das ist ein Widerspruch zu a).b)⇒ a): Aus |R(z)| = 1 für Re z = 0 folgt limz→∞ |R(z)| = 1. Zu ρ > 0 betrachte
Ωρ := z ∈ C− : |z| ≤ ρ.
Für zρ ∈ C− mit |zρ| = ρ gilt limρ→∞ |R(zρ)| = 1 und aus dem Maximumsprinzip folgt
maxz∈Ωρ|R(z)| = max
z∈∂Ωρ|R(z)|
(denn R ist in Ωρ holomorph) und somit gilt
maxz∈C−
|R(z)| = limρ→∞
maxz∈Ωρ|R(z)| = lim
ρ→∞maxz∈∂Ωρ
|R(z)| = 1.
Daraus folgt C− ⊂ S.Annahme: Es existiert ein z ∈ intS mit Re(z) = 0.Dann existiert wegen der Stetigkeit von R ein z ∈ intS mit Re(z) > 0, d.h. −z ∈ S. Dabereits die Äquivalenz von b) und c) gezeigt wurde, folgen
R(z)R(−z) = 1, |R(z)| ≤ 1, |R(−z)| ≤ 1,
woraus sich sofort |R(z)| = |R(−z)| = 1 ergibt.Also existiert ein ε > 0, sodass |R(y)| = 1 für alle y ∈ C mit |z − y| ≤ ε, woraus|R(z)| ≡ 1 folgt. Das ist ein Widerspruch dazu, dass R(z) = 1 + z +O(z2) gilt.
6Eine komplex differenzierbare Funktion mit höchstens abzählbar vielen Polstellen heißt meromorph.
57
(4.12) SatzSei A ∈ RM,M mit AT = −A (schief-symmetrisch) und sei R die rationale Funktion zueinem Runge-Kutta-Verfahren mit S = C−.Dann ist R(τA) orthogonal und es gilt für un = R(τA)un−1
|un|2 = |un−1|2.
Beweis. Es gilt
(iA)H = iAT = −iAT = iA,
also ist iA hermitesch7 und hat daher ausschließlich relle Eigenwerte. Außerdem sind iAund A diagonalisierbar und das Spektrum σ(A) von A ist rein imaginär.Mit (4.11) folgt, dass R keine Polstellen auf iR hat. Ferner gilt R(τA)T = R(τAT ) =R(−τA). Damit folgt R(τA)R(τA)T = R(τA)R(−τA) = IM . Also ist R(τA) orthogo-nal. Da orthogonale Matrizen Isometrien bezüglich der euklidischen Norm beschreiben,gilt
|un|2 = |R(τA)un−1|2 = |un−1|2 .
Beispiel (Wellengleichung, hyperbolisch)Gesucht ist eine Funktion u : [0,∞)× R→ R mit
∂2t u(t, x) = c2∂2
xu(t, x) (t ≥ 0, x ∈ R),
u(0, x) = g(x) (x ∈ R),
wobei c die Wellengeschwindigkeit ist und g die Anfangsbedingungen festlegt.Die Ausbreitungsgeschwindigkeit ist endlich und deshalb folgt aus g(x) = 0 für |x| > r,dass u(t, x) = 0 für |x| > r + ct gilt.Wähle zu T > 0 ein R > 0 groß genug mit u(t,−R) = u(t, R) für alle t ∈ [0, T ].Setze h := 2R
Mund
∆h := xm = −R +mh : m = 0, . . . ,M.
Setze uh0(t) := uhM(t) = 0 und bestimme uh ∈ C2([0, T ],RM−1) mit
uhm = c2 1
h2(uhm−1 − 2uhm + uhm+1) (m = 1, . . . ,M − 1).
Damit folgt
uh = Auh
mit einer entsprechenden Matrix A ∈ RM−1,M−1.Wir beobachten für die Energie E(u) = 1
2
∫R
(|u|2 + |c∂xu|2
)dx
d
dtE(u) =
∫R
(uu+ c∂xuc∂xu
)dx
PI=
∫R
(u− c2∂xu︸ ︷︷ ︸
=0
)udx = 0.
7A ∈ CM,M heißt hermitesch, wenn A = AT und AH bezeichnet die zu A adjungierte Matrix.
58
Also gilt E(u) = E(u0) = const und das System ist damit energieerhaltend.Wir schreiben das System als Differentialgleichung erster Ordnung um. Dafür setzen wir
w := c∂xu,
u := c∂xw
und damit folgt
u = c∂xw = c2∂2xu.
Nun diskretisiert man w auf dem verschobenen Gitter (engl. staggered grid)−R +
(1
2+m
)h︸ ︷︷ ︸
=xm+1
2
: m = 0, . . . ,M − 1
.
Damit ergibt sich das Gesamtsystem
uh0 = uh0 mit uh0(t0) = 0
uhm =c
h
(whm+ 1
2− wh
m− 12
)m = 1, . . . ,M
uhM = uhM mit uhM(t0) = 0,
w 12
=c
h
(uh1 − uh0
)wm+ 1
2=
c
h
(uhm+1 − uhm
)m = 1, . . . ,M − 1.
mit un(t) ∈ RM+1 und wh(t) ∈ RM , also uh = Bwh und wh = −BTuh. Dabei ist
B =c
h
1−1 1
−1 1. . .
. . .−1 1
−1
∈ RM+1,M , −BT =
c
h
−1 1
−1 1. . .
. . .−1 1
∈ RM,M+1.
Insgesamt folgt dann
d
dt
(uh
wh
)=
(B
−BT
)(uh
wh
).
Wir betrachten die explizite Zeitschrittdiskretisierung
uh,0 = u(t0), wh,0 = w(t0)
wh,12 = wh,0 − τ
2BTuh,0
uh,n = uh,n−1 + τBwh,n−12
wh,n+ 12 = wh,n−
12 − τBTuh,n.
Damit das Verfahren funktioniert, ist eine Schrittweitenbeschränkung von τ ≤ hc
erforder-lich.
59
4.4 B-Stabilität(4.13) DefinitionEine Funktion f ∈ C([t0, t0 + T ] × G,RM) heißt monoton (in der zweiten Komponente)bezüglich eines Skalarproduktes (·, ·) im RM , wenn(
f(t, y)− f(t, z), y − z)≥ 0
für alle t ∈ [t0, t0 + T ] und alle y, z ∈ G gilt.
BeispielSei F : G→ R konvex, d.h.
F((1− s)y + sz
)≤ (1− s)F (y) + sF (z), s ∈ [0, 1],
dann ist f(t, z) := ∇F (z) monoton8.
(4.14) DefinitionEine Anfangswertaufgabe
u = f(t, u), u(t0) = u0
heißt dissipativ, wenn −f monoton ist.
BemerkungWenn f eine einseitige Lipschitz-Bedingung9, d.h.(
f(t, y)− f(t, z), y − z)≤ L|y − z|2
erfüllt, dann gilt für zwei Lösungen u = f(t, u), v = f(t, v) und alle t ∈ [t0, t0 + T ]
|u(t)− v(t)| ≤ exp(L(t− t0)
)|u(t0)− v(t0)|.
Der Beweis erfolgt analog zu dem von (1.10).Zur Vereinfachung verwenden wir hier nur die Euklidische Norm. Analog lassen sich ein-seitig Lipschitz-Bedingungen zu gewichteten Normen betrachten.Anwendung:
L = 0 : −f monoton,L < 0 : −f strikt monoton, Anfangswertaufgabe asymptotisch stabil.
BeispielWir betrachten das lineare Problem mit f(t, z) = Az, wobei Re(λ) ≤ ρ für alle λ ∈ σ(A)gelten soll.Dann unterscheiden wir drei Fälle:
1) A ist diagonalisierbar. Dann folgt(A(y − z), y − z
)≤ ρ|y − z|2.
8Vgl. Optimierungstheorie.9Dabei kann L auch negativ sein.
60
2) Für alle λ ∈ σ(A) sei die algebraische Vielfachheit gleich der geometrischen Viel-fachheit. Dann folgt die Existenz einer symmetrischen und positiv definiten MatrixS ∈ RM,M mit
(Ay − Az, y − z)S = (A(y − z))TS(y − z) ≤ ρ(y − z)TS(y − z) = ρ|y − z|2S.
3) Allgemein existiert zu jedem ε > 0 ein symmetrisches und positiv definites S ∈ RM,M
mit
(Ay − Az, y − z)S ≤ (ρ+ ε)|y − z|2S.
Also folgt aus der Stabilität der linearen Anfangswertaufgabe u = Au, dass die Anfangs-wertaufgabe dissipativ ist.
(4.15) DefinitionEin Einschrittverfahren mit Verfahrensfunktion ψ heißt B-stabil, wenn für dissipative An-fangswertaufgaben gilt
|un − vn| ≤ |un−1 − vn−1|
für
un = un−1 + τnψ(tn−1, τn, un−1),
vn = vn−1 + τnψ(tn−1, τn, vn−1).
(4.16) LemmaB-stabile Runge-Kutta-Verfahren sind A-stabil.
Beweis. Wähle z = α + iβ ∈ C−, d.h. α = Re(z) ≤ 0.Wir zeigen nun, dass |R(z)| ≤ 1 gilt.Dazu definieren wir die Anfangswertaufgabe u = Au mit
A =
(α −ββ α
),
wobei wir C und R2 miteinander identifizieren. Durch einfaches Nachrechnen sieht man,dass z, z ∈ σ(A) gilt, und aus
un = R(τA)un−1, vn = R(τA)vn−1
folgt
(Ay − Aw, y − w) = (y − w)TAT (y − w) = α(y − w)T (y − w) = α|y − w|2.
Damit ist die Anfangswertaufgabe u = Au dissipativ. Mit der vorausgesetzten B-Stabilitätdes Verfahrens folgt
|R(τA)(un−1 − vn−1)| ≤ |un−1 − vn−1|.
Mit w = un−1 − vn−1 folgen |R(τA)w| ≤ |w| und ‖R(τA)‖ ≤ 1 und mit z, z ∈ σ(A)folgt dann |R(τz)| ≤ 1 für alle τ > 0.
61
(4.17) DefinitionEin Runge-Kutta-Verfahren heißt algebraisch stabil, wenn gilt:
a) Die Matrix M = diag(b)A + AT diag(b) − bbT ∈ RS,S ist symmetrisch und positivsemidefinit.
b) bs ≥ 0 für alle s = 1, . . . , S.
(4.18) SatzAlgebraisch stabile Runge-Kutta-Verfahren sind B-stabil.
Beweis. Die Anfangswertaufgabe sei dissipativ und ohne Einschränkungen autonom. Set-ze
ks = f(un,s) mit un,s = un−1 + τ
S∑r=1
asrkr, un = un−1 + τS∑s=1
bsks,
ls = f(vn,s) mit vn,s = vn−1 + τS∑r=1
asrlr, vn = vn−1 + τS∑s=1
bsls
und setze
Us = un,s − vn,s, U0 = un−1 − vn−1, Ks = τ(ks − ls).
Damit folgt (Ks, Us) = τ(f(un,s)− f(vn,s), un,s − vn,s
)≤ 0, da −f monoton ist.
Es bleibt zu zeigen, dass |un − vn| ≤ |U0| = |un−1 − vn−1| gilt:
|un − vn|2 =
∣∣∣∣∣U0 +S∑s=1
bsKs
∣∣∣∣∣2
= |U0|2 + 2S∑s=1
bs(U0, Ks) +S∑
r,s=1
bsbr(Ks, Kr)
= |U0|2 + 2S∑s=1
bs(Us, Ks)︸ ︷︷ ︸≤0
+2S∑s=1
bs(U0 − Us, Ks) +S∑
r,s=1
bsbr(Ks, Kr)
≤ |U0|2 − 2S∑s=1
bs
S∑r=1
asr(Kr, Ks) +S∑
r,s=1
brbs(Ks, Kr)
= |U0|2 −S∑s=1
S∑r=1
(bsasr + bsars − bsbr︸ ︷︷ ︸=Msr
)(Ks, Kr)
≤ |U0|2,
denn es gilt, da M positiv semidefinit istS∑
s,r=1
Msr(Ks, Kr) =S∑
s,r=1
Msr
S∑q=1
KsqKrq =S∑
s,r,q=1
MsrKsqKrq =S∑q=1
zTq Mzq ≥ 0
für zq =
K1q...
KSq
(q = 1, . . . , S),
62
wobei Ksq die q-te Komponente des Vektors Ks bezeichnet (s = 1, . . . , S).
Konstruktion von B-stabilen Verfahren
(4.19) Definition (Kollokations-Verfahren)Zu Stützstellen 0 ≤ c1 < · · · < cS ≤ 1 definieren wir ein Kollokations-Verfahren durchein Polynom P ∈ PS mit
P (tn−1) = un−1,d
dtP (tn,s) = f(tn,s, P (tn,s))
mit tn,s = tn−1 + τcs für s = 1, . . . , S.
Falls die Interpolationsaufgabe lösbar ist, setze un := P (tn).
(4.20) LemmaDas Kollokations-Verfahren ist ein Runge-Kutta-Verfahren mit
bs =
∫ 1
0
Ls(t)dt, asr =
∫ cs
0
Lr(t)dt, Ls(t) =S∏
r=1,r 6=s
t− crcs − cr
für s = 1, . . . , S.
Beweis. Die Quadratur mit Stützstellen cs und den Gewichten bs ist exakt für PolynomeQ ∈ PS−1 und es gilt
un = un−1 +
∫ tn
tn−1
d
dtP (t)dt = un−1 + τ
∫ 1
0
(d
dtP
)(tn−1 + Θτ)dΘ
= un−1 + τS∑s=1
bsks, ks =
(d
dtP
)(tn,s) = f(tn,s, P (tn,s)).
Entsprechend gilt
un,s = P (tn,s) = un−1 +
∫ tn,s
tn−1
d
dtP (t)dt
= P (tn−1) + τ
∫ cs
0
(d
dtP
)(tn−1 + Θτ)︸ ︷︷ ︸
=∑Sr=1 krLr(θ)
dΘ
= P (tn−1) + τ
S∑r=1
kr
∫ cs
0
Lr(Θ)dΘ︸ ︷︷ ︸=:asr
.
BeispielA) Gauß-Verfahren
63
Kollokationsverfahren zu den Stützstellen der Gauß-Quadratur in [0, 1]
S = 1, p = 2 :
12
12
1
S = 2, p = 4 :
12−√
36
14
14−√
32
12−√
36
14
+√
36
14
12
12
B) Radau-Verfahren
Es existieren Stützstellen 0 < c1 < . . . < cS 6= 1, sodass die zugehörige Quadraturdie Ordnung 2S − 1 hat mit S = 3, p = 5 :
4−√
610
88−7√
6360
296−169√
61800
−2+3√
6225
4+√
610
296−169√
61800
88+7√
6360
−2−3√
6225
1 16−√
636
16+√
636
19
16−√
636
16+√
636
19
Bemerkunga) Gauß-Verfahren sind A, B-stabil und reversibel.
b) Radau-Verfahren sind A, B und L-stabil.
(4.21) SatzWenn die Quadratur (cs, bs) die Ordnung p hat, dann hat das zugehörige Kollokationsver-fahren auch die Ordnung p.Für das Gauß-Verfahren gilt p = 2S.
(4.22) SatzDas Kollokationsverfahren zur Gauß-Quadratur ist B-stabil.
Beweis. Sei −f monoton. Zu un−1 und vn−1 definiere Kollokationspolynome P,Q ∈ PSso dass gilt
un = P (tn), vn = Q(tn).
Setze
R(Θ) := |P (tn−1 + Θτn)−Q(tn−1 + Θτn)|2 ∈ P2S.
Damit folgt, da die Gauß-Quadratur exakt von der Ordnung 2S − 1 ist10
|un − vn|2 = |P (tn)−Q(tn)|2 = R(1) = R(0) +
∫ 1
0
R′(Θ)dΘ
= R(0) +S∑s=1
bsR′(cs) ≤ R(0) = |un−1 − vn−1|2 ,
10Siehe hierzu Numerik I.
64
denn bs > 0 und mit tn,s = tn−1 + csτn folgt
R′(cs) = 2(P ′(tn−1 + csτn)−Q′(tn−1 + csτn), P (tn,s)−Q(tn,s)
)= 2
(f(tn,s, P (tn,s)︸ ︷︷ ︸
=:y
)− f(tn,s, Q(tn,s)︸ ︷︷ ︸=:z
), P (tn,s)−Q(tn,s)︸ ︷︷ ︸=y−z
)= −2
(− f(tn,s, z)− (−f(tn,s, y)), z − y
)︸ ︷︷ ︸≥0
≤ 0.
Das war zu zeigen.
BemerkungDie Konzepte der A-Stabilität und B-Stabilität sind nicht äquivalent. Betrachte dazu
f(u) =
|u|3, u < 0
−u2, u ≥ 0.
Dann ist −f monoton. Betrachte die Anfangswertaufgaben
u = f(u), u(0) = −2 v = f(v), v(0) = 0, v ≡ 0,
für die |u(t)| ≤ |u(0)| für alle t ∈ [t0, t0 + T ] gilt.Betrachte die A-stabile implizite Trapez-Regel
0 0 01 1
212
12
12
,
die wegen R(z) = z+2z−2
nicht L-stabil ist.
Dann gilt für n = 1, τ = 367
, dass u1 = 52
ist und, da v0 = v1 = 0, gilt
|u1 − v1| =5
2> 2 = |u0 − v0|.
Also ist das Verfahren A-stabil, aber nicht B-stabil.
BemerkungFür dissipative Anfangswertaufgaben ist das Gauß-Verfahren wohldefiniert.
Beweis für S = 1. Zu un−1 bestimme z = un mit
un = un−1 + τf
(tn−1 +
τn2,1
2(un−1 + un)
),
d.h. löse
G(z) = un−1 + τf
(tn + tn−1
2,1
2(un−1 + z)
)− z = 0.
Idee: Betrachte y = G(y) und definiere z = limt→∞ y(t).
65
Es gilt, da −G strikt monoton ist
(G(z)−G(z), z − z
)=
(f
(t,
1
2(un−1 + z)
)− f
(t,
1
2(un−1 + z)
)− z − z,
z + un−1 − (z + un−1)
)≤ −|z − z|2.
Also gilt für y = G(y), w = G(w)
|y(t)− w(t)| ≤ exp(−t)|y(0)− w(0)| ∀t ≥ 0.
Damit gilt für den Fluss φ zu G für Θ = exp(−1) < 1
|φ(t, 1, y0)− φ(t, 1, w0)| ≤ Θ|y0 − w0|.
Definiere F (w) := φ(t, 1, w). Dann gilt für ein Θ ∈ (0, 1)
|F (y)− F (w)| ≤ Θ|y − w|,
d.h. F ist kontrahierend und mit dem Banach’schen Fixpunktsatz folgt die Existenz genaueines Fixpunktes z = F (z). Dann ist φ(t, τ, z) = z für alle τ > 0. Also gilt G(z) = 0.
(4.23) LemmaGauß-Verfahren sind reversibel.
Beweis. Für die Gauß-Quadratur gilt cs = 1− cS−s+1.Definiere Q(tn − τΘ) = P (tn−1 + τΘ). Dann folgen P (tn) = Q(tn−1) = un undP (tn−1) = Q(tn) = un−1 und damit
Q(tn − csτ) = f(tn − csτ,Q(tn − csτ)).
Somit folgt schließlich ψ(tn,−τn, ψ(tn−1, τn, z)) = z.
(4.24) DefinitionEine Funktion E : G → R heißt erstes Integral zur Differentialgleichungen u(t) =f(t, u(t)), falls E(u(t)) = const für alle t ∈ [t0, t0 + T ].
BeispielE(z) = zT z, f(z) = Az mit AT = −A schief-symmetrisch.
BezeichnungenDer Fluss φ heißt isometrisch, wenn E(z) = |z| ein erstes Integral ist.
(4.25) LemmaE ∈ C1(G) ist genau dann ein erstes Integral einer autonomen Differentialgleichungu = f(u), wenn E ′(z)f(z) = 0 gilt.
66
Beweis. Es gilt
d
dtE(u(t)) = E ′(u(t))u(t) = E ′(u(t))f(u(t)).
“⇒”: Es sei E(u(t)) = const. Dann folgt E ′(u(t))f(u(t)) = 0. Wähle z = u(0).“⇐”: Es gelte E ′(z)f(z) = 0. Dann folgt
E(u(t)) = E(u(0)) +
∫ t
0
d
dtE(u(s))ds = E(u(0)) = const .
Also gilt die Äquivalenz.
(4.26) SatzDie Differentialgleichung u = f(u) besitze ein quadratisches erstes Integral, d.h.
E(z) = zTQz + dT z + e
für ein Q ∈ RM,M und ein d ∈ RM .Dann gilt für das Gauß-Verfahren
E(un) = E(un−1).
Beweis. Sei P ∈ PS das Kollokationspolynom. Es gilt zu zeigen: E(P (tn)) = E(P (tn−1)).Definiere dazu R(t) = E(P (t)) ∈ P2S . Dann folgt
E(un) = E(P (tn)) = R(tn) = R(tn−1) +
∫ tn
tn−1
R′(t)︸ ︷︷ ︸∈P2S−1
dt
= R(tn−1) + τS∑s=1
bsR′(tn−1 + csτ) = R(tn−1) = E(un−1),
denn es gilt
R′(tn−1 + csτ) = E ′(P (tn,s)︸ ︷︷ ︸=z
) · f(P (tn,s)︸ ︷︷ ︸=z
) = 0.
Damit gilt die Behauptung.
67
5 Randwertaufgaben (RWA)
(5.1) Definition (Sturm-Liouville Randwertaufgabe)Seien a, b ∈ R und sei (a, b) ⊂ R ein Intervall, p ∈ C1((a, b)), q, r, f ∈ C((a, b)) undαj, βj, γj ∈ R gegeben.Bestimme u ∈ C2((a, b)) ∩ C1([a, b]) mit
−(p(x)u′(x)
)′+ q(x)u′(x) + r(x)u(x) = f(x) ∀x ∈ (a, b)
und Randwerten
α0u(a) + α1u′(a) + β0u(b) + β1u
′(b) = γ0,
α2u(a) + α3u′(a) + β2u(b) + β3u
′(b) = γ1.
BeispielBetrachte die freie Schwingung mit der Gleichung
−u′′ + ω2u = 0 (ω > 0)
und der Lösung
u(x) = c0 sin(ωx) + c1 cos(ωx).
Für (a, b) =(0, π
ω
)ergeben sich folgende Fälle:
0) Gilt u(a) = γ0, u′(a) = γ1, dann ist die Anfangswertaufgabe eindeutig lösbar.
1) Wenn u(a) = u(b) = u′(a) = u′(b) = 0 gilt, dann gibt es nur die eindeutige Lösungu ≡ 0.
2) Im Falle von u(a) = u(b) gibt es unendlich viele Lösungen c0, c1 ∈ R.
3) Für u(a) = 0, u(b) = 1 gibt es keine Lösung.
Sturm-Liouville-Randwertaufgabe als System Setze v = u′ und es gelte p(x) 6= 0 füralle x ∈ (a, b). Dann folgt
−pv′ − p′v + qv + ru = f
und damit gilt(u′
v′
)=
(0 1rp
q−p′p
)·(uv
)+
(0
−fp
)mit den Randwerten(
α0 α2
α1 α3
)·(u(a)v(a)
)+
(β0 β2
β1 β3
)·(u(b)v(b)
)=
(γ0
γ1
).
68
(5.2) Definition (allgemeine inhomogene lineare Randwertaufgabe)Sei I = (a, b) ⊂ R ein Intervall und seien A ∈ C(I,RM,M), b ∈ C(I,RM), Ba, Bb ∈RM,M und g ∈ RM gegben.
Bestimme u ∈ C1((a, b),RM) ∩ C([a, b],RM) mit
u′(x) = A(x)u(x) + b(x) x ∈ (a, b),
Bau(a) +Bbu(b) = g.
(5.3) SatzSei u0 ∈ C1(I,RM) eine Lösung der inhomogenen Anfangswertaufgabe
(u0)′ = Au0 + b, u0(a) = 0M
und sei um ∈ C1(I,RM) eine Lösung der homogenen Anfangswertaufgabe
(um)′ = Aum, um(a) = em, m = 1, . . . ,M.
Dann ist
U(x) =(u1(x)| · · · |uM(x)
)∈ RM,M
ein Fundamentalsystem und jede Lösung von (5.2) hat die Form
u(x) = u0(x) +M∑m=1
ymum(x),
wobei y ∈ RM eine Lösung der linearen Gleichung[Ba +BbU(b)
]y = g −Bbu
0(b)
ist.
Wir werden häufig die Bezeichnung
Q := Ba +BbU(b) ∈ RM,M
verwenden.
Also gilt die Fredholm’sche Alternative:
a) Q = Ba +BbU(b) ist regulär. Dann ist (5.2) eindeutig lösbar.
b) Q ist singulär. Dann gibt es die folgenden Möglichkeiten
b1) Qy = g −Bbu0(b) lösbar. Dann ist die Randwertaufgabe mehrdeutig lösbar.
b2) Qy = b−Bbu0(b) nicht lösbar. Dann ist auch die Randwertaufgabe nicht lösbar.
Völlig analog lässt sich nun eine numerische Lösung definieren.
69
(5.4) SatzSei u0
h eine diskrete Lösung der Anfangswertaufgabe
(u0)′ = Au0 + b, u0h(a) = 0M
und sei umh eine diskrete Lösung der Anfangswertaufgabe
(um)′ = Aum, umh (a) = em, m = 1, . . . ,M
mit h = b−aN
, xn = a+ nh.Definiere
Uh :=(u1h| · · · |uMh
),
Qh := Ba +BbUh(b) ∈ RM,M .
Sei yh ∈ RM eine Lösung von
Qhyh = g −Bbu0h(b),
und setze
uh := u0h +
M∑m=1
yh,mumh
und für umh gelte
|umh (xn)− um(xn)| = O(hp) (m = 0, . . . ,M).
Dann gilt:Wenn Q = Ba + BbU(b) regulär ist, dann existiert ein h0 > 0, sodass Qh für h < h0
regulär ist und für die Lösung der Randwertaufgabe gilt
|u(xn)− uh(xn)| = O(hp).
Beweis. Der Beweis erfolgt in vier Schritten.
i) Es gilt in der Spektralnorm
‖Q−Qh‖ ≤ ‖Bb
(U(b)− Uh(b)
)‖ ≤ ‖Bb‖‖U(b)− Uh(b)‖
≤ ‖Bb‖ maxm=1,...,M
|um(b)− umh (b)| = O(hp).
Demnach existiert zu jedem c ∈ (0, 1) ein h0 > 0 mit
‖Q−Qh‖ ≤c
‖Q−1‖
für h ≤ h0.
70
ii) Nun gilt für h < h0
‖Q−1(Q−Qh)‖ ≤ ‖Q−1‖‖(Q−Qh)‖ ≤ c < 1,
woraus mit der Neumannreihe die Regularität von Q−1Qh = IM − Q−1(Q − Qh)folgt. Dabei ist
(Q−1Qh)−1 =
∞∑k=0
(Q−1(Q−Qh)
)k.
Somit ist auch Qh regulär. Ferner liefert die Neumannreihe die Abschätzung
‖(Q−1Qh)−1‖ ≤ 1
1− ‖Q−1(Q−Qh)‖.
Mit ‖Q−1h ‖ = ‖(QQ−1Qh)
−1‖ = ‖(Q−1Qh)−1Q−1‖ ≤ ‖(Q−1Qh)
−1‖‖Q−1‖ folgt
‖Q−1h ‖ ≤
‖Q−1‖1− ‖Q−1(Q−Qh)‖
≤ ‖Q−1‖
1− c
und es gilt mit i)
‖Q−1 −Q−1h ‖ = ‖Q−1(Qh −Q)Q−1
h ‖ ≤‖Q−1‖2
1− c‖Q−Qh‖
≤ O(hp), h < h0.
iii) Ferner gilt
y − yh = Q−1(g −Bbu0(b))−Q−1
h
(g −Bbu
0h(b)
)= (Q−1 −Q−1
h )(g −Bbu
0h(b)
)+Q−1Bb
(u0h(b)− u0(b)
)Somit folgt |y − yh| = O(hp).
iv) Letztendlich gilt
|u(xn)− uh(xn)| =∣∣∣u0(xn)− u0
h(xn) +M∑m=1
(ymu
m(xn)− yh,mumh (xn)
− yh,mum(xn) + yh,mum(xn)︸ ︷︷ ︸
=0
)∣∣∣≤ |u0(xn)− u0
h(xn)|+M maxm=1,...,M
|um(xn)| |ym − yh,m|
+M maxm=1,...,M
|yh,m| |um(xn)− umh (xn)|
= O(hp)
Das war zu zeigen.
71
Nichtlinearen RandwertaufgabenAnwendung (Variationsrechnung)Wir wollen die Geodätische auf der Mannigfaltigkeit M = S2 (Einheitssphäre) bestim-men. Seien dazu A,B ∈ M gegeben. Wir suchen nun eine Kurve c : [0, 1] → M mitc(0) = A, c(1) = B und minimaler Länge, d.h.∫ 1
0
|c(t)| dt = Min!
Nach Einführung von sphärischen Koordiaten erhalten wir
c(t) =
cosφ(t) cosψ(t)cosφ(t) sinφ(t)
sinφ(t)
∈ S2 , φ(t) ∈(−π
2,π
2
), ψ(t) ∈ (0, π) ,
und damit
l(c) =
∫ 1
0
√[cosψ(t)]2φ(t) + ψ(t)2︸ ︷︷ ︸
=:L(t,(φψ),(
φ
ψ))
dt.
Da wir ein Minimum von l(c) suchen, muss δl(c) = 0 gelten. Das führt zur Euler-Lagrange-Gleichung
d
dtD3L
(t,
(φ
ψ
),
(φ
ψ
))= D2L
(t,
(φ
ψ
),
(φ
ψ
)).
Daraus folgt
φ = 2 tanψφψ, ψ = − sinψ cosψφ2.
BeispielNichtlineare Zweipunkt-Randwertaufgabe zweiter Ordnung:
u′′ = f(x, u(x), u′(x)
), x ∈ (a, b), f ∈ C(I × R× R)
u(a) = ua, u(b) = ub.
Beispiel (Schieß-Verfahren (eindimensionaler Fall))Zu v ∈ R berechne die Anfangswertaufgabe
(uv)′′ = f(x, uv, (uv)′
),
uv(a) = ua, (uv)′(a) = v
Setze F (v) = uv(b)− ub. Nach dem Gronwall-Lemma (1.12) ist F stetig.Wir nehmen nun an, dass F differenzierbar ist und F ′ sich durch den Differenzenquotien-ten approximieren lässt:
F ′(v) ≈ 1
δ
(F (v + δ)− F (v)
).
72
AlgorithmusS0) Wähle v ∈ R, δ > 0 und ε > 0.
S1) Berechne uv(b).
S2) Falls |uv(b)− ub| < ε: STOPP.
S3) Berechne uv+δ(b), J = 1δ
(uv+δ(b)− uv(b)
)S4) Berechne v := v − 1
J
(uv(b)− ub
)und gehe zu S1)
(5.5) Definition (Allgemeine Randwertaufgabe)Seien I = [a, b], f ∈ C(I × RM ,RM) und r ∈ C(RM × RM) gegeben.
Bestimme u ∈ C1(I,RM) mit
u′(x) = f(x, u(x)), x ∈ (a, b)
r(u(a), u(b)
)= 0.
Beispiel (Schieß-Verfahren)Bestimme v ∈ RM , sodass die Lösung der Anfangswertaufgabe
(uv)′(x) = f(x, uv(x)
), x ∈ (a, b)
uv(a) = v
die Bedingung r(v, uv(b)
)= 0 erfüllt.
Damit ein Newton-Verfahren sinnvoll ist, muss die Lösung der Anfangswertaufgabe diffe-renzierbar von v abhängen.
(5.6) SatzSei f ∈ C1(I × RM ,RM). Dann ist uv nach v differenzierbar mit
J = Dvuv ∈ C1(I, RM,M)
Jm,k(x) = limδ→0
1
δ
(uv+δek
m − uvm)
(x)
und J erfüllt die lineare Matrix-Anfangswertaufgabe
J ′(x) = D2f(x, uv(x))︸ ︷︷ ︸=A(x)
J(x), J(a) = I , (∗)
d.h., J ist ein Fundamentalsystem zur linearen Anfangswertaufgabe u′ = A(x)u.
Beweis. Zeige: Die Lösung J ∈ C1(I, RM,M) der Gleichung (∗) erfüllt
J(x)ek = limδ→0
1
δ
(uv+δek(x)− uv(x)
).
73
Dazu setzen wir w := v + δek für festes δ. Dann gilt
1
δ(uw − uv)(x) =
1
δ(uw(a)− uv(a)) +
1
δ
∫ x
a
((uw)′(y)− (uv)′(y)) dy
=1
δ(w − v) +
1
δ
∫ x
a
(f(y, uw(y)
)− f
(y, uv(y)
))dy
= ek +1
δ
∫ x
a
[∫ 1
0
(d
dλf(y, uv(y) + λ
(uw(y)− uv(y)
)))dλ
]dy
= ek +
∫ x
a
∫ 1
0
D2f(y, uv(y) + λ
(uw(y)− uv(y)
))dλ
1
δ
(uw(y)− uv(y)
)dy.
Es gilt
J(x)ek = J(a)ek +
∫ x
a
J ′(y)ek dy = ek +
∫ x
a
D2f(y, uv(y)
) [J(x)ek
]dy .
Nach dem Gronwall-Lemma (1.12) gilt limδ→0 uw(x) = uv(x) gleichmäßig in (a, b). Da f
stetig differenzierbar ist, konvergiert also∫ 1
0D2f
(y, uv(y)+λ
(uw(y)−uv(y)
))dλ gegen
D2f(y, uv(y)
)für δ −→ 0.
Da die Lösung der linearen AWA (*) eindeutig ist, existiert der Grenzwert
limδ→0
1
δ
(uw(x)− uv(x)
)= J(x)ek .
d.h. 1δ
(uw(x)− uv(x)
)konvergiert gegen die eindeutige Lösung z(x) = J(x)ek der AWA
z(x)′ = A(x)z(x) mit z(a) = ek. Das wollten wir zeigen.
Algorithmus (Schieß-Verfahren für allgemeine Randwertaufgaben)S0) Wähle Startwert v ∈ R und ε > 0.
S1) Berechne uv(b) durch Lösen der Anfangswertaufgabe
(uv)′(x) = f(x, uv(x)
), uv(a) = v.
Berechne F (v) = r(v, uv(b)
)∈ RM .
Falls |F (v)| < ε: STOPP.
S2) Berechne eine Approximation δF (v) von F ′(v) spaltenweise:Für δ > 0 berechne uv+δek und setze
δF (v)ek :=1
δ
(F (v + δek)− F (v)
)k = 1, . . . ,M.
S3) Setze v := v − δF (v)−1F (v).
Gehe zu S1).
Bemerkunga) Im Allgemeinen sind Homotopie- bzw. Dämpfungsstrategien notwendig.
74
b) Wenn f, r glatt sind und u eine isolierte Lösung11 ist, dann gelten
1) F ∈ C2(U,RM) in einer Umgebung U ⊂ RM von u(a).
2) F (u(a)) = 0 ist die einzige Nullstelle in U .
3) F ′(u(a)) ist regulär.
In diesem Fall ist das Schieß-Verfahren konvergent.
Die Mehrzielmethode (multiple shooting)
BeispielBetrachte auf dem Intervall I = [0, 10] die Differentialgleichung
u′′(x)− u′(x)− 110u(x) = 0
mit dem charakteristischen Polynom λ2 − λ − 110 = (λ − 11)(λ + 10). Also ist dieallgemeine Lösung von der Form
u(x) = y1 exp(−10x) + y2 exp(11x).
Mit den Anfangswerten u1(0) = 1, u2(0) = 1, (u1)′(0) = 0 und (u2)′(0) = 1 ergibt sichein Fundamentalsystem
u1(x) =11
21exp(−10x) +
10
21exp(11x) ,
u2(x) = − 1
21exp(−10x) +
1
21exp(11x) .
Für u(0) = u(10) = 1 gilt u = u1 + y2u2 mit
y2 = −10 +21 + exp(−100)
exp(110)− exp(−110)≈ −10 + 3.5 · 10−47 ,
d.h., der Koeffizient y2 ist mit normaler Rechner-Arithmetik nicht darstellbar und somitauch durch ein einfaches Schießverfahren nicht berechenbar.
Stabilitätsanalyse für lineare Anfangswertaufgaben u′ = Au+ f . Für beliebige An-fangswertaufgaben erhält man folgende Fehlerabschätzung für zwei Lösungen u und u
|u(b)− u(b)| ≤ exp((b− a)L
)|u(a)− u(a)|.
Dabei ist L ≥ Reλ für alle Eigenwerte λ von A.
11Eine isolierte Lösung ist lokal eindeutig.
75
Stabilitätsanalyse für lineare Randwertaufgaben u′ = Au mit den RandbedingungenBau(a) +Bbu(b) = 0. Sei U(x) ein Fundamentalsystem und es gelte
U ′ = AU, U(a) = I, Q = Ba +BbU(b).
Definiere die Green’sche Funktion
G(x) =
−U(x)Q−1BbU(y)−1, x < y
U(x)Q−1BaU(y)−1, x > y.
Dann löst
u(x) =
∫ b
a
G(x, y)b(y)dy + U(x)Q−1g
die Randwertaufgabe und es gilt
‖u‖∞ ≤ C
(∫ b
a
|b(y)|dy + ‖U(x)Q−1‖)
mit C = maxx,y
‖G(x, y)‖, ‖U(x)Q−1‖
.
BeispielSei A =
(0 11 0
). Dann ist L = 1 und somit hat die Anfangswertaufgabe die Kondition
exp(b− a).
Aus der Stabilitätsanalyse folgt, dass das Randwertproblem für große Zeitintervalle vielbesser konditioniert ist, als die Anfangswertaufgabe. Für zu große Intervalle kann die An-fangswertaufgabe sogar so schlecht konditioniert sien, dass das einfache Schießverfahrenumerisch nicht durchführbar ist. Die Mehrzielmethode zerlegt daher das Itervall [a, b] inso kleine Teilintervalle, dass die Kondition der Anfangswertaufgabe nicht zu groß ist. DieForderung, dass die Lösung an den Intervallgrenzen stetig ist, ergibt ein Gleichungssys-tem.
AlgorithmusS0) Wähle eine Zerlegung a = x0 < x1 < · · · < xR = b.
Wähle Startwerte v = (v0, ..., vR) ∈ RM(R+1).
S1) Berechne Approximation ur der AWA mit
(ur)′ = f(x, ur), uv(xr−1) = vr−1 .
berechne G(v) := (Gr(v))r=0,...,R mit G0(v) = g(v0, vR) und Gr(v) = ur(xr)− vrfür r = 1, ..., R.Falls |G(v)| klein genug: STOP
S2) Berechne eine Approximation ∆G(v) von G′(v).
S3) Berechne v := v −(∆G(v)
)−1G(v). Gehe zu S1).
76
Wir analysieren das Verfahren nur für lineare Randwertaufgaben u′ = Au. Sei U dasFundamentalsystem mit U ′ = AU und U(a) = IM . Dann ist G0(v) = Bav
0 + BbvR − g
und ur(x) = U(x)U−1(xr−1)vr−1, d.h. Gr(v) = vr−U(x)U−1(x−1)vr−1 für r = 1, ..., R.Damit ergibt sich für
G′ =
Ba 0 · · · Bb
−U(x1)U−1(x0) IM · · · 0· · ·
0 0 · · · −U(xR)U−1(xR−1) IM
.
Die Block-LR-Zerlegung ist
G′ =
Q1 Q2 · · · QR
0 IM · · · 0· · ·
0 0 · · · IM
IM 0 · · · 0−U(x1)U−1(x0) IM · · · 0
· · ·0 0 · · · −U(xR)U−1(xR−1) IM
.
mit QR = BbU(xR)U−1(xR−1), Qr = Qr+1U(xr)U−1(xr−1) für r = R − 1, ..., 2 und
Q1 = Ba +Q2U(x1) = Ba +BbU(xR) = Q. Damit erhalten wir das folgende Resultat:
(5.7) SatzWenn die lineare Randwertaufgabe (5.2) eindeutig lösbar ist, dann ist Q1 = Q regulärund damit auch G. Dann besitzt auch die Mehrzielmethode eine eindeutige Lösung.
Für lineare Randwertaufgaben und ∆G(v) = G′(v) wird die Lösung in einem Schrittberechnet.
77
Finite-Differenzen-VerfahrenBeispielBetrachte die Randwertaufgabe
−u′′(x) = f(x), x ∈ (0, 1), u(0) = u(1) = 0.
Sei u ∈ C2((0, 1)) ∩ C([0, 1]) eine Lösung. Dann gilt
u(x) = u(0) +
∫ x
0
u′(y)dy = u(0) +
∫ x
0
(u′(0) +
∫ y
0
u′′(z)dz
)dy
= u(0)︸︷︷︸=:c0=0
+xu′(0)︸︷︷︸=:c1
−∫ x
0
∫ y
0
f(z)dz︸ ︷︷ ︸=:F (y)
dy.
Mit partieller Integration folgt∫ x
0
F (y)dy =[yF (y)
]y=x
y=0−∫ x
0
yf(y)dy = x
∫ x
0
f(y)dy −∫ x
0
yf(y)dy
=
∫ x
0
(x− y)f(y)dy
und durch Einsetzen sieht man
u(1) = 0 = c1 −∫ 1
0
F (y)dy.
Damit folgt
c1 =
∫ 1
0
(1− y)f(y)dy
und somit
u(x) = x
∫ 1
0
(1− y)f(y)dy +
∫ x
0
(y − x)f(y)dy =
∫ 1
0
G(x, y)f(y)dy
mit der Green’schen Funktion
G(x, y) =
y(1− x), 0 ≤ y ≤ x,
x(1− y), x ≤ y ≤ 1.
Folgerung
a) Es gilt G(x, y) ≥ 0 für x, y ∈ [0, 1] und damit folgt, dass aus f ≥ 0 auch u ≥ 0 folgt.
b) Da für alle stetigen f eine Lösung existiert, liefert (5.3), dass diese Lösung eindeutigist.
78
c) Es gilt die a-priori-Abschätzung
‖u‖∞ = maxx∈[0,1]
|u(x)| ≤ maxx∈[0,1]
∫ 1
0
|G(x, y)||f(y)|dy
≤ ‖f‖∞ maxx∈[0,1]
∫ 1
0
|G(x, y)|dy
= ‖f‖∞ maxx∈[0,1]
1
2x(1− x) =
1
8‖f‖∞.
(5.8) SatzSei h > 0, x ∈ R und [x− h, x+ h] ⊂ I . Dann gilt für hinreichend glatte u ∈ Cp(I)
u′(x) =1
h
(u(x+ h)− u(x)
)+ hR1(u, x) mit |R1(u, x)| ≤ 1
2‖u′′‖∞,
u′(x) =1
h
(u(x)− u(x− h)
)+ hR2(u, x) mit |R2(u, x)| ≤ 1
2‖u′′‖∞,
u′(x) =1
2h
(u(x+ h)− u(x− h)
)+ h2R3(u, x) mit |R3(u, x)| ≤ 1
6‖u′′′‖∞,
u′′(x) =1
h2
(u(x+ h)− 2u(x)− u(x− h)
)+ h2R4(u, x) mit |R4(u, x)| ≤ 1
12‖u′′′′‖∞.
Beweis. Ohne Beweis.
Setze
∂hu(x) :=1
2h
(u(x+ h)− u(x− h)
).
Beispiel (Linearer Sturm-Liouville-Operator)Approximiere L mit
Lu = −(pu′)′ + qu′ + ru auf (a, b) mit u(a) = u(b) = 0
durch Lh mit
Lhu = −∂h/2(p∂h/2u) + q∂hu+ ru
auf ∆ = ∆h = xn = a+ nh, n = 1, . . . , N, wobei h := b−aN+1
sei.
Dann folgt für die Lösung uh der diskreten Aufgabe Lhuh = fh
−(pn− 1
2un−1 −
(pn− 1
2+ pn+ 1
2
)un + pn+ 1
2un+1
)+
1
2hqn(un+1 − un−1) + h2rnun = h2fn
für (1 ≤ n ≤ N) mit u0 = uN+1 = 0, pn+ 12
= p(xn + 1
2h), qn = q(xn), rn = r(xn),
fn = f(xn) und uh =
( u1...uN
).
Setze fh :=
(f1...fN
). Dann folgt Ahuh = fh mit der Tridiagonalmatrix Ah ∈ RN,N
Ah =1
h2
p 1
2+ p 3
2+ h2r1 −p 3
2+ 1
2hq1
. . .−pn− 1
2− 1
2hqn pn− 1
2+ pn+ 1
2+ h2rn −pn+ 1
2+ 1
2hqn
. . .
.
79
BeispielIm Fall −u′′ = f ergibt sich A = 1
h2
( 2 −1−1 2 −1
. . .−1 2
).
BezeichnungenZu u ∈ C([a, b]) definiere
Ihu :=
u(x1)...
u(xN)
und
‖u‖∞,∆ := maxn=1,...,N
|u(xn)| = |Ihu|∞.
Wir werden in den Normabschätzungen oft die Funktionen mit ihren jeweiligen linearenInterpolationen an den Sützstellen x1, . . . , xN identifizieren und umgekehrt.
(5.9) DefinitionEine Finite-Differenzen-Approximation heißt
a) konsistent von der Ordnung p, wenn gilt
‖LhIhu− fh‖∞,∆ = O(hp),
b) stabil, C > 0 unabhängig von h ∈ (0, h0) existiert mit ‖L−1h ‖∞,∆ ≤ C.
(5.10) SatzEine Finite-Differenzen-Diskretisierung ist konvergent (von der Ordnung p), wenn sie kon-sistent (von der Ordnung p) und stabil ist.
Beweis. Es gilt
‖u− uh‖∞,∆ = ‖Ihu− uh‖∞,∆ = ‖L−1h Lh(Ihu− uh)‖∞,∆
≤ ‖L−1h ‖∞,∆︸ ︷︷ ︸≤C
‖LhIhu− fh‖∞,∆︸ ︷︷ ︸=O(hp)
= O(hp)
und damit ist das Verfahren konvergent von der Ordnung p.
(5.11) SatzFür A ∈ RN,N gelte:
a) A ist stark diagonal dominant, d.h.
N∑k=1,k 6=n
|A[n, k]| ≤ |A[n, n]|, n = 1, . . . , N
und es existiert ein j ∈ 1, . . . , N mit
N∑k=1,k 6=j
|A[j, k]| < |A[j, j]|.
80
b) A ist irreduzibel, d.h. zu jedem Paar j 6= n existiert eine Folge j = j0, j1, j2, . . . , jR =n mit
A[j1, j0] 6= 0, A[j2, j1] 6= 0, . . . , A[jR, jR−1] 6= 0.
Dann gelten:
1) A ist regulär.
2) Falls A[n, n] > 0 für n = 1, . . . , N , dann ist A positiv definit12.
3) Falls A[n, n] > 0 und A[n, k] ≤ 0 für n, k = 1, . . . , N und n 6= k, dann gilt A−1 ≥ 0,d.h. A−1[n, k] ≥ 0 für alle n, k = 1, . . . , N .Eine solche Matrix heißt M-Matrix.
Beweis. Da A irreduzibel ist, folgt aus a)
N∑k=1,k 6=n
|A[n, k]| > 0
und damit |A[n, n]| > 0 für alle n = 1, . . . , N . Also existiert zu A = D + L + R mitD = diag(A),L = lower(A),R = upper(A) die Matrix J := D−1(L+R) = D−1A−I .13
Behauptung: ρ(J) < 1.
Sei µ ∈ C ein Eigenwert von J mit Eigenvektor w ∈ CN\0 und es gelte ohne Ein-schränkungen |w|∞ = 1. Wähle n ∈ 1, . . . , N mit |wn| = 1. Dann folgt
|µ| = |µwn| = |(Jw)n| =
∣∣∣∣∣A[n, n]−1
N∑k=1,k 6=n
A[n, k]wk
∣∣∣∣∣≤ |A[n, n]|−1
N∑k=1,k 6=n
|A[n, k]|a)
≤ 1.
Also gilt ρ(J) ≤ 1.
Annahme: Es existiert ein µ ∈ σ(J) mit |µ| = 1.
Wähle j mit der zweiten Forderung von a). Dann gilt
|wj| = |µwj| ≤ |A[j, j]−1|N∑
k=1,k 6=j
|A[j, k]|a)< 1 .
12Eine Matrix A ∈ RN,N heißt positiv definit, wenn zTAz > 0 für alle z ∈ Rn\0. Ist A positiv definit,dann gilt Reλ > 0 für alle λ ∈ σ(A).
13 −J ist die Iterationsmatrix zum Jacobi-Verfahren. Siehe dazu Numerik I.
81
Nun wähle j = j0, j1, . . . , jR = n mit der Eigenschaft b). Dann gilt
|wj1| = |µwj1 | ≤ |A[j1, j1]−1|N∑
k=1,k 6=j1
|A[j1, k]||wk|
= |A[j1, j1]|−1
(N∑
k 6=j,k 6=j1
|A[j1, k]| |wk|︸︷︷︸≤1
+ |A[j1, j]|︸ ︷︷ ︸6=0
|wj|︸︷︷︸<1
)
< |A[j1, j1]|−1
N∑k 6=j1
|A[j1, k]|a)
≤ 1.
Damit folgt induktiv |wjr | < 1 für r = 1, . . . , R. Es gilt aber dann |wn| = |wjR | < 1,was ein Widerspruch zu |wn| = |w|∞ = 1 ist. Also ist die Annahme falsch und es giltρ(J) < 1.Nun können wir die drei behaupteten Eigenschaften zeigen:Zu 1): Annahme: Es existiert ein w ∈ CN\0 mit Aw = 0.Dann folgt 0 = Aw = Dw + (L + R)w = D(w − Jw) und somit Jw = w. Das heißtaber, dass w ein Eigenvektor von J zum Eigenwert µ = 1 ist. Das ist ein Wiederspruch zuρ(J) < 1.Zu 2): Sei λ ∈ C ein Eigenwert von A mit Aw = λw für ein w ∈ CN\0 und sei ohneEinschränkungen |w|∞ = 1. Wähle n ∈ 1, . . . , N mit wn = 1. Dann gilt
|λ− A[n, n]| = |λwn − A[n, n]wn|
=
∣∣∣∣∣N∑k=1
A[n, k]wk − A[n, n]wn
∣∣∣∣∣ =
∣∣∣∣∣N∑
k=1,k 6=n
A[n, k]wk
∣∣∣∣∣≤
N∑k=1,k 6=n
|A[n, k]|a)
≤ |A[n, n]| = A[n, n].
Damit folgt∣∣∣ λA[n,n]
− 1∣∣∣ ≤ 1. Aus A[n, n] > 0 folgt damit |λ − A[n, n]| ≤ A[n, n] und
insbesondere Reλ ≥ 0; weiterhin gilt Reλ = 0 nur dann wenn λ = 0 ist. Da A regulärist, tritt dieser Fall nicht auf. Also gilt Reλ > 0 für alle Eigenwerte von A.Zu 3): Es ist A[n, n] = D[n, n] > 0 und damit auch D[n, n]−1 > 0 und nach Vor-aussetzung gilt L,R ≤ 0 (elementweise). Somit folgen −J = −D−1(L + R) ≥ 0 undρ(−J) < 1.Aus Numerik I wissen wir, dass dann eine Norm ‖ · ‖ existiert, sodass ‖ − J‖ < 1 gilt.Dann liefert die Neumann’sche Reihe die Invertierbarkeit von IN + J mit
(In + J)−1 =∞∑k=0
(−J)k ≥ 0
und damit folgt schließlich mit
A−1 = (D + L+R)−1 = (IN + J)−1D−1 ≥ 0
die letzte Behauptung.
82
Anwendung1) Betrachte −u′′ = f in (a, b) mit u(a) = u(b) = 0. Es folgt Lu = −u′′.
Für die Diskretisierung gilt
Lhu(xn) = −∂2h/2u(xn) = −∂h/2
(∂h/2u
)(xn)
=1
h2
(− u(xn + h) + 2u(xn)− u(xn − h)
).
Konsistenz:
Mit f = Lu und Ihf = fh folgt fh = IhLu und somit gilt
‖LhIhu− fh‖∞,∆ = ‖LhIhu− IhLu‖∞,∆= max
n=1,...,N
∣∣−∂h/2 (∂h/2u) (xn) + u′′(xn)∣∣
(5.8)≤ 1
12h2‖uiv‖∞.
Stabilität:
Die Matrix
Ah =1
h2
2 −1−1 2 −1
. . .−1 2 −1
−1 2
ist stark diagonal dominant und irreduzibel. Dann folgt mit (5.11), dass Ah regulärund A−1
h ≥ 0 ist.
Also gilt für fh =
(f1...fN
)und e =
(1...1
)∈ RN :
‖L−1h f‖∞,∆ = max
n=1,...,N
∣∣∣∣∣N∑k=1
A−1h [n, k]fk
∣∣∣∣∣ ≤ maxn=1,...,N
N∑k=1
A−1h [n, k]|fk|
≤ ‖f‖∞,∆ maxn=1,...,N
N∑k=1
A−1h [n, k]|ek| = ‖f‖∞,∆‖L−1
h e‖∞,∆
Damit folgt
‖L−1h ‖∞,∆ = sup
f 6=0
‖L−1h f‖∞,∆‖f‖∞,∆
≤ ‖L−1h e‖∞,∆.
Die RWA Lw ≡ 1 (d.h. −w′′ = 1) mit w(a) = w(b) = 0 läßt sich explizit lösen: Es giltw(x) = 1
2(x− a)(b− x), und wh = Ihw löst Lhwh = e.
Also ist das Verfahren stabil, denn es gilt
‖L−1h e‖∞,∆ = ‖wh‖∞,∆ ≤
1
8(b− a)2,
83
und (5.10) liefert die Konvergenz der Ordnung 2 mit
‖u− uh‖∞,∆ ≤1
12· 1
8(b− a)2h2‖u′′′′‖∞.
Beispiel (Singulär gestörte Randwertaufgabe)Wir betrachten die Randwertaufgabe
Lu(x) := −εu′′(x) + u′(x)!
= 0, x ∈ (0, 1), u(0) = 1, u(1) = 0.
Wir setzen für die lineare homogene Differentialgleichung die Lösunguε(x) = c0 + c1 exp(λt) an. Einsetzen in die Differentialgleichung liefert
−ελ2 + λ = ε
(1
ε− λ)λ = 0
und damit λ = 1ε. Also hat die Lösung die Gestalt
uε(x) = c0 + c1 expx
ε.
Durch Hinzunahme der Randwerte ergibt sich für jedes ε > 0 die eindeutige Lösung
uε(x) =exp 1
ε− exp x
ε
exp 1ε− 1
.
Für ε 1 und x = 1− δ, (δ > ε) gilt
uε(1− δ) =exp 1
ε
exp 1ε− 1
(1− exp
(−δε
))≈ 1.
Der Grenzwert u0 := limε→0 uε ≡ 1 erfüllt aber nicht die Randbedingung u(1) = 0.
Sprechweise: Die Lösung hat eine Grenzschicht.
a) Zentrale Differenzen
Der Ansatz
ε
h2(−un−1 + 2un − un+1) +
1
2h(−un−1 + un+1) = 0
führt zu (−ε− 1
2h
)un−1 + 2εun +
(−ε+
1
2h
)un+1 = 0, u0 = 1, uN+1 = 0.
Wir lösen die Dreitermrekursion mit dem Ansatz un = c+λn+ + c−λ
n−, wobei λ± die
Nullstellen des charakteristischen Polynoms
P (λ) = λ2 +2ε
12h− ε
λ−12h+ ε
12h− ε
84
sind. Es ergibt sich
λ± =−ε±
√ε2 +
(12h+ ε
) (12h− ε
)12h− ε
=ε∓ 1
2h
ε− 12h
und damit ist λ+ = 1. Die Randbedingungen liefern die beiden Gleichungen
c+ + c− = 1, c+λN+1+ + c−λ
N+1− = 0,
welche zu
c+ =λN+1
+
λN+1+ − λN+1
−und c− = − λN+1
−
λN+1+ − λN+1
−
führen. Damit und mit λ+ = 1 ergibt sich schließlich
un =λN+1
+ λn− − λN+1− λn+
λN+1+ − λN+1
−=λn− − λN+1
−
1− λN+1−
.
Nun gilt λ− ≈ −1 für ε 12h und somit oszilliert un, wodurch die Stabiliät verloren
geht.
Beobachtung: Konsistenz zweiter Ordnung, aber eine Schrittweitenbeschränkung istfür die Stabilität erforderlich.
b) Upwind-Verfahren
Wir definieren die einseitigen Differenzenquotienten durch
∂+h u(x) :=
1
h
(u(x+ h)− u(x)
), ∂−h u(x) :=
1
h
(u(x)− u(x− h)
).
Damit approximieren wir
q(x)u′(x) ≈
q(x)∂−h u(x), q(x) ≥ 0,
q(x)∂+h u(x), q(x) < 0.
Anwendung auf Lu := −εu′′ + u′ = 0 liefert14
Lhuh = −ε∂2
huh + ∂−h u
h
und damit
(−ε− h)un−1 + (2ε+ h)un − εun+1 = 0.
Löse nun
λ2 − 2ε+ h
ελ+
ε+ h
ε= 0.
14 Dabei ist ∂2hu(xn) = ∂h/2(∂h/2u(xn)) =1h2 (un−1 − 2un + un+1).
85
Das ergibt
λ± =2ε+ h
2ε±√
(2ε+ h)2
4ε2− ε+ h
ε=
2ε+ h± h2ε
.
Also gilt λ+ = ε+hε
und λ− = 1.
Mit u0 = 1 und uN+1 = 0 ergibt sich
un =λN+1
+ − λn+λN+1
+ − 1,
was keine Oszillationen mehr aufweist.
Vorteil: Das Verfahren ist stabil, daAh = 1h2
tridiag(−ε−h, 2ε+h,−ε) eine M-Matrixist.
Nachteil: Es handelt sich mit ‖LhIhu − fh‖∞,∆ = O(h) nur um eine Diskretisierungerster Ordnung.
c) Künstliche Diffusion
Idee: Wir ersetzen den Diffusionskoeffizienten ε durch ε = ε+ δh.
Das führt zu
−(ε+
h
2
)un−1 + 2εun −
(ε− h
2
)un+1 = 0, u0 = 1, uN+1 = 0.
Durch eine ähnliche Rechnung wie oben ergibt sich
un =λN+1
+ − λ+
λN+1+ − 1
, λ+ =ε+ h
2
ε− h2
.
Dann gilt
λ+ > 0⇐⇒ ε+ δh >h
2⇐= δ ≥ 1
2,
womit Ah eine M-Matrix ist und das Verfahren stabil ist.
Nachteil: Stark “verschmierte” Grenzschicht und nur erste Konsistenzordnung.
d) Adaptive Gitter
Für eine nicht-äquidistante Diskretisierung von Lu = −u′′ + qu′ + ru definieren wirhn := xn+1 − xn und
∂huh(xn) :=1
hn + hn+1
(hnhn+1
un+1 +
(hn+1
hn− hnhn+1
)un −
hn+1
hnun−1
),
∂2huh(xn) :=
2
hn + hn+1
(1
hn+1
un+1 −(
1
hn+1
+1
hn
)un +
1
hnun−1
).
86
Das führt dann zu
Lhuh = −∂2
huh + q∂hu
h + ruh.
Fehlerschätzer
Löse Leh = f − Lhuh in (xn−1, xn) mit den Randbedingungen
eh(xn−1) = [(uh)′(xn−1)]
eh(xn) = [(uh)′(xn)].
Dabei ist [g(x)] = limδ−→0 g(x+ δ)− g(x− δ) der Sprung einer unstetigen Funktiong and der Stelle x.Definiere dann
η :=
√√√√ N∑n=1
η2n mit ηn :=
|xn − xn−1|2
(|eh(xn−1)|2 + |eh(xn)|2
).
als Maß für die Krümmung in (xn−1, xn).
AlgorithmusS0) Starte mit ∆1 = x0, . . . , xN+1, k = 1.
S1) Löse Lhuh = fh auf ∆k.
S2) Schätze den Fehler mit ηn in (xn−1, xn).
S3) Verfeinere ∆k → ∆k+1 durch Hinzufügen von xn−1+xn2
in allen Intervallen mitηn ≥ 0.5 max1≤j≤N ηj .
S4) Setze k := k + 1 und gehe zu S1).
87
Variationsmethoden
Betrachte die Sturm-Liouville-Randwertaufgabe
Lu(x) := −(p(x)u′(x)
)′+ q(x)u′(x) + r(x)u(x) = f(x), x ∈ (a, b)
u(a) = u(b) = 0, p(x) > 0
mit hinreichend glatten p, q, r, f .Dann gilt für jede Lösung u ∈ C2((a, b)) ∩ C([a, b]) mit Lu = f∫ b
a
Lu(x)ϕ(x)dx =
∫ b
a
f(x)ϕ(x)dx
für jede Testfunktion ϕ ∈ C([a, b]). Wir definieren den Raum15 der Testfunktionen durch
V := ϕ ∈ C([a, b]) : ϕ(a) = ϕ(b) = 0, ϕ stückweise differenzierbar.
BeispielDie linearen Splines s auf [a, b] mit s(a) = s(b) = 0 sind in V enthalten.
Zu ϕ ∈ V wähle eine Zerlegung a = x0 < x1 < . . . < xN+1 = b, sodass ϕ|[xn−1,xn] ∈C1((xn−1, xn)). Dann folgt mit partieller Integration
−∫ b
a
(pu′)′ϕdx = −N+1∑n=1
∫ xn
xn−1
(pu′)′ϕdx =N+1∑n=1
([− pu′ϕ
]xnxn−1
+
∫ xn
xn−1
pu′ϕ′ dx
)= −p(b)u′(b)ϕ(b)︸︷︷︸
=0
+p(a)u′(a)ϕ(a)︸︷︷︸=0
+
∫ b
a
pu′ϕ′ dx.
Damit folgt∫ b
a
Luϕdx =
∫ b
a
(pu′ϕ′ + qu′ϕ+ ruϕ
)dx.
BezeichnungenWir verwenden die folgenden Schreibweisen
a(v, w) =
∫ b
a
(pv′w′ + qv′w + rvw
)dx Bilinearform auf V ,
l(v) =
∫ b
a
fv dx Linearform auf V ,
‖v‖ := ‖v‖2 =
(∫ b
a
|v|2 dx) 1
2
L2-Norm.
Wir zeigen nun, dass die Abbildung v 7→ ‖v′‖ eine Norm in V ist.
15Man sieht leicht, dass V ein Vektorraum ist.
88
(5.12) Satza) Es gilt die Poincaré-Ungleichung ‖v‖ ≤ b−a
2‖v′‖ für alle v ∈ V .
b) l(·) ist stetig bezüglich ‖ · ‖ und bezüglich v 7→ ‖v′‖, denn es existiert ein C > 0 mit|l(v)| ≤ C ‖v′‖ für alle v ∈ V .
c) a(·, ·) ist stetig bezüglich v 7→ ‖v′‖, denn es existiert ein C > 0 mit |a(v, w)| ≤C‖v′‖‖w′‖ für alle v, w ∈ V .
d) Sei zusätzlich min p(x) ≥ ρ > 0 und
ρ+
(b− a
2
)2
minx∈[a,b]
(r(x)− 1
2q′(x)
)> 0.
Dann ist a(·, ·) elliptisch, d.h. es existiert ein c > 0, sodass a(v, v) ≥ c‖v′‖2 für allev ∈ V gilt.
Beweis. a) Für v ∈ V gelten v(a) = v(b) = 0 und
v(x) = v(a) +
∫ x
a
v′(y)dy =
∫ x
a
v′(y)dy = −∫ b
x
v′(y)dy.
Die Cauchy-Schwarz-Ungleichung liefert dann
|v(x)| =∣∣∣∣∫ x
a
v′(y) · 1dy∣∣∣∣ ≤ (∫ x
a
|v′(x)|2dy) 1
2(∫ x
a
1dy
) 12
(analog in (x, b)). Damit gilt |v(x)|2 ≤ ‖v′‖2 min(x− a), (b− x). Daraus folgt
‖v‖2 =
∫ b
a
|v(x)|2 dx ≤ ‖v′‖2
∫ b
a
min(x− a), (b− x) dx
= ‖v′‖2 · 2 ·∫ b+a
2
a
(x− a) dx = ‖v′‖2
(b− a
2
)2
.
b) Es gilt mit der Cauchy-Schwarz-Ungleichung
|l(v)| =∣∣∣∣∫ b
a
fv dx
∣∣∣∣ ≤ ∫ b
a
|fv| dx ≤ ‖f‖ · ‖v‖,
also ist l ∈ C(L2,R). Mit a) folgt dann |l(v)| ≤ ‖f‖ b−a2‖v′‖ = C‖v′‖.
c) Wieder gilt mit Cauchy-Schwarz
|a(v, w)| ≤ ‖p‖∞∫ b
a
|u′||v′| dx+ ‖q‖∞∫ b
a
|u′||v| dx+ ‖r‖∞∫ b
a
|u||v| dx
≤ ‖p‖∞‖u′‖‖v′|‖+ ‖q‖∞‖u′‖‖v‖+ ‖r‖∞‖u‖‖v‖,
woraus sich mit a) die Behauptung |a(v, w)| ≤ C‖v′‖‖w′‖ ergibt.
89
d) Es gilt ρ0 ∈ (0, ρ) mit ρ0 +(b−a
2
)2min
(r − 1
2q′)> 0. Es gilt wegen v(a) = v(b) = 0
∫ b
a
q′v2 dx =[qv2]ba−∫ b
a
q(v2)′ dx = −2
∫ b
a
qv′v dx.
Damit folgt
a(v, v) =
∫ b
a
(p|v′|2 + qv′v + r|v|2
)dx
=
∫ b
a
[(p− ρ0)|v′|2 + ρ0|v′|2 −
1
2q′|v|2 + r|v|2
]dx
≥ (ρ− ρ0)︸ ︷︷ ︸>0
‖v′‖2 + ρ0
(‖v′‖2 −
(2
b− a
)2
‖v‖2
)︸ ︷︷ ︸
>0 nach a)
+
(ρ0
(2
b− a
)2
+ minx∈[a,b]
(r(x)− 1
2q′(x)
))︸ ︷︷ ︸
>0 nach Vor.
‖v‖2
≥ c‖v′‖2
mit c = ρ− ρ0.
FolgerungAus a) folgt, dass v 7→ ‖v′‖ eine Norm auf V definiert. Die Norm ist durch das Skalar-produkt (v, w)V =
∫ bav′w′ dx induziert. Also ist V ein Prähilbertraum16, der Teilraum
von L2((a, b)) ist. Der Abschluss bezüglich der Norm v 7→ ‖v′‖ ist der HilbertraumV = H1
0 ((a, b)), ein Sobolevraum. Alle Aussagen aus (5.12) gelten auch für V .
(5.13) SatzSei a(·, ·) elliptisch.Dann hat die Sturm-Liouville-Randwertaufgabe eine eindeutige Lösung.
Beweis. Aus der Fredholm’schen Alternative folgt:
Wenn die Aufgabe Lu = 0 mit u(a) = u(b) = 0 nur die triviale Lösung u ≡ 0 besitzt,dann ist Lu = f mit u(a) = u(b) = 0 für jede rechte Seite f eindeutig lösbar.
Sei also Lu = 0. Dann gilt
0 =
∫ b
a
(Luu
)dx = a(u, u) ≥ c‖u′‖2.
Damit folgt ‖u′‖ = 0 und somit, da v 7→ ‖v′‖ eine Norm ist, u = 0.
16 Ein Prähilbertraum ist ein normierter Vektorraum, dessen Norm durch ein Skalarprodukt induziertwird. Ein vollständiger Prähilbertraum heißt Hilbertraum.
90
Galerkin-Verfahren
Wähle einen endlichdimensionalen Teilraum Vh ⊂ V mit Basis ϕh1 , . . . , ϕhN und definiere
Ah :=(a(ϕhn, ϕ
hk))n,k=1,...,N
∈ RN,N , fh :=(l(ϕhn)
)n=1,...,N
∈ RN .
(5.14) SatzSei a(·, ·) elliptisch. Dann ist Ah regulär und es existiert eine eindeutige Lösung uh ∈ Vhder Variationsgleichung a(uh, vh) = l(vh) für alle vh ∈ Vh.Für diese Lösung gilt
uh =N∑n=1
unϕhn mit u = A−1
h fh ∈ RN .
Beweis. Für
vh =N∑n=1
vnϕhn ∈ Vh
gilt
c‖v′h‖2 ≤ a(vh, vh) = a
(N∑n=1
vnϕhn,
N∑k=1
vkϕhk
)=
N∑n,k=1
vnvka(ϕhn, ϕhk)
= vTAhv.
Und damit folgt vTAhv > 0 für v 6= 0N . Also ist Ah positiv definit und folglich regulär.Somit ist u := A−1
h fh wohldefiniert. Da u die Gleichung Ahu = fh löst, löst es auch dieVariationsgleichung, denn mit
N∑n=1
a(ϕhk, ϕkn)un =
(Ahu
)k
=(fh)k
= l(ϕhk) für k = 1, . . . , N
folgt
a(uh, vh) =N∑
n,k=1
unvka(ϕhn, ϕhk) =
N∑k=1
vk
N∑n=1
a(ϕhn, ϕhk)un =
N∑k=1
vkl(ϕhk)
= l(vh),
also die Variationsgleichung.
(5.15) Lemma (Galerkin-Orthogonalität)Sei u ∈ C2((a, b)) ∩ C([a, b]) Lösung der Sturm-Liouville-Randwertaufgabe Lu = f unduh ∈ Vh eine Lösung von (5.14). Dann gilt für den Fehler eh := u− uh ∈ V
a(eh, vh) = 0 ∀vh ∈ Vh.
91
Beweis. Aus Lu = f folgt a(u, vh) = l(vh) und nach (5.14) gilt a(uh, vh) = l(vh) (jeweilsfür alle vh ∈ Vh ⊂ V ).Durch Subtraktion der Gleichungen folgt dann a(u− uh, vh) = 0 für alle vh ∈ Vh.
(5.16) Satz (Cea’s Lemma)Sei a(·, ·) beschränkt und elliptisch, d.h.
|a(u, v)| ≤ C‖u′‖‖v′‖, a(v, v) ≥ c‖v′‖2 ∀u, v ∈ V .
Dann gilt für den Galerkin-Fehler eh = u− uh
‖e′h‖ ≤C
cinfvh∈Vh
‖u′ − v′h‖.
Beweis. Es gilt mit (5.15)
c‖e′h‖2 ≤ a(eh, eh) = a(eh, u) = a(eh, u− vh) ≤ C‖e′h‖‖u′ − v′h‖
und damit folgt
c‖e′h‖ ≤ C infvh∈Vh
‖u′ − v′h‖,
da vh ∈ Vh beliebig war.
(5.17) SatzSei a(·, ·) symmetrisch (d.h. q ≡ 0) und elliptisch. Sei F (v) := 1
2a(v, v)− l(v).
Dann gilt für u ∈ V
F (u) ≤ F (v) ∀v ∈ V ⇐⇒ a(u, v) = l(v) ∀v ∈ V .
Beweis. Es gilt
F (v)− F (u) =1
2
(a(v, v)− a(u, u)
)− l(v) + l(u)
=1
2a(u− v, u− v) + a(u, v − u)− l(v − u).
“⇐”: Damit folgt F (v)− F (u) = 12a(u− v, u− v) ≥ c‖u− v‖2 ≥ 0.
“⇒”: Annahme: Es existiert ein ϕ ∈ V mit a(u, ϕ) 6= l(ϕ).
Dann ist ϕ 6= 0 und für v = u+ tϕ, t ∈ R gilt
0 ≤ F (v)− F (u) =1
2t2a(ϕ, ϕ) + t
(a(u, ϕ)− l(ϕ)
).
Wähle nun t = 1a(ϕ,ϕ)
(l(ϕ)− a(u, ϕ)
)6= 0. Dann gilt
0 ≤ −1
2t2a(ϕ, ϕ) < 0,
was ein Widerspruch ist.
92
Bemerkung1) Verfahren von Ritz
Bestimme uh ∈ Vh mit F (uh) ≤ F (vh) ∀vh ∈ Vh.
2) Verfahren von Galerkin
Bestimme uh ∈ Vh mit a(uh, vh) = l(vh) ∀vh ∈ Vh.
Lineare Finite Elemente
Zu einer Zerlegung ∆ = a = x0 < x1 < · · · < xN+1 = b mit xn = a + nh (n =0, . . . , N + 1), h = b−a
N+1definiere
φn(xk) = δn,k mit φn|[xn−1,xn] affin linear (n, k = 1, . . . , N + 1).
Setze außerdem Vh := spanφn : n = 1, . . . , N (Knotenbasis) und A[n, k] := a(φn, φk)für n, k = 1, . . . , N . Dann gilt
A[n, k] = a(φn, φk) = 0 für |n− k| > 1
A[n, n] =
∫ xn
xn−1
(p(φ′n)2 + qφ′nφn + rφ2
n
)dx
≈ 2
h
(pn− 1
2+ pn+ 1
2
)+
1
2
(qn− 1
2− qn+ 1
2
)+h
3
(rn− 1
2+ rn+ 1
2
)A[n, n− 1] =
∫ xn
xn−1
(pφ′nφ
′n−1 + qφ′nφn−1 + rφnφn−1
)dx
≈ −1
hpn− 1
2+
1
2qn− 1
2− h
6rn− 1
2,
wobei jeweils durch die Mittelpunktsregel approximiert wird.
(5.18) SatzSei Vh ⊂ V der Raum der finiten Elemente mit der Gitterweite h und Ih : V → Vh,u 7→ Ihu mit Ihu(xn) = u(xn), d.h. Ihu =
∑Nn=1 u(xn)φn, die lineare Interpolation nach
Vh.Dann gelten für u ∈ C2([a, b])
a) ‖u− Ihu‖ ≤ h2‖u′′‖,
b) ‖(u− Ihu)′‖ ≤ h‖u′′‖,
c) ‖u− Ihu‖∞ ≤ 12h2‖u′′‖∞.
Beweis. Wir zeigen nur b).Sei dazu die Fehlerfunktion w := u − Ihu. Dann folgt w(xn) = 0 und somit existiert fürn = 1, . . . , N + 1 nach dem Satz von Rolle ein ξn ∈ (xn−1, xn) mit w′(ξn) = 0.Damit ergibt sich für x ∈ (xn−1, xn)
|w′(x)| =
∣∣∣∣∫ x
ξn
w′′(y)dy
∣∣∣∣ CSU≤∣∣∣∣∫ x
ξn
(w′′(y)
)2dy
∣∣∣∣ 12 ∣∣∣∣∫ x
ξn
1dy
∣∣∣∣ 12≤
(∫ xn
xn−1
(w′′(y)
)2dy
) 12 √|x− ξn|
93
und es folgt∫ xn
xn−1
|w′(x)|2 dx ≤∫ xn
xn−1
(w′′(y)
)2dy
∫ xn
xn−1
|x− ξn|︸ ︷︷ ︸≤h
dx ≤ h2
∫ xn
xn−1
(w′′(y)
)2dy.
Nach Summation über n = 1, . . . , N + 1 folgt schließlich mit
‖(u− Ihu)′‖2 =N+1∑n=1
∫ xn
xn−1
(w′(y)
)2dy ≤ h2‖w′′‖2
= h2‖u′′ − (Ihu)′′‖2 = h2‖u′′‖2
wegen (Ihu)′′ = 0 in (xn−1, xn) die Behauptung.
(5.19) SatzSei a(·, ·) elliptisch und es existiere ein ρ > 0 mit min p(x) ≥ ρ > 0.Dann gilt für die Lösung u ∈ C2([a, b]) der Randwertaufgabe Lu = f , u(a) = u(b) = 0die Abschätzung ‖u′′‖ ≤ C‖f‖.
Beweis. Satz (5.12) liefert ‖u‖ ≤ Cp‖u′‖ und da a(·, ·) elliptisch ist, gilt
‖u′‖2 ≤ 1
ca(u, u) =
1
cl(u) ≤ 1
c‖f‖‖u‖ ≤ Cp
c‖f‖‖u′‖,
also ‖u′‖ ≤ Cpc‖f‖.
Aus Lu = f folgt−(pu′)′+ qu′+ ru = f . Löst man diese Gleichung nach Anwenden derProduktregel nach u′′ auf, ergibt sich mit min p(x) ≥ ρ > 0
‖u′′‖ =
∥∥∥∥1
p
(f − ru− qu′ + p′u′
)∥∥∥∥≤ 1
ρ
(‖f‖+ ‖r‖∞‖u‖+ ‖q‖∞‖u′‖+ ‖p′‖∞‖u′‖
)≤ C‖f‖
mit C = 1ρ
(1 + Cp‖r‖∞ + Cp
c
(‖q‖∞ + ‖p′‖∞
)).
(5.20) SatzUnter den Voraussetzungen von (5.16) gelten für die Galerkin-Lösung uh
a) ‖u′ − u′h‖ ≤ Ch‖f‖,
b) ‖u− uh‖ ≤ Ch2‖f‖.
Beweis. a) Da Ihu ∈ Vh gilt, folgt
‖u′ − u′h‖ = ‖e′h‖(5.16)≤ C
cinfvh∈Vh
‖u′ − v′h‖ ≤C
c‖(u′ − Ihu)′‖
(5.18)≤ C
ch‖u′′‖
(5.19)≤ Ch‖f‖.
94
b) Wir betrachten die adjungierte Aufgabe (Dualitätstrick) zu g ∈ C((a, b)).
Wähle wh ∈ Vh und w ∈ V so, dass
a(vh, wh) =
∫ b
a
gvh dx ∀vh ∈ Vh und a(v, w) =
∫ b
a
gv dx ∀v ∈ V
gelten. Da g stetig ist, gilt17 w ∈ C2((a, b)). Außerdem gilt
‖w′ − w′h‖(5.18)≤ h‖w′′‖
(5.19)≤ Ch‖g‖.
Mit g := u− uh folgt dann
‖u− uh‖2 =
∫ b
a
g(u− uh) dx
u−uh∈V= a(u− uh, w)(5.15)= a(u− uh, w − Ihw)
(5.12)≤ C‖u′ − u′h‖‖w′ − (Ihw)′‖
(5.18)≤a)
C ′h‖f‖(Ch‖w′′‖
)(5.19)≤ Ch2‖f‖‖g‖ = Ch2‖f‖‖u− uh‖.
Nach Teilen der Ungleichung durch ‖u− uh‖ folgt die Behauptung.
17Vorsicht: So kann man nur bei gewöhnlichen Differenzialgleichungen schließen!
95
Ein singulär gestörtes Modellproblem
Wir betrachten
Lu = −εu′′ + u′ + u
Lu = f, u(a) = u(b) = 0.
Wir kennen bereits Ansätze, dieses Problem numerisch zu lösen:
A) Zentrale Differenzen: Ah = tridiag(− εh2
+ 12h, 2εh2
+ 1, − εh2− 1
2h
)Konsistenzfehler O(h2) in ‖ · ‖∞, aber nicht stabil für ε < h
2.
B) Upwind: Ah = tridiag(− εh2, 2εh2
+ 12h
+ 1, − εh2− 1
2h
)Konsistenzfehler nur O(h) in ‖ · ‖∞, aber dafür stabil.
C) Künstliche Diffusion: Ah = tridiag(− εhh2
+ 12h, 2εh
h2+ 1, − εh
h2− 1
2h
)mit εh = ε+ δh.
Konsistenzfehler nur O(h) in ‖ · ‖∞, aber dafür stabil für geeignetes δ > 0.
D) Lineare Finite Elemente:
a(u, v) =∫ ba
(εu′v′+u′v+uv
)dx,Ah = tridiag
(− εh
+ 12
+ h6, 2εh2
+ 2h3, − ε
h− 1
2− h
6
)Konsistenzfehler O(h2) in ‖ · ‖, stabil nur für ausreichend kleines h.
E) Streamline Diffusion (SD):
Wähle δ > 0, teste (zum Teil) mit vh + δv′h, vh ∈ Vh
aδ(uh, vh) =
∫ b
a
(εu′hv
′h + (u′h + uh)(vh + δv′h)
)dx,
lδ(vh) =
∫ b
a
f(vh + δv′h) dx.
(5.21) SatzDie Bilinearform aδ(·, ·) ist elliptisch in V bezüglich ‖v‖δ :=
√ε‖v′‖2 + δ‖v′‖+ ‖v‖2
(es gilt sogar aδ(v, v) = ‖v‖2δ).
Beweis. Es gilt∫ b
a
v′v dx =
∫ b
a
1
2
d
dx(v2) dx =
1
2
(v2(b)− v2(a)
)= 0 für v ∈ V .
Dann folgt
aδ(v, v) = ε‖v′‖2 + δ‖v′‖2 + ‖v‖2 + (1 + δ)
∫ b
a
v′v dx = ‖v‖2δ ,
was zu zeigen war.
96
Daraus folgt mit (5.14), dass Ah =(aδ(φn, φk)
)n,k=1,...,N
∈ RN,N positiv definit ist, unddamit existiert eine eindeutige Lösung uh ∈ Vh von aδ(uh, vh) = lδ(vh) für alle vh ∈ Vh.
(5.22) SatzFür ε ≤ h und δ = h ≤ 1 gilt
‖u− uh‖ ≤ Ch32‖u′′‖,
wobei C > 0 unabhängig von ε und h ist.
Beweis. Für eh = u− uh gilt
aδ(eh, vh) =
∫ b
a
[ε(u′ − u′h)v′h + (u′ − u′h + u− uh)(vh + δv′h)] dx
=
∫ b
a
[εu′v′h + (u′ + u)(vh + δv′h)] dx− aδ(uh, vh)
=
∫ b
a
fvh dx+ δ
∫ b
a
(u′ + u)v′h dx−∫ b
a
f(vh + δv′h) dx
= δ
∫ b
a
(u′ + u− f︸ ︷︷ ︸=εu′′
)v′h dx
Damit folgt
aδ(eh, eh)(5.21)= ‖eh‖2
δ
= aδ(eh, u− vh) + aδ(eh, vh − uh)
= aδ(u− uh, u− vh)︸ ︷︷ ︸=:E
+δε
∫ b
a
u′′(vh − uh)′ dx
siehe≤
unten
1
4‖eh‖2
δ + Ch3‖u′′‖2 + 2h3‖u′′‖2 +1
4‖eh‖δ
+C2
4h3‖u′′‖.
Ungleichungen, die wir benötigen:
E = aδ(eh, u− vh)
≤∣∣∣∣ε∫ b
a
e′h(u′ − v′h) dx
∣∣∣∣+
∣∣∣∣∫ b
a
(e′h + eh)(u− vh + δ(u′ − v′h)
)dx
∣∣∣∣≤ ε‖e′h‖‖u′ − v′h‖+
(‖e′h‖+ ‖eh‖
)‖u− vh‖
+√δ(‖e′h‖+ ‖eh‖
)√δ(‖u′ − v′h‖
).
97
Mit (5.18) folgt, dass für vh = Ihu die Ungleichungen‖u− Ihu‖ ≤ Ch2‖u′′‖ und ‖(u− Ihu)′‖ ≤ Ch‖u′′‖ gelten. Daraus folgt
|aδ(eh, u− Ihu)| ≤ ε‖e′h‖(Ch‖u′′‖) + (√δ‖e′h‖+ ‖eh‖)
(Ch2
√δ‖u′′‖
)+(√δ‖e′h‖+ ‖eh‖)Ch
√δ‖u′′‖
≤ ε
4‖e′h‖2 + 4εC2h2‖u′′‖2 +
1
8
(δ‖e′h‖2 + ‖eh‖2
)+4C2h3‖u′′‖2 +
1
8
(δ‖e′h‖2 + ‖eh‖2
)+ 4Ch3‖u′′‖
≤ 1
4‖eh‖δ + Ch3‖u′′‖2
und schließlich
εδ
∫ b
a
u′′(uh − Ihu)′ dx ≤ ε√δ‖u′′‖
√δ‖uh − Ihu‖
≤ ε√δ‖u′′‖
√δ(‖(uh − u)′‖+ ‖(u− Ihu)′‖
)≤ ε
√δ‖u′′‖
(√δ‖e′h‖+
√δCh‖u′′‖
)≤ 2 ε2δ︸︷︷︸
≤h3‖u′′‖2 +
1
4
(δ‖e′h‖2 + Ch3‖u′′‖
)≤ 1
4‖eh‖δ + Ch3‖u′′‖2 .
98
