Advanced Games Physics
Inhaltsverzeichnis zum
Inhalt

Die Familie der RUNGE-KUTTA-Verfahren

Das GEAR-Verfahren (BDF): ein Mehrschrittverfahren

Stellvertretend für die Verfahrensgruppe der Mehrschritt-Verfahren soll hier nur das BDF-Verfahren (Backward Differentiation Methods), das auch unter der Bezeichnung Gear-Verfahren bekannt ist, besprochen werden.
Die Idee besteht darin, dass auf der Grundlage von N-1 bekannten Werten vi-N bis vi der zu lösenden Differential­gleichung ein neuer Wert vi+1 vorher gesagt wird. Natürlich wird diese Vorhersage Fehler behaftet sein. Darum muss im Anschluss an die Vorhersage noch eine iterative Verbesserung des neuen Wertes erfolgen.
Zunächst aber wollen wir uns mit dem Vorhersageteil befassen. Dazu betrachten wir die .

Lösungsprinzip des BDF-Verfahrens

Abb. Lösungsprinzip des BDF-Verfahrens

Die grüne Kurve versinnbildlicht den zeitlichen Verlauf, der durch die Lösung der Differential­gleichung beschrieben wird. Wobei der Wert zum Zeitpunkt ti+1 aber noch gar nicht bekannt ist. Was wir kennen, ist die Steigung der Tangente in diesem Punkt! Sie entspricht genau der Gradientenfunktion
()
Formel
zum Zeitpunkt ti+1.
Nun konstruieren wir ein Polynom (blaue gestrichelte Kurve),
()
Formel
das die Kurve v(t) durch die Kurve v*(t) = P(t) ersetzt und zu den vorangegangenen diskreten Zeitpunkten ti bis ti-N genau mit der Lösung der DGl. zu diesen Zeitpunkten übereinstimmt. Beachte dabei, dass diese Zeitpunkte stets ganzzahlige Vielfache der Schrittweite Δt sind! Zeitliche Zwischenwerte interessieren uns aus eben diesem Grund nicht.
Und wozu das Ganze? Polynome sind differenzierbar:
()
Formel
So ist es leicht, die erste Ableitung des Polynoms zum Zeitpunkt ti+1 nach der Zeit mit der Gradientenfunktion () zu vergleichen:
()
Formel
Berücksichtigen wir dabei, dass die Zeit tn = n·Δt ist, geht die in die über:

Polynom <span class=P(n)">

Abb. Polynom P(n)

Dadurch geht der absolute Zeitbezug verloren und das Polynom Zeit P(t) wird zum Polynom P(n), wobei wichtig ist, dass alle Stützstellen äquidistant sind.

Wie werden nun die Koeffizienten an des Polynoms so bestimmt, dass die Stützstellen des Polynoms P(n) mit den Stützstellen der Funktion v(n·Δt) überein stimmen? Der mathematische Werkzeugkasten bietet hier eine ganze Reihe unterschiedlicher Möglichkeiten, wie z.B. das Interpolationsverfahren nach NEWTON oder das Interpolationsverfahren nach LAGRANGE an.
In letzteren Fall spielen die Koeffizienten Li(x) der LAGRANGE-Basis eine wichtige Rolle. Auf unser Problem angewendet berechnen sich diese Koeffizienten zu
()
Formel
woraus sich dann das Polynom
()
Formel
ergibt. In dieser Form ist das Polynom allerdings noch nicht brauchbar. Es müssen noch die Lj berechnet, nach Potenzen von t geordnet und entsprechend differenziert werden. Ist dies erfolgt, erhalten wir das differenzierte Polynom
()
Formel
Lasse Dich nicht durch die Namen der Koeffizienten dieses Polynoms verwirren! Die bn setzen sich aus den Stützstellen­werten vi-n , den Lj und den Faktoren, die von der Differen­tiation herrühren, zusammen. In der step-by-step Erklärung findest Du die Herleitung der Berechnung der b-Koeffizienten an einem Beispiel.

Beachte weiterhin: Unter der Voraussetzung, dass jedes tn = n·Δt ist, verschwindet der Zeitbezug vollständig aus der Gleichung. Die vi bis vi-N sind bekannte Werte und daher als Konstanten zu betrachten. Nur vi+1 ist nicht bekannt, also als die maßgebliche Variable zu betrachten.
step by step explanation
Bitte einen Augenblick Geduld
während das Programm geladen wird!


