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 Lösung nichtlinearer Gleichungen und Gleichungssysteme. Im Falle einer Gleichung in einer Variablen lassen sich zu einer gegebenen stetig differenzierbaren Funktion f:ℝ→ℝ 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 zu linearisieren, d.h. ihre Tangente zu bestimmen, und die Nullstelle der Tangente als verbesserte Näherung der Nullstelle der Funktion zu verwenden.

Einleitung

Geometrische Deutung

Anschaulich gelangt man wie folgt zu diesem Verfahren: Sei f:ℝ→ℝ eine stetig differenzierbare reelle Funktion, von der wir eine Stelle x_n mit "kleinem" Funktionswert kennen. Wir wollen einen Punkt x_n+1 nahe x_n finden, der eine bessere 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'(x_n).

Die Tangente ist durch die Funktion t(x_n+h):=f(x_n)+f'(x_n)h gegeben, setzen wir h=x-x_n ein, so erhalten wir

t(x):=f(x_n)+f'(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'(x_n) (x_n+1-x_n) ⇒ 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 Folge von "verbesserten" Stellen (x_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.

Historisches

Isaac Newton verfaßte im Zeitraum 1664-1671 die Arbeit "Methodus fluxionum et serierum infinitarum" (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:

(2+p)³=8+12p+6p²+p³ => p³+6p²+10p-1=0.

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.. erhalten.

Joseph Raphson beschrieb 1690 in der Arbeit "Analysis Aequationum universalis" diesen Rechenprozess formal und illustrierte den Formalismus an der allgemeinen Gleichung 3. Grades. (Nach Quelle [1].)

Erstes Beispiel

Zur Bestimmung einer Quadratwurzel von a>0 kann man die Nullstellen der Funktion f(x)=1-a/x² betrachten. Die Newton-Iteration erfolgt dann 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 (s. unten) ist, dass es divisionsfrei ist, sobald einmal der Kehrwert von a bestimmt wurde.

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

Gegenbeispiele

Das Newton-Verfahren ist ein so genanntes lokal konvergentes Verfahren. Konvergenz zu einer Nullstelle ist also nur garantiert, wenn der Startwert hinreichend nah an der Nullstelle liegt. Ist der Startwert zu weit weg, kann alles passieren: das Verfahren divergiert, es konvergiert trotzdem oder, falls die Funktion mehrere Nullstellen hat, ist es auch möglich, dass das Verfahren eine andere als die gewünschte (falls man weiß, welche man will) Nullstelle findet.

1.) Oszillierendes Verhalten ergibt sich für das Polynom f(x):=x³-2x+2 (s. Quelle [2]) mit f'(x)=3x²-2. Der Punkt x=0 mit f(0)=2 und f'(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'(1)=1, wird auf N(1)=1-1/1=0 abgebildet, so dass sich in der Newton-Iteration mit einem dieser Punkte als Startwert diese beiden Punkte ständig abwechseln. Erschwerend kommt hinzu, dass dieser Zyklus stabil ist, d.h. es gibt eine kleine Umgebung beider Punkte, so dass Startpunkte in dieser Umgebung gegen den Zyklus konvergieren, d.h. 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'(x)=cos(x) und N(x)=x-tan(x). Es gibt eine Stelle x₀∈[-π/2,0] mit tan(x₀)=-2π. Man überzeugt sich, dass dann x_n=x₀+2π n gilt. Dieses Verhalten ist nicht stabil, d.h. bei leichter Variation des Anfangswertes, wie sie z.B. 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.

Konvergenzbetrachtungen

Das Newton-Verfahren ist ein so genanntes lokal konvergentes Verfahren. Konvergenz zu einer Nullstelle ist also nur garantiert, wenn der Startwert hinreichend nah an der Nullstelle liegt. Ist der Startwert zu weit weg, kann alles passieren: das Verfahren divergiert, es konvergiert trotzdem oder, falls die Funktion mehrere Nullstellen hat, ist es auch möglich, dass das Verfahren eine andere als die gewünschte Nullstelle findet. Bei geeigneter Wahl des Startwertes x₀ kann das Newtonsche Verfahren quadratisch, also mit der Konvergenzordnung 2, konvergieren.

Newton-Verfahren als Fixpunktiteration

Sei f:ℝ→ℝ eine stetig differenzierbare reelle Funktion, von der wir eine Nullstelle bestimmen möchten. Wir versuchen, die Voraussetzungen des Banachschen Fixpunktsatzes zu erfüllen. Dazu konstruieren wir aus f(x)=0 eine Fixpunktgleichung, eine allgemeine Form ist x=N(x):=x+g(x)f(x) mit einer zusätzlichen, stetig differenzierbaren Funktion g. Jede Nullstelle ξ von f, f(ξ)=0, ist Fixpunkt von N:

$N(\xi )=\xi +g(\xi )\cdot \underbrace {f(\xi )} _{=0}=\xi$.

Wir benötigen, nach den Voraussetzungen des Fixpunktsatzes, ein Intervall I⊆ℝ, welches die Nullstelle ξ enthält, und dass die Abbildung N auf diesem Intervall kontraktiv ist. Dazu ist es ausreichend, dass die Ableitung N'(x) für x∈I nur Werte im Intervall [-1,1] annimmt. Insbesondere kann man fordern, dass der Wert der Ableitung N`(ξ) von N in ξ einen möglichst kleinen Betrag habe. Die Ableitung von N ist

$N'(x)=1+g'(x)\cdot f(x)+g(x)\cdot f'(x)\quad \Longrightarrow \quad N'(\xi )=1+g(\xi )f'(\xi )$,

wählt man also immer g(x):=-f'(x)^-1, und gibt es eine Umgebung von ξ, in der f zweimal differenzierbar ist und f'(x) nirgends Null wird, so ist N'(ξ)=0.

Wir gelangen somit zur Fixpunktgleichung

$x=N_{f}(x):=x-{\frac {f(x)}{f'(x)}}$

mit dem Newton-Operator N_f, welche als Fixpunktiteration wieder die Newton-Iteration ergibt:

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

bei "geeigneter" Wahl eines Startpunktes x₀.

Von dieser muß natürlich noch die Konvergenz gegen eine Nullstelle exakt nachgewiesen werden.

Lineare Konvergenz

Satz 1: Sei f einmal stetig differenzierbar, ξ eine Nullstelle von f. Sei g ebenfalls einmal stetig differenzierbar mit g(ξ)f'(ξ)∈(0,5;1,5). Dann gibt es eine Umgebung I von ξ, so dass die Iteration x_{n+1:=N(xn):=xn-g(xn)f(xn)} für jeden Startpunkt x₀ aus I gegen ξ konvergiert.

Beweis: Wegen der Stetigkeit von N'(x)=1-g'(x)f(x)-g(x)f'(x) und wegen |N'(ξ)|<0,5 laut Voraussetzung gibt es ein r>0, so dass auf dem gesamten Intervall I:=[ξ-r,ξ+r] gilt -0.5 ≤ N'(x) ≤ 0.5 für alle Stellen x∈I. Wählen wir den Startwert x0∈I in diesem Intervall, so liegt auch jedes nachfolgende Glied der Folge in diesem Intervall. Denn mit xn∈I folgt aus den Fixpunkteigenschaften und dem Mittelwertsatz der Differentialrechnung: $x_{n+1}-\xi =N_{f}(x_{n})-N_{f}(\xi )=N'_{f}(x_{n}^{*})\cdot (x_{n}-\xi )$ mit einem Zwischenpunkt xn* zwischen xn und ξ, $\Longrightarrow |x_{n+1}-\xi |\leq {\frac {1}{2}}|x_{n}-\xi |\leq {\frac {1}{2}}r$. Wir lesen daraus nicht nur ab, dass auch xn+1∈I gilt, sondern sogar, dass die Differenzfolge (xn-ξ) eine Nullfolge mit geometrischer Majorante ist: $|x_{n}-\xi |\leq \left({\frac {1}{2}}\right)^{n}|x_{0}-\xi |$.

Diese Art der Konvergenzgeschwindigkeit nennt man linear (im Exponenten).

Ist f zweimal stetig differenzierbar und f'(ξ)≠0, so erhalten wir die Konvergenz des Newton-Verfahrens. Für diese spezielle Wahl von g kann allerdings eine bessere Abschätzung der Konvergenz angegeben werden.

Quadratische Konvergenz

Satz 2: Sei f zweimal stetig differenzierbar und ξ eine Nullstelle von f. Dann gibt es eine Konstante K>0, so dass die Newton-Iteration mit Startpunkt im Intervall I=(ξ-1/K,ξ+1/K) gegen ξ konvergiert, genauer gilt |x_{n-ξ|≤ K/2 |xn-1-ξ|²≤}$(0,5)^{2^{n}-1}|x_{0}-\xi |$.

Beweis: Schauen wir uns die Ableitung N'f(x) einmal genauer an, mit der Quotientenregel des Differenzierens gilt: $N'_{f}(x)=1-{\frac {f'(x)f'(x)-f(x)f''(x)}{f'(x)^{2}}}={\frac {f(x)f''(x)}{f'(x)^{2}}}$. Ist die Funktion f gutartig oder das Intervall I klein genug, so sind die Ableitungen f'(x) und f"(x) fast konstant auf I, der Funktionswert f(x) jedoch nahezu linear mit Nullstelle in ξ und Anstieg f'(ξ). Wir können also (wieder mit dem Mittelwertsatz) einen weiteren Faktor (x-ξ) aus f(x)=f(x)-f(ξ) abspalten: $N'_{f}(x)={\frac {f''(x)}{f'(x)^{2}}}\cdot (f(x)-f(\xi ))={\frac {f''(x)}{f'(x)^{2}}}f'(x^{*})\cdot (x-\xi )$ mit einem Zwischenpunkt x* zwischen x und ξ. Für x nahe ξ gilt damit näherungsweise $N'_{f}(x)\approx {\frac {f''(\xi )}{f'(\xi )}}\cdot (x-\xi )$, Integration von ξ bis x ergibt $N_{f}(x)=N_{f}(\xi )+\int _{\xi }^{x}N'_{f}(z)\,dz\approx \xi +{\frac {f''(\xi )}{2f'(\xi )}}\cdot (x-\xi )^{2}$. Dies entspricht, näherungsweise, der Behauptung. Um zu einer exakten Abschätzung zu gelangen, können wir die zwei "komplizierten" Faktoren in N'f(x) gegen ihre Maxima über I abschätzen: $|N'_{f}(x)|\leq \max _{x\in I}{\frac {f''(x)}{f'(x)^{2}}}\cdot \max _{x^{*}\in I}|f'(x^{*})|\cdot |x-\xi |=K\cdot |x-\xi |$. Dabei wurde mit K die Konstante, die das Produkt der beiden Maxima ist, bezeichnet. Wir erhalten für die Rekursionsfolge der Newton-Iteration die folgenden Abschätzungen (dabei sei hn:=xn-ξ) $x_{n+1}-\xi =N_{f}(x_{n})-N_{f}(\xi )=\int _{0}^{1}N'_{f}(\xi +th_{n})h_{n}\,dt$, $\Longrightarrow |x_{n+1}-\xi |\leq \int _{0}^{1}K|(\xi +th_{n})-\xi |\cdot |h_{n}|\,dt=K|x_{n}-\xi |^{2}\int _{0}^{1}t\,dt={\frac {K}{2}}|x_{n}-\xi |^{2}$. Die rekursive Ungleichung $|h_{n+1}|\leq {\frac {K}{2}}|h_{n}|^{2}$ hat die Lösung $|h_{n}|=|x_{n}-\xi |\leq \left({\frac {K}{2}}\right)^{2^{n}-1}\cdot |x_{0}-\xi |^{2^{n}}=\left({\frac {K|x_{0}-\xi |}{2}}\right)^{2^{n}-1}\cdot |x_{0}-\xi |$, wovon man sich mittels vollständiger Induktion überzeugt. Ist also K/2|x0-ξ|<1, so konvergiert die Folge (xn) gegen ξ.

Diese Geschwindigkeit der Konvergenz wird als quadratisch bezeichnet, die (logarithmische) Genauigkeit bzw. Anzahl gültiger Stellen verdoppelt sich in jedem Schritt. Die Abschätzung des Abstands |x_n-ξ| zur Nullstelle wird oft linear in |x_0-ξ| angegeben, so gilt z.B.

• für $|x_{0}-\xi |\leq {\frac {1}{K}}$ durch $2^{n}-1$-faches Einsetzen

$|x_{n}-\xi |\leq \left({\frac {1}{2}}\right)^{2^{n}-1}\cdot |x_{0}-\xi |$,

wodurch sich die Anzahl der gültigen Stellen im Binärsystem abschätzen läßt, oder

• für $|x_{0}-\xi |\leq {\frac {1}{5K}}$ gilt

$|x_{n}-\xi |\leq \left({\frac {1}{10}}\right)^{2^{n}-1}\cdot |x_{0}-\xi |$,

d.h. nahe der Nullstelle ergibt sich auch eine Verdopplung der Dezimalstellen in jedem Schritt.

Anfangsbedingungen

Es muss anfänglich ein Näherungswert x₀ bekannt sein. Die Funktion f(x) muss in jedem Punkt der Ausgangsmenge differenzierbar sein. Das heißt für f(x) muss dort die Ableitung f'(x) existieren. Weiterhin muss gelten, dass f'(x) stetig invertierbar ist. Das heißt die Funktion darf von x₀ bis zur anzunähernden Nullstelle keine Extrema oder Sattelpunkte besitzen, da dort für die Ableitung f'(x) = 0 gelten würde.

Diese Voraussetzung ist erfüllt, wenn gilt

$f:\mathbb {R} \rightarrow \mathbb {R}$ differenzierbar mit $f'(x)\neq 0\quad \forall \quad x\in \,]x_{1},x_{2}[\qquad ;\,x_{1}<x_{2}$

Bemerkungen

• Schon bei Polynomen gibt es oft mehr als eine Nullstelle von f

Um alle Nullstellen zu finden, muss man das Newtonverfahren mehrmals mit verschiedenen Startwerten durchführen.

• Der Konvergenzbeweis basiert auf der Taylor-Entwicklung des Grades 2, ist im mehrdimensionalen Fall allerdings technisch schwierig. Für diesen Fall wurde er zuerst von Leonid Kantorowitsch geführt.

Satz von Kantorowitsch.

• Jede Gleichung lässt sich in eine Nullstellenform bringen.

Das Newtonverfahren ist also zur Lösung von fast beliebigen nichtlinearen Gleichungen geeignet, solange der Startwert eine gute Schätzung der gesuchten Nullstelle ist.

• Bei unbekanntem Startpunkt kann man eine Homotopie zu einem einfachen Problem verwenden, d.h. man durchläuft eine Folge sich nur "wenig" unterscheidender Funktionen, von der man zur ersten eine Nullstelle kennt. Als Startwert der aktuellen Rekursion verwendet man die Näherung einer Nullstelle der vorhergehenden Funktion.

Als Beispiel mag die "Flutungshomotopie" dienen: mit einem willkürlichen z bilden wir die Ausgangsfunktion 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)-nhf(z)), h=1/N, n=1..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.

