Newton-Verfahren

Konvergenzbetrachtungen

Lokale quadratische Konvergenz

Sei f eine zweimal stetig differenzierbare reelle Funktion und a eine Nullstelle von f, in welcher die Ableitung keine Nullstelle hat. Das bedeutet, dass der Graph der Funktion transversal, d. h. nicht-berührend, die x-Achse schneidet. Sei x ein Punkt nahe bei a. Dann kann die Taylor-Formel zweiten Grades (mit Restglied)

liegt zwischen x und a,

nach der Differenz (x-a) umgestellt werden,

.

Es wird nun so umgestellt, dass der Newton-Operator auf der rechten Seite erscheint,

.

Seien I ein Intervall um a ohne Nullstelle der Ableitung f'(x) und sowie Schranken der Ableitungen von f. Dann folgt für alle dieAbschätzung

.

Mit sei der konstante Faktor bezeichnet. In jedem Schritt n der Newtoniteration wird die Größe d_n = K | x_n - a | kleiner sein als das Quadrat derselben Größe im vorhergehenden Schritt, . Nach vollständiger Induktion ergibt sich

.

Kann also für den Startpunkt der Iteration die Abschätzung garantiert werden, z. B. indem die Intervallänge von I kleiner als 1/K ist, so konvergiert die Folge (x_n ) der Newton-Iteration gegen die Nullstelle a, denn die Folge und damit ist nach der angegebenen Abschätzung eine Nullfolge. Die Verkürzung des Intervalls kann durch einige Iterationen eines langsameren Verfahrens zur Nullstelleneinschränkung erreicht werden, z. B. des Bisektionsverfahrens oder der Regula falsi.

Die aus dieser Abschätzungen folgende Konvergenzgeschwindigkeit wird als quadratisch bezeichnet, die (logarithmische) Genauigkeit bzw. Anzahl gültiger Stellen verdoppelt sich in jedem Schritt. Die Abschätzung des Abstands | x_n - a | zur Nullstelle wird oft linear in | x₀ - a | angegeben, so gilt z. B.

• , falls die Länge des Intervalls I kleiner als ist. Dies ergibt eine Abschätzung der gültigen Stellen im Binärsystem.
• , falls die Länge des Intervalls I kleiner als ist, d. h. nahe genug an der Nullstelle ergibt sich eine Verdopplung der gültigen Dezimalstellen in jedem Schritt.

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