4.5. Gauss–Newton Verfahren

Im Fall einer Funktion \(F: \R^n \rightarrow \R^m\) mit \(m > n\) lässt sich die Jacobi-Matrix \(F' \in \R^{m \times n}\) von \(F\) nicht invertieren, so dass wir das Newton-Verfahren aus Das Newton-Verfahren nicht zur Lösung der Gleichung \(F(x) = 0\) verwenden können.

Stattdessen versuchen wir wieder ein Kleinste-Quadrate Problem zu lösen der Form

(4.6)\[\min_{x \in \R^n} f(x) \ \coloneqq \ \frac{1}2 \Vert F(x) \Vert^2 .\]

Ein Minimierer \(\overline{x} \in \R^n\) von (4.6) muss offensichtlich die notwendige Bedingung erster Ordnung erfüllen, d.h.

\[f'(\overline{x}) \ = \ F'(\overline{x})^T F(\overline{x}) \ = \ 0.\]

Da \(f'\) eine Funktion ist mit \(f' \colon \R^n \rightarrow \R^n\) können wir nun das Newton-Verfahren anwenden. Da wir im Allgemeinen nicht von Regularität der Ableitungen von \(f'\) ausgehen können, liefert uns das Newton-Verfahren zunächst das folgende lineare Gleichungssystem:

\[f''(x_k) (x_{k+1} - x_k) \ = \ - f'(x_k).\]

Hier bezeichnet \(f''\) die Hesse-Matrix der Funktion \(f\) und es gilt

(4.7)\[f''(x) \ = \ F''(x)^T F(x) + F'(x)^T F'(x).\]

Währen der zweite Teil \(F'(x)^T F'(x)\) sicher positiv semi-definit ist, können wir wenig über den Term \(F''(x)^T F(x)\) aussagen. Deshalb approximiert man häufig die Hesse-Matrix nur durch den zweiten Term und führt somit das sogenannte Gauss–Newton Verfahren durch mit der Iterationsvorschrift

\[F'(x_k)^T F'(x_k) (x_{k+1} - x_k) \ = \ - F'(x_k)^T F(x_k).\]

Man beobachtet, dass das Verfahren insbesondere eine gute Approximation ist, falls sich (4.6) exakt zu Null lösen lässt, d.h. im Fall \(F(\overline{x}) = 0\). Hier gilt wegen (4.7) offensichtlich

\[f''(\overline{x}) = F'(\overline{x})^T F'(\overline{x}).\]

Mit Hilfe dieser Identität und der üblichen Taylor-Entwicklung können wir in diesem Fall die superlineare Konvergenz des Gauss–Newton Verfahrens nachweisen.

Bemerkung 4.7 (Varianten des Gauss–Newton Verfahrens)

Da das Matrixprodukt \(F'(x)^T F'(x)\) potentiell schlecht-konditioniert sein kann, ergibt sich daraus ein numerisches Problem für das Gauss–Newton Verfahren, denn hierdurch kann der Iterationsschritt \(x_{k+1}-x_k\) zu groß werden. Als Alternative können wir Verfahren der folgenden Form betrachten

\[B_k (x_{k+1} - x_k) \ = \ - F'(x_k)^T F(x_k),\]

mit geeigneten positiv definiten Matrizen \(B_k\).

Der einfachste Fall einer positiv definiten Matrix ist durch das Gradientenverfahren gegeben mit \(B_k \coloneqq \frac{1}\tau_k I\), d.h. wir erhalten die einfache Fixpunktiteration

\[x_{k+1} \ = \ x_k - \tau_k F'(x_k)^T F(x_k) \ = \ x_k - \tau_k f'(x_k).\]

Der Schrittweitenparameter \(\tau_k > 0\) kann so gewählt werden, dass zu große Schritte vermieden werden. Das Gradientenverfahren ist ein sogenanntes Abstiegsverfahren, d.h. es gilt für hinreichend kleine Schrittweiten \(\tau_k\) die folgende Abschätzung

\[f(x_{k+1}) \ = \ f(x_k - \tau_k f'(x_k)) \ = \ f(x_k) - \tau_k \Vert f'(x_k) \Vert^2 + o(\tau_k) < f(x_k).\]

Damit lässt sich gewährleisten, dass das Gradientenverfahren nicht gegen eine beliebige Lösung von \(f'(x) = 0\) konvergiert, sondern zumindest die Funktion \(f\) dabei reduziert.

Ein Kompromiss zwischen Gradienten- und Gauss–Newton-Verfahren ist das sogenannte Levenberg–Marquardt Verfahren, das gegeben ist durch:

\[(F'(x_k)^T F'(x_k) + \tau_k I ) (x_{k+1} - x_k) \ = \ - F'(x_k)^T F(x_k).\]

Um anfänglich zu große Schritte zu vermeiden, wählt man zunächst \(\tau_k > 0\) groß. Um asymptotisch die superlineare Konvergenz zu erhalten, sollte \(\tau_k\) dann im Verlauf der Iterationen gegen Null konvergieren.