Fakult at Grundlagen April 2011 - Hochschule Esslingenmohr/praes/dgl_handout.pdf · 2011-04-20 · April 2011 Fakult at Grundlagen Di erenzialgleichungen. Grunds atzliches Einschrittverfahren

GrundsatzlichesEinschrittverfahren

Implizite Verfahren, StabilitatMehrschrittverfahren

Differenzialgleichungen

Fakultat Grundlagen

April 2011

Fakultat Grundlagen Differenzialgleichungen



Ubersicht

1 GrundsatzlichesProblemstellungRichtungsfeldBeispiel

2 EinschrittverfahrenEulerverfahrenHeunverfahrenRunge-Kutta-Verfahren

3 Implizite Verfahren, StabilitatImpizites EulerverfahrenStabilitatSchritweitensteuerung

4 Mehrschrittverfahren

Fakultat Grundlagen Differenzialgleichungen Folie: 2



ProblemstellungRichtungsfeldBeispiel

Definition

Anfangswertproblem einer Differentialgleichung erster Ordnung.

y ′ = f (x , y) , y(x0) = y0

Die rechte Seite der Differentialgleichung weist jedem Punkt desDefinitionsbereichs eine Steigung zu.

Der Grundgedanke fast aller numerischer Verfahren ist, die sichkontinuierlich andernde Steigung durch die Steigung(en) an einemoder mehreren diskreten Punkt(en) zu ersetzen.

Alle Numerischen Verfahren lassen sich auf vektorwertigeFunktionen ubertragen.





Richtungsfeld





Mathematisches Pendel

Die Differenzialgleichung des math-ematischen Pendels mit Anregungf (t) und Dampfung proportional zurGeschwindigkeit lautet:

x(t) + k · x(t) + sin(x(t)) = f (t)

Mit der Substitution y1(t) = x(t)und y2(t) = x(t) erhalt man aus derDifferentialgleichung 2. Ordnung einaquivalentes System von zwei Differ-entialgleichungen 1. Ordnung:

x

x

~G

~R

r

∣∣∣~R∣∣∣ =∣∣∣~G ∣∣∣ · sin x

y1 = x = y2

y2 = x = f (t)− k · y2 − sin(y1)





Mathematisches Pendel (vektoriell)

Pendel :

(y1

y2

)=

(y2

f (t)− k · y2 − sin(y1)

)Allgemein:

y(x) =

y1(x)...

yn(x)

, y′(x) =

y ′1(x)...

y ′n(x)

, f(x , y) =

f1(x , y)

.

.

.fn(x , y)

Vektorielle Form eines Differenzialgleichungssystems:

y′ = f(x , y) , y(x0) = y0




EulerverfahrenHeunverfahrenRunge-Kutta-Verfahren

Konstruktion des Eulerverfahrens

x

y

x0

y0

m0

y1

x0 + h︸︷︷︸x1

g0

m1

y2

x1 + h︸︷︷︸x2

y(x)

g1

m2

g2





Algorithmus des Eulerverfahrens

Steigungen der Geraden Rechenvorschrift

g0 : m0 = f (x0, y0) y1 = y0 + h · f (x0, y0)

g1 : m1 = f (x1, y1) y2 = y1 + h · f (x1, y1)

g2 : m2 = f (x2, y2) y3 = y2 + h·f (x2, y2)

......

......

...

x

y

x0 x1 x2

y0

y1

y2

g0

g1

g2

y(x)

Algorithmus

yn+1 = yn + h · f (xn, yn)xn+1 = xn + h





Konstruktion des Heunverfahrensy(x)

x0

y0

x

y

m0

x1

yE1

m1

yH1

Algorithmus

k1 = h · f (xn, yn)

k2 = h · f (xn + h, yn + k1)

yn+1 = yn + k1 + k22

xn+1 = xn + h

Beim Eulerverfahren wird die Steigung nur am Ausgangspunkt derjeweiligen Teilintervalle abgegriffen; Beim Heun-Verfahren wird miteine

”gemittelten“ Steigung die Naherungsgerade bestimmt.

Runge-Kutta-VerfahrenFakultat Grundlagen Differenzialgleichungen Folie: 9




Runge-Kutta-Verfahreny

x

x0 x0 + h2 x0 + h

m1 m2

m3

m4

y(x)

y0

yR1

k1 = h · f (xn, yn) ”Euler-Schritt“

k2 = h · f (xn + 12h, yn + 1

2k1)

k3 = h · f (xn + 12h, yn + 1

2k2)

k4 = h · f (xn + h, yn + k3)

yn+1 = yn + 16 [k1 + 2k2 + 2k3 + k4]

xn+1 = xn + h

mi = f (x?, y??)

Steigungen in der”Umgebung“ des vermuteten Kurvenverlaufs wer-

den ermittelt. Der eigentliche Rechenschritt wird dann mit einemgewichteten arithmetischen Mittel dieser Steigungen durchgefuhrt.





