9 Numerische Verfahren fur¨ Anfangswertauf- gabenernst/Lehre/Numerik_II/Folien/...9.3 Runge-Kutta-Verfahren 9.4 Lineare Mehrschrittverfahren 9.5 Konvergenz von Einschrittverfahren

Numerik II 63

9 Numerische Verfahren fur Anfangswertauf-gaben

Inhalt

9.1 Einige einfache Verfahren

9.2 Einschrittverfahren – Definition und Eigenschaften

9.3 Runge-Kutta-Verfahren

9.4 Lineare Mehrschrittverfahren

9.5 Konvergenz von Einschrittverfahren

9.6 Nullstabilitat linearer Mehrschrittverfahren

9.7 Schrittweitensteuerung

9 Numerische Verfahren fur Anfangswertaufgaben TU Bergakademie Freiberg, SS 2010

Numerik II 64

9.1 Einige einfache Verfahren

Wir betrachten die AWA

y ′ = f (t,y), y(t0) = y0. (AWA)

Unter den Voraussetzungen von Satz 8.1 besitzt es eine eindeutige Losung,sagen wir uber dem Intervall I. Wir wollen diese Losung y(t) fur t ∈[t0, tend] ⊆ I durch das Euler-Verfahrena (auch Euler-Cauchy-Verfahrenb

oder Polygonzug-Verfahren), den Prototyp eines numerischen Verfahrenszur Losung von AWAen, approximieren.

Wie alle numerischen Methoden, die hier besprochen werden, basiert dasEuler-Verfahren auf der Idee der Diskretisierung: Statt (AWA) uber [t0, tend]

zu losen, geben wir uns damit zufrieden, Naherungswerte fur die Losungauf einer diskreten Teilmenge {tn : n = 0, 1, . . . , N} zu bestimmen.

aLEONHARD EULER (1707–1783)bAUGUSTIN LOUIS CAUCHY (1789–1857)

9.1 Einige einfache Verfahren TU Bergakademie Freiberg, SS 2010

Numerik II 65

Wahle N ∈ N, h = (tend−t0)/N und definiere tn := t0 +nh, n = 0, 1, . . . , N ,d.h. t0 < t1 · · · < tN−1 < tN = tend. Die Zahl h > 0 heißt Schrittweite(ausser Bequemlichkeit gibt es vorerst keinen Grund, die Schrittweite h

konstant zu wahlen).

Bezeichnet nun yn einen Naherungswert fur y(tn), n = 0, 1, . . . , N − 1,dann ist (falls y ∈ C2[t0, tend])

y(tn+1) = y(tn + h) = y(tn) + hy ′(tn) +1

2h2y ′′(ξ)

≈ y(tn) + hy ′(tn) = y(tn) + hf (tn,y(tn)) ≈ yn + hf (tn,yn).

(Explizites) Euler-Verfahren:

y0 gegeben,

yn+1 := yn + hf (tn,yn) (n = 0, 1, . . . , N − 1).


Numerik II 66

Zur Veranschaulichung einer GDG 1. Ordnung y′ = f(t, y) wird oft dasassoziierte Richtungsfeld herangezogen: In jedem Punkt (t, y) ∈ R2 wirdein Pfeil gezeichnet, der in die Richtung y′ = f(t, y) weist.

Der Graph der Losung der AWA y′ = f(t, y), y(t0) = y0, muss dann einer-seits das Richtungsfeld respektieren (d.h. die Tangenten an den Graphensind Elemente des Richtungsfelds), andererseits den Punkt (t0, y0) enthal-ten.

Die nachste Abbildung zeigt, wie das Euler-Verfahren die logistische Glei-chung y′ = y(1 − y) mit AB y(0) = 1/10 lost. Statt der exakten Trajektoriezu folgen (was naturlich unmoglich ist), produziert das Euler-Verfahren ei-ne ”stuckweise lineare Losung“ (einen Polygonzug). An der Stelle t0 = 0

arbeitet das Euler-Verfahren mit der richtigen Steigung f(t0, y0) = 9/100,bereits an der Stelle t = 1 ist die Steigung ”falsch“. In spateren Schrittenentfernt man sich (potentiell) immer weiter von der exakten Losung.


Numerik II 67

0 0.5 1 1.5 2 2.5 3 3.5 40

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9Euler−Verfahren

y’=y(1−y), y(0)=1/10


Numerik II 68

−3 −2 −1 0 1 2 30

1

2

3

4Richtungsfeld von y’=x(y−2)

und Loesungen mit Anfangswerten y(0) = −1:0.5:1


Numerik II 69

Konvergiert das Euler-Verfahren, d.h. strebt die Naherungslosung furh→ 0 gegen die exakte Losung y(t)?

Formal: Zu jedem Wert von h > 0 gehort eine Folge von Naherungenyn = yn(h), n = 0, 1, . . . , N(h) := b(tend − t0)/hc.

Das Verfahren heißt konvergent (in [t0, tend]), wenn gilt

limh→0+

max0≤n≤N(h)

‖yn(h)− y(tn)‖ = 0. (Konv)

Satz 9.1 (Konvergenz des Euler-Verfahrens) Unter den Voraussetzun-gen von Satz 8.1 konvergiert das Euler-Verfahren, genauer:

max0≤n≤N(h)

‖yn(h)− y(tn)‖ = O(h) fur h→ 0.


Numerik II 70

t_0 t

exakte Loesung Schrittweite h

0Schrittweite h

1Schrittweite h

2


Numerik II 71

Modifiziertes Euler-Verfahren:

y0 gegeben,

yn+1 := yn + hf(tn + 1

2h,yn + 12hf (tn,yn)

)(n = 0, 1, . . . , N − 1).

Verbessertes Euler-Verfahren:

y0 gegeben,

yn+1 := yn + 12h[f (tn,yn) + f (tn + h,yn + hf (tn,yn))]

(n = 0, 1, . . . , N − 1).

Die Idee dieser beiden Verfahren macht man sich leicht im Richtungsfeldklar. Auch das modifizierte und das verbesserte Euler-Verfahren konver-gieren: Eine triviale Modifikation des Beweises von Satz 9.1 zeigt, dass furdiese Verfahren sogar max0≤n≤N(h) ‖yn(h)− y(tn)‖ = O(h2) gilt.


Numerik II 72

0 0.5 1 1.5 2 2.5 3 3.5 40

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9exakte Loesung Euler−Verfahren modifiziertes Euler−Verf.verbessertes Euler−Verf.


Numerik II 73

Implizites Euler-Verfahren:

y0 gegeben,

yn+1 := yn + hf (tn + h,yn+1) (n = 0, 1, . . . , N − 1).

Im Gegensatz zu allen bisher erwahnten Verfahren ist dieses Verfahrenimplizit, d.h. um yn+1 zu bestimmen, muss in jedem Schritt ein i.Allg.nichtlineares Gleichungssystem gelost werden.

