Newtonverfahren

Das Newtonsche Näherungsverfahren, auch Newton-Raphsonsche Methode, (benannt nach Sir Isaac Newton 1669 und Joseph Raphson 1690) ist in der Mathematik das Standardverfahren zur numerischen Lösung von nichtlinearen Gleichungen und Gleichungssystemen. Im Falle einer Gleichung mit einer Variablen lassen sich zu einer gegebenen stetig differenzierbaren Funktion $f: \mathbb{R} \to \mathbb{R}$ Näherungswerte zu Lösungen der Gleichung f(x) = 0, d. h. Näherungen der Nullstellen dieser Funktion finden. Die grundlegende Idee dieses Verfahrens ist, die Funktion in einem Ausgangspunkt zu linearisieren, d. h. ihre Tangente zu bestimmen, und die Nullstelle der Tangente als verbesserte Näherung der Nullstelle der Funktion zu verwenden. Die erhaltene Näherung dient als Ausgangspunkt für einen weiteren Verbesserungsschritt. Diese Iteration erfolgt bis die Änderung in der Näherungslösung eine festgesetzte Schranke unterschritten hat. Das Iterations-Verfahren konvergiert im günstigsten Fall asymptotisch mit quadratischer Konvergenzordnung, die Zahl der korrekten Dezimalstellen verdoppelt sich dann in jedem Schritt.

Newton-Verfahren für reelle Funktionen einer Veränderlichen

Historisches über das Newtonverfahren

Isaac Newton verfasste im Zeitraum 1664 bis 1671 die Arbeit „Methodus fluxionum et serierum infinitarum“ (latein für: Von der Methode der Fluxionen und unendlichen Folgen). Darin erklärt er einen neuen Algorithmus zum Lösen einer polynomialen Gleichung am Beispiel y³ − 2y − 5 = 0. Dazu kann man leicht den Punkt y = 2 als erste Näherung raten. Newton machte den Ansatz y = 2 + p mit einem als „klein“ angenommenen p und setzte diesen in die Gleichung ein:

Nach den binomischen Formeln gilt

$y^3 = (2+p)^3 = 8+12p+6p^2+p^3\$

$\ 2y = 2(2+p) = 4+2p$

$\Rightarrow\ 0 = y^3-2y-5 = -1+10p+6p^2+p^3$.

Da p „klein“ sein soll, können die Terme höherer Ordnung gegen den linearen und konstanten vernachlässigt werden, womit 10p − 1 = 0 bzw. p = 0,1 übrig bleibt. Wir können nun dieses Vorgehen wiederholen und p = 0,1 + q ansetzen, in die zweite Gleichung einsetzen, höhere Terme weglassen und $q = -0{,}061/11{,}23 = -0{,}0054\dots$ erhalten.

Joseph Raphson beschrieb 1690 in der Arbeit „Analysis Aequationum universalis“ diesen Rechenprozess formal und illustrierte den Formalismus an der allgemeinen Gleichung 3. Grades, wobei er die nachfolgende Iterationsvorschrift fand.^[1]

Die abstrakte Form des Verfahrens mit Benutzung der Ableitung $x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}$ stammt von Thomas Simpson.

Konstruktion am Graphen

Anschaulich gelangt man wie folgt zu diesem Verfahren: Sei $f: \mathbb{R} \to \mathbb{R}$ eine stetig differenzierbare reelle Funktion, von der wir eine Stelle x_n im Definitionsbereich mit „kleinem“ Funktionswert kennen. Wir wollen einen Punkt x_{n + 1} nahe x_n finden, der eine verbesserte Näherung der Nullstelle darstellt. Dazu linearisieren wir die Funktion f an der Stelle x_n, d. h. wir ersetzen sie durch ihre Tangente im Punkt $P(x_n\,;\,f(x_n))$ mit Anstieg $f^\prime(x_n)$.

Die Tangente ist durch die Funktion $t(x_n+h):=f(x_n)+f^\prime(x_n)h$ gegeben. Setzen wir h = x − x_n ein, so erhalten wir

$t(x):=f(x_n)+f^\prime(x_n) (x-x_n)$.

Wir wählen als x_{n + 1} die einzige Nullstelle dieser linearen Funktion,

