13. Kapitel

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:

()

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:

()

Die Iteration wird mit einem Startwert x₀ begonnen und die Funktion φ(x₀) gibt den Wert x₁ 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 x_n so weit an den wirklichen Fixpunkt herangerückt, dass er diesem bis auf einen Restfehler |φ(x_n) - x*| entspricht. In diesem Fall war die Iteration konvergent

Abb. Fixpunkt-Iteration (konvergierend)

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

()

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

()

Worin λ < 1 die Kontraktionskostante, auch als LIPSCHITZ-Konstante bezeichnet, ist.

Gilt für das gesamte Intervall mit x_o als obere und x_u als untere Grenze

()

so kann jeder beliebige Wert x dieses Intervalls als Startwert x₀ für eine konvergierende Iteration verwendet werden. Mit

()

kann gezeigt werden, dass mit jedem Iterationsschritt ein Zuwachs an Genauigkeit verbunden ist. Wenn im n-ten Schritt die Abweichung vom wirklichen Fixpunkt noch x_n - x* betrug, beträgt sie im Folgeschritt nur noch λ·(x_n - 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 x₀ und x₁ (deshalb A-priori) sowie die Kontraktionskonstante λ benötigt:

()

Wohingegen aus der A-posteriori-Fehlerabschätzung (d.h. nach der Berechnung) eine Abbruchbedingung für die Iteration ableiten lässt. Ist nämlich

()

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

()

und gesucht sei der x-Wert, bei dem y = -2 wird. Das ist eine klassische Nullstellenaufgabe, ...

()

... 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 x₁ = -0,7 und bei x₂ = 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:

()

und

()

Einmal durch einfaches Auflösen des Produktes 2·x (), das andere mal durch Logarithmieren der Exponentialfunktion e^x (). Die zugehörigen Fixpunkt-Grafen sind in den und zu sehen.

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

()

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 x₁₀ = 0 und x₂₀ = 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 e^x 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

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 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 x₀ ü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 q_i 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 q0_i für die Iteration.

()

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 ().

()

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 ().

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) t_S ist natürlich abhängig von der Flugzeit der Kugel t_K, auf der Münchhausen gerade sitzt, und der Zeit des Rendezvous t_R ( 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).

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 t_K und der zweiten Kugel t_B 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 t_K und t_B her und führt so auf die gesuchte Startzeit t_S.

()

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 t_K und t_B: Aus kann durch einfaches Umstellen die Fixpunktgleichung ermittelt werden. In wird der lineare Summand separiert und führt so auf die zweite Fixpunktgleichung ():

()

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:

()

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.

()

zeigt einen Auszug aus der Implementation der zweidimensionalen Fixpunktiteration. Nach der Initialisierung der beiden Variablen t_K und t_R 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 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 t_{Rend 1} und t_{Rend 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 t_{Start 1} und t_{Start 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.

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 t_M = 1 und t_R = 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.

Symbol	Bedeutung
φ(x) / φ(q_i)	Funktion / mehrdimensionale Funktion der Fixpunktgleichung
x / q_i	Variable / mehrdimensionale Variable der Fixpunktgleichung
λ	Kontraktionskonstante
v	Geschwindigkeit [m/s]
t	Zeit [s]
dt	Zeitquant, Bildwechseldauer [s]