Das Newton-Raphson-Verfahren

Zusammenfassung

Der Satz von Bolzano sichert, dass eine stetige Funktion, die ihr Vorzeichen wechselt, eine Nullstelle hat, und das Bisektionsverfahren schließt sie ein, wobei es pro Halbierung eine Binärziffer gewinnt. Diese Lektion behandelt ein viel schnelleres Verfahren, wenn es funktioniert: das Newton-Raphson-Verfahren, das den Graphen durch seine Tangente ersetzt und als neue Näherung den Punkt nimmt, in dem die Tangente die waagerechte Achse schneidet. Die so erhaltenen Näherungen werden eine nach der anderen für die ganzen Zahlen $n \geq 0$ definiert, und ihr Grenzwert wird mit der Definition des Grenzwerts, wenn die Variable gegen unendlich strebt, verstanden, ohne die Theorie der Folgen. Die Lektion beweist mit Hilfe der Konvexität, dass die Iterierten, die auf der richtigen Seite beginnen, sich der Nullstelle nähern, ohne sie zu überschreiten, und gegen sie konvergieren, wenn die Ableitung nicht verschwindet und die Funktion konvex oder konkav ist; und mit Hilfe des Mittelwertsatzes, dass der Funktionswert, den man berechnet, den Abstand zur Nullstelle, den man nicht kennt, beschränkt. Sie zeigt danach an Zahlenbeispielen, dass sich die Anzahl der richtigen Ziffern bei jeder Iteration verdoppelt, und auf welche Weisen das Verfahren versagt: eine verschwindende Ableitung, ein Zyklus, eine Divergenz. Die Aufgaben berechnen Kubikwurzeln und Kehrwerte ohne Division, brechen einen Zyklus auf, untersuchen eine doppelte Nullstelle und finden für den Arkustangens die genaue Grenze zwischen Konvergenz und Divergenz.

Lernziele

Die Newton-Raphson-Iterierten einer differenzierbaren Funktion berechnen und in ihnen den Schnittpunkt der Tangente mit der Achse erkennen.
Die monotone Konvergenz der Iterierten beweisen, wenn die Ableitung nicht verschwindet und die Funktion konvex oder konkav ist, und einen Startwert auf der richtigen Seite wählen.
Den Abstand einer Näherung zur Nullstelle mit dem Funktionswert und einer unteren Schranke der Ableitung abschätzen.
Die Weisen erkennen, auf die das Verfahren versagt, und es mit dem Bisektionsverfahren vergleichen, in Schnelligkeit und Sicherheit.

Die Iteration

Es sei $f$ eine differenzierbare Funktion, deren Nullstelle $r$ gesucht wird, und es sei $x_0$ eine erste Näherung. In der Nähe von $x_0$ ähnelt der Graph von $f$ seiner Tangente, $y = f(x_0) + f'(x_0)(x - x_0)$ , gemäß der Definition der Tangente aus der Lektion über die Ableitung als Grenzwert; mit dem Differential aus der Lektion über höhere Ableitungen und das Differential gesagt, ähnelt der Zuwachs $f(x_0 + \Delta x) - f(x_0)$ dem Ausdruck $f'(x_0) \Delta x$ . Die Tangente schneidet die Achse in genau einem Punkt, wenn $f'(x_0) \neq 0$ , und es liegt nahe, ihn als neue Näherung zu nehmen: Man erhält ihn, indem man die Gleichung der Tangente gleich null setzt. Das Verfahren von dem erhaltenen Punkt aus zu wiederholen, ist das Newton-Raphson-Verfahren.

DefinitionNewton-Raphson-Iterierte

Es seien $f$ eine auf einem Intervall $I$ differenzierbare Funktion und $x_0$ ein Punkt aus $I$ . Die Newton-Raphson-Iterierten ausgehend von $x_0$ sind die Zahlen, die eine nach der anderen definiert werden durch

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

solange $x_n$ in $I$ liegt und $f'(x_n) \neq 0$ . Sind diese Bedingungen für jede ganze Zahl $n \geq 0$ erfüllt, so bilden die Iterierten eine Funktion $n \mapsto x_n$ , definiert auf der Menge der nichtnegativen ganzen Zahlen, die nicht nach oben beschränkt ist, und die Definition des Grenzwerts, wenn die Variable gegen unendlich strebt, aus der Lektion über Grenzwerte, wenn die Variable gegen unendlich strebt, ist auf sie anwendbar. Man sagt, die Iterierten konvergieren gegen $r$ , wenn $\lim_{n \to \infty} x_n = r$ , das heißt, wenn

