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\R^d$ für ein gewisses -Intervall in $\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 $t_0<t_1<t_2<\ldots$ berechnen, also Näherungen $y_n\cong x(t_n),\,n=1,2,\ldots$ , wobei y_0=x(t_0) als Anfangswert bekannt ist. Die verwendeten Schrittweiten nennt man $h_n=t_{n+1}-t_n,\,n\ge0$ . 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_nh_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 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 und h/2 durchführt und die beiden Näherungen vergleicht. Weniger Aufwand erfordern bei Runge-Kutta-Verfahren eingebette 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

$\|\hat y_{n+1}-y_{n+1}\|=c_nh_n^p$

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

${\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 $\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 folgenden Ablauf:

berechne die beiden Lösungen $y_{n+1},\hat y_{n+1}$ zur Schrittweite und damit den Fehlerquotienten ,
berechne damit $\hat h=H\cdot\min\{2,\max\{0.2,0.9\sqrt[p]{fe}\}\},$
wenn $fe<1$ , setze $H:=\hat h$ , gehe nach 1,
wenn $fe\geq 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\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 y(t_n) eine Näherung für x(t_n) , also mit kleinem Residuum $F\big(y(t_n),t_n)\cong0$ . 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 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{\|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 $q\in[0.1,0.3]$ lautet eine einfache Schrittweitensteuerung hierfür so:

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

Bei einer starken Unterschreitung der Referenzgröße , 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 .

Basierend auf einem Artikel in:

Wikipedia.de