Das Verfahren im Mehrdimensionalen

Das Newton-Verfahren kann auch benutzt werden, um Nullstellen von mehrdimensionalen Funktionen $f(x):\mathbb {R} ^{n}\to \mathbb {R} ^{n}$ zu bestimmen. Ausgangspunkt der Iteration ist wieder die obige Fixpunktgleichung:

$x=N_{f}(x):=x-(Df(x))^{-1}f(x)\,$

die das Newton-Verfahren inspiriert:

$x_{n+1}:=N_{f}(x_{n})=x_{n}-(Df(x_{n}))^{-1}f(x_{n})\,,$

wobei $Df(x)=f'(x)={\frac {\partial f}{\partial x}}(x)$ die Jacobi-Matrix, also die Matrix der partiellen Ableitungen von $f(x)\,$, ist. $Df(x):={\frac {\partial (f_{1},\dots ,f_{n})}{\partial (x_{1},\dots ,x_{n})}}={\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}}$

Da die Berechnung der Inversen einer Matrix sehr aufwändig ist, wird auf die Aufstellung von $(Df(x))^{-1}\,$ verzichtet und statt dessen folgender Weg gewählt: Man berechnet den Wert

$\Delta x:=-(Df(x_{n}))^{-1}f(x_{n})\;,$

