Advanced Games Physics
Inhaltsverzeichnis zum
Inhalt

Lösung von nicht elementar lösbaren Aufgaben mittels numerischer Methoden

Die Familie der RUNGE-KUTTA-Verfahren

Alle Verfahren dieser Familie gehören zu den Einschritt-Verfahren. Bei vorgegebener Ordnung p kann die Zahl der erforderlichen Stufen s ≥ p frei gewählt werden. Dadurch ergibt sich eine große Anzahl verschiedener Verfahren.

Um zu verstehen, wie diese Verfahren funktionieren, beschränken wir uns zunächst auf die Lösung einer Differentialgleichung 1. Ordnung. Die Erweiterung auf solche 2. Ordnung, also Bewegungs-Differentialgleichungen, werden wir im Anschluss anhand konkreter Lösungsverfahren besprechen.

Zunächst also das Lösungsprinzip: Innerhalb eines Schrittes werden, um einen neuen Wert aus einem bereits bekannten Wert yi zu berechnen, s Berechnungsschritte ausgeführt. Dabei werden Zwischen­ergebnisse erzeugt, die entsprechend a aufsummiert, den neuen Wert yi+1 ergeben. Für die Summation werden die Zwischenresultate kj mit den Koeffizienten bj gewichtet. Die so erhaltene Summe wird nun noch mit der Schrittweite Δt multipliziert und dem alten Wert yi zu addiert.
(a)
Formel
Das besondere an diesem Verfahrenstyp ist nun die Erzeugung der s Zwischenergebnisse. Dafür werden für s unterschiedliche Zeitpunkte tj (sofern die Gradientenfunktion f(t,y) Zeit-abhängig ist, was bei uns aber sehr selten der Fall ist) und s unterschiedliche Werte der gesuchten Variablen y innerhalb des aktuellen Intervalls berechnet:
(b)
Formel
3. Geistesblitz
on/off
worin tj und yj nach
(c)
Formel
und
(d)
Formel
berechnet werden.
Die aktuelle Zeit ergibt sich in bekannter Weise zu
(c)
Formel
Die Koeffizienten bj, cj und aj,l werden der Stufenzahl s und der gewählten Ordnung p entsprechend berechnet. Diese Koeffizienten sind Konstanten und können der Literatur entnommen werden.
Sehr theoretisch! Um Licht ins Dunkel zu bringen, schauen wir uns gleich ein bekanntes Beispiel an, nämlich

Das klassische RUNGE-KUTTA-Verfahren (RK4)

Das klassische RUNGE-KUTTA-Verfahren ist ein 4-stufiges, explizites Verfahren und damit ein Spezialfall der Verfahrensfamilie der RUNGE-KUTTA-Verfahren. Es zeichnet sich durch eine besonders geringe Anzahl, von 0 verschiedener, Koeffizienten, die zudem noch Brüche einfacher, ganzer Zahlen sind, aus. Dadurch konnten in früheren Zeiten Differentialgleichungen auch ohne Computer numerisch gelöst werde. Das Verfahren hat die Konsistenzordnung p = 4.

Der besseren Anschaulichkeit halber bleiben wir bei der Lösung einer Differential­gleichung 1. Ordnung. Gegeben sei die Gradienten­funktion dy/dt = f(t,y). Dann erfolgt die Berechnung des neuen Wertes yi+1 entsprechend zu:
()
Formel
mit den folgenden Zwischenschritten:
()
Formel
Betrachten wir jetzt die Gleichungen . Wir sehen, dass die Gradientenfunktion f(t,y) an 4 verschiedenen Stellen berechnet werden muss, daher handelt es sich um ein 4-stufiges Verfahren! Die Zwischenschritte ks werden entsprechend der Gewichte, die durch die Koeffizenten laut b) zu berechnen sind, gegeben. Zur besseren Übersichtlichkeit stellen wir die Gewichte zu Spaltenvektoren zusammen. Die bj nach a):
()
Formel
und die  cj  nach  c):
()
Formel
und die aj, l nach d) als Matrix A:
()
Formel


Da es, wie schon erwähnt, eine Vielzahl unterschiedlicher RUNGE-KUTTA-Algorithmen gibt, ist eine vereinfachte Schreibweise für die Koeffizienten üblich. Das sog. BUTCHER-Tableau. Es stellt eine schematische Anordnung der Koeffizienten in einer Art Tabelle dar. Die grundlegende Anordnung zeigt :
()
Formel
Speziell für das klassische RUNGE-KUTTA-Verfahren nimmt das Butcher-Tableau folgende Gestalt an:
()
Formel
Da die rechte Hälfte der durch die Diagonale geteilten A-Matrix stets gleich 0 ist, hat sich die vereinfachte Schreibweise nach durchgesetzt:
()
Formel


