www.wikidata.de-de.nina.az

Schrittweitensteuerung ist eine Technik die in der numerischen Mathematik bei Algorithmen angewendet werden kann die ein

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 für ein gewisses -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 berechnen, also Näherungen , wobei als Anfangswert bekannt ist. Die verwendeten Schrittweiten nennt man . 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 . 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 von der unbekannten Lösungskurve abhängen, insbesondere von ihren Ableitungen , die Größenordnung dieser Vorfaktoren kann daher stark schwanken. Daher verwendet man bei modernen Algorithmen keine konstante Schrittweite . Die wichtigsten Argumente für eine Schrittweitensteuerung sind

  • aus Effizienzgründen ist es sinnvoll bei kleinen Werten mit großen Schrittweiten und bei großen Werten 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 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 Bearbeiten

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 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 im nächsten Schritt zwei Näherungen und 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 eine Schätzung für den auftretenden lokalen Fehler. Zur Bestimmung der idealen Schrittweite betrachtet man mit der aktuellen Schrittweite die Bedingung

als Gleichung für den unbekannten Faktor und bestimmt dann damit die Schrittweite, welche eine vom Anwender vorgegebene Toleranz genau einhalten würde, also mit :

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

  1. berechne die beiden Lösungen zur Schrittweite und damit den Fehlerquotienten ,
  2. berechne damit
  3. wenn , setze , gehe nach 1,
  4. wenn ist, setze und . Der nächste Schritt beginnt wieder mit Anweisung 1.

In Anweisung 3 wird also der aktuelle Versuch verworfen und der Schritt ab 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 Bearbeiten

Bei der Verfolgung der Lösungskurven nichtlinearerer Gleichungssysteme 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 eine Näherung für , also mit kleinem Residuum . Bei der einfachen Kurvenverfolgung stellen Homotopieverfahren einen Prädiktor bereit, der eine Startnäherung für die unbekannte berechnet. Mit führt man zwei Newtonschritte durch, welche verbesserte Näherungen berechnen. Die schnelle Konvergenz des Newton-Verfahrens wird mit dem Quotienten

der Differenzen überprüft. Mit einem kleinen Referenzwert lautet eine einfache Schrittweitensteuerung hierfür so:

  1. berechne zur Schrittweite
  2. für setze und gehe zu Anweisung 1.
  3. für akzeptiere , setze , beginne nächsten Schritt mit Anweisung 1.

Bei einer starken Unterschreitung der Referenzgröße , z. B. für , kann im Schritt 3 vor dem Sprung zu Anweisung 1 die Schrittweiten-Vorhersage für auch wieder vergrößert werden durch .

Literatur Bearbeiten

  • 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.
wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
Schrittweitensteuerung ist eine Technik die in der numerischen Mathematik bei Algorithmen angewendet werden kann die ein kontinuierliches Problem durch Diskretisierung in einzelne Schritte losen Verschiedene Problemklassen fuhren auf die Aufgabe eine Kurve t x t R d displaystyle t mapsto x t in mathbb R d fur ein gewisses t displaystyle t Intervall in R displaystyle mathbb R zu konstruieren Dazu gehoren die Losung eines Anfangswertproblems fur gewohnliche Differentialgleichungen und die Verfolgung einer Losungskurve nichtlinearerer Gleichungssysteme mit Homotopieverfahren Solche Probleme werden in der numerischen Mathematik oft mit Verfahren gelost die die Losung nur schrittweise an einzelnen Punkten t 0 lt t 1 lt t 2 lt displaystyle t 0 lt t 1 lt t 2 lt ldots berechnen also Naherungen y n x t n n 1 2 displaystyle y n cong x t n n 1 2 ldots wobei y 0 x t 0 displaystyle y 0 x t 0 als Anfangswert bekannt ist Die verwendeten Schrittweiten nennt man h n t n 1 t n n 0 displaystyle h n t n 1 t n n geq 0 Typischerweise ist der Rechenaufwand fur einen einzelnen Schritt i w konstant und der Fehler hangt ab von einer Potenz der Schrittweite er hat die Form c n h n p displaystyle c n h n p Man steht dann vor der Frage wie gross die Schrittweiten zu wahlen sind um eine gewunschte Genauigkeit insgesamt zu erreichen Dabei ist zu beachten dass die Vorfaktoren c n displaystyle c n von der unbekannten Losungskurve abhangen insbesondere von ihren Ableitungen x q q p displaystyle x q q leq p die Grossenordnung dieser Vorfaktoren kann daher stark schwanken Daher verwendet man bei modernen Algorithmen keine konstante Schrittweite h n h displaystyle h n equiv h Die wichtigsten Argumente fur eine Schrittweitensteuerung sind aus Effizienzgrunden ist es sinnvoll bei kleinen Werten c n displaystyle c n mit grossen Schrittweiten und bei grossen Werten c n displaystyle c n mit kleinen zu arbeiten um einen gleichmassig kleinen Gesamtfehler mit moglichst wenigen Schritten zu erreichen eine feste Schrittweite h displaystyle h musste sich nach der ungunstigsten Stelle mit dem grossten c n displaystyle c n richten und man wurde in weniger kritischen Bereichen viel zu viele Schritte machen was bei Anfangswertproblemen auch zu grossen Rundungsfehlern in der Losung fuhren kann Schrittweitensteuerung ermoglicht die Programmierung automatischer selbststeuernder Algorithmen Schrittweitensteuerung bei Anfangswertproblemen BearbeitenVoraussetzung fur eine Schrittweitensteuerung bei gewohnlichen Anfangswertproblemen ist das Vorhandensein einer Fehlerschatzung fur den lokalen Fehler Solche Schatzungen kann man allgemein durch Richardson Extrapolation bekommen indem man einen Schritt mit den Test Schrittweiten h displaystyle h nbsp und h 2 displaystyle h 2 nbsp durchfuhrt und die beiden Naherungen vergleicht Weniger Aufwand erfordern bei Runge Kutta Verfahren eingebettete Verfahren bzw Verfahrenspaare wobei man ausgehend von einer berechneten Naherung y n displaystyle y n nbsp im nachsten Schritt zwei Naherungen y n 1 displaystyle y n 1 nbsp und y n 1 displaystyle hat y n 1 nbsp unterschiedlicher Genauigkeit berechnet Bei Mehrschrittverfahren kann man die Naherungen einer Pradiktor Korrektor Methode als Verfahrenspaar verwenden Mit einem solchen Verfahrenspaar ist die Differenz y n 1 y n 1 displaystyle hat y n 1 y n 1 nbsp eine Schatzung fur den auftretenden lokalen Fehler Zur Bestimmung der idealen Schrittweite betrachtet man mit der aktuellen Schrittweite h n displaystyle h n nbsp die Bedingung y n 1 y n 1 c n h n p displaystyle hat y n 1 y n 1 c n h n p nbsp als Gleichung fur den unbekannten Faktor c n displaystyle c n nbsp und bestimmt dann damit die Schrittweite welche eine vom Anwender vorgegebene Toleranz ϵ displaystyle epsilon nbsp genau einhalten wurde also mit c n h p ϵ displaystyle c n hat h p epsilon nbsp h h n f e p f e ϵ y n 1 y n 1 displaystyle hat h h n cdot sqrt p fe quad fe frac epsilon hat y n 1 y n 1 nbsp Da dieser Wert allerdings erst nach Durchfuhrung des Schritts bekannt ist geht man nach einem Trial and Error Verfahren vor und nutzt die Schrittweite h displaystyle hat h nbsp nur in einer Wiederholung des Schrittes wenn die Toleranz nicht eingehalten wurde d h wenn der Fehlerquotient f e lt 1 displaystyle fe lt 1 nbsp war Da Wiederholungen relativ teuer sind ist man vorsichtig und benutzt einen kleineren Wert etwa H 0 9 h displaystyle H 0 9 hat h nbsp Ausserdem begrenzt man den Schrittweitenfaktor nach oben und unten Die Steuerung im Schritt ab t n displaystyle t n nbsp hat daher mit einer ersten Schatzung H displaystyle H nbsp folgenden Ablauf berechne die beiden Losungen y n 1 y n 1 displaystyle y n 1 hat y n 1 nbsp zur Schrittweite H displaystyle H nbsp und damit den Fehlerquotienten f e displaystyle fe nbsp berechne damit h H min 2 max 0 2 0 9 f e p displaystyle hat h H cdot min 2 max 0 2 0 9 sqrt p fe nbsp wenn f e lt 1 displaystyle fe lt 1 nbsp setze H h displaystyle H hat h nbsp gehe nach 1 wenn f e 1 displaystyle fe geq 1 nbsp ist setze t n 1 t n H n n 1 displaystyle t n 1 t n H n n 1 nbsp und H h displaystyle H hat h nbsp Der nachste Schritt beginnt wieder mit Anweisung 1 In Anweisung 3 wird also der aktuelle Versuch verworfen und der Schritt ab t n displaystyle t n nbsp mit kleinerer Schrittweite wiederholt wahrend in Punkt 4 der Schritt akzeptiert wird und der nachste Integrationsschritt erfolgen kann Eine Zusatzabfrage beendet das Verfahren am Ende des Losungsintervalls Dieses Verfahren steuert aber nur die lokalen Fehlerbeitrage und erwartet dass der globale Fehler am Ende des Intervalls ungefahr in der gleichen Grossenordnung liegt Schrittweitensteuerung bei Homotopieverfahren BearbeitenBei der Verfolgung der Losungskurven nichtlinearerer Gleichungssysteme F x t t 0 displaystyle F big x t t 0 nbsp 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 moglichst schnell voranzukommen ohne die Kurve dabei zu verlieren oder auf einen Nachbarzweig zu wechseln Zur Fehlerschatzung pruft man daher die Konvergenzgeschwindigkeit der Newton Iteration Es sei jetzt y t n displaystyle y t n nbsp eine Naherung fur x t n displaystyle x t n nbsp also mit kleinem Residuum F y t n t n 0 displaystyle F big y t n t n cong 0 nbsp Bei der einfachen Kurvenverfolgung stellen Homotopieverfahren einen Pradiktor bereit der eine Startnaherung y 0 t n H displaystyle y 0 t n H nbsp fur die unbekannte x t n H displaystyle x t n H nbsp berechnet Mit y 0 t n H displaystyle y 0 t n H nbsp fuhrt man zwei Newtonschritte durch welche verbesserte Naherungen y 1 t n H y 2 t n H displaystyle y 1 t n H y 2 t n H nbsp berechnen Die schnelle Konvergenz des Newton Verfahrens wird mit dem Quotienten Q y 2 t n H y 1 t n H y 1 t n H y 0 t n H displaystyle Q frac y 2 t n H y 1 t n H y 1 t n H y 0 t n H nbsp der Differenzen uberpruft Mit einem kleinen Referenzwert q 0 1 0 3 displaystyle q in 0 1 0 3 nbsp lautet eine einfache Schrittweitensteuerung hierfur so berechne y 0 t n H y 1 t n H y 2 t n H displaystyle y 0 t n H y 1 t n H y 2 t n H nbsp zur Schrittweite H displaystyle H nbsp fur Q gt q displaystyle Q gt q nbsp setze H H 2 displaystyle H H 2 nbsp und gehe zu Anweisung 1 fur Q q displaystyle Q leq q nbsp akzeptiere h n H y t n 1 y 2 t n H displaystyle h n H y t n 1 y 2 t n H nbsp setze n n 1 displaystyle n n 1 nbsp beginne nachsten Schritt mit Anweisung 1 Bei einer starken Unterschreitung der Referenzgrosse q displaystyle q nbsp z B fur Q q 4 displaystyle Q leq q 4 nbsp kann im Schritt 3 vor dem Sprung zu Anweisung 1 die Schrittweiten Vorhersage fur h n 1 displaystyle h n 1 nbsp auch wieder vergrossert werden durch H 2 H displaystyle H 2H nbsp Literatur BearbeitenErnst Hairer Gerhard Wanner Solving Ordinary Differential Equations 1 Nonstiff Problems ISBN 3 540 56670 8 K Strehmel R Weiner H Podhaisky Numerik gewohnlicher 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 fur Naturwissenschaftler und Ingenieure Fachbuchverlag Leipzig 1991 ISBN 3 343 00580 0 S 200 Abgerufen von https de wikipedia org w index php title Schrittweitensteuerung amp oldid 216220157