Advanced Games Physics
Inhaltsverzeichnis zum
Inhalt

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

Bitte einen Augenblick Geduld
während das Programm geladen wird!
Alle Themen in diesem Kapitel:

Findung von Nullstellen mittels Fixpunkt-Iteration

Oft werden Lösungen von Gleichungen gesucht, aber nicht immer gefunden! Im folgenden soll die Lösung von nicht elementar lösbaren Aufgaben mittels numerischer Methoden betrachtet werden. Die Fixpunkt-Iteration ist eine numerische Methode zur näherungsweisen Lösung von Nullstellen-Problemen. Dabei werden an die Funktion selbst keine Anforderungen gestellt, d.h. auch nichtlineare Funktionen können mit Hilfe der Fixpunkt-Iteration behandelt werden.
Was ist nun eine Fixpunkt-Iteration? Ausgangspunkt ist eine sog. Fixpunktgleichung, eine Funktion, die eine Menge M in sich selbst abbildet:
()
Formel
d.h. ist x* ein Fixpunkt, dann gibt die Funktion φ(x*) den Wert x* zurück. Diese Eigenschaft kann nun, wie zeigt, genutzt werden, um genau diesen Punkt iterativ anzunähern:
()
Formel
Die Iteration wird mit einem Startwert x0 begonnen und die Funktion φ(x0) gibt den Wert x1 zurück. Wenn die Funktion φ(x) gewisse Bedingungen erfüllt, dann liegt der zurück gegebene Wert näher an dem wirklichen Fixpunkt x* als der Startwert. In kannst Du das verfolgen, indem Du dem rot eingezeichneten Verlauf nach gehst. Nach einer bestimmten Anzahl von Iterationen ist der Näherungswert xn so weit an den wirklichen Fixpunkt herangerückt, dass er diesem bis auf einen Restfehler |φ(xn) - x*| entspricht. In diesem Fall war die Iteration konvergent

Fixpunkt-Iteration (konvergierend)

Abb. Fixpunkt-Iteration (konvergierend)
 nichtkonvergierende Iteration

Abb. nichtkonvergierende Iteration
Doch wie zeigt, geht die Iteration nicht immer erfolgreich aus. Dieses Beispiel einer nichtkonvergierenden Iteration zeigt, dass eine Fixpunktgleichung Bedingungen erfüllen muss. Der direkte Vergleich zwischen und zeigt, dass die Steigung der Funktion φ(x) in der Nähe des Fixpunktes nicht größer als die Steigung der Funktion f(x) = x sein darf. Steigungen werden durch die 1. Ableitung der Funktion gebildet, also muss in der Nähe des Fixpunktes die Bedingung
()
Formel
erfüllt sein, da ja die Ableitung der Funktion f'(x) = 1 ist.
In mathematischen Termini ausgrdrückt, muss die Fixpunkt-Funktion φ(x) kontrahierende Eigenschaften besitzen. Auf unsere Verhältnisse bezogen gilt
()
Formel
Worin λ < 1 die Kontraktionskostante, auch als LIPSCHITZ-Konstante bezeichnet, ist.

Gilt für das gesamte Intervall mit xo als obere und xu als untere Grenze
()
Formel
so kann jeder beliebige Wert x dieses Intervalls als Startwert x0 für eine konvergierende Iteration verwendet werden. Mit
()
Formel
kann gezeigt werden, dass mit jedem Iterationsschritt ein Zuwachs an Genauigkeit verbunden ist. Wenn im n-ten Schritt die Abweichung vom wirklichen Fixpunkt noch xn - x* betrug, beträgt sie im Folgeschritt nur noch λ·(xn - x*). Das heißt aber auch, dass die Konvergenz linear verläuft, also recht langsam! Deshalb kann es eine mehrere hundert Schritte umfassende Iteration bedürfen.

