5.1 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 lösen, 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^{0}$ 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 $\mathbb {R} ^{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 $\|\cdot \|$ eine Norm auf dem $\mathbb {R} ^{n}$ und $(x^{k})$ eine Folge in $\mathbb {R} ^{n}$ mit $\lim _{k\to \infty }x^{k}=x^{*}$ .

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

(5.1)

\left\|x^{k+1}-x^{*}\right\|\leq C\left\|x^{k}-x^{*}\right\|^{p},\quad k\geq 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 \mathbb {R} ^{n}$ ), wenn $x^{k}\neq x^{*},k\geq k_{0}$ für ein $k_{0}\in \mathbb {N}$ gilt sowie

(5.2)

\lim _{k\to \infty }{\frac {\left\|x^{k+1}-x^{*}\right\|}{\|x^{k}-x^{*}\|}}=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}\neq x^{*},k\geq 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 $(\varepsilon _{k})$ von Zahlen $\varepsilon _{k}\geq 0$ mit $\lim _{k\to \infty }\varepsilon _{k}=0$ durch

(5.3)

\left\|x^{k+1}-x^{*}\right\|\leq \varepsilon _{k}\left\|x^{k}-x^{*}\right\|,\quad k\geq k_{1}

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

\left\|x^{k+1}-x^{*}\right\|=o\left(\left\|x^{k}-x^{*}\right\|\right)

ausdrücken und quadratische Konvergenz durch

\left\|x^{k+1}-x^{*}\right\|={\mathcal {O}}\left(\left\|x^{k}-x^{*}\right\|^{2}\right).

Beispiel 5.2

Die Folgen $(x_{k}),(y_{k})$ und $(z_{k})$ mit

x_{k}:=1+0.5^{k},\quad y_{k}:=1+k^{-k},\quad z_{k}:=1+0.5^{2^{k}}

konvergieren für $k\to \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\quad (k\to \infty ),

{\frac {|z_{k+1}-z^{*}|}{|z_{k}-z^{*}|^{2}}}={\frac {0.5^{2^{k+1}}}{\left(0.5^{2^{k}}\right)^{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}{c|c c c c c c}k&1&2&3&4&5&6\\\hline x_{k}&1.500\,000&1.250\,000&1.125\,000&1.062\,500&1.031\,250\,000&1.015\,625\,000\\y_{k}&2.000\,000&1.250\,000&1.037\,037&1.003\,906&1.000\,320\,000&1.000\,021\,434\\z_{k}&1.250\,000&1.062\,500&1.003\,906&1.000\,015&1.000\,000\,000&1.000\,000\,\ldots \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}$

\left\|x^{k+1}-x^{*}\right\|\leq \left(C\left\|x^{k}-x^{*}\right\|\right)\left\|x^{k}-x^{*}\right\|,\quad k\geq k_{0},

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

(5.4)

\left\|x^{k+1}-x^{*}\right\|\leq \varepsilon \left\|x^{k}-x^{*}\right\|,\quad k\geq k_{\varepsilon }.

Letztere Beziehung drückt gerade die lineare Konvergenz aus.

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

\left\|x^{k+1}-x^{*}\right\|\leq C\left\|x^{k}-x^{*}\right\|\leq C^{2}\left\|x^{k-1}-x^{*}\right\|\leq C^{k-k_{0}+1}\left\|x^{k_{0}}-x^{*}\right\|,\quad k\geq k_{0}

und damit wegen $C<1$ auch die Konvergenz $\lim _{k\to \infty }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}{c|c c c}k&100&1000&2000\\\hline x_{k}&1.366\,032\,341&1.000\,043\,171&1.000\,000\,002\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 $\left\|x^{*}-x^{k}\right\|<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

\left\|x^{*}-x^{k+1}\right\|\leq \left\|x^{*}-x^{k}\right\|^{2},\quad k\geq k_{0},

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

\left\|x^{*}-x^{k}\right\|\leq 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 $\mathbb {R} ^{n}$ aufgrund der Äquivalenz aller Normen im $\mathbb {R} ^{n}$ unabhängig von der gewählten Norm sind. Denn die Äquivalenz zweier Normen $\|\cdot \|_{a}$ und $\|\cdot \|_{b}$ auf dem $\mathbb {R} ^{n}$ besagt, dass mit zwei Konstanten $\alpha \geq 0$ und $\beta \geq 0$

\alpha \|x\|_{b}\leq \|x\|_{a}\leq \beta \|x\|_{b},\quad x\in \mathbb {R} ^{n}

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

\alpha \left\|x^{k+1}-x^{*}\right\|_{b}\leq \left\|x^{k+1}-x^{*}\right\|_{a}\leq \varepsilon _{k}\left\|x^{k}-x^{*}\right\|_{a}\leq \beta \varepsilon _{k}\left\|x^{k}-x^{*}\right\|_{b},\quad k\geq k_{1}

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

\left\|x^{k+1}-x^{*}\right\|_{b}\leq \eta _{k}\left\|x^{k}-x^{*}\right\|_{b}.

Ähnlich garantiert quadratische Konvergenz bezüglich der Norm $\|\cdot \|_{a}$ auch die quadratische Konvergenz

\left\|x^{k+1}-x^{*}\right\|_{b}\leq C_{b}\left\|x^{k}-x^{*}\right\|_{b}^{2}

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

\left\|x^{k+1}-x^{*}\right\|_{b}\leq C_{b}\left\|x^{k}-x^{*}\right\|_{b}

