Newton-Verfahren

Varianten des Newton-Verfahrens

Das größte Problem bei der Anwendung des Newton-Verfahrens liegt darin, dass man die erste Ableitung der Funktion benötigt. Die Berechnung dieser ist meist aufwändig und in vielen Anwendungen ist eine Funktion auch nicht explizit, sondern beispielsweise nur durch ein Computerprogramm gegeben (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 n² Einträgen ist, der Aufwand der Berechnung steigt also quadratisch mit der Dimension.

Vereinfachtes Newton-Verfahren

Statt die Ableitung in jedem Newton-Schritt auszurechnen, ist es auch möglich, sie nur in jedem n-ten Schritt zu berechnen. Dies senkt die Kosten für einen Iterationsschritt drastisch, der Preis ist ein Verlust an Konvergenzgeschwindigkeit. Die Konvergenz ist dann nicht mehr quadratisch, es kann aber weiterhin superlineare Konvergenz erreicht werden.

Inexakte Newton-Verfahren

Eine ähnliche Idee besteht darin, in jedem Schritt eine Approximation der Ableitung zu berechnen, beispielsweise über finite Differenzen. Eine quantitative Konvergenzaussage ist in diesem Fall schwierig, als Faustregel lässt sich jedoch sagen, dass die Konvergenz umso schlechter wird, je schlechter die Approximation der Ableitung ist. Ein Beispiel für ein solches Verfahren ist das Sekantenverfahren.

Newton-Krylow-Verfahren

Für die numerische Lösung nichtlinearer partieller Differentialgleichungen bietet sich prinzipiell das Newton-Verfahren als Grundlöser an. Die entsprechende Jacobi-Matrix ist immer dünnbesetzt und so bieten sich Krylow-Unterraum-Verfahren zur Lösung der linearen Gleichungssysteme an. Man spricht dann von Newton-Krylow-Verfahren. Im Krylow-Verfahren selbst tritt die Jacobi-Matrix nur in Matrix-Vektorprodukten auf, welche als Richtungsableitungen interpretiert werden können. Approximiert man diese durch Finite Differenzen, so erhält man komplett matrixfreie Verfahren.

Copyright- und Lizenzinformationen: Diese Seite basiert auf dem Artikel Newton-Verfahren aus der freien Enzyklοpädιe Wιkιpedιa und steht unter der Lizenz Creative Commons CC-BY-SA 3.0 Unported (Kurzfassung). Liste der Autoren

Anbieterkennzeichnung