Um abschätzen zu können, welcher maximaler Fehler nach dem n-ten Schritt zu erwarten ist, kann eine A-priori-Fehlerabschätzung vorgenommen werden. Dazu werden die ersten beiden Schritte x0 und x1 (deshalb A-priori) sowie die Kontraktionskonstante λ benötigt:
()
Formel
Wohingegen aus der A-posteriori-Fehlerabschätzung (d.h. nach der Berechnung) eine Abbruchbedingung für die Iteration ableiten lässt. Ist nämlich
()
Formel
kleiner als eine beliebig gewählte Schranke ε, kann die Iteration beendet werden. Es gibt allerdings ein aber: nämlich die Rechengenauigkeit der verwendeten Programme. Diese beschränkt die erreichbare Genauigkeit und damit auch die Wahl eines sinnvollen ε. Insbesondere spielt die Wahl des Datentyps der Variablen eine wichtige Rolle. So liefert z.B. eine Rechnung in JAVA (→ processing) auf der Basis von double-Variablen Ergebnisse nicht genauer als 1,1·10-16. JAVASCRIPT (→ p5.js) kennt nur den Datentyp Number, der ebenfalls diese Genauigkeit erreicht.

Eindimensionale Funktionen

An einem eindimensionalen (d.h. die Zielfunktion ist nur von einer Variablen abhängig) Anwendungsbeispiel wollen wir die Funktionsweise der Fixpunkt-Iteration studieren und gleichzeitig auf das Problem der Mehrdeutigkeit eingehen.

Gegeben sei die Funktion
()
Formel
und gesucht sei der x-Wert, bei dem y = -2 wird. Das ist eine klassische Nullstellenaufgabe, ...
()
Formel
... wobei die Funktion nichtlinear und daher eine analytische Lösung unmöglich ist. Hinzu kommt, dass die Funktion in zwei Nullstellen aufweist, nämlich in der Nähe von x1 = -0,7 und bei x2 = 1,6. Genauer wissen wir das noch nicht, darum soll eine Fixpunkt-Iteration genauere Werte für die Nullstellen liefern. Wie gehen wir vor?

Zunächst können wir feststellen, dass es (entsprechend der zwei Nullstellen) zwei Möglichkeiten gibt, in Fixpunkt-Gleichungen durch geeignetes Umstellen zu überführen:
()
Formel
und
()
Formel
Einmal durch einfaches Auflösen des Produktes 2·x (), das andere mal durch Logarithmieren der Exponential­funktion ex (). Die zugehörigen Fixpunkt-Grafen sind in den und zu sehen.

konvergierende Fixpunkt-Gleichung

Abb. konvergierende Fixpunkt-Gleichung
im Intervall [-∞,0)
konvergierende Fixpunkt-Gleichung

Abb. konvergierende Fixpunkt-Gleichung
im Intervall (0,∞]


Beide Grafen stimmen in den zwei Kreuzungspunkten überein! Überprüfen wir beide Möglichkeiten auf ihr Konvergenzverhalten. Dazu bilden wir jeweils die ersten Ableitungen nach x und suchen die Bereiche, in denen die jeweiligen Kontraktionskonstante λ < 1 sind:
()
Formel
sowie
()
Formel
Aus bzw. folgt, dass jede Fixpunkt-Gleichung einen Bereich mit λ < 1 aufweist, jedoch an verschiedenen Stellen. So können beide Fixpunkte der und damit die gesuchten Nullstellen der aufgefunden werden. Als geeigneter Startwert für die Iterationen können die Werte x10 = 0 und x20 = 1 gewählt werden.

Eine intuitive Herangehensweise besteht darin, dass aus der gegebenen Funktion nach diejenigen Summanden separiert werden, die bei einem bestimmten Startwert den größten Einfluss auf die Summe nehmen. In unserem Beispiel wäre das der Summand 2·x für x < 0. Dort liefert die Exponentialfunktion ex vergleichsweise kleine Werte, so dass die Kontraktion bei dieser Fixpunktgleichung () im Intervall x < 0 sicher zu sein scheint. Analoge Überlegungen können dann für das Intervall x > 0 angestellt werden.

