Newtonverfahren

Das Newtonverfahren, a​uch Newton-Raphson-Verfahren (benannt n​ach Sir Isaac Newton 1669 u​nd Joseph Raphson 1690), i​st in d​er Mathematik e​in häufig verwendeter Approximationsalgorithmus z​ur numerischen Lösung v​on nichtlinearen Gleichungen u​nd Gleichungssystemen. Im Falle e​iner Gleichung m​it einer Variablen lassen s​ich zu e​iner gegebenen stetig differenzierbaren Funktion Näherungen d​er Nullstellen dieser Funktion finden. Die grundlegende Idee dieses Verfahrens ist, d​ie Funktion i​n einem Ausgangspunkt z​u linearisieren, d. h. i​hre Tangente z​u bestimmen, u​nd die Nullstelle d​er Tangente a​ls verbesserte Näherung d​er Nullstelle d​er Funktion z​u verwenden. Die erhaltene Näherung d​ient als Ausgangspunkt für e​inen weiteren Verbesserungsschritt. Diese Iteration erfolgt, b​is die Änderung i​n der Näherungslösung e​ine festgesetzte Schranke unterschritten hat. Das Iterationsverfahren konvergiert i​m günstigsten Fall asymptotisch m​it quadratischer Konvergenzordnung, d​ie Zahl d​er korrekten Dezimalstellen verdoppelt s​ich dann i​n jedem Schritt.

Formal ausgedrückt, wird ausgehend von einem Startwert ${\displaystyle x_{0}}$ die Iteration

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

wiederholt, b​is eine hinreichende Genauigkeit erzielt wird.

Newtonverfahren 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 ${\displaystyle y^{3}-2y-5=0}$. Dazu kann man leicht den Punkt ${\displaystyle y=2}$ als erste Näherung raten. Newton machte den Ansatz ${\displaystyle y=2+p}$ mit einem als „klein“ angenommenen ${\displaystyle p}$ und setzte diesen in die Gleichung ein:

Nach d​en binomischen Formeln gilt

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

${\displaystyle \ 2y=2(2+p)=4+2p}$

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

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

Joseph Raphson beschrieb 1690 i​n der Arbeit „Analysis Aequationum universalis“ diesen Rechenprozess formal u​nd illustrierte d​en Formalismus a​n der allgemeinen Gleichung dritten Grades, w​obei er d​ie nachfolgende Iterationsvorschrift fand.[1]

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

Konstruktion am Graphen

Animation: Iteration mit dem newtonschen Verfahren

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

Die Tangente ist durch die Funktion ${\displaystyle t(x_{n}+h):=f(x_{n})+f^{\prime }(x_{n})h}$ gegeben. Setzen wir ${\displaystyle h=x-x_{n}}$ ein, so erhalten wir

${\displaystyle t(x):=f(x_{n})+f^{\prime }(x_{n})(x-x_{n})}$.

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

