<<

. 17
( 31 .)



>>


2. Existieren Konstanten c > 0 und p > 1, so daß

xk+1 ’ x—
(4.6) ¤ c, ∀ k = 0, 1, 2, . . .
xk ’ x— p

gilt, so heißt {xk } konvergent von Grade p. Das zugeh¨rige Iterationsver-
o
fahren wird konvergent von der Ordnung p genannt. Im Sonderfall p = 2
spricht man auch von quadratischer Konvergenz.

Bemerkung 4.4. Aus der aus (4.6) hergeleiteten Schreibweise

xk+1 ’ x— ¤ c xk ’ x— p , ∀ k = 0, 1, 2, . . .
72 Nichtlineare Gleichungen und Gleichungssysteme




ergibt sich fur den Fehler ek := xk ’ x— die Beziehung
¨

ek+1 ¤ cep ,
k

d.h. es ist
ek+1 = O(ep ).
k

Dies verdeutlich nochmals den Begri¬ der Ordnung eines Verfahrens.

Bemerkung 4.5. Im Sonderfall p = 1 (lineare Konvergenz) erh¨lt man aus (4.4)
a
die Absch¨tzung
a

ek+m ¤ cm ek ,
(4.7) m > 0.

{xk } mit einem unteren Index k bezeichnet.

Beispiel 4.6. Fur 0 < q < 1 sei xk der Abschnitt der geometrischen Reihe
¨
k
qi ,
xk =
i=0
1

mit x = lim xk = ,
1’q
k’∞
lim ek+1 = q
k’∞ ek

’ p = 1 : lineare Konvergenz.


4.3 Nichtlineare Gleichungen
In diesem Abschnitt betrachten wir den Sonderfall D = IR.
Hinweis: Zur Vermeidung von Mißverst¨ndnissen werden reelle Folgen {xk } mit
a
einem unteren Index k bezeichnet.

4.3.1 Bisektionsverfahren
Wir suchen eine Nullstelle x— ∈ IR einer reellen stetigen Funktion f : IR ’
IR, f (x— ) = 0. Das Bisektionsverfahren wird auch Intervallhalbierungsverfahren
genannt. Der Name wird sofort aus dem Algorithmus ersichtlich.

Algorithmus 4.7. (Bisektionsverfahren) Gegeben sei eine stetige Funktion
f : IR ’ IR und Werte a < b mit f (a) · f (b) < 0 (d.h. f (a) und f (b) haben unter-
schiedliches Vorzeichen und damit existiert eine Nullstelle von f (x) im Intervall
(a, b)). Die gewunschte Genauigkeit sei durch ein µ > 0 gegeben.
¨

1. Setze k = 0 (Z¨hlindex) und a0 = a, b0 = b.
a
Nichtlineare Gleichungen 73




2. Setze xk = ak + (bk ’ ak )/2 (Intervallhalbierung).

3. Ist f (xk ) = 0 oder (bk ’ ak )/2 < µ beende den Algorithmus.

4. Ist f (xk )f (ak ) < 0, dann setze ak+1 = ak , bk+1 = xk .
Ist f (xk )f (ak ) > 0, dann setze ak+1 = xk , bk+1 = bk .
Setze k = k + 1 und gehe zu Schritt 2.
Man kann die Punkte ak und bk als Intervallgrenzen der Intervalle [ak , bk ] ver-
stehen, mit denen die Nullstelle durch immer weitere Halbierung eingeschachtelt
wird. Daher stammt der Name Bisektion (=Zweiteilung).
Die Auswahlbedingung der neuen Werte ak+1 und bk+1 stellt sicher, daß f (ak+1 )
und f (bk+1 ) unterschiedliches Vorzeichen haben, daher muß sich immer eine Null-
stelle zwischen den Werten be¬nden (daher auch die Voraussetzung der Stetig-
keit).
Vorteilig beim Bisektionsverfahren ist:
• Es funktioniert fur allgemeine stetige Funktionen.
¨
• Es liefert immer ein Ergebnis (globale Konvergenz), wenn man geeignete
Startwerte ¬nden kann.

• Die Anzahl der Schritte bis zur gewunschten Genauigkeit h¨ngt nur von a
a
¨
und b ab, aber nicht von f .
Leider konvergiert das Verfahren (vgl. auch Beispiel) nur sehr langsam und wird
daher in der Praxis so gut wie nie eingesetzt.
Bemerkung 4.8. Wegen
1
|bk+1 ’ ak+1 | ¤ |bk ’ ak |
2
folgt aus (4.7) lineare Konvergenz.
Beispiel 4.9. Fur f (x) = x’tan(x), berechnet man mit dem Bisektionsverfahren
¨
eine Nullstelle von f :
a = 2, b = 4.6
f (a) ≈ 4.18, f (b) ≈ ’4.26

