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. 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^2$ Einträgen ist, der Aufwand der Berechnung steigt also quadratisch mit der Dimension.

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.

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 schlechter wird, je schlechter die Approximation der Ableitung ist.

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.