02.2 – adaptive Schrittweitensteuerung

 

a )

Wiederholen Sie den Algorithmus zur Schrittweitensteuerung aus der Vorlesung

b )

Als Verfahren höherer Ordnung soll das klassische Runge-Kutta-Verfahren

\begin{array}{*{20}{c}}{1/2} &\vline & {1/2} & {} & {} & {} \\{1/2} &\vline & 0 & {1/2} & {} & {} \\  1 &\vline & 0 & 0 & 1 & {} \\ \hline{} &\vline & {1/6} & {1/3} & {1/3} & {1/6} \\  \end{array}

verwendet werden. Ist es möglich, ein eingebettetes 4-stufiges Verfahren der Ordnung 3 zu konstruieren?

c )

Konstruieren Sie ein eingebettetes 5-stufiges Verfahren der Ordnung 3 in der Form

\begin{array}{*{20}{c}}{1/2} &\vline & {1/2} & {} & {} & {} & {} \\{1/2} &\vline & 0 & {1/2} & {} & {} & {} \\  1 &\vline & 0 & 0 & 1 & {} & {} \\{{\gamma _5}} &\vline & {{{\tilde \beta }_{5,1}}} & {{{\tilde \beta }_{5,2}}} & {{{\tilde \beta }_{5,3}}} & {{{\tilde \beta }_{5,4}}} & {} \\ \hline{} &\vline & {1/6} & {1/3} & {1/3} & {1/6} & {} \\{} &\vline & {{{\tilde \beta }_1}} & {{{\tilde \beta }_2}} & {{{\tilde \beta }_3}} & {{{\tilde \beta }_4}} & {{{\tilde \beta }_5}} \\  \end{array}

so dass der zusätzliche Aufwand durch die 5. Stufe nicht ins Gewicht fällt. Wie kann man den Aufwand im Algorithmus aus a) durch geschickte Wahl der Gewichte {\tilde \beta _i},\:\:i = 1, \ldots ,5, verringern?

Lösung

a )

Die lokale Schrittweite muss einerseits möglichst groß sein, um Rechenaufwand zu sparen. Andererseits muss sie klein genug sein, um den Fehler klein zu halten.

Erschwerend kommt bei der Wahl der lokalen Schrittweite hinzu, dass der lokale Fehler oft stark schwankt.

Der Ausweg liegt in einer adaptiven Schrittweitensteuerung. Das Ziel ist dabei, die Schrittweite so anzupassen, dass der lokale Fehler in jedem schritt etwa gleich einer vorgegebenen Größe \varepsilon ist.

b )

Ordnungsbedingungen für p = 3:

{\beta _1}+{\beta _2}+{\beta _3}+{\beta _4} = 1

{\beta _2}{\gamma _2}+{\beta _3}{\gamma _3}+{\beta _4}{\gamma _4} = \frac{1}{2}\quad \Rightarrow \quad \frac{1}{2}{\beta _2}+\frac{1}{2}{\beta _3}+\frac{1}{2}{\beta _4} = \frac{1}{2}

{\beta _2}\gamma _2^2+{\beta _3}\gamma _3^2+{\beta _4}\gamma _4^2 = \frac{1}{3}\quad \Rightarrow \quad \frac{1}{4}{\beta _2}+\frac{1}{4}{\beta _3}+{\beta _4} = \frac{1}{3}

{\beta _3}{\beta _{32}}{\gamma _2}+{\beta _4}{\beta _{43}}{\gamma _3} = \frac{1}{6}\quad \Rightarrow \quad \frac{1}{2} \cdot \frac{1}{2}{\beta _3}+1 \cdot \frac{1}{2} \cdot {\beta _4} = \frac{1}{6}

Dies können wir in einem Gleichungssystem zusammenfassen:

\left( {\begin{array}{*{20}{c}}  1 & 1 & 1 & 1 \\  0 & {\frac{1}{2}} & {\frac{1}{2}} & 1 \\  0 & {\frac{1}{4}} & {\frac{1}{4}} & 1 \\  0 & 0 & {\frac{1}{4}} & {\frac{1}{2}} \\  \end{array} } \right)\left( {\begin{array}{*{20}{c}}{{\beta _1}} \\{{\beta _2}} \\{{\beta _3}} \\{{\beta _4}} \\  \end{array} } \right) = \left( {\begin{array}{*{20}{c}}  1 \\{\frac{1}{2}} \\{\frac{1}{3}} \\{\frac{1}{6}} \\  \end{array} } \right)