Damit
f (x5 ) = 2.87 · 10’1
x5 = 4.47812 ,
f (x20 ) = ’1.51 · 10’5
x20 = 4.493410 ,
x— = x100 = 4.49340946 , f (x100 ) = ’1.72294616 · 10’10 .
74 Nichtlineare Gleichungen und Gleichungssysteme




4.3.2 Newton“Verfahren
Wir betrachten ein weiteres Verfahren zur Nullstellenbestimmung einer gegebe-
nen Funktion f . Im Gegensatz zum Bisektionsverfahren ben¨tigen wir nicht nur
o
die Funktion f sondern auch ihre erste Ableitung.


y
f(x) T(x)

(xk ,f( xk))



xk x
xk+1
x*

Abbildung 4.2: Zur Motivation des Newton“Verfahrens.

Sei xk eine N¨herung fur x— . Im Punkt (xk , f (xk )) wird eine Tangente
a ¨

T (x) = f (xk ) + f (xk )(x ’ xk )

an die Kurve y = f (x) konstruiert und xk+1 als Nullstelle von T gewahlt. Also
¨

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

Eine Losung existiert nur fur f (xk ) = 0. (Was bedeutet das anschaulich?)
¨ ¨

Algorithmus 4.10. (Newton“Verfahren) Gegeben sei eine Funktion f : IR ’
IR, ihre Ableitung f , ein Anfangswert x0 und eine gewunscht Genauigkeit µ > 0.
¨
f (xk )
1. Berechne xk+1 = xk ’ .
f (xk )

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

Bemerkung 4.11. Das Newton“Verfahren ist eine Fixpunktiteration.

Satz 4.12 (Konvergenz des Newton“Verfahrens). Ist f zwei mal stetig dif-
ferenzierbar, f (x) = 0 und x0 hinreichend nahe bei x— , dann konvergiert das
Newton“Verfahren quadratisch.

Beweis: Spater.
¨
Nichtlineare Gleichungen 75




Beispiel 4.13. Es sei f (x) = x2 ’2 (d.h. Berechnung von x— = 2 ≈ 1.414213562373)
mit f (x) = 2x. Die Iterationsvorschrift des Newton“Verfahrens ergibt hier

x2 ’ 2 1 1
= xk ’ k
xk+1 = xk +
2xk 2 xk
Wir starten mit x0 = 1 und erhalten

k xk Anzahl korrekter Dezimalstellen
0 1.0 1
1 1.5 1
2 1.417 3
3 1.414216 6
4 1.414213562 10

Die schnelle Konvergenz belegt das theoretische Resultat einer quadratischen Kon-
vergenz.

Anmerkung: Newton hatte bereits 1669 ein Verfahren zur Berechnung einer Wur-
zel einer kubischen Gleichung entwickelt, das auf einen iterativen Linearisierungs-
prozeß hinausl¨uft. Er ver¨¬entlichte sein Verfahren als Mittel zur L¨sung der
a o o
Keplerschen Gleichung:

E = e · sin(E) + t
U
zur Bahnbestimmung von Planeten. Gesucht ist die ™exzentrische Anomalie™ E bei
einer Umlaufzeit U , einer Zeit (in Tagen) t seit dem Periheldurchgang und einer
numerischen Exzentrizit¨t e der Bahnellipse. Joseph Raphson brachte um 1690
a
¨
die Newtonschen Uberlegungen fur Polynome auf eine Form, die der heutigen
¨
Darstellung n¨her kommt. Man spricht deshalb h¨u¬g vom Newton“Raphson“
a a
Verfahren.
Es ist unmittelbar einzusehen, daß das Newton“Verfahren nicht immer konver-
giert (vgl. Abbildung 4.3).

Bemerkung 4.14. Wesentlicher Nachteil des Newton“Verfahrens ist die Abh¨ngig-
a
keit von der Ableitung. Die Ableitung kann zwar auch numerisch berechnet wer-
den, ist dann jedoch h¨u¬g anf¨llig gegenuber Rundungsfehlern.
a a ¨


4.3.3 Sekanten“Verfahren
Zur Vermeidung von Ableitungen betrachten wir das Sekanten“Verfahren, hier
ergibt sich die neue N¨herung xk+1 nicht nur aus xk sondern auch aus xk’1 .
a
76 Nichtlineare Gleichungen und Gleichungssysteme




y=f(x)




x0 =x =x x x x1=x=x x
3 2k+1
2 2k




Abbildung 4.3: Keine Konvergenz beim Newton“Verfahren.

y
f(x)




xk’1
x* xk+1 xk x

Abbildung 4.4: Zur Motivation des Sekanten“Verfahrens.

<<

. 17
( 31 .)



>>