Vergleich: y ′ = 2 · (x − 15 ) · (y + 1

2 ), y( 15 ) = 1

2 ; xe = 1.2

exakt Runge-Kutta Heun Euler2.21828 2.21314 2.16087 1.75612

x

xex0

y0

yEe

yHe

yRe

y(x)y

Das Runge-Kutta-Verfahrenbenotigt pro Schritt vierFunktionsauswertungen,das Heun-Verfahren nurzwei, wahrend das Euler-Verfahren nur einmal dierechte Seite f (x , y)

auswerten muss.

Das Grundintervall wird deshalb zum Vergleich bei Runge-Kutta in zwei Teil-intervalle, bei Heun in vier Teilintervalle und bei Euler in acht Teilintervalleunterteilt, sodass jeweils acht Funktionsauswertungen notig sind.




Impizites EulerverfahrenStabilitatSchritweitensteuerung

Testgleichung: y ′ = λy ; y(0) = 1

Das Euler-Verfahrenlautet in diesem Fall:

yn+1 = yn + hf (xn, yn) = yn + hλyn = (1 + λh)yn

xn+1 = xn + h

Iteriert man den Algorithmus, so erhalt man: yn+1 = (1 + λh)n+1 · 1Ist λ > 0, so wachst die Losung y = eλx exponentiell an und dasNaherungsverfahren (Euler) ergibt qualitativ den richtigen Verlauf.Ist λ� 0, so klingt die exakte Losung exponentiell schnell ab. DieNaherungslosung klingt aber nur dann ab, wenn der Ausdruck (1 + λh)betragsmaßig kleiner 1 wird. Problematisch fur Re{λ} � 0 !!Wir wahlen nun die Stutzstelle y1 so, dass eine Gerade durch (x0 + h, y1)mit der Steigung f (x0 + h, y1) durch den Startpunkt (x0, y0) geht.

Impizites Eulerverfahren

yn+1 = yn + h · f (xn+1, yn+1)yn+1 = yn + h · λyn+1

xn+1 = xn + h

Testgleichung:yn+1 = yn + λyn+1

yn+1 = yn1− λ

yn+1 = y0

(1− λ)n+1

Ist λ� 0 so ist (1− hλ)� 1 und damit klingt die Naherungslosung ab.





Skizze: y ′ = λy fur λ = −2.13 ; h = 1

x

yeλx

y v2

y v1

y r2

y r1





Coulomb-Reibung

Probleme bereiten bereits relativ einfache mechanische Beispiele.

Dm

~GOszillator mit Coulomb-Reibung

mx = −Dx − a · sign(x) , D : Federkonstante a : Reibungskonstante

Beim Aufruf der Prozedur ode45 fur a = 0.3 zeigt sich, dass obigeDifferenzialgleichung damit nicht gelost werden kann. Fur sehr kleineGeschwindigkeiten mit wechselndem Vorzeichen ergeben sich große,zeitlich dicht aufeinanderfolgende Sprunge fur die Beschleunigung. DasRunge-Kutta-Verfahren kann dieses starke Abklingen und Anwachsen nurmit immer kleiner werdender Schrittweite nachvollziehen und

”frisst“ sich

schließlich fest. implizite DGL-LoserMATAB: coulombreibung.m, dgl ode vergleich.m





Stabilitat

Die Testgleichung y ′ = λy , y(0) = 1; λ ∈ IR heißt stabil, wenn y(t)fur t →∞ beschrankt bleibt, d. h. fur Re{λ} ≤ 0.

Die Naherungsfolgen{y0, y1, y2, y3, . . .}

explizites Eulerverfahren yn+1 = (1 + λh) · yn

implizites Eulerverfahren yn+1 = yn

(1− λh)

besitzen dasselbe Ab-klingverhalten, wenn

explizites Eulerverfahren∣∣(1 + λh)

∣∣ ≤ 1

implizites Eulerverfahren∣∣∣ 1(1− λh)

∣∣∣ ≤ 1

Wir bezeichnen die Bereiche,in denen diese Ungleichung giltals Stabilitatsbereich des Ver-fahrens. Mit der Abkurzungz = λh erhalt man:

explizit: |1 + z | ≤ 1

implizit: |1− z | ≥ 1

Explizites Eulerverfahren

1

−1 Re{z}

Im{z}

Implizites Eulerverfahren

Re{z}

Im{z}

1

1





Schrittweitensteuerung; Schatzung des Fehlers

Schatzung des lokalen Fehlers D

Parallelrechnen mit zwei verschiedenen Verfahren, derenFehlerordnung sich um 1 unterscheiden; nach jedem Schritt wird dieDifferenz der beiden Resultate gebildet.

Parallelrechnen mit halber Schrittweite. Die Differenz ergibt wiederden Parameter fur die Schrittweitensteuerung. Mit diesen beidenWerten wird dann noch ein Extrapolationsschritt durchgefuhrt.