Wie in Satz 9.1 zeigt man auch fur das implizite Euler-Verfahren

max0≤n≤N(h)‖yn(h)− y(tn)‖ = O(h) fur h→ 0.


Numerik II 74

Bisher traten in der Verfahrensgleichung ausschließlich Approximationenan die Losung an zwei aufeinanderfolgenden Zeitpunkten auf, sog. Ein-schrittverfahren.

Mehrschrittverfahren dagegen beruhen auf mehrere Stellen umfassendenDifferenzenformeln, etwa

y(t+ h)− y(t− h)

2h= y′(t) +

h2

6y′′′(t) +O(h4),

3y(t)− 4y(t− h) + y(t− 2h)

2h= y′(t)− h2

3y′′′(t) +O(h3).


Numerik II 75

Diese Formeln fuhren, bei t = tn+1 ausgewertet, zur expliziten

Mittelpunktsregel: (midpoint-rule, leapfrog method)

y0,y1 gegeben,

yn+1 = yn−1 + 2hf (tn,yn) (n = 1, 2, . . . , N − 1).(9.1)

sowie einem impliziten Verfahren aus der sog. BDF-Familie (BackwardDifferentiation Methods)

Ein BDF-Verfahren:

y0,y1 gegeben,

3yn+1 − 4yn + yn−1 = 2hf (tn + h,yn+1) (n = 1, 2, . . . , N − 1).

Wie man sieht kann hier die Verfahrensgleichung erst dann ausgewertetwerden, wenn neben den Anfangswerten y0 auch eine Approximation y1vorliegt. Eine solche Anlaufrechnung erfordern alle Mehrschrittverfahren.


Numerik II 76

9.2 Einschrittverfahren – Definition und Eigenschaften

Ein Einschrittverfahren (ESV) hat die Form

yn+1 = yn + hΦf (yn+1,yn, tn;h). (ESV)

Wir werden ausschließlich Verfahren untersuchen, bei denen die Verfah-rensfunktion Φf die folgenden beiden Eigenschaften besitzt:

Φf≡0 (yn+1,yn, tn;h) ≡ 0 (V1)

und

‖Φf (yn+1,yn, tn;h)− Φf (y∗n+1,y∗n, tn;h)‖ ≤M

1∑j=0

‖yn+j − y∗n+j‖. (V2)

Bei ”vernunftigen“ ESV ist (V2) eine Folge der Lipschitz-Stetigkeit von f

(vgl. Satz 8.1), die immer vorausgesetzt wird.

9.2 Einschrittverfahren – Definition und Eigenschaften TU Bergakademie Freiberg, SS 2010

Numerik II 77

Beispiele fur etwas kompliziertere ESV:

yn+1 − yn = 14h(k1 + 3k3)

mit k1 = f (tn,yn), k2 = f (tn + 13h,yn + 1

3hk1),

k3 = f (tn + 23h,yn + 2

3hk2),

(Beispiel 1)

ein explizites ESV, das zur Klasse der Runge-Kutta-Verfahren a b (vgl. §9.3)gehort und ein implizites ESV der Runge-Kutta-Klasse,

yn+1 − yn = 12h(k1 + k2)

mit k1 = f (tn,yn), k2 = f (tn + h,yn + 12hk1 + 1

2hk2).(Beispiel 2)

aCARLE DAVID TOLME RUNGE (1856–1927)bMARTIN WILHELM KUTTA (1867–1944)


Numerik II 78

Das Verfahren (ESV) heißt konvergent, wenn

limh→0

t=t0+nh

yn = limh→0

t=t0+nh

yn(h) = y(t)

gilt – und zwar

• fur alle AWPe, die den Voraussetzungen von Satz 8.1 genugen(y(t) bezeichnet die Losung eines solchen AWPs),• gleichmaßig fur alle t ∈ [t0, tend],• fur alle Losungen {yn(h)} = {yn} von (ESV) mit Anfangswerty0(h), der limh→0 y0(h) = y0 erfullt.

Aquivalent: Der globale Diskretisierungsfehler en = en(h) := y(tn) −yn(h) strebt gleichmaßig gegen 0 (fur h→ 0):

limh→0

max0≤n≤N

‖en(h)‖ = limh→0

max0≤n≤N

‖y(tn)− yn(h)‖ = 0.


Numerik II 79

Wir definieren den lokalen Diskretisierungsfehler (lokaler Abbruchfehler)eines Verfahrens Tn = Tn(h) im n-ten Schritt als die Differenz von lin-ker Seite und rechter Seite der Verfahrensgleichung (so skaliert, dassfur h → 0 die Differentialgleichung approximiert wird) wenn anstelle derNaherungslosung die exakte Losung eingesetzt wird.

Ein Verfahren heißt konsistent von der Ordnung p, falls

Tn(h) = O(hp) fur h→ 0.

Beispiel: Mittelpunktsregel

Tn =y(tn+1)− y(tn−1)

2h− f(tn,y(tn))

=

[y ′(tn) +

h2

6y ′′′(tn) +O(h4)

]− y ′(tn) =

h2

6y ′′′(tn) +O(h4),

d.h. konsistent von der Ordnung p = 2.


Numerik II 80

In der Literatur wird oft auch eine abweichende Definition des lokalenDiskretisierungsfehlers verwandt, und zwar basierend auf der Verfahrens-gleichung in der Form (ESV), was zur Erhohung um eine h-Potenz fuhrt.

Motivation: Beschreibung des Fehlers in einem Schritt unter der Lokali-sierungsannahme yn = y(tn). In diesem Fall liefert 1 Schritt von (ESV) imVgl. zur exakten Losung

yn+1(h) = y(tn) + hΦf (yn+1,y(tn), tn;h),

y(tn+1) = y(tn) + hΦf (y(tn+1),y(tn), tn;h) + hTn+1(h).

Wir bezeichnen die Differenz Sn+1(h) := y(tn+1) − yn+1 als Schrittfehler.Es gilt (mit (V2))

‖Sn+1‖ ≤ h‖Φf (y(tn+1),y(tn), tn;h)− Φf (yn+1,y(tn), tn;h)‖+ h‖Tn+1‖≤ hM‖Sn+1‖+ h‖Tn+1‖,

d.h. wegen (1− hM)‖Sn+1‖ ≤ hTn+1 verhalt sich Sn fur h→ 0 wie hTn.


Numerik II 81

Relevanz von Sn: Bei der Integration von (AWA) von t0 bis tend sind(tend − t0)/h Schritte erforderlich. Wird im n-ten Schritt der SchrittfehlerSn begangen, so ergibt sich – unter der vereinfachenden Annahme, dassdiese Fehler sich nicht gegenseitig beeinflussen – insgesamt ein akkumu-lierter (globaler) Fehler von