indem man das lineare Gleichungssystem

$Df(x_{n})\;\Delta x=-f(x_{n})$

löst, und hat dann

$x_{n+1}=x_{n}+\Delta x_{n}\;.$

Statt die Inverse auszurechnen, wird also ein lineares Gleichungssystem gelöst. Häufig kann man hier Eigenschaften der Jacobi-Matrix ausnutzen, um schnell und effizient zu einer Lösung zu kommen. Die weiteren Eigenschaften des Newton-Verfahrens (lokale, quadratische Konvergenz) sind im mehrdimensionalen genau wie im eindimensionalen Fall.

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.

Anwendungen

Berechnung der Quadratwurzel

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

Wendet man die Iterationsformel auf die Funktion
$f(x)=x^{2}-a=0$
an, dann erhält man die für die Lösung ${\sqrt {a}}$ das Näherungsverfahren

$x_{n+1}:={\frac {1}{2}}(x_{n}+{a \over x_{n}})$
Dieses Verfahren konvergiert bei $a\geq 0$ 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 f(x) = cos(x) - x³.

Wir haben nun f '(x) = -sin(x) - 3x². Da cos(x) ≤ 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})}}&=&{\frac {\cos(0.5)-0.5^{3}}{-\sin(0.5)-3\times 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.

 <script>
  
  function NewtonIterationFnct(x) {
     return  x - (Math.cos(x) - x*x*x) / (-Math.sin(x) - 3*x*x)     
  }  

  x = 0.5
  
  for (i=0; i<=99; i++) {
	document.write("Iteration " + i + ": ")
	document.write(x)
	document.write('<br>')
        xold = x
	x = NewtonIterationFnct(x) 
        if (x == xold) break 
  }
 </script>

Probleme bei der praktischen Anwendung

Das größte Problem liegt darin, dass man die erste Ableitung der Funktion benötigt. Sollte man diese nicht explizit gegeben haben, so ist fast immer die Regula Falsi, eine Abwandlung der Newton-Iteration, vorzuziehen.

Weblinks

• Facharbeit über das Newtonsche Näherungsverfahren und die Regula Falsi

• Newton-Verfahren interaktiv

• [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)