Abschnitt 1.7: Schrittweitensteuerung 27

zu oben analoge Schrittweitensteuerung durch Kombinationvon drei- und vierstufigen Runge-Kutta-Methoden ist nicht moglich, weil die betreffenden Gleichungssysteme keine Losungen zu-lassen, so daßk1, k2 undk3 in beiden Verfahren identisch sind.

Die erreichbare Fehlerordnungp einer expliziten m-stufigen Runge-Kutta-Methode ist furp ≤ 9gemaß der folgenden Tabelle gegeben.

Tab. 1.4: Maximale Fehlerordnung von expliziten Runge-Kutta-Verfahren

m = 1 2 3 4 5 6 7 8 9p = 1 2 3 4 4 5 6 6 7

Von Fehlberg stammt ein eingebttetes Runge-Kutta-Verfahren 3. und 4. Ordnung, in welcher eineFunktionauswertung doppelt verwendet wird.

0

14

14

49

481

3281

67

5798 −432

3431053686

1 16 0 27

5249156

y(3)k+1

16 0 27

5249156 0

y(4)k+1

43288 0 243

4163431872

112

dk+1 ≈ − 5288 0 27

416 − 2451872

112

Ebenso von Fehlberg stammt eine geschickte Kombination vonRunge-Kutta-Verfahren 4. und 5.Ordnung, in welcher die Runge-Kutta-Methode 4. Ordnung funf der ohnehin sechs der erforderli-chen Auswertungen verwendet.

Angewandte Numerik II, 12. November 2013

28 Kapitel 1: Gewohnliche Differentialgleichungen

0

14

14

38

332

932

1213

19322197 −7200

219772962197

1 83414104 −32832

4104294404104 − 845

4104

12 − 6080

205204104020520 −28352

20520929520520 − 5643

20520

yk+1237520520

1126420520

1098520520 − 4104

20520 0

dk+1 ≈ 1045376200 − 11264

376200 − 10985376200

7524376200

13680376200

Angewandte Numerik II, 12. November 2013

Abschnitt 1.8: Implizite Runge-Kutta-Verfahren 29

1.8 IMPLIZITE RUNGE-KUTTA-VERFAHREN

Zur numerischen Losung von steifen Differentialgleichungen (siehe spateres Kapitel) sind spe-zielle Methoden erforderlich. Zu diesen gehoren die impliziten Runge-Kutta-Verfahren, welchedadurch charakterisiert sind, daß die Steigungenk1, k2, . . . durch ein implizites Gleichungssys-tem definiert werden. Da die Herleitung von mehrstufigen impliziten Runge-Kutta-Methoden sehraufwendig ist, wollen wir solche Verfahren hier nur definieren.Das Butcher-Diagramm solcher impliziten Runge-Kutta-Verfahrenm-ter Stufe hat die Form

a1 b11 b12 · · · b1ma2 b21 b22 · · · b2m...

...am bm1 bm2 · · · bmm

c1 c2 · · · cm

wobei mindestens einbij 6= 0, (i ≤ j) gilt. Alternativ schreibt man auch

ki := f

(tk + ar, yk + h

(bi1k1 + . . . + bimkm

))(i = 1, . . . ,m) (1.46)

yk+1 := yk + h

(c1k1 + · · ·+ cmkm

).

Bei der Wahl dera ∈ Rm, b ∈ R

m×m undc ∈ Rm gibt es verschiedene Ansatze:

1. Gauß-Form: Die a, b, c seien beliebig wahlbar. Zielsetzung ist die Maximierung der Kon-sistenzordnung. Man kann zeigen, dass somit dieai’s Nullstellen der auf das Intervall[0, 1]transformierten Legendre-PolynomePm(2t− 1) := 1

m!dm

dtm (tm(t− 1)m) sind.

2. Radau I - Form: Es gilta1 = 0 und diea2, . . . am sind Nullstellen vondm−1

dtm−1 (tm(t−1)m−1)