Für die konkrete Lösung einer Fixpunkt-Aufgabe besteht wohl die größte Herausforderung darin, eine geeignete Fixpunkt-Funktion sowie einen geeigneten Startwert zu finden. Beides fordert die Intuition des Programmierers heraus. Damit er aber die Überprüfung der Kontraktion nicht auf dem Papier zu machen braucht, wird in der Implementation eine Berechnung und Überprüfung der Kontraktionskonstanten λ < 1 durchgeführt. Dazu ist natürlich die Eingabe der Fixpunkt-Funktion φ(x) und deren erste Ableitung dφ(x)/dx = λ erforderlich ().



Abb. Programmauszug Fixpunkt-Iteration

In diesem Beispiel sollen die Nullstellen der nicht­linearen Funktion y = 2 2 x e x bestimmt werden. Da dies in geschlossener Form nicht möglich ist, wird hier die Fixpunkt-Iteration eingesetzt. Eine überschlägige Rechnung zeigt, dass diese Funktion zwei Null­stellen, also zwei Fixpunkte aufweist. Ebenso gibt es zwei mögliche Fixpunkt-Gleichungen. In der Grafik sind die beiden möglichen Fixpunkt-Gleichungen und je ein Startwert (grüner bzw. roter Punkt) dargestellt. Die Startpunkte können mit der Maus bewegt werden. Inwieweit die Startpunkte zu konver­gierenden Lösungen führen, kann anhand der Werte der Kontraktions­konstanten λ überprüft werden. Schließlich werden die Anzahlen der erforderlichen Iterationen n und ein absoluter Fehler angezeigt.
download processing
download p5.js
run program


Ergebnisdiskussion: Zunächst wird die Nullstellen-Aufgabe in alle Fixpunktgleichungen, die die Nullstellen-Aufgabe umfasst, umgewandelt. Dadurch ergeben sich zwei Iterations-Aufgaben, für jede Fixpunktgleichung eine. Bevor die Iteration beginnen kann, wird die Kontraktionsfähigkeit für den vorgegebenen Startwert x0 überprüft. Im Ergebnis liegt eine Kontraktionskonstante λ vor. Ist diese < 1 kann die Iteration erfolgversprechend durchgeführt werden. In der Grafik sind die Startpunkte grün bzw. rot markiert und können mit der Maus verschoben werden. Dabei können die Grenzen der Konvergenzbereiche ausgetestet werden. Schließlich wir die erreichte Genauigkeit dadurch überprüft, dass die gefundenen Nullstellen (also die Fixpunkte) in die ursprünglich zu lösende Nullstellen-Aufgabe eingesetzt werden. Jetzt müssten die Ergebnisse = 0 ergeben. Die Abweichung hiervon ist dem Iterationsfehler proportional.

Mehrdimensionale Funktionen

Die Fixpunktitaration kann auch zur Lösung nichtlinearer Gleichungssysteme herangezogen werden. Zu diesem Zweck wird für jede der Variablen qi eine Fixpunktgleichung φi aufgestellt (). Alle anderen Variablen werden für genau diese Fixpunktgleichung als Konstanten angesehen. Natürlich gibt es auch für jede der Fixpunktgleichungen einen eigenen Startwert q0i für die Iteration.
()
Formel
Um zu prüfen, ob die Fixpunktgleichungen und die gewählten Startwerte zu einer Konvergenz führen, müssen für jede der Gleichungen die Kontraktionskonstante λi < 1 sein ().
()
Formel
Eine typische Anwendung der mehrdimensionalen Fixpunktiteration ist die Vorausberechnung des Treffpunktes oder des Augenblicks des Treffens zweier Objekte, die sich unabhängig voneinander bewegen. Wie z.B. der Kanonenritt des Barons von Münchhausen. Die Lügengeschichte ist schnell erzählt: Im Russisch-Türkischen Krieg von 1787-1792 wollte der Baron bei seinem Ritt auf der Kanonenkugel die türkischen Stellungen ausspionieren. Dazu ist er beim Abschuss einer Kanone auf die Kugel aufgesprungen und hat sich so in Richtung des türkischen Lagers tragen lassen. Um nun wieder zurück zu kommen hat er auf eine andere Kugel, die ihm entgegen kam, umgesattelt. Nun ist uns klar, dass dieses Manöver einen exakten Abschuss der zweiten Kanonenkugel voraussetzt ().

