v1.6 – Mehrschrittverfahren

 

1.6.1 Definition und Konvergenz

1.6.1.1 Nachteile von Einschrittverfahren

Einschrittverfahren haben gewisse Nachteile:

  • hohe Anzahl von Funktionsauswertungen, die man für eine hohe Konsistenzordnung benötigt
  • Funktionswertauswertungen aus einem früheren Schritt werden nicht mehrmals benutzt.

Abhilfe bringen Mehrschrittverfahren. Wir gehen hier nur auf Verfahren konstanter Schrittweite ein.

1.6.1.2 r-Schritt-Verfahren

Bei einem r-Schritt-Verfahren werden zur Berechnung von {u_{k+1}} die bereits berechneten Größen {u_k},{u_{k-1}}, \ldots ,{u_{k-r+1}} verwendet. Sie haben die allgemeine Form

{u_{k+1}}+{\alpha _{r-1}}{u_k}+ \ldots +{\alpha _0}{u_{k-r+1}} = \tau \left[ {{\beta _r}f\left( {{t_{k+1}},{u_{k+1}}} \right)+ \ldots +{\beta _0}f\left( {{t_{k-r+1}},{u_{k-r+1}}} \right)} \right]

bzw.

{u_{k+1}}+\sum\limits_{i = 0}^{r-1} {{\alpha _{r-1-i}}{u_{k-i}}} = \tau \sum\limits_{i = -1}^{r-1} {{\beta _{r-1-i}}f\left( {{t_{k-i}},{u_{k-i}}} \right)}

mit {\left| {{\alpha _0}} \right|^2}+{\left| {{\beta _0}} \right|^2} > 0. Für {\beta _r} = 0 ist das Verfahren explizit, sonst implizit.

1.6.1.3 Anlaufrechnung

Für k = 0, \ldots ,r-2 muss man sich zunächst Startwerte verschaffen, z.B. mit einem Einschrittverfahren.

1.6.1.4 Konsistenzfehler

Der Konsistenzfehler ist definiert durch

{\ell _\tau }\left( {{t_k}} \right) = \frac{1}{\tau }\left( {y\left( {{t_{k+1}}} \right)+\sum\limits_{i = 0}^{r-1} {{\alpha _{r-1-i}}y\left( {{t_{k-i}}} \right)} } \right)-\sum\limits_{i = -1}^{r-1} {{\beta _{r-1-i}}f\left( {{t_{k-i}},y\left( {{t_{k-i}}} \right)} \right)}

1.6.1.5 Konvergenz

Mehrschrittverfahren, die mit der Ordnung p konsistent sind, sind auch mit der Ordnung p konvergent, falls sie nullstabil sind.

1.6.1.6 Nullstabilität

Nullstabilität sichert, dass sich Fehler in den Startwerten und Rundungsfehler nicht aufschaukeln. Wesentliches Merkmal ist die Betrachtung des Grenzprozesses \tau \to 0, also der Differentialgleichung

{u_{k+1}}+{\alpha _{r-1}}{u_k}+ \ldots +{\alpha _0}{u_{k-r+1}} = 0

mit dem ersten charakteristischen Polynom

\psi \left( \mu \right): = {\mu ^r}+{\alpha _{r-1}}{\mu ^{r-1}}+ \ldots +{\alpha _0}

Nullstabilität ist über die folgenden beiden Eigenschaften definiert:

  • \psi \left( \lambda \right) = 0\quad \Rightarrow \quad \left| \lambda \right| \leq 1
  • \psi \left( \lambda \right) = 0\quad \wedge \quad \left| \lambda \right| = 1\quad \Rightarrow \quad \lambda ist einfache Nullstelle von \psi

Es muss also gelten: \mathop {\lim }\limits_{n \to \infty } \frac{{{u_n}}}{n} = 0

1.6.2 Adams-Bashforth-Verfahren

1.6.2.1 Definition und Nullstabilität

Es gilt:

y\left( {{t_{k+1}}} \right)-y\left( {{t_k}} \right) = \int_{{t_k}}^{{t_{k+1}}} {\dot y\left( t \right)dt} = \int_{{t_k}}^{{t_{k+1}}} {f\left( {t,y\left( t \right)} \right)dt}

also

y\left( {{t_{k+1}}} \right) = y\left( {{t_k}} \right)+\int_{{t_k}}^{{t_{k+1}}} {\underbrace {f\left( {t,y\left( t \right)} \right)}_{ = :F\left( t \right)}dt}