$0=t(x_{n+1})=f(x_n)+f^\prime(x_n) (x_{n+1}-x_n) \quad\Rightarrow\quad x_{n+1}=x_n-f(x_n)/f'(x_n)$.

Wenden wir diese Konstruktion mehrfach an, so erhalten wir aus einer ersten Stelle x₀ eine unendliche Folge von Stellen $(x_n)_{n\in\mathbb N}$, die durch die Rekursionsvorschrift

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

definiert ist. Diese Vorschrift wird auch als Newton-Iteration bezeichnet, die Funktion N_f als Newton-Operator. Die Newton-Iteration ist ein spezieller Fall einer Fixpunktiteration, falls die Folge gegen $\xi=\lim_{n\to\infty} x_n\,$ konvergiert, so gilt ξ = N_f(ξ) = ξ − f(ξ) / f'(ξ) und daher f(ξ) = 0.

Die Kunst der Anwendung des Newton-Verfahrens besteht darin, geeignete Startwerte x₀ zu finden. Je mehr über die Funktion f bekannt ist, desto kleiner lässt sich die notwendige Menge von Startwerten gestalten.

Viele nichtlineare Gleichungen haben mehrere Lösungen, so hat ein Polynom n-ten Grades bis zu n Nullstellen. Will man alle Nullstellen in einem bestimmten Bereich $D \subseteq \R$ ermitteln, so muss zu jeder Nullstelle ein passender Startwert in D gefunden werden, für den die Newton-Iteration konvergiert. Dazu könnte man z. B. per Bisektion genügend kleine isolierende Intervalle zu jeder Nullstelle bestimmen.

Erstes Beispiel

Die Quadratwurzel einer Zahl a > 0 sind die Nullstellen der Funktion f(x) = 1 − a / x². Diese Funktion hat die Ableitung $f^\prime(x)=2a/x^3$, die Newton-Iteration erfolgt also nach der Vorschrift

$x_{n+1}:=N_f(x_n)=x_n-\frac{1-a/x_n^2}{2a/x_n^3}=x_n-\frac{x_n^3}{2a}+\frac{x_n}{2}$$=\frac{x_n}{2}\left(3-\frac{x_n^2}{a}\right)$

Der Vorteil dieser Vorschrift gegenüber dem Wurzelziehen nach Heron (siehe unten) ist, dass es divisionsfrei ist, sobald einmal der Kehrwert von a bestimmt wurde. Als Startwert wurde in der Tabelle x₀: = (1 + a) / 2 gewählt. Die Iterierten wurden an der ersten ungenauen Stelle abgeschnitten. Es ist zu erkennen, dass nach wenigen Schritten die Anzahl gültiger Stellen schnell wächst.

n	xn bei a = 2	xn bei a = 3	xn bei a = 5
0	1,5	2	3
1	1,40	1,6	1,8
2	1,4141	1,72	2,1
3	1,41421355	1,73203	2,22
4	1,41421356237309502	1,7320508074	2,23601
5	1,414213562373095048801688724209697	1,73205080756887729351	2,236067975
6	1,414213562373095048801688724209698	1,7320508075688772935274463415058723669426	2,236067977499789692
7	1,414213562373095048801688724209698	1,7320508075688772935274463415058723669428	2,23606797749978969640917366873127622
8	1,414213562373095048801688724209698	1,7320508075688772935274463415058723669428	2,23606797749978969640917366873127623

Betrachten wir die Differenz $x_{n+1}-\sqrt a$ zum Grenzwert im (n + 1)-ten Schritt, so kann mittels der binomischen Formeln die Differenz im n-ten Schritt zweimal abgespalten werden:

$x_{n+1}-\sqrt a =\frac{3}{2}x_n-\frac{x_n^3}{2a}-\frac{3}{2}\sqrt a+\frac{\sqrt{a}^3}{2a} =(x_n-\sqrt a)\cdot\left(\frac32-\frac{x_n^2+x_n\sqrt a+a}{2a}\right)$

$=(x_n-\sqrt a)\cdot\frac{a-x_n^2+a-x_n\sqrt a}{2a}=-(x_n-\sqrt a)^2\cdot(x_n+2\sqrt a)$

