Inhalt Kapitel I: Nichtlineare Gleichungssysteme · Prof. Dr. Barbara Wohlmuth Lehrstuhl fu¨r Numerische Mathematik Inhalt Kapitel I: Nichtlineare Gleichungssysteme I Nichtlineare

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



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



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


Feh

ler

Lineare Konvergenz

Reduktion der Intervalllange variabel





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


Feh

ler

Konvergenzordnung i.d.R. p = (1 +√5)/2


Reduktion der Intervalllange variabel




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


Feh

ler

Fixpunkt: Φ(x) =√x = x, Nullstelle: g(x) =

√x− x

Pro Schritt eine Funktionsauswertung, lin. Konvergenz Φ′(1) = 1

2




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


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


Iterie

rte

0 5 10 15 200.4

0.45

0.5

0.55

0.6

Fixpunktiteration


Feh

ler




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


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


Iterie

rte




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∗‖.




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




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




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




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


abs.

Feh

ler

1.0

1.3 1.3917

1.35

1.391745

1.39




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




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




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.




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)




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




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!




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




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




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.




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




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!)


Documents

Inhalt Kapitel I: Nichtlineare Gleichungssysteme · Prof. Dr. Barbara Wohlmuth Lehrstuhl fu¨r Numerische Mathematik Inhalt Kapitel I: Nichtlineare Gleichungssysteme I Nichtlineare