Ersetzen wir das nicht an jeder Stelle bekannte F\left( t \right) durch ein Interpolationspolynom {P_{r-1}}\left( t \right) mit den r Stützstellen {t_k},{t_{k-1}}, \ldots ,{t_{k-r+1}} und integrieren dieses, dann erhalten wir daraus ein r-Schritt-Verfahren vom Adams-Bashforth-Typ:

{u_{k+1}} = {u_k}+\tau \left[ {{\beta _{r-1}}f\left( {{t_k},{u_k}} \right)+ \ldots +{\beta _0}f\left( {{t_{k-r+1}},{u_{k-r+1}}} \right)} \right]

num-106-adams-bashforth-interpolation-integration

Adams-Bashforth-Verfahren sind explizite r-Schritt-Verfahren mit Konsistenzordnung r.

Nullstabilität:

\tau \to 0\quad \Rightarrow \quad {u_{k+1}} = {u_k}\quad \Rightarrow \quad {u_{k+1}}-{u_k} = 0\quad \Rightarrow \quad \lambda -1 = 0\quad \Rightarrow \quad \lambda = 1

Da \lambda = 1 eine einfache Nullstelle ist, ist das Adams-Bashforth-Verfahren nullstabil.

1.6.2.2 Beispiel r=1

Die Interpolation erfolgt mit r Stützstellen. Wir haben also hier nur eine Stützstelle, das Polynom ergibt sich als konstante Funktion (Polynom r-1 = 0-ten Grades) mit dem Wert der Stützstelle f\left( {{t_k},{u_k}} \right).

Es folgt:

\int_{{t_k}}^{{t_{k+1}}} {f\left( {{t_k},{u_k}} \right)dt} = \tau f\left( {{t_k},{u_k}} \right)

{u_{k+1}} = {u_k}+\tau f\left( {{t_k},{u_k}} \right)

Dies entspricht dem expliziten Eulerverfahren.

1.6.2.3 Beispiel r=2

Hier haben wir zwei Stützstellen für die Interpolation. Es ergibt sich eine Geradengleichung. Das daraus folgende Adams-Bashforth-Verfahren lautet:

{u_{k+1}} = {u_k}+\frac{3}{2}\tau f\left( {{t_k},{u_k}} \right)-\frac{1}{2}\tau f\left( {{t_{k-1}},{u_{k-1}}} \right)

1.6.3 Adams-Moulton-Verfahren

Analog zu den Adams-Bashforth-Verfahren ersetzt man F\left( t \right) = f\left( {t,y\left( t \right)} \right) durch ein Interpolationspolynom, hier allerdings {P_r}\left( t \right) vom Grad r mit den r+1 Stützstellen {t_{k+1}},{t_k},{t_{k-1}}, \ldots ,{t_{k-r+1}}. Adams-Moulton-Verfahren sind implizite r-Schritt-Verfahren

{u_{k+1}} = {u_k}+\tau \left[ {{\beta _r}f\left( {{t_{k+1}},{u_{k+1}}} \right)+ \ldots +{\beta _0}f\left( {{t_{k-r+1}},{u_{k-r+1}}} \right)} \right]

mit Konsistenzordnung r+1.

num-106-adams-moulton-interpolation-integration

Zur Berechnung von {u_{k+1}} muss eine Gleichung bzw. ein Gleichungssystem gelöst werden. Es bietet sich eine Fixpunktiteration an, da die Gleichung bereits in Fixpunktform ist. Einen guten Startwert verschafft man sich durch ein explizites Verfahren, z.B. vom Adams-Bashforth-Typ.

Für r = 1 ergibt sich die Trapezregel:

{P_1}\left( t \right) = \frac{1}{\tau }\left[ {\left( {t-{t_k}} \right){f_{k+1}}-\left( {t-{t_{k+1}}} \right){f_k}} \right]

\int_{{t_k}}^{{t_{k+1}}} {{P_1}\left( t \right)dt} = \frac{1}{\tau }\int_{{t_k}}^{{t_{k+1}}} {\left( {t-{t_k}} \right)dt} \cdot {f_{k+1}}-\frac{1}{\tau }\int_{{t_k}}^{{t_{k+1}}} {\left( {t-{t_{k+1}}} \right)dt} \cdot {f_k} = \frac{\tau }{2}\left( {{f_{k+1}}+{f_k}} \right)

{u_{k+1}} = {u_k}+\frac{\tau }{2}\left[ {f\left( {{t_{k+1}},{u_{k+1}}} \right)+f\left( {{t_k},{u_k}} \right)} \right]

Nullstabilität:

{u_{k+1}} = {u_k}\quad \Rightarrow \quad siehe Adams-Bashforth-Verfahren

