Kurs:Numerik I/Konvergenzraten

Einleitung - Konvergenzraten

Die Verfahren, die wir bisher im Zusammenhang mit der Lösung linearer Gleichungssysteme und Ausgleichsprobleme vorgestellt haben, bestimmen in endlich vielen Schritten eine Lösung, welche, wenn man exakt rechnen könnte, immer die exakte Lösung des Problems wäre. In der Praxis lassen sich aber viele mathematische Probleme nur mittels eines Iterationsverfahrens näherungsweise lösen.

Iterationsverfahren

d. h. mittels wiederholter Anwendung derselben Rechenvorschriften, wobei in der $k$-ten Iteration („Wiederholung“), ausgehend von einer Näherung $x_k$, eine neue und möglichst genauere Näherung $x_{k+1}$ für eine gesuchte Lösung des Problems berechnet wird. Für den Start eines solchen Verfahrens muss man folglich eine Startnäherung $x^{*}$ vorgeben.

Iterationsverfahren würden im allgemeinen, wenn sie nicht nach endlich vielen Schritten abgebrochen würden, eine unendliche Folge $(x_k)$ von Iterierten generieren. Aufgabe des Numerikers ist es zu zeigen, dass jede konvergente Teilfolge oder die ganze vom Verfahren erzeugte Folge $(x_k)$ für jeden Startpunkt aus einer gewissen Menge gegen eine (ja a priori unbekannte!) Lösung $x^{*}$ des gegebenen Problems konvergiert. In diesem Zusammenhang spricht man von globaler Konvergenz eines Verfahrens, wenn diese Konvergenz für jede Wahl des Startpunktes aus einer wohlbestimmten Menge (z. B. dem ganzen ${ℝ}^n$) gegeben ist, und von lokaler Konvergenz, wenn dies nur für Startpunkte aus einer (im Allgemeinen nicht spezifizierbaren) Umgebung einer Lösung der Fall ist. In der Praxis wird ein Iterationsverfahren natürlich nach einer endlichen Anzahl von Iterationen gestoppt und zwar dann, wenn zum ersten Mal ein Abbruchkriterium erfüllt ist, welches ausreichende Genauigkeit der aktuellen Näherung im Hinblick auf eine Lösung des Problems sicherstellt. Die Angabe eines sinnvollen Abbruchkriteriums kann dabei durchaus ein schwieriges Unterfangen sein.

Für ein gegebenes Verfahren ist neben dem rechnerischen Aufwand, der pro Iteration zu leisten ist, naturgemäß von Interesse, wie schnell es, wenn es nicht abgebrochen würde, gegen eine gesuchte Lösung konvergieren würde und damit, ob im Schnitt nur wenige oder viele Iterationen durchlaufen werden müssen, bis ein gegebenes Abbruchkriterium erfüllt ist. Wir wollen daher als nächstes den Begriff der Konvergenzgeschwindigkeit eines Verfahrens genauer fassen.

Definition 5.1

Sei $\Vert \cdot \Vert$ eine Norm auf dem ${ℝ}^n$ und $(x^k)$ eine Folge in ${ℝ}^n$ mit $\underset{k\to \mathrm{\infty }}{\lim }{x}_k=x^{*}$.

(i) Die Folge $(x^k)$ konvergiert von (mindestens) der Ordnung $p>0$ (gegen $x^{*}\in {ℝ}^n$), wenn mit einem $k_0\in \mathbb{N}$ und einem $C>0$

(5.1) $\Vert x_{k+1}-x^{*}\Vert \le C{\Vert x_k-x^{*}\Vert }^p,k\ge k_0$

gilt, wobei $C<1$ für $p=1$ sei. Im Fall $p=1$ spricht man auch von linearer und im Fall $p=2$ von quadratischer Konvergenz.

(ii) Die Folge $(x^k)$ konvergiert superlinear (gegen $x^{*}\in {ℝ}^n$), wenn $x^k\ne x^{*},k\ge k_0$ für ein $k_0\in \mathbb{N}$ gilt sowie

(5.2) $\underset{k\to \mathrm{\infty }}{\lim }\frac{\Vert x_{k+1}-x^{*}\Vert }{\Vert x_k-x^{*}\Vert }=0.$