3. Radau II - Form : Es giltam = 1 unda1 . . . am−1 sind Nullstellen vondm−1

dtm−1 (tm−1(t−1)m)

4. Lobatto III - Form : Es gilt a1 = 0, am = 1 und a2 . . . an−1 sind Nullstellen vondm−2

dtm−2 (tm−1(t− 1)m−1)

Einige implizite Runge-Kutta-Verfahrenm-ter Stufe undp-ter Ordnung in tabellarischer Form:

Gauß-Form

m = 1, p = 2

12

12

1

m = 2, p = 4

3−√3

614

3−2√3

12

3+√3

63+2

√3

1214

12

12

Angewandte Numerik II, 12. November 2013

30 Kapitel 1: Gewohnliche Differentialgleichungen

Radau I - Form

m = 2, p = 3

0 14 −1

4

23

14 − 5

12

14

34

m = 3, p = 5

0 19

−1−√6

18−1+

√6

18

6−√6

1019

88+7√6

36088−43

√6

360

6+√6

1019

88+43√6

36088−7

√6

360

19

518

518

Radau II - Form

m = 1, p = 1 (implizites Euler-Verfahren)

1 1

1

m = 2, p = 3

13

512 − 1

12

1 34

14

34

14

m = 3, p = 5

4−√6

1088−7

√6

360296−169

√6

1800−2+3

√6

225

4−√6

10296+169

√6

36088+7

√6

1800−2−3

√6

225

1 16−√6

3616+

√6

3619

19

518

518

Angewandte Numerik II, 12. November 2013

Abschnitt 1.9: Mehrschrittverfahren 31

Lobatto III A - Form (b1j = 0)

m = 3, p = 4

0 0 0 0

12

524

13 − 1

24

1 16

23

16

16

23

16

Lobatto III B - Form (bin = 0)

m = 3, p = 4

0 16 −1

6 0

12

16

13 0

1 16

56 0

16

23

16

Allgemein gilt, daß einm-stufiges implizites Runge-Kutta-Verfahren von der Gauß-Form durchgeeignete Wahl derm(m+1) freien Parameter die maximal erreichbare Fehlerordnung2m besitzt.Ahnliches gilt auch fur die Radau-Formen(2m− 1) und Lobatto-Formen(2m− 2).Die Fixpunktiteration zum Losen von (1.46) ist konvergentfur alle Schrittweitenh, die der Bedin-gung

hBL < 1 mit B := maxi

∑

j

|bij|

genugen undL die Lipschitz-Konstante der Funktionf(x, y) darstellt.

Bemerkung 38 Die impliziten Runge-Kutta-Verfahren besitzen eine Stabilitatseigenschaft, diebei der Integration von steifen Differentialgleichungssystemen entscheidend ist. Fur allgemei-ne Differentialgleichungssysteme sind die impliziten Runge-Kutta-Methoden trotz ihrer hohenFehlerordnung wenig attraktiv, weil in jedem Integrationsschritt ein im allgemeinen nichtlinearesGleichungssystem fur diem Unbekanntenki (1 ≤ i ≤ m) zu losen ist.

1.9 MEHRSCHRITTVERFAHREN

Ein Nachteil der Einschrittverfahren ist die hohe Anzahl der Funktionsauswertungen, die fur einehohe Konsistenzordnung und somit fur eine hohe Konvergenzordnung notig sind. Dieser Nach-teil tritt bei den folgenden Mehrschrittverfahren nicht auf. Es bleibt im allgemeinen jedoch nurein deutlicher Vorteil, solange die Schrittweite fest gew¨ahlt wird. Fur Einschrittverfahren habenwir schon in Kapitel 1.6 gesehen, daß adaptive Schrittweitensteuerung dort recht einfach durch-zufuhren ist. Dies laßt sich fur Mehrschrittverfahren nicht so einfach realisieren.Es seitj = t0 + jh (j = 0, 1, 2, . . .).

Angewandte Numerik II, 12. November 2013

32 Kapitel 1: Gewohnliche Differentialgleichungen

