Das Newtonsche Verfahren.

3.15.2 Das Newtonsche Verfahren.

Im Newtonschen Verfahren (der Tangentenmethode) ersetzen wir die Funktion $f (x)$ durch Tangenten an diese Funktion. Wir nehmen zunächst an, dass einer der Fälle (a) oder (d) vorliegt. Die Gleichung der Tangente im Punkt $b$ ist gegeben durch¹⁶

g (x) = f (b) + f^{'} (b) (x - b) .

Diese Tangente schneidet die $x$ -Achse im Punkt

x_{1} = b - \frac{f (b)}{f^{'} (b)} .

Da diese Tangente im Fall (a) unterhalb einer monoton wachsenden konvexen Funktion und im Fall (d) oberhalb einer monoton fallenden konkaven Funktion liegt, so gilt $ξ < x_{1} < b$ . Iteriert man dieses Verfahren durch

x_{n + 1} = x_{n} - \frac{f (x_{n})}{f^{'} (x_{n})},

(3.57)

so erhält man eine monoton fallende Folge ${x_{n}}_{n = 1}^{\infty}$ mit

ξ < \dots < x_{n} < \dots < x_{1} < b .

Als monotone und beschränkte Folge besitzt ${x_{n}}_{n = 1}^{\infty}$ einen Grenzwert $x^{*}$ . Geht man in (3.57) zum Grenzwert über, so erhält man

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

Wegen $f^{'} (x^{*}) \neq 0$ ist dies äquivalent zu $f (x^{*}) = 0$ . Damit konvergiert die Folge ${x_{n}}_{n = 1}^{\infty}$ gegen $ξ$ .

Wir führen nun eine Fehlerabschätzung für diese Konvergenz durch. Die Taylorsche Formel für $f$ im Punkt $ξ$ gibt wegen $f (ξ) = 0$ die Identität

f (x) = f^{'} (ξ) (x - ξ) + \frac{f^{''} (ξ)}{2!} {(x - ξ)}^{2} + o ({(x - ξ)}^{2}), x \to ξ .

(3.58)

Wegen der Beschränktheit von $f$ existiert damit eine Konstante $M$ , so dass

| f (x) - f^{'} (ξ) (x - ξ) | \leq M {(x - ξ)}^{2}, x \in] a, b [.

(3.59)

Wir setzen $h_{n} = ξ - x_{n}$ . Dann gilt unter Anwendung von (3.57) und (3.59) $\begin{array}{rcl} | h_{n + 1} | & = & | ξ - x_{n + 1} | = |ξ - x_{n} + \frac{f (x_{n})}{f^{'} (x_{n})}| \\ = & |\frac{h_{n} f^{'} (x_{n})}{f^{'} (x_{n})} - \frac{h_{n} f^{'} (ξ)}{f^{'} (x_{n})} + \frac{f (x_{n}) + f^{'} (ξ) h_{n}}{f^{'} (x_{n})}| \\ \leq & |\frac{h_{n}}{f^{'} (x_{n})} (f^{'} (x_{n}) - f^{'} (ξ))| + M |\frac{h_{n}^{2}}{f^{'} (x_{n})}| . \end{array}$

Nach der Formel von Lagrange gilt $f^{'} (ξ) - f^{'} (x_{n}) = f^{''} (c) h_{n}$ für einen gewissen Punkt $c$ zwischen $ξ$ und $x_{n}$ . Nach Satz 2.13.7 ist $min_{x \in [a, b]} | f^{'} (x) | > 0$ und damit

| h_{n + 1} | \leq \frac{M}{min_{x \in [a, b]} | f^{'} (x) |} | h_{n} |^{2}, n \in ℕ .

(3.60)

Im weiteren Verlauf der Vorlesung werden wir sehen, dass man die Taylorsche Zerlegung (3.58) folgendermassen spezifizieren kann: Unter den gegebenen Voraussetzungen gilt

f (x) = f^{'} (ξ) (x - ξ) + \frac{f^{''} (c)}{2!} {(x - ξ)}^{2}

für einen gewissen Punkt $c$ zwischen $ξ$ und $x$ . Damit lässt sich die Konstante $M$ in (3.59) durch $max_{x \in [a, b]} | f^{''} (x) |$ ersetzen, was die Schranke (3.60) in

| h_{n + 1} | \leq \frac{max_{x \in [a, b]} | f^{''} (x) |}{min_{x \in [a, b]} | f^{'} (x) |} | h_{n} |^{2}, n \in ℕ,

(3.61)

überführt.

Im Fall (b) oder (c) beginnt die Konstruktion der Tangenten im Punkt $a$ und führt auf gleiche Weise zu einer monoton wachsenden Folge ${x_{n}}_{n = 1}^{\infty}$ , welche gegen $ξ$ konvergiert. Die Abschätzung (3.61) lässt sich auf diesen Fall ausweiten.

¹⁶Wir setzen voraus, dass die halbseitige Ableitung $f^{'} (b - 0)$ existiert und dass deren Wert mit der stetigen Fortsetzung von $f^{'} (x)$ zu $f^{'} (b)$ übereinstimmt.

[prev] [prev-tail] [front] [up]