Aus Wikiversity

Inhaltsverzeichnis

1 5.1 Konvergenzraten
- 1.1 Definition 5.1
  - 1.1.1 Beispiel 5.2
  - 1.1.2 Beispiel 5.3
2 5.2 Nullstellenbestimmung reeller Funktionen einer Veränderlichen
3 5.3 Fixpunktiteration
4 5.4 Das Newton-Verfahren im
- 4.1 4.1 Grundlagen
  - 4.1.1 Lemma 5.17
    - 4.1.1.1 Beweis.
- 4.2 5.4.2 Das Verfahren
  - 4.2.1 Algorithmus 9 (Newton-Verfahren)
  - 4.2.2 Satz 5.18
    - 4.2.2.1 Beweis.
    - 4.2.2.2 Beispiel 5.19

[Bearbeiten] 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 $\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.

[Bearbeiten] Definition 5.1

Sei $\|\cdot\|$ eine Norm auf dem $\R^n$ und $(x k)$ eine Folge in $\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 \R^n$ ), wenn mit einem $k_0 \in \N$ und einem $C > 0$

(5.1) $\left\| x^{k+1} - x^* \right\| \le C\left\| x^k - x^* \right\|, \quad 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 \R^n$ ), wenn $x^k \neq x^*, k \ge k_0$ für ein $k_0 \in \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 \ge k_0$ für ein $k_0 \in \N$ “ bei der Definition der superlinearen Konvergenz kann man vermeiden, indem man diese mit einer Folge $(\varepsilon_k)$ von Zahlen $\varepsilon_k \ge 0$ mit $\lim_{k \to \infty} \varepsilon_k = 0$ durch

(5.3) $\left\| x^{k+1} - x^* \right\| \le \varepsilon_k \left\| x^k - x^* \right\|, \quad k \ge k_1$

für ein $k_1 \in \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).$

[Bearbeiten] 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^{2k}$

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 1k} \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 \N$

$\left\|x^{k+1} - x^*\right\| \le \left( C \left\|x^k - x^*\right\| \right) \left\|x^k - x^*\right\|, \quad k \ge 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 \N$ , so dass gilt:

(5.4) $\left\| x^{k+1} - x^* \right\| \le \varepsilon \left\| x^k - x^* \right\|, \quad k \ge 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\| \le C \left\| x^k - x^* \right\| \le C^2 \left\| x^{k-1} - x^* \right\| \le C^{k-k_0+1} \left\| x^{k_0} - x^* \right\|, \quad k \ge 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.

[Bearbeiten] Beispiel 5.3

Für die gegen 1 konvergierende Folge $(x k)$ mit $x_k = 1 + 0.99^k, k \in \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\| \le \left\| x^* - x^k \right\|^2, \quad k \ge 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\| \le 5 \cdot 10^{-(\ell+1)}$ hat und somit im $(k + 1)$ -ten Schritt einen Fehler

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

$\alpha \|x\|_b \le \|x\|_a \le \beta \|x\|_b, \quad x \in \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 \le \left\| x^{k+1} - x^* \right\|_a \le \varepsilon_k \left\| x^k - x^* \right\|_a \le \beta \varepsilon_k \left\| x^k - x^* \right\|_b, \quad k \ge k_1$

impliziert und damit für die Nullfolge ${η k}$ mit $\eta_k := (\beta/\alpha) \varepsilon_k$ auch

$\left\| x^{k+1} - x^* \right\|_b \le \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 \le 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 $\R^n$ bezüglich einer Norm nicht notwendig die lineare Konvergenz hinsichtlich einer anderen Norm auf dem $\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 \le 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).

[Bearbeiten] 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 $[α,β]$ in $[a, b]$ zu ermitteln, in dem ein und zwar möglichst nur ein solches $x *$ liegt. Dazu berechnet man im Allgemeinen Funktionswerte $f (ξ 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 \N$ . Die Menge aller $ξ i$ bezeichnet man auch als ein Gitter in $[a, b]$ , die $ξ 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 $[ξ i,ξ i + 1]$ eine (einfache) Nullstelle besitzen und können wir $α: = ξ i$ und $β: = ξ 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.

[Bearbeiten] 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.

[Bearbeiten] 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 12 (a_k + b_k)$ und

f (x k + 1)

.

(2) Falls $|f(x_{k+1})| \le \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 12 |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} \le x^* \le 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^*| \le |b_{k+1} - a_{k+1}| \le \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})| \le \varepsilon$ in Schritt (2) von Algorithmus 5 nach endlich vielen Schritten erfüllt. Statt dieses Abbruchkriteriums, das beispielsweise im Fall