Die drei wichtigsten Konvergenzraten bei Algorithmen sind lineare, superlineare und quadratische Konvergenz, so dass wir uns im Folgenden nur auf sie beziehen werden.

Die (praktisch irrelevante) Voraussetzung „$x^k\ne x^{*},k\ge k_0$ für ein $k_0\in \mathbb{N}$“ bei der Definition der superlinearen Konvergenz kann man vermeiden, indem man diese mit einer Folge $({\epsilon }_k)$ von Zahlen ${\epsilon }_k\ge 0$ mit $\underset{k\to \mathrm{\infty }}{\lim }{\epsilon }_k=0$ durch

(5.3) $\Vert x_{k+1}-x^{*}\Vert \le {\epsilon }_k\Vert x_k-x^{*}\Vert ,k\ge k_1$

für ein $k_1\in \mathbb{N}$ definiert. Für $\underset{k\to \mathrm{\infty }}{\lim }{x}_k=x^{*}$ kann man superlineare Konvergenz der Folge $(x^k)$ auch durch die Beziehung

$\Vert x_{k+1}-x^{*}\Vert =o\left(\Vert x_k-x^{*}\Vert \right)$

ausdrücken und quadratische Konvergenz durch

$\Vert x_{k+1}-x^{*}\Vert =𝒪\left({\Vert x_k-x^{*}\Vert }^2\right).$

Beispiel 5.2

Die Folgen $(x_k),(y_k)$ und $(z_k)$ mit

$x_k:=1+0.5^k,y_k:=1+k^{-k},z_k:=1+0.5^{2^k}$

konvergieren für $k\to \mathrm{\infty }$ gegen $x^{*}=y^{*}=z^{*}:=1$. Man errechnet

$\frac{|x_{k+1}-x^{*}|}{|x_k-x^{*}|}=0.5,$

$\frac{|y_{k+1}-y^{*}|}{|y_k-y^{*}|}=\frac{k^k}{(k+1{)}^{k+1}}=\frac{1}{k+1}{\left(\frac{1}{1+\frac{1}{k}}\right)}^k\to 0(k\to \mathrm{\infty }),$

$\frac{|z_{k+1}-z^{*}|}{|z_k-z^{*}{|}^2}=\frac{0.5^{2^{k+1}}}{{(0.5^{2^k})}^2}=1.$

Also konvergiert $(x_k)$ linear, $(y_k)$ superlinear und $(z_k)$ quadratisch gegen 1. Die folgende Tabelle demonstriert, was die unterschiedlichen Konvergenzraten praktisch bedeuten.

$\begin{array}{ccccccc}k& 1& 2& 3& 4& 5& 6\\ x_k& 1.500000& 1.250000& 1.125000& 1.062500& 1.031250000& 1.015625000\\ y_k& 2.000000& 1.250000& 1.037037& 1.003906& 1.000320000& 1.000021434\\ z_k& 1.250000& 1.062500& 1.003906& 1.000015& 1.000000000& 1.000000\dots \end{array}$

Quadratische Konvergenz impliziert superlineare Konvergenz und diese wiederum lineare Konvergenz. Denn im Fall quadratischer Konvergenz hat man mit einem $C>0$ und einem $k_0\in \mathbb{N}$

$\Vert x^{k+1}-x^{*}\Vert \le \left(C\Vert x^k-x^{*}\Vert \right)\Vert x^k-x^{*}\Vert ,k\ge k_0,$

was wegen $\underset{k\to \mathrm{\infty }}{\lim }{x}^k=x^{*}$ die Bedingung (5.3) impliziert. Ist andererseits (5.2) gegeben, dann existiert zu jedem $\epsilon \in (0,1)$ ein $k_{\epsilon }\in \mathbb{N}$, so dass gilt:

(5.4) $\Vert x^{k+1}-x^{*}\Vert \le \epsilon \Vert x^k-x^{*}\Vert ,k\ge k_{\epsilon }.$

Letztere Beziehung drückt gerade die lineare Konvergenz aus.