tend − t0h

S(h) ∼ T (h).

Die entscheidende Voraussetzung fur diese vereinfachende Annahme ist,wie wir sehen werden, die Stabilitat des Verfahrens.


Numerik II 82

9.3 Runge-Kutta-Verfahren

9.3.1 Herleitung mittels Quadraturverfahren

Ausgangspunkt wie immer

y(t+ h) = y(t) + [y(t+ h)− y(t)] = y(t) +

∫ t+h

t

y ′(s) ds

Substitution: s = t+ τh, 0 ≤ τ ≤ 1

= y(t) + h

∫ 1

0

y ′(t+ τh) dτ.

Approximiere durch Quadraturformel∫ 1

0

g(τ) dτ ≈m∑

j=1

βjg(γj). (∗)

Damit zumindest g ≡ 1 exakt integriert wird, fordern wir∑m

j=1 βj = 1.

9.3 Runge-Kutta-Verfahren TU Bergakademie Freiberg, SS 2010

Numerik II 83

Daraus folgt

y(t+ h) ≈ y(t) + h

m∑j=1

βjy′(t+ γjh)

= y(t) + h

m∑j=1

βjf (t+ γjh,y(t+ γjh))

(RK-1)

Problem: y(t+γjh) = y(t)+h∫ γj0

y ′(t+τh) dτ sind unbekannt. Naherungenwieder durch Quadraturformeln, aber mit den alten Knoten γj (j = 1, . . . ,m)aus (∗) (sonst wurden sich neue ‘Unbekannte’ y(t+ Knoten · h) ergeben).∫ γj

0

g(τ) dτ ≈m∑`=1

αj,`g(γ`) (j = 1, . . . ,m). (∗∗)

Damit zumindest g ≡ 1 exakt integriert wird, fordern wir∑m`=1 αj,` = γj

∀ j = 1, . . . ,m.


Numerik II 84

Damit ergibt sich

y(t+ γjh) ≈ y(t) + h∑m`=1αj,`y

′(t+ γ`h)

= y(t) + h∑m`=1αj,`f (t+ γ`h,y(t+ γ`h))

(RK-2)

Abkurzung: kj := f (t+ γjh,y(t+ γjh)) (j = 1, . . . ,m).

(RK-2): kj ≈ f

(t+ γjh,y(t) + h

m∑`=1

αj,`k`

)(j = 1, . . . ,m).

(RK-1): y(t+ h) ≈ y(t) + hm∑j=1

βj kj .


Numerik II 85

m-stufiges Runge-Kutta-Verfahren (RKV):

yn+1 = yn + h

m∑j=1

βjkj mit

kj = f

(tn + γjh,yn + h

m∑`=1

αj,`k`

)(j = 1, . . . ,m).

(RKV)

Ubliche Darstellung durchButcher-Tableaua

aJOHN CHARLES BUTCHER (∗1933)

γ1 α1,1 · · · α1,m

......

...

γm αm,1 · · · αm,m

β1 · · · βm


Numerik II 86

Beispiele.

0 0 0

1 1 0

1/2 1/2

symbolisiert ein zweistufiges explizites RKV, namlichdas verbesserte Euler-Verfahren:

k1 = f(tn,yn),

k2 = f(tn + h,yn + hk1),

yn+1 = yn + h2 (k1 + k2)

= yn + h2

(f(tn,yn) + f(tn + h,yn + hf(tn,yn))

)

Beachte: ein RKV ist explizit, wenn αj,` = 0 ∀j ≤ ` gilt, d.h. wenn dieKoeffizienten αj,` eine echte untere Dreiecksmatrix bilden.


Numerik II 87

0 1/4 −1/4

2/3 1/4 5/12

1/4 3/4

symbolisiert ein zweistufiges implizites RKV:

k1 = f(tn,yn + h( 1

4k1 −14k2)

),

k2 = f(tn + 2

3h,yn + h( 14k1 + 5

12k2)),

(” zwei “ i.A. nichtlineare Gleichungen fur k1 und k2)

yn+1 = yn + h4 (k1 + 3k2).

(Beispiel 2 aus §9.2 is ein weiteres implizites zweistufiges RKV.)


Numerik II 88

0 0 0 0

1/2 1/2 0 0

1 −1 2 0

1/6 4/6 1/6

symbolisiert ein dreistufiges explizites RKV

Verfahren dritter Ordnung von Kutta:

k1 = f (tn,yn),

k2 = f(tn + 1

2h,yn + 12hk1

),

k3 = f(tn + h,yn + h(−k1 + 2k2)

),

yn+1 = yn + 16h(k1 + 4k2 + k3).


Numerik II 89

0 0 0 0

1/3 1/3 0 0

2/3 0 2/3 0

1/4 0 3/4

symbolisiert ein dreistufiges explizites RKV

Verfahren dritter Ordnung von Heun:

k1 = f (tn,yn),

k2 = f(tn + 1

3h,yn + 13hk1

),

k3 = f(tn + 2

3h,yn + 23hk2

),

yn+1 = yn + h4 (k1 + 3k3)

(vgl. Beispiel 1 aus §9.2).


Numerik II 90

0 0 0 0 0

1/2 1/2 0 0 0

1/2 0 1/2 0 0

1 0 0 1 0

1/6 2/6 2/6 1/6

symbolisiert ein vierstufiges explizites RKV

Klassisches Runge-Kutta-Verfahren:

k1 = f (tn,yn),

k2 = f (tn + 12h,yn + 1

2hk1),

k3 = f (tn + 12h,yn + 1

2hk2),

k4 = f (tn + h,yn + hk3),

yn+1 = yn + 16h(k1 + 2k2 + 2k3 + k4).


Numerik II 91

Eine alternative Form von (RKV) ist

yn+1 = yn + hm∑j=1

βjf (tn + γjh, yj)

mit yj = yn + hm∑`=1

