Direktes Mehrfachschießverfahren

In der Numerik gewöhnlicher Differentialgleichungen, einem Teilgebiet der Mathematik, bezeichnen Direkte Mehrfachschießverfahren (engl. direct multiple shooting methods) ein numerisches Verfahren zur Lösung von Randwertproblemen. Dabei wird das Intervall, auf welchem die Lösung bestimmt werden soll, zunächst in kleinere Intervalle unterteilt, auf denen dann jeweils ein Anfangswertproblem gelöst wird. Mit zusätzlichen Passbedingungen wird dann eine Lösung auf dem kompletten Intervall bestimmt. Diese Methode ist eine wesentliche Weiterentwicklung der Einfachschießverfahren (single shooting methods), insbesondere was die numerische Stabilität anbelangt.

Einfachschießverfahren

Zur Lösung von Randwertproblemen können Schießverfahren verwendet werden:

$y'(t) = f(t, y(t)), \quad y(t_a) = y_a, \quad y(t_b) = y_b,$

mit bekannten Zeitpunkten t_a und t_b aber unbekannten und zu bestimmenden Anfangs- und Endwerten y_a und y_b.

Einfachschießverfahren gehen folgendermaßen vor: Sei y(t;t₀,y₀) die Lösung des Anfangswertproblems

$y'(t) = f(t, y(t)), \quad y(t_0) = y_0.$

Definiere nun die Funktion F(p) als den Unterschied zwischen y(t_b;p) und dem gegebenen Randwert y_b: F(p) = y(t_b;p) − y_b. Dann haben wir für jede Lösung (y_a,y_b) des Randwertproblems y_a = y₀ wobei y_b mit einer Nullstelle von F zusammenfällt. Diese Nullstelle kann durch ein beliebiges Verfahren bestimmt werden (solange die dafür notwendigen Voraussetzungen erfüllt sind). Oftmals sind hierfür Startwerte für y_a und y_b erforderlich. Meist ist eine analytische Bestimmung der Nullstelle nicht möglich, weshalb iterative Methoden wie das Newton-Verfahren verwendet werden.

Die Anwendung von Einfachschießverfahren wird oft durch einige Probleme behindert:

• Für einen gegebenen Anfangswert y₀ muss die Lösung des Anfangswertproblems auf dem Intervall [t_a,t_b] existieren, damit die Funktion F zur Nullstellensuche überhaupt ausgewertet werden kann. Bei stark nichtlinearen oder instabilen gewöhnlichen Differentialgleichungen muss der Anfangswert y₀ einem tatsächlichen aber unbekannten y_a nah genug sein. Anfangswerte die zu weit von einer Lösung entfernt liegen, können so zu Singularitäten oder zum Abbruch des ODE-Lösers führen. Solche Lösungen zu finden, ist unabdingbar bei der Nullstellenbestimmung.
• Für Rechner mit endlicher Genauigkeit kann es unmöglich sein, Anfangswerte zu finden, die für das gesamte Intervall eine Lösung liefern.
• Die Nichtlinearität einer gewöhnlichen Differentialgleichung schlägt sich in einer Nichtlinearität von F nieder und erfordern von einem Nullstellen-Such-Verfahren die Fähigkeit, mit diesen umgehen zu können. Solche Verfahren konvergieren jedoch meist langsamer, wenn Nichtlinearitäten zunehmen, worunter dann auch die Performance des ODE-Lösers leidet.
• Sogar stabile und gut konditionierte Differentialgleichungen können zu instabilen oder schlecht konditionierten Randwertproblemen führen. Eine kleine Änderung des geschätzten Anfangswertes y₀ kann so zu einem extrem großen Schritt in der ODE-Lösung y(t_b;t_a,y₀) führen und damit in den Werten der Funktion F. Damit haben nicht-analytische Verfahren zur Nullstellenbestimmung aber meist Schwierigkeiten.

Mehrfachschießverfahren

Ein direktes Mehrfachschießverfahren teilt das Intervall [t_a,t_b] durch Einführung zusätzlicher Gitterpunkte

$t_a = t_0 < t_1 < \cdots < t_N = t_b$.

auf. Das Verfahren beginnt mit gewählten Startdaten für die y-Werte an allen Gitterpunkten t_k, 0 ≤ k ≤ N − 1. Bezeichnen wir diese Werte mit y_k und ist y(t;t_k,y_k) die vom kten Gitterpunkt ausgehende Lösung, also die Lösung des Anfangswertproblems

$y'(t) = f(t, y(t)), \quad y(t_k) = y_k.$

Diese Lösungen können nun in Form einer stetigen Trajektorie zusammengefügt werden, wenn die Werte y an allen Gitterpunkten zusammenpassen. Daher korrespondieren Lösungen des Randwertproblems mit Lösungen des folgenden Systems aus N Gleichungen:

$\begin{align} & y(t_1; t_0, y_0) = y_1 \\ & \qquad\qquad\vdots \\ & y(t_{N-1}; t_{N-2}, y_{N-2}) = y_{N-1} \\ & y(t_N; t_{N-1}, y_{N-1}) = y_b. \end{align}$

Die mittleren N−2 Gleichungen sind die Schließbedingungen, während die erste und die letzte Gleichung die Bedingungen y(t_a) = y_a und y(t_b) = y_b aus dem Randwertproblem darstellen. Das Mehrfachschießverfahren löst das Randwertproblem durch Lösung dieses Gleichungssystems üblicherweise mit einem Newton-Verfahren.

Literatur

• Josef Stoer, Roland Bulirsch: Introduction to Numerical Analysis. 3. Auflage. Springer-Verlag, Berlin, New York 2002, ISBN 978-0-387-95452-3, 7.3.5 ff.
• Hans Georg Bock, Karl J. Plitt: A multiple shooting algorithm for direct solution of optimal control problems. In: Proceedings of the 9th IFAC World Congress. Budapest 1984.