Schatzung des relativen lokalen Fehlers l bei Verfahren der Ordnung p :

Dh ≈ l1 =

Y (p+1)(h)− Y (p)(h)h ; D

h ≈ l2 =Y (0.5 · h)− Y (h)

h ·(1− 2−p

)Ist ε die vorgegebene lokale Toleranz, so kann man nach dem folgendenKriterium verfahren.

Ist l ≤ ε, so wird die Schrittweite akzeptiert.

Andernfalls muss eine neue Schrittweite bestimmt werden.





Schrittweitenbestimmung h → hneu

Fur den lokalen Fehler D ergibt sich bei Vernachlassigung der Terme mitOrdnung m > p + 1 : D ≈ c · hp+1

Akzeptiert man einen lokalen Fehler der Große ε · h, dann ist zu erwarten,dass der globale Fehler die Großenordnung ε · (tend − t0) hat. Fur dieoptimale Schrittweite erhalt man daraus die Beziehung:

ε · hopt = c · hp+1opt

Nach Elimination der Konstante c aus den beiden Gleichungen erhaltenwir einen Schatzwert fur die optimale Schrittweite.

hopt = h ·(εl

) 1p

Bei konkreter Implementierung wird zusatzlich eine maximale und eineminimale Schrittweite hmax bzw. hmin vorgegeben. Unterschreitet dievorgeschlagene Schrittweite hmin, so ist eine Singularitat wahrscheinlich.

hneu = min(hmax, fV ·h, fS ·hopt)fS Sicherheitsfaktor mit fS < 1fV Skalierungsfaktor mit fV > 1




Integralgleichung

Ausgangspunkt: Formulierung als Integralgleichung

y(xk+1) = y(xk) +

xk+1∫xk

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

Bei Einschrittverfahren wird der nachste Naherungwert yk+1 nurausgehend von (xk |yk) bestimmt. So versucht z. B. das klassischeRunge-Kutta-Verfahren das Integral dadurch abzuschatzen, dass es anvier Stellen in der Nahe des vermuteten Kurvenverlaufs im Intervall[xk , xk+1] Steigungen abgreift und eine Durchschnittssteigung durch einegewichtete arithmetische Mittelung bestimmt.

Mehrschrittverfahren dagegen benutzen auch die vorhandene Information

uber f (x , y) an den vorhergehenden, aquidistanten Stutzstellen

(xk−1|yk−1), (xk−2|yk−2), . . . .




Extrapolation

Zur Approximation von f (x , y(x)) im Intervall [xk , xk+1] extrapoliertman f (x , y(x)) an den Stellen(xk |f (xk , yk)), (xk−1|f (xk−1, yk−1)), (xk−2|f (xk−2, yk−2)), (xk−3|f (xk−3, yk−3))mittels eines Polynomansatzes p3(x)

x

f

xk−3 xk−2 xk−1 xk xk+1

f (xk−3, yk−3)

f (xk−2, yk−2)

f (xk−1, yk−1)

f (xk , yk)f (xk+1, yk+1)




Adams-Bashforth

Integration uber Polynom:xk+1∫xk

f (x , y(x)) dx ≈xk+1∫xk

p3(x) dx

o. B. d. A. Stutzstellen (−2|fk−3), (−1|fk−2), (0|fk−1), (1|fk) (fn = f (xn, yn))

p3(x) = a0 + a1 · x + a2 · x2 + a3 · x3

Punktprobe ergibt ein lineares Gleichungssystem fur die Koeffizienten ai :

p3(1) = a0 + a1 + a2 + a3 = fkp3(0) = a0 = fk−1

p3(−1) = a0 − a1 + a2 − a3 = fk−2

p3(−2) = a0 − 2a1 + 4a2 − 8a3 = fk−3

a0 = fk−1

a1 = 16

[2fk − 3fk−1 − 6fk−2 + fk−3]

a2 = 12

[fk − 2fk−1 + fk−2]

a3 = 16

[fk − 3fk−1 + 3fk−2 − fk−3]2∫

1

p3(x)dx = a0 +3

2· a1 +

7

3· a2 +

15

4· a3 =

1

24· [55 · fk − 59 · fk−1 + 37 · fk−2 − 9 · fk−3]

yk+1 = yk + h24 ·

[55 · f (xk , yk )︸︷︷︸

fk

−59 · f (xk−1, yk−1)︸︷︷︸fk−1

+37 · f (xk−2, yk−2)︸︷︷︸fk−2

−9 · f (xk−3, yk−3)︸︷︷︸fk−3

]

benotigt eine Funktionsauswertung pro Schritt!


Documents

Fakult at Grundlagen April 2011 - Hochschule Esslingenmohr/praes/dgl_handout.pdf · 2011-04-20 · April 2011 Fakult at Grundlagen Di erenzialgleichungen. Grunds atzliches Einschrittverfahren