Nach der Ungleichung vom arithmetischen und geometrischen Mittel gilt $0<\sqrt a\le \frac{1+a}2$, so dass der zweite Faktor sinnvoll durch 3 / 2(1 + a) beschränkt werden kann. Ist die Differenz im n-ten Schritt eine kleine Zahl, so ist die Differenz im (n + 1)-ten Schritt proportional zum Quadrat davon, also wesentlich kleiner. So entsteht durch Quadrieren eines Fehlers 10 ^{− m} eine Fehlerabschätzung proportional zu 10 ^{− 2m}. Deshalb spricht man davon, dass sich die Anzahl der gültigen Stellen in jedem Schritt der Newton-Iteration in etwa verdoppelt.

Konvergenzbetrachtungen

Das Newton-Verfahren für das Polynom z³ − 1 über den komplexen Zahlen konvergiert für Startwerte aus den roten, den grünen und den blauen Bereichen jeweils zu einer der drei Nullstellen des Polynoms. Für Startwerte aus der hellen Struktur – dem Newton-Fraktal – konvergiert das Verfahren nicht.

Das Newton-Verfahren ist ein so genanntes lokal konvergentes Verfahren. Konvergenz der in der Newton-Iteration erzeugten Folge zu einer Nullstelle ist also nur garantiert, wenn der Startwert, d. h. das 0-te Glied der Folge, schon „ausreichend nahe“ an der Nullstelle liegt. Ist der Startwert zu weit weg, kann alles passieren:

• Die Folge divergiert, der Abstand zur Nullstelle wächst über alle Grenzen.
• Die Folge divergiert, bleibt aber beschränkt. Sie kann z. B. periodisch werden, d. h. endlich viele Punkte wechseln sich in immer derselben Reihenfolge ab. Man sagt auch, dass die Folge oszilliert.
• Die Folge konvergiert trotz der Distanz zur Nullstelle, kann jedoch, falls die Funktion mehrere Nullstellen hat, gegen eine andere als die gewünschte Nullstelle (falls man weiß, welche man will) konvergieren.

Dynamik des Newton-Verfahrens für die Funktion x³ − 2x + 2 mit Startwerten zwischen −4 und 4: Jede farbcodierte Zeile zeigt das Resultat eines Schritts des Verfahrens, angewandt auf die jeweils darüberliegende Zeile. Die Startwerte befinden sich in der obersten Zeile. Viele Startwerte konvergieren gegen die (einzige reellwertige) Nullstelle des Polynoms bei ca. -1.769, deren Farbe mittelblau ist. Es gibt jedoch auch viele Startwerte, für welche das Verfahren nicht konvergiert und zwischen Null (schwarz) und Eins (rot) hin- und herpendelt. Diese nicht zur Nullstelle führenden Startwerte bilden eine Menge von vollem Maß, bilden also keine Nullmenge, denn sie enthält komplette Intervalle.