$0 \le 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| \le \vartheta$ mit einer kleinen Konstante $\vartheta > 0$ als Abbruchkriterium verwenden.

[Bearbeiten] Beispiel 5.4

Ist $b 0 - a 0 = 1$ , so folgt aus (5.6)

$|x_1 - x^*| \le 0.5,$

$|x_5 - x^*| \le [0.5]^5 \approx 0.031,$

$|x_{20} - x^*| \le [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 * | .

[Bearbeiten] 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.

[Bearbeiten] 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.

[Bearbeiten] 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})| \le \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.

[Bearbeiten] 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:

[Bearbeiten] 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})| \le \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 \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):

[Bearbeiten] 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 $sgn(f (x k)) = 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.

[Bearbeiten] 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^2_k - 2\right] \frac{x_k - x_{k-1}}{x^2_k - x^2_{k-1}} = x_k - \frac{x^2_k - 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.

[Bearbeiten] 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:

[Bearbeiten] 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})| \le \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.

[Bearbeiten] Beispiel 5.8

Es sei wieder $f (x): = x 2 - 2$ und damit $f'(x) = 2 x$ . 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^2_k - 2}{2x_k} = \frac 12 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: \R^n \to \R^n$ nennen wir einen Punkt $x^* \in \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 \R: |x - x^*| < \delta\}$

eine offene $δ$ -Umgebung des Punktes $x^* \in \R$ bezeichne.

[Bearbeiten] Satz 5.9

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

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

Dann existiert ein $δ > 0$ , so dass die durch

$x_{k+1} := g(x_k), \quad k \in \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$ .

[Bearbeiten] Beweis.

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

$g(x) = \sum^p_{i=0} \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 $δ > 0$ existiert und

$|g(x) - x^*| \le \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, $δ$ so klein zu wählen, dass $\tilde C(x) \le 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^*| \le \delta$ auch $|g(x) - x^*| \le \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 \N$ , so dass man

$|x_{k+1} - x^*| \le C |x_k - x^*|^p \le \tilde C |x_k - x^*| \le \tilde C^{k+1} |x_0 - x^*|, \quad k \in \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^*| \ge \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 \N$

$\hat C |x_k - x^*|^p \le |x_{k+1} - x^*| \le \overline C |x_k - x^*|^{p+1}, \quad k \ge k_0$

und damit im Widerspruch zu Konvergenz von $(x k)$ gegen $x *$

$0 < \frac{\hat C}{\overline C} \le |x_k - x^*|, \quad k \ge k_0.$

q.e.d.

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

[Bearbeiten] Satz 5.10

Es sei $f: \R \to \R$ gegeben und es existiere $x^* \in \R$ mit $f (x *) = 0$ . Mit einem $η > 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 \ge 3$ .

(ii) Ist $x *$ andererseits eine $m$ -fache Nullstelle von $f$ mit einem $m \ge 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 1m$

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.

[Bearbeiten] 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')^3f'' + 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 1m.$

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.

[Bearbeiten] 5.3 Fixpunktiteration

Wir verallgemeinern zunächst die Fixpunktiteration auf Funktionen $g: \R^n \to \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 \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 \R^n$ . Wir definieren nun zunächst:

[Bearbeiten] Definition 5.11

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

(5.18) $\|g(x) - g(y)\| \le 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, \R^n)$ für $D \subseteq \R^n$ , wobei wir damit eine Funktion $g: D \subseteq \R^n \to \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 \R^{n \times n}$

gegeben ist, gewinnen. Dazu definieren wir:

[Bearbeiten] Definition 5.12

Eine Menge $D \subseteq \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.

[Bearbeiten] Lemma 5.13

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

$\|\mathcal J_g(x)\| \le L, \quad x \in D.$

Dann folgt die Abschätzung

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

Dazu geben wir Beispiele.

[Bearbeiten] 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| \le 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.

[Bearbeiten] Satz 5.15