αj,`f (tn + γ`h, y`) (j = 1, . . . ,m)

(RKV∗)

(setze kj = f (tn + γjh, yj)).

Interpretation:

yj : Approximationen an die Losung y zur Zeit tn + γjh

kj : Approximationen an die Steigungen y ′(tn + γjh)


Numerik II 92

9.3.2 Konsistenzordnung bei Runge-Kutta-Verfahren

Jedes RKV hat die Form

yn+1 = yn+hΦf (yn+1,yn, tn;h)

mit Φf (yn+1,yn, tn;h) =

m∑j=1

βjkj .

Ein RKV ist genau dann konsistent (und damit konvergent), wenn

m∑j=1

βj = 1.

Um die Konsistenzordnung eines RKVs zu bestimmen (oder um m-stufigeRKV mit moglichst hoher Konsistenzordnung zu konstruieren), sind kompli-zierte Rechnungen erforderlich.


Numerik II 93

Wir untersuchen als Beispiel explizite dreistufige RKV,

0 0 0 0

γ2 γ2 0 0

γ3 γ3 − α3,2 α3,2 0

β1 β2 β3

,

und entwickeln

Tn+1(h) =y(tn+1)− y(tn)

h− Φf (y(tn), tn;h)

=y(tn+1)− y(tn)

h−

3∑j=1

βjkj

nach Potenzen von h (unter der Voraussetzung, dass y bzw. f genugendoft differenzierbar sind).


Numerik II 94

Fur skalare AWA ergibt sich mit den Abkurzungen

F := ft + fyf und G := ftt + 2ftyf + fyyf2

(alle Ableitungen von f werden an der Stelle (tn, y(tn)) ausgewertet) dieBeziehung

y(tn+1)− y(tn)

h= f +

1

2Fh+

1

6(G+ fyF )h2 +O(h3).

Anderseits ist

k1 = f(tn, y(tn)) = f,

k2 = f(tn + hγ2, y(tn) + hγ2k1) = f + hγ2F + 12h

2γ22G+O(h3),

k3 = f(tn + hγ3, y(tn) + h(γ3 − α3,2)k1 + hα3,2k2)

= f + hγ3F + h2(γ2α3,2Ffy + 12γ

23G) +O(h3).


Numerik II 95

Das bedeutet:

Tn+1(h) =[1−

∑3j=1βj

]f +

[12 − β2γ2 − β3γ3

]Fh

+[( 13 − β2γ

22 − β3γ23) 1

2G+ ( 16 − β3γ2α3,2)Ffy

]h2 +O(h3)

Folgerungen:

1. Das Euler-Verfahren ist das einzige einstufige explizite RKV der Ord-nung 1 (β1 = 1). Es gibt kein einstufiges explizites RKV hoherer Ord-nung.

2. Die zweistufigen expliziten RKV der Ordnung 2 sind durch

β1 + β2 = 1 und β2γ2 = 12

charakterisiert. Beispiele sind das modifizierte (β1 = 0, β2 = 1, γ2 = 12 )

und das verbesserte Euler-Verfahren (β1 = β2 = 12 , γ2 = 1). Kein

explizites zweistufiges RKV besitzt die Ordnung 3.


Numerik II 96

3. Explizite dreistufige RKV der Ordnung 3 sind durch die vier Gleichun-gen

β1 + β2 + β3 = 1, β2γ22 + β3γ

23 = 1

3 ,

β2γ2 + β3γ3 = 12 , β3γ2α3,2 = 1

6

charakterisiert. (Man kann zeigen, dass keine dieser Methoden dieOrdnung 4 besitzt.) Beispiele sind das Verfahren von Heun (β1 = 1

4 ,β2 = 0, β3 = 3

4 , γ2 = 13 , γ3 = α3,2 = 2

3 ) und das Verfahren von Kutta(β1 = 1

6 , β2 = 23 , β3 = 1

6 , γ2 = 12 , γ3 = 1, α3,2 = 2).

4. Ahnliche (kompliziertere) Rechnungen zeigen, dass es eine zweipa-rametrige Familie expliziter vierstufiger RKV der Ordnung 4 gibt, vondenen keines die Ordnung 5 besitzt. Ein Beispiel ist das klassischeRunge-Kutta-Verfahren. Weitere Beispiele sind


Numerik II 97

0 0 0 0 0

1/3 1/3 0 0 0

2/3 −1/3 1 0 0

1 1 −1 1 0

1/8 3/8 3/8 1/8

(3/8-Regel)

0 0 0 0 0

2/5 2/5 0 0 0

3/5 −3/20 3/4 0 0

1 19/44 −15/44 40/44 0

55/360 125/360 125/360 55/360

(Formel von Kuntzmann).


Numerik II 98

Die oben beschriebene Methode, die Ordnung eines RKVs zu bestimmen,wird fur Verfahren hoherer Ordnung schnell unubersichtlich: Die Koeffizi-enten eines expliziten Verfahrens der Ordnung 3 mussen 4 Gleichungenerfullen (s.o.), wahrend bei einem Verfahren der Ordnung 8 bereits 200nicht-lineare Gleichungen uberpruft werden mussen. Die sog. Butcher-Theorie (vgl. J. C. Butcher, The Numerical Analysis of Ordinary DifferentialEquations. Runge-Kutta and General Linear Methods. John Wiley & Sons,Chichester 1987) erleichtert mit Hilfe graphentheoretischer Baume dieBuchhaltung bei den partiellen Ableitungen von f und erlaubt eine elegan-te Berechnung der Ordnung eines gegebenen RKVs (sie liefert aber keineMethode, ein Verfahren mit gewunschter Ordnung zu konstruieren).

Wir beschranken uns hier darauf, notwendige Ordnungsbedingungen ab-zuleiten, die sich aus den speziellen AWPen y′ = y+ t`−1, y(0) = 0, (` ∈ N)ergeben.


Numerik II 99

Satz 9.2 (Notwendige Ordnungsbedingungen fur RKV) Das durch dasButcher-Tableau

c A

b>

definierte RKV besitze die Ordnung p. Dann gelten

b>AkC`−1e =(`− 1)!

(`+ k)!=

1

`(`+ 1) . . . (`+ k)

fur ` = 1, 2, . . . , p und k = 0, 1, . . . , p− `.

Dabei sind

b := [β1, β2, . . . , βm]>, A := [αj,ν ]1≤j,ν≤m,

C := diag(γ1, γ2, . . . , γm) und e := [1, 1, . . . , 1]> ∈ Rm.


Numerik II 100

Spezialfalle der notwendigen Bedingungen aus Satz 9.2 sind (fur k = 0)

b>C`−1e =m∑j=1

βjγ`−1j =

1

`fur ` = 1, 2, . . . , p

sowie (fur ` = 1 mit k ← k + 1)

b>Ak−1e =1

k!fur k = 1, 2, . . . , p.

Bemerkung. Ein explizites m-stufiges RKV besitzt hochstens die Konsis-tenzordnung m, denn hier ist Am = O (A ist echte untere Dreiecksmatrix).Fur die optimale Ordnung p(m) eines expliziten m-stufigen RKVs gilt sogarp(m) ≤ m− 1 falls m ≥ 5, genauer:

m 1 2 3 4 5 6 7 8 9 10 11 12

p(m) 1 2 3 4 4 5 6 6 7 7 8 9


Numerik II 101

9.4 Lineare Mehrschrittverfahren

Bei Mehrschrittverfahren gehen, im Gegensatz zu den Einschrittverfahren,bei der Berechnung der Naherung yn+1 neben yn noch weiter zuruckliegendeNaherungen yn−1,yn−2, . . . mit ein. Die wichtigste Klasse der linearenMehrschrittverfahren (LMV) besitzt die allgemeine Form

r∑j=0

