6  Iterationsverfahren für nichtlineare Gleichungen

6.1 Newton-Verfahren

  1. Wähle den Startwert \(x^0 \in D\) und die Fehlertoleranz \(\varepsilon\). Setze \(k := 0\).
  2. Falls \(|F(x^k)| < \varepsilon\): STOP.
  3. Berechne die Newton-Korrektur \(d^k\): Löse \[ F'(x^k) \cdot d^k = -F(x^k) \]
  4. Setze
    \[ x^{k+1} = x^k + d^k \]
    und \(k := k + 1\). Gehe dann zu S1).

Somit handelt es sich um eine Fixpunktiteration mit \[ \Phi(x) = x - F'(x)^{-1} F(x). \] wobei \(F'(x)=DF=\nabla F\) die Jacobi-Matrix von \(F\) in \(x\) ist.

Tipp(6.2) Satz

Sei \(D \subset \mathbb{R}^N\) offen, \(F \in C^1(D, \mathbb{R}^N)\) und \(x^* \in D\) mit \(F(x^*) = 0_N\). Falls ein \(B \in \mathbb{R}^{N \times N}\) mit \[ \rho(I - BF'(x^*)) < 1 \] existiert, dann ist die Fixpunktiteration \[ x^{k+1} = \Phi(x^k) \] mit \[ \Phi(x) = x - BF(x) \] lokal linear konvergent, d. h. es existiert ein \(\delta > 0\), \(C > 0\) und \(\theta \in (0,1)\) mit \[ |x^k - x^*| \leq C\theta^k |x^* - x^0| \] für alle \(x^0 \in B(x^*, \delta)\).

  1. Das Newton-Verfahren ist lokal quadratisch konvergent, falls \(F'(x^*)\) regulär ist.
  2. Das Newton-Verfahren konvergiert nur in der Nähe der Lösung.