<<

. 19
( 31 .)



>>

Beispiel 4.25. Erneut greifen wir das Beispiel f (x) = x ’ tan(x) auf.
Die Nullstelle x wird in D = [π, 3 π] gesucht. Die Funktion g(x) = tan x ist nicht
2
kontrahierend wegen
1
g (x) = ≥ 1.
cos2 x
Umformulierung:

x = tan x = tan(x ’ π) ” arctan x = x ’ π.

Setze nun
3
g(x) = π + arctan x, D = [π, π].
2
O¬enbar gilt g(D) ⊆ D und

1
q := max|g (x)| = ≈ 0.092 < 1.
1 + π2
x∈D


g ist also kontrahierend in D nach (4.20).
Fur x = 4.4934094 ist g (x) = 0.04719.
¨
|x’xk |
q
xk |xk
’ xk’1 | |x ’ xk |
k |x’xk’1 |
1’q
0 3.14159265 “ “ “
1 4.40421991 0.1351 0.0892 “
2 4.48911945 0.008918 0.0043 0.0672
3 4.49320683 0.0004280 0.0002 0.0481
4 4.4933999 “ “ 0.0472

4.4.3 Konvergenzs¨tze
a
Satz 4.26 (Lokaler Konvergenzsatz). Sei g : IRn ’’ IRn mit g(x) = x. Ist
g in einer Umgebung von x stetig di¬erenzierbar und g (x) ∞ < 1, dann gibt es
eine Umgebung D von x, so dass das Iterationsverfahren

xk+1 = g(xk ), x0 ∈ D

gegen x konvergiert.

Beweis: Sei D eine Kugel mit Radius r um x mit g (x) ¤ q < 1 fur x ∈ D.
¨

Fur x ∈ D gilt
¨

g(x) ’ x = g(x) ’ g(x) ¤q x’x ¤r
∞ ∞ ∞


’ g(x) ∈ D.
82 Nichtlineare Gleichungen und Gleichungssysteme




Damit ist g kontrahierend in D und es gilt g(D) ⊆ D. Mit dem Fixpunktsatz
4.21 folgt die Behauptung.

Als Anwendung erh¨lt man im Falle n = 1 einfache Kriterien dafur, dass die
a ¨
Fixpunkt-Iteration ein Verfahren p-ter Ordnung ist.
Satz 4.27. Sei g : IR ’ IR eine C p -Funktion mit p ∈ IN+ . Sei x ein Fixpunkt
von g mit
(a) |g (x)| < 1 fur p = 1,
¨
(b) g (i) (x) = 0 (i = 1, . . . , p ’ 1) fur p > 1.
¨
Dann gibt es ein Intervall
I = [x ’ δ, x + δ], δ > 0,
so dass fur alle x0 ∈ I die Iteration xk+1 = g(xk ), k = 0, 1, 2, . . . konvergent vom
¨
Grade p ist mit
|xk+1 ’ x| 1 (p)
lim = g (x).
p
k’∞ |xk ’ x| p!
Beweis: Aus den Vor. (a),(b) folgt insbesondere |g (x)| < 1. Der lokale Kon-
vergenzsatz 4.26 sichert dann die (mindestens) lineare Konvergenz der Folge
xk+1 = g(xk ) fur alle x0 ∈ I = [x ’ δ, x + δ], δ > 0 geeignet.
¨
Die Taylor-Entwicklung ergibt mit Vor. (b) und x = g(x) :
1 (p)
g (x)(xk ’ x)p + o(|xk ’ x|p ).
xk+1 = x +
p!
Hieraus folgt die Behauptung
|xk+1 ’ x| 1 (p)
lim p= g (x)
k’∞ |xk ’ x| p!



4.4.4 Konvergenz des Newton“Verfahrens
Als Anwendung betrachten wir das Newton-Verfahren
f (xk )
xk+1 = g(xk ) = xk ’ .
f (xk )
Ist f eine C 3 -Funktion, so ist g eine C 2 -Funktion.

1. Fall: x ist einfache Nullstelle von f, d.h. f (x) = 0 : man berechnet
f (x)f (x)
g (x) = , g (x) = 0,
f (x)2
f (x)
g (x) = .
f (x)
Das Newton“Verfahren im IRn 83