Abb. Berechnung aller BDF-Koeffizienten für N = 2 ... 10

Jetzt kann die Gleichsetzung des differenzierten Polynoms mit der Gradientenfunktion gemäß erfolgen:
()
Formel
nun noch umstellen
download p5.js
()
Formel
und wir erhalten den Wert der neuen Stützstelle.

Nun zeigt sich aber, dass der neue Wert die Berechnung der Gradientenfunktion f(vi+1) unter Verwendung genau dieses Wertes voraussetzt. Es handelt sich hier also wieder um eine implizite Berechnungs­vorschrift für die Lösung der DGl.! Damit kommen wir zum zweiten Teil der Aufgabe.
ist in den meisten Fällen mit einer Fixpunktiteration am einfachsten zu behandeln. In der Implementierung sieht das so aus, dass der gerade gefundene neue Wert in die Berechnung der Gradientenfunktion eingeht und so einen verbesserten Wert für vi+1 liefert. Diese Iteration wird so lange fortgesetzt, bis die Verbesserung unter einer festgesetzten Schranke ε liegt. Eine Bedingung für die Lösbarkeit ist die Wahl eines geeigneten Startpunktes für die Iteration. In unserem Fall bietet sich dafür der letzte bekannte Wert, also vi, an.

Bleibt nun noch die Frage, wo nehme ich die ersten N-1 Stützstellen her, wenn die Berechnung gerade begonnen hat? Da bleibt nur, diese Stützstellen mit einem Einschritt-Verfahren (z.B. EULER-CAUCHY oder RUNGE-KUTTA) zu berechnen. Diese sog. Vorleistung ist immer zu erbringen, wenn ein Mehrschrittverfahren angewendet werden soll.

Die Implementierung beginnt wie üblich mit der Instanzierung des Solvers in der setup()-Funktion, wobei Angaben über die Schrittzahl N, die maximale Anzahl R von Rückweisungen und die Genauigkeitsschranke ε erforderlich sind. Und für die Ausführung des Programms ist eine Gradientenfunktion notwendig:



Abb. Anwendung des BDF-(6)-Verfahrens


Im Beispielprogramm werden je ein 2-, 4- und 6-stufiges BDF-Lösungsverfahren gegenüber gestellt. Zu lösen ist die Differntialgleichung für ein hängendes Feder-Masse-System, dessen Eigenfrequenz f0 und Dämpfung δ frei wählbar sind.
download processing
download p5.js
run program

Schlussfolgerungen: Es ist eine Tatsache, dass die Approximation einer Kurve anhand ausgewählter Stützstellen durch ein Polynom zunächst nur für die Stützstellen und deren unmittelbarer Umgebung eine Deckung erlaubt. Zwischen den Stützstellen und vor allem außerhalb des Bereiches, der durch die Stützstellen beschrieben ist, kann es zu erheblichen Abweichungen kommen. Je höher der Grad des Polynoms, also je mehr Stützstellen in die Interpolation eingehen, um so gravierender sind diese Abweichungen. Aus diesem Grund darf für das BDF-Verfahren der Grad des Polynoms nicht größer als N ≤ 6 sein.
Aus eben diesem Grund ist auch die Wahl eines impliziten Verfahrens für die Lösung der DGl. mittels Polynom sehr sinnvoll. Denn auf diese Weise wird die neue Stützstelle in den Bereich des Polynoms eingebunden, in dem die Approximationsgenauigkeit noch sehr groß ist.
Im Versuch scheint, wie das Verhalten der Kontrollfunktion ΔW nahelegt, die Lösung mit einem Polynom 4. Grades nicht sehr stabil zu sein, da die Energie über der Zeit zunimmt (auch ein Polynom 3. Grades scheint keine stabile Lösung zu liefern). Dieses Verhalten ist von der gewählten Schrittweite unabhängig. Allerdings muss hinzugefügt werden, dass diese Instabilität Größenordnungen unter der Instabilität liegt, sollte die Schrittzahl N > 6 sein!

Weil das BDF-Verfahren ein implizites Verfahren ist, wird diesem Verfahren ein besonders hohes Potential zur Lösung steifer Differential­gleichungen nachgesagt. Was die Genauigkeit betrifft, kann es aber mit dem RUNGE-KUTTA-(4)-Verfahren oder dem DORMAND-PRINCE-(45)-Verfahren nicht mithalten.