<<

. 18
( 31 .)



>>


Die Sekantenmethode ist eine Vereinfachung des Newton“Verfahrens, wobei die
Tangente durch die Sekante der letzten beiden Punkte ersetzt wird. Die Steigung
der Sekante ergibt sich zu

f (xk ) ’ f (xk’1 )
(4.8) ≈ f (xk ).
xk ’ xk’1

Fur das Sekanten“Verfahren wird f (xk ) einfach durch (4.8) ersetzt.
¨

Algorithmus 4.15. (Sekanten“Verfahren) Gegeben sei eine Funktion f :
IR ’ IR, Anfangswerte x0 , x1 und eine gewunscht Genauigkeit µ > 0. Setze
¨
k = 1.
f (xk )(xk ’xk’1 )
1. Berechne xk+1 = xk ’ .
f (xk )’f (xk’1 )


2. Ist |xk+1 ’ xk | < µ, beende den Algorithmus,
sonst setze k = k + 1 gehe zu 1.

Bemerkung 4.16. Das Sekanten“Verfahren ist eine Fixpunktiteration.

Satz 4.17 (Konvergenz des Sekanten“Verfahrens). Ist f zwei mal stetig
di¬erenzierbar, f (x— ) = 0 und x0 , x1 hinreichend nahe bei x— , dann konvergiert

das Sekanten“Verfahren mit der Ordnung p = 1 (1 + 5) = 1.618 . . ..
2
Konvergenzs¨tze
a 77




Beweis: Spater.
¨

Beispiel 4.18. Wir betrachten erneut f (x) = x2 ’ 2. Die Iterationsvorschrift des
Sekanten“Verfahrens ergibt hier
x2 ’ 2
k
xk+1 = xk ’
xk + xk’1
Wir starten mit x0 = 1, x1 = 2 und erhalten
k xk Anzahl korrekter Dezimalstellen
0 1.0 1
1 2.0 0
2 1.3 1
3 1.43 2
4 1.414 4
5 1.414211 6
6 1.4142135627 10
Das Sekanten“Verfahren startet zwar in diesem Beispiel recht langsam aufgrund
der schlechten Startsch¨tzung fur x1 , konvergiert aber sp¨ter entsprechend schnell.
a a
¨


4.4 Konvergenz von Iterationsverfahren
4.4.1 Kontraktion
Sei D ‚ IRn und g : D ’ IRn . Wir untersuchen die Frage, wann die Fixpunktite-
ration
xk+1 = g(xk ), x0 ∈ D gegeben,
(4.9) k ≥ 0,
wohl de¬niert ist und gegen einen Fixpunkt x ∈ D, konvergiert.
De¬nition 4.19. Die Abbildung g : D ’ IRn heißt kontrahierend in D, falls es
eine Zahl 0 ¤ q < 1 gibt mit
g(x) ’ g(y) ¤ q x ’ y ∀x, y ∈ D.
Fur di¬erenzierbare Abbildungen g kann ein einfaches Kriterium fur die Kontrak-
¨ ¨
tion mit der Ableitung
« ‚g1 ‚g1 
. . . ‚xn
‚x1
¬. .·
g (x) = ¬ . .·
. .
‚gn ‚g
. . . ‚xn
‚x1 n
78 Nichtlineare Gleichungen und Gleichungssysteme




gegeben werden. D heißt konvex, wenn fur x, y ∈ D gilt
¨

±x + (1 ’ ±)y ∈ D ∀± ∈ [0, 1].




D
y

x



Abbildung 4.5: Konvexes Gebiet.

Satz 4.20. Sei D konvex, g : D ’ IRn di¬erenzierbar und sei

sup g (x) ¤ q < 1.

x∈D

Dann ist g kontrahierend in D.
Beweis: Fur zwei beliebige Punkte x, y ∈ D betrachten wir • : [0, 1] ’ IRn :
¨
•(») := g(»x + (1 ’ »)y), » ∈ [0, 1],
•(1) = g(x), •(0) = g(y),
• (») = g (»x + (1 ’ »)y)(x ’ y).

Aus dem Mittelwertsatz folgt:

| •i (1) ’ •i (0)| ¤ max | •i (») | , i = 1, . . . , n.
0¤»¤1

’ g(x) ’ g(y) = •(1) ’ •(0)
∞ ∞

¤ max • (») ∞
0¤»¤1
= max g (»x + (1 ’ »)y)(x ’ y) ∞
0¤»¤1
¤ sup g (z) x’y ∞.

z∈D


Fur n = 1 ist D = [a, b] konvex und g ∈ C 1 [a, b] kontrahierend, falls
¨