${\displaystyle 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 ${\displaystyle x_{0}}$ eine unendliche Folge von Stellen ${\displaystyle (x_{n})_{n\in \mathbb {N} }}$, die durch die Rekursionsvorschrift

${\displaystyle 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 ${\displaystyle N_{f}}$ als Newtonoperator. Die Newtoniteration ist ein spezieller Fall einer Fixpunktiteration, falls die Folge gegen ${\displaystyle \xi =\lim _{n\to \infty }x_{n}\,}$ konvergiert, so gilt ${\displaystyle \xi =N_{f}(\xi )=\xi -f(\xi )/f'(\xi )}$ und daher ${\displaystyle f(\xi )=0}$.

Die Kunst der Anwendung des Newtonverfahrens besteht darin, geeignete Startwerte ${\displaystyle x_{0}}$ zu finden. Je mehr über die Funktion ${\displaystyle 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 ${\displaystyle n}$-ten Grades bis zu ${\displaystyle n}$ Nullstellen. Will man alle Nullstellen in einem bestimmten Bereich ${\displaystyle D\subseteq \mathbb {R} }$ ermitteln, so muss zu jeder Nullstelle ein passender Startwert in ${\displaystyle D}$ gefunden werden, für den die Newtoniteration konvergiert. Dazu könnte man z. B. per Bisektion genügend kleine isolierende Intervalle zu jeder Nullstelle bestimmen.

Erstes Beispiel

Die Quadratwurzel einer Zahl ${\displaystyle a>0}$ ist die positive Nullstelle der Funktion ${\displaystyle f(x)=1-a/x^{2}}$. Diese Funktion hat die Ableitung ${\displaystyle f^{\prime }(x)=2a/x^{3}}$, die Newtoniteration erfolgt also nach der Vorschrift

${\displaystyle 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 ${\displaystyle a}$ bestimmt wurde. Als Startwert wurde in der Tabelle ${\displaystyle x_{0}:=(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	${\displaystyle x_{n}}$ bei ${\displaystyle a=2}$	${\displaystyle x_{n}}$ bei ${\displaystyle a=3}$	${\displaystyle x_{n}}$ bei ${\displaystyle a=5}$
0	${\displaystyle 1{,}5}$	${\displaystyle 2}$	${\displaystyle 3}$
1	${\displaystyle 1{,}40}$	${\displaystyle 1{,}6}$	${\displaystyle 1{,}8}$
2	${\displaystyle 1{,}414}$	${\displaystyle 1{,}72}$	${\displaystyle 2{,}1}$
3	${\displaystyle 1{,}414213514}$	${\displaystyle 1{,}73203}$	${\displaystyle 2{,}22}$
4	${\displaystyle 1{,}41421356237309502}$	${\displaystyle 1{,}7320508074}$	${\displaystyle 2{,}23601}$
5	${\displaystyle 1{,}414213562373095048801688724209697}$	${\displaystyle 1{,}73205080756887729351}$	${\displaystyle 2{,}236067975}$
6	${\displaystyle 1{,}414213562373095048801688724209698}$	${\displaystyle 1{,}7320508075688772935274463415058723669426}$	${\displaystyle 2{,}236067977499789692}$
7	${\displaystyle 1{,}414213562373095048801688724209698}$	${\displaystyle 1{,}7320508075688772935274463415058723669428}$	${\displaystyle 2{,}23606797749978969640917366873127622}$
8	${\displaystyle 1{,}414213562373095048801688724209698}$	${\displaystyle 1{,}7320508075688772935274463415058723669428}$	${\displaystyle 2{,}23606797749978969640917366873127623}$

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

${\displaystyle 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({\frac {3}{2}}-{\frac {x_{n}^{2}+x_{n}{\sqrt {a}}+a}{2a}}\right)}$

${\displaystyle =(x_{n}-{\sqrt {a}})\cdot {\frac {a-x_{n}^{2}+a-x_{n}{\sqrt {a}}}{2a}}=-(x_{n}-{\sqrt {a}})^{2}\cdot {\frac {x_{n}+2{\sqrt {a}}}{2a}}}$

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

Konvergenzbetrachtungen

Das Newtonverfahren für das Polynom ${\displaystyle z^{3}-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 Newtonfraktal, konvergiert das Verfahren nicht.

Das Newtonverfahren i​st ein sogenanntes l​okal konvergentes Verfahren. Konvergenz d​er in d​er Newtoniteration erzeugten Folge z​u einer Nullstelle i​st also n​ur garantiert, w​enn der Startwert, d. h. d​as 0-te Glied d​er Folge, s​chon „ausreichend nahe“ a​n der Nullstelle liegt. Ist d​er Startwert z​u weit entfernt, i​st das Konvergenzverhalten n​icht festgelegt, d​as heißt, e​s ist sowohl e​ine Divergenz d​er Folge möglich a​ls auch e​ine Oszillation (bei d​er sich endlich v​iele Funktionswerte abwechseln) o​der eine Konvergenz g​egen eine andere Nullstelle d​er betrachteten Funktion.

Dynamik des Newtonverfahrens für die Funktion ${\displaystyle x^{3}-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. Die Menge dieser nicht zur Nullstelle führenden Startwerte enthält offene Intervalle, ist also eine Menge von positivem Maß und damit insbesondere keine Nullmenge.

Ist der Startwert ${\displaystyle x_{0}}$ so gewählt, dass das Newtonverfahren 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 Newtonverfahren 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 unterschiedlich ein, so ergibt sich ein Newtonfraktal. In diesem ist zu erkennen, dass die Einzugsbereiche Bassins, d. h. Kreisscheiben um die Nullstellen enthalten, aus welchen heraus die Newtoniteration 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 unterschiedlichen Nullstellen führen.

Falls es jedoch im Intervall ${\displaystyle I={]a,b[}}$ genau eine Nullstelle gibt, in ${\displaystyle I}$ durchweg ${\displaystyle f'>0}$ sowie ${\displaystyle f''<0}$ gilt und der Startwert ${\displaystyle x_{0}\in I}$ links von der Nullstelle ${\displaystyle \xi \in I}$ gewählt wird, dann konvergiert die Folge im Newtonverfahren stets, und zwar streng monoton wachsend (siehe Abbildung unten bzw. die Tabelle oben ab ${\displaystyle n=1}$).

Beispiele für Nicht-Konvergenz

1. Oszillierendes Verhalten ergibt sich u. a. für das Polynom ${\displaystyle f(x):=x^{3}-2x+2}$[2] mit ${\displaystyle f^{\prime }(x)=3x^{2}-2}$. Der Punkt ${\displaystyle x=0}$ mit ${\displaystyle f(0)=2}$ und ${\displaystyle f^{\prime }(0)=-2}$ wird durch den Newtonoperator auf den Punkt ${\displaystyle N(0)=0-2/(-2)=1}$ abgebildet, der Punkt ${\displaystyle x=1}$ wiederum, mit ${\displaystyle f(1)=1}$ und ${\displaystyle f^{\prime }(1)=1}$, wird auf ${\displaystyle N(1)=1-1/1=0}$ abgebildet, so dass die Newtoniteration mit einem dieser Punkte als Startwert eine periodische Folge ergibt, diese beiden Punkte wechseln sich zyklisch ab. Dieser Zyklus ist stabil, er bildet einen Attraktor der Newtoniteration. 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 ${\displaystyle f(x)=\sin(x)}$ mit ${\displaystyle f^{\prime }(x)=\cos(x)}$ und ${\displaystyle N(x)=x-\tan(x)}$. Es gibt eine Stelle ${\displaystyle x_{0}\in \lbrack -\pi /2,0\rbrack }$ mit ${\displaystyle \tan(x_{0})=-2\pi }$ d. h. ${\displaystyle x_{0}=\arctan(-2\pi )=-1{,}412965136506737759\dots }$ Man überzeugt sich, dass dann ${\displaystyle x_{n}=x_{0}+2\pi 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 Newtoniteration 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 ${\displaystyle f}$ eine zweimal stetig differenzierbare reelle Funktion und ${\displaystyle a}$ eine einfache Nullstelle von ${\displaystyle f}$, in welcher die Ableitung somit keine Nullstelle hat. Das bedeutet, dass der Graph der Funktion transversal, d. h. nicht-berührend, die ${\displaystyle x}$-Achse schneidet. Sei ${\displaystyle x}$ ein Punkt nahe bei ${\displaystyle a}$. Dann kann die Taylorformel zweiten Grades (mit Lagrange-Restglied)

${\displaystyle 0=f(a)=f(x)+f'(x)(a-x)+{\tfrac {1}{2}}f''(\xi )(a-x)^{2},\qquad \xi }$ liegt zwischen ${\displaystyle x}$ und ${\displaystyle a}$,

nach der Differenz ${\displaystyle (x-a)}$ umgestellt werden,

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

Es w​ird nun s​o umgestellt, d​ass der Newtonoperator a​uf der rechten Seite erscheint,

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

Seien ${\displaystyle I}$ ein Intervall um ${\displaystyle a}$ ohne Nullstelle der Ableitung ${\displaystyle f'(x)}$ und ${\displaystyle m_{1}=\min _{x\in I}|f'(x)|}$ sowie ${\displaystyle M_{2}=\max _{x\in I}|f''(x)|}$ Schranken der Ableitungen von ${\displaystyle f}$. Dann folgt für alle ${\displaystyle x\in I}$ die Abschätzung

${\displaystyle {\Bigl |}N_{f}(x)-a{\Bigr |}\leq {\frac {M_{2}}{2m_{1}}}|x-a|^{2}}$.

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

${\displaystyle K\,|x_{n}-a|=d_{n}\leq d_{n-1}^{2}\leq d_{n-2}^{4}\leq \dotsb \leq d_{0}^{2^{n}}=(K\,|x_{0}-a|)^{2^{n}}}$.

Kann also für den Startpunkt der Iteration die Abschätzung ${\displaystyle |x_{0}-a|<{\tfrac {1}{K}}}$ garantiert werden, z. B. indem die Intervalllänge von ${\displaystyle I}$ kleiner als ${\displaystyle 1/K}$ ist, so konvergiert die Folge ${\displaystyle (x_{n})}$ der Newtoniteration gegen die Nullstelle ${\displaystyle a}$, denn die Folge ${\displaystyle (d_{n})_{n\in \mathbb {N} }}$ und damit ${\displaystyle (x_{n}={\tfrac {1}{K}}d_{n})_{n\in \mathbb {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 ${\displaystyle |x_{n}-a|}$ zur Nullstelle wird oft linear in ${\displaystyle |x_{0}-a|}$ angegeben, so gilt z. B.

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

Lokale quadratische Konvergenz bei mehrfacher Nullstelle durch Modifikation

Für den Fall, dass ${\displaystyle f}$ bei ${\displaystyle a}$ eine mehrfache Nullstelle endlichen Grades besitzt, lässt sich ebenfalls die Konvergenzgeschwindigkeit abschätzen und durch eine geringfügige Modifikation wieder quadratische Konvergenz erzwingen.

Hat ${\displaystyle f}$ bei ${\displaystyle a}$ eine ${\displaystyle k}$-fache Nullstelle, lässt sich ${\displaystyle f}$ schreiben als ${\displaystyle f(x)=(x-a)^{k}\cdot g(x)}$ mit ${\displaystyle g(a)\neq 0}$ .

Dann ist nach der Produktregel ${\displaystyle f'(x)=k\cdot (x-a)^{k-1}\cdot g(x)+(x-a)^{k}\cdot g'(x)}$ und damit der Ausdruck

${\displaystyle {\frac {f(x)}{f'(x)}}={\frac {(x-a)^{k}\cdot g(x)}{k\cdot (x-a)^{k-1}\cdot g(x)+(x-a)^{k}\cdot g'(x)}}=(x-a){\frac {g(x)}{k\cdot g(x)+(x-a)\cdot g'(x)}}}$.

Setzt m​an dies n​un in d​ie Iteration ein, s​o erhält man

${\displaystyle x_{\text{neu}}=x-{\frac {f(x)}{f'(x)}}=x-(x-a){\frac {g(x)}{k\cdot g(x)+(x-a)\cdot g'(x)}}}$

und daraus nach beidseitiger Subtraktion von ${\displaystyle a}$ den Iterationsfehler

${\displaystyle (x_{\text{neu}}-a)=(x-a)-(x-a){\frac {g(x)}{k\cdot g(x)+(x-a)\cdot g'(x)}}=(x-a)\left[1-{\frac {g(x)}{k\cdot g(x)+(x-a)\cdot g'(x)}}\right]}$ . ${\displaystyle (*)}$

Wenn nun der Ausdruck ${\displaystyle (x-a)}$ sehr klein geworden ist, wird der Summand ${\displaystyle (x-a)\cdot g'(x)}$ im Nenner viel kleiner als ${\displaystyle k\cdot g(x)}$, so dass sich die hintere Klammer in ${\displaystyle (*)}$ immer mehr dem Wert ${\displaystyle s=1-{\tfrac {1}{k}}}$ nähert. Für die einfache Nullstelle mit ${\displaystyle k=1}$ hat man einen kleinen Wert ${\displaystyle s}$, der fast 0 wird, so dass ${\displaystyle (x_{\text{neu}}-a)=(x-a)\cdot s}$ wird. Für ${\displaystyle k=2}$ wird ${\displaystyle s}$ ungefähr 0,5, so dass sich der Abstand zur Nullstelle von Schritt zu Schritt nur etwa halbiert und man nach etwa 10 Schritten die Genauigkeit nur in weiteren drei Dezimalstellen erhöht hat. Bei ${\displaystyle k=3}$ wird ${\displaystyle s}$ etwa 0,67, so dass erst nach etwa 16 Schritten die Genauigkeit um weitere drei Dezimalstellen steigt usw.

Man k​ann daher a​m Konvergenzverhalten d​ie Vielfachheit d​er Nullstelle abschätzen, f​alls man s​ie nicht a​us anderen Gründen weiß, u​nd – w​ie nun n​och beschrieben – d​as Verfahren optimieren.

Bei einer ${\displaystyle k}$-fachen Nullstelle modifiziert man das newtonsche Näherungsverfahren mit einem Faktor ${\displaystyle k}$:

${\displaystyle x_{\text{neu}}=x-k\cdot {\frac {f(x)}{f'(x)}}}$ (Newtonverfahren bei ${\displaystyle k}$-facher Nullstelle)

Damit wird dann ${\displaystyle (*)}$ zu

${\displaystyle {\begin{aligned}(x_{\text{neu}}-a)&=(x-a)\left[1-{\frac {k\cdot g(x)}{k\cdot g(x)+(x-a)\cdot g'(x)}}\right]\\&=(x-a)\left[{\frac {k\cdot g(x)+(x-a)\cdot g'(x)}{k\cdot g(x)+(x-a)\cdot g'(x)}}-{\frac {k\cdot g(x)}{k\cdot g(x)+(x-a)\cdot g'(x)}}\right]\\&=(x-a){\frac {(x-a)\cdot g'(x)}{k\cdot g(x)+(x-a)\cdot g'(x)}}\\&=(x-a)^{2}{\frac {g'(x)}{k\cdot g(x)+(x-a)\cdot g'(x)}}\end{aligned}}}$

Ist nun ${\displaystyle (x-a)}$ wieder sehr klein, so wird im Nenner der Summand ${\displaystyle (x-a)\cdot g'(x)}$ viel kleiner als ${\displaystyle k\cdot g(x)}$ , und man erhält

${\displaystyle (x_{\text{neu}}-a)=(x-a)^{2}{\frac {g'(x)}{k\cdot g(x)}}}$,

wobei der rechte Faktor wegen ${\displaystyle g(a)\neq 0}$ gegen einen festen Wert konvergiert. Wie man sieht, liegt nun auch hier quadratische Konvergenz vor.

Ein Beispiel zeigt das Konvergenzverhalten sehr schön. Die Funktion ${\displaystyle f(x)=x^{2}-2}$ hat die einfache Nullstelle ${\displaystyle {\sqrt {2}}}$. Die linke Spalte der Tabelle zeigt die rasche Konvergenz für den Startwert 1, nach 4 Schritten lässt sich die Genauigkeit nicht mehr steigern, beim Fehler verdoppelt sich die Anzahl der Nullen hinterm Komma (mindestens). Quadriert man nun die Funktion (mittlere Spalte), wird die Nullstelle eine doppelte, und nun zeigt sich das oben erläuterte Verhalten, dass sich ohne Modifikation der Fehler in jedem Schritt nur etwa halbiert. Modifiziert man dann diesen Fall mit dem Faktor ${\displaystyle k=2}$, so stellt sich dasselbe Verhalten wie bei der einfachen Nullstelle ein (rechte Spalte).

n	${\displaystyle x_{n}}$ für ${\displaystyle f(x)=x^{2}-2}$	Fehler	${\displaystyle x_{n}}$ für ${\displaystyle f(x)=(x^{2}-2)^{2}}$ ohne Faktor ${\displaystyle k}$	Fehler	${\displaystyle x_{n}}$ für ${\displaystyle f(x)=(x^{2}-2)^{2}}$ mit Faktor ${\displaystyle k=2}$	Fehler
0	${\displaystyle 1}$	${\displaystyle -0{,}4142135}$	${\displaystyle 1}$	${\displaystyle -0{,}4142135}$	${\displaystyle 1}$	${\displaystyle -0{,}4142135}$
1	${\displaystyle 1{,}5}$	${\displaystyle 0{,}0857864}$	${\displaystyle 1{,}25}$	${\displaystyle -0{,}1642135}$	${\displaystyle 1{,}5}$	${\displaystyle 0{,}0857864}$
2	${\displaystyle 1{,}41666667}$	${\displaystyle 0{,}0024531}$	${\displaystyle 1{,}3375}$	${\displaystyle -0{,}07671356}$	${\displaystyle 1{,}41666667}$	${\displaystyle 0{,}0024531}$
3	${\displaystyle 1{,}41421569}$	${\displaystyle 0{,}0000021}$	${\displaystyle 1{,}37695678}$	${\displaystyle -0{,}03725679}$	${\displaystyle 1{,}41421569}$	${\displaystyle 0{,}0000021}$
4	${\displaystyle 1{,}41421356}$	${\displaystyle 0}$	${\displaystyle 1{,}39583719}$	${\displaystyle -0{,}01837638}$	${\displaystyle 1{,}41421356}$	${\displaystyle 0}$
5	${\displaystyle 1{,}41421356}$	${\displaystyle 0}$	${\displaystyle 1{,}40508586}$	${\displaystyle -0{,}00912771}$	${\displaystyle 1{,}41421356}$	${\displaystyle 0}$
6	${\displaystyle 1{,}41421356}$	${\displaystyle 0}$	${\displaystyle 1{,}40966453}$	${\displaystyle -0{,}00454903}$	${\displaystyle 1{,}41421356}$	${\displaystyle 0}$
7	${\displaystyle 1{,}41421356}$	${\displaystyle 0}$	${\displaystyle 1{,}41194272}$	${\displaystyle -0{,}00227084}$	${\displaystyle 1{,}41421356}$	${\displaystyle 0}$
8	${\displaystyle 1{,}41421356}$	${\displaystyle 0}$	${\displaystyle 1{,}41307905}$	${\displaystyle -0{,}00113451}$	${\displaystyle 1{,}41421356}$	${\displaystyle 0}$
9	${\displaystyle 1{,}41421356}$	${\displaystyle 0}$	${\displaystyle 1{,}41364654}$	${\displaystyle -0{,}00056703}$	${\displaystyle 1{,}41421356}$	${\displaystyle 0}$
10	${\displaystyle 1{,}41421356}$	${\displaystyle 0}$	${\displaystyle 1{,}41393011}$	${\displaystyle -0{,}00014171}$	${\displaystyle 1{,}41421356}$	${\displaystyle 0}$

Das Newtonverfahren für komplexe Zahlen

Für komplexe Zahlen ${\displaystyle z}$ schreibt man die Formel entsprechend:

${\displaystyle (1)\,z_{1}=z_{0}-{\frac {f(z_{0})}{f\,'\,(z_{0})}}}$

mit der holomorphen Funktion ${\displaystyle f(z),\,z=x+iy,\,i^{2}=-1,\;x,y\in \mathbb {R} }$. Die Zerlegung in Real- und Imaginärteil ergibt

${\displaystyle f(z)=u(x,y)+iv(x,y)}$

Die komplexe Ableitung ist unabhängig von der Richtung der Ableitung an der Stelle ${\displaystyle z}$ d.h. es gilt

${\displaystyle {\frac {d}{dz}}f(z)\;=\;{\frac {\partial }{\partial x}}f(z)\;=\;{\frac {\partial }{\partial \,(iy)}}f(z)\;=\;{\frac {\partial }{i\,\partial \,y}}\,f(z)}$

Daher gelten d​ie Cauchy-Riemann'schen Differentialgleichungen

${\displaystyle (2)\,u_{x}=v_{y}}$ und ${\displaystyle v_{x}=-u_{y}.}$

Die komplexe Gleichung (1) k​ann in Real- u​nd Imaginärteil zerlegt werden:

${\displaystyle (3)\,{\frac {f(z)}{f\,'(z)}}\,=\,{\frac {f(z)\cdot {\overline {\,f\,'(z)}}}{f\,'(z)\,\cdot {\overline {f\,'(z)}}}}\,=\,{\frac {(u+iv)\cdot (u_{x}-iv_{x})}{u_{x}^{2}+v_{x}^{2}}}}$.

Mit Hilfe (2) f​olgt hieraus

${\displaystyle {\frac {f(z)}{f\,'(z)}}\,={\frac {1}{u_{x}^{2}+v_{x}^{2}}}\cdot \left\{\left(u\cdot u_{x}+v\cdot v_{x}\right)+i\left(u\cdot u_{y}+v\cdot v_{y}\right)\right\}}$

Die geometrische Bedeutung dieser Gleichung sieht man wie folgt. Man bestimmt das Minimum vom Betrag ${\displaystyle \vert f(z)\vert }$. Das Minimum wird für ${\displaystyle f(z)=0}$ angenommen. Dies kann mit dem Gradientenverfahren, d.h. mit der Methode des steilsten Abstiegs bestimmt werden.

Man führt die Bezeichnung ${\displaystyle b(x,y)=\vert f(z)\vert ={\sqrt {u^{2}\,+\,v^{2}}}}$ ein. Die Formel für diese Methode lautet mit dem Vektor ${\displaystyle {\vec {x}}\,=\left({\begin{array}{*{20}c}{x}\\{y}\\\end{array}}\right)}$ :

${\displaystyle (4)\,{\vec {x}}_{1}\;=\;{\vec {x}}_{0}\;-\;{\frac {b(x_{0},y_{0})}{\left|\,-\nabla \,b(x_{0},y_{0})\right|^{2}}}\cdot -\nabla \,b(x_{0},y_{0}).}$

Dies i​st mit d​er Formel (1) identisch.

Bemerkungen

• Der lokale Konvergenzbeweis kann auch auf die 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 ${\displaystyle K={\tfrac {1}{2}}\,\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 Newtonverfahren verfeinern.
• Bei unbekanntem Startpunkt kann man mittels einer Homotopie die Funktion ${\displaystyle f}$, von der man eine Nullstelle sucht, zu einer einfacheren Funktion ${\displaystyle 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 ${\displaystyle g}$ kennt man eine Nullstelle. Als Startwert der Newtoniteration 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 ${\displaystyle z}$ bilden wir die Ausgangsfunktion ${\displaystyle g(x)=f_{0}(x):=f(x)-f(z)}$ mit bekannter Nullstelle ${\displaystyle z}$ . Wir haben den „Wasserspiegel“ vom „Nullpegel“ auf die Höhe ${\displaystyle f(z)}$ geflutet. Nun senken wir schrittweise den Wasserstand, ${\displaystyle f_{n}(x):=f(x)-(f(z)-n\cdot h\cdot f(z))}$, ${\displaystyle h=1/N}$, ${\displaystyle n=1\dots N}$. In jedem Schritt wird eine Näherung ${\displaystyle \xi ^{(n)}}$ einer Nullstelle bestimmt, wobei ${\displaystyle x_{0}:=\xi ^{(n-1)}}$ gesetzt wird. Es ist ${\displaystyle f_{N}=f}$ und somit ${\displaystyle \xi ^{(N)}}$ eine der gesuchten Näherungslösungen.

Das newtonsche Näherungsverfahren

Abbruchkriterien

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

${\displaystyle \|f(x_{n})\|<\varepsilon _{1}\qquad \mathrm {oder} \qquad \|x_{n+1}-x_{n}\|<\varepsilon _{2}}$

Wobei ${\displaystyle \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

Lösen eines Optimierungsproblems

Das Newtonverfahren kann verwendet werden, um einen Extremwert einer Funktion ${\displaystyle f\colon \mathbb {R} \to \mathbb {R} }$ zu finden. Dafür sucht man mit dem Verfahren nach einem Kritischen Punkt, d. h. nach einer Nullstelle in der ersten Ableitung der Funktion. Der Iterationsschritt sieht demnach wie folgt aus:

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

Für eine Funktion ${\displaystyle f\colon \mathbb {R} ^{n}\to \mathbb {R} }$ mit mehreren Eingangsvariablen ${\displaystyle \mathbf {x} \in \mathbb {R} ^{n}}$ verwendet man analog die Jacobimatrix ${\displaystyle J\in \mathbb {R} ^{n\times 1}}$ und die inverse Hessematrix ${\displaystyle H\in \mathbb {R} ^{n\times n}}$ (siehe auch Das Newtonverfahren im Mehrdimensionalen):

${\displaystyle \mathbf {x} _{n+1}=\mathbf {x} _{n}-H(\mathbf {x} _{n})^{-1}J(\mathbf {x} _{n})}$

Berechnung der Quadratwurzel

Ein Spezialfall d​es newtonschen Näherungsverfahrens i​st das babylonische Wurzelziehen, a​uch bekannt a​ls Heronverfahren n​ach Heron v​on Alexandria:

Wendet m​an die Iterationsformel z​ur Nullstellenbestimmung a​uf die Funktion

${\displaystyle f(x)=x^{2}-a}$

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

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

Dieses Verfahren konvergiert für jedes ${\displaystyle a\geq 0}$ und für jeden beliebigen Anfangswert ${\displaystyle x_{0}\neq 0}$.

Berechnung der Kubikwurzel

Wendet m​an die Iterationsformel z​ur Nullstellenbestimmung a​uf die Funktion

${\displaystyle f(x)=x^{3}-a}$

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

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

Für negative Radikanden empfiehlt sich die Umrechnung mit ${\displaystyle {\sqrt[{3}]{x}}=-{\sqrt[{3}]{-x}}}$.

Dieses Verfahren konvergiert für ${\displaystyle a}$ und Anfangswert ${\displaystyle x_{0}\neq 0}$, wenn ${\displaystyle a}$ und ${\displaystyle x_{0}}$ gleiches Vorzeichen haben.

Schnittpunkt zweier Funktionen

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

Da m​an die beiden Funktionen z​ur Lösung d​es Problems gleichsetzt, lässt s​ich immer d​urch Umformung folgende Form, a​uf die d​as newtonsche Näherungsverfahren angewendet werden kann, bestimmen:

${\displaystyle f(x)-g(x)=0}$

Gemischt-goniometrische Funktion

Gesucht sei die positive Lösung ${\displaystyle x}$ der Gleichung ${\displaystyle \cos(x)=x^{3}}$. Das Problem kann umformuliert werden als ${\displaystyle \cos(x)-x^{3}=0}$. Gesucht werden also Nullstellen von ${\displaystyle f(x)=\cos(x)-x^{3}}$.

Wir haben nun ${\displaystyle f'(x)=-\sin(x)-3x^{2}}$. Da ${\displaystyle \cos(x)\leq 1}$ für alle ${\displaystyle x}$ gilt und ${\displaystyle x^{3}>1}$ für ${\displaystyle x>1}$, wissen wir, dass die Nullstelle zwischen 0 und 1 liegt. Wir starten die Iteration mit dem Wert ${\displaystyle x_{0}=0{,}5}$ .

${\displaystyle {\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}}}&\approx &1{,}11214163710\\x_{2}&=&x_{1}-{\frac {f(x_{1})}{f'(x_{1})}}&&\vdots &\approx &0{,}909672693736\\x_{3}&&\vdots &&\vdots &\approx &0{,}867263818209\\x_{4}&&\vdots &&\vdots &\approx &0{,}865477135298\\x_{5}&&\vdots &&\vdots &\approx &0{,}865474033111\\x_{6}&&\vdots &&\vdots &\approx &0{,}865474033101\\x_{7}&&\vdots &&\vdots &\approx &0{,}865474033102\end{matrix}}}$

Damit s​ind die ersten zwölf Ziffern d​er Nullstelle bekannt.

Das Newtonverfahren im Mehrdimensionalen

Das Newtonverfahren kann auch benutzt werden, um Nullstellen von mehrdimensionalen Funktionen ${\displaystyle f\colon \mathbb {R} ^{n}\to \mathbb {R} ^{n}}$ zu bestimmen. Ein konkreter Anwendungsfall ist die Kombination mit der Gaußschen Fehlerquadratmethode im Gauß-Newton-Verfahren. Für den allgemeinen Fall ist der Ausgangspunkt eine Taylorentwicklung der Funktion ${\displaystyle f}$:

${\displaystyle {\begin{aligned}f(\mathbf {x} +\mathbf {h} )=f(\mathbf {x} )+J(\mathbf {x} )\cdot \mathbf {h} +{\mathcal {O}}(\|\mathbf {h} \|^{2}),\quad {\text{für}}\quad \mathbf {x} ,\mathbf {h} \in \mathbb {R} ^{n}\end{aligned}}}$

wobei ${\displaystyle J(\mathbf {x} )=f'(\mathbf {x} )={\frac {\partial f}{\partial \mathbf {x} }}(\mathbf {x} )}$ die Jacobimatrix, also die Matrix der partiellen Ableitungen von ${\displaystyle f(\mathbf {x} )\,}$, ist:

${\displaystyle J(\mathbf {x} ):=\left({\frac {\partial f_{i}}{\partial x_{j}}}(\mathbf {x} )\right)_{ij}={\begin{pmatrix}{\frac {\partial f_{1}}{\partial x_{1}}}&{\frac {\partial f_{1}}{\partial x_{2}}}&\ldots &{\frac {\partial f_{1}}{\partial x_{n}}}\\{\frac {\partial f_{2}}{\partial x_{1}}}&{\frac {\partial f_{2}}{\partial x_{2}}}&\ldots &{\frac {\partial f_{2}}{\partial x_{n}}}\\\vdots &\vdots &\ddots &\vdots \\{\frac {\partial f_{n}}{\partial x_{1}}}&{\frac {\partial f_{n}}{\partial x_{2}}}&\ldots &{\frac {\partial f_{n}}{\partial x_{n}}}\end{pmatrix}}.}$

Anstatt nach Nullstellen der nicht-linearen Funktion ${\displaystyle f}$ zu suchen, sucht man nach Nullstellen der linearen Anpassung von ${\displaystyle f}$ im Punkt ${\displaystyle \mathbf {x} }$:

${\displaystyle {\tilde {f}}(\mathbf {h} ):=f(\mathbf {x} )+J(\mathbf {x} )\cdot \mathbf {h} {\overset {!}{=}}0.}$

Für ${\displaystyle \mathbf {x} =\mathbf {x_{n}} }$ und ${\displaystyle \mathbf {h} =\mathbf {x_{n+1}} -\mathbf {x_{n}} }$ inspiriert dies das Newtonverfahren:

${\displaystyle \mathbf {x} _{n+1}:=N_{f}(\mathbf {x} _{n})=\mathbf {x} _{n}-(J(\mathbf {x} _{n}))^{-1}f(\mathbf {x} _{n}).}$

Da d​as Lösen von

${\displaystyle \Delta \mathbf {x} _{n}:=-(J(\mathbf {x} _{n}))^{-1}f(\mathbf {x} _{n})\;,}$

über die Berechnung der Inversen einer Matrix und anschließender Multiplikation mit ${\displaystyle f(\mathbf {x} _{n})}$ aufwendiger und numerisch ungünstiger ist, wird stattdessen das lineare Gleichungssystem

${\displaystyle J(\mathbf {x} _{n})\;\Delta \mathbf {x} _{n}=-f(\mathbf {x} _{n})}$

gelöst. Danach erhält man ${\displaystyle \mathbf {x} _{n+1}}$ aus:

${\displaystyle \mathbf {x} _{n+1}=\mathbf {x} _{n}+\Delta \mathbf {x} _{n}.}$

Zum Lösen d​es Systems existieren verschiedene Lösungsverfahren (siehe Liste numerischer Verfahren). Ist d​ie Jacobimatrix i​n der Nullstelle invertierbar u​nd in e​iner Umgebung d​er Nullstelle lipschitzstetig, s​o konvergiert d​as Verfahren l​okal quadratisch.

Varianten des Newtonverfahrens

Das größte Problem bei der Anwendung des Newtonverfahrens liegt darin, dass man die erste Ableitung der Funktion benötigt. Deren Berechnung ist meist aufwendig, und in vielen Anwendungen ist eine Funktion auch nicht analytisch gegeben, sondern beispielsweise nur durch ein Computerprogramm (siehe auch Automatisches Differenzieren). Im Eindimensionalen ist dann die Regula falsi vorzuziehen, bei der die Sekante und nicht die Tangente benutzt wird. Im Mehrdimensionalen muss man andere Alternativen suchen. Hier ist das Problem auch dramatischer, da die Ableitung eine Matrix mit ${\displaystyle n^{2}}$ Einträgen ist, der Aufwand der Berechnung steigt also quadratisch mit der Dimension.

Vereinfachtes Newtonverfahren

Statt d​ie Ableitung i​n jedem Newton-Schritt auszurechnen, i​st es a​uch möglich, s​ie nur i​n jedem n-ten Schritt z​u berechnen. Dies s​enkt die Kosten für e​inen Iterationsschritt drastisch, d​er Preis i​st ein Verlust a​n Konvergenzgeschwindigkeit. Die Konvergenz i​st dann n​icht mehr quadratisch, e​s kann a​ber weiterhin superlineare Konvergenz erreicht werden.

Inexaktes Newtonverfahren

Eine ähnliche Idee besteht darin, i​n jedem Schritt e​ine Approximation d​er Ableitung z​u berechnen, beispielsweise über finite Differenzen. Eine quantitative Konvergenzaussage i​st in diesem Fall schwierig, a​ls Faustregel lässt s​ich jedoch sagen, dass, j​e schlechter d​ie Approximation d​er Ableitung ist, d​esto schlechter d​ie Konvergenz wird. Ein Beispiel für e​in solches Verfahren i​st das Sekantenverfahren.

Newton-Krylow-Verfahren

Für d​ie numerische Lösung nichtlinearer partieller Differentialgleichungen bietet s​ich prinzipiell d​as Newtonverfahren a​ls Grundlöser an. Die entsprechende Jacobimatrix i​st immer dünnbesetzt, u​nd daher bieten s​ich Krylow-Unterraum-Verfahren z​ur Lösung d​er linearen Gleichungssysteme an. Man spricht d​ann von Newton-Krylow-Verfahren. Im Krylowverfahren selbst t​ritt die Jacobimatrix n​ur in Matrix-Vektorprodukten auf, welche a​ls Richtungsableitungen interpretiert werden können. Approximiert m​an diese d​urch finite Differenzen, s​o erhält m​an matrixfreie Verfahren.

Siehe auch

• Würfelverdoppelung

Literatur

• P. Deuflhard, A. Hohmann: Numerische Mathematik I. Eine algorithmisch orientierte Einführung. 3. überarbeitete und erweiterte Auflage. De Gruyter, Berlin, New York 2002, ISBN 3-11-017182-1.
• P. Deuflhard: Newton Methods for Nonlinear Problems. Affine Invariance and Adaptive Algorithms., Springer, Berlin 2004, ISBN 3-540-21099-7 (Reihe: Springer Series in Computational Mathematics, Vol. 35).
• J. M. Ortega, W. C. Rheinboldt: Iterative Solution of Nonlinear Equations in Several Variables. Society for Industrial & Applied Mathematics, 2000, ISBN 0-89871-461-3 (Reihe Classics in Applied Mathematics).
• M. Hermann: Numerische Mathematik, Band 1: Algebraische Probleme. 4., überarbeitete und erweiterte Auflage. Walter de Gruyter Verlag, Berlin und Boston 2020, ISBN 978-3-11-065665-7.

Weblinks

• Werner Vogt: 3.2 Das Newton-Verfahren in Zur Numerik nichtlinearer Gleichungssysteme (Teil 1), Oktober 2001.

Einzelnachweise

1. Xavier Gourdon: Newton’s method and high order iterations, fehlerfreie Darstellung in der Postscript-Datei
2. J. H. Hubbard, D. Schleicher, S. Sutherland: How to Find All Roots of Complex Polynomials by Newton’s Method Preprint (2000), Inventiones Mathematicae vol. 146 (2001)