Numerisches Lösen von Gleichungen

Modellierung
und
Simulation
Numerisches Lösen von Gleichungen
Britta Nestler
Lösen von
Gleichungen
Bisektion
Newton-Verfahren
Gesucht ist eine Lösung der Gleichung f (x) = 0.
Regula falsi
Das Bisektionsverfahren ist eine numerische Methode zur
Bestimmung einer Nullstelle. Es basiert auf dem
Zwischenwertsatz:
Satz (1.1.1)
Zwischenwertsatz: Sei f : [a, b] → R stetig mit f (a) < 0 und
f (b) > 0. Dann existiert eine Zwischenstelle ξ ∈ (a, b) mit
f (ξ) = 0.
Modellierung
und
Simulation
Britta Nestler
Lösen von
Gleichungen
Bisektion
Newton-Verfahren
Regula falsi
Darstellung des Zwischenwertsatzes
Sei f : [a, b] → R stetig mit f (a) < 0 und f (b) > 0. Dann
existiert eine Zwischenstelle ξ ∈ (a, b) mit f (ξ) = 0.
Modellierung
und
Simulation
Bisektion: Algorithmus
Britta Nestler
Lösen von
Gleichungen
Bisektion
1
Newton-Verfahren
Regula falsi
2
Initialisierung:
x1 = a, x2 = b, f1 = f (x1 ), f2 = f (x2 ), δ = 10−5
Iteration:
a) Bestimme Intervallmitte: x3 = 12 (x1 + x2 )
b) Bestimme Funktionswert: f3 = f (x3 )
c) Festlegung des neuen Intervalls:
i) falls f3 · f2 6 0 (Nullstelle zwischen x2 und x3 ),
dann x1 := x3 und f1 := f3
ii) falls f3 · f2 > 0 (Nullstelle zwischen x1 und x3 ),
dann x2 := x3 und f2 := f3
d) Abbruchbedingungen
i) falls |x2 − x1 | 6 δ, dann x3 := ξ Stop
ii) falls |x2 − x1 | > δ, dann weiter mit a)
Modellierung
und
Simulation
Bemerkungen zum Bisektionsverfahren
Britta Nestler
Lösen von
Gleichungen
Bisektion
Newton-Verfahren
Regula falsi
Das Bisektionsverfahren liefert nur eine Nullstelle im
Intervall I = [a, b].
δ ist Abbruchskriterium und sollte nicht kleiner als die
Rechengenauigkeit sein.
Beispiel
Gegeben ist die Funktion f (x) = x3 −
I = [1, 2]
√
x2 + 1 im Intervall
Da f (1) = −0.4142 und f (2) = 5.7639 liegt nach dem
Zwischenwertsatz eine Nullstelle im Intervall I = [1, 2].
1. Schritt des Algorithmus:
x3 = 1.5 ⇒ f (1.5) = 1.5722 usw.
Nach 13 Iterationen ergibt sich als Nullstelle: ξ = 1.1509.
Modellierung
und
Simulation
Britta Nestler
Lösen von
Gleichungen
Bisektion
Newton-Verfahren
Beispiel
Regula falsi
Es soll die n-ten Wurzel x =
werden.
√
n
a für a ≥ 0, a 6= 1 berechnet
Diese Aufgabe ist äquivalent mit dem folgenden
√
Nullstellenproblem: x = n a ⇒ f (x) = xn − a = 0
√
z.B. x = 5 8 ⇒ f (x) = x5 − 8 = 0.
Modellierung
und
Simulation
Newton-Verfahren
Britta Nestler
Lösen von
Gleichungen
Bisektion
Newton-Verfahren
Regula falsi
Das Newton-Verfahren ist die am häufigsten eingesetzte
Methode zur numerischen Bestimmung einer Nullstelle
f (x) = 0 im Intervall I = [a, b], da es eine schnelle Konvergenz
bestitzt.
Iteratives Verfahren:
Man startet mit einem Startwert x0 , berechnet die Tangente an
die Funktion f (x) in x0 und bestimmt den Schnittpunkt mit
der x-Achse. Dieser Schnittpunkt wird der neue Punkt x1 , an
dem die nächste Tangente berechnet wird und wieder der
Schnittpunkt mit der x-Achse usw..
Modellierung
und
Simulation
Britta Nestler
Lösen von
Gleichungen
Bisektion
Newton-Verfahren
Regula falsi
Darstellung des Newton-Verfahrens
Modellierung
und
Simulation
Formeln zum Newton-Verfahren
Britta Nestler
Lösen von
Gleichungen
Bisektion
Newton-Verfahren
Regula falsi
Tangentengleichung in x0 :
y = f (x0 ) + f 0 (x0 )(x − x0 )
Schnittpunkt x1 mit der x-Achse, d.h. für y = 0:
0 = f (x0 ) + f 0 (x0 )(x1 − x0 )
f (x0 )
⇒ x1 = x0 − 0
f (x0 )
Modellierung
und
Simulation
Newton: Algorithmus
Britta Nestler
Lösen von
Gleichungen
Bisektion
Newton-Verfahren
1
Regula falsi
2
Initialisierung: wähle x0 und δ := 10−5
Iteration:
a) Newton-Formel:
xn+1 = xn −
f (xn )
,
f 0 (xn )
n = 0, 1, 2, 3, . . .
b) Abbruchbedingung:
i) falls |xn+1 − xn | < δ, dann δ = xn+1 ; Stop
ii) falls |xn+1 − xn | > δ, dann weiter mit a).
Modellierung
und
Simulation
Eigenschaften des Newton-Verfahrens
Britta Nestler
Lösen von
Gleichungen
Bisektion
Newton-Verfahren
Regula falsi
schnelle Konvergenz (wenige Iterationsschritte)
bei einem schlechten Startwert kann das Verfahren
divergieren.
Ausweg: Finde über das Bisektionsverfahren zunächst
einen guten Startwert.
die Ableitung f 0 (x) muss existieren
das Verfahren ist erweiterbar auf Funktion mehrerer
Veränderlicher f (x, y, . . .)
Modellierung
und
Simulation
Britta Nestler
Lösen von
Gleichungen
Beispiel
Gegeben ist die Funktion f (x) = x3 −
I = [1, 2].
√
x2 + 1, im Intervall
Bisektion
Newton-Verfahren
Regula falsi
Die Ableitung lautet: f 0 (x) = 3x2 −
√ x
.
x2 +1
Die Newton-Iteration ergibt:
n
0
1
2
3
4
xn
1.5
1.2343
1.1573
1.1510
1.1509
f (xn )
1.5722
0.2920
0.0207
0.0001
0.6·10−8
d.h. nach 4 Iterationen hat man die Nullstelle bis auf 8
Dezimalstellen genau bestimmt.
Modellierung
und
Simulation
Regula falsi
Britta Nestler
Lösen von
Gleichungen
Bisektion
Newton-Verfahren
Regula falsi
Das Newton-Verfahren benötigt die Berechung der ersten
Ableitung von f (x). Falls dies nicht möglich ist, ist das Regula
falsi Verfahren eine alternative Methode zur Lösung der
Gleichung f (x) = 0. Hierzu werden zwei Startwerte x0 und x1
benötigt.
Geometrisch: Statt einer Tangente wird eine Sekante zwischen
den Punkten (x0 , f (x0 )) und (x1 , f (x1 )) bestimmt und dann
der Schnittpunkt x2 der Sekanten mit der x-Achse berechnet.
Daraus ergibt sich ein neuer Punkt (x2 , f (x2 )), der zusammen
mit (x1 , f (x1 )) den nächsten Iterationsschritt bildet, usw..
Modellierung
und
Simulation
Britta Nestler
Lösen von
Gleichungen
Bisektion
Newton-Verfahren
Regula falsi
Darstellung des Regula fals Verfahrens
Modellierung
und
Simulation
Formeln zum Regula falsi Verfahren
Britta Nestler
Lösen von
Gleichungen
Bisektion
Newton-Verfahren
Regula falsi
Sekantengleichung in x0 und x1 :
f (x1 ) − f (x0 )
y − f (x0 )
=
x1 − x0
x − x0
Schnittpunkt x2 mit der x-Achse, d.h. für y = 0:
x2 = x0 − f (x0 ) ·
x1 − x0
f (x1 ) − f (x0 )
Modellierung
und
Simulation
Britta Nestler
Lösen von
Gleichungen
Bisektion
Newton-Verfahren
Regula falsi
Konstruktion der Sekanten
Modellierung
und
Simulation
Regula falsi: Algorithmus
Britta Nestler
Lösen von
Gleichungen
Bisektion
Newton-Verfahren
Regula falsi
1
2
Initialisierung: wähle x0 , x1 und δ := 10−5
Iteration:
a) Sekanten-Formel:
xn+1 = xn−1 − f (xn−1 )
xn − xn−1
f (xn ) − f (xn−1 )
b) Abbruchbedingung:
i) falls |xn+1 − xn | < δ, dann δ = xn+1 ; Stop
ii) falls |xn+1 − xn | > δ, dann weiter mit a).
Modellierung
und
Simulation
Bemerkungen
Britta Nestler
Lösen von
Gleichungen
Bisektion
Newton-Verfahren
Regula falsi
die Konvergenz des Regula falsi Verfahrens ist langsamer
als die des Newton-Verfahrens
Bei Nullstellen von Polynomausdrücken ist das
Horner-Schema zur Auswertung der Funktionswerte f (x1 )
sehr geeignet. Es kann außerdem zur Berechnung der
Ableitung f 0 (x1 ) an einem Punkt x1 angewendet werden.
Bei dem Newton-Verfahren muss in jedem Iterationsschritt
f (xn ) und f 0 (xn ) berechnet werden. Hierzu ist es schnell,
das doppelte Horner-Schema zu verwenden.
Modellierung
und
Simulation
Britta Nestler
Lösen von
Gleichungen
Bisektion
Horner-Schema zur Auswertung der Ableitung
Gegeben ist ein Polynomausdruck:
f (x) = (x − x1 ){bk xk−1 + bk−1 xk−2 + ... + b2 x + b1 } + b0
Newton-Verfahren
Regula falsi
Mit der Produktregel folgt
f 0 (x)
⇒ f 0 (x1 )
n
o
bk xk−1 + bk−1 xk−2 + . . . + b2 x + b1 +
n
o
(x − x1 ) (k − 1)bk xk−2 + (k − 2)bk−1 xk−3 + . . . + b2
=
= {bk xk−1
+ bk−1 xk−2
+ . . . + b2 x1 + b1 }
1
1
mit dem Horner-Schema ergeben sich die Koeffizienten bi :
ck
ci−1
und f 0 (x1 )
= bk
= bi−1 + ci xx ,
= c1 .
i = k, k − 1, . . . , 2
Modellierung
und
Simulation
Doppeltes Horner-Schema
Britta Nestler
Lösen von
Gleichungen
Bisektion
Beispiel
Newton-Verfahren
Regula falsi
Gegeben ist die Funktion f (x) = 4x3 − 5x2 + 2x + 1. Gesucht
ist der Wert der Funktion f (x) und der Wert der Ableitung
f 0 (x) jeweils an der Stelle x1 = 2.
−5
2·4
4
3
4
+
+
4
2
2·3
8
2·4
2 · 11
11 30 = f 0 (2)
1
8·2
17 = f (2)

Download Report