Ein k-Schrittverfahren zur Losung des AWPy′(t) = f(t, y(t)), y(t0) = y0 ist ein Verfahren zurBerechnung von Naherungswertenyj+k zuy(tj+k) ausyj, . . . , yj+k−1 durch Losen der Gleichung

k∑

ℓ=0

αℓyj+ℓ = hφ(tj , yj, . . . , yj+k, h, f) (1.47)

fur j = 0, 1, 2, . . . mit geeigneten Startwerteny0, . . . , yk−1. Dabei ist 1h∑k

ℓ=0 αℓyj+ℓ als eineNaherung an die Ableitungy′ (bisher1h(yj+1− yj)) undφ(tj , yj, . . . , yj+k, h, f) als Naherung anf(t, y(t)) aufzufassen.Ein linearesk-Schrittverfahren ist von der Form

k∑

ℓ=0

αℓyj+ℓ = h

k∑

ℓ=0

βℓf(tj+ℓ, yj+ℓ) (j = 0, 1, 2, . . .) (1.48)

mit geeigneten Startwerteny0, . . . , yk−1. Gilt βk = 0 so spricht man von einem expliziten Verfah-ren, ansonsten von einem impliziten.Die im allgemeinen nichtlineare Gleichung inyj+k im impliziten linearenk-Schrittverfahren kannaus (1.48) iterativ berechnet werden. Es seif Lipschitz-stetig iny mit einer Lipschitz-KonstantenL. Dann gilt fur die Iteration nach dem Banachschen Fixpunktsatz

y(r+1)j+k = h

βkαkf(tj+k, y

(r)j+k)−

1

αk(h

k−1∑

ℓ=0

βℓf(tj+ℓ, yj+ℓ)−k−1∑

ℓ=0

αℓyj+ℓ)

=: ψ(y(r)j+k),

daß diese konvergent ist, falls| βk

αk|hL < 1 gilt.

Untersuchen wir nun zuerst, ob die Diskretisierung der Differentialgleichung lokal vernunftig ist.

Definition 39 Der lokale Diskretisierungsfehler des Mehrschrittverfahrens (1.47)ist

dj+k(tj, h, f) =

k∑

ℓ=0

αℓy(tj+ℓ)− hφ(tj , y(tj), . . . , y(tj+k−1), yj+k, h, f).

Das Mehrschrittverfahren heißt mit einer Differentialgleichungy′ = f(t, y) konsistent, falls

limh→0

dj+k(tj , h, f)

h= 0

gilt. Es heißt konsistent von der Ordnungp, falls

dj+k(tj , h, f) = O(hp+1)

gilt.

Beispiel 40 (eines Mehrschrittverfahrens)Man betrachte die Taylor-Entwicklungen

y(t+ h) = y(t) + hy′(t) +h2

2y′′(t) +O(h3)

y(t− h) = y(t)− hy′(t) +h2

2y′′(t) +O(h3)

Angewandte Numerik II, 12. November 2013

Abschnitt 1.9: Mehrschrittverfahren 33

Subtraktion beider Gleichungen liefert

y(t+ h)− y(t− h) = 2hy′(t) +O(h3) = 2hf(t, y(t)) +O(h3).

Dies motiviert das lineare 2-Schrittverfahren

yk+1 = 2hf(tk, yk) + yk−1, k = 1, 2, 3, . . . ,

welches als Quadratur der Mittelpunktsregel entspricht. Die Konsistenzordnung ist 2, was sich ausder Herleitung sofort ergibt.

Im Gegensatz zu Einschrittverfahren impliziert Konsistenz nicht immer Konvergenz, welches wirspater untersuchen werden.Betrachten wir nun zuerst die Entwicklung der wichtigsten Mehrschrittverfahren, die man ubernumerische Integration herleiten kann, ahnlich wie Runge-Kutta-Verfahren.Es gilt

y(tj+k)− y(tj+r−ℓ) =

∫ tj+k

tj+r−ℓ

f(t, y(t)) dt. (1.49)