A-Stabilität (\tau \ne 0, Dahlquistsche Testgleichung einsetzen, z = \tau \lambda, char. Polynom):

{u_{k+1}}-{u_k}-\frac{\tau }{2}\left[ {f\left( {{t_{k+1}},{u_{k+1}}} \right)+f\left( {{t_k},{u_k}} \right)} \right] = 0

\quad \Rightarrow \quad {u_{k+1}}-{u_k}-\frac{\tau }{2}\left[ {\lambda {u_{k+1}}+\lambda {u_k}} \right] = 0

\quad \Rightarrow \quad {u_{k+1}}-{u_k}-\frac{{\tau \lambda }}{2}{u_{k+1}}-\frac{{\tau \lambda }}{2}{u_k} = 0

\quad \Rightarrow \quad \left( {1-\frac{z}{2}} \right){u_{k+1}}-\left( {1+\frac{z}{2}} \right){u_k} = 0

\quad \Rightarrow \quad \lambda = \frac{{1+\frac{z}{2}}}{{1-\frac{z}{2}}}

Aus \left| \lambda \right| < 1 folgt:

\left| {\frac{{1+\frac{z}{2}}}{{1-\frac{z}{2}}}} \right| < 1\quad \Rightarrow \quad \operatorname{Re} \left\{ z \right\} < 0

Das Verfahren ist also unbedingt absolut stabil.

1.6.4 Nyström- und Milne-Simpson-Verfahren

Mit der Formel

y\left( {{t_{k+1}}} \right) = y\left( {{t_{k-1}}} \right)+\int_{{t_{k-1}}}^{{t_{k+1}}} {f\left( {t,y\left( t \right)} \right)dt}

und der Interpolationsidee f\left( {t,y\left( t \right)} \right) \approx {P_r}\left( t \right) erhält man die expliziten Nyströmverfahren:

num-106-nystrom-verfahren-interpolation-integration

Analog ergeben sich die impliziten Milne-Simpson-Verfahren:

num-106-milne-simpson-interpolation-integration

Ein explizites Zweischrittverfahren nach Nyström ist die Mittelpunktregel:

{u_{k+1}} = {u_{k-1}}+2\tau f\left( {{t_k},{u_k}} \right)

Dabei ist das Integrationsgebiet größer als das Interpolationsgebiet!

Nullstabilität:

{u_{k+1}} = {u_{k-1}}\quad \Rightarrow \quad {\lambda ^2} = 1\quad \Rightarrow \quad {\lambda _1} = 1,\quad {\lambda _2} = -1

Es handelt sich um zwei einfache Nullstellen, die Nullstabilität ist also gegeben.

Absolute Stabilität:

{u_{k+1}} = 2\tau \lambda {u_k}+{u_{k-1}}

{\lambda ^2}-2z\lambda -1 = 0

{\lambda _{1,2}} = z \pm \sqrt {z+1}

z+\sqrt {z+1} < 1\quad \wedge \quad z-\sqrt {z+1} < 1

Dies scheint auf den ersten Blick nicht erfüllbar zu sein. Für z = iy,\quad y \in \left( {-\sqrt 3 ,\sqrt 3 } \right) ergibt sich aber \left| {{\lambda _1}} \right| = 1 = \left| {{\lambda _2}} \right|.

Ein implizites Zweischrittverfahren nach Milne-Simpson ist die Keplersche Fassregel:

{u_{k+1}} = {u_{k-1}}+\frac{\tau }{3}\left[ {f\left( {{t_{k-1}},{u_{k-1}}} \right)+4f\left( {{t_k},{u_k}} \right)+f\left( {{t_{k+1}},{u_{k+1}}} \right)} \right]

1.6.5 BDF-Verfahren

Sei {P_r}\left( t \right) das Interpolationspolynom von y\left( t \right) bezüglich der Stützstellen {t_{k+1}},{t_k},{t_{k-1}}, \ldots ,{t_{k-r+1}}. Approximiert man die linke Seite der Gleichung

\dot y\left( {{t_{k+1}}} \right) = f\left( {{t_{k+1}},y\left( {{t_{k+1}}} \right)} \right)

durch {\dot P_r}\left( {{t_{k+1}}} \right) und ersetzt y\left( {{t_j}} \right) durch {u_j}, ergeben sich die impliziten BDF (backward differentiation formulae), die besonders für steife Differentialgleichungen geeignet sind.

Für r = 1 ergibt sich

{P_1}\left( t \right) = y\left( {{t_k}} \right)+\frac{{t-{t_k}}}{\tau }\left[ {y\left( {{t_{k+1}}} \right)-y\left( {{t_k}} \right)} \right]