Im Fall der superlinearen Konvergenz gilt ja (5.4), d. h. lineare Konvergenz mit einem $\epsilon \in (0,1)$, so dass man bei der Definition der linearen und superlinearen Konvergenz auf die Voraussetzung $\underset{k\to \mathrm{\infty }}{\lim }{x}^k=x^{*}$ verzichten könnte. Denn die Ungleichung (5.1) impliziert im Fall der linearen Konvergenz

$\Vert x^{k+1}-x^{*}\Vert \le C\Vert x^k-x^{*}\Vert \le C^2\Vert x^{k-1}-x^{*}\Vert \le C^{k-k_0+1}\Vert x^{k_0}-x^{*}\Vert ,k\ge k_0$

und damit wegen $C<1$ auch die Konvergenz $\underset{k\to \mathrm{\infty }}{\lim }{x}^k=x^{*}$. Bei der Definition einer Konvergenzordnung $p>1$ muss man aber, da dort nicht $C<1$ gefordert ist, die Konvergenz der Folge $(x^k)$ explizit voraussetzen.

Man beachte, dass lineare Konvergenz mit einer Konstanten $C\approx 1$ sehr langsame Konvergenz bedeuten kann.

Beispiel 5.3

Für die gegen 1 konvergierende Folge $(x_k)$ mit $x_k=1+0.99^k,k\in {\mathbb{N}}_0$ gilt

$|x_{k+1}-1|=0.99\cdot |x_k-1|=0.99^{k+1}|x_0-1|=0.99^{k+1}.$

Die langsame Konvergenz sei mit der Berechnung einiger Folgenglieder gezeigt:

$\begin{array}{cccc}k& 100& 1000& 2000\\ x_k& 1.366032341& 1.000043171& 1.000000002\end{array}$

Man hofft also, dass die Konstante $C$ in der Praxis im Fall der linearen Konvergenz $\ll 1$ ist und im Fall der quadratischen Konvergenz nicht allzu groß wird. In letzterem Fall besagt die Ungleichung (5.1) für $C:=1$, dass sich für einen Fehler $\Vert x^{*}-x^k\Vert <1$ die Anzahl der korrekten Stellen hinter dem Dezimalpunkt von $x^{k+1}$ bezüglich $x^{*}$ gegenüber der von $x^k$ ungefähr verdoppelt. Denn dann ist

$\Vert x^{*}-x^{k+1}\Vert \le {\Vert x^{*}-x^k\Vert }^2,k\ge k_0,$

so dass man bei einer Genauigkeit von $\ell$ Stellen hinter dem Dezimalpunkt für $x^k$ bezüglich der Norm $\Vert \cdot \Vert$ im $k$-ten Schritt einen Fehler $\Vert x^{*}-x^k\Vert \le 5\cdot 10^{-(\ell +1)}$ hat und somit im $(k+1)$-ten Schritt einen Fehler

$\Vert x^{*}-x^k\Vert \le 25\cdot 10^{-2(\ell +1)}=2.5\cdot 10^{-(2\ell +1)}.$

Quadratische Konvergenz ist demnach eine für die Praxis sehr gute Eigenschaft eines Verfahrens und meist die schnellste Konvergenz, die man mit vernünftigen Mitteln erreichen kann.

Es sei jedoch darauf hingewiesen, dass eine gute Konvergenzrate eines Verfahrens alleine nicht dessen Effizienz garantiert. Von einem gegebenen Verfahren ausgehend, kann man ja immer ein noch schnelleres Verfahren erzeugen, indem man mehrere Iterationen des ersten Verfahrens zu einer einzigen zusammenfasst. Neben der Konvergenzgeschwindigkeit eines Verfahrens hat man also bei der Beurteilung eines Verfahrens den numerischen Aufwand pro Iteration und natürlich auch seine Stabilität zu berücksichtigen.

Wir bemerken ferner, dass die Eigenschaften der superlinearen und quadratischen Konvergenz einer Folge $(x^k)$ gegen einen Punkt $x^{*}$ im ${ℝ}^n$ aufgrund der Äquivalenz aller Normen im ${ℝ}^n$ unabhängig von der gewählten Norm sind. Denn die Äquivalenz zweier Normen $\Vert \cdot {\Vert }_a$ und $\Vert \cdot {\Vert }_b$ auf dem ${ℝ}^n$ besagt, dass mit zwei Konstanten $\alpha \ge 0$ und $\beta \ge 0$