αjyn+j = h

r∑j=0

βjf (tn+j ,yn+j), n = 0, 1, 2, . . . . (LMV)

mit Konstanten {αj}rj=0 sowie {βj}rj=0.

Da diese nur bis auf einen (von Null verschiedenen) Skalierungsfaktoreindeutig sind, wird oft die Normierung αr = 1 vorgenommen.

Das Verfahren (LMV) ist explizit falls βr = 0, ansonsten implizit.

Wir gehen zunachst auf spezielle Unterfamilien LMV ein.

9.4 Lineare Mehrschrittverfahren TU Bergakademie Freiberg, SS 2010

Numerik II 102

9.4.1 Adams-Verfahren

Adams-Verfahren sind von der speziellen Gestalt

yn+r − yn+r−1 = h

r∑j=0

βjf (tn+j ,yn+j), (9.2)

d.h. sie sind charakterisiert durch

αr = 1, αr−1 = −1, sowie α0 = α1 = · · · = αr−2 = 0.

Die Koeffizienten βj ergeben sich aus der Forderung maximaler Ordnungfur gegebenes r. Diese betragt im expliziten Fall r, im impliziten r + 1. Ers-tere Verfahrensklasse werden als Adams-Bashforth-Verfahren bezeichnet,letztere als Adams-Moulton-Verfahren.


Numerik II 103

Alternative Herleitung der Adams-Verfahren:

Aus der Dgl. ergibt sich

y(tn+r) = y(tn+r−1) +

∫ tn+r

tn+r−1

y ′(τ) dτ = y(tn+r−1) +

∫ tn+r

tn+r−1

f (τ,y(τ)) dτ.

Wahlt man {βj}rj=0 nun so, dass∫ tn+r

tn+r−1

g(τ) dτ ≈ hr∑j=0

βjg(tn+j)

eine interpolatorische Quadraturformel darstellta., so ergeben sich eben-so die Koeffizienten des jeweiligen (expliziten bzw. impliziten) Adams-Verfahrens.

ad.h. man ersetze g durch das Interpolationspolynom durch die Wertepaare{(tn, g(tn)), . . . , (tn+r−1, g(tn+r−1))} vom Grad r − 1 (expliziter Fall) bzw. durch{(tn, g(tn)), . . . , (tn+r, g(tn+r))} vom Grad r (impliziter Fall)


Numerik II 104

Fur r = 1 bis 4 ergeben sich die expliziten Adams-Bashforth-Verfahrenwie folgt:

r = 1 : yn+1 = yn + hf (tn,yn),

r = 2 : yn+2 = yn+1 +h

2(−f (tn,yn) + 3f (tn+1,yn+1)) ,

r = 3 : yn+3 = yn+2 +h

12(5f (tn,yn)− 16f (tn+1,yn+1)

+23f (tn+2,yn+2)) ,

r = 4 : yn+4 = yn+3 +h

24(−9f (tn,yn) + 37f (tn+1,yn+1)

−59f (tn+2,yn+2) + 55f (tn+3,yn+3)) .

Insbesondere erhalten wir fur r = 1 das explizite Euler-Verfahren.


Numerik II 105

Die impliziten Adams-Moulton-Verfahren fur r = 1 bis 4 lauten:

r = 1 : yn+1 = yn +h

2(f (tn,yn) + f (tn+1,yn+1)) ,

r = 2 : yn+2 = yn+1 +h

12(−f (tn,yn) + 8f (tn+1,yn+1)

+5f (tn+2,yn+2)) ,

r = 3 : yn+3 = yn+2 +h

24(f (tn,yn)− 5f (tn+1,yn+1)

+19f (tn+2,yn+2 + 9f (tn+3,yn+3))) ,

r = 4 : yn+4 = yn+3 +h

720

(−19f (tn,yn) + 106f (tn+1,yn+1)

− 264f (tn+2,yn+2) + 646f (tn+3,yn+3)

+ 251f (tn+4,yn+4)).

Fur r = 1 erhalten wir die Trapezregel.


Numerik II 106

9.4.2 Nystrom-Verfahren

Nystrom-Verfahren besitzen die Form

yn+r − yn+r−2 = hr∑j=0

βjf (tn+j ,yn+j). (9.3)

Als explizites Nystrom-Verfahren mit r = 2 erhalten wir die bereits bekannteMittelpunktsregel (9.1).

Als implizites Nystrom-Verfahren mit r = 2 ergibt sich die Simpson-Regel

yn+2 − yn =h

3

(f (tnyn) + 4f (tn+1,yn+1) + f (tn+2,yn+2)

).


Numerik II 107

9.4.3 BDF-Verfahren

Im Gegensatz zu den Runge-Kutta- und Adams-Verfahren, die mit Hilfevon Quadratur hergeleitet wurden, beruht die Idee der BDF-Verfahren(backward differentiation formulas) auf numerischer Differentiation.

Zur Konstruktion eines linearen r-Schritt-Verfahrens seien die Naherungenyn, yn−1, . . . , yn−r+1 bekannt und die nachste Naherung yn+1 zu berech-nen. Hierzu wird folgende Konstruktionsidee verwandt:

(1) Lege durch die r + 1 Wertepaare {(tj , yj)}n+1j=n−r+1 das eindeutig be-

stimmte Interpolationspolynom p ∈Pr.

(2) Die fehlende Intepolationsvorschrift p(tn+1) = yn+1 (yn+1 ist noch zuberechnen) wird ersetzt durch die Vorschrift

p′(tn+1) = f(tn+1, yn+1), (9.4)

d.h. dass p an der Stelle tn+1 die Differentialgleichung erfullen soll.


Numerik II 108

Die Newton-Darstellung des gesuchten Interpolationspolynoms ist gege-ben durch

p(t) =fn+1 + fn+1,n(t− tn+1) + fn+1,n,n−1(t− tn+1)(t− tn)

+ · · ·+ fn+1,n,...,n−r+2,n−r+1(t− tn+1) · · · (t− tn−r+2)

Unter der vereinfachenden Annahme konstanter Schrittweite h erhalt manaus des Newton-Darstellung von p

p′(tn+1) =

r∑j=1

fn+1,n,...,n+1−jhj−1(j − 1)! . (9.5)

Fuhrt man die Notation der Ruckwartsdifferenzen ein:

∇0yn+1 := yn+1

∇yn+1 := yn+1 − yn,∇jyn+1 := ∇(∇j−1yn+1) = ∇j−1yn+1 −∇j−1yn, j = 2, 3, . . .


Numerik II 109

so laßt sich p′(tn+1) ausdrucken als

p′(tn+1) =1

h

r∑j=1

∇jyn+1

j,

und zusammen mit der Forderung (9.4) die Verfahrensvorschrift

r∑j=1

1

j∇jyn+1 = hf(tn+1, yn+1) (9.6)