Ist der Startwert $x_0\,$ so gewählt, dass das Newton-Verfahren konvergiert, so ist die Konvergenz allerdings quadratisch, also mit der Konvergenzordnung 2 (falls die Ableitung an der Nullstelle nicht verschwindet). Die Menge der Startpunkte, für die das Newton-Verfahren gegen eine bestimmte Nullstelle konvergiert, bildet den Einzugsbereich dieser Nullstelle. Färbt man für eine Polynomfunktion, mit reellen oder komplexen Koeffizienten, die Einzugsbereiche verschiedener Nullstellen in der komplexen Ebene verschieden ein, so ergibt sich ein Newton-Fraktal. In diesem ist zu erkennen, dass die Einzugsbereiche Bassins, d. h. Kreisscheiben um die Nullstellen enthalten, aus welchen heraus die Newton-Iteration stabil gegen die Nullstelle im Zentrum konvergiert. Aber es ist auch zu erkennen, dass die Ränder der Einzugsbereiche „ausgefranst“ sind, sie haben sogar eine fraktale Struktur. Geringe Abweichungen im Startpunkt können also zu verschiedenen Nullstellen führen. Falls es jedoch im Intervall $I=]a;b[\,$ genau eine Nullstelle gibt, in $I\,$ durchweg $f^\prime>0$ sowie $f^{\prime\prime}<0$ gilt und der Startwert $x_0\in I=]a;b[$ links von der Nullstelle $\xi\in I\,$ gewählt wird, dann konvergiert die Folge im Newton-Verfahren stets, und zwar streng monoton wachsend (siehe Abbildung unten bzw. die Tabelle oben ab n = 1).

Beispiele für Nicht-Konvergenz

1. Oszillierendes Verhalten ergibt sich u.a. für das Polynom f(x): = x³ − 2x + 2 ^[2] mit $f^\prime(x)=3x^2-2$. Der Punkt x = 0 mit f(0) = 2 und $f^\prime(0)=-2$ wird durch den Newton-Operator auf den Punkt N(0) = 0 − 2 / ( − 2) = 1 abgebildet, der Punkt x = 1 wiederum, mit f(1) = 1 und $f^\prime(1)=1$, wird auf N(1) = 1 − 1 / 1 = 0 abgebildet, so dass die Newton-Iteration mit einem dieser Punkte als Startwert eine periodische Folge ergibt, diese beiden Punkte wechseln sich zyklisch ab. Des Weiteren ist dieser Zyklus stabil, er bildet einen Attraktor der Newton-Iteration. Das bedeutet, um beide Punkte gibt es Umgebungen, so dass Startpunkte aus diesen Umgebungen gegen den Zyklus konvergieren und somit je einen der Punkte 0 und 1 als Grenzwert der Teilfolge mit geradem Index und der mit ungeradem Index haben.
2. Divergenz bzw. beliebig weites Entfernen vom Startpunkt ergibt sich für f(x) = sin(x) mit $f^\prime(x)=\cos(x)$ und N(x) = x − tan(x). Es gibt eine Stelle $x_0 \isin \lbrack -\pi /2,0 \rbrack$ mit tan(x₀) = − 2π. Man überzeugt sich, dass dann x_n = x₀ + 2πn gilt. Dieses Verhalten ist nicht stabil, denn bei leichter Variation des Anfangswertes, wie sie zum Beispiel durch die numerische Berechnung entsteht, entfernt sich die Newton-Iteration immer weiter von der idealen divergierenden Folge. Selbst bei schließlicher Konvergenz wird die gefundene Nullstelle sehr weit vom Startwert entfernt sein.

Lokale quadratische Konvergenz

Sei f eine zweimal stetig differenzierbare reelle Funktion und a eine Nullstelle von f, in welcher die Ableitung keine Nullstelle hat. Das bedeutet, dass der Graph der Funktion transversal, d. h. nicht-berührend, die x-Achse schneidet. Sei x ein Punkt nahe bei a. Dann kann die Taylor-Formel zweiten Grades (mit Restglied)

$0=f(a)=f(x)+f'(x)(a-x)+\tfrac12 f''(\xi)(a-x)^2,\qquad \xi$ liegt zwischen x und a,

nach der Differenz (x-a) umgestellt werden,

$x-a=\frac{f(x)}{f'(x)}+\frac{f''(\xi)}{2\,f'(x)}(x-a)^2$.

Es wird nun so umgestellt, dass der Newton-Operator auf der rechten Seite erscheint,

$N_f(x)-a=x-\frac{f(x)}{f'(x)}-a=\frac{f''(\xi)}{2\,f'(x)}(x-a)^2$.

Seien I ein Intervall um a ohne Nullstelle der Ableitung f'(x) und $m_1=\min_{x\in I}|f'(x)|$ sowie $M_2=\max_{x\in I}|f''(x)|$ Schranken der Ableitungen von f. Dann folgt für alle $x\in I$ die Abschätzung

$\Bigl|N_f(x)-a\Bigr|\le\frac{M_2}{2m_1}|x-a|^2$.

Mit $K=\tfrac{M_2}{2m_1}$ sei der konstante Faktor bezeichnet. In jedem Schritt n der Newtoniteration wird die Größe $d_n=K\,|x_n-a|$ kleiner sein als das Quadrat derselben Größe im vorhergehenden Schritt, $d_n\le K\cdot K|x_{n-1}-a|^2=d_{n-1}^2$. Nach vollständiger Induktion ergibt sich

$K\,|x_n-a|=d_n\le d_{n-1}^2\le d_{n-2}^4\le\ldots\le d_0^{2^n}=(K\,|x_0-a|)^{2^n}$.

Kann also für den Startpunkt der Iteration die Abschätzung $|x_0-a |<\tfrac1K$ garantiert werden, z. B. indem die Intervallänge von I kleiner als 1/K ist, so konvergiert die Folge (x_n) der Newton-Iteration gegen die Nullstelle a, denn die Folge $(d_n)_{n\in\N}$ und damit $(x_n=\tfrac1K d_n)_{n\in\N}$ ist nach der angegebenen Abschätzung eine Nullfolge. Die Verkürzung des Intervalls kann durch einige Iterationen eines langsameren Verfahrens zur Nullstelleneinschränkung erreicht werden, z. B. des Bisektionsverfahrens oder der Regula falsi.

Die aus dieser Abschätzungen folgende Konvergenzgeschwindigkeit wird als quadratisch bezeichnet, die (logarithmische) Genauigkeit bzw. Anzahl gültiger Stellen verdoppelt sich in jedem Schritt. Die Abschätzung des Abstands | x_n − a | zur Nullstelle wird oft linear in | x₀ − a | angegeben, so gilt z. B.

• $|x_n-a|\le \left(\tfrac12\right)^{2^n-1}\cdot |x_0-a|$, falls die Länge des Intervalls I kleiner als $\tfrac{1}{2K}$ ist. Dies ergibt eine Abschätzung der gültigen Stellen im Binärsystem.
• $|x_n-a|\le \left(\tfrac1{10}\right)^{2^n-1}\cdot |x_0-a|$, falls die Länge des Intervalls I kleiner als $\tfrac{1}{10K}$ ist, d. h. nahe genug an der Nullstelle ergibt sich eine Verdopplung der gültigen Dezimalstellen in jedem Schritt.

Bemerkungen

• Der lokale Konvergenzbeweis kann auch auf gleiche Weise im mehrdimensionalen Fall geführt werden, allerdings ist er dann technisch etwas schwieriger, da mit zwei- und dreistufigen Tensoren für die erste bzw. zweite Ableitung gearbeitet wird. Im wesentlichen ist die Konstante K durch $K=\tfrac12\,\sup_{x\in U}\|f'(x)^{-1}\|_{(1,1)}\,\sup_{x\in U}\|f''(x)\|_{(1,2)}$ zu ersetzen, mit geeigneten induzierten Operatornormen.
• Der lokale Konvergenzbeweis setzt voraus, dass ein eine Nullstelle enthaltendes Intervall bekannt ist. Aus seinem Beweis ergibt sich aber keine Möglichkeit, dies schnell zu testen. Ein Konvergenzbeweis, der auch hierfür ein Kriterium liefert, wurde zuerst von Leonid Kantorowitsch geführt und ist als Satz von Kantorowitsch bekannt.
• Um einen geeigneten Startpunkt zu finden, verwendet man gelegentlich andere („gröbere“) Verfahren. Beispielsweise kann man mit dem Gradientenverfahren eine ungefähre Lösung ermitteln und diese dann mit dem Newton-Verfahren verfeinern.
• Bei unbekanntem Startpunkt kann man mittels einer Homotopie die Funktion f, von der man eine Nullstelle sucht, zu einer einfacheren Funktion g deformieren, von der (mindestens) eine Nullstelle bekannt ist. Man durchläuft dann die Deformation rückwärts in Form einer endlichen Folge sich nur „wenig“ unterscheidender Funktionen. Von der ersten Funktion g kennt man eine Nullstelle. Als Startwert der Newton-Iteration zur gerade aktuellen Funktion der Folge verwendet man die Näherung einer Nullstelle der in der Folge vorhergehenden Funktion. Zum genauen Vorgehen siehe Homotopieverfahren.

Als Beispiel mag die „Flutungshomotopie“ dienen: mit einem willkürlichen z bilden wir die Ausgangsfunktion g(x) = f₀(x): = f(x) − f(z) mit bekannter Nullstelle z . Wir haben den „Wasserspiegel“ vom „Nullpegel“ auf die Höhe f(z) geflutet. Nun senken wir schrittweise den Wasserstand, $f_n(x):= f(x)-(f(z)-n\cdot h\cdot f(z))$, h = 1 / N, $n=1\dots N$. In jedem Schritt wird eine Näherung ξ⁽ⁿ⁾ einer Nullstelle bestimmt, wobei x₀: = ξ^{(n − 1)} gesetzt wird. Es ist f_N = f und somit ξ^(N) eine der gesuchten Näherungslösungen.

Abbruchkriterien

Mögliche Abbruchkriterien bezüglich einer Restgröße (zum Beispiel Rechner-Arithmetik) sind:

$\| f(x_n)\|< \varepsilon_1\qquad\mathrm{oder}\qquad \| x_{n+1}-x_n\|<\varepsilon_2$

Wobei $\varepsilon_1,\varepsilon_2\in\mathbb{R}^+$ die Qualität der „Nullstelle“ bestimmt. In beiden Fällen kann es vorkommen, dass das Abbruchkriterium zu einem „schlechten“ Zeitpunkt erfüllt ist.

Weitere Anwendungsbeispiele

Berechnung der Quadratwurzel

Ein Spezialfall des Newtonschen Näherungsverfahrens ist das Babylonische Wurzelziehen, auch bekannt als Heronverfahren nach Heron von Alexandria:

Wendet man die Iterationsformel zur Nullstellenbestimmung auf die Funktion

f(x) = x² − a

an, so erhält man wegen der Ableitungsfunktion f'(x) = 2x für die Lösung $\sqrt{a}$ das Näherungsverfahren

$x_{n+1}:=x_n-\frac{x_n^2 - a}{2x_n}=\frac12 \left(x_n + \frac{a}{x_n}\right)$.

Dieses Verfahren konvergiert für jedes $a\geq0$ und für jeden beliebigen Anfangswert $x_0 \neq 0$.

Schnittpunkt zweier Funktionen

Auf ähnliche Weise lässt sich auch der x -Wert des Schnittpunktes zweier Funktionen g(x) und f(x) bestimmen:

Da man die beiden Funktionen zur Lösung des Problems gleichsetzt, lässt sich immer durch Umformung folgende Form, auf die das Newtonsche Näherungsverfahren angewendet werden kann, bestimmen:

f(x) − g(x) = 0

Trigonometrische Funktion

Gesucht sei die positive Lösung eines Problems x wobei cos(x) = x³. Das Problem kann umformuliert werden als cos(x) − x³ = 0. Gesucht werden also Nullstellen von f(x) = cos(x) − x³.

Wir haben nun f'(x) = − sin(x) − 3x². Da $\cos(x) \leq 1$ für alle x gilt und x³ > 1 für x > 1, wissen wir, dass die Nullstelle zwischen 0 und 1 liegt. Wir starten die Iteration mit dem Wert x₀ = 0,5 .

$\begin{matrix} x_1 & = & x_0 - \frac{f(x_0)}{f'(x_0)} & = & 0{,}5 - \frac{\cos(0{,}5) - 0{,}5^3}{-\sin(0{,}5) - 3 \cdot 0{,}5^2} & = & 1{,}1121416371 \\ x_2 & = & x_1 - \frac{f(x_1)}{f'(x_1)} & & \vdots & = & 0{,}909672693736 \\ x_3 & & \vdots & & \vdots & = & 0{,}867263818209 \\ x_4 & & \vdots & & \vdots & = & 0{,}865477135298 \\ x_5 & & \vdots & & \vdots & = & 0{,}865474033111 \\ x_6 & & \vdots & & \vdots & = & 0{,}865474033101 \\ x_7 & & \vdots & & \vdots & = & 0{,}865474033102 \end{matrix}$

Damit haben wir die ersten zwölf Ziffern der Nullstelle.

Das folgende Programm in JavaScript bestimmt diese Nullstelle. Um es auszuführen, kopieren Sie den Programmtext inklusive der Marken in eine neue Textdatei und speichern Sie sie mit dem Dateityp .html ab. Öffnen Sie dann die Datei mit einem Webbrowser.