Baron von Münchhausens Kanonenritt

Abb. Baron von Münchhausens Kanonenritt

Beide Bewegungen, Münchhausens aktuelle Kugel und die der noch abzuschießenden russischen Kugel, sind bekannt. Das sind die Bewegungsgleichungen des Schrägen Wurfs ( und ), wobei hier der Einfachheit halber die Luftreibung unbeachtet bleibt. Nun könnte der Treffzeitpunkt durch die Lösung des (nichtlinearen) Gleichungssystems direkt durch Gleichsetzung der Ortskoordinaten beider Bewegungsgleichungen vorausberechnet werden. Die Startzeit der russischen Kanonenkugel (auf die Münchhausen aufspringen will) tS ist natürlich abhängig von der Flugzeit der Kugel tK, auf der Münchhausen gerade sitzt, und der Zeit des Rendezvous tR ( und ). Für die Lösung des Gleichungssystems gibt es nun zwei mögliche Wege: Zunächst können im Eliminationsverfahren (klassischer Weg) die gesuchten Zeiten berechnet werden, indem eine quadratische Gleichung zu lösen ist (Details siehe nebenstehende step-by-step-Erklärung 1. Seite). Dieser Weg lässt aber die Lösung beliebiger nichtlinearer Gleichungssysteme nicht zu. Daher soll hier die andere Lösung mit Hilfe der Fixpunktiteration zum Vergleich ausgeführt werden (2. und 3. Seite).
step by step explanation

Zeitbezüge

Abb. Zeitbezüge entsprechend gemäß

Die und ergeben sich aus den Bedingungen für ein Rendezvous der beiden Kugeln. ergibt sich aus der Bedingung, dass ein Treffen stattfindet, wenn beide Kugeln die gleiche x-Koordinate aufweisen. Da die horizontale Bewegung nicht von der Gravitation beeinflusst wird, gestaltet sich die daraus resultierende Gleichung für den Zusammenhang zwischen der Flugdauer der ersten Kugel tK und der zweiten Kugel tB sehr einfach. Hingegen ergibt sich aus den Bewegungsgleichungen für die vertikale Bewegung ein komplizierterer Zusammenhang infolge der Gravitationswirkung (). stellt in diesem Zusammenhang die Beziehung zwischen den Zeiten tK und tB her und führt so auf die gesuchte Startzeit tS.
()
Formel
()
Formel
()
Formel
Wie ersichtlich, ist eine quadratische Gleichung, die zwei Lösungen aufweisen muss. Folglich gibt es zwei Fixpunkte, die zu ermittel sind. Die Aufgabe besteht nun darin, und in je eine Fixpunktgleichung umzustellen. Zur Ermittlung des ersten Fixpunktes separieren wir die Linearglieder der Variablen tK und tB: Aus kann durch einfaches Umstellen die Fixpunktgleichung ermittelt werden. In wird der lineare Summand separiert und führt so auf die zweite Fixpunktgleichung ():
()
Formel
()
Formel
Die Werte Δx und Δy entsprechen den Ortsdifferenzen der Startwerte beider Bewegungsgleichungen. Aus und können durch Differentiation der Fixpunktgleichungen φK und φB die Kontraktionskonstanten λK und λB ermittelt werden. Beide Konstanten müssen im Betrag < 1 sein.

Um den zweiten Fixpunkt bestimmen zu können, wird nun nach dem quadratischen Term aufgelöst (). kann unverändert übernommen werden, da in kein quadratischer Term vorliegt:
()
Formel
()
Formel
Auch bei diesem Fixpunkt können aus und durch Differentiation der Fixpunktgleichungen φK und φB die Kontraktionskonstanten λK und λB ermittelt werden. Wieder müssen beide Konstanten im Betrag < 1 sein.
()
Formel
()
zeigt einen Auszug aus der Implementation der zweidimensionalen Fixpunktiteration. Nach der Initialisierung der beiden Variablen tK und tR mit Startwerten wird eine for-Schleife gestartet, in der beide Fixpunktgleichungen gemeinsam zur Verbesserung der Genauigkeit der Variablen iteriert werden. Abgebrochen wird diese Schleife, wenn entweder beide Variablen mit der geforderten Genauigkeit vorliegen oder die maximale Anzahl n von Iterationen überschritten wird. In diesem Fall ist die Fixpunktiteration gescheitert und eine Fehlermeldung wird generiert.



