4.3. Konvergenzgeschwindigkeit

Um zu beschreiben wie schnell die Folge von Punkten \((x_k)_{k\in \mathbb{N}}\) eines Iterationsverfahrens \(x_{k+1} = G(x_k)\) gegen einen Fixpunkt \(\overline{x}\) konvergiert verwenden wir den Begriff der Konvergenzgeschwindigkeit, den wir im Folgenden definieren wollen.

Definition 4.2 (Konvergenzgeschwindigkeit)

Sei \(X\) ein Banachraum, d.h. ein vollständiger normierter Vektorraum. Wir sagen, dass eine Folge von Punkten \((x_k)_{k\in\mathbb{N}} \subset X\) mit \(\lim_{k\rightarrow \infty} x_k = \overline{x}\) gegen einen Punkt \(\overline{x} \in X\) mindestens mit Ordnung \(p \geq 1, p\in \mathbb{N}\) konvergiert, falls es ein \(C > 0\) und ein \(N \in \mathbb{N}\) gibt, so dass für alle \(k \geq N\) gilt

\[||x_{k+1} - \overline{x}|| \ \leq \ C ||x_k - \overline{x}||^p.\]

Im Fall \(p = 1\) spricht man von linearer Konvergenz und für \(p=2\) von quadratischer Konvergenz.

Ein weiterer interessanter Spezialfall liegt vor, falls es eine gegen Null konvergente Zahlenfolge \((c_k)_{k\in\mathbb{N}}\) gibt, so dass man zeigen kann, dass gilt:

\[||x_{k+1} - \overline{x}|| \ \leq \ c_k||x_{k} - \overline{x}||.\]

In diesem Fall sprechen wir von superlinearer Konvergenz.

Bemerkung 4.3 (Konvergenzfaktor)

Im Fall von linearer Konvergenzgeschwindigkeit, d.h. für \(p=1\) muss man in Definition Definition 4.2 zusätzlich fordern, dass für die Konstante \(C < 1\) gilt. Diese Konstante wird auch Konvergenzfaktor genannt und es ist klar, dass eine Folge umso schneller konvergiert, je kleiner der Konvergenzfaktor \(C\) ist. In diesem Fall entspricht der Konvergenzfaktor \(C\) der Kontraktionskonstanten \(q < 1\) aus Definition 4.1, da

\[\Vert G(x_k) - G(\overline{x}) \Vert \ = \ \Vert x_{k+1} - \overline{x} \Vert \ \leq \ C \Vert x_k - \overline{x}\Vert \ = \ q \Vert x_k - \overline{x} \Vert.\]

Um die Konvergenzgeschwindigkeit eines Iterationsverfahrens \(x_{k+1} = G(x_k)\) zu analysieren können wir die Taylorentwicklung von \(G\) um den Fixpunkt \(\overline{x}\) betrachten, falls \(G\) genügend oft in \(\overline{x}\) differenzierbar ist. Hierbei spielen die Ableitungen des Iterationsverfahrens eine wichtige Rolle für die Konvergenzgeschwindigkeit, wie das folgende Theorem aussagt.

Satz 4.3 (Konvergenzgeschwindigkeit)

Sei \(U(\overline{x}) \subset \mathbb{R}\) eine lokale Umgebung von \(\overline{x}\) und sei \(G \colon \mathbb{R} \rightarrow \mathbb{R}\) ein in \(U(\overline{x})\) konvergentes Iterationsverfahren mit \(\lim_{k\rightarrow \infty} G(x_k) = \overline{x}\) für eine Folge \((x_k)_{k\in\N} \subset U(\overline{x})\).

Falls \(G\) in der lokalen Umgebung \(U(\overline{x})\) mindestens \(p\)-Mal stetig differenzierbar ist für \(p\geq 1, p\in \mathbb{N}\) und außerdem für die Ableitungen von \(G\) in \(\overline{x}\) gilt:

\[G^{(j)}(\overline{x}) \: = \: 0, \quad \forall \: j=1,\ldots,p-1,\]

so konvergiert das Iterationsverfahren mindestens mit Ordnung \(p\).

Proof. Sei \(x_k \in U(\overline{x})\) ein Punkt der konvergenten Folge \((u_k)_{k \in \N}\). Dann betrachten wir die Taylorentwicklung von \(G(x_k)\) im Fixpunkt \(\overline{x}\) und erhalten