$\alpha \Vert x{\Vert }_b\le \Vert x{\Vert }_a\le \beta \Vert x{\Vert }_b,x\in {ℝ}^n$

gilt, so dass z. B. die Beziehung in (5.3) bezogen auf die Norm $\Vert \cdot {\Vert }_a$

$\alpha {\Vert x^{k+1}-x^{*}\Vert }_b\le {\Vert x^{k+1}-x^{*}\Vert }_a\le {\epsilon }_k{\Vert x^k-x^{*}\Vert }_a\le \beta {\epsilon }_k{\Vert x^k-x^{*}\Vert }_b,k\ge k_1$

impliziert und damit für die Nullfolge $\{{\eta }_k\}$ mit ${\eta }_k:=(\beta /\alpha ){\epsilon }_k$ auch

${\Vert x^{k+1}-x^{*}\Vert }_b\le {\eta }_k{\Vert x^k-x^{*}\Vert }_b.$

Ähnlich garantiert quadratische Konvergenz bezüglich der Norm $\Vert \cdot {\Vert }_a$ auch die quadratische Konvergenz

${\Vert x^{k+1}-x^{*}\Vert }_b\le C_b{\Vert x^k-x^{*}\Vert }_b^2$

bezüglich einer Norm $\Vert \cdot {\Vert }_b$, wobei die Konstante $C_b$ von der Norm $\Vert \cdot {\Vert }_a$ abhängt. Dagegen muss lineare Konvergenz einer Folge im ${ℝ}^n$ bezüglich einer Norm nicht notwendig die lineare Konvergenz hinsichtlich einer anderen Norm auf dem ${ℝ}^n$ zur Folge haben. Zwar gilt beispielsweise für jede linear bezüglich $\Vert \cdot {\Vert }_a$ konvergente Folge $(x^k)$ auch

${\Vert x^{k+1}-x^{*}\Vert }_b\le C_b{\Vert x^k-x^{*}\Vert }_b$

mit einer Konstanten $C_b$ für eine Norm $\Vert \cdot {\Vert }_b$, jedoch nicht notwendig $C_b<1$. Sprechen wir also von linearer Konvergenz, so müssen wir klarstellen, bezüglich welcher Norm wir dies tun. Wenn nichts Anderes gesagt wird, beziehen wir uns immer auf Konvergenz im Sinne der Euklidischen Norm $\Vert \cdot {\Vert }_2$.

Die hier eingeführten Begriffe der linearen, superlinearen und quadratischen Konvergenz werden gelegentlich auch als $Q$-lineare, $Q$-superlineare bzw. $Q$-quadratische Konvergenz bezeichnet, im Unterschied zur $R$-linearen, $R$-superlinearen bzw. $R$-quadratischen Konvergenz (siehe z. B. das Buch von Ortega und Rheinboldt aus dem Jahre 1970). Das „$Q$“ steht dabei für „Quotient“, da die Konvergenzrate in allen Fällen mittels des Quotienten $\Vert x^{k+1}-x^{*}\Vert /\Vert x^k-x^{*}\Vert$ ausgedrückt werden kann (während „$R$“ für engl. „Root“, also „Wurzel“ steht).

Siehe auch

• Gradientenabstiegsverfahren

Seiteninformation

Diese Lernresource können Sie als Wiki2Reveal-Foliensatz darstellen.

Wiki2Reveal

Dieser Wiki2Reveal Foliensatz wurde für den Lerneinheit Kurs:Numerik I' erstellt der Link für die Wiki2Reveal-Folien wurde mit dem Wiki2Reveal-Linkgenerator erstellt.

• Die Seite wurde als Dokumententyp PanDocElectron-SLIDE erstellt.
• Link zur Quelle in Wikiversity: https://de.wikiversity.org/wiki/Kurs:Numerik%20I/Konvergenzraten
• siehe auch weitere Informationen zu Wiki2Reveal und unter Wiki2Reveal-Linkgenerator.