Newton-Verfahren für Gleichungssysteme

Studium

J_F(x^{(k)})\,\Delta x^{(k)} = -F(x^{(k)}), \qquad x^{(k+1)} = x^{(k)} + \Delta x^{(k)}

Voraussetzung: $F: \mathbb{R}^n \to \mathbb{R}^n$ $stetig$ $differenzierbar$ $,$ $J_F(x^{(k)})$ $invertierbar$

$F$: Funktion, deren Nullstelle F(x) = 0 gesucht ist
$x^{(k)}$: Näherungsvektor nach k Schritten
$J_F$: Jacobi-Matrix von F, Matrix der partiellen Ableitungen ∂F_i/∂x_j
$\Delta x^{(k)}$: Korrekturvektor im k-ten Schritt

Das Newton-Verfahren für Systeme ersetzt F durch seine Linearisierung und löst in jedem Schritt ein lineares Gleichungssystem.

Erklärung

Das Newton-Verfahren für Gleichungssysteme sucht eine Nullstelle von $F(x) = 0$ mit $n$ Gleichungen und $n$ Unbekannten. Wie im eindimensionalen Fall ersetzt man $F$ in der Nähe der aktuellen Näherung durch seine Linearisierung

F(x^{(k)} + \Delta x) \approx F(x^{(k)}) + J_F(x^{(k)})\,\Delta x

und setzt sie null. Die Rolle von $f'$ übernimmt die Jacobi-Matrix $J_F$ mit den Einträgen $\frac{\partial F_i}{\partial x_j}$ .

Formal ist $x^{(k+1)} = x^{(k)} - J_F(x^{(k)})^{-1} F(x^{(k)})$ . Man berechnet die Inverse aber nicht, sondern löst in jedem Schritt das lineare Gleichungssystem für $\Delta x^{(k)}$ , z.B. mit LU-Zerlegung.

Eigenschaften:

Quadratische Konvergenz, wenn der Startwert nahe genug an einer Nullstelle liegt und die Jacobi-Matrix dort invertierbar und Lipschitz-stetig ist.
Ohne guten Startwert kann das Verfahren divergieren. Abhilfe schafft eine Dämpfung: $x^{(k+1)} = x^{(k)} + \tau\,\Delta x^{(k)}$ mit $0 < \tau \leq 1$ .
Pro Schritt muss man die Jacobi-Matrix aufstellen und ein lineares System lösen. Vereinfachte Varianten verwenden dieselbe Matrix für mehrere Schritte.

Abbruch typischerweise, wenn $\|\Delta x^{(k)}\|$ oder $\|F(x^{(k)})\|$ klein genug ist.

Beispiele

Gesucht ist eine Lösung von

F(x, y) = \begin{pmatrix} x^2 + y - 3 \\ x + y^2 - 5 \end{pmatrix} = 0, \qquad J_F(x, y) = \begin{pmatrix} 2x & 1 \\ 1 & 2y \end{pmatrix}

Eine Lösung ist $(1, 2)$ . Start bei $(1, 1)$ : $F = (-1;\ -3)$ , und das System

\begin{pmatrix} 2 & 1 \\ 1 & 2 \end{pmatrix} \Delta = \begin{pmatrix} 1 \\ 3 \end{pmatrix}

hat die Lösung $\Delta = \left(-\frac{1}{3};\ \frac{5}{3}\right)$ . Neue Näherung: $\left(\frac{2}{3};\ \frac{8}{3}\right) \approx (0{,}6667;\ 2{,}6667)$ .

Zweiter Schritt: $F = \left(\frac{1}{9};\ \frac{25}{9}\right)$ , die Jacobi-Matrix ist $\begin{pmatrix} 4/3 & 1 \\ 1 & 16/3 \end{pmatrix}$ . Das System hat die Lösung $\Delta = \left(\frac{59}{165};\ -\frac{97}{165}\right)$ , also

x^{(2)} = \left(\frac{169}{165};\ \frac{343}{165}\right) \approx (1{,}0242;\ 2{,}0788)

Der größte Komponentenfehler ist $0{,}079$ (in $y$ ). Ein weiterer Schritt drückt ihn auf etwa $0{,}0016$ , der nächste auf etwa $7 \cdot 10^{-7}$ : Die Zahl der richtigen Stellen verdoppelt sich ungefähr.

Typische Fehler

Das Vorzeichen vergessen: Rechts steht $-F(x^{(k)})$ , nicht $F(x^{(k)})$ .
Zeilen und Spalten der Jacobi-Matrix vertauschen. Zeile $i$ enthält die Ableitungen von $F_i$ nach allen Variablen.
Die Inverse der Jacobi-Matrix explizit berechnen. Das ist teurer und numerisch ungünstiger als das Lösen des Systems.
Bei einer (fast) singulären Jacobi-Matrix weiterrechnen. Dann ist der Schritt nicht oder nur ungenau bestimmt.

Newton-Verfahren für Gleichungssysteme