Beim Newton-Verfahren geht es darum, Nullstellen einer Funktion zu finden. Das heißt es wird der Schnittpunkt einer Funktion mit der X-Achse gesucht. Das Newton-Verfahren ist ein iteratives Verfahren, es wird also ein Schritt nach dem anderen ausgeführt und mit jedem Schritt steigt die Genauigkeit des Ergebnisses. Wie das funktioniert zeigt die folgende Animation:
(Ein Klick auf das Bild zeigt die Animation)
Animation: Ralf Pfeifer Lizenz: Creative Commons by-sa 3.0 de / kurz
Es wird ein Startwert auf der X-Achse gewählt. An dieser Stelle wird eine Tangente zu der Funktion gebildet. Die Steilheit der Tangente entspricht der Steilheit der Funktion an diesem Punkt, lässt sich also mit der Ableitung der Funktion bestimmen. Da die Tangente eine Gerade ist und man ihre Steilheit kennt, lässt sich leicht der Schnittpunkt der Tangente mit der X-Achse bestimmen. Der X-Wert dieses Punktes wird als Startwert für den nächsten Schritt des Newton-Verfahrens genutzt.
Nach einigen Schritten kommt man der Nullstelle schon ziemlich nahe. Im günstigsten Fall verdoppelt sich die Zahl der richtig ermittelten Dezimalstellen mit jedem Schritt.
Formel
Die Formel für das Newton-Verfahren lautet:
[pmath]x_{n+1}=x_n-{f(x_n)}/{f prime(x_n)}[/pmath]
[pmath]x_n[/pmath] ist immer der Startwert des aktuellen Schritts und [pmath]x_{n+1}[/pmath] ist entsprechend der Startwert des nächsten Schritts.
Aus [pmath]f(x_n)[/pmath] und der Tangente an der Stelle [pmath]x_n[/pmath], mit der Steilheit [pmath]f prime(x_n)[/pmath], wird ein Steigungsdreieck gebildet. Der Bruch [pmath]{f(x_n)}/{f prime(x_n)}[/pmath] ist also ein Verhältnis von der senkrechten Seite des Dreiecks ([pmath]f(x_n)[/pmath]) und der Steigung ([pmath]f prime(x_n)[/pmath]) und beschreibt die Strecke ([pmath]Delta x[/pmath]) zwischen [pmath]x_n[/pmath] und dem Schnittpunkt der Tangente mit der X-Achse ([pmath]x_{n+1}[/pmath]).
Code
Die Umsetzung in einer Programmiersprache ist hier sehr einfach. Die Klasse Fkt stellt eine Funktion und deren Ableitung zur Verfügnug. Die Methode calcY() erwartet als Parameter 1. welche Funktion betrachtet werden soll (Grundfunktion oder Ableitung) und 2. an welcher Stelle. Sie gibt den Y-Wert der entsprechenden Funktion an der Stelle X zurück.
Der folgende Code stammt aus der „Newton-App“:
while(differenz > grenze) {
x = x - fkt.calcY(Fkt.GRUNDFUNKTION, x) / fkt.calcY/(Fkt.ABLEITUNG1, x);
differenz = fkt.clacY(Fkt.GRUNDFUNKTION, x);
differenz = Math.sqrt(differenz * differenz);
}
Da das Newton-Verfahren ein iteriertes Verfahren ist, wird es in einer Schleife ausgeführt. Die Schleife wird ausgeführt, so lange der Wert von „differenz“ größer ist als der Wert von „grenze“. „grenze“ wird im Quelltext vorher festgelegt und setzt die maximale Ungenauigkeit des Ergebnis fest. Steht also im Quelltext „grenze = 0.0001;“, dann weicht f(x) maximal 0,0001 von Null ab. Wenn im Quelltext steht „grenze = 0.0;“, dann bleibt das Ergebnis zwar eine Annäherung, hat aber die maximale Genauigkeit, die z.B. eine 32-Bit-Variable leisten kann.
In Zeile 2 wird einfach der nächste X-Wert mit der oben stehenden Formel berechnet.
Zeile 3 und 4 bestimmen die Differenz zwischen f(x) und Null. Da wir ja eine Nullstelle suchen, sollte diese Differenz so klein wie möglich sein. In Zeile 3 wird der Funktionswert bei X berechnet und in Zeile 4 wird der Betrag gebildet. Die Betragsbildung ist nötig, weil eine negative Differenz nicht größer wäre als „grenze“ und die Schleife dadurch beendet werden würde, auch wenn das Ergebnis noch sehr ungenau ist.
Hinweis: Der Code oben ist nur zur Veranschaulichung. So wie er oben steht sollte man den Code nicht in einem Programm verwenden. Es fehlt zum Beispiel eine Absicherung für den Fall, dass die Funktion keine Nullstelle hat. Dieser Code würde dann in eine Endlosschleife resultieren.