Fehlerabschätzung für das Newton-Verfahren
Mit Hilfe des Satzes von Taylor können wir die hohe Konvergenzgeschwindigkeit des Newton-Verfahrens nachweisen:
Satz (Fehlerabschätzung für das Newton-Verfahren)
Sei f : [ p, x0 ] → ℝ zweimal stetig differenzierbar und konvex mit f (p) = 0, f (x0) > 0 und amin = f ′(p) > 0. Dann gilt für die monoton fallend gegen p konvergierende Newton-Iteration (xn)n ∈ ℕ für den Startpunkt x0:
xn − xn + 1 ≤ xn − p ≤ cmax2 amin (xn − 1 − xn)2 für alle n ≥ 1,
wobei cmax = maxx ∈ [ p, x0 ] f ″(x).
Beweis
Sei n ≥ 1. Die erste Ungleichung folgt aus p ≤ xn + 1 ≤ xn. Die zweite Ungleichung ist klar für xn = p. Sei also p < xn (und damit auch xn < xn − 1). Aufgrund der Konvexität von f ist f ′ monoton steigend, also ist
amin = minx ∈ [ p, x0 ] f ′(x).
Damit ist amin (x − p) ≤ f (x) für alle x ∈ [ p, x0 ], speziell gilt also
xn − p ≤ f (xn)amin.
Es genügt also zu zeigen:
(+) f (xn) ≤ cmax2 (xn − 1 − xn)2.
Beweis von (+)
Nach dem Satz von Taylor für f und den Entwicklungspunkt xn − 1 existiert ein ξ zwischen xn und xn − 1 mit
f (xn) = f(xn − 1) + f ′(xn − 1) (xn − xn − 1) + f ″(ξ)2 (xn − xn − 1)2.
Nach der Rekursionsgleichung der Newton-Iteration gilt aber
xn = xn − 1 − f (xn − 1)f ′(xn − 1),
und damit ist
f (xn) = 0 + f ″(ξ)2 (xn − xn − 1)2 ≤ cmax2 (xn − 1 − xn)2.
Um ein Gefühl für die quadratische Konvergenzgeschwindigkeit des Verfahrens zu bekommen, nehmen wir an, dass
cmax ≤ 2 amin,
und dass wir die Rekursion soweit durchgeführt haben, dass xn − 1 − xn < 1/10. Dann gilt nach der zweiten Ungleichung
xn − p ≤ 1 · (xn − 1 − xn)2 ≤ 1102 = 1100.
Nach der ersten Ungleichung gilt xn − xn + 1 ≤ xn − p, sodass xn − xn + 1 < 1/100. Mit der Argumentation wie eben folgt, dass
xn + 1 − p ≤ 1(100)2 = 1104.
Im nächsten Schritt erhalten wir xn + 2 − p < 1/108 usw.