\[\begin{split} |x_{k+1} - \overline{x}| \ &= \ |G(x_k) - \overline{x}| \ = \ \left|\sum_{j=0}^\infty G^{(j)}(\overline{x})\frac{(x_k-\overline{x})^j}{j!} - G(\overline{x}) \right| \\ \ &= \ \Bigl|\underbrace{G(\overline{x})\cdot 1 - G(\overline{x})}_{=0} \: + \: \underbrace{G'(\overline{x})(x_k-\overline{x})}_{=0} \: + \: \ldots \: + \: \underbrace{G^{(p-1)}(\overline{x})\frac{(x_k-\overline{x})^{p-1}}{(p-1)!}}_{=0} \\ &\quad \ + \ G^{(p)}(\overline{x})\frac{(x_k-\overline{x})^{p}}{p!} + \mathcal{O}((x_k-\overline{x})^{p+1})\Bigr| \\ \ &= \ \Bigl|\frac{G^{(p)}(\overline{x})}{p!}(x_k-\overline{x})^{p} + \mathcal{O}((x_k-\overline{x})^{p+1})\Bigr| \ \leq \ \underbrace{\Bigl|\frac{G^{(p)}(\overline{x})}{p!}\Bigr|}_{ =: C} \cdot |x_k - \overline{x}|^p + \mathcal{O}(|x_k-\overline{x}|^{p+1}) \end{split}\]

Wenn wir die Terme höherer Ordnung vernachlässigen haben wir gezeigt, dass ein \(C > 0\) existiert, so dass gilt

\[|x_{k+1} - \overline{x}| \ \leq \ C |x_k - \overline{x}|^p.\]

Wir sehen also, dass das Iterationsverfahren \(x_{k+1} = G(x_k)\) in einer lokalen Umgebung \(U(\overline{x})\) mit Ordnung \(p\) gegen den Fixpunkt \(\overline{x}\) konvergiert. ◻

Bemerkung 4.4

Sei \(x_{k+1} = G(x_k)\) ein allgemeines Iterationsverfahren, das in einer Umgebung \(U(\overline{x})\) eines Fixpunktes \(\overline{x}\) differenzierbar ist. Falls \(0 < G'(\overline{x}) < 1\) gilt, so konvergiert das Iterationsverfahren linear und monoton gegen den Fixpunkt \(\overline{x}\).

Falls jedoch \(-1 < G'(\overline{x}) < 0\) gilt, so konvergiert das Iterationsverfahren linear und alternierend gegen den Fixpunkt \(\overline{x}\).

Wir können nun das hinreichende Kriterium aus Satz 4.3 anwenden, um die Konvergenzgeschwindigkeit des Newton-Verfahrens genauer zu untersuchen.

Korollar 4.2 (Konvergenzgeschwindigkeit des Newton-Verfahrens)

Betrachten wir im Folgenden das Newton-Verfahren zur Approximation einer Nullstelle \(F(\overline{x}) = 0\) der Funktion \(F \colon \mathbb{R} \rightarrow \mathbb{R}\) mit der Iterationsvorschrift

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

Hierbei nehmen wir an, dass die Funktion \(F\) in einer lokalen Umgebung \(U(\overline{x})\) der Nullstelle genügend häufig stetig differenzierbar ist.

Zur Analyse der Konvergenzgeschwindigkeit des Newton-Verfahrens in der lokalen Umgebung \(U(\overline{x})\) verwenden wir das Kriterium aus Satz 4.3. Hierfür berechnen wir die ersten Ableitungen von \(G\) im Fixpunkt \(\overline{x}\):

\[\begin{split} G'(x) \ &= \ 1 - \frac{(F'(x))^2 - F(x)F''(x)}{(F'(x))^2} \ = \ \frac{F(x)F''(x)}{(F'(x))^2} \\ G''(x) \ &= \ \frac{(F'(x)F''(x) + F(x)F'''(x))(F'(x))^2 - 2F(x)F''(x)F'(x)F''(x)}{(F'(x))^4} \end{split}\]

Betrachten wir nun die Ableitungen \(G'(x)\) und \(G''(x)\) des Iterationsverfahrens in der Nullstelle \(F(\overline{x}) = 0\), so sehen wir, dass gilt:

\[\begin{split} G'(\overline{x}) \ &= \ \frac{F(\overline{x})F''(\overline{x})}{(F'(\overline{x}))^2} \ = \ 0,\\ G''(\overline{x}) \ &= \ \frac{F'(\overline{x})F''(\overline{x})(F'(\overline{x}))^2}{(F'(\overline{x}))^4} \ = \ \frac{F''(\overline{x})}{F'(\overline{x})}. \end{split}\]

Es gilt also, dass \(G'(\overline{x}) = 0\) jedoch \(G''(\overline{x}) \not= 0\) im Allgemeinen. Somit können wir mit Satz 4.3 folgern, dass es eine lokale Umgebung \(U(\overline{x})\) gibt in der das Newton-Verfahren eine quadratische Konvergenzgeschwindigkeit aufweist.

Das Newton-Verfahren konvergiert lokal quadratisch gegen die Nullstelle \(F(\overline{x}) = 0\), wie wir im obigen Korollar festgestellt haben. Es gibt jedoch besondere Nullstellen, die wir im Folgenden definieren wollen.

Definition 4.3 (p-fache Nullstelle)

Sei \(p\geq 0, p \in \mathbb{N}\). Wir nennen \(\overline{x} \in \mathbb{R}\) eine \(p\)-fache Nullstelle einer Funktion \(F \colon \mathbb{R}^n \rightarrow \mathbb{R}^m\), falls gilt

\[F^{(j)}(\overline{x}) \ = \ 0, \quad \forall j=0,\ldots,p-1.\]

Im Fall einer \(p\)-fachen Nullstelle von \(F\) ändert sich das Konvergenzverhalten des Newton-Verfahrens überraschenderweise, wie das folgende Theorem besagt.

Satz 4.4 (Lineare Konvergenz bei p-facher Nullstelle)

Sei \(F \colon \mathbb{R} \rightarrow \mathbb{R}\) eine Funktion und \(\overline{x}\in \R\) eine \(p\)-fache Nullstelle von \(F\). Sei außerdem \(F\) in einer lokalen Umgebung \(U(\overline{x})\) von \(\overline{x}\) \(p\)-fach stetig differenzierbar.

Dann konvergiert das Newton-Verfahren für jeden Startwert \(x_0 \in U(\overline{x})\) nur linear gegen den Fixpunkt \(\overline{x}\).

Proof. Beweis. Sei \(\overline{x}\) eine \(p\)-fache Nullstelle der Funktion \(F\) mit \(p > 1\) und es gelte \(F^{(p)}(\overline{x}) \neq 0\). Sei weiterhin \(x \in U(\overline{x})\) ein Punkt in der lokalen Umgebung um die Nullstelle \(\overline{x}\). Aus der Taylorentwicklung in Satz 4.3 sehen wir, dass es eine differenzierbare Funktion \(g\) geben muss mit \(g(\overline{x}) \neq 0\), so dass lokal gilt:

\[\begin{split} F(x) \ &= \ (x - \overline{x})^p g(x), \\ F'(x) \ &= \ p(x - \overline{x})^{p-1} g(x) + (x - \overline{x})^p g'(x). \end{split}\]

Wir können somit das Newton-Verfahren umschreiben zu

\[\begin{split} G(x) \ = \ x - \frac{F(x)}{F'(x)} \ &= \ x - \frac{(x - \overline{x})^p g(x)}{p(x - \overline{x})^{p-1} g(x) + (x - \overline{x})^p g'(x)} \\ &= \ x- \frac{(x-\overline{x})g(x)}{p g(x) + (x-\overline{x})g'(x)}. \end{split}\]

Zur Bestimmung der Konvergenzgeschwindigkeit betrachten wir wieder die Ableitung \(G'(x)\) und erhalten:

\[\begin{split} G'&(x) \ = \\ &1 - \frac{(g(x)+(x-\overline{x})g'(x))(pg(x)+(x-\overline{x})g'(x))-(x-\overline{x})g(x)(pg'(x) + g'(x) + (x - \overline{x})g''(x))}{(p g(x) + (x-\overline{x})g'(x))^2} \end{split}\]

Glücklicherweise fallen viele Terme der Ableitung \(G'(x)\) weg im Fixpunkt \(\overline{x}\), so dass wir erhalten:

\[G'(\overline{x}) \ = \ 1 - \frac{p(g(\overline{x}))^2}{(pg(\overline{x}))^2} \ = \ 1 - \frac{1}{p} \ \neq \ 0.\]

Wir sehen also, dass im Fall einer \(p\)-fachen Nullstelle von \(F\) mit \(p > 1\) die erste Ableitung des Newton-Verfahrens nicht verschwindet. Daher erhalten wir nur lineare Konvergenz. ◻

Bemerkung 4.5

Die quadratische Konvergenz des Newton-Verfahrens lässt sich im Fall einer \(p\)-fachen Nullstelle von \(F\) in \(\overline{x}\) wiederherstellen indem man folgende Variante implementiert:

(4.5)\[x_{k+1} \ = \ G(x_k) \ = \ x_k - p\cdot \frac{F(x_k)}{F'(x_k)}.\]

Leider ist dieses Verfahren numerisch instabil, da es bei der Division von \(F\) und \(F'\) in (4.5) nahe der \(p\)-fachen Nullstelle zu Auslöschung kommt (siehe Rundungsfehler und Gleitkommaarithmetik).