des BDF-Verfahrens der Ordnung r, kurz BDFr genannt.

Durch die Indexverschiebung n+ 1 7→ n+ r erhalten wir die BDF-Verfahrenin unserer STandardnotation fur lineare Mehrschritttverfahren.


Numerik II 110

Die BDF-Verfahren fur r = 1 bis 6 lauten:

r = 1 : yn+1 − yn = hf (tn+1,yn+1),

r = 2 : 32yn+2 − 2yn+1 + 1

2yn = hf (tn+2,yn+2)

r = 3 : 116 yn+3 − 3yn+2 + 3

2yn+1 − 13yn = hf (tn+3,yn+3),

r = 4 : 2512yn+4 − 4yn+3 + 3yn+2 − 4

3yn+1 + 14yn = hf (tn+4,yn+4),

r = 5 : 13760 yn+5 − 5yn+4 + 5yn+3 − 10

3 yn+2 + 54yn+1 − 1

5un

= hf (tn+5,yn+5),

r = 6 : 14760 yn+6 − 6yn+5 − 15

2 yn+4 − 203 yn+3 + 15

4 yn+2 − 65yn+1 + 1

6un

= hf (tn+6,yn+6).

Fur r = 1 erhalten wir das implizite Euler-Verfahren.


Numerik II 111

9.4.4 Der lokale Diskretisierungsfehler bei LMV

Setzt man in (LMV) die exakte Losung ein und beachtet, dass diesey ′(tn) = f (tn,y(tn)) erfullt, so erhalten wir (nach Division durch h)

Tn+r(h) =1

h

r∑j=0

αjy(tn+j)− hr∑j=0

βjy′(tn+j)

.

Entwickelt man alle Auswertungen von y bzw. y ′ an der Stelle t = tn

y(tn+j) = y(tn) + jhy ′(tn) +(jh)2

2y ′′(tn) +

(jh)3

6y ′′′(tn) + . . .

y ′(tn+j) = y ′(tn) + jhy ′′(tn) +(jh)2

2y ′′′(tn) +

(jh)3

6y ′′′′(tn) + . . . ,

und sortiert Terme mit gleicher h-Potenz, so erhalt man die Darstellung . . .


Numerik II 112

Tn+r(h) =1

h

r∑j=0

αj

y(tn) +

r∑j=0

(jαj − βj)

y ′(tn)

+ h

r∑j=0

(j2

2αj − jβj

)y ′′(tn)

+ · · ·+ hq

r∑j=0

(jq+1

(q + 1)!αj −

jq

q!βj

)y (q+1)(tn) +O(hq+1).

Konsistentz des LMV, also Tn(h)→ 0 fur h→ 0, liegt somit vor, sofern

r∑j=0

αj = 0 sowier∑j=0

jαj =r∑j=0

βj . (9.7)

Konsistenzordnung p ∈ N liegt vor, wenn die ersten p+ 1 Terme in eckigenKlammern verschwinden.


Numerik II 113

9.4.5 Charakteristische Polynome

Bei der Analyse LMV spielen die mit den Koeffizienten {αj}rj=0 und {βj}rj=0

gebildeten charakteristischen Polynome

ρ(ζ) :=

r∑j=0

αjζj und σ(ζ) :=

r∑j=0

βjζj (9.8)

eine zentrale Rolle.

Bei einem r-Schrittverfahren gilt ρ ∈Pr und, bei impliziten r-Schrittverfahren,σ ∈Pr. Bei expliziten LMV ist der Grad von σ kleiner als r.

Mit Hilfe der charakteristischen Polynome lassen sich die beiden Konsis-tenzbedingungen (9.7) formulieren als

ρ(1) = 0 und ρ′(1) = σ(1). (9.9)


Numerik II 114

Beispiel: Beim Adams-Moulton-Verfahren fur r = 2

yn+2 = yn+1 +h

12

(−f (tn,yn) + 8f (tn+1,yn+1) + 5f (tn+2,yn+2)

),

gilt

α0 = 0, α1 = −1, α2 = 1, β0 =−1

12, β1 =

8

12, β2 =

5

12

und man erhalt die charakteristischen Polynome

ρ(ζ) = ζ2 − ζ, σ(ζ) =1

12

(5ζ2 + 8ζ − 1

).


Numerik II 115

Wegen

α0 + α1 + α2 = 0,

0 · α0 + 1 · α1 + 2 · α2 − (β0 + β1 + β2) = 0,

0 · α0 +1

2· α1 +

4

2α2 − (0 · β0 + 1 · β1 + 2 · β2) = 0,

1

6(0 · α0 + 1 · α1 + 8α2)− 1

2(0 · β0 + 1 · β1 + 4 · β2) = 0,

1

24(0 · α0 + 1 · α1 + 16α2)− 1

6(0 · β0 + 1 · β1 + 8 · β2) =

5

8− 2

36= 0

besitzt dieses Verfahren die Konsistenzordnung p = 3.


Numerik II 116

9.4.6 Anlaufrechnung

Bei jedem Start (oder Neutsart) eines r-Schrittverfahrens (r > 1) mussenzunachst neben den Anfangswerten y0 die Approximationen y1,y2, . . . ,yr−1berechnet werden.

Um die Ordnung p dieses Verfahrens aufrechtzuerhalten genugt es, dieAnfangswerte mit einem Verfahren der Ordnung p− 1 zu berechnen.Grund: da dies nur r − 1 Mal erfolgt – unabhangig von n – verliert man imGrenzwert h → 0 keine h-Potenz durch die Akkumulation der Schrittfehlerbei der Anlaufrechnung; somit ist die Konvergenzordnung des ab n = r

benutzen Verfahrens ausschlaggebend.

Beispiel: Zur Berechnung von y1 bei der Anlaufrechnung fur die Mittel-punktsregel (9.1), welche konsistent ist von der Ordnung p = 2, konnteman ohne Ordnungsverlust das explizite Euler-Verfahren heranziehen.


Numerik II 117

9.4.7 Pradiktor-Korrektor-Verfahren

Eine beliebte Technik, das aufwandige Gleichungslosen in jedem Schritteines impliziten LMV zu umgehen besteht darin, zunachst mittels einesexpliziten Verfahrens gleicher Schrittlange eine Naherung yn+r zu berech-nen (Pradiktor) und diesen Wert dann im impliziten Verfahren (Korrektor)anstelle von yn+r einzusetzen.

Beispiel: Kombination des Adams-Bashforth-Verfahrens mit r = 1 (ex-plizites Euler-Verfahren) mit dem Adams-Moulton-Verfahren der gleichenSchrittzahl (Trapezregel):

yn+1 = yn + hf (tn,yn), (Pradiktorschritt),

yn+1 = yn +h

2(f (tn,yn) + f (tn+1, yn+1)) , (Korrektorschritt).

