Advanced Games Physics
Inhaltsverzeichnis zum
Inhalt

Die Familie der RUNGE-KUTTA-Verfahren

ODE-Solver nach dem Dormand-Prince-Verfahren

Der ODE-Solver nach dem DORMAND-PRINCE-Verfahren gehört der RUNGE-KUTTA-Familie an und ist ebenfalls ein explizites Einschritt-Verfahren. Es hat dem klassischen RK4-Verfahren gegenüber aber einen Genauigkeitsvorteil, der kaum auf die Rechenleistung Rückwirkungen hat. Dieses Verfahren ist ein sog. eingebettetes Verfahren, welches mit einer automatisch funktionierenden dynamischen Schrittweitensteuerung ausgestattet ist. Was bedeutet "eingebettet"? Das wird deutlich, wenn wir uns das BUTCHER-Schema des Verfahrens ansehen.

BUTCHER-Array des DORMAND-PRINCE-(45)-Verfahrens

Abb. BUTCHER-Array des DORMAND-PRINCE-(45)-Verfahrens

Aus geht hervor, dass das DP45-Verfahren sowohl eine Lösung mit der Konsistenzordnung p = 5 als auch eine mit der Konsistenzordnung p = 4 zur Verfügung stellt. Von Vorteil ist dabei, dass die Rechnung mit p = 4 auf die selben Funktionswerte zugreift wie das Verfahren mit p = 5. Das bedeutet, dass die Berechnung mit p = 4 kaum zusätzlichen Rechenaufwand bedeutet, sieht man von der Summation nach a) ab. Daher der Namenszusatz eingebettet. Was bringt uns aber diese zusätzliche Rechnung? Wir wissen doch, dass die Konsistenzordnung p = 5 bessere Ergebnisse liefert als die Konsistenzordnung p = 4! Betrachten wir doch die Rechnung mit der Konsistenzordnung p = 4 einmal als Vergleichsrechnung, um abschätzen zu können, welchen Gewinn an Genauigkeit der Schritt von p = 4 auf p = 5 bringt. Aus dem Unterschied zwischen beiden Rechnungen kann ein Kriterium s für die Veränderung der Schrittweite Δt im Sinne einer Verbesserung der Genauigkeit abgeleitet werden:
()
Formel
Worin ε eine Schranke darstellt, unter der eine weitere Verringerung der Schrittweite nicht erfolgen soll. Dabei ist das Intervall Δt gleich der von außen, z.B. durch die Bildwechselfrequenz, vorgegebenen Schrittweite. Hingegen ist Δt' die aktuelle, automatisch veränderbare Schrittweite.
Solange die Schranke ε nicht erreicht ist, werden die bisher erzielten Ergebnisse verworfen und eine neue Rechnung mit verkleinerter Schrittweite durchgeführt. Als zweckmäßig hat sich eine Halbierung der jeweils aktuellen Schrittweite erwiesen. Ebenso könnte die Vergleichsrechnung auch ergeben, dass die aktuelle Schrittweite kleiner als unbedingt notwendig ist, dann sollte die aktuelle Schrittweite verdoppelt werden. Allerdings gibt es für uns im Spieleumfeld die Einschränkung, dass die Schrittweite nicht größer als die durch die Bildwechsel­frequenz vorgegebene Schrittweite sein sollte.
Eine automatische Schrittweitensteuerung ist überaus sinnvoll! Denn eine Verringerung der Schrittweite führt zu erhöhtem Rechenaufwand. Und warum soll der Aufwand erhöht werden, wenn der Gewinn an Genauigkeit das nicht rechtfertigt? In Dormand-Prince-Method ist eine sehr schöne Erläuterung dieser automatisch ablaufenden Schrittweitensteuerung gegeben. Hier die Empfehlung für die Schrittweiten­steuerung: Der ökonomische Vorteil der Schrittweitensteuerung besteht darin, dass die aktuelle Schrittweite Δt' für die nächsten Rechenschritte übernommen wird. Erst, wenn sich eine Änderung erforderlich macht, wird die aktuelle Schrittweite angepasst.

