Schrittweitensteuerung

Schrittweitensteuerung i​st eine Technik, d​ie in d​er numerischen Mathematik b​ei Algorithmen angewendet werden kann, d​ie ein kontinuierliches Problem d​urch Diskretisierung i​n einzelne Schritte lösen.

Verschiedene Problemklassen führen auf die Aufgabe eine Kurve ${\displaystyle t\mapsto x(t)\in \mathbb {R} ^{d}}$ für ein gewisses ${\displaystyle t}$-Intervall in ${\displaystyle \mathbb {R} }$ 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 ${\displaystyle t_{0}<t_{1}<t_{2}<\ldots }$ berechnen, also Näherungen ${\displaystyle y_{n}\cong x(t_{n}),\,n=1,2,\ldots }$, wobei ${\displaystyle y_{0}=x(t_{0})}$ als Anfangswert bekannt ist. Die verwendeten Schrittweiten nennt man ${\displaystyle h_{n}=t_{n+1}-t_{n},\,n\geq 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 ${\displaystyle 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 ${\displaystyle c_{n}}$ von der unbekannten Lösungskurve abhängen, insbesondere von ihren Ableitungen ${\displaystyle x^{(q)},\,q\leq p}$, die Größenordnung dieser Vorfaktoren kann daher stark schwanken. Daher verwendet man bei modernen Algorithmen keine konstante Schrittweite ${\displaystyle h_{n}\equiv h}$. Die wichtigsten Argumente für eine Schrittweitensteuerung sind

• aus Effizienzgründen ist es sinnvoll bei kleinen Werten ${\displaystyle c_{n}}$ mit großen Schrittweiten und bei großen Werten ${\displaystyle c_{n}}$ mit kleinen zu arbeiten, um einen gleichmäßig kleinen Gesamtfehler mit möglichst wenigen Schritten zu erreichen.
• eine feste Schrittweite ${\displaystyle h}$ müsste sich nach der ungünstigsten Stelle mit dem größten ${\displaystyle 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 ${\displaystyle h}$ und ${\displaystyle 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 ${\displaystyle y_{n}}$ im nächsten Schritt zwei Näherungen ${\displaystyle y_{n+1}}$ und ${\displaystyle {\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 ${\displaystyle {\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 ${\displaystyle h_{n}}$ die Bedingung

${\displaystyle \|{\hat {y}}_{n+1}-y_{n+1}\|=c_{n}h_{n}^{p}}$

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

${\displaystyle {\hat {h}}=h_{n}\cdot {\sqrt[{p}]{fe}},\quad fe:={\frac {\epsilon }{\|{\hat {y}}_{n+1}-y_{n+1}\|}}.}$

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 ${\displaystyle {\hat {h}}}$ nur in einer Wiederholung des Schrittes, wenn die Toleranz nicht eingehalten wurde, d. h. wenn der Fehlerquotient ${\displaystyle fe<1}$ war. Da Wiederholungen relativ teuer sind, ist man vorsichtig und benutzt einen kleineren Wert, etwa ${\displaystyle H=0.9{\hat {h}}}$. Außerdem begrenzt man den Schrittweitenfaktor nach oben und unten. Die Steuerung im Schritt ab ${\displaystyle t_{n}}$ hat daher mit einer ersten Schätzung ${\displaystyle H}$ folgenden Ablauf:

1. berechne die beiden Lösungen ${\displaystyle y_{n+1},{\hat {y}}_{n+1}}$ zur Schrittweite ${\displaystyle H}$ und damit den Fehlerquotienten ${\displaystyle fe}$,
2. berechne damit ${\displaystyle {\hat {h}}=H\cdot \min\{2,\max\{0.2,0.9{\sqrt[{p}]{fe}}\}\},}$
3. wenn ${\displaystyle fe<1}$, setze ${\displaystyle H:={\hat {h}}}$, gehe nach 1,
4. wenn ${\displaystyle fe\geq 1}$ ist, setze ${\displaystyle t_{n+1}:=t_{n}+H,\,n:=n+1,}$ und ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle F{\big (}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 ${\displaystyle y(t_{n})}$ eine Näherung für ${\displaystyle x(t_{n})}$, also mit kleinem Residuum ${\displaystyle F{\big (}y(t_{n}),t_{n})\cong 0}$. Bei der einfachen Kurvenverfolgung stellen Homotopieverfahren einen Prädiktor bereit, der eine Startnäherung ${\displaystyle y_{0}(t_{n}+H)}$ für die unbekannte ${\displaystyle x(t_{n}+H)}$ berechnet. Mit ${\displaystyle y_{0}(t_{n}+H)}$ führt man zwei Newtonschritte durch, welche verbesserte Näherungen ${\displaystyle y_{1}(t_{n}+H),y_{2}(t_{n}+H)}$ berechnen. Die schnelle Konvergenz des Newton-Verfahrens wird mit dem Quotienten

${\displaystyle Q:={\frac {\|y_{2}(t_{n}+H)-y_{1}(t_{n}+H)\|}{\|y_{1}(t_{n}+H)-y_{0}(t_{n}+H)\|}}}$

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

1. berechne ${\displaystyle y_{0}(t_{n}+H),y_{1}(t_{n}+H),y_{2}(t_{n}+H)}$ zur Schrittweite ${\displaystyle H}$
2. für ${\displaystyle Q>q}$ setze ${\displaystyle H:=H/2}$ und gehe zu Anweisung 1.
3. für ${\displaystyle Q\leq q}$ akzeptiere ${\displaystyle h_{n}:=H,\,y(t_{n+1}):=y_{2}(t_{n}+H)}$, setze ${\displaystyle n:=n+1}$, beginne nächsten Schritt mit Anweisung 1.

Bei einer starken Unterschreitung der Referenzgröße ${\displaystyle q}$, z. B. für ${\displaystyle Q\leq q/4}$, kann im Schritt 3 vor dem Sprung zu Anweisung 1 die Schrittweiten-Vorhersage für ${\displaystyle h_{n+1}}$ auch wieder vergrößert werden durch ${\displaystyle 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.
• Schwetlick, H. und Kretschmar, H.: Numerische Verfahren für Naturwissenschaftler und Ingenieure. Fachbuchverlag Leipzig, 1991, ISBN 3-343-00580-0, S. 200.