Sei $D \subseteq \R^n$ abgeschlossen und die Abbildung $g: D \to D$ bezüglich der Vektornorm $\|\cdot\|: \R^n \to \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\| \le \frac{L}{1 - L} \left\| x^k - x^{k-1} \right\| \le \frac{L^k}{1 - L} \left\| x^1 - x^0 \right\|, \quad k = 1, 2, \ldots.$

[Bearbeiten] Beweis.

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

$\|x^* - y^*\| = \|g(x^*) - g(y^*)\| \le L \|x^* - y^*\|$

bzw. $(1 - L) \|x^* - y^*\| \le 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 \N_0)$ folgt. Man hat somit weiter

$\|x^{\ell+1} - x^\ell\| = \|g(x^\ell) - g(x^{\ell-1})\| \le L \|x^\ell - x^{\ell-1}\|, \quad \ell \in \N_0,$

so dass man die folgenden Abschätzungen für $k, n \in \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\|$

$\le \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^{n-1}_{\ell=0} L^\ell \right) \left\| x^{k+1} - x^k \right\|$

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

Also gilt

(5.21) $\left\| x^{k+n} - x^k \right\| \le \frac{L}{1 - L} \left\| x^k - x^{k-1} \right\| \le \frac{L^k}{1 - L} \left\| x^1 - x^0 \right\|, \quad k, n \in \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\| \le L \left\| x^k - x^* \right\|, \quad k \in \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 \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\| \le \varepsilon \Leftrightarrow k \log(L) \le \log \left( \frac{(1 - L) \varepsilon}{\|x^1 - x^0\|} \right) \Leftrightarrow k \ge a$

mit

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

so dass mit (5.21) folgt:

$k \ge a \Rightarrow \left\| x^{k+1} - x^* \right\| \le \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\| \le \varepsilon$ erfüllt, wobei $\lceil a \rceil$ die kleinste ganze Zahl $\ge 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\| \le \varepsilon$

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

Wir geben dazu ein Beispiel.

[Bearbeiten] Beispiel 5.16

Es sei

$f(x) := x - e^{-x}, \quad x \in \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 \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 \le \varepsilon$ . Die a posteriori Abschätzung liefert dagegen für $k = 4$

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

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

Parser-Fehler (Syntaxfehler): 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.

[Bearbeiten] 5.4 Das Newton-Verfahren im $\R^n$

[Bearbeiten] 4.1 Grundlagen

Es sei $D \subseteq \R^n$ eine offene Menge und $F: D \subseteq \R^n \to \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, \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 \R^{n\times n}.$

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

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

[Bearbeiten] Lemma 5.17

Sei $v: [a, b] \to \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^b_a v(t)\, dt$ der Vektor mit den Komponenten $u_i := \int\limits^b_a v_i(t)\, dt$ . Dann gilt:

$\left\| \int\limits^b_a v(t)\, dt \right\| \le \int\limits^b_a \|v(t)\|\, dt$

[Bearbeiten] Beweis.

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

$\langle x, y \rangle := \sum^n_{i=1} x_iy_i, \quad x, y \in \R^n$

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

$K^2 = \langle u, u \rangle = \left\langle \int\limits^b_a v(t)\, dt, u \right\rangle = \sum^n_{i = 1} u_i \int\limits^b_a v_i(t)\, dt = \int\limits^b_a \sum^n_{i = 1} u_iv_i(t)\, dt = \int\limits^b_a \langle u, v(t) \rangle\, dt \le \int\limits^b_a \|u\|\|v(t)\|\, dt$

$= K \int\limits^b_a \|v(t)\|\, dt.$

q.e.d.

[Bearbeiten] 5.4.2 Das Verfahren

Es sei wieder $D \subseteq \R^n$ eine offene Menge und es sei $F \in C^1(D, \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, \R^n)$ mit beliebigem $n \in \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 \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 \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:

[Bearbeiten] 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 \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 \le \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.

[Bearbeiten] Satz 5.18

Es sei $D \subset \R^n$ offen und $F \in C^1(D, \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 $δ > 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^*)\| \le L \|x - x^*\|, \quad x \in \mathcal U_\delta(x^*),$

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

[Bearbeiten] Beweis.

Wegen der Stetigkeit von $\mathcal J_F(x)$ auf $D$ können wir zunächst $η > 0$ so klein wählen, dass gilt:

$\|\mathcal J_F(x) - \mathcal J_F(x^*)\| \le \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\| \le \frac{\left\|[\mathcal J_F(x^*)]^{-1}\right\|}{1 - \left\|[\mathcal J_F(x^*)]^{-1}\right\| \|\mathcal J_F(x) - \mathcal J_F(x^*)\|} \le 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^1_0 \mathcal J_F(x^* + s(x - x^*)) (x - x^*)\, ds = F(x^* + s(x - x^*)) \Big|^1_0 = 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^1_0 [\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^1_0 [\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^1_0 \|\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^*\| \le \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) \le 1/2$ auf $\mathcal U_\delta(x^*)$ ist und damit gilt:

$\|\mathcal N(x) - x^*\| \le \frac 12 \|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\| \le \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\| \le L \left\| x^k - x^* \right\|.$

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

$\varepsilon(x^k) \le 2\beta \left\{ L + \frac 12 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.

[Bearbeiten] 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^2_1 + x^2_2 + 0.6x_2 - 0.16 = 0, \\ F_2(x_1, x_2) := x^2_1 - 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^0_1, x^0_2)^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^0_1 \\ h^0_2 \end{pmatrix} = \begin{pmatrix} -0.254\ 960 \\ -0.096\ 862 \end{pmatrix},$

so dass sich

$\begin{pmatrix} x^1_1 \\ x^1_2 \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^1_2)]^2 + [F_2(x^1_1, x^1_2)]^2} = 0.092\ 882\ 7.$

Mit $(x^1_1, x^1_2)^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^k_1 & x^k_2 & \left\| F(x^k) \right\| & h^k_1 & h^k_2 \\ \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 \R^{n\times n}$ eine beliebige reguläre Matrix und $c \in \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 (A z + 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

die Äquivalenz

$\left\| F(x^k) \right\| \le \varepsilon \Leftrightarrow \left\| G(z^k) \right\| \le \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\ge0} \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 \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.

Kurs:Numerik I/5 Numerische Lösung nichtlinearer Gleichungssysteme

Aus Wikiversity

Inhaltsverzeichnis

[Bearbeiten] 5.1 Konvergenzraten

[Bearbeiten] Definition 5.1

[Bearbeiten] Beispiel 5.2

[Bearbeiten] Beispiel 5.3

[Bearbeiten] 5.2 Nullstellenbestimmung reeller Funktionen einer Veränderlichen

[Bearbeiten] 5.2.1 Das Bisektionsverfahren

[Bearbeiten] Algorithmus 5 (Bisektionsverfahren)

[Bearbeiten] Beispiel 5.4

[Bearbeiten] Beispiel 5.5

[Bearbeiten] 5.2.2 Die Regula falsi

[Bearbeiten] Algorithmus 6 (Regula Falsi)

[Bearbeiten] 5.2.3 Das Sekantenverfahren

[Bearbeiten] Algorithmus 7 (Sekantenverfahren)

[Bearbeiten] Satz 5.6

[Bearbeiten] Beispiel 5.7

[Bearbeiten] 5.2.4 Das Newton-Verfahren

[Bearbeiten] Algorithmus 8 (Newton-Verfahren)

[Bearbeiten] Beispiel 5.8

[Bearbeiten] Satz 5.9

[Bearbeiten] Beweis.

[Bearbeiten] Satz 5.10

[Bearbeiten] Beweis.

[Bearbeiten] 5.3 Fixpunktiteration

[Bearbeiten] Definition 5.11

[Bearbeiten] Definition 5.12

[Bearbeiten] Lemma 5.13

[Bearbeiten] Beispiel 5.14

[Bearbeiten] Satz 5.15

[Bearbeiten] Beweis.

[Bearbeiten] Beispiel 5.16

[Bearbeiten] 5.4 Das Newton-Verfahren im

[Bearbeiten] 4.1 Grundlagen

[Bearbeiten] Lemma 5.17

[Bearbeiten] Beweis.

[Bearbeiten] 5.4.2 Das Verfahren

[Bearbeiten] Algorithmus 9 (Newton-Verfahren)

[Bearbeiten] Satz 5.18

[Bearbeiten] Beweis.

[Bearbeiten] Beispiel 5.19

Ansichten

Persönliche Werkzeuge

Suche

Navigation

Aktuell

Werkzeuge

[Bearbeiten] 5.4 Das Newton-Verfahren im $\R^n$