(\forall \varepsilon > 0)(\exists M)(\forall n \geq 0)\left(n > M \rightarrow \abs{x_n - r} < \varepsilon\right)

Jede Iterierte ist der Schnittpunkt der Tangente in $(x_n, f(x_n))$ mit der Achse: Setzt man $y = 0$ und $x = x_{n+1}$ in die Gleichung $y = f(x_n) + f'(x_n)(x - x_n)$ ein und löst auf, so erhält man die Formel der Definition. Das Verfahren verlangt nicht, dass die Funktion auf einem gegebenen Intervall ihr Vorzeichen wechselt, wie das Bisektionsverfahren, sondern dass sie differenzierbar ist und dass ihre Ableitung in den durchlaufenen Punkten nicht verschwindet; dafür sichert nichts im Voraus, dass sich die Iterierten einer Nullstelle nähern. Im Folgenden werden Bedingungen angegeben, die das sichern.

BeispielDie Quadratwurzel aus 2

Das Newton-Raphson-Verfahren auf $f(x) = x^2 - 2$ mit dem Startwert $x_0 = 2$ anwenden. Die folgende Rechnung zeigt nacheinander die ersten drei Tangenten und ihre Schnittpunkte mit der Achse.

Beweis

$x_{n+1} = x_n - \frac{x_n^2 - 2}{2x_n} = \frac{1}{2}\left(x_n + \frac{2}{x_n}\right), \qquad \resaltar{x_1 = \frac{3}{2}}$
Die Ableitung ist $f'(x) = 2x$ , die nicht verschwindet, wenn $x > 0$ . Die Iteration nimmt folgende Gestalt an: Jede Näherung ist das arithmetische Mittel aus der vorigen und aus $2$ dividiert durch sie. Ausgehend von $x_0 = 2$ schneidet die Tangente $y = 2 + 4(x - 2)$ die Achse in $\frac{3}{2}$ .
$x_2 = \frac{1}{2}\left(\frac{3}{2} + \frac{4}{3}\right) = \resaltar{\frac{17}{12}} \approx 1{,}416667$
Die Tangente in $\left(\frac{3}{2}, \frac{1}{4}\right)$ schneidet die Achse viel näher an der Nullstelle.
$x_3 = \frac{1}{2}\left(\frac{17}{12} + \frac{24}{17}\right) = \resaltar{\frac{577}{408}} \approx 1{,}4142157, \qquad \sqrt{2} \approx 1{,}4142136$
Die dritte Iterierte hat schon fünf richtige Nachkommastellen. Die Fehler, $x_n - \sqrt{2}$ , betragen etwa $0{,}59$ , $0{,}086$ , $0{,}0025$ und $0{,}0000021$ : Jeder liegt in der Größenordnung des Quadrats des vorigen.

Der Fehler dieses Beispiels wird exakt quadriert. Aus der Formel der Iteration erhält man für jedes $x_n > 0$ folgende Identität:

x_{n+1} - \sqrt{2} = \frac{x_n^2 - 2\sqrt{2}\,x_n + 2}{2x_n} = \frac{\left(x_n - \sqrt{2}\right)^2}{2x_n}

Folglich sind alle Iterierten ab der ersten größer oder gleich $\sqrt{2}$ , und wenn $x_n \geq 1$ , ist der neue Fehler höchstens die Hälfte des Quadrats des aktuellen Fehlers: Die vierte Iterierte, $x_4 = \frac{665\,857}{470\,832}$ , hat elf richtige Nachkommastellen. Wird $2$ durch eine beliebige positive Zahl ersetzt, so berechnet dasselbe Verfahren Quadratwurzeln; es findet sich schon in der Metrika Herons von Alexandria, im 1. Jahrhundert, und deshalb heißt es auch Heron-Verfahren.

Isaac Newton beschrieb sein Verfahren für Polynomgleichungen 1669 in einer Schrift, die handschriftlich zirkulierte und 1711 veröffentlicht wurde; Joseph Raphson veröffentlichte 1690 eine einfachere Darstellung, und Thomas Simpson stellte es 1740 als iteratives Verfahren für allgemeine Gleichungen vor.