Nun wollen wir überlegen, wie wir das für Differentialgleichungen 1. Ordnung erläuterte RUNGE-KUTTA-Verfahren auch auf Differentialgleichungen 2. Ordnung anwenden können. Erst diese Lösungsmethode kann uns die mgesuchten Bewegungsgleichungen liefern!
Im Kapitel Verfahren von EULER-CAUCHY für DGLn. 2. Ordnung haben wir die Vorgehensweise ausführlich geschildert. Das Vorgehen besteht darin, dass die Differentialgleichung 2. Ordnung in ein System von zwei Differentialgleichungen 1. Ordnung überführt wird ().

Wir gehen wieder davon aus, dass die Gradientenfunktion f(s, v) nicht zeitabhängig ist, was zu einer Vereinfachung der Lösung des DGl.-Systems führt.
Gemäß haben wir nun zwei Differentialgleichungen zu lösen. Entsprechend der Vorgabe des 4-stufigen RUNGE-KUTTA-Verfahrens sind die Orts-DGl.
(a)
Formel
und die Geschwindigkeits-DGl.
(b)
Formel
zu lösen.
In jeder der Gleichungen befindet sich jetzt ein Satz von kj-Koeffizienten, die aber je nach Bestimmung andere sind. Ihrer physikalischen Bedeutung nach sind die ks,j Gechwindigkeiten und die kv,j Beschleunigungen.
Es gibt ksJ-Koeffizienten für die Ortsberechnung und kvJ-Koeffizienten für die Geschwindigkeitsberechnung! Ihre Berechnung erfolgt in wechselseitiger Abhängigkeit von Ort und Geschwindigkeit, wobei sich diese Abhängigkeiten stets auf die folgende Stufe der Rechnung beziehen:
()
Formel
So gesehen sind diese Schritte jeweils einem symplektischen EC-Lösungsschritt vergleichbar.
Die Berechnung der Koeffizienten des Ortes in ist vergleichsweise einfach, da die erste Differentialgleichung (a) naturgemäß keine Ortsabhängigkeit aufweist, es fließt nur die Geschwindigkeit v ein. Die zweite Differentialgleichung (b) erfordert einen höheren Aufwand, da die Gradientenfunktion sowohl vom Ort (z.B. Federauslenkung) und der Geschwindigkeit (z.B. Luftreibung) abhängig sein kann.
So sieht die Implementierung in p5.js aus:



Abb. klassisches 4-stufiges RUNGE-KUTTA-Verfahren

Und so wird das RUNGE-KUTTA-Verfahren angewandt:



Abb. Anwendung des 4-stufiges RUNGE-KUTTA-Verfahren auf ein Feder-Masse-System

Die Implementation des ODE-Solvers nach RUNGE-KUTTA ist in processing leider nicht so unproblematisch wie in p5.js, weil ein Funktionsaufruf innerhalb ein Funktionsdeklaration nicht möglich ist. Wie dennoch eine passable Lösung für processing aussehen kann, zeigt der nebenstehende Geistesblitz:
Geistesblitz
on/off


Grau ist alle Theorie. Erproben wir den RUNGE-KUTTA-Algorithmus am Beispiel des hängenden Feder-Masse-Systems. Seine Bewegungs-DGl. ist durch gegeben.
Das folgende Beispielprogramm zeigt, wie wirksam die 4-stufige Berechnungsmethode des RUNGE-KUTTA-Verfahrens ist. Dämpfung δ und Eigenfrequenz &omega0; können wieder per Schieberegler gewählt werden, ebenso kann die Schrittweite mit dem Button Width verändert werden.
download processing
download p5.js
run program

Ergebnisgiskussion: Schon beim ersten Blick auf die Fehlerausschriften Δω und ΔWges fallen die im Vergleich zu den bisher besprochenen Verfahren deutlich besseren Werte auf. Aber bei nicht vorhandenem Reibungseinfluss im Feder-Masse-System ist zu bemerken, dass - das negative Vorzeichen beim ΔWges zeigt es an - ein geringer Energieverlust im System in Erscheinung tritt. Der sich wegen seines 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. Auch der Einfluss der Schrittweite ist deutlich nachweisbar. Je kleiner die Schrittweite desto exakter die Lösung.