Kap. 32

144
IV. Taylor-Formel und Reihenentwicklungen
32
Das Newton-Verfahren
Mit Hilfe der Taylor-Formel entwickeln wir nun ein wichtiges Iterationsverfahren zur
Lösung (nichtlinearer) Gleichungen
f (x) = 0 .
(1)
32.1 Herleitung des Newton-Verfahrens. Es seien I ⊆ R ein offenes Intervall,
f ∈ C 1 (I, R) und xn eine Näherung für eine Lösung von (1). Zur Berechnung einer
besseren Näherung ersetzt man f durch sein Taylor-Polynom erster Ordnung in xn ,
d. h. man versucht
f (xn ) + f ′ (xn ) (x − xn ) = 0
(2)
zu lösen. Für f ′ (xn ) 6= 0 ist dies offenbar möglich; die Lösung
xn+1 := xn −
f (xn )
f ′ (xn )
(3)
wird dann als nächste Näherung verwendet. Geometrisch bedeutet dies, daß die
Funktion f durch ihre Tangente in xn ersetzt und deren Schnittpunkt mit der x Achse bestimmt wird.
√
32.2 Beispiel. Für a > 0 und 2 ≤ p ∈ N benutzt man zur Berechnung von p a
die Funktion f (x) := xp − a . Als Newton-Verfahren erhält man:
xn+1
1
xp − a
= xn − n p−1 =
p
p xn
(p − 1) xn +
a
xp−1
n
(4)
.
Der Fall p = 2 wurde in Satz 4.18 behandelt: Für beliebige Startwerte√
x0 > 0 ist die
Folge (xn )n∈N monoton fallend, und sie konvergiert quadratisch gegen a . Analoges
gilt auch für p > 2 .
1
wurde in Beispiel 5.2 b)
32.3 Beispiel. Für das Polynom P (x) = 15 x3 + 21 x2 − 10
mit dem Intervallhalbierungsverfahren die Näherung x7 = 0.41406 für eine Nullstelle
ermittelt. Das Newton-Verfahren liefert mit diesem Startwert dann
x8
x9
x10
x11
=
=
=
=
0, 4142135965
0, 4142135623730967
0, 4142135623730950488016887242138
0, 414213562373095048801688724209698078569671875 ,
und diese Ziffern sind bereits alle korrekt.
Allgemein gilt nun (vgl. [K1], 35.5):
32.4 Theorem (Newton-Verfahren). Es seien I ⊆ R ein Intervall, f ∈ C 2 (I, R) ,
und es gebe a ∈ I mit f (a) = 0 .
Es gelte M := sup | f ′′ (x) | < ∞ und m := inf | f ′(x) | > 0 . Für einen Startwert
x∈I
x∈I
x0 ∈ I und d := | x0 − a | gelte [a − d, a + d] ⊆ I und q :=
M
2m
d < 1.
32 Das Newton-Verfahren
145
a) Dann wird durch (3) rekursiv eine Folge (xn ) mit | xn − a | ≤ d definiert; für
n ∈ N0 gilt
xn+1 − a =
| xn+1 − a | ≤
R a ′′
1
xn f (t) (a
f ′ (xn )
M
| xn − a |2 .
2m
− t) dt ,
(5)
(6)
b) Die Folge (xn ) konvergiert quadratisch gegen a ;
a priori- und a posteriori-Abschätzungen
| xn − a | ≤
| xn − a | ≤
2m 2n
q , n ∈ N,
M
1
M
| f (xn ) | ≤ 2m
m
genauer gelten die
2
| xn − xn−1 | .
(7)
(8)
Formel (5) ergibt sich aus der Taylor-Formel 2. Ordnung mit Integral-Restglied.
32.5 Bemerkungen. a) In der Situation von Theorem 32.4 ist stets f ′ (x) 6= 0 .
Daher f ist streng monoton; somit hat f höchstens eine Nullstelle in I und diese ist
einfach. Die in Theorem 32.4 vorausgesetzte Existenz einer solchen Nullstelle a ∈ I
von f kann oft mit dem Zwischenwertsatz gezeigt werden.
b) Ist diese garantiert und f ′ (a) 6= 0 , so konvergiert das Newton-Verfahren quadratisch gegen a , wenn der Startwert x0 bereits nahe genug an a liegt. Einen solchen
Startwert kann man sich etwa mit dem Intervallhalbierungsverfahren (vgl. 5.2) verschaffen. Liegt x0 nicht nahe genug an a , so kann das Newton-Verfahren divergieren.
c) Theorem 32.4 gilt sinngemäß auch in C oder Rn . Das Hauptproblem ist meist
das Auffinden eines geeigneten Startwertes.
Für konvexe oder konkave Funktionen gilt:
32.6 Satz. Es sei f ∈ C 2 [a, b] mit f (a) · f (b) < 0 und f ′ (x) · f ′′ (x) 6= 0 für alle
x ∈ [a, b] . Für einen Startwert x0 ∈ [a, b] mit f (x0 ) · f ′′ (x0 ) > 0 konvergiert das
Newton-Verfahren (3) monoton gegen die eindeutig bestimmte Lösung ξ ∈ [a, b] der
Gleichung f (x) = 0 .
Beweis. Nach dem Zwischenwertsatz gibt es genau ein ξ ∈ [a, b] mit f (ξ) = 0 . Nun
sei f streng monoton wachsend und konvex. Dann liegen Tangenten stets unterhalb
des Graphen von f ; aus f (x0 ) > 0 folgt daher induktiv auch f (xn ) > 0 und
ξ ≤ xn+1 ≤ xn . Nach Satz 4.14 existiert η := lim xn , und mit n → ∞ in (3) folgt
n→∞
f (η) = 0 , also η = ξ .
Ab einem Index n0 gilt dann
M
2m
d < 1 , und man hat quadratische Konvergenz.
32.7 Beispiel. Die Funktion log ist konkav auf (0, ∞) mit Nullstelle ξ = 1 . Das
Newton-Verfahren
xn+1 := xn − xn log xn
konvergiert monoton für Startwerte 0 < x0 < 1 . Für x0 ≥ e jedoch ist x1 < 0 , und
das Verfahren bricht zusammen.
146
IV. Taylor-Formel und Reihenentwicklungen
32.8 Bemerkungen. a) Auch im Fall f ′ (a) = 0 hat man oft Konvergenz des
Newton-Verfahrens, allerdings keine quadratische.
b) Für f (x) = xp , p > 1 und x0 > 0 hat man
xn+1 := xn −
xpn
p xp−1
n
= (1 − 1p ) xn ,
also xn → 0 mit der linearen Konvergenzrate 1 − p1 .
c) Ist m die Ordnung der Nullstelle von f , so hat man für das Verfahren
xn+1 := xn − m ·
f (xn )
f ′ (xn )
(9)
quadratische Konvergenz. Allerdings ist m i. A. nicht bekannt.
32.9 Beispiele und Bemerkungen. a) Auch komplexe Nullstellen können mit
Hilfe des Newton-Verfahrens berechnet werden. Ist etwa P ∈ C[z] ein komplexes
Polynom mit deg P ≥ 1 , so konvergiert die Newton-Iteration
zn+1 := zn −
P (zn )
P ′ (zn )
(10)
gegen eine Nullstelle von P , falls der Startwert z0 nahe genug an einer solchen
gewählt wurde. Im Fall einfacher Nullstellen kann der Beweis wie der von Theorem
32.4 geführt werden; in der Tat gilt nach (8.12) eine Taylor-Formel
0 = P (a) = P (zn ) + P ′ (zn ) (a − zn ) +
P ′′ (zn )
2
(a − zn )2 + O(| a − zn |3 ) .
Man erhält dann wieder quadratische Konvergenz.
b) Für das Polynom P (z) := z 5 + z + 1 und den Startwert z0 = 1 + i erhält man
z1
z2
z3
z4
z5
=
=
=
=
=
0, 89
0, 87068
0, 87693
0, 8774393
0, 877438833123
+
+
+
+
+
i · 0, 84
i · 0, 75970
i · 0, 74478
i · 0, 74486159
i · 0, 744861766619 ,
und diese Ziffern sind bereits alle korrekt.

Download Report