Schrittweitensteuerung

Grundidee und Nutzen

Schrittweitensteuerung ist eine Technik der numerischen Mathematik. Sie wird bei Algorithmen eingesetzt, die ein kontinuierliches Problem durch einzelne diskrete Schritte lösen. Typische Aufgaben sind, eine Kurve t\mapsto x(t)\in\mathbb {R} ^d auf einem t-Intervall zu konstruieren: etwa bei einem Anfangswertproblem für gewöhnliche Differentialgleichungen oder beim Verfolgen einer Lösungskurve nichtlinearer Gleichungssysteme mit Homotopieverfahren.

Die Verfahren berechnen die Lösung nur an Stützstellen t_0<t_1<t_2<\ldots. Dabei sind y_n\cong x(t_n), und der bekannte Anfangswert ist y_0=x(t_0). Die Schrittweite zwischen zwei Stützstellen lautet h_n=t_{n+1}-t_n für n\geq0.

Meist ist der Rechenaufwand eines Schritts im Wesentlichen konstant. Der Fehler hat jedoch typischerweise die Form c_nh_n^p. Der Faktor c_n hängt von der unbekannten Lösungskurve ab, insbesondere von ihren Ableitungen x^{(q)} mit q\leq p, und kann daher stark schwanken. Kleine c_n erlauben große, große c_n verlangen kleine Schritte.

Eine konstante Schrittweite h_n\equiv h müsste sich nach der ungünstigsten Stelle mit dem größten c_n richten. Dann würden in unkritischen Bereichen unnötig viele Schritte ausgeführt; bei Anfangswertproblemen können dadurch auch große Rundungsfehler entstehen. Adaptive Schrittweiten sollen deshalb einen gleichmäßig kleinen Gesamtfehler mit möglichst wenigen Schritten erreichen und automatische, selbststeuernde Algorithmen ermöglichen.

Steuerung bei Anfangswertproblemen

Für gewöhnliche Anfangswertprobleme braucht man eine Schätzung des lokalen Fehlers, also des Fehlers eines einzelnen Schritts. Diese lässt sich allgemein durch Richardson-Extrapolation gewinnen: Ein Schritt wird mit den Test-Schrittweiten h und h/2 berechnet, anschließend werden die Näherungen verglichen.

Bei Runge-Kutta-Verfahren sind eingebettete Verfahren oder Verfahrenspaare sparsamer. Aus einer Näherung y_n werden im nächsten Schritt zwei Näherungen y_{n+1} und \hat y_{n+1} unterschiedlicher Genauigkeit berechnet. Bei Mehrschrittverfahren können die Näherungen einer Prädiktor-Korrektor-Methode als Verfahrenspaar dienen. Die Differenz \hat y_{n+1}-y_{n+1} schätzt den lokalen Fehler.

Mit der aktuellen Schrittweite h_n wird \|\hat y_{n+1}-y_{n+1}\|=c_nh_n^p als Gleichung für c_n verwendet. Für die vom Anwender vorgegebene Toleranz \epsilon soll c_n\hat h^p=\epsilon gelten. Daraus folgt \hat h=h_n\cdot\sqrt[p]{fe},\qquad fe:=\frac{\epsilon}{\|\hat y_{n+1}-y_{n+1}\|}. Da \hat h erst nach dem Versuchsschritt bekannt ist, wird bei zu großem Fehler der Schritt wiederholt. Um Wiederholungen möglichst zu vermeiden, verwendet man vorsichtig etwa H=0.9\hat h und begrenzt die Änderung des Schrittweitenfaktors.

Für einen Schritt ab t_n wird zunächst mit der Schätzung H gerechnet und der Fehlerquotient fe bestimmt. Dann gilt \hat h=H\cdot\min\{2,\max\{0.2,0.9\sqrt[p]{fe}\}\}. Falls fe<1, wird der Versuch verworfen, H:=\hat h gesetzt und derselbe Schritt wiederholt. Falls fe\geq1, wird der Schritt akzeptiert: t_{n+1}:=t_n+H, n:=n+1 und H:=\hat h für den nächsten Schritt. Eine Zusatzabfrage beendet das Verfahren am Ende des Lösungsintervalls. Gesteuert werden nur lokale Fehlerbeiträge; erwartet wird, dass der globale Fehler am Intervallende ungefähr dieselbe Größenordnung besitzt.

Steuerung bei Homotopieverfahren

Homotopieverfahren verfolgen Lösungskurven nichtlinearer Gleichungssysteme F(x(t),t)=0. Anders als bei Anfangswertproblemen spielt die Ansammlung von Fehlern dabei keine Rolle: Mit dem Newton-Verfahren kann die Kurve jederzeit wieder beliebig genau approximiert werden. Entscheidend ist vielmehr, schnell voranzukommen, ohne die Kurve zu verlieren oder auf einen Nachbarzweig zu wechseln.

Aus einer Näherung y(t_n) mit kleinem Residuum F(y(t_n),t_n)\cong0 liefert die einfache Kurvenverfolgung für die Schrittweite H einen Prädiktor y_0(t_n+H). Ein Prädiktor ist eine Startnäherung für die noch unbekannte Lösung x(t_n+H). Zwei Newtonschritte erzeugen daraus y_1(t_n+H) und y_2(t_n+H). Die schnelle Konvergenz der Newton-Iteration wird durch Q:=\frac{\|y_2(t_n+H)-y_1(t_n+H)\|}{\|y_1(t_n+H)-y_0(t_n+H)\|} überprüft. Als Referenzwert dient ein kleines q\in[0.1,0.3].

Man berechnet zunächst y_0(t_n+H), y_1(t_n+H) und y_2(t_n+H). Bei Q>q ist die Konvergenz nicht ausreichend schnell; daher wird H:=H/2 gesetzt und der Versuch wiederholt. Bei Q\leq q wird der Schritt akzeptiert: h_n:=H, y(t_{n+1}):=y_2(t_n+H), n:=n+1; danach beginnt der nächste Schritt. Wird q deutlich unterschritten, beispielsweise bei Q\leq q/4, darf die Vorhersage für die nächste Schrittweite vor dem nächsten Versuch durch H:=2H vergrößert werden.