Dabei seiy(tj+k) der Wert, welcher approximiert werden soll. Es ist nun eine naheliegende Idee,den Integrandenf durch ein InterpolationspolynomPr,j(s) = Pf (s|tj , . . . , tj+r) vom Grader zuersetzen, welches an den Stellentj, . . . , tj+r interpoliert.Dabei betrachtet man das Integral uber(tj+r−ℓ, tj+k), wahrend nur auf[tj , tj+r] interpoliert wird.Dieses Vorgehen ist graphisch in Abbildung 1.10 dargestellt.

Interpolationsintervall

Integrationsintervall

tj tj+r−ℓ tj+r tj+k

f

Pr

Abb. 1.10: Exemplarische Darstellung von Interpolations-und Integrationsintervall

Die Lagrangesche Darstellungsform fur das InterpolationspolynomPr,j(s) sieht folgendermaßenaus:

Pr,j(s) =r∑

i=0

f(tj+i, yj+i)r∏

p=0

p 6=i

s− tj+p

tj+i − tj+p

=

r∑

i=0

f(tj+i, yj+i)

r∏

p=0

p 6=i

s− tj+p

(i− p)h

Angewandte Numerik II, 12. November 2013

34 Kapitel 1: Gewohnliche Differentialgleichungen

Also erhalten wir, fallsPr,j(s) in (1.49) furf eingesetzt wird:

yj+k − yj+r−ℓ ≈ hr∑

i=0

f(tj+i, yj+i)β(r,ℓ)i , (1.50)

wobei

hβ(r,ℓ)i =

∫ tj+k

tj+r−ℓ

r∏

p=0

p 6=i

s− tj+p

(i− p)ds

= h

∫ k−r

−ℓ

r∏

p=0

p 6=i

r − p+ s

i− pds

ist. Dabei erhalt man den letzten Schritt durch Substitution s = tj + (r + s)h.Die Rechenvorschrift lautet somit

uj+k = uj+r−ℓ + hr∑

i=0

β(r,ℓ)i f(tj+i, yj+i).

Ubliche Wahlen furr undℓ:

r ℓ Name Art

k − 1 0 Adams-Bashforth Extrapolation, explizites Verfahrenk − 1 1 Nystrom Extrapolation, explizites Verfahrenk 1 Adams-Moulton Interpolation, implizites Verfahrenk 2 Milne-Simpson Interpolation, implizites Verfahren

Angewandte Numerik II, 12. November 2013

Literaturverzeichnis

[A] R.A. A DAMS, “Sobolev Spaces”, Pure Appl. Math. 65, Academic Press, NewYork, 1975.

[G] G. H. GOLUB, C. F.VAN LOAN, Matrix Computations, 3. ed., Hopkins Univ. Press, 1996.

[H] W. H ACKBUSCH, Iterative Losung großer schwachbesetzter Gleichungssysteme,2. Auflage, Teubner-Verlag, Stuttgart, 1993.

[HH] G. HAMMERLIN , K.-H. HOFFMANN, Numerische Mathematik, 4. Auflage, Springer-Verlag, Berlin u.a., 1994.

[P] R. PLATO, Numerische Mathematik kompakt, Vieweg-Verlag.

[Sc] H. R. SCHWARZ, Numerische Mathematik, 4. Auflage, Teubner-Verlag, Stuttgart, 1997.

[St] J. STOR, R. BULIRSCH, Numerische Mathematik 1 und 2, Springer-Verlag, Berlin u.a.,1994.

[SW] K. STREHMEL, R. WEINER, Numerik gewohnlicher Differentialgleichungen, Teubner-Verlag, Stuttgart, 1995.

[TS] W. TORNIG, P. SPELLUCCI, Numerische Mathematik fur Ingenieure und Physiker, Band1 & 2, Springer-Verlag, Berlin u.a.

[W] W. WALTER, Gewohnliche Differentialgleichungen, 6. Auflage, Springer-Verlag, Berlinu.a., 1996.