13. Kapitel
Lösung von nicht elementar lösbaren Aufgaben mittels numerischer Methoden
Bitte einen Augenblick Geduld
während das Programm geladen wird!
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:
()
()
Abb. Fixpunkt-Iteration (konvergierend)
Abb. nichtkonvergierende Iteration
()
In mathematischen Termini ausgrdrückt, muss die Fixpunkt-Funktion φ(x) kontrahierende Eigenschaften besitzen. Auf unsere Verhältnisse bezogen gilt
()
Gilt für das gesamte Intervall mit xo als obere und xu als untere Grenze
()
()
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:
()
()
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
()
()
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:
()
und
()
Abb. konvergierende Fixpunkt-Gleichung
im Intervall [-∞,0)
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:
()
sowie
()
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 nichtlinearen Funktion
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 Nullstellen, 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 konvergierenden
Lösungen führen, kann anhand der Werte der Kontraktionskonstanten
λ überprüft werden. Schließlich werden die Anzahlen der
erforderlichen Iterationen n und ein absoluter Fehler angezeigt.
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.
()
()
Abb. Baron von Münchhausens Kanonenritt
Abb. Zeitbezüge entsprechend gemäß
()
()
()
()
()
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:
()
()
()
()
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 Versorgungsraumschiffs 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 Versorgungsraumschiffs dank des Raketenantriebs einen anderen Charakter als der schräge Wurf vorgibt. So ist das zu lösende nichtlineare Gleichungssystem 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.
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.