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 t-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

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 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:

{\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 \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 {\displaystyle fe<1}, setze H:=\hat h, gehe nach 1,
  4. wenn {\displaystyle 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 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{\|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:

  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.

Trenner
Basierend auf einem Artikel in: Wikipedia.de
Seitenende
Seite zurück
©  biancahoegel.de
Datum der letzten Änderung:  Jena, den: 03.06. 2020