Die Anwendung des DORMAND-PRINCE-Verfahrens auf Differentialgleichungen 2. Ordnung erfolgt genau so, wie wir das beim klassischen RUNGE-KUTTA- Verfahren besprochen haben. Die Implementierung und Anwendung des DP45-Verfahrens () ist ähnlich dem des RUNGE-KUTTA(4)-Verfahrens. Eine Besonderheit tritt jedoch auf: im Construktor sind die Genauigkeitsschranke ε und die Anzahl der maximalen Rückweisungen N anzugeben. Letzteres ist wichtig, um endlos-Schleifen zu vermeiden, wenn die geforderte Genauigkeit nicht erreichbar ist.



Abb. Anwendung des DORMAND-PRINCE-(45)-Verfahrens


Das Beispiel zeigt die Anwendung des DP45-Verfahrens auf das schon bekannte hängend befestigte Feder-Masse-System. Resonanz­frequenz ω0 und Däpfung δ können wieder per Schieberegler frei gewählt werde. Von Interesse sind hier insbesondere die Parameter­treue, d.h. wie genau stimmt die tatsächlich gemessene Schwingungs­frequenz mit der vorge­gebenen überein und die Änderung der im System befindlichen Energie. Beide Werte sind bei δ = 0 zu messen!
download processing
download p5.js
run program

Ergebnisgiskussion: Schon beim ersten Blick auf die Fehlerausschriften Δf und ΔW fallen die im Vergleich zu den bisher besprochenen Verfahren um mehrere 10er-Potenzen besseren Werte auf. Aber bei nicht vorhandenem Reibungseinfluss im Feder-Masse-System ist zu bemerken, dass - das negative Vorzeichen beim ΔW zeigt es an - ein geringer Energieverlust im System in Erscheinung tritt. Der sich wegen seines äußerst geringen Ausmaßes natürlich erst nach langer Beobachtungsdauer wirklich bemerkbar macht. In der Spielewelt ist dieser Energieverlust natürlich völlig ohne Bedeutung, da unsere Systeme ja generell mit Reibungseinflüssen zu tun haben.
Wohingegen die Parametertreue uneingeschränkt sehr gut ist. Beide Fehlermaße steigen proportional mit der eingestellten Eigenfrequenz, was gleichbedeutend mit einer steiferen Feder ist.

Der ODE-Solver nach DORMAND-PRINCE (45) ist der genaueste Algorithmus zur Lösung gewöhnlicher Differential­gleichungen 2. Ordnung! Dies betrifft sowohl die Parametertreue als auch die Stabilität der Lösung.


Jetzt die Nagelprobe. Wie gut sind die Verfahren der RUNGE-KUTTA-Familie im Vergleich zu den vorher besprochenen Verfahren wirklich? Dazu bemühen wir noch einmal das kosmische Szenarium: die Planetenbewegung um die Sonne. Zum Vergleich stehen das velocity Verlet-, das klassische 4-stufige RUNGE-KUTTA-Verfahren und das DORMAND-PRINCE-45-Verfahren. Die Bahnparameter des Planeten (oder Kometen) sind im Vergleich zum vorherigen Experiment verschärft worden, um die Unterschiede der Verfahren deutlicher machen zu können.

Das Beispiel zeigt die Anwendung des DP45-Verfahrens auf die schon bekannte Kometenbahn-Problematik. Hier werden die drei aussichtsreichsten Kandidaten für stabile und parametertreue ODE-Solver gegenüber gestellt. Die Stabilität der Lösungen zeigt sich in den mehr oder weniger geschlossenen Bahnkurven.
download processing
download p5.js
run program

Ergebnisdisskusion: Das kosmische Projekt zeigt insbesondere bei großen Schrittweiten deutlich die Überlegenheit der Verfahren höherer Ordnung. Die extremeren Bahnparameter bringen das velocity Verlet-Verfahren sehr schnell an seine Grenzen. Das RUNGE-KUTTA (RK4)-Verfahren ist sichtbar besser, zeigt aber über längere Zeiten eine Zunahme der Gesamtenergie, was zu einer nichtschließenden Bahn führt. Erst das DORMAND-PRINCE (DP45)-Verfahren kann bei geringstem Energieverlust über lange Zeiten den Eindruck einer geschlossenen Bahn erwecken. Wegen seiner hervorragenden Eigenschaften ist das DORMAND-PRINCE-Verfahren unter der Bezeichnung DOPRI oder RKDP als Standardverfahren als ODE-Solver weit verbreitet. U.a. in solchen Programmsystemen wie MATLAB (hier als ode45 aufrufbar) bzw. Simulink.