eine der wichtigsten Methoden zur numerischen Approximation von Nullstellen einer Funktion und – damit verbunden – zur Approximation lokaler Extremalpunkte von Optimierungsproblemen.

Die Einsatzbereiche des Newtonverfahrens sind so vielfältig, daß hier nur ein kleiner Eindruck vermittelt werden kann. Die Methode ist sowohl theoretisch als auch praktisch von unschätzbarer Bedeutung.

Die elementarste Form der Newtonmethode ist ihre Anwendung auf die Bestimmung einer Nullstelle einer stetig differenzierbaren Funktion f : [a, b] → ℝ. Das Verfahren versucht, iterativ von einem Startpunkt x₀ ∈ (a, b) aus eine Folge {x_k, k ∈ ℕ} zu konstruieren, die gegen eine Nullstelle von f in (a, b) konvergiert. Dabei berechnet sich die neue Iterierte x_k+1 aus der alten x_k gemäß \begin{eqnarray}{x}_{k+1}:={x}_{k}-\displaystyle\frac{f({x}_{k})}{f^{\prime} ({x}_{k})}.\end{eqnarray}Hierbei ist vorausgesetzt, daß die Ableitung f′(x_k) nicht verschwindet. Die geometrische Idee hinter dieser Iteration ist es, in x_k die Tangente an den Graphen von f zu legen und diese mit der x–Achse zu schneiden. Der Schnittpunkt ist dann gerade x_k+1. Damit führt das Newtonverfahren eine Linearisierung des Problems aus: In jedem Schritt wird anstelle einer (möglicherweise) nichtlinearen Gleichung f(x) = 0 das entsprechende lineare System \begin{eqnarray}f({x}_{k})+{f}{^{\prime} }({x}_{k})\cdot (x-{x}_{k})=0\end{eqnarray} zu x_k gelöst.

Sei f : [a, b] → ℝ eine dreimal stetig differenzierbare Funktion, die in \(\bar{x}\in (a,b)\)eine Nullstelle habe. Gelte ferner f′(x) = 0 in einer Umgebung U von \(\bar{x}\)(d. h. insbesondere, daß \(\bar{x}\)eine einfache Nullstelle ist). Dann konvergiert das Newtonverfahren für f für jeden Startpunkt x₀ ∈ U gegen die Nullstelle \(\bar{x}\). Die Konvergenzgeschwindigkeit ist quadratisch, d. h., es gibt eine Konstante C > 0, so daß \begin{eqnarray}|\bar{x}-{x}_{k+1}|\le C{|\bar{x}-{x}_{k}|}^{2},\,\,k\in {\mathbb{N}},\end{eqnarray}gilt.

Letzteres bedeutet, daß sich die Anzahl der korrekten Stellen mit jedem Iterationsschritt nahezu verdoppelt (in Abwesenheit von Rundungsfehlern). Genauer kann man sogar zeigen, daß \begin{eqnarray}\mathop{\mathrm{lim}}\limits_{k\to \infty }\displaystyle\frac{|{x}_{k+1}-\bar{x}|}{{({x}_{k}-\bar{x})}^{2}}=\displaystyle\frac{1}{2}\left|\displaystyle\frac{{f}{^{\prime\prime} }(\bar{x})}{{f}{^{\prime} }(\bar{x})}\right|.\end{eqnarray}

Während obiges Kriterium Ableitungen bis zur dritten Ordnung verwendet und diese über einer offenen Menge U Einschränkungen unterwirft, gibt es andere Kriterien, die höhere Differenzierbarkeitsordnungen von f verlangen, dafür aber nur Bedingungen an die Ableitungen in der aktuellen Newtoniterierten stellen. Ein solches Kriterium stellt etwa die α-Theorie von Smale bereit.

I. allg. ist die Frage nach Konvergenzbereichen von immenser Schwierigkeit und Gegenstand intensiver Forschung. Die Frage nach den sogenannten Einzugsbereichen verschiedener Nullstellen (d. h. den Mengen von Startwerten, für die das Newtonverfahren gegen die entsprechende Nullstelle konvergiert) beispielsweise führt in die Theorie der dynamischen Systeme.

