<<

. 20
( 31 .)



>>

1.0981595 — 10’5
x = x13 = .
9.10614
Die Matrix
9.1 — 104 0.11
f (x) =
’1.1 — 10’4
’1
hat die Kondition
· (f (x))’1 = O(109 ).
f (x) ∞ ∞

Bei der Berechnung von f2 (x) entsteht Ausl¨sung; f2 (x) l¨ßt sich in folgender
o a
Gestalt besser berechnen:
e’x1 + e’x2 ’ 1.0001 = (e’x1 ’ 1) + (e’x2 ’ 10’4 )
≈ (’x1 + (x1 )2 /2) + (e’x2 ’ 10’4 ).
86 Nichtlineare Gleichungen und Gleichungssysteme




4.5.3 Newton“Kantorovich
Zum Nachweis der lokalen quadratischen Konvergenz des Newton-Verfahrens (4.11)
ben¨tigen wir den folgenden Hilfssatz:
o
Hilfssatz 4.31. Sei D0 ‚ D konvex. Es gebe γ > 0 mit

f (x) ’ f (y) ¤ γ x ’ y fur x, y ∈ D0 .
¨

Dann gilt
γ 2
f (x) ’ f (y) ’ f (y)(x ’ y) ¤ x’y ∀ x, y ∈ D0
2
Beweis: De¬niere die di¬erenzierbare Funktion • : [0, 1] ’ IRn durch

•(t) := f (y + t(x ’ y)), x, y ∈ D0 ,
f (y + t(x ’ y))(x ’ y) ∈ IRn .
• (t) =

Mit der Voraussetzung folgt
• (t) ’ • (0) = (f (y + t(x ’ y)) ’ f (y))(x ’ y)
¤ γt x ’ y x’y .