mit einer Konstanten $C_{b}$ für eine Norm $\|\cdot \|_{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 $\|\cdot \|_{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 $\left\|x^{k+1}-x^{*}\right\|/\left\|x^{k}-x^{*}\right\|$ ausgedrückt werden kann (während „ $R$ “ für engl. „Root“, also „Wurzel“ steht).

5.2 Nullstellenbestimmung reeller Funktionen einer Veränderlichen

Häufig hat man in Anwendungen für eine gegebene Funktion $f\in C[a,b]$ eine Nullstelle, auch Wurzel genannt, zu bestimmen, d. h. einen Punkt $x^{*}\in (a,b)$ mit $f(x^{*})=0$ . So benötigt man für die Bestimmung der Extremalpunkte einer Funktion $g$ die Nullstellen von $f:=g'$ . Um eine möglichst gute Startnäherung für jede solche Nullstelle zu erhalten, hat man dann meistens zunächst ein kleines Intervall $[\alpha ,\beta ]$ in $[a,b]$ zu ermitteln, in dem ein und zwar möglichst nur ein solches $x^{*}$ liegt. Dazu berechnet man im Allgemeinen Funktionswerte $f(\xi _{i})$ mit

\xi _{i}:=a+ih\quad (i=0,\ldots ,n),\quad h:={\frac {b-a}{m}}

für ein gegebenes, genügend großes $m\in \mathbb {N}$ . Die Menge aller $\xi _{i}$ bezeichnet man auch als ein Gitter in $[a,b]$ , die $\xi _{i}$ selbst als Gitterpunkte und den Prozess der Auswahl von endlich vielen Punkten aus $[a,b]$ als Diskretisierung des Intervalls. Sind $f(\xi _{i})\neq 0$ und $f(\xi _{i+1})\neq 0$ (anderenfalls hätte man eine Nullstelle von $f$ gefunden) und ist

f(\xi _{i})f(\xi _{i+1})<0\quad (i=0,\ldots ,n-1),

so muss $f$ nach dem Zwischenwertsatz im Intervall $[\xi _{i},\xi _{i+1}]$ eine (einfache) Nullstelle besitzen und können wir $\alpha :=\xi _{i}$ und $\beta :=\xi _{i+1}$ setzen.

Es sind eine Reihe von Verfahren vorgeschlagen worden, die, ausgehend von einem solchen Intervall, unter geeigneten Bedingungen eine genäherte Nullstelle von $f$ liefern. Wir betrachten im Folgenden einige dieser Verfahren. Dabei gehen wir davon aus, dass eine Funktion $f\in C[a,b]$ gegeben ist und ein $x^{*}\in (a,b)$ existiert mit $f(x^{*})=0$ , welches bestimmt werden soll.

5.2.1 Das Bisektionsverfahren

Das erste Verfahren, das wir vorstellen wollen, ist das Intervallschachtelungs- oder auch Bisektionsverfahren. Bei diesem wird, beginnend mit dem Intervall $[a_{0},b_{0}]\subseteq [a,b]$ , eine Folge von Intervallen $[a_{k},b_{k}]$ erzeugt, so dass $f(a_{k})f(b_{k})<0$ und damit $x^{*}\in (a,b)$ gilt. Dieses Verfahren verwendet in jeder Iteration als einzige Information nur die Vorzeichen der Funktionswerte an den Randpunkten des aktuellen Intervalls, so dass keine schnelle Konvergenzgeschwindigkeit zu erwarten ist.

Algorithmus 5 (Bisektionsverfahren)

(0) Gib

a_{0},b_{0}\in [a,b]

mit

f(a_{0})f(b_{0})<0

und

\varepsilon >0

. Setze

k=0

.

(1) Berechne

x_{k+1}:={\frac {1}{2}}(a_{k}+b_{k})

und

f(x_{k+1})

.

(2) Falls

|f(x_{k+1})|\leq \varepsilon

, stop!

(3) Falls

f(a_{k})f(x_{k+1})<0

, setze

a_{k+1}:=a_{k},b_{k+1}:=x_{k+1}

.

Falls

f(a_{k})f(x_{k+1})>0

, setze

a_{k+1}:=x_{k+1},b_{k+1}:=b_{k}

.

(4) Setze

k:=k+1

und gehe nach (1).

Offenbar gilt für die Länge der bei der Bisektionsmethode erzeugten Intervalle $[a_{k},b_{k}]$

(5.5)

|b_{k}-a_{k}|={\frac {1}{2}}|b_{k-1}-a_{k-1}|={\frac {1}{2^{k}}}|b_{0}-a_{0}|,\quad k=0,1,\ldots .

Wenn Algorithmus 5 nicht abgebrochen wird, folgt damit

\lim _{k\to \infty }|b_{k}-a_{k}|=0.

Wegen $a_{k+1}\leq x^{*}\leq b_{k+1}$ sowie $x_{k+1}=a_{k+1}$ oder $x_{k+1}=b_{k+1}$ hat man weiter mit (5.5)

(5.6)

|x_{k+1}-x^{*}|\leq |b_{k+1}-a_{k+1}|\leq {\frac {1}{2^{k+1}}}|b_{0}-a_{0}|,\quad k=0,1,\ldots

und demnach

\lim _{k\to \infty }x_{k}=\lim _{k\to \infty }a_{k}=\lim _{k\to \infty }b_{k}=x^{*}.

Da $f(x^{*})=0$ und $f$ stetig ist, ist daher das Abbruchkriterium $|f(x_{k+1})|\leq \varepsilon$ in Schritt (2) von Algorithmus 5 nach endlich vielen Schritten erfüllt. Statt dieses Abbruchkriteriums, das beispielsweise im Fall

0\leq f(x)\ll 1,\quad x\in [a,b]

ungünstig ist, könnte man alternativ oder zusätzlich auch die Abfrage $|b_{k}-a_{k}|\leq \vartheta$ mit einer kleinen Konstante $\vartheta >0$ als Abbruchkriterium verwenden.

Beispiel 5.4

Ist $b_{0}-a_{0}=1$ , so folgt aus (5.6)

|x_{1}-x^{*}|\leq 0.5,

|x_{5}-x^{*}|\leq [0.5]^{5}\approx 0.031,

|x_{20}-x^{*}|\leq [0.5]^{20}\approx 0.000\,000\,95.

Das Bisektionsverfahren ist ein sicheres und numerisch stabiles Verfahren, aber mit langsamer Konvergenz. Es konvergiert i. a. nicht einmal linear. Für die Fehler zweier aufeinander folgender Iterierter $x_{k+1}$ und $x_{k}$ kann sogar gelten:

|x_{k+1}-x^{*}|>|x_{k}-x^{*}|.

Beispiel 5.5

Die Nullstelle $x^{*}=-0.1$ der Geraden $f(x):=x+0.1$ in $[-1,1]$ werde mit dem Bisektionsverfahren berechnet. Dann hat man wegen $f(-1)<0$ und $f(1)>0$

[a_{0},b_{0}]:=[-1,1],\quad x_{1}:=0,\quad f(x_{1})=0.1>0,

[a_{1},b_{1}]:=[-1,0],\quad x_{2}:=-0.5,\quad f(x_{2})=-0.4<0

und demzufolge

|x_{1}-x^{*}|=0.1<|x_{2}-x^{*}|=0.3.

5.2.2 Die Regula falsi

Bei der Regula Falsi verwendet man im $k$ -ten Schritt die Sekante, welche die Punkte $(a_{k},f(a_{k}))$ und $(b_{k},f(b_{k}))$ verbindet. Diese hat die Gleichung

y={\frac {f(b_{k})-f(a_{k})}{b_{k}-a_{k}}}(x-a_{k})+f(a_{k})

und schneidet die $x$ -Achse bei

(5.7)

x_{k+1}:=a_{k}-f(a_{k}){\frac {b_{k}-a_{k}}{f(b_{k})-f(a_{k})}}.

Der Punkt $x_{k+1}$ wird nun als neue Näherung für $x^{*}$ genommen. Ansonsten verfährt man wie bei der Bisektion.

Algorithmus 6 (Regula Falsi)

(0) Gib

a_{0},b_{0}\in [a,b]

mit

f(a_{0})f(b_{0})<0

und

\varepsilon >0

. Setze

k=0

.

(1) Berechne

x_{k+1}:=a_{k}-f(a_{k}){\frac {b_{k}-a_{k}}{f(b_{k})-f(a_{k})}}

sowie

f(x_{k+1})

.

(2) Falls

|f(x_{k+1})|\leq \varepsilon

, stop!

(3) Falls

f(a_{k})f(x_{k+1})<0

, setze

a_{k+1}:=a_{k},b_{k+1}:=x_{k+1}

.

Falls

f(a_{k})f(x_{k+1})>0

, setze

a_{k+1}:=x_{k+1},b_{k+1}:=b_{k}

.

(4) Setze

k:=k+1

und gehe nach (1).

Für die Regula Falsi ist keine aussagekräftige Fehlerabschätzung erhältlich. Aber sie konvergiert unter gewissen Voraussetzungen mindestens linear (siehe z. B. Stoer). Man beachte, dass wegen $f(a_{k})f(b_{k})<0$ keine Auslöschung bei der Berechnung von $x_{k+1}$ eintritt, so dass das Verfahren überdies numerisch stabil ist. Die erzeugten Näherungen $x_{k}$ liegen alle im Ausgangsintervall $[a_{0},b_{0}]$ und können alle auf einer Seite der gesuchten Nullstelle liegen.

5.2.3 Das Sekantenverfahren

Beim Sekantenverfahren wählt man, ähnlich wie bei der Regula Falsi, die Nullstelle einer Sekante als neue Iterierte, wobei jeweils die Sekante, welche die Punkte $(x_{k-1},f(x_{k-1}))$ und $(x_{k},f(x_{k}))$ verbindet, genommen und mit zwei Startpunkten $x_{-1},x_{0}\in [a,b]$ begonnen wird. Dabei muss nicht notwendig $f(x_{-1})f(x_{0})<0$ gelten. Die Nullstelle dieser Sekante ist offenbar durch

x_{k+1}:=x_{k}-f(x_{k}){\frac {x_{k}-x_{k-1}}{f(x_{k})-f(x_{k-1})}}

gegeben (vgl. (5.7)). Das Sekantenverfahren sieht demnach folgendermaßen aus:

Algorithmus 7 (Sekantenverfahren)

(0) Gib

x_{-1},x_{0}\in [a,b]

und

\varepsilon >0

. Berechne

f(x_{-1})

sowie

f(x_{0})

und setze

k=0

.

(1) Berechne

(5.8)

x_{k+1}:=x_{k}-f(x_{k}){\frac {x_{k}-x_{k-1}}{f(x_{k})-f(x_{k-1})}}

sowie

f(x_{k+1})

.

(2) Falls

|f(x_{k+1})|\leq \varepsilon

, stop!

(3) Setze

k:=k+1

und gehe nach (1).

Man beachte hier (vgl. (5.8)), dass man die Iterierte im $(k+1)$ -ten Schritt eines Verfahrens meist als Korrektur der Iterierten im $k$ -ten Schritt, also in der Form $x_{k+1}:=x_{k}+h_{k}$ mit einem $h_{k}\in \mathbb {R}$ schreibt, so dass man bei Konvergenz des Verfahrens (gegen $x^{*}\neq 0$ ) $|h_{k}|\ll |x_{k}|$ zumindest für größere $k$ hat.

Während bei dem Bisektionsverfahren und der Regula Falsi sofort einleuchtet, dass diese Verfahren immer konvergieren, ist dies beim Sekantenverfahren nicht offensichtlich und hat man die Konvergenz zu beweisen. Es muss insbesondere nicht $x_{k+1}\in [x_{k-1},x_{k}]$ bzw. $x_{k+1}\in [x_{k},x_{k-1}]$ gelten, so dass das Verfahren im Allgemeinen nur lokal konvergiert. Genauer kann man den folgenden Satz beweisen (vgl. Isaacson and Keller):

Satz 5.6

Sei $f\in C^{2}[a,b]$ , und es existiere ein $x^{*}\in [a,b]$ mit $f(x^{*})=0$ und $f'(x^{*})\neq 0$ . Sind die Anfangsnäherungen $x_{-1}$ und $x_{0}$ hinreichend nahe bei $x^{*}$ gewählt, so konvergiert die nach Streichung von Schritt (2) durch Algorithmus 7 erzeugte Folge $(x_{k})$ superlinear gegen $x^{*}$ von der Ordnung $p:=(1+{\sqrt {5}})/2=1.618\ldots$ .

Das Sekantenverfahren konvergiert also im Allgemeinen schneller als das Bisektionsverfahren und die Regula Falsi. Anders als diese, neigt es aber zu instabilem Verhalten, da der Fall $\operatorname {sgn} (f(x_{k}))=\operatorname {sgn} (f(x_{k-1}))$ und damit Auslöschung bei der Berechnung von $x_{k+1}$ eintreten kann.

Die schnelle Konvergenz des Sekantenverfahrens soll an einem Beispiel demonstriert werden.

Beispiel 5.7

Es soll ${\sqrt {2}}$ berechnet werden. Dies kann man tun, indem man die positive Nullstelle der Funktion $f(x):=x^{2}-2$ z. B. in dem Intervall $[0,5]$ bestimmt. Der gesuchte Wert lautet auf 12 Stellen hinter dem Dezimalpunkt genau

{\sqrt {2}}=1.414\,213\,562\,373\ldots .

Die Iterationsvorschrift des Sekantenverfahrens lässt sich hier vereinfachen zu

x_{k+1}:=x_{k}-\left[x_{k}^{2}-2\right]{\frac {x_{k}-x_{k-1}}{x_{k}^{2}-x_{k-1}^{2}}}=x_{k}-{\frac {x_{k}^{2}-2}{x_{k}+x_{k-1}}}.

Man errechnet mit $x_{-1}:=1.3$ und $x_{0}:=1.5$ für $k:=0$

x_{1}:=1.5-{\frac {(1.5)^{2}-2}{1.5+1.3}}=1.410\,714\,285\,71.

mit $x_{0}:=1.5$ und $x_{1}:=1.410\,714\,285\,71$ für $k:=1$

x_{2}:=1.410\,714\,285\,71-{\frac {(1.410\,714\,285\,71)^{2}-2}{1.410\,714\,285\,71+1.5}}

usw. Insgesamt erhält man die Iteriertenfolge

x_{1}={\underline {1.41}}0\,714\,285\,71,

x_{2}={\underline {1.414}}\,110\,429\,45,

x_{3}={\underline {1.414\,213}}\,690\,13,

x_{4}={\underline {1.414\,213\,562\,37}},\ldots ,

wobei die richtigen Ziffern jeweils unterstrichen sind.

Hätte man mit der ursprünglichen Formel (5.8) gearbeitet, wie man das meist in der Praxis zu tun hat, so hätte man 2 Funktionsauswertungen von $f$ zur Berechnung von $x_{1}$ und jeweils eine für die von $x_{2}$ bis $x_{4}$ , d. h. insgesamt 5 Funktionsauswertungen zur Berechnung von $x_{4}$ benötigt.

Funktionsauswertungen sind in vielen Situationen ein gutes praktisches Vergleichskriterium für unterschiedliche Algorithmen zur Lösung eines Problems, da diese häufig die numerisch teuersten Teilaufgaben bei der Problemlösung darstellen.

5.2.4 Das Newton-Verfahren

Es sei nun $f\in C^{1}[a,b]$ und die Existenz eines $x^{*}\in (a,b)$ mit $f(x^{*})=0$ vorausgesetzt. Beim Newton-Verfahren benötigt man nur eine Startnäherung $x_{0}\in (a,b)$ für $x^{*}$ . Ist $x_{k}$ die Näherung für $x^{*}$ zu Beginn der $k$ -ten Iteration, so wählt man bei diesem Verfahren die Nullstelle $x_{k+1}$ der Tangente im Punkt $(x_{k},f(x_{k}))$ an den Graphen von $f$ als nächste Näherung. Die Gleichung dieser Tangente ist offenbar durch

y=f(x_{k})+f'(x_{k})(x-x_{k})

gegeben, so dass man

x_{k+1}:=x_{k}-{\frac {f(x_{k})}{f'(x_{k})}}

erhält. Wenn wir beispielsweise $f'(x^{*})\neq 0$ voraussetzen ( $x^{*}$ ist dann eine einfache Nullstelle), können wir dabei zumindest für solche $x_{k}$ , die nahe bei $x^{*}$ liegen, $f'(x_{k})\neq 0$ annehmen. (Im Fall $f(x_{k})\neq 0$ und $f'(x_{k})=0$ hätte die Tangente auch keine Nullstelle.) Das Newton-Verfahren lautet demnach:

Algorithmus 8 (Newton-Verfahren)

(0) Wähle ein

\varepsilon >0

und

x_{0}\in (a,b)

, berechne

f(x_{0})

und setze

k:=0

.

(1) Berechne

f'(x_{k})

,

(5.9)

x_{k+1}:=x_{k}-{\frac {f(x_{k})}{f'(x_{k})}}

und

f(x_{k+1})

.

(2) Falls

|f(x_{k+1})|\leq \varepsilon

, stop!

(3) Setze

k:=k+1

und gehe nach (1).

Bevor wir das Newton-Verfahren weiter untersuchen, betrachten wir sein Verhalten für das Problem in Beispiel 5.7.

Beispiel 5.8

Es sei wieder $f(x):=x^{2}-2$ und damit $f'(x)=2x$ . Gesucht ist die positive Nullstelle ${\sqrt {2}}=1.414\,213\,562\,373$ von $f$ . Die Iterationsvorschrift des Newton-Verfahrens lässt sich hier schreiben als

x_{k+1}:=x_{k}-{\frac {f(x_{k})}{f'(x_{k})}}=x_{k}-{\frac {x_{k}^{2}-2}{2x_{k}}}={\frac {1}{2}}x_{k}+{\frac {1}{x_{k}}}.

Beginnend mit $x_{0}:=1.5$ und $k:=0$ berechnet man die Iterierten

x_{1}={\underline {1.41}}6,

x_{2}={\underline {1.414\,21}}5\,686\,27,

x_{3}={\underline {1.414\,213\,562\,3}}8,\ldots .

Bei direkter Verwendung von (5.9) wären für die Berechnung von $x_{3}$ jeweils 3 Funktionsauswertungen von $f$ und $f'$ , also insgesamt 6 Funktionsauswertungen erforderlich gewesen. Das Newtonverfahren ist also in diesem Fall ein sehr schnelles Verfahren. Bei diesem Beispiel und der Wahl von Startwerten (!) erreicht das Sekantenverfahren aber mit etwas weniger Aufwand sogar etwas höhere Genauigkeit.

Wir wollen uns nun mit der Konvergenz des Newton-Verfahrens beschäftigen. Dazu holen wir etwas weiter aus. Für eine gegebene Funktion $g:\mathbb {R} ^{n}\to \mathbb {R} ^{n}$ nennen wir einen Punkt $x^{*}\in \mathbb {R} ^{n}$ mit

g(x^{*})=x^{*}

einen Fixpunkt von $g$ . Weiter sprechen wir bei der Iterationsvorschrift

x^{k+1}:=g(x^{k}),\quad k=0,1,2,\ldots

von der Fixpunktiteration mit der Verfahrensfunktion $g$ . Ist $g$ stetig und konvergiert die Iteriertenfolge, so muss ihr Grenzwert offenbar notwendig ein Fixpunkt von $g$ sein. Man beachte in diesem Zusammenhang, dass $x^{*}$ genau dann Fixpunkt von $g$ ist, wenn $x^{*}$ Nullstelle z. B. der Funktion $f(x):=g(x)-x$ ist, dass also die Probleme der Bestimmung einer Nullstelle und der eines Fixpunktes einer Funktion äquivalent sind.

Wir beweisen nun folgenden allgemeinen Satz über die lokale Konvergenz der Fixpunktiteration, wobei

{\mathcal {U}}_{\delta }(x^{*}):=\{x\in \mathbb {R} :|x-x^{*}|<\delta \}

eine offene $\delta$ -Umgebung des Punktes $x^{*}\in \mathbb {R}$ bezeichne.

Satz 5.9

Sei $g:\mathbb {R} \to \mathbb {R}$ gegeben und $x^{*}\in \mathbb {R}$ Fixpunkt von $g$ . Weiter sei $g$ in $x^{*}$ $p$ -mal differenzierbar mit einem $p\in \mathbb {N}$ , und es gelte entweder

(5.10)

{\begin{cases}g^{(k)}(x^{*})=0,k=1,\ldots ,p-1,&f{\ddot {u}}r\ p\geq 2\ oder\\0<|g'(x^{*})|<1,&f{\ddot {u}}r\ p=1.\end{cases}}

Dann existiert ein $\delta >0$ , so dass die durch

x_{k+1}:=g(x_{k}),\quad k\in \mathbb {N} _{0}

erzeugte Iteriertenfolge $(x_{k})$ für jeden Startpunkt $x_{0}\in {\mathcal {U}}_{\delta }(x^{*})$ gegen $x^{*}$ konvergiert und zwar mindestens von der Ordnung $p$ . Im Fall $g^{(p)}(x^{*})\neq 0$ ist die Konvergenzordnung genau $p$ .

Beweis.

Taylorentwicklung von $g$ um $x^{*}$ liefert für beide Fälle in (5.10)

g(x)=\sum _{i=0}^{p}{\frac {g^{(i)}(x^{*})}{i!}}(x-x^{*})^{i}+o(|x-x^{*}|^{p})

=\underbrace {g(x^{*})} _{=x^{*}}+{\frac {g^{(p)}(x^{*})}{p!}}(x-x^{*})^{p}+o(|x-x^{*}|^{p})

für

x\to x^{*}

Somit hat man

(5.11)

\left|{\frac {g(x)-x^{*}}{(x-x^{*})^{p}}}-{\frac {g^{(p)}(x^{*})}{p!}}\right|\to 0\quad (x\to x^{*}),

so dass zu einem gegebenen $\varepsilon >0$ ein $\delta >0$ existiert und

|g(x)-x^{*}|\leq \left(\varepsilon +{\frac {\left|g^{(p)}(x^{*})\right|}{p!}}\right)|x-x^{*}|^{p}

(5.12)

=\left[C|x-x^{*}|^{p-1}\right]|x-x^{*}|={\tilde {C}}(x)|x-x^{*}|,\quad x\in {\mathcal {U}}_{\delta }(x^{*})

mit $C:=\varepsilon +\left|g^{(p)}(x^{*})\right|/p!$ und ${\tilde {C}}(x):=C|x-x^{*}|^{p-1}$ gilt. Im Fall $p=1$ sei dabei $\varepsilon$ so klein gewählt, dass

{\tilde {C}}:={\tilde {C}}(x)\equiv C=\varepsilon +|g'(x^{*})|<1

ist, was aufgrund der Voraussetzung $|g'(x^{*})|<1$ möglich ist. Für $p>1$ ist es offenbar möglich, $\delta$ so klein zu wählen, dass ${\tilde {C}}(x)\leq 0.5=:{\tilde {C}}<1$ für alle $x\in {\mathcal {U}}_{\delta }(x^{*})$ folgt.

Die Ungleichung (5.12) impliziert nun für $|x-x^{*}|\leq \delta$ auch $|g(x)-x^{*}|\leq \delta$ und damit im Fall $x_{0}\in {\mathcal {U}}_{\delta }(x^{*})$ auch $x_{k}\in {\mathcal {U}}_{\delta }(x^{*})$ für alle $k\in \mathbb {N}$ , so dass man

|x_{k+1}-x^{*}|\leq C|x_{k}-x^{*}|^{p}\leq {\tilde {C}}|x_{k}-x^{*}|\leq {\tilde {C}}^{k+1}|x_{0}-x^{*}|,\quad k\in \mathbb {N} _{0}

hat und daraus wegen ${\tilde {C}}<1$ die Konvergenz $\lim _{k\to \infty }x_{k}=x^{*}$ von mindestens der Ordnung $p$ schließen kann. Ist die Zusatzbedingung $g^{(p)}(x^{*})\neq 0$ erfüllt und wird oben $\varepsilon$ so gewählt, dass $0<\varepsilon <\left|g^{(p)}(x^{*})\right|/p!$ gilt, so gilt wegen (5.11)

(5.13)

|g(x)-x^{*}|\geq \left({\frac {\left|g^{(p)}(x^{*})\right|}{p!}}-\varepsilon \right)|x-x^{*}|^{p}=:{\hat {C}}|x-x^{*}|^{p},\quad x\in {\mathcal {U}}_{\delta }(x^{*})

Daraus folgt die genaue Konvergenzordnung $p$ in diesem Fall, denn wäre diese mindestens $p+1$ , so folgte mit (5.13) für ein ${\overline {C}}$ und ein $k_{0}\in \mathbb {N}$

{\hat {C}}|x_{k}-x^{*}|^{p}\leq |x_{k+1}-x^{*}|\leq {\overline {C}}|x_{k}-x^{*}|^{p+1},\quad k\geq k_{0}

und damit im Widerspruch zu Konvergenz von $(x_{k})$ gegen $x^{*}$

0<{\frac {\hat {C}}{\overline {C}}}\leq |x_{k}-x^{*}|,\quad k\geq k_{0}.

q.e.d.

In dem folgenden Satz wird nun unter verschiedenen Voraussetzungen eine jeweilige Konvergenzordnung des Newton-Verfahrens angegeben.

Satz 5.10

Es sei $f:\mathbb {R} \to \mathbb {R}$ gegeben und es existiere $x^{*}\in \mathbb {R}$ mit $f(x^{*})=0$ . Mit einem $\eta >0$ sei weiter für Aussage (i) $f\in C^{3}({\mathcal {U}}_{\eta }(x^{*}))$ und für Aussage (ii) $f\in C^{2}({\mathcal {U}}_{\eta }(x^{*}))$ . Dann gilt nach Streichung von Schritt (2) für die durch das Newton-Verfahren (Algorithmus 8) erzeugte Folge $(x_{k})$ :

(i) Ist $f'(x^{*})\neq 0$ , dann existiert ein $\delta \in (0,\eta ]$ , so dass $(x_{k})$ für jeden Startpunkt $x_{0}\in {\mathcal {U}}_{\delta }(x^{*})$ gegen $x^{*}$ konvergiert und zwar mindestens quadratisch. Im Fall $f''(x^{*})=0$ konvergiert $(x_{k})$ sogar von einer Ordnung $p\geq 3$ .

(ii) Ist $x^{*}$ andererseits eine $m$ -fache Nullstelle von $f$ mit einem $m\geq 2$ , d. h., ist

f(x)=(x-x^{*})^{m}z(x),\quad z(x^{*})\neq 0

und ist weiter $z$ in $x^{*}$ zweimal differenzierbar, so ist die Iterationsfunktion

(5.14)

g(x):={\begin{cases}x-{\frac {f(x)}{f'(x)}},&falls\ x\neq x^{*},\\x^{*},&falls\ x=x^{*}\end{cases}}

des Newton-Verfahrens differenzierbar in $x^{*}$ mit

(5.15)

g'(x^{*})=1-{\frac {1}{m}}

und existiert ein $\delta \in (0,\eta ]$ , so dass $(x_{k})$ für jeden Startpunkt $x_{0}\in {\mathcal {U}}_{\delta }(x^{*})$ (genau) linear gegen $x^{*}$ konvergiert.

Beweis.

Die Behauptung folgt mit Satz 5.9, wenn man diesen auf $g$ in (5.14) anwendet sowie mit den folgenden Darstellungen. Im Fall (i) zeigt man zunächst die Stetigkeit von $g,g'$ und $g''$ in $x^{*}$ . Man ermittelt dann

g'=1-{\frac {(f')^{2}-ff''}{(f')^{2}}}={\frac {ff''}{(f')^{2}}},\quad g''={\frac {(f')^{3}f''+f(f')^{2}(f''')-2ff'(f'')^{2}}{(f')^{4}}},

so dass also

g(x^{*})=x^{*},\quad g'(x^{*})=0,\quad g''(x^{*})={\frac {f''(x^{*})}{f'(x^{*})}}

gilt. Damit folgt die Behauptung.

Im Fall (ii) erhält man

f'(x)=m(x-x^{*})^{m-1}z(x)+(x-x^{*})^{m}z'(x)

und somit

(5.16)

{\frac {f(x)}{f'(x)}}={\frac {(x-x^{*})z(x)}{mz(x)+(x-x^{*})z'(x)}}.

Wegen $z(x^{*})\neq 0$ folgt damit $\lim _{x\to x^{*}}f(x)/f'(x)=0$ und ist demzufolge $g$ aus (5.14) stetig in $x^{*}$ . Weiter hat man mit (5.16) wegen $f(x^{*})=0$

g'(x^{*})=\lim _{h\to 0}{\frac {g(x^{*}+h)-g(x^{*})}{h}}=\lim _{h\to 0}{\frac {x^{*}+h-{\frac {f(x^{*}+h)}{f'(x^{*}+h)}}-x^{*}}{h}}=1-\lim _{h\to 0}{\frac {f(x^{*}+h)}{hf'(x^{*}+h)}}

=1-\lim _{h\to 0}{\frac {hz(x^{*}+h)}{h[mz(x^{*}+h)+hz'(x^{*}+h)]}}=1-{\frac {1}{m}}.

Also ist $0<g'(x^{*})<1$ und damit insbesondere auch $g'(x^{*})\neq 0$ .

q.e.d.

Man beachte, dass das Newton-Verfahren pro Iteration zwei Funktionsauswertungen benötigt, während das Sekanten-Verfahren nur eine verlangt. Im Fall, dass der Grenzwert eine einfache Nullstelle ist, konvergiert letzteres Verfahren unter geeigneten Voraussetzungen aber nur superlinear, während das Newton-Verfahren dann mindestens quadratisch konvergiert. Es stellt sich also die Frage, welches der Verfahren in der Praxis effizienter ist. Bemerkenswert ist es daher, dass man zeigen kann, dass das Sekantenverfahren, wenn man zwei Iterationen zu einer zusammenfasst und es damit etwa gleichen Aufwand pro Iteration wie das Newton-Verfahren bekommt, eine Konvergenzrate von mindestens $p:=2.618$ hat, und es folglich lokal schneller als das Newton-Verfahren konvergiert. Allerdings neigt das Sekanten-Verfahren, anders als das Newton-Verfahren, aufgrund von Auslöschungen zu instabilem Verhalten.

5.3 Fixpunktiteration

Wir verallgemeinern zunächst die Fixpunktiteration auf Funktionen $g:\mathbb {R} ^{n}\to \mathbb {R} ^{n}$ , die wir in Abschnitt 5.2.4 für $n=1$ und hinreichend glattes $g$ diskutiert hatten. Für die Bestimmung eines Fixpunktes von $g$ , d. h. eines Punktes $x^{*}\in \mathbb {R} ^{n}$ mit $g(x^{*})=x^{*}$ , betrachten wir also die Iterationsvorschrift

(5.17)

x^{k+1}:=g(x^{k}),\quad k=0,1,2,\ldots

mit einem gegebenen Startwert $x^{0}\in \mathbb {R} ^{n}$ . Wir definieren nun zunächst:

Definition 5.11

(i) Sei $D\subseteq \mathbb {R} ^{n}$ und $\|\cdot \|:\mathbb {R} ^{n}\to \mathbb {R} _{+}$ eine Norm auf dem $\mathbb {R} ^{n}$ . Eine Abbildung $g:D\to \mathbb {R} ^{n}$ heißt Lipschitz-stetig auf $D$ mit (Lipschitz-)Konstante $L>0$ , wenn gilt:

(5.18)

\|g(x)-g(y)\|\leq L\|x-y\|,\quad x,y\in D.

(ii) Eine Lipschitz-stetige Abbildung $g:D\to D$ mit Konstante $L>0$ heißt eine Kontraktion auf $D$ , wenn $L<1$ ist.

Sei nun speziell $g\in C^{1}(D,\mathbb {R} ^{n})$ für $D\subseteq \mathbb {R} ^{n}$ , wobei wir damit eine Funktion $g:D\subseteq \mathbb {R} ^{n}\to \mathbb {R} ^{n}$ mit

g(x)=(g_{1}(x),\ldots ,g_{n}(x))^{T},\quad x\in D

und stetigen partiellen Ableitungen $(\partial g_{i}/\partial x_{j})(x)$ $(i,j=1,\ldots ,n)$ für alle $x\in D$ meinen. Für ein solches $g$ kann man in der Praxis häufig eine Konstante $L$ wie in (5.18) mittels der ersten Ableitung von $g$ bzw. der Jacobi-Matrix von $g$ , welche durch

{\mathcal {J}}_{g}(x):=\left({\frac {\partial g_{i}}{\partial x_{j}}}(x)\right)_{i,j=1,\ldots ,n}={\begin{pmatrix}{\frac {\partial g_{1}}{\partial x_{1}}}(x)&{\frac {\partial g_{1}}{\partial x_{2}}}(x)&\ldots &{\frac {\partial g_{1}}{\partial x_{n}}}(x)\\{\frac {\partial g_{2}}{\partial x_{1}}}(x)&{\frac {\partial g_{2}}{\partial x_{2}}}(x)&\ldots &{\frac {\partial g_{2}}{\partial x_{n}}}(x)\\\vdots &\vdots &\ddots &\vdots \\{\frac {\partial g_{n}}{\partial x_{1}}}(x)&{\frac {\partial g_{n}}{\partial x_{2}}}(x)&\ldots &{\frac {\partial g_{n}}{\partial x_{n}}}(x)\end{pmatrix}}\in \mathbb {R} ^{n\times n}

gegeben ist, gewinnen. Dazu definieren wir:

Definition 5.12

Eine Menge $D\subseteq \mathbb {R} ^{n}$ heißt konvex, falls für je zwei Elemente $x,y\in D$ auch die ganze Verbindungsstrecke von $x$ nach $y$ zu $D$ gehört, d. h. falls

x,y\in D,\quad t\in [0,1]\Rightarrow tx+(1-t)y\in D.

Damit lässt sich bekanntlich das folgende Lemma aus dem Mittelwertsatz der Differentialrechnung ableiten.

Lemma 5.13

Es sei $g\in C^{1}(D,\mathbb {R} ^{n})$ für eine offene, konvexe Menge $D\subseteq \mathbb {R} ^{n}$ und für eine Konstante $L>0$ gelte

\|{\mathcal {J}}_{g}(x)\|\leq L,\quad x\in D.

Dann folgt die Abschätzung

\|g(x)-g(y)\|\leq L\|x-y\|,\quad x,y\in D.

Dazu geben wir Beispiele.

Beispiel 5.14

(1) Die Funktion $f(x):=x^{2}$ ist auf $[0,0.4]$ eine Kontraktion, denn es ist

f([0,0.4])=[0,0.16]\subseteq [0,0.4]

und mit $L:=\max _{x\in [0,0.4]}(2x)=0.8$

\left|x^{2}-y^{2}\right|\leq 0.8|x-y|,\quad x,y\in [0,0.4].

(2) Die Funktion $f(x):={\sqrt {x}}$ ist auf $[0,a]$ mit $a>0$ nicht Lipschitz-stetig, denn für $y=0$ hat man

\left|{\sqrt {x}}-{\sqrt {0}}\right|={\sqrt {x}}={\frac {1}{\sqrt {x}}}(x-0)={\frac {1}{\sqrt {x}}}|x-0|,\quad x\in (0,a]

und $\lim _{x\to 0}(1/{\sqrt {x}})=\infty$ .

Der folgende sog. Banachsche Fixpunktsatz gibt an, dass die Fixpunktiteration (5.17) konvergiert, und zwar für allgemeines $n$ und ohne Differenzierbarkeitsforderungen an $g$ , wobei als Startvektor alle Elemente $x^{0}$ der zugrunde gelegten Menge zugelassen sind. Überdies liefert er unter den genannten Voraussetzungen die Existenz eines eindeutigen Fixpunktes. Die geforderte Kontraktionseigenschaft für die Iterationsfunktion $g$ ist allerdings eine relativ starke Voraussetzung.

Satz 5.15

Sei $D\subseteq \mathbb {R} ^{n}$ abgeschlossen und die Abbildung $g:D\to D$ bezüglich der Vektornorm $\|\cdot \|:\mathbb {R} ^{n}\to \mathbb {R} _{+}$ eine Kontraktion mit Konstante $L\in (0,1)$ . Dann gilt:

(i) $g$ besitzt genau einen Fixpunkt $x^{*}\in D$ .

(ii) Für jeden Startpunkt $x^{0}\in D$ liefert die Fixpunktiteration

(5.19)

x^{k+1}=g(x^{k}),\quad k=0,1,\ldots

eine Folge $(x^{k})$ in $D$ , welche gegen $x^{*}$ konvergiert und man hat

(5.20)

\left\|x^{k}-x^{*}\right\|\leq {\frac {L}{1-L}}\left\|x^{k}-x^{k-1}\right\|\leq {\frac {L^{k}}{1-L}}\left\|x^{1}-x^{0}\right\|,\quad k=1,2,\ldots .

Beweis.

(i) Sind $x^{*},y^{*}\in D$ Fixpunkte von $g$ , so gilt

\|x^{*}-y^{*}\|=\|g(x^{*})-g(y^{*})\|\leq L\|x^{*}-y^{*}\|

bzw. $(1-L)\|x^{*}-y^{*}\|\leq 0$ , was $x^{*}=y^{*}$ impliziert. Also besitzt $g$ höchstens einen Fixpunkt.

(ii) Sei nun der Startvektor $x^{0}\in D$ beliebig und $(x^{k})$ bezeichne die damit durch die Fixpunktiteration (5.19) erzeugte Folge. Für $x^{k}\in D$ ist dann offenbar auch $g(x^{k})=x^{k+1}$ in $D$ , so dass $x^{k}\in D$ $(k\in \mathbb {N} _{0})$ folgt. Man hat somit weiter

\|x^{\ell +1}-x^{\ell }\|=\|g(x^{\ell })-g(x^{\ell -1})\|\leq L\|x^{\ell }-x^{\ell -1}\|,\quad \ell \in \mathbb {N} _{0},

so dass man die folgenden Abschätzungen für $k,n\in \mathbb {N} _{0}$ erhält:

\left\|x^{k+n}-x^{k}\right\|=\left\|\left(x^{k+1}-x^{k}\right)+\left(x^{k+2}-x^{k+1}\right)+\ldots +\left(x^{k+n}-x^{k+n-1}\right)\right\|

=\left\|x^{k+1}-x^{k}\right\|+\left\|x^{k+2}-x^{k+1}\right\|+\ldots +\left\|x^{k+n}-x^{k+n-1}\right\|

\leq \left\|x^{k+1}-x^{k}\right\|+L\left\|x^{k+1}-x^{k}\right\|+\ldots +L^{n-1}\left\|x^{k+1}-x^{k}\right\|=\left(\sum _{\ell =0}^{n-1}L^{\ell }\right)\left\|x^{k+1}-x^{k}\right\|

\leq {\frac {1-L^{n}}{1-L}}\left\|x^{k+1}-x^{k}\right\|\leq {\frac {1}{1-L}}\left\|x^{k+1}-x^{k}\right\|\leq {\frac {L}{1-L}}\left\|x^{k}-x^{k-1}\right\|\leq {\frac {L^{k}}{1-L}}\left\|x^{1}-x^{0}\right\|.

Also gilt

(5.21)

\left\|x^{k+n}-x^{k}\right\|\leq {\frac {L}{1-L}}\left\|x^{k}-x^{k-1}\right\|\leq {\frac {L^{k}}{1-L}}\left\|x^{1}-x^{0}\right\|,\quad k,n\in \mathbb {N} _{0}.

Demnach ist die Folge $(x^{k})$ eine Cauchy-Folge und hat sie als solche einen Grenzwert $x^{*}\in D$ . Da $g$ nach Voraussetzung (Lipschitz-)stetig ist und die Fixpunktiteration dann, wenn sie konvergiert, gegen einen Fixpunkt konvergiert, ist $x^{*}$ der (eindeutige) Fixpunkt von $g$ . Der Grenzübergang „ $n\to \infty$ “ in (5.21) liefert schließlich die Abschätzung (5.20).

q.e.d.

Man beachte, dass man unter den Voraussetzungen des Banachschen Fixpunktsatzes mindestens lineare Konvergenz für die Fixpunktiteration hat, denn dann gilt

\left\|x^{k+1}-x^{*}\right\|=\left\|g(x^{k})-g(x^{*})\right\|\leq L\left\|x^{k}-x^{*}\right\|,\quad k\in \mathbb {N} _{0},

wobei $L\in (0,1)$ ist. Der Ausdruck

{\frac {L^{k}}{1-L}}\left\|x^{1}-x^{0}\right\|

in (5.20) kann, nachdem $x^{1}$ berechnet wurde, für jedes $k\in \mathbb {N}$ vor Beginn der Iteration bestimmt werden. Er ermöglicht eine a priori Fehlerabschätzung für den Approximationsfehler $\left\|x^{k}-x^{*}\right\|$ . Weiter hat man wegen $L\in (0,1)$ für eine Abbruchschranke $\varepsilon >0$

{\frac {L^{k}}{1-L}}\left\|x^{1}-x^{0}\right\|\leq \varepsilon \Leftrightarrow k\log(L)\leq \log \left({\frac {(1-L)\varepsilon }{\|x^{1}-x^{0}\|}}\right)\Leftrightarrow k\geq a

mit

a:=\log \left({\frac {(1-L)\varepsilon }{\|x^{1}-x^{0}\|}}\right)/\log(L),

so dass mit (5.21) folgt:

k\geq a\Rightarrow \left\|x^{k+1}-x^{*}\right\|\leq \varepsilon .

Praktisch ist also spätestens in Schritt $k:=k(\varepsilon )$ mit

(5.22)

k(\varepsilon )=\lceil a\rceil

die Fehlerabschätzung $\left\|x^{k}-x^{*}\right\|\leq \varepsilon$ erfüllt, wobei $\lceil a\rceil$ die kleinste ganze Zahl $\geq a$ bezeichnet.

Der mittlere Ausdruck in (5.20) kann im $k$ -ten Iterationsschritt bestimmt werden und erlaubt eine a posteriori Fehlerabschätzung für den Approximationsfehler $\left\|x^{k}-x^{*}\right\|$ . Praktisch wird für eine gegebene Schranke $\varepsilon >0$ in Schritt $k:=k(\varepsilon )$ abgebrochen, wenn erstmalig

{\frac {L}{1-L}}\left\|x^{k}-x^{k-1}\right\|\leq \varepsilon

erfüllt ist. In diesem Fall genügt $x^{k}$ der Fehlerabschätzung $\left\|x^{k}-x^{*}\right\|\leq \varepsilon$ .

Wir geben dazu ein Beispiel.

Beispiel 5.16

Es sei

f(x):=x-e^{-x},\quad x\in \mathbb {R} .

Dann hat man

f(x^{*})=0

für

x^{*}\approx 0.567\ 143\ 29.

Diese Nullstelle $x^{*}$ soll nun approximativ berechnet werden. Mit

g(x):=e^{-x},\quad x\in \mathbb {R}

gilt offenbar

g(x^{*})=x^{*}\Leftrightarrow f(x^{*})=0,

so dass wir dazu die Fixpunktiteration $x_{k+1}=g(x_{k})$ mit der Iterationsfunktion $g$ anwenden wollen.

Dafür müssen wir zunächst die Voraussetzungen von Satz 5.15 überprüfen. Auf dem Intervall $D:=[0.5,0.69]$ ist $g$ monoton fallend und somit

g(D)=[e^{-0.69},e^{-0.5}]\subseteq [0.5,0.61]\subseteq D

sowie

L:=\max _{x\in [0.5,0.69]}|g'(x)|=\max _{x\in [0.5,0.69]}e^{-x}=e^{-1/2}\approx 0.606\ 531.

Also ist $g$ eine Kontraktion. Die folgende Tabelle liefert für den Startwert $x_{0}:=0.55$ ausgewählte Iterierte des Verfahrens:

{\begin{array}{c|c||c|c||c|c}k&x_{k}&k&x_{k}&k&x_{k}\\\hline &&\vdots &\vdots &\vdots &\vdots \\0&0.550\ 000\ 00&10&0.567\ 083\ 94&20&0.567\ 143\ 09\\1&0.576\ 949\ 81&11&0.567\ 176\ 95&21&0.567\ 143\ 40\\2&0.561\ 608\ 77&12&0.567\ 124\ 20&22&0.567\ 143\ 23\\3&0.570\ 290\ 86&13&0.567\ 154\ 12&23&0.567\ 143\ 32\\4&0.565\ 360\ 97&14&0.567\ 137\ 15&24&0.567\ 143\ 27\\\vdots &\vdots &\vdots &\vdots &\vdots &\vdots \end{array}}

Die Situation soll nun für $k=12$ genauer betrachtet werden. Die Fehlerabschätzung (5.20) liefert in diesem Fall

{\frac {L^{12}}{1-L}}|x_{1}-x_{0}|={\frac {0.606\ 531^{12}}{1-0.606\ 531}}0.026\ 949\ 81=1.70\cdot 10^{-4},

{\frac {L}{1-L}}|x_{12}-x_{11}|={\frac {0.606\ 531}{1-0.606\ 531}}0.000\ 052\ 75=8.13\cdot 10^{-5}.

Der tatsächliche Fehler

|x_{12}-x^{*}|\approx 1.91\cdot 10^{-5}

wird also durch die a posteriori Abschätzung um etwa den Faktor 4 und durch die a priori Abschätzung um etwa den Faktor 9 überschätzt.

Das praktische Vorgehen soll nun für die spezielle Fehlerschranke $\varepsilon =0.007\ 6$ illustriert werden. Der (üblicherweise unbekannte) Approximationsfehler unterschreitet diese Schranke bereits für $k=2$ , denn man hat $|x_{2}-x^{*}|\approx 0.005\ 5\leq \varepsilon$ . Die a posteriori Abschätzung liefert dagegen für $k=4$

|x_{4}-x^{*}|\leq {\frac {e^{-1/2}}{1-e^{-1/2}}}|0.565\ 360\ 97-0.570\ 290\ 86|=0.007\ 599\leq \varepsilon ,

also $k(\varepsilon ):=4$ als Stoppzahl, während die a priori Abschätzung in (5.22) mit

Fehler beim Parsen (Syntaxfehler): {\displaystyle a = \log \left( \frac{(1 - L) \varepsilon}{\|x^1 - x^0\|} \right) / \log(L) = \log \left( \frac{\left( 1 - e^{-1/2} \right) 0.007\ 6}{0.576\ 949\ 81 - 0.55} / \log(e^{-1/2}) \approx 4.397}

die Vorhersage $k(\varepsilon ):=5$ macht.

5.4 Das Newton-Verfahren im $\mathbb {R} ^{n}$

4.1 Grundlagen

Es sei $D\subseteq \mathbb {R} ^{n}$ eine offene Menge und $F:D\subseteq \mathbb {R} ^{n}\to \mathbb {R} ^{n}$ eine Funktion mit

F(x):=(F_{1}(x),\ldots ,F_{n}(x))^{T},\quad x\in D

und stetigen partiellen Ableitungen $(\partial F_{i}/\partial x_{j})(x)$ $(i,j=1,\ldots ,n)$ , es sei also $F\in C^{1}(D,\mathbb {R} ^{n})$ . Die zu $F$ gehörige Jacobi-Matrix bezeichnen wir mit

{\mathcal {J}}_{F}(x):=\left({\frac {\partial F_{i}}{\partial x_{j}}}(x)\right)_{i,j=1,\ldots ,n}\in \mathbb {R} ^{n\times n}.

Mit $\|\cdot \|$ ist im ganzen Abschnitt 5.4 wieder die Euklidische Norm auf dem $\mathbb {R} ^{n}$ bzw. die durch sie induzierte Spektralnorm gemeint.

Schließlich werden wir von dem folgenden Lemma Gebrauch machen.

Lemma 5.17

Sei $v:[a,b]\to \mathbb {R} ^{n}$ eine stetige vektorwertige Funktion, sei $v(t):=(v_{1}(t),\ldots ,v_{n}(t))^{T}$ für $t\in [a,b]$ und sei $u:=\int \limits _{a}^{b}v(t)\,dt$ der Vektor mit den Komponenten $u_{i}:=\int \limits _{a}^{b}v_{i}(t)\,dt$ . Dann gilt:

\left\|\int \limits _{a}^{b}v(t)\,dt\right\|\leq \int \limits _{a}^{b}\|v(t)\|\,dt

Beweis.

Es sei $K:=\|u\|$ . Dann kann man unter Verwendung des Standardskalarprodukts

\langle x,y\rangle :=\sum _{i=1}^{n}x_{i}y_{i},\quad x,y\in \mathbb {R} ^{n}

auf dem $\mathbb {R} ^{n}$ und der Cauchy-Schwarz-Ungleichung abschätzen:

K^{2}=\langle u,u\rangle =\left\langle \int \limits _{a}^{b}v(t)\,dt,u\right\rangle =\sum _{i=1}^{n}u_{i}\int \limits _{a}^{b}v_{i}(t)\,dt=\int \limits _{a}^{b}\sum _{i=1}^{n}u_{i}v_{i}(t)\,dt=\int \limits _{a}^{b}\langle u,v(t)\rangle \,dt\leq \int \limits _{a}^{b}\|u\|\|v(t)\|\,dt

=K\int \limits _{a}^{b}\|v(t)\|\,dt.

q.e.d.

5.4.2 Das Verfahren

Es sei wieder $D\subseteq \mathbb {R} ^{n}$ eine offene Menge und es sei $F\in C^{1}(D,\mathbb {R} ^{n})$ mit

F(x)=(F_{1}(x),\ldots ,F_{n}(x))^{T},\quad x\in D

und Jacobi- bzw. Funktionalmatrix ${\mathcal {J}}_{F}(x)$ gegeben. Es soll nun das Newton-Verfahren zur Bestimmung einer Lösung $x^{*}\in D$ des Gleichungssystems

F(x)=0\Leftrightarrow F_{i}(x_{1},\ldots ,xn)=0\quad (i=1,\ldots ,n)

vorgestellt und seine Konvergenz untersucht werden. Für $n=1$ hatten wir dies bereits in Abschnitt 5.2.4 getan.

Die Iterationsvorschrift des Newton-Verfahrens lautete im Fall $n=1$

x_{k+1}:=x_{k}-[f'(x_{k})]^{-1}f(x_{k}),

wobei sich $x_{k+1}$ als Nullstelle einer linearen Approximation von $f$ , der Tangente bei $x_{k}$ an $f$ , ergab. Ähnlich kann man für eine Funktion $F\in C^{1}(D,\mathbb {R} ^{n})$ mit beliebigem $n\in \mathbb {N}$ das Newton-Verfahren dadurch motivieren, dass man $x^{k+1}$ als Nullstelle der linearen Approximation von $F$ bei $x^{k}$

F_{k}(x):=F(x^{k})+{\mathcal {J}}_{F}(x^{k})\left(x-x^{k}\right)

wählt. Dieses Vorgehen führt zu der allgemeinen Iterationsvorschrift

(5.23)

x^{k+1}:=x^{k}-\left[{\mathcal {J}}_{F}(x^{k})\right]^{-1}F(x^{k}),\quad k\in \mathbb {N} _{0}

des Newton-Verfahrens. Wir gehen hier implizit davon aus, dass die Jacobi-Matrix ${\mathcal {J}}_{F}(x^{k})$ des Systems für jedes $k\in \mathbb {N} _{0}$ nichtsingulär ist. Da man, wenn immer möglich, die Berechnung der Inversen einer Matrix vermeiden sollte, geht man praktisch bei der Berechnung von $x^{k+1}$ von der zu (5.23) äquivalenten Gleichung

{\mathcal {J}}_{F}(x^{k})(\underbrace {x^{k+1}-x^{k}} _{=:h^{k}})=-F(x^{k})

aus und bestimmt man die eindeutige Lösung $h^{k}$ des linearen Gleichungssystems

{\mathcal {J}}_{F}(x^{k})h=-F(x^{k}).

Anschließend setzt man

x^{k+1}:=x^{k}+h^{k}.

Das Newton-Verfahren lautet somit wie folgt:

Algorithmus 9 (Newton-Verfahren)

(0) Wähle

x^{0}\in D

und ein

\varepsilon >0

. Berechne

F(x^{0})

und setze

k:=0

.

(1) Berechne

{\mathcal {J}}_{F}(x^{k})

und bestimme die eindeutige Lösung

h^{k}\in \mathbb {R} ^{n}

von

(5.24)

{\mathcal {J}}_{F}(x^{k})h=-F(x^{k}).

(2) Setze

x^{k+1}:=x^{k}+h^{k}

und berechne

F(x^{k+1})

.

(3) Falls

\left\|F(x^{k+1})\right\|_{2}\leq \varepsilon

, stop!

(4) Setze

k:=k+1

und gehe nach (1).

Der folgende Satz besagt, dass das Newton-Verfahren unter geeigneten Voraussetzungen durchführbar, d. h. für alle $k$ insbesondere $x^{k}\in D$ und ${\mathcal {J}}_{F}(x^{k})$ nichtsingulär ist und dass es superlinear bzw. quadratisch konvergiert.

Satz 5.18

Es sei $D\subset \mathbb {R} ^{n}$ offen und $F\in C^{1}(D,\mathbb {R} ^{n})$ . Ferner existiere ein $x^{*}\in D$ , für welches $F(x^{*})=0$ und ${\mathcal {J}}_{F}(x^{*})$ nichtsingulär sei. Dann gibt es eine Umgebung ${\mathcal {U}}_{\delta }(x^{*})$ von $x^{*}$ für ein $\delta >0$ , so dass das Newton-Verfahren, Algorithmus 9, für jeden Startpunkt $x^{0}\in {\mathcal {U}}_{\delta }(x^{*})$ durchführbar ist und die durch ihn ohne das Abbruchkriterium (3) erzeugte Iteriertenfolge $(x^{k})$ superlinear gegen $x^{*}$ konvergiert. Gilt mit einem $L>0$

(5.25)

\|{\mathcal {J}}_{F}(x)-{\mathcal {J}}_{F}(x^{*})\|\leq L\|x-x^{*}\|,\quad x\in {\mathcal {U}}_{\delta }(x^{*}),

so konvergiert $(x^{k})$ gegen $x^{*}$ sogar quadratisch.

Beweis.

Wegen der Stetigkeit von ${\mathcal {J}}_{F}(x)$ auf $D$ können wir zunächst $\eta >0$ so klein wählen, dass gilt:

\|{\mathcal {J}}_{F}(x)-{\mathcal {J}}_{F}(x^{*})\|\leq {\frac {1}{2\left\|[{\mathcal {J}}_{F}(x^{*})]^{-1}\right\|}},\quad x\in {\mathcal {U}}_{\eta }(x^{*}).

Für $x\in {\mathcal {U}}_{\eta }(x^{*})$ ergibt sich damit und mit $\beta :=\left\|[{\mathcal {J}}_{F}(x^{*})]^{-1}\right\|$ gemäß Korollar 2.21 die Invertierbarkeit der Matrix

{\mathcal {J}}_{F}(x)={\mathcal {J}}_{F}(x^{*})+[{\mathcal {J}}_{F}(x)-{\mathcal {J}}_{F}(x^{*})]

sowie die Abschätzung

(5.26)

\left\|[{\mathcal {J}}_{F}(x)]^{-1}\right\|\leq {\frac {\left\|[{\mathcal {J}}_{F}(x^{*})]^{-1}\right\|}{1-\left\|[{\mathcal {J}}_{F}(x^{*})]^{-1}\right\|\|{\mathcal {J}}_{F}(x)-{\mathcal {J}}_{F}(x^{*})\|}}\leq 2\beta .

Sei nun

{\mathcal {N}}(x):=x-[{\mathcal {J}}_{F}(x)]^{-1}F(x),\quad x\in {\mathcal {U}}_{\eta }(x^{*})

die Iterationsfunktion des lokalen Newton-Verfahrens, die nach dem Gezeigten auf ${\mathcal {U}}_{\eta }(x^{*})$ wohldefiniert ist. Mit $F(x^{*})=0$ und den Identitäten

\int \limits _{0}^{1}{\mathcal {J}}_{F}(x^{*}+s(x-x^{*}))(x-x^{*})\,ds=F(x^{*}+s(x-x^{*})){\Big |}_{0}^{1}=F(x)-F(x^{*})=F(x)

schließen wir als nächstes

{\mathcal {N}}(x)-x^{*}=x-x^{*}-[{\mathcal {J}}_{F}(x)]^{-1}[F(x)-F(x^{*})]

=x-x^{*}-[{\mathcal {J}}_{F}(x)]^{-1}\left\{{\mathcal {J}}_{F}(x^{*})(x-x^{*})+\int \limits _{0}^{1}[{\mathcal {J}}_{F}(x^{*}+s(x-x^{*}))-{\mathcal {J}}_{F}(x^{*})](x-x^{*})\,ds\right\}

=-[{\mathcal {J}}_{F}(x)]^{-1}[{\mathcal {J}}_{F}(x^{*})-{\mathcal {J}}_{F}(x)](x-x^{*})-[{\mathcal {J}}_{F}(x)]^{-1}\int \limits _{0}^{1}[{\mathcal {J}}_{F}(x^{*}+s(x-x^{*}))-{\mathcal {J}}_{F}(x^{*})](x-x^{*})\,ds.

Für

(5.27)

\varepsilon (x):=2\beta \left\{\|{\mathcal {J}}_{F}(x^{*})-{\mathcal {J}}_{F}(x)\|+\int \limits _{0}^{1}\|{\mathcal {J}}_{F}(x^{*}+s(x-x^{*}))-{\mathcal {J}}_{F}(x^{*})\|\,ds\right\}

leiten wir daraus unter Anwendung von Lemma 5.17 mit (5.26) die folgende Abschätzung ab:

(5.28)

\|{\mathcal {N}}(x)-x^{*}\|\leq \varepsilon (x)\|x-x^{*}\|.

Wegen der Stetigkeit von ${\mathcal {J}}_{F}(x)$ auf ${\mathcal {U}}_{\eta }(x^{*})$ existiert ein $\delta \in (0,\eta ]$ , so dass $\varepsilon (x)\leq 1/2$ auf ${\mathcal {U}}_{\delta }(x^{*})$ ist und damit gilt:

\|{\mathcal {N}}(x)-x^{*}\|\leq {\frac {1}{2}}\|x-x^{*}\|,\quad x\in {\mathcal {U}}_{\delta }(x^{*}).

Beginnend mit $x^{0}\in {\mathcal {U}}_{\delta }(x^{*})$ , liegt folglich mit $x^{k}\in {\mathcal {U}}_{\delta }(x^{*})$ auch $x^{k+1}:={\mathcal {N}}(x^{k})$ in ${\mathcal {U}}_{\delta }(x^{*})$ und konvergiert die Folge $(x^{k})$ linear gegen $x^{*}$ . Die Konvergenz von $(x^{k})$ impliziert weiter die Konvergenz $\varepsilon (x^{k})\to 0$ $(k\to \infty )$ . Da gemäß (5.28)

(5.29)

\left\|x^{k+1}-x^{*}\right\|\leq \varepsilon (x^{k})\left\|x^{k}-x^{*}\right\|

für alle k gilt, folgt schließlich die superlineare Konvergenz von $(x^{k})$ .

Gilt nun (5.25) auf ${\mathcal {U}}_{\delta }(x^{*})$ , dann liegt für jedes $k$ mit $x^{*}$ und $x^{k}$ auch $x^{*}+s(x^{k}-x^{*})$ für alle $s\in [0,1]$ in ${\mathcal {U}}_{\delta }(x^{*})$ und folgt somit

\left\|{\mathcal {J}}_{F}(x^{*}+s(x^{k}-x^{*}))-{\mathcal {J}}_{F}(x^{*})\right\|\leq L\left\|x^{k}-x^{*}\right\|.

Aus (5.27) gewinnt man damit für alle $k$ die Abschätzung

\varepsilon (x^{k})\leq 2\beta \left\{L+{\frac {1}{2}}L\right\}\left\|x^{k}-x^{*}\right\|=3\beta L\left\|x^{k}-x^{*}\right\|

Letzteres zeigt zusammen mit (5.29) die quadratische Konvergenz der Folge $(x^{k})$ .

q.e.d.

Beispiel 5.19

Gesucht sei die Lösung $x^{*}:=(x_{1}^{*},x_{2}^{*})^{T}$ der beiden Gleichungen

(5.30)

{\begin{matrix}F_{1}(x_{1},x_{2}):=x_{1}^{2}+x_{2}^{2}+0.6x_{2}-0.16=0,\\F_{2}(x_{1},x_{2}):=x_{1}^{2}-x_{2}^{2}+x_{1}-1.6x_{2}-0.14=0,\end{matrix}}

für die $x_{1}^{*},x_{2}^{*}>0$ gilt, wobei wir hier keine Abbruchschranke $\varepsilon >0$ angeben. Die Jacobi-Matrix von $F$ lautet

{\mathcal {J}}_{F}(x)={\begin{pmatrix}2x_{1}&2x_{2}+0.6\\2x_{1}+1&-2x_{2}-1.6\end{pmatrix}}.

Für $(x_{1}^{0},x_{2}^{0})^{T}:=(0.6,0.25)^{T}$ erhält man somit das lineare Gleichungssystem (5.24)

{\begin{pmatrix}1.2&1.1\\2.2&-2.1\end{pmatrix}}{\begin{pmatrix}h_{1}\\h_{2}\end{pmatrix}}=-{\begin{pmatrix}0.4125\\0.3575\end{pmatrix}}.

Dieses besitzt die Lösung

{\begin{pmatrix}h_{1}^{0}\\h_{2}^{0}\end{pmatrix}}={\begin{pmatrix}-0.254\ 960\\-0.096\ 862\end{pmatrix}},

so dass sich

{\begin{pmatrix}x_{1}^{1}\\x_{2}^{1}\end{pmatrix}}={\begin{pmatrix}0.60\\0.25\end{pmatrix}}+{\begin{pmatrix}-0.254\ 960\\-0.096\ 862\end{pmatrix}}={\begin{pmatrix}0.345\ 040\\0.153\ 138\end{pmatrix}}

ergibt mit dem Defekt

{\sqrt {[F_{1}(x_{1}^{1},x_{2}^{1})]^{2}+[F_{2}(x_{1}^{1},x_{2}^{1})]^{2}}}=0.092\ 882\ 7.

Mit $(x_{1}^{1},x_{2}^{1})^{T}$ verfährt man nun analog usw. Für die ersten vier Iterationen ergibt sich insgesamt die folgende Tabelle:

{\begin{array}{|c|c|c|c|c|c|}\hline k&x_{1}^{k}&x_{2}^{k}&\left\|F(x^{k})\right\|&h_{1}^{k}&h_{2}^{k}\\\hline 0&0.600000+0&0.250000+0&0.545859+0&-0.254960+0&-0.096862+0\\\hline 1&0.345040+0&0.153138+0&0.928827-1&-0.675094-1&-0.306747-1\\\hline 2&0.277531+0&0.122463+0&0.658124-2&-0.564594-2&-0.279860-2\\\hline 3&0.271885+0&0.119664+0&0.464212-4&-0.406023-4&-0.210055-4\\\hline 4&0.271845+0&0.119643+0&0.241346-8&&\\\hline \end{array}}

Das Newton-Verfahren, Algorithmus 9, ist invariant gegenüber affin-linearen Transformationen (Übung!). Dies bedeutet, wenn $A\in \mathbb {R} ^{n\times n}$ eine beliebige reguläre Matrix und $c\in \mathbb {R} ^{n}$ irgendein Vektor: Ist $\{x^{k}\}$ die durch das lokale Newton-Verfahren für den Startpunkt $x^{0}$ erzeugte Iteriertenfolge zur Bestimmung einer Lösung des Gleichungssystems $F(x)=0$ , so erzeugt das Verfahren bei Anwendung auf das System

G(z):=F(Az+c)=0

für den Startpunkt $z^{0}:=A^{-1}(x^{0}-c)$ die Iteriertenfolge $\{z^{k}\}$ mit

z^{k}=A^{-1}\left(x^{k}-c\right)\Leftrightarrow x^{k}=Az^{k}+c.

Verfahren, die invariant gegenüber affin-linearen Transformationen sind, gelten gegenüber Verfahren, die diese Eigenschaft nicht besitzen, insofern als robuster, als ihre Konvergenzgeschwindigkeit weit weniger von den gerade vorliegenden speziellen Daten abhängt. Anders als z. B. bei dem CG-Verfahren zur Lösung linearer Gleichungssysteme mit symmetrischer, positiv definiter Matrix (s. Kanzow) ändert sich beim lokalen Newton-Verfahren insbesondere durch eine (affin-)lineare Transformation der Variablen die Konvergenzgeschwindigkeit des Verfahrens nicht. Denn ist $\varepsilon >0$ eine vorgegebene Abbruchschranke, so gilt aufgrund der oben beschriebenen Invarianz gegenüber affin-linearen Transformationen und der sich daraus ergebenden Identitäten

\left\|G(z^{k})\right\|=\left\|F(Az^{k}+c)\right\|=\left\|F(x^{k})\right\|

die Äquivalenz

\left\|F(x^{k})\right\|\leq \varepsilon \Leftrightarrow \left\|G(z^{k})\right\|\leq \varepsilon .

Bei Verfahren, die wie die CG-Verfahren nicht invariant gegenüber affin-linearen Transformationen sind, kann man zwar möglicherweise die Konvergenzgeschwindigkeit durch eine geeignete Wahl der Matrix $A$ erheblich beschleunigen, ist es aber häufig nicht vorhersehbar, ob das Verfahren für die aktuellen Daten langsam konvergiert, oder ist es nicht klar, ob gegebenenfalls eine geeignete Transformation zur Konvergenzbeschleunigung gefunden werden kann. Mit

p^{k}:=\left[{\mathcal {J}}_{F}(x^{k})\right]^{-1}F(x^{k})

lautet die Iterationsvorschrift des Newton-Verfahrens

x^{k+1}:=x^{k}+p^{k},\quad k=0,1,\ldots .

Die Richtung $p^{k}$ bezeichnet man dabei auch als Newton-Richtung in $x^{k}$ .

Es gibt eine große Zahl von Varianten des Newton-Verfahrens, die zum Ziel haben, den Konvergenzbereich des Verfahrens zu vergrößern und/oder seinen numerischen Aufwand zu reduzieren. So kann man das Newton-Verfahren in gewisser Weise globalisieren, indem man eine geeignete Schrittweite $t_{k}>0$ einführt und

x^{k+1}:=x^{k}+t_{k}p^{k},\quad k=0,1,\ldots

definiert. Dabei wählt man $t_{k}$ beispielsweise als (Näherungs-)Lösung des Problems

(5.31)

\min _{t\geq 0}\left\|F(x^{k}+tp^{k})\right\|_{2},

da ja $\left\|F(x^{k+1})\right\|_{2}$ möglichst klein werden sollte. Von dem so modifizierten sog. gedämpften Newton-Verfahren kann man unter relativ schwachen Voraussetzungen für jeden Startpunkt $x^{0}$ einer geeigneten, hinreichend großen Menge Konvergenz zeigen. (Man hat sich dabei zu überlegen, dass ein solches $t_{k}$ existiert und eine positive Zahl ist. Da eine Lösung des globalen Optimierungsproblems (5.31) im Allgemeinen nicht realistisch ist, wählt man die Schrittweite $t_{k}$ häufig aber auf eine andere Weise; siehe z. B. Stoer, wo für eine solche andere Schrittweitenwahl auch ein Konvergenzsatz zu finden ist.)

Eine weitere praktisch relevante Modifikation des Newton-Verfahrens besteht darin, die numerisch aufwendig zu berechnende Jacobi-Matrix ${\mathcal {J}}_{F}(x^{k})$ im Verfahren durch eine geeignete Näherung $H_{k}\in \mathbb {R} ^{n\times n}$ zu ersetzen, wobei $H_{k}$ alleine aus den Daten $x^{k},x^{k-1},F(x^{k})$ und $F(x^{k-1})$ numerisch relativ günstig berechnet werden kann und somit insbesondere keine partiellen Ableitungen benötigt werden. Wir kennen ein solches Vorgehen schon vom Sekantenverfahren her, bei dem der Faktor

{\frac {x_{k}-x_{k-1}}{f(x_{k})-f(x_{k-1})}},

der eine Näherung für $1/f'(x_{k})$ darstellt, in der Iterationsvorschrift vorkommt. Verfahren dieses Typs werden als Sekanten- oder Quasi-Newton-Verfahren bezeichnet. Das bekannteste ist das Broyden-Verfahren.

Quasi-Newton-Verfahren haben vor allem im Zusammenhang mit der Bestimmung von Extremalpunkten von $F$ und damit der Lösung des Systems $\nabla F(x)=0$ große Bedeutung, da man ja bei Anwendung des Newton-Verfahrens in einem solchen Fall in jeder Iteration die Hesse-Matrix $\nabla ^{2}F(x^{k})$ für $F$ , also etwa $n^{2}/2$ partielle Ableitungen zweiter Ordnung zu berechnen hat. Von solchen Quasi-Newton-Verfahren gibt es eine Reihe von Varianten, die sich durch die Wahl der $H_{k}$ unterscheiden, wobei man im Fall der Lösung von Optimierungsaufgaben zusätzlich bestrebt ist, die positive oder negative (Semi-)Definitheit der Hesse-Matrix in einer Umgebung des Extremalpunktes auch für die $H_{k}$ zu erreichen. Die verbreitetste Methode ist das BFGS-Verfahren, das nach seinen Erfindern Broyden, Fletcher, Goldfarb und Shanno benannt wurde, die das Verfahren 1970 unabhängig voneinander vorschlugen. Es hat sich herausgestellt, dass dieses unter allen Quasi-Newton-Verfahren das wohl unempfindlichste gegenüber der Schrittweitenwahl ist. (Es gibt Alternativen zu der numerisch teuren Berechnung der Minimumschrittweite in (5.31).)

Von Quasi-Newton-Verfahren kann man keine quadratische Konvergenz erwarten, da sie ja weniger Information der Funktion als das Newton-Verfahren verwenden. Unter geeigneten Voraussetzungen lässt sich aber für sie im Allgemeinen superlineare Konvergenz nachweisen. Die schlechtere Konvergenzrate gegenüber dem Newton-Verfahren wird jedoch durch den pro Iteration erforderlichen, geringeren numerischen Aufwand kompensiert.

Allgemein kann man sagen, dass das Newton-Verfahren wohl das erfolgreichste und verbreitetste Verfahren der Mathematik ist. Es wurde im Hinblick auf die Lösung zahlloser Probleme, auch solcher in unendlich-dimensionalen Räumen, verallgemeinert und modifiziert.

This article is issued from Wikiversity. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

5.1 Konvergenzraten

Definition 5.1

Beispiel 5.2

Beispiel 5.3

5.2 Nullstellenbestimmung reeller Funktionen einer Veränderlichen

5.2.1 Das Bisektionsverfahren

Algorithmus 5 (Bisektionsverfahren)

Beispiel 5.4

Beispiel 5.5

5.2.2 Die Regula falsi

Algorithmus 6 (Regula Falsi)

5.2.3 Das Sekantenverfahren

Algorithmus 7 (Sekantenverfahren)

Satz 5.6

Beispiel 5.7

5.2.4 Das Newton-Verfahren

Algorithmus 8 (Newton-Verfahren)

Beispiel 5.8

Satz 5.9

Beweis.

Satz 5.10

Beweis.

5.3 Fixpunktiteration

Definition 5.11

Definition 5.12

Lemma 5.13

Beispiel 5.14

Satz 5.15

Beweis.

Beispiel 5.16

5.4 Das Newton-Verfahren im R n {\displaystyle \mathbb {R} ^{n}}

4.1 Grundlagen

Lemma 5.17

Beweis.

5.4.2 Das Verfahren

Algorithmus 9 (Newton-Verfahren)

Satz 5.18

Beweis.

Beispiel 5.19

5.4 Das Newton-Verfahren im $\mathbb {R} ^{n}$