Ein noch recht einfaches Kriterium für einen Spezialfall liefert folgender Satz:

Es sei f ein Polynom r-ten Grades, r > 1, d. h. \begin{eqnarray}f(x)=\displaystyle \sum _{k=0}^{r}{a}_{k}{x}^{k},\,\,x\in {\mathbb{R}},\end{eqnarray}welches nur reelle Nullstellen ξ_i mit \begin{eqnarray}{\xi }_{1}\ge {\xi }_{2}\ge \ldots \ge {\xi }_{r}\end{eqnarray}besitzt.

Dann liefert das Newtonverfahren für jeden Startwert x₀ > ξ₁eine gegen ξ₁konvergente monoton fallende Folge. Diese Konvergenz ist im Fall r ≥ 2 streng monoton.

Durch Abdivision lassen sich in dem durch den Satz beschriebenen Fall sukzessive sämtliche Nullstellen von f iterativ bestimmen.

Ersetzt man den in obiger Formel auftretenden Differentialquotienten f′(x_k) durch den Differenzenquotienten \begin{eqnarray}\displaystyle\frac{f({x}_{k})-f({x}_{k-1})}{{x}_{k}-{x}_{k-1}},\,\,k\in {\mathbb{N}},\end{eqnarray} so erhält man das sogenannte Sekantenverfahren. Dieses ist durch die Iterationsvorschrift der Regula falsi, \begin{eqnarray}{x}_{k+1}=\displaystyle\frac{{x}_{k-1}f({x}_{k})-{x}_{k}f({x}_{k-1})}{f({x}_{k})-f({x}_{k-1})},\,\,k\in {\mathbb{N}},\end{eqnarray} festgelegt. Der wesentliche Vorteil des Sekantenverfahrens ist es, daß man für dieses f′ nicht explizit kennen muß. Andererseits konvergiert es i. allg. nicht quadratisch, sondern es gilt lediglich \begin{eqnarray}|\bar{x}-{x}_{k+1}|\le C{|\bar{x}-{x}_{k}|}^{1.618},\,\,k\in {\mathbb{N}}.\end{eqnarray}

Eine geradlinige Verallgemeinerung des bisher gesagten ist für mehrdimensionale Abbildungen möglich. Ist f : ℝⁿ → ℝⁿ differenzierbar, so definiert man die Newtonabbildung N_f : ℝⁿ → ℝⁿ zu f durch \begin{eqnarray}{N}_{f}(x):=x-{(Df(x))}^{-1}\cdot f(x),\end{eqnarray} sofern die Jacobi-Matrix Df(x) invertierbar ist. Eine Folge von Newtoniterierten wird analog zur eindimensionalen Situation erzeugt, und dieselben Fragen sind von fundamentaler Bedeutung. Entsprechend läßt sich das Newtonverfahren auf allgemeineren Räumen definieren.

Es ist unmittelbar einsichtig, daß das Newtonverfahren auch eine wesentliche Rolle bei der Suche nach Extremalpunkten spielt; die Mehrzahl der bekannten notwendigen und hinreichenden Optimalitätskriterien differenzierbarer Probleme lassen sich in Form von Gleichungssystemen und damit letztlich als Nullstellenprobleme beschreiben. Zahlreiche Verfahren benutzen dabei Varianten der Methode von Newton, so z. B. das DFP-Verfahren, das BFGS-Verfahren, viele innere-Punkte-Methoden, das Lagrange-Newton-Verfahren, Homotopieverfahren etc.

Eine Verallgemeinerung für die Situation, wenn die Matrix Df(x) nicht invertierbar ist, liefern Verfahren, die dem obigen Zugang ähneln, aber statt Inversen Pseudo-Inverse verwenden.

[1] Hämmerlin, G.; Hoffmann K.-H.: Numerische Mathematik. Springer-Verlag Heidelberg/Berlin, 1991.
[2] Meinardus, G.; Merz G.: Praktische Mathematik I, II. BI-Wissenschaftsverlag Mannheim, 1979/1982.
[3] Stoer, J.: Einführung in die Numerische Mathematik I. Springer-Verlag Heidelberg/Berlin, 1972.