3.0. Newtonverfahren

Das Newtonverfahren (nach Sir Isaac Newton) ist ein häufig verwendeter Approximationsalgorithmus zur Lösung von nichtlinearen Gleichungen und Gleichungssystemen, bei denen die Nullstellen nicht wie z. B. durch Polynomdivision zu berechnen sind.
Die grundlegende Idee dieses Verfahrens ist, die Funktion in einem Ausgangspunkt zu linearisieren. Man bestimmt hierfür zunächst ihre Tangente. Die Nullstelle der Tangente wird als verbesserte Näherung der Nullstelle der Funktion verwendet. 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.
Es wird, ausgehend von einem Startwert x_{0} die Iteration x_{n+1} = x_{n} - \frac{f(x_{n})}{f'(x_{n})} so oft wiederholt bis eine gewünschte Genauigkeit erreicht wird.
Schauen wir uns mal das Beispiel f(x) = x³ + 5x – 5 an. Wir können hier weder x ausklammern noch eine Nullstelle raten, folglich auch keine Polynomdivision anwenden. Daher ermitteln wir die Nullstellen mithilfe des Newtonsverfahrens.
Ist eine Intervall vorgegeben, in welchem sich die Nullstelle befindet, so nimmt man in diesem Fall die Mitte des Intervalls als Startwert x_{0} . Denn je näher der Startwert an der Nullstelle liegt, desto weniger Rechenschritte benötigt man.
Wir wählen in unserem Fall als Startwert x_{0}   = 0.
Da wir im Nenner der Iterationsformel mit der Ableitung rechnen, berechnen wir diese bevor wir mit dem eigentlichen Newtonverfahren beginnen. f'(x) = 3x² + 5.
Im ersten Schritt bestimmen wir x_{1} mit x_{1} = x_{0} - \frac{f(x_{0})}{f'(x_{0})} = 0 - \frac{0³ + 5•0 - 5}{3•0² + 5} = 0 - \frac{-5}{5} = 0 - (-1) = 1
Mit dem soeben errechneten Wert x_{1} = 1 bestimmen wir x_{2} mit x_{2} = x_{1} - \frac{f(x_{1})}{f'(x_{1})} = 1 - \frac{1³ + 5•1 - 5}{3•1² + 5} = 1 - \frac{1}{8} = \frac{7}{8} = 0,875
Nun bestimmen wir x_{3} mit x_{3} = x_{2} - \frac{f(x_{2})}{f'(x_{2})} = 0,875 - \frac{0,875³ + 5•0,875 - 5}{3•0,875² + 5} = 0,875 - \frac{23}{512}:\frac{467}{64} = 0,875 - \frac{1623}{1868} = 0,86884
Und x_{4} mit x_{4} = x_{3} - \frac{f(x_{3})}{f'(x_{3})} = 0,86884 - \frac{0,86884³ + 5•0,86884 - 5}{3•0,86884² + 5} = 0,86884 - 0,000099:7,26465 = 0,86883
Man sieht, dass sich die letzten beiden Werte nur noch in der fünften Nachkommastelle ändern. Das soll als Genauigkeit reichen.
Macht man die Probe, bestimmt also f(0,86883), dann erhält man -0,00000014. Da wir mit einem gerundeten Ergebnis gerechnet haben, erhalten wir als Ergebnis nicht genau 0. Die Genauigkeit sollte aber für schulische Zwecke ausreichend sein.

 

Übung

Newtonverfahren 1

Newtonverfahren 2