Also ist das Newton-Verfahren (mindestens) quadratisch konvergent mit der asym-
ptotischen Fehlerkonstanten
1 f (x)
c= .
2 f (x)
2. Fall: x sei m-fache Nullstelle von f, d.h. f (i) (x) = 0 fur i = 0, . . . , m ’ 1 :
¨

f (x) = (x ’ x)m f0 (x), f0 (x) = 0

1
’ g (x) = 1 ’ .
m
Fur m > 1 ist daher g (x) = 0 und das Newton-Verfahren ist nur linear konver-
¨
gent.
Fur das modi¬zierte Newton-Verfahren
¨
f (xk )
xk+1 = g(xk ) := xk ’ m
f (xk )

gilt jedoch g (x) = 0, also hat man quadratische Konvergenz.


Das Newton“Verfahren im IRn
4.5
4.5.1 Herleitung des Newton“Verfahrens
Gegeben sei eine C 1 -Funktion f : D ’ IRn . Gesucht ist eine Nullstelle x ∈ D von
f. Das Newton-Verfahren zur Berechnung von x ist die folgende Fixpunktiterati-
on:

xk+1 = xk ’ (f (xk ))’1 f (xk ), x0 ∈ D gegeben.
(4.11) k ≥ 0,

Das Newton-Verfahren im IRn laßt sich auf verschiedene Weise erkl¨ren:
a
¨

(1) Verallgemeinerung des Newton“Verfahrens mittels Taylor-Entwicklung:
Es gilt
0 = f (x) = f (xk ) + f (xk )(x ’ xk ) + o( x ’ xk ).
Vernachl¨ssigt man o( x’xk ) und ersetzt den unbekannten Punkt x durch
a
xk+1 , so erh¨lt man
a

0 = f (xk ) + f (xk )(xk+1 ’ xk )

und daraus (4.11).
84 Nichtlineare Gleichungen und Gleichungssysteme




(2) Anwendung des lokalen Konvergenzsatzes 4.26:
f (x) = 0 gilt genau dann, wenn x Fixpunkt von

g(x) := x + A(x)f (x)

ist mit einer geeignet zu wahlenden regularen (n, n) C 1 -Matrix A(x). Nach
¨ ¨
Satz 4.26 ist g kontrahierend, falls g (x) ∞ < 1 ist. Wegen f (x) = 0 gilt

g (x) = I + A(x)f (x).

Wahlen wir nun
¨
A(x) = ’(f (x))’1
so ist g (x) = 0. Da x unbekannt ist setzen wir

A(x) = ’(f (x))’1

d.h.
g(x) = x ’ (f (x))’1 f (x).
Die Fixpunktiteration xk+1 = g(xk ) ergibt gerade (4.11). Satz 4.26 sichert
wegen g (x) = 0 die lokale Konvergenz.

Beispiel 4.28. Gesucht ist die L¨sung des Systems
o

x2 + x2 ’ 1
f1 (x) 1 2
f (x) = = =0
f2 (x) x1

Die Ableitung f (x) ist gegeben durch

2x1 2x2
f (x) = ,
1 0

wodurch sich die Inverse zu

0 1
(f (x))’1 =
’ x2
1 1
2x2 x


ergibt. Die Iterationsvorschrift lautet somit

0 1 (xk )2 + (xk )2 ’ 1
1 2
k+1 k
x =x ’ .
xk
1
xk
’ x1 1
2xk k
2 2
Das Newton“Verfahren im IRn 85




Mit x0 = (1, 1) ergibt sich

k xk xk Max. Anzahl korrekter Dezimalstellen
1 2
01 1 0
10 1.5 1
20 1.08 2
30 1.003 3
40 1.000005 6

4.5.2 Praktische Realisierung
Bemerkung 4.29. Praktisch benutzt man in h¨heren Dimensionen das Newton-
o
Verfahren in der Form

f (xk )(xk+1 ’ xk ) = ’f (xk ).

So muß anstatt der Invertierung von f (xk ) (n3 Operation) nur noch ein LGS
1
gel¨st werden ( 3 n3 Operationen).
o

Beispiel 4.30. f : IR2 ’ IR2 ,

104 x1 x2 ’ 1 104 x2 104 x1
f (x) = , f (x) = .
e’x1 + e’x2 ’ 1.0001 ’e’x1 ’e’x2

0 ’1
0 0
x = , f (x ) = ,
1 0, 36

<<

. 19
( 31 .)



>>