Man kann zeigen, dass dieses Verfahren die Konsistenzordnung p = 2

besitzt.


Numerik II 118

9.4.8 Vergleich Ein- und Mehrschrittverfahren

Vorteile von Einschrittverfahren:

• Einschrittverfahren sind selbststartend.

• Eine Anderung der Schrittweite h ohne Mehraufwand moglich.

• Integration uber Unstetigkeitsstellen der Losung bei Einschrittverfahrenmoglich ohne Ordnungsverlust, sofern diese nur Gitterpunkte sind.

Vorteil von Mehrschrittverfahren: wenige Auswertungen der rechten Seitebei gleicher Konsistenzordnung.


Numerik II 119

9.5 Konvergenz von Einschrittverfahren

Satz 9.3 (Beziehung lokaler-globaler Diskretisierungsfehler) Unter dengebenen Voraussetzungen (vgl. Satz 8.1 sowie (V2)) gilt

‖en‖ ≤(

(‖e0‖+ (tn − t0) max1≤j≤n

‖Tj‖)

exp(M(tn − t0)).

Insbesondere ist ein ESV genau dann konvergent, wenn es konsistent ist.

9.5 Konvergenz von Einschrittverfahren TU Bergakademie Freiberg, SS 2010

Numerik II 120

Satz 9.4 (Gesamtfehler bei expliziten ESV) Das explizite ESV (ESV)werde auf einem Rechner durch

yn+1 = yn + hΦf (yn, tn;h) + εn+1, y0 = y0 + ε0,

realisiert. Ist ‖εn‖ ≤ ε und ‖Tn‖ ≤ T fur alle n = 0, 1, . . ., so folgt

‖y(tn)− yn‖ ≤(‖ε0‖+ (tn − t0)(T + ε

h ))

exp(M(tn − t0)).

Dilemma: Bei ”großer“ Schrittweite h ist (ublicherweise) T groß; wahltman h sehr ”klein“, so ist zwar T klein, aber ε

h groß, dh. der Anteil derRundungsfehler dominiert den Gesamtfehler.

Wichtig sind also Verfahren hoher Ordnung, weil dort T schon bei ”mode-rater“ Große von h klein wird.

9.5 Konvergenz von Einschrittverfahren TU Bergakademie Freiberg, SS 2010

Numerik II 121

9.6 Nullstabilitat linearer Mehrschrittverfahren

Konvergenz bei Einschrittverfahren: Beitrag des n-ten Schrittfehlers Snbeschrankt durch eM(tend−t0)‖Sn‖, was fur h→ 0 noch gegen Null geht.

Diese Eigenschaft nennt man auch Nullstabilitat, und sie ist fur ESV immergegeben. Bei LMV ist dies nicht der Fall.

Beispiel: Beim LMV yn+2 − 3yn+1 + 2yn = −hf (tn,yn) betragt der lokaleDiskretisierungsfehler

Tn+2(h) =h

2y ′′(tn) +O(h2).

Wir wenden es an auf die AWA

y′(t) = 0, y(0) = 0 mit Losung y(t) ≡ 0. (9.10)

Mit den Startwerten y0 = y1 = 0 liefert es tatsachlich die exakte Losung.

9.6 Nullstabilitat linearer Mehrschrittverfahren TU Bergakademie Freiberg, SS 2010

Numerik II 122

Setzt man jedoch y1 = h um einen kleinen Fehler der Ordnung h bei derApproximation von y(t1) zu simulieren, so erhalt man fur die Approximationder Losung an der Stelle t = 1 folgende Werte (h = 1/N ):

N yN

5 6.2

10 102.3

20 5.2× 104

Wegen y1 → 0 fur h→ 0 sind diese Anfangsdaten zulassig. Wie man siehtkonvergiert yN aber nicht gegen y(tN ) = y(1) = 0.

Die Approximationen erfullen die Differenzengleichung

yn+2 − 3yn+1 + 2yn = 0, n = 0, 1, 2, . . . . (9.11)

mit der Losung

yn = (2n − 1)y1 − (2n − 2)y0 = 2y0 − y1 + 2n(y1 − y0), n ≥ 2.


Numerik II 123

9.6.1 Losung linearer Differenzengleichungen

Zur Losung der homogenen linearen Differenzengleichung der Ordnung r

αryn+r + αr−1yn+r−1 + · · ·+ α0yn =

r∑j=0

αjyn+j = 0 (9.12)

macht man den Ansatz yn = ζn. Einsetzen in (9.12) fuhrt nach Divisiondurch ζn auf die Bedingung

r∑j=0

αjζj = 0,

d.h. yn = ζn lost (9.12) falls ζ Nullstelle des ersten charakteristischenPolynoms ρ(ζ) ist (vgl. (9.8)).


Numerik II 124

Ist nunρ(ζ) = αr(ζ − ζ1)(ζ − ζ2) · · · (ζ − ζr)

und sind die Nullstellen paarweise verschieden, so stellen {ζni }ri=1 insge-samt r linear unabgangige Losungen von (9.12) dar. Aufgrund der Linearitatund Homogenitat von (9.12) ist jede Linearkombination

yn = c1ζn1 + c2ζ

n2 + . . . crζ

nr , c1, . . . , cr beliebig (9.13)

ebenfalls Losung. Zu gegebenen Anfangsbedingungen y0, . . . , yr−1 werdendie Koeffizienten cj bestimmt als Losung des LGS

c1 + c2 + · · ·+ cr = y0,

c1ζ1 + c2ζ2 + · · ·+ crζr = y1,

......

c1ζr−11 + c2ζ

r−12 + · · ·+ crζ

r−1r = yr−1.


Numerik II 125

Beispiel: Das charakteristische Polynom der DIfferenzengleichung (9.11)ist

ρ(ζ) = ζ2 − 3ζ + 2 = (ζ − 1)(ζ − 2).

Fazit: Besitzt ρ(ζ) Nullstellen vom Betrag > 1, so kann das zugehorigeLMV nicht konvergent sein.

Fallen zwei Nullstellen zusammen, d.h. ζi = ζj , so sind ζni und ζnj linearabhangig. Eine weitere linear unabhangige Losung ist nζn−1i .

Bei einer dreifachen Nullstelle ζi ist n2ζn−2i eine weitere etc.

Beispiel: Das (konsistente) LMV

yn+2 − 2yn+1 + yn =h

2(f (tn+2,yn+2)− f (tn,yn)) .

angewandt auf y′(t) = 0.

Fazit: Besitzt ρ(ζ) mehrfache Nullstellen von Betrag 1, so kann ebenfallskeine Konvergenz vorliegen.


Numerik II 126

Beispiel: Das konsistente LMV

yn+3 − 2yn+2 +5

4yn+1 −

1

4yn =

h

4f(tn,yn)

angewandt auf (9.10).

Fazit: Bei mehrfachen Nullstellen mit Betrag < 1 liegt Konvergenz vor (li-neares Wachstum wird ubertroffen durch exponentielles Abklingen).

Ein LMV heißt nullstabil, falls fur die Nullstellen dessen ersten charakteris-tischen Polynoms ρ(ζ) gilt

(a) |ζi| ≤ 1 fur alle i = 1, 2, . . . , r

(b) Ist ζi mehrfache Nullstelle, so gilt |ζi| < 1.

Beispiele:

• Die Adams-Verfahren sind nullstabil.• Die BDF-Verfahren sind nullstabil fur 1 ≤ r ≤ 6.


Numerik II 127

Unsere Beispiele zeigen, dass Nullstabilitat notwendig fur die Konvergenzist. Tatsachlich ist sie auch hinreichend, damit ein konsistentes LMV kon-vergiert.

Satz 9.5 (Dahlquist, 1956) Fur LMV angewandt auf (AWA) gilt

Konsistenz + Nullstabilitat ⇔ Konvergenz .

Bemerkungen 9.6(a) Ein konsistentes LMV besitzt stets die Nullstelle ζ = 1 (vgl. (9.9)).

(b) Wir werden sehen, dass außer Nullstabilitat auch andere Stabilitatsbegriffebei AWAen von Bedeutung sind.

(c) Einschrittverfahren sind stets nullstabil.


Numerik II 128

9.7 Schrittweitensteuerung

Kein Verfahren zur Losung von AWAen arbeitet in der Praxis mit einerkonstanten Schrittweite. Man wird vielmehr versuchen, die Schrittweite andas Verhalten der Losung y anzupassen (andert sich y in einem Bereichschnell, so ist dort eine kleine Schrittweite angebracht; in Bereichen, indenen y kaum variiert, ist eine großere Schrittweite ausreichend). Wirwerden hier eine Schrittweitensteuerung vorstellen, die zum Ziel hat, denlokalen Diskretisierungsfehler Tn zu kontrollieren:

‖Tn‖ ∼ tol, n = 1, 2, . . . ,

mit einer vorgebenen Toleranz tol. Bei Systemen von DGen (insbesonderedann, wenn die Losungskomponenten von unterschiedlicher Großenord-nung sind) wird man fur jede Komponente eine eigene absolute Fehlertole-ranz und global eine relative Fehlertoleranz festsetzen.

9.7 Schrittweitensteuerung TU Bergakademie Freiberg, SS 2010

Numerik II 129

Satz 9.3 besagt, dass mit dem lokalen auch der (eigentlich interessierende)globale Diskretisierungsfehler kontrolliert wird.

Um den lokalen Diskretisierungsfehler zu schatzen verwendet man zweiMethoden unterschiedlicher Konsistenzordnungen (sagen wir p und q mitp < q), um yn aus yn−1 zu berechnen:

yn = yn−1 + hΦf (yn−1, tn−1;h) bzw. yn = yn−1 + hΦf (yn−1, tn−1;h)

Fur die zugehorigen lokalen Diskretisierungsfehler gelten:

Tn =y(tn)− y(tn−1)

h− Φf (y(tn−1), tn−1;h) = O(hp),

Tn =y(tn)− y(tn−1)

h− Φf (y(tn−1), tn−1;h) = O(hq).

Daraus folgt

Tn − Tn = Φf (yn−1, tn−1;h)− Φf (yn−1, tn−1;h) = 1h (yn − yn).


Numerik II 130

Wegen Tn − Tn = Tn(1 +O(hq−p)) ∼ Tn erhalten wir aus

1h‖yn − yn‖ ∼ ‖Tn‖

eine (grobe) Schatzung fur ‖Tn‖.

Ist 1h‖yn − yn‖ > tol, so wird die Schrittweite h verworfen und mit(

h

h

)p= α

h tol

‖yn − yn‖(∗)

eine neue Schrittweite h bestimmt.Die Wahl von h motiviert sich folgendermaßen:

benutzte Schrittweite h: 1h‖yn − yn‖ ∼ ‖Tn‖ = chp +O(hp+1) ∼ chp,

erwunschte Schrittweite h: tol = ‖Tn‖ = chp +O(hp+1) ∼ chp.

(α ist hier ein Sicherheitsfaktor, etwa α = 0.9).


Numerik II 131

Ausgehend von yn−1 werden jetzt neue Naherungen yn und yn (an derStelle tn−1 + h) berechnet. Diesen Prozess wiederholt man solange, bis1h‖yn − yn‖ ≤ tol erfullt ist. Dann wird (∗) verwendet, um eine neue(großere) Schrittweite fur den nachsten Schritt (n→ n+ 1) vorzuschlagen.

Um den Aufwand in Grenzen zu halten, verwendet man zur Berechnungvon yn und yn zwei RKV (verschiedener Ordnungen), deren Butcher-Tableaus sich nur in b unterscheiden (d.h. A und c sind gleich, so dass diekj nur einmal berechnet werden mussen). Man spricht von eingebettetenRKV und schreibt

c A

b>

b>

z.B.

0 0 0

1 0 0

1 0

1/2 1/2

.

Hier wird das Euler-Verfahren (p = 1) in das verbesserte Euler-Verfahren(p = 2) eingebettet.


Numerik II 132

Ein populares Beispiel ist die Fehlberg 4(5)-Formel:

0 0 0 0 0 0 014

14 0 0 0 0 0

38

332

932 0 0 0 0

1213

19322197 − 7200

219772962197 0 0 0

1 439216 −8 3680

513 − 8454104 0 0

12 − 8

27 2 − 35442565

18594104 − 11

40 025216 0 1408

256521974104 − 1

5 016135 0 6656

128252856156430 − 9

50255

Hier werden zwei sechsstufige RKV der Ordnungen 4 bzw. 5 kombiniert.


Numerik II 133

Ein weiteres Beispiel ist die Dormand-Prince 4(5)-Formel:

0 0 0 0 0 0 0 015

15 0 0 0 0 0 0

310

340

940 0 0 0 0 0

45

4445 − 56

15329 0 0 0 0

89

193726561 − 25360

2187644486561 − 212

729 0 0 0

1 90173168 − 355

33467325247

49176 − 5103

18656 0 0

1 35384 0 500

1113125192 − 2187

67841184 0

35384 0 500

1113125192 − 2187

67841184 0

517957600 0 7571

16695393640 − 92097

3392001872100

140

Hier wird ein sechsstufiges RKV der Ordnung 4 in ein siebenstufiges derOrdnung 5 eingebettet.


Documents

9 Numerische Verfahren fur¨ Anfangswertauf- gabenernst/Lehre/Numerik_II/Folien/...9.3 Runge-Kutta-Verfahren 9.4 Lineare Mehrschrittverfahren 9.5 Konvergenz von Einschrittverfahren