Kapitel 6

Eine nichtlineare Gleichung hat oft keine einfache algebraische Lösung. (Zum Beispiel $e^{-x} - x = 0$.) Deshalb verwenden wir iterative Methoden, die mit einem Punkt $x_0$ anfangen und aus den vorherigen Punkten eine immer bessere Lösung berechnen.

Wir wollen allgemein $x^\star$ finden mit $F(x^\star) = 0$.

Konvergenz

Eine iterative Methode konvergiert zur Lösung, falls gilt

und der Fehler in jeder Iteration ist

Falls die Methode konvergiert, können wir ihre Konvergenzordnung $p > 0$ feststellen falls

mit $C$ konstant. Das bedeutet, in der Unendlichkeit verändert sich der Fehler von Schritt zu Schritt mit Potenz $p$. Wenn $p=1$ sagen wir lineare Konvergenz, für grössere $p$ superlinear. Falls $p=2$ konvergiert die Methode quadratisch. Quadratische Konvergenz bedeutet, dass sich die Anzahl der korrekten Ziffern in der Approximation bei jeder Iteration verdoppeln.

Mit Hilfe der Dreiecksungleichung können wir den Fehler abschätzen. Für lineare Konvergenz mit Rate $L$ gilt

Abbruch

Wenn wir zu lange iterieren, überwiegen Rundungsfehler und wir verschwenden zeit. Deshalb wollen wir unsere Methode irgendwann abbrechen. Zwei mögliche Abbruchkriterien sind der absolute Fehler

und der relative Fehler

Meistens werden beide kombiniert

Gute Wahlen sind $\epsilon_{abs}=10^{-8}$ und $\epsilon_{rel}=10^{-6}$.

Eine andere Möglichkeit ist da Residuum $r_k = F(x_k)$. Wir stoppen dann, falls

Das heisst, wir sind nahe genug an null dran. Aber diese Methode kann auch schiefgehen, falls die Funktion eine beinahe-Nullstelle hat, bei der wir stoppen.

Intervallhalbierungsverfahren

Falls die Funktion $f$ stetig ist und gilt $f(a) * f(b) < 0$, dann gibt es eine Nullstelle auf dem Intervall $[a,b]$. Wir können das verwenden, um ähnlich wie bei binary-search, in jeder Iteration das Intervall zu halbieren

Falls $f(a_k) * f_m < 0$ liegt die Nullstelle im linken Teil und wir setzen $a_{k+1} = a_k, \space b_{k+1} = m_k$. Ansonsten liegt es im rechten Teil und wir arbeiten auf $[m_k, b_k]$ weiter.

Da wir das Intervall in jedem Schritt halbieren, konvergiert die Methode linear mit

und wir können absolute Genauigkeit $\epsilon_{abs}$ mit der Wahl $k \geq \log_2((b_0-a_0)/\epsilon_{abs})$ erreichen.

Die Methode konvergiert immer (für geeignete Startpunkte), aber langsamer als andere Methoden (wie Newton).

Fixpunkt-Methode

Ein Fixpunkt ist ein Vektor $x^\star$ sodass $\Phi(x^\star) = x^\star$. Anstatt die Lösung $F(x)=0$ zu finden, können wir das Problem zur Gleichung $\Phi(x) = x$ umschreiben und den Fixpunkt suchen. Falls

ist die Fixpunktiteration konsistent. Unsere Iteration wird dann

Diese Methode konvergiert lokal und mindestens linear, falls

Falls $|\Phi'(x^\star)| = 1$ kann beides passieren und ansonsten divergiert sie. Wir können die Konvergenz am Fixpunkt also überprüfen, indem wir die erste Ableitung berechnen. In höheren Dimensionen ist die Bedingung $\| D\Phi(x^\star)\| < 1$ (Norm der Jacobi-Matrix).

Wenn $\Phi$ (m+1)-mal differenzierbar ist und gilt

dann konvergiert sie lokal mit Ordnung mindestens $m+1$.

Newton-Verfahren

Wir verwenden die erste Taylor-Approximation und bekommen das Newton-Update

was wie eine Fixpunkt-Methode mit $\Phi(x) = x - f(x)/f'(x)$ ist. Wenn wir die Ableitung ausrechnen, bekommen wir

und somit ist $\Phi(x^\star) = 0$. Das bedeutet, Newton konvergiert lokal quadratisch. Newton kann aber auch fehlschlagen, falls $f'(x^\star) \approx 0$, der Startpunkt sehr weit weg ist, oder die Funktion nicht differenzierbar ist. Die Newton-Methode funktioniert also nicht global und kann für schlechte Startpunkte irgendwo anders hinspringen.

Sekantenverfahren

Wir wollen (oder können) die Ableitung der Funktion für das Newton-Verfahren nicht auswerten. Stattdessen approximieren wir sie durch die Sekante

und erhalten ein neues Verfahren

Die Konvergenzordnung des Sekantenverfahrens ist $p \approx 1.6$ (der goldene Schnitt), also konvergiert sie superlinear.

Mehrdimensionales Newton-Verfahren

Wir müssen jetzt einen Vektor $x^\star$ finden, sodass $F(x^\star)=0$. Wieder durch Taylor erhalten wir die Iteration

wobei $J_F(x)$ die Jacobi-Matrix von $F$ ist. Wir sollten aber das inverse einer Matrix niemals manuell ausrechnen. Stattdessen lösen wir

und setzen

Wir müssen also in jeder Iteration ein $n \times n$ System lösen, was sehr teuer werden kann.

Die Methode konvergiert lokal quadratisch, falls sie zweimal stetig differenzierbar bei $x^\star$ und die Jacobi-Matrix invertierbar ist.

Gedämpftes Newton-Verfahren

Das Newton-Verfahren springt manchmal zu weit und divergiert für Ausgangspunkte nicht nahe an der Lösung. Deshalb dämpfen wir jeden Schritt mit einem Dämpfungsfaktor $\alpha_k$

Je kleiner der Dämpfungsfaktor, desto langsamer nähert sich das Verfahren der Lösung an, aber desto höher ist die Wahrscheinlichkeit, dass es auch konvergiert.

Eine gute Methode, um $\alpha_k$ zu wählen, ist zuerst mit $\alpha_k = 1$ zu starten. Solange das Verfahren $|f(x_{k+1})|$ erhöht, verkleinern wir den Faktor (zum Beispiel halbieren), solange bis wir uns der Lösung annähern.

Broyden-Quasi-Newton

Anstatt die (teure und möglicherweise schlecht konditionierte) Jacobi-Matrix in jeder Iteration zu berechnen, wollen wir sie approximieren. Die Jacobi-Matrix $J_k$ für jeden Schritt sollte

erfüllen. Wir suchen uns die Matrix (aus allen möglichen) aus, welche am nähesten an der alten ist, also $\| J_k - J_{k-1} \|_F$ minimiert. Übrigens ist die Frobeniusnorm

Unsere neue Jacobi-Matrix ist in jedem Schritt also

mit $s_k = x_k - x_{k-1}$ und $y_k = F(x_k) - F(x_{k-1})$.