{{\dot P}_1}\left( t \right) = \frac{1}{\tau }\left[ {y\left( {{t_{k+1}}} \right)-y\left( {{t_k}} \right)} \right]

und damit das implizite Eulerverfahren

\frac{1}{\tau }\left[ {{u_{k+1}}-{u_k}} \right] = f\left( {{t_{k+1}},{u_{k+1}}} \right)

Für r = 2 ergibt sich das BDF2-Verfahren:

{P_2}\left( t \right) = y\left( {{t_{k-1}}} \right)\frac{{\left( {t-{t_k}} \right)\left( {t-{t_{k+1}}} \right)}}{{2{\tau ^2}}}-y\left( {{t_k}} \right)\frac{{\left( {t-{t_{k-1}}} \right)\left( {t-{t_{k+1}}} \right)}}{{{\tau ^2}}}+y\left( {{t_{k+1}}} \right)\frac{{\left( {t-{t_{k-1}}} \right)\left( {t-{t_k}} \right)}}{{2{\tau ^2}}}

{{\dot P}_2}\left( t \right) = y\left( {{t_{k-1}}} \right)\frac{{\left( {t-{t_k}} \right)+\left( {t-{t_{k+1}}} \right)}}{{2{\tau ^2}}}-y\left( {{t_k}} \right)\frac{{\left( {t-{t_{k-1}}} \right)+\left( {t-{t_{k+1}}} \right)}}{{{\tau ^2}}}+y\left( {{t_{k+1}}} \right)\frac{{\left( {t-{t_{k-1}}} \right)+\left( {t-{t_k}} \right)}}{{2{\tau ^2}}}

{{\dot P}_2}\left( {{t_{k+1}}} \right) = y\left( {{t_{k-1}}} \right)\frac{{{t_{k+1}}-{t_k}}}{{2{\tau ^2}}}-y\left( {{t_k}} \right)\frac{{{t_{k+1}}-{t_{k-1}}}}{{{\tau ^2}}}+y\left( {{t_{k+1}}} \right)\frac{{\left( {{t_{k+1}}-{t_{k-1}}} \right)+\left( {{t_{k+1}}-{t_k}} \right)}}{{2{\tau ^2}}}

{{\dot P}_2}\left( {{t_{k+1}}} \right) = y\left( {{t_{k-1}}} \right)\frac{1}{{2\tau }}-y\left( {{t_k}} \right)\frac{2}{\tau }+y\left( {{t_{k+1}}} \right)\frac{3}{{2\tau }}

\quad \Rightarrow \quad \frac{3}{2}{u_{k+1}}-2{u_k}+\frac{1}{2}{u_{k-1}} = \tau f\left( {{t_{k+1}},{u_{k+1}}} \right)

Nullstabilität:

\frac{3}{2}{u_{k+1}}-2{u_k}+\frac{1}{2}{u_{k-1}} = 0

\quad \Rightarrow \quad {u_{k+1}}-\frac{4}{3}{u_k}+\frac{1}{3}{u_{k-1}} = 0

\quad \Rightarrow \quad {\lambda ^2}-\frac{4}{3}\lambda +\frac{1}{3} = 0

\quad \Rightarrow \quad {\lambda _1} = 1,\quad {\lambda _2} = \frac{1}{3}

Nullstabilität ist also gegeben.

1.6.6 Weitere Mehrschrittverfahren

Mit dem Ansatz

{u_{k+1}}+{\alpha _0}{u_k}+ \ldots +{\alpha _{r-1}}{u_{k-r+1}} = \tau \left[ {{\beta _0}f\left( {{t_{k+1}},{u_{k+1}}} \right)+ \ldots +{\beta _r}f\left( {{t_{k-r+1}},{u_{k-r+1}}} \right)} \right]

kann man allgemeine lineare Mehrschrittverfahren konstruieren. Zum Beispiel ist das Verfahren

{u_{k+1}}+4{u_k}-5{u_{k-1}} = \tau \left[ {4f\left( {{t_k},{u_k}} \right)+2f\left( {{t_{k-1}},{u_{k-1}}} \right)} \right]

explizit und von Konsistenzordnung 3. Es ist allerdings nicht nullstabil!

Eine Schrittweitensteuerung führt zu nichtäquidistanten Stützstellen {t_k}. Dann müssen die Koeffizienten des Verfahrens in jedem Zeitschritt neu berechnet werden. Man kombiniert das Verfahren dann noch mit einer adaptiven Steuerung der Ordnung des Verfahrens.

Ähnliche Artikel

1 Kommentar zu “v1.6 – Mehrschrittverfahren”

sehr schön!!!weiter so!

Kommentar verfassen