Schrittweitensteuerung

Schrittweitensteuerung ist eine Technik, die in der numerischen Mathematik bei Algorithmen angewendet werden kann, die ein kontinuierliches Problem durch Diskretisierung in einzelne Schritte lösen.

Verschiedene Problemklassen führen auf die Aufgabe eine Kurve $t\mapsto x(t)\in {ℝ}^d$ für ein gewisses $t$-Intervall in $ℝ$ zu konstruieren. Dazu gehören die Lösung eines Anfangswertproblems für gewöhnliche Differentialgleichungen und die Verfolgung einer Lösungskurve nichtlinearerer Gleichungssysteme mit Homotopieverfahren. Solche Probleme werden in der numerischen Mathematik oft mit Verfahren gelöst, die die Lösung nur schrittweise an einzelnen Punkten $t_0<t_1<t_2<\dots$ berechnen, also Näherungen $y_n\cong x(t_n),n=1,2,\dots$, wobei $y_0=x(t_0)$ als Anfangswert bekannt ist. Die verwendeten Schrittweiten nennt man $h_n=t_{n+1}-t_n,n\ge 0$. Typischerweise ist der Rechenaufwand für einen einzelnen Schritt i.w. konstant und der Fehler hängt ab von einer Potenz der Schrittweite, er hat die Form $c_n{h}_n^p$. Man steht dann vor der Frage, wie groß die Schrittweiten zu wählen sind, um eine gewünschte Genauigkeit insgesamt zu erreichen. Dabei ist zu beachten, dass die Vorfaktoren $c_n$ von der unbekannten Lösungskurve abhängen, insbesondere von ihren Ableitungen $x^{(q)},q\le p$, die Größenordnung dieser Vorfaktoren kann daher stark schwanken. Daher verwendet man bei modernen Algorithmen keine konstante Schrittweite $h_n\equiv h$. Die wichtigsten Argumente für eine Schrittweitensteuerung sind

• aus Effizienzgründen ist es sinnvoll bei kleinen Werten $c_n$ mit großen Schrittweiten und bei großen Werten $c_n$ mit kleinen zu arbeiten, um einen gleichmäßig kleinen Gesamtfehler mit möglichst wenigen Schritten zu erreichen.
• eine feste Schrittweite $h$ müsste sich nach der ungünstigsten Stelle mit dem größten $c_n$ richten und man würde in weniger kritischen Bereichen viel zu viele Schritte machen, was bei Anfangswertproblemen auch zu großen Rundungsfehlern in der Lösung führen kann.
• Schrittweitensteuerung ermöglicht die Programmierung automatischer, selbststeuernder Algorithmen.

Schrittweitensteuerung bei Anfangswertproblemen

Voraussetzung für eine Schrittweitensteuerung bei gewöhnlichen Anfangswertproblemen ist das Vorhandensein einer Fehlerschätzung für den lokalen Fehler. Solche Schätzungen kann man allgemein durch Richardson-Extrapolation bekommen, indem man einen Schritt mit den (Test-)Schrittweiten $h$ und $h/2$ durchführt und die beiden Näherungen vergleicht. Weniger Aufwand erfordern bei Runge-Kutta-Verfahren eingebettete Verfahren bzw. Verfahrenspaare, wobei man ausgehend von einer berechneten Näherung $y_n$ im nächsten Schritt zwei Näherungen $y_{n+1}$ und ${\hat{y}}_{n+1}$ unterschiedlicher Genauigkeit berechnet. Bei Mehrschrittverfahren kann man die Näherungen einer Prädiktor-Korrektor-Methode als Verfahrenspaar verwenden.

Mit einem solchen Verfahrenspaar ist die Differenz ${\hat{y}}_{n+1}-y_{n+1}$ eine Schätzung für den auftretenden lokalen Fehler. Zur Bestimmung der idealen Schrittweite betrachtet man mit der aktuellen Schrittweite $h_n$ die Bedingung

$\Vert {\hat{y}}_{n+1}-y_{n+1}\Vert =c_n{h}_n^p$

als Gleichung für den unbekannten Faktor $c_n$ und bestimmt dann damit die Schrittweite, welche eine vom Anwender vorgegebene Toleranz $ϵ$ genau einhalten würde, also mit $c_n{\hat{h}}^p=ϵ$:

$\hat{h}=h_n\cdot \sqrt[p]{fe},fe:=\frac{ϵ}{\Vert {\hat{y}}_{n+1}-y_{n+1}\Vert }.$

