Prof. Dr. Barbara Wohlmuth
Lehrstuhl fur Numerische Mathematik
Inhalt Kapitel I: Nichtlineare Gleichungssysteme
I Nichtlineare Gleichungssysteme
I.1 Nullstellenbestimmung von Funktionen einer Veranderlichen
I.2 Fixpunktiteration
I.3 Newton-Verfahren
Kapitel I (UebersichtKapI) 1
Prof. Dr. Barbara Wohlmuth
Lehrstuhl fur Numerische Mathematik
Bisektionsverfahren am Beispiel f = x2 − 1
0 1 2 3 4 5 6−5
0
5
10
15
20
25
30
35Bisektion
x2−1
Startwert: 0, 5
0 2 4 6 8 1010
−3
10−2
10−1
100
Bisektion
Anzahl der Iterationen
Feh
lers
chra
nke
Lineare Konvergenz
In jedem Schritt Halbierung der Intervalllange
Pro Schritt eine Funktionsauswertung
Kapitel I (nonlin05) 2
Prof. Dr. Barbara Wohlmuth
Lehrstuhl fur Numerische Mathematik
Regula falsi am Beispiel f = x2 − 1
0 1 2 3 4 5−5
0
5
10
15
20
25Regula falsi
x2−1
Startwert: 0, 5
0 5 10 15 20 2510
−4
10−3
10−2
10−1
100
101
Regula falsi
Anzahl der Iterationen
Feh
ler
Lineare Konvergenz
Reduktion der Intervalllange variabel
Pro Schritt eine Funktionsauswertung
Kapitel I (nonlin06) 3
Prof. Dr. Barbara Wohlmuth
Lehrstuhl fur Numerische Mathematik
Sekantenverfahren
0 1 2 3 4 5−5
0
5
10
15
20
25Sekantenverfahren
x2−1
Startwert: 0, 5
0 2 4 6 8 10 1210
−10
10−5
100
105
Sekantenverfahren
Anzahl der Iterationen
Feh
ler
Konvergenzordnung i.d.R. p = (1 +√5)/2
Pro Schritt eine Funktionsauswertung
Reduktion der Intervalllange variabel
Kapitel I (nonlin07) 4
Prof. Dr. Barbara Wohlmuth
Lehrstuhl fur Numerische Mathematik
Fixpunktiteration x =√x (Start x = 7)
0 1 2 3 4 5 6 70
0.5
1
1.5
2
2.5
3Fixpunktiteration
Wurzelfunktion
0 2 4 6 8 100.001
0.01
0.1
1
5
Fixpunktiteration
Anzahl der Iterationen
Feh
ler
Fixpunkt: Φ(x) =√x = x, Nullstelle: g(x) =
√x− x
Pro Schritt eine Funktionsauswertung, lin. Konvergenz Φ′(1) = 1
2
Kapitel I (nonlin02) 5
Prof. Dr. Barbara Wohlmuth
Lehrstuhl fur Numerische Mathematik
Fixpunktiteration: Kritischer Einfluss der Wahl von Φ
am Beispiel 2− x2 − ex = 0 (Start x0 = 0.4)
Konvergenz: Φ(x) = log(2− x2)
0.4 0.55 0.70.4
0.55
0.7Fixpunktiteration
log(2−x2)0 5 10 15 20
0.0001
0.001
0.01
0.1
0.5
Fixpunktiteration
Anzahl der Iterationen
Feh
ler
Keine Konvergenz: Φ(x) =√2− ex
−0.5 0 0.5 1−0.5
0
0.5
1
Fixpunktiteration
0 20 40 60 80 1000.1
0.2
0.5
1
4Fixpunktiteration
Anzahl der Iterationen
Iterie
rte
0 5 10 15 200.4
0.45
0.5
0.55
0.6
Fixpunktiteration
Anzahl der Iterationen
Feh
ler
Kapitel I (nonlin03) 6
Prof. Dr. Barbara Wohlmuth
Lehrstuhl fur Numerische Mathematik
Fixpunktiteration: Kritischer Einfluss des Startwerts
am Beispiel x2 = x,Φ(x) = x2
Divergenz
0 1 2 3 4 50
1
2
3
4
5Fixpunktiteration
x2: DivergenzStartwert: 1.01
0 5 10 15 2010
−100
100
10100
10200
10300
Anzahl der Iterationen
Iterie
rte
quad. Konvergenz gegen x = 0, (x = 1 instabil)
0 0.2 0.4 0.6 0.8 10
0.2
0.4
0.6
0.8
1Fixpunktiteration
x2: Konvergenz
Startwert: 0.99
0 5 10 1510
−40
10−30
10−20
10−10
100
Fixpunktiteration
Anzahl der Iterationen
Iterie
rte
Kapitel I (nonlin04) 7
Prof. Dr. Barbara Wohlmuth
Lehrstuhl fur Numerische Mathematik
Fixpunktiteration: Konvergenzgeschwindigkeit
in Abhangigkeit von Φ bzw. Φ′
Verschiedene Fixpunktiterationen
mit Fixpunkt x∗ = 1:
φ1(x) = x1/4, φ′1(x∗) =
1
4,
φ2(x) = x1/2, φ2′(x∗) =
1
2,
φ3(x) = x3/4, φ3′(x∗) =
3
4,
Startwert x0 = 2.20 40 60 80 100
10−15
10−10
10−5
100
Fehlerabnahme
φ1
φ2
φ3
⇒ Fur 0 < |φ′j(x∗)| = qj < 1 lokal lineare Konvergenz mit
‖φj(xk)− x∗‖ ≈ qj‖xk − x∗‖.
Kapitel I (nonlin24) 8
Prof. Dr. Barbara Wohlmuth
Lehrstuhl fur Numerische Mathematik
Wurzelberechnung mit dem Newton-Verfahren
Beispiel
Gesucht sei x∗ = n√a, a > 0, 2 ≤ n ∈ N.
Umformung ergibt xn∗ − a = 0.
Setze f(x) := xn − a.Anwendung des Newton-Verfahrens ergibt die Folge (xk) mit
xk+1 =1
n
(
(n− 1)xk + ax1−nk
)
.
Beispiel: Fur die Berechnung von 3√8 ergibt sich mit x0 = 2.9
k xk ek ek/e2
k−1
0 2.900000000000000 9.00e-01
1 2.250416171224733 2.50e-01 0.31
2 2.026831612491640 2.68e-02 0.43
3 2.000353634974019 3.54e-04 0.49
4 2.000000062514109 6.25e-08 0.50
5 2.000000000000002 1.78e-15 0.46
6 2.000000000000000 < eps
Kapitel I (nonlin08) 9
Prof. Dr. Barbara Wohlmuth
Lehrstuhl fur Numerische Mathematik
Wurzelberechnung mit dem Newton-Verfahren
Konvergenzbetrachtung
Das Newton-Verfahren ist lokal quadratisch konvergent, d.h.
∃ε > 0 : ‖xk+1 − x∗‖ ≤ ω
2‖xk − x∗‖2, ∀xk ∈ [x∗ − ε, x∗ + ε].
Beispiel
0 1 2 3 4 5
10−10
10−5
k
ek−12
ek
ek/e2k−1
konstant ⇒ quadratische Konvergenz
Kapitel I (nonlin09) 10
Prof. Dr. Barbara Wohlmuth
Lehrstuhl fur Numerische Mathematik
Wurzelberechnung 3√8 mit dem Newton-Verfahren
Iterationsverlauf abhangig vom Startwert
x0 = 5
2 3 4 50
50
100
150
x0 = −2
−2 0 2 4 6
0
50
100
150
Kapitel I (nonlin10) 11
Prof. Dr. Barbara Wohlmuth
Lehrstuhl fur Numerische Mathematik
Lokale Konvergenz beim Newtonverfahren
−3 −2 −1 0 1 2 3−1.5
−1
−0.5
0
0.5
1
1.5
Startwert: 1
−3 −2 −1 0 1 2 3−1.5
−1
−0.5
0
0.5
1
1.5
Startwert: 1.3
−3 −2 −1 0 1 2 3−1.5
−1
−0.5
0
0.5
1
1.5
Startwert: 1.39
−2 −1.5 −1 −0.5 0 0.5 1 1.5 2−1.5
−1
−0.5
0
0.5
1
1.5
Startwert: 1.391745
Sei s die kritische Schranke gegebendurch: 2s− (1 + s2)arctan(s) = 0.Oben: Konvergenz fur x0 ∈ (−s, s)Unten: Divergenz fur x0 6∈ (−s, s)
−2 −1.5 −1 −0.5 0 0.5 1 1.5 2−1.5
−1
−0.5
0
0.5
1
1.5
Startwert: 1.391745200270735
−5 0 5 10 15 20 25−2
−1.5
−1
−0.5
0
0.5
1
1.5
2
Startwert: 1.391746 0 5 10 15 20 2510
−20
10−10
100
Anzahl der Iterationen
abs.
Feh
ler
1.0
1.3 1.3917
1.35
1.391745
1.39
Kapitel I (nonlin14) 12
Prof. Dr. Barbara Wohlmuth
Lehrstuhl fur Numerische Mathematik
Newton-Verfahren: Berechnung von π/4Setze f(x) := tanx− 1.Anwendung des Newton-Verfahrens ergibt die Folge (xk) mit
xk+1 = xk −1
2sin 2xk + cos2 xk.
Beispiel: Mit x0 = 1.5
k xk ek ek/e2
k−1
0 1.500000000000000 7.15e-01
1 1.434443747669844 6.49e-01 1.27
2 1.318252032435956 5.33e-01 1.26
3 1.138743742375321 3.53e-01 1.24
4 0.9338260207395713 1.48e-01 1.19
5 0.8094380881164263 2.40e-02 1.09
6 0.7859852310561355 5.87e-04 1.02
7 0.7853985081807326 3.45e-07 1.00
8 0.7853981633975672 1.19e-13 1.00
9 0.7853981633974483 < eps
ek/e2k−1
konstant ⇒ quadratische Konvergenz
Kapitel I (nonlin11) 13
Prof. Dr. Barbara Wohlmuth
Lehrstuhl fur Numerische Mathematik
Newton-Verfahren: Berechnung von π/4
Konvergenzbetrachtung
Fehler
0 2 4 6 8
10−10
10−5
k
ek−12
ek
Visualisierung
0.8 1 1.2 1.4
0
5
10
15
Kapitel I (nonlin12) 14
Prof. Dr. Barbara Wohlmuth
Lehrstuhl fur Numerische Mathematik
Vergleich Newton– und Sekantenverfahren
Nullstellenbestimmung von f(x) = 2− x2 − ex:
Startwerte: x0 = 1, x1 = 2.
Fehler ek = |xk − x∗|k ek Sekant ek Newton
0 4.6272555e-01 4.6272555e-01
1 2.4627256e+00 9.8550224e-02
2 3.2725312e-01 5.8822435e-03
3 2.3503058e-01 2.2909460e-05
4 4.0076805e-02 3.4958791e-10
5 5.5073255e-03 < eps
6 1.4366892e-04
7 5.2551511e-07
8 5.0286553e-11
9 1.1102230e-16
x∗ muss numerisch bestimmt werden.
1 2 3 4 5 6 7
10−10
100
ek Sekant
e2k
Sekant
ek Newton
Aufwand: Newton ≈ 2·SekantKonvergenz:
2 = pnew > psek ≈ 1.618pnew < (psek)
2 ≈ 2.618.
Kapitel I (nonlin23) 15
Prof. Dr. Barbara Wohlmuth
Lehrstuhl fur Numerische Mathematik
Verfahren im Vergleich (Startwert abhangig)
−5 0 5−1.5
−1
−0.5
0
0.5
1
1.5
atan(x)
−5 0 5 10 15−1000
−800
−600
−400
−200
0
200
400
x3−16x2−50
−10 −5 0 5 10−4
−2
0
2
4
6
8
10
(4sin x2+x3+0.5) exp(−0.2(x−0.5)2)
0 5 10 15 2010
−30
10−20
10−10
100
1010
Regula falsi
Sekanten
Newton
0 10 20 30 40 5010
−15
10−10
10−5
100
x3−16 x2−50
Bisektion
Sekanten
Regula falsiNewton0 10 20 30 40 50
10−15
10−10
10−5
100
Sekanten
Regula falsi
Bisektion
Anzahl der Iterationen versus Fehlernorm (Mitte: typisch)
Kapitel I (nonlin15) 16
Prof. Dr. Barbara Wohlmuth
Lehrstuhl fur Numerische Mathematik
Gedampfte Variante des Newton-Verfahrens (F (xi) < F (xi−1))
−4 −2 0 2 4−1.5
−1
−0.5
0
0.5
1
1.5
−10 −5 0 5 10−1.5
−1
−0.5
0
0.5
1
1.5
−20 −10 0 10 20
−1.5
−1
−0.5
0
0.5
1
1.5
Unterschiedliche Startwerte: Iterierte (oben), Fehler (unten links)
0 2 4 6
10−10
100
1 1.5 5 1001 2 3 4 5 6 7
0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
Dämpfungsparameter
Dampfungsparameter (unten rechts) geht gegen 1, lokal quadratische Konvergenz
Kapitel I (nonlin16) 17
Prof. Dr. Barbara Wohlmuth
Lehrstuhl fur Numerische Mathematik
Newton-Verfahren mit festem Dampfungsparameter λ = 1
2
0 0.2 0.4 0.6
0
0.1
0.2
0.3
0.4
0.5
−1 0 1 2
−0.5
0
0.5
1
−4 −2 0 2 4
−1
−0.5
0
0.5
1
Unterschiedliche Startwerte: Iterierte (oben) und Fehler (unten)
0 20 40 60 80 100
10−10
100
0.51.02.02.8864...
Fester Dampfungsparameter fuhrt zu Verlust der lokal quadratischen Konvergenz!
Kapitel I (nonlin17) 18
Prof. Dr. Barbara Wohlmuth
Lehrstuhl fur Numerische Mathematik
Newton-Verfahren: System
Berechnet wird die Nullstelle (x∗, y∗) = (1, 2) von
f : R2 → R2; f(x, y) =
(
(y − 2)(3x2 + x+ 1)(x− 1)(y2 − y + 4)
)
.
Startwert (x0, y0) := (3, 3).
k xk yk ek ek/e2
k−1
0 3.000000000000000 3.000000000000000 2.24e+00
1 0.416666666666667 3.583333333333333 1.69e+00 0.34
2 0.503205158698697 1.752481302359999 5.55e-01 0.20
3 1.121515983782909 2.271832749614574 2.98e-01 0.97
4 1.014608957035601 2.038103031097112 4.08e-02 0.46
5 1.000274416148627 2.000758627349442 8.07e-04 0.48
6 1.000000104062970 2.000000291297514 3.09e-07 0.48
7 1.000000000000015 2.000000000000043 4.52e-14 0.47
8 1.000000000000000 2.000000000000000 < eps
Kapitel I (nonlin18) 19
Prof. Dr. Barbara Wohlmuth
Lehrstuhl fur Numerische Mathematik
Fixpunktiteration: Wahl von φ
Nullstellenbestimmung von 2− x2 − ex:
−1.5 −1 −0.5 0 0.5 1 1.5−1.5
−1
−0.5
0
0.5
1
1.5Fixpunktiteration
φ1(x) = ln(2− x2), x0 = 0.99
⇒ Konvergenz
−0.5 0 0.5 1−0.5
0
0.5
1
Fixpunktiteration
φ2(x) =√2− ex, x0 = 0.6
⇒ Divergenz
Kapitel I (nonlin22) 20
Prof. Dr. Barbara Wohlmuth
Lehrstuhl fur Numerische Mathematik
Rang-1-Verfahren von Broyden
Gegeben seien der Startwert x0 und die Startmatrix B0 (z.B. durchDifferenzenbildung). Fur k ≥ 0 bis Konvergenz berechne
dk := B−1
k f(xk),
xk+1 := xk − λkdk,
pk := xk+1 − xk,
qk := f(xk+1)− f(xk),
Bk+1 := Bk +1
pTk pk(qk −Bkpk)p
Tk .
Das Verfahren konvergiert lokal superlinear, d.h.
limk→∞
‖xk+1 − x∗‖‖xk − x∗‖
= 0.
Kapitel I (nonlin20) 21
Prof. Dr. Barbara Wohlmuth
Lehrstuhl fur Numerische Mathematik
Rang-1-Verfahren von Broyden, Beispiel
Funktion f , Startwert (x0, y0) wie oben, λk := 1.Vergleich
Broyden vs. exakt
0 5 10 1510
−15
10−10
10−5
100
105
Broydenexakt
k ek ek/ek−1
0 2.24e+00
1 1.69e+00 7.55e-01
2 1.00e+00 5.95e-01
3 8.25e-01 8.22e-01
4 6.06e-01 7.35e-01
5 3.37e-01 5.55e-01
6 2.27e-02 6.75e-02
7 7.60e-03 3.34e-01
8 2.99e-03 3.94e-01
9 5.58e-04 1.87e-01
10 2.52e-06 4.52e-03
11 4.27e-08 1.69e-02
12 8.35e-10 1.96e-02
13 6.82e-13 8.16e-04
14 < eps
Kapitel I (nonlin21) 22
Prof. Dr. Barbara Wohlmuth
Lehrstuhl fur Numerische Mathematik
Newton-Verfahren: Funktionswert vs. Fehler
1 1.2 1.40
5
10
15
20
25f(x) = tan(x) − 3/2x
0 = 3/2
k ek |fk|
0 5.17e − 01 1.26e + 01
1 4.54e − 01 5.93e + 00
2 3.49e − 01 2.60e + 00
3 2.03e − 01 9.65e − 01
4 6.62e − 02 2.39e − 01
5 6.76e − 03 2.22e − 02
10 12 14 16 18 20
−0.02
−0.01
0
0.01
0.02 f(x) = atan(x) −3/2x
0 = 20
k ek |fk|
0 5.90e + 00 2.08e − 02
1 2.46e + 00 1.49e − 02
2 4.26e − 01 2.20e − 03
3 1.28e − 02 6.41e − 05
4 1.15e − 05 5.78e − 08
5 9.40e − 12 4.71e − 14
Residuum nicht immer gutes Abbruchkriterium (Kondition!)
Kapitel I (nonlin13) 23