Es ist
:= f (x) ’ f (y) ’ f (y)(x ’ y)
1
= •(1) ’ •(0) ’ • (0) = (• (t) ’ • (0))dt,
0
1
’ ¤ (• (t) ’ • (0) dt
0
1
γ
2
x ’ y 2.
¤γ x’y t dt = 2
0




Satz 4.32 (Newton-Kantorovich). Es sei eine o¬ene Menge D ⊆ IRn gegeben,
ferner eine konvexe Menge D0 mit D0 ⊆ D und f : D ’ IRn sei eine fur alle
¨
x ∈ D0 di¬erenzierbare und fur alle x ∈ D stetige Funktion.
¨
0
Fur ein x ∈ D0 gebe es positive Konstanten r, ±, β, γ, h mit:
¨
Sr (x0 ) := {x | x ’ x0 < r} ⊆ D0 ,
h := ±βγ/2 < 1,
r := ±/(1 ’ h).

f (x) habe die Eigenschaften
Das Newton“Verfahren im IRn 87




(a) f (x) ’ f (y) ¤ γ x ’ y fur alle x, y ∈ D0
¨
(Lipschitz-Bedingung fur f ),
¨

(b) f (x)’1 existiert und es gilt
(f (x))’1 ¤ β fur alle x ∈ D0 ,
¨

(c) (f (x0 ))’1 f (x0 ) ¤ ±.
Dann gilt
(i) ausgehend von x0 ist jedes

xk+1 = xk ’ (f (xk ))’1 f (xk ), k≥0

wohlde¬niert und es gilt xk ∈ Sr (x0 ) fur alle k ≥ 0.
¨

(ii) x = lim xk existiert und es gilt
k’∞

x ∈ Sr (x0 ) und f (x) = 0.

2k ’1
h
(iii) x ’ xk ¤ ± 1’h2 k fur alle k ≥ 0.
¨
Wegen 0 < h < 1 ist also das Newton-Verfahren mindestens quadratisch konver-
gent.
Beweis: zu (i):
Zunachst wird xk ∈ Sr (x0 ), k ≥ 0 induktiv gezeigt. Fur k = 1 ist
¨ ¨
±
x1 = x0 ’ f (x0 )’1 f (x0 ) ’ x1 ’ x0 ¤ ± < =r
1’h
Seien x0 , . . . , xk ∈ Sr (x0 ) :

xk+1 ’ xk ’ f (xk )’1 f (xk ) ¤ β f (xk )
=
= β f (xk ) ’f (xk’1 ) ’ f (xk’1 )(xk ’ xk’1 )
=0 nach Def.
1 k k’1 2
¤ β γ x ’x nach Hilfssatz 4.31
2

Hiermit zeigen wir nun induktiv
k ’1
xk+1 ’ xk ¤ ±h2
(4.12) .

Fur k = 0 ist dies bereits gezeigt (s.o.). Ist die Absch¨tzung fur k ≥ 0 richtig, so
a
¨ ¨
1
(wegen h = 2 ±βγ) auch fur k + 1, denn
¨
βγ k βγ 2 2k ’2 k
xk+1 ’ xk ¤ x ’ xk’1 2
= ±h2 ’1 .
¤ ±h
2 2
88 Nichtlineare Gleichungen und Gleichungssysteme




Nun folgt mit (4.12)
xk+1 ’ x0 xk+1 ’ xk + xk ’ xk’1 + . . . + x1 ’ x0
¤
k ’1
¤ ±(1 + h + h3 + h7 + . . . + h2 ) < ±/(1 ’ h) = r
und daher xk+1 ∈ Sr (x0 ).
Zu (ii) und (iii):
{xk } ist eine Cauchy-Folge, denn fur m ≥ n hat man nach (4.12)
¨
xm+1 ’ xn xm+1 ’ xm + xm ’ xm’1 + . . . + xn+1 ’ xn
¤
n ’1 n n
¤ ±h2 (1 + h2 + (h2 )2 + . . .)
n
±h2 ’1
< <µ
1’h2n

fur genugend großes n ≥ N (µ), da 0 < h < 1. Also existiert
¨ ¨
lim xk =: x ∈ Sr (x0 ),
k’∞

und fur m ’ ∞ ergibt sich die Absch¨tzung (iii). Zu zeigen ist noch f (x) = 0 :
a
¨
Mit der Dreiecksungleichung und x ’ y ¤ r folgt aus (a) fur K := γr + f (x0 )
¨
f (xk ) = f (xk )(xk+1 ’ xk ) ¤ K xk+1 ’ xk ’ 0 fur k ’ ∞
¨
’ f (x) = 0, da f stetig in x ∈ D ist.



Bemerkung 4.33. Sei x eine isolierte Nullstelle von f, so dass die Vor. (a),(b)
in einer Umgebung D0 von x erfullt sind. Fur x0 in einer genugend kleinen Um-
¨ ¨ ¨
gebung E (Einzugsbereich) von x ist dann ± in Vor. (c) hinreichend klein, so dass
die Vor. von Satz 4.32 erfullt sind. Dann konvergiert {xk } quadratisch gegen x
¨
0
fur x ∈ E.
¨
Bemerkung 4.34. Fur eine C 2 -Funktion f ist die Lipschitz-Bedingung in Vor.
¨
(a) erfullt.
¨

4.5.4 Erweiterungen
4.5.4.1 Approximation von f (x) durch Di¬erenzen
Die Berechnung von f (x) kann sehr zeitraubend bzw. explizit nicht moglich sein.
¨
k
Man kann f (x ) z.B. numerisch approximieren, indem man f (x) in der N¨he von
a
k
x geeignet auswertet.
fi (xk + hej ) ’ fi (xk )
‚fi (x)
≈ , h > 0 klein
‚xj h
x=xk
Das Newton“Verfahren im IRn 89




Bemerkung 4.35. Diese Methode erfordert n Berechnungen von f fur jeden
¨
Schritt des Newton-Verfahrens und dies ist fur n groß ungunstig.
¨ ¨

4.5.4.2 »-Strategie, Modi¬ziertes Newton-Verfahren
Durch Einfuhrung eines konvergenzerzeugenden Faktors 0 < » ¤ 1 kann der
¨
Einzugsbereich des Newton“Verfahrens vergr¨ßert werden. Sei
o

dk = f (xk )’1 f (xk ) ∈ IRn .

Gewohnliches Newton-Verfahren:
¨

xk+1 = xk ’ dk .

Modi¬ziertes Newton-Verfahren:

xk+1 = xk ’ »k dk
(4.13) 0 < »k ¤ 1

Zur Bestimmung der konvergenzerzeugenden Faktoren »k vergleiche man STOER,
§5.4.
90 Nichtlineare Gleichungen und Gleichungssysteme
Kapitel 5

Interpolation

5.1 Einfuhrung und Aufgabenstellung
¨
Hau¬g tritt die Situation auf, daß statt einer Funktion nur einige diskrete Daten
¨
(xj , fj ), j = 0, . . . , n gegeben sind (z.B. Messwerte eines Experimentes). Histo-
risch trat das Problem bei der Berechnung von zus¨tzlichen Funktionswerten
a
zwischen tabellierten Werten auf (z.B. fur sin, cos, log). Heute ist es ein hau¬g
¨ ¨
auftretendes Problem sowohl in der Mathematik als auch in vielen Anwendungen.
Gesucht ist eine Funktion ¦ : IR ’ IR, fur die die Gleichungen
¨
(5.1) ¦(xj ) = fj , j = 0, . . . , n

gelten. Sind z.B. fj = f (xj ) Messdaten einer unbekannten Funktion f , so soll
¦ m¨glichst nahe an f liegen. Zudem soll ¦ leicht auswertbar sein. Ohne Ein-
o
schr¨nkung verlangen wir x0 < x1 < . . . < xn .
a
Beispiel 5.1. (Lineare Interpolationsprobleme)
• Interpolation durch Polynome
n
aj xj ,
¦(x) =
j=0

<<

. 20
( 31 .)



>>