Abb. Programmauszug zweidimensionale Fixpunktiteration

Im Kapitel Flugdauer bis zum Erreichen einer bestimmten Höhe wird ein gleich geartetes Problem untersucht. Diese Aufgabenstellung ist nicht trivial. Beim Rendezvous eines Versorgungs­raumschiffs mit der ISS liegt eine etwas kompliziertere Aufgabe vor, denn hier ist zusätzlich noch die Luftreibung zu berücksichtigen, auch hat die Bewegungsgleichung des Versorgungs­raumschiffs dank des Raketen­antriebs einen anderen Charakter als der schräge Wurf vorgibt. So ist das zu lösende nichtlineare Gleichungs­system nicht mehr so einfach zu lösen, wie das quadratische Gleichungssystem im Falle Münchhausens.

Das Beispielprogramm basiert auf dem Münchhausen-Fall. Zunächst werden die Rendezvous-Zeiten tRend 1 und tRend 2 auf herkömmlichem (Lösung der quadratischen Gleichung nach dem Wurzelsatz von VIETA) Weg und durch Fixpunktiteration gefunden. Gleiches gilt für die Berechnung der Startzeiten tStart 1 und tStart 2 der russischen Kugel. Da es bei einer quadratischen Gleichung immer zwei Lösungen gibt, werden auch beide Lösungen berechnet, aber nur die Lösung mit der berechneten kürzesten Zeit weiterverwendet.
download processing
download p5.js
run program
Vor dem Start des Programms werden, nachdem Du mittels des roten (Münchhausens Kugel) und des blauen (russische Kuge) Vektors Startgeschwindigkeit und -richtung festgelegt hast, alle erforderlichen Zeiten berechnet.
Nach dem START werden die Bewegungen der beiden Kugeln berechnet und auch als Spuren dargestellt. Die russische Kugel startet um die berechnete Verzögerung versetzt.

Ergebnisdiskussion: Mit relativ wenigen Iterationsschritten können die beiden Fixpunkte verglichen mit der "klassischen" Lösung sehr genau berechnet werden. Die Startwerte für tM = 1 und tR = 1 liefern über den gesamten Anwendungsbereich (Richtwinkel der Kanone im Bereich von α = 60° ... 120°) konvergierende Fixpunktgleichungen. Da die Fixpunktgleichung abgeleitet aus der Bedingung für die x-Koordinate eine lineare Abhängigkeit der beiden Zeiten aufweist, ist die Kontraktionskonstante stets λM = 0). Die zweite Kontraktionskonstante λR) wird angegeben.
Beim schrägen Wurf handelt es sich um quadratische Gleichungen, daher gibt es stets zwei Lösungen, d.h. zwei Schnittpunkte der Flugbahnen. Wobei im praktischen Fall die spätere oder gar negative Startzeit irrelevant ist. Die frühere Lösung ist die zutreffende! Auch die Zeiten für die Rendezvous werden berechnet, auch wenn sie hier wenig Aussagekraft besitzen.
Für die praktische Anwendung in einem Spiel sollten noch verschiedene Tests eingefügt werden, um zwar mathematisch lösbare, aber praktisch unlösbare Situationen zu vermeiden. Z.B. führt ein zu kurzer Kanonenritt dazu, dass die Kugel noch vor dem russischen Lager auf dem Erdboden auftrifft, was einen sinnvollen Wechsel Münchhausens auf die russische Kugel unmöglich macht. Aber im mathematischen Sinn können sich auch die Wurfparabeln unterhalb der Erdoberfläche treffen.
Ein anderer Fall tritt ein, wenn die Startzeit negativ werden sollte. Dann müsste die russische Kugel bereits vor Spielbeginn gestartet werden, um Baron Münchhausen den Wechsel der Kugeln zu ermöglichen.