max |g (x)| = q < 1.
a¤x¤b

(Vgl. Graphik zum Fixpunkt).
Konvergenzs¨tze
a 79




4.4.2 Fixpunktsatz von Banach
Satz 4.21 (Fixpunktsatz von Banach). Sei D abgeschlossen und g : D ’ IRn
kontrahierend in D mit g(D) ⊆ D. Dann konvergiert die Folge

xk+1 = g(xk ), k = 0, 1, 2, . . . , x0 ∈ D beliebig,

gegen den eindeutig bestimmten Fixpunkt x von g in D und es gilt:
qk
q
(i) x ’ xk ¤ xk ’ xk’1 ¤ x1 ’ x0 ,
1’q 1’q

(ii) x ’ xk ¤ q x ’ xk’1 .

Beweis: Wir zeigen zun¨chst, dass {xk } eine Cauchy-Folge ist. Fur k ≥ 1 gilt
a ¨

xk+1 ’ xk = g(xk ) ’ g(xk’1 ) ¤ q xk ’ xk’1

¤ q 2 xk’1 ’ xk’2 ¤ q k x1 ’ x0
und damit fur j > l
¨
j’1 j’1
j l k+1 k
xk+1 ’ xk
x ’x = (x ’x ) ¤
k=l k=l
j’1
(4.10) q k x1 ’ x0
¤
k=l
1
q l 1’q x1 ’ x0 ’’ 0.
¤
l’∞


Die xk bilden damit eine Cauchy-Folge. Sei x ∈ D der Grenzwert der Folge xk .
Dann gilt
g(x) ←’ g(xk ) = xk+1 ’’ x,
k’∞ k’∞

’ g(x) = x.
In (4.10) ergibt der Grenzwert fur j ’ ∞ :
¨

ql
l
x1 ’ x0 .
x’x ¤
1’q

Mit l = 1 folgt hieraus nach Ersetzen x0 ’ xk’1
q
x ’ xk ¤ xk ’ xk’1 .
1’q

Damit ist (i) gezeigt; (ii) folgt aus der Kontraktionseigenschaft:

x ’ xk = g(x) ’ g(xk’1 ) ¤ q x ’ xk’1 .
80 Nichtlineare Gleichungen und Gleichungssysteme




Zu zeigen bleibt noch die Eindeutigkeit von x.
Seien x, x— Fixpunkte von g:
x ’ x— = g(x) ’ g(x— ) ¤ q x ’ x— , q < 1,
x ’ x— = 0.




Bemerkung 4.22. Wegen Teil (ii) konvergiert {xk } linear gegen x.
Bemerkung 4.23. Die Schwierigkeiten bei der Anwendung des Kontraktionssat-
zes auf ein konkretes Problem bestehen darin:
(a) man ¬nde eine zugeh¨rige kontrahierende Funktion g : D ’ IRn ,
o

(b) man prufe g(D) ⊆ D.
¨
Beispiel 4.24. Gesucht ist die L¨sung x der Gleichung
o
x = e’x =: g(x), x ∈ IR.
Auf das Intervall D = [0.5, 0.69] tri¬t die Voraussetzung g(D) ‚ D zu. Als
Kontraktionszahl q dient nach Satz 4.20 die Zahl
max |g (x)| = e’0.5 = 0.606531 < 1.
x∈D

Zum Startwert x(0) = 0.55 ∈ D berechnet man die Iterierten:

x(k) x(k) x(k)
k k k
0 0.55000000 10 0.56708394 20 0.56714309
1 0.57694981 11 0.56717695 21 0.56714340
2 0.56160877 12 0.56712420 22 0.56714323
3 0.57029086 13 0.56715412 23 0.56714332
4 0.56536097 14 0.56713715 24 0.56714327
kq
Mit der a priori Fehlerabsch¨tzung x ’ x(k) ¤ 1’q x(1) ’ x(0) kann die Anzahl
a
k der Iteration gesch¨tzt werden, die n¨tig sind, damit z. B. x’x(k) ¤ µ = 10’6
a o
gilt. Man erh¨lt
a
µ(1 ’ q)
k ≥ log / log q = 22.3,
x1 ’ x0
¨
eine gegenuber der Tabelle leichte Ubersch¨tzung. Fur den Wert x(12) erh¨lt man
a a
¨ ¨
die a posteriori Fehlerschranke
q
x ’ x(12) ¤ x(12) ’ x(11) = 8.3 · 10’5 .
1’q
Konvergenzs¨tze
a 81




<<

. 18
( 31 .)



>>