Da dieser Wert allerdings erst nach Durchführung des Schritts bekannt ist, geht man nach einem Trial-and-Error-Verfahren vor und nutzt die Schrittweite $\hat{h}$ nur in einer Wiederholung des Schrittes, wenn die Toleranz nicht eingehalten wurde, d. h. wenn der Fehlerquotient $fe<1$ war. Da Wiederholungen relativ teuer sind, ist man vorsichtig und benutzt einen kleineren Wert, etwa $H=0.9\hat{h}$. Außerdem begrenzt man den Schrittweitenfaktor nach oben und unten. Die Steuerung im Schritt ab $t_n$ hat daher mit einer ersten Schätzung $H$ folgenden Ablauf:

1. berechne die beiden Lösungen $y_{n+1},{\hat{y}}_{n+1}$ zur Schrittweite $H$ und damit den Fehlerquotienten $fe$,
2. berechne damit $\hat{h}=H\cdot \min \{2,\max \{0.2,0.9\sqrt[p]{fe}\}\},$
3. wenn $fe<1$, setze $H:=\hat{h}$, gehe nach 1,
4. wenn $fe\ge 1$ ist, setze $t_{n+1}:=t_n+H,n:=n+1,$ und $H:=\hat{h}$. Der nächste Schritt beginnt wieder mit Anweisung 1.

In Anweisung 3 wird also der aktuelle Versuch verworfen und der Schritt ab $t_n$ mit kleinerer Schrittweite wiederholt, während in Punkt 4 der Schritt akzeptiert wird und der nächste Integrationsschritt erfolgen kann. Eine Zusatzabfrage beendet das Verfahren am Ende des Lösungsintervalls. Dieses Verfahren steuert aber nur die lokalen Fehlerbeiträge und erwartet, dass der globale Fehler am Ende des Intervalls ungefähr in der gleichen Größenordnung liegt.

Schrittweitensteuerung bei Homotopieverfahren

Bei der Verfolgung der Lösungskurven nichtlinearerer Gleichungssysteme $F(x(t),t)=0$ mit Homotopieverfahren spielt eine Akkumulation von Fehlern keine Rolle, da man mit dem Newton-Verfahren die Kurve jederzeit wieder beliebig genau approximieren kann. Hier kommt es eher darauf an, möglichst schnell voranzukommen ohne die Kurve dabei zu verlieren oder auf einen Nachbarzweig zu wechseln. Zur Fehlerschätzung prüft man daher die Konvergenzgeschwindigkeit der Newton-Iteration.

Es sei jetzt $y(t_n)$ eine Näherung für $x(t_n)$, also mit kleinem Residuum $F(y(t_n),t_n)\cong 0$. Bei der einfachen Kurvenverfolgung stellen Homotopieverfahren einen Prädiktor bereit, der eine Startnäherung $y_0(t_n+H)$ für die unbekannte $x(t_n+H)$ berechnet. Mit $y_0(t_n+H)$ führt man zwei Newtonschritte durch, welche verbesserte Näherungen $y_1(t_n+H),y_2(t_n+H)$ berechnen. Die schnelle Konvergenz des Newton-Verfahrens wird mit dem Quotienten

$Q:=\frac{\Vert y_2(t_n+H)-y_1(t_n+H)\Vert }{\Vert y_1(t_n+H)-y_0(t_n+H)\Vert }$

der Differenzen überprüft. Mit einem kleinen Referenzwert $q\in [0.1,0.3]$ lautet eine einfache Schrittweitensteuerung hierfür so:

1. berechne $y_0(t_n+H),y_1(t_n+H),y_2(t_n+H)$ zur Schrittweite $H$
2. für $Q>q$ setze $H:=H/2$ und gehe zu Anweisung 1.
3. für $Q\le q$ akzeptiere $h_n:=H,y(t_{n+1}):=y_2(t_n+H)$, setze $n:=n+1$, beginne nächsten Schritt mit Anweisung 1.

Bei einer starken Unterschreitung der Referenzgröße $q$, z. B. für $Q\le q/4$, kann im Schritt 3 vor dem Sprung zu Anweisung 1 die Schrittweiten-Vorhersage für $h_{n+1}$ auch wieder vergrößert werden durch $H:=2H$.

Literatur

• Ernst Hairer, Gerhard Wanner: Solving Ordinary Differential Equations 1. Nonstiff Problems ISBN 3-540-56670-8
• K. Strehmel, R. Weiner, H. Podhaisky: Numerik gewöhnlicher Differentialgleichungen – Nichtsteife, steife und differential-algebraische Gleichungen. Springer Spektrum, 2012.
• E. L. Allgower, K. Georg: Introduction to numerical continuation methods. SIAM Philadelphia, 2003, ISBN 0-89871-544-X.
• Vorlage:Literatur