Konvergenzordnung

Studium

|x_{k+1} - x^*| \leq C\,|x_k - x^*|^p

Voraussetzung: $p \geq 1,$ $C > 0,$ $C < 1$ $falls$ $p = 1,$ $k \geq k_0$

$x_k$: Näherung nach k Iterationsschritten
$x^*$: gesuchter Grenzwert, z.B. eine Nullstelle
$p$: Konvergenzordnung
$C$: Konstante; bei p = 1 die Konvergenzrate
$k_0$: Index, ab dem die Ungleichung gilt

Die Konvergenzordnung p gibt an, wie schnell der Fehler eines Iterationsverfahrens von Schritt zu Schritt schrumpft.

Erklärung

Die Konvergenzordnung beschreibt, wie schnell eine Folge von Näherungen $x_k$ gegen den Grenzwert $x^*$ läuft. Mit dem Fehler $e_k = |x_k - x^*|$ heißt das Verfahren konvergent von der Ordnung $p$ , wenn ab einem Index $e_{k+1} \leq C\,e_k^p$ gilt.

Linear ( $p = 1$ , $C < 1$ ): Der Fehler wird pro Schritt um den Faktor $C$ kleiner. Man gewinnt pro Schritt etwa $-\log_{10} C$ Dezimalstellen.
Superlinear: $\frac{e_{k+1}}{e_k} \to 0$ , also schneller als jede lineare Rate.
Quadratisch ( $p = 2$ ): Die Zahl der richtigen Stellen verdoppelt sich ungefähr in jedem Schritt.

Typische Werte:

Verfahren	Ordnung
Bisektion	linear mit $C = \frac{1}{2}$ (Fehlerschranke)
Fixpunktiteration	linear mit $C \approx \lvert g'(x^) \rvert$ , falls $g'(x^) \neq 0$
Sekantenverfahren	$p = \frac{1 + \sqrt{5}}{2} \approx 1{,}618$
Newton-Verfahren	$p = 2$ bei einfacher Nullstelle

Aus drei aufeinanderfolgenden Fehlern lässt sich $p$ schätzen:

p \approx \frac{\ln(e_{k+1} / e_k)}{\ln(e_k / e_{k-1})}

Die Ordnung gilt asymptotisch, also nahe am Grenzwert. Weit weg vom Ziel kann ein Verfahren hoher Ordnung langsam sein oder gar nicht konvergieren.

Beispiele

Newton-Verfahren für $x^2 - 2 = 0$ , also $x_{k+1} = \frac{1}{2}\left(x_k + \frac{2}{x_k}\right)$ , ab $x_0 = 1$ :

$k$	$x_k$	Fehler $e_k$
1	1,5	0,0858
2	$\frac{17}{12} \approx 1{,}416667$	0,0025
3	$\frac{577}{408} \approx 1{,}414216$	$2{,}1 \cdot 10^{-6}$

Die Schätzformel mit $e_1$ , $e_2$ , $e_3$ ergibt $p \approx 1{,}98$ , also quadratische Konvergenz. Die Konstante ist $C = \left|\frac{f''(x^*)}{2 f'(x^*)}\right| = \frac{1}{2\sqrt{2}} \approx 0{,}35$ .

Die Fixpunktiteration $x_{k+1} = \frac{x_k}{2} + 1$ hat den Fixpunkt $2$ , und es gilt exakt $x_{k+1} - 2 = \frac{1}{2}(x_k - 2)$ . Das ist lineare Konvergenz mit $C = 0{,}5$ : Pro Schritt gewinnt man nur etwa $0{,}3$ Dezimalstellen.

Typische Fehler

Bei $p = 1$ die Bedingung $C < 1$ vergessen. Mit $C \geq 1$ muss der Fehler nicht kleiner werden.
Die Ordnung aus den ersten, noch weit entfernten Schritten schätzen. Die Schätzung wird erst nahe am Grenzwert verlässlich.
Quadratische Konvergenz von Newton auch bei mehrfachen Nullstellen erwarten. Dort konvergiert das Verfahren nur linear.
Ordnung und Aufwand verwechseln: Das Sekantenverfahren hat eine kleinere Ordnung als Newton, braucht aber keine Ableitung und pro Schritt nur eine Funktionsauswertung.

Konvergenzordnung