Die einzige Lösung dieses Gleichungssystems ist:

{\beta _1} = \frac{1}{6},\quad {\beta _2} = \frac{1}{3},\quad {\beta _3} = \frac{1}{3},\quad {\beta _4} = \frac{1}{6}

Wir können also kein eingebettetes 4-stufiges Runge-Kutta-Verfahren der Ordnung 3 konstruieren, da wir wieder das klassische Runge-Kutta-Verfahren erhalten.

c )

Da ein vierstufiges Verfahren nicht möglich war, möchten wir nun ein 5-stufiges Verfahren konstruieren. Die zusätzlichen Freiheitsgrade sollten ausreichen, ein Verfahren 3. Ordnung zu erhalten.

Damit der Mehraufwand durch diese 5. Stufe nicht ins Gewicht fällt, werden die Koeffizienten so bestimmt, dass {f_{1,k+1}} = {f_{5,k}}. Das bedeutet, dass die zusätzliche Stufe wieder verwendet wird (sog. “Fehlberg-Trick”, auch FSAL-Technik (First Same As Last) genannt).

{f_{5,k}} = f\left( {{t_k}+{\gamma _5}\tau ,\:{u_k}+\tau \sum\limits_{s = 1}^4 {{{\tilde \beta }_{5,s}}{f_{5,k}}} } \right)

{f_{1,k+1}} = f\left( {\underbrace {{t_k}+\tau }_{ = {t_{k+1}}},\:\underbrace {{u_k}+\tau \:\sum\limits_{i = 1}^4 {{\beta _i}{f_{i,k}}} }_{ = {u_{k+1}}}} \right)

Daraus folgt:

{t_k}+{\gamma _5}\tau = {t_k}+\tau \quad \Rightarrow \quad {\gamma _5} = 1

{{\tilde \beta }_{5,s}} = {\beta _s}\quad \quad s = 1, \ldots ,4

Wenn wir nun wieder alle Bedingungen in ein Gleichungssystem schreiben, hat dieses keine eindeutige Lösung. Wir können also unendlich viele mögliche Verfahren konstruieren. Wir wollen nun eine “besonders geschickte” Möglichkeit wählen.

\sum\limits_{i = 1}^5 {{{\tilde \beta }_i}} = 1,\quad \quad \sum\limits_{i = 1}^5 {{{\tilde \beta }_i}\gamma _i^2} = \frac{1}{3},\quad \quad \sum\limits_{i = 1}^5 {{{\tilde \beta }_i}} {\gamma _i} = \frac{1}{2},\quad \quad \sum\limits_{i = 1}^5 {\sum\limits_{j = 1}^5 {{{\tilde \beta }_i}{\beta _{i,j}}{c_j}} } = \frac{1}{6}

Beispiel:

\begin{array}{*{20}{c}}{1/2} &\vline & {1/2} & {} & {} & {} & {} \\{1/2} &\vline & 0 & {1/2} & {} & {} & {} \\  1 &\vline & 0 & 0 & 1 & {} & {} \\  1 &\vline & {1/6} & {1/3} & {1/3} & {1/6} & {} \\ \hline{} &\vline & {1/6} & {1/3} & {1/3} & {1/6} & 0 \\{} &\vline & {1/6} & {1/3} & {1/3} & 0 & {1/6} \\  \end{array}

Daraus ergibt sich:

\quad \Rightarrow \quad {f_{i,k}} = {{\tilde f}_{i,k}}\quad \quad i = 1, \ldots ,4

\quad \Rightarrow \quad {{\tilde u}_{k+1}}-{u_{k+1}} = {u_k}+\tau \sum\limits_{i = 1}^5 {{{\tilde \beta }_i}{{\tilde f}_{i,k+1}}} -\left( {{u_k}+\tau \sum\limits_{i = 1}^4 {{{\tilde \beta }_i}{{\tilde f}_{i,k+1}}} } \right)

\quad \Rightarrow \quad {{\tilde u}_{k+1}}-{u_{k+1}} = \tau \left( {{{\tilde \beta }_5}{{\tilde f}_{5,k+1}}-{\beta _4}{f_{4,k+1}}} \right)

\quad \Rightarrow \quad {{\tilde u}_{k+1}}-{u_{k+1}} = \tau \left( {\frac{1}{6}{f_{1,k+1}}-\frac{1}{6}{f_{4,k+1}}} \right)

Die Werte für {\tilde u_{k+1}} bzw. \tilde f müssen also nicht explizit berechnet werden.