Content

26. Intervallhalbierungs-, Regula-falsi- und Newton-Verfahren in:

Michael Merz, Mario V. Wüthrich

Mathematik für Wirtschaftswissenschaftler, page 789 - 804

Die Einführung mit vielen ökonomischen Beispielen

1. Edition 2012, ISBN print: 978-3-8006-4482-7, ISBN online: 978-3-8006-4483-4, https://doi.org/10.15358/9783800644834_789

Bibliographic information
Teil IX Numerische Verfahren Kapitel26 Intervallhalbierungs-, Regula-falsi- und Newton-Verfahren Kapitel 26 Intervallhalbierungs-, Regula-falsi- und Newton-Verfahren 26.1 Numerische Lösung von Gleichungen S. Ramanujan Der berühmte indische Mathematiker Srinivasa Ramanujan (1887–1920) hat sich sein gesamtes mathematisches Wissen autodidaktisch angeeignet. Dennoch gelang es ihm eine Vielzahl von bisher unbekannten Gleichungen zu entdecken. Eine der schönsten und bekanntesten dieser Gleichungen lautet: 1 1 + e −2π 1 + e −4π 1 + e −6π 1 + e −8π . . . = ⎛ ⎝ √ 5 +√5 2 − √ 5 + 1 2 ⎞ ⎠ e 2π 5 Auf Ramanujan geht auch das folgende Zitat zurück: „Eine Gleichung hat für mich keinen Sinn, es sei denn, sie drückt einen Gedanken Gottes aus.“ Natürlich führen jedoch auch viele wirtschafts- und naturwissenschaftliche Fragestellungen zu Gleichungen der Form f (x) = c (26.1) mit einer reellen Funktion f und einer Konstanten c. Gleichungen besitzen daher auch eine ganz irdische Bedeutung und das Lösen von Gleichungen ist eine in der Praxis immer wieder auftretende Problemstellung. Da jedoch die Gleichung (26.1) zu f (x)− c = 0 äquivalent ist, kann man sich bei der Betrachtung von Lösungsverfahren auf Gleichungen der Form f (x) = 0, (26.2) also auf die Berechnung von Nullstellen einer reellen Funktion, beschränken. Zum Beispiel wird man bei der Ermittlung der Extremalstellen einer reellen Funktion (vgl. Abschnitt 18.1) oder bei der Partialbruchzerlegung einer gebrochen-rationalen Funktion (siehe Abschnitt 14.2) mit der Problemstellung konfrontiert, die Nullstellen einer reellen Funktion bestimmen zu müssen. Aber auch vielen anderen mathematischen oder ökonomischen Fragestellungen liegt im Wesentlichen die Aufgabe zu Grunde, die Nullstellen einer oder mehrerer reeller Funktionen zu ermitteln. Bedauerlicherweise ist jedoch die Auflösung einer Gleichung (26.2) nach der Variablen x nur in wenigen Fällen explizit möglich. Wie in Abschnitt 4.4 bereits erläutert wurde, sind quadratische Gleichungen der Form a2x 2 + a1x + a0 = 0 ein solcher Ausnahmefall. Ebenso lassen sich prinzipell auch noch Gleichungen dritten und vierten Grades a3x 3 + a2x2 + a1x + a0 = 0 bzw. a4x 4 + a3x3 + a2x2 + a1x + a0 = 0 explizit nach x auflösen, wenn auch die dazu benötigten Lösungsformeln deutlich komplizierter sind (siehe z. B. König et al. [34], Seiten 323–324 und Bronstein et al. [8], Seiten 29–31). Dagegen ist bei Gleichungen anx n + an−1xn−1 + . . .+ a1x + a0 = 0 vom Grade n > 4 und auch in den meisten anderen Fällen eine explizite Auflösung nach der Variablen x nicht mehr möglich. Aus diesem Grunde besitzen numerische Verfahren zur Berechnung von Nullstellen eine sehr große Bedeutung. Diese Verfahren bestehen darin, dass ausgehend von einem oder mehreren Näherungswerten, den sogenannten Startwerten, iterativ (d. h. schrittweise) nach einer gewissen Vorschrift immer genauere Näherungswerte xn für die gesuchte Lösung x von (26.2) numerisch berechnet werden. Unter gewissen Voraussetzungen konvergiert dann die so ermittelte Folge von Näherungswerten (xn)n∈N0 gegen die Lösung x. Dies bedeutet, dass sich für ein hinreichend großes n (also nach hinreichend vielen Iterationen) die Näherungswerte xn um weniger als eine zuvor festgelegte maximale Fehlertoleranz von der Lösung x unterscheiden. In der Praxis wird ein numerisches Verfahren zur Berechnung von Nullstellen abgebrochen, sobald man einen Näherungswert xn erhalten hat, der eine gewisse Genauigkeitsanforderung erfüllt. Ein solches Abbruchkriterium ist z. B. die Forderung, dass |f (xn)| hinreichend klein ist. Ein anderes häufig verwendetes Kriterium verlangt, dass sich zwei aufeinanderfolgende Näherungswerte xn−1 und xn hinreichend wenig unterscheiden. In den folgenden vier Abschnitten werden mit dem Intervallhalbierungsverfahren, dem Regula-falsi-Verfahren, dem 798 Kapitel 2626.2 Intervallhalbierungsverfahren Newton-Verfahren, dem Sekantenverfahren und dem vereinfachten Newton-Verfahren fünf bekannte numerische Verfahren vorgestellt. Prinzipiell können zur numerischen Berechnung von Nullstelllen aber auch Fixpunktsätze, wie z. B. der in Abschnitt 15.9 betrachtete Fixpunktsatz von Banach, eingesetzt werden. Denn definiert man die reelle Funktion g durch g(x) := f (x)+ x, dann gilt f (x) = 0 ⇐⇒ g(x) = x. Das heißt, der Wert x ist genau dann eine Nullstelle von f , wenn x ein Fixpunkt der Funktion g ist. Es hängt somit lediglich von der Betrachtungsweise ab, ob man Fixpunkte oder Nullstellen von reellen Funktionen sucht. 26.2 Intervallhalbierungsverfahren Das Intervallhalbierungsverfahren oder auch Bisektion genannt, ist ein einfaches numerisches Verfahren zur Berechnung von Nullstellen einer stetigen reellen Funktion f : [a, b] −→ R mit der Eigenschaft f (a)f (b) < 0. (26.3) Dabei kann in (26.3) ohne Beschränkung der Allgemeinheit f (a) < 0 und f (b) > 0 (26.4) angenommen werden, da man andernfalls einfach f durch −f zu ersetzen braucht. Der Nullstellensatz (vgl. Satz 15.27) besagt dann, dass die Funktion f mindestens eine Nullstelle im offenen Intervall (a, b) besitzt. Das heißt, es gibt mindestens einen Wert x ∈ (a, b) mit der Eigenschaft f (x) = 0. Das Intervallhalbierungsverfahren besitzt den Vorteil, dass es lediglich die Stetigkeit der Funktion f voraussetzt und damit unter sehr allgemeinen Voraussetzungen zur Berechnung von Nullstellen eingesetzt werden kann. Zur näherungsweisen Berechnung einer Nullstelle x von f wird beim Intervallhalbierungsverfahren durch fortgesetzte Halbierung des Ausgangsintervalls [a, b] bzw. der dadurch resultierenden Teilintervalle eine Intervallschachtelung konstruiert, welche eine Nullstelle x immer besser annähert. Dazu setzt man [a0, b0] := [a, b] und definiert die Teilintervalle [an+1, bn+1] := { [an,mn] falls f (mn) ≥ 0 [mn, bn] falls f (mn) < 0 (26.5) für alle n ∈ N0, wobei mn := an + bn 2 (26.6) die Mitte des Intervalls [an, bn] ist. Für die so definierte Folge von Intervallen [a0, b0], [a1, b1], [a2, b2], [a3, b3], . . . erhält man wegen (26.4) und dem Nullstellensatz (vgl. Satz 15.27), dass es eine Nullstelle mit x ∈ [an, bn] für alle n ∈ N0 gibt und ein beliebiger Wert xn aus dem n-ten Teilintervall [an, bn] von dieser Nullstelle x höchstens den Abstand bn − an = 2−n(b − a) (26.7) besitzt. Wegen lim n→∞(bn − an) = 0 bedeutet dies jedoch, dass auf diese Weise die Nullstelle x durch eine Folge (xn)n∈N0 von Näherungswerten mit xn ∈ [an, bn] für alle n ∈ N0 beliebig genau angenähert wird (vgl. Abbildung 26.1). Das heißt, es gilt der folgende Satz: Satz 26.1 (Konvergenz Intervallhalbierungsverfahren) Es sei f : [a, b] −→ R eine stetige reelle Funktion mit der Eigenschaft f (a)f (b) < 0. Dann konvergiert eine mittels des Intervallhalbierungsverfahrens ermittelte Folge von Näherungswerten (xn)n∈N0 gegen eine Nullstelle x ∈ (a, b) von f . Beweis: Siehe Ausführungen vor diesem Satz. Ist ε > 0 eine gewünschte Approximationsgenauigkeit und gilt für die Anzahl n der Iterationen im Intervallhalbierungsverfahren b − a 2n ≤ ε, d. h. n ≥ 1 ln(2) ln ( b − a ε ) , dann erhält man mit (26.7), dass sich ein beliebiger Wert xn aus dem Teilintervall [an, bn] maximal um ε > 0 von einer Nullstelle x unterscheidet. Das heißt, die Anzahl der benötigten Iterationen n für eine gewünschte Approximationsgenauigkeit von ε ist durch das Verhältnis der Intervalllänge b−a zu ε festgelegt. 799 Kapitel 26 Intervallhalbierungs-, Regula-falsi- und Newton-Verfahren a b 0 f (x) l ll lll x a0 b0 = b1a1 = a2 b2 = b3a3 Abb. 26.1: Konstruktion einer Intervallschachtelung [a0, b0], [a1, b1], [a2, b2], . . . zur näherungsweisen Berechnung einer Nullstelle x für eine stetige reelle Funktion f : [a, b] −→ R mit f (a)f (b) < 0 mittels Intervallhalbierungsverfahren Wie bereits erwähnt, besitzt das Intervallhalbierungsverfahren im Vergleich zu den meisten anderen Näherungsverfahren den Vorteil, dass es unter sehr allgemeinen Voraussetzungen einsetzbar ist. Es weist jedoch nur ein sehr langsames Konvergenzverhalten gegen eine Nullstelle x auf, da durch die Intervallhalbierung mit jedem Iterationsschritt der Fehler lediglich (ungefähr) halbiert wird. Das Intervallhalbierungsverfahren besitzt somit nur eine lineare Konvergenzgeschwindigkeit und wird daher häufig ausschließlich zur Berechnung von Startwerten für schnellere Näherungsverfahren, wie z. B. das Regula-falsi-Verfahren (vgl. Abschnitt 26.3) und das Newton-Verfahren (vgl. Abschnitt 26.4) verwendet. Beispiel 26.2 (Intervallhalbierungsverfahren) a) Es soll eine Nullstelle der stetigen reellen Funktion f : R −→ R, x %→ f (x) = x4 + x3 + 1,662x2 − x − 0,250 im Intervall [0, 1] berechnet werden. Es gilt f (0) = −0,250 und f (1) = 2,412. Mit dem Intervallhalbierungsverfahren erhält man die Werte in der folgenden Tabelle: n an bn f ( an+bn 2 ) 0 0 1 −0,147000000 1 0,5 1 0,673156200 2 0,5 0,75 0,170947300 3 0,5 0,625 −0,008541382 4 0,5625 0,625 0,075773780 5 0,5625 0,59375 0,032297350 6 0,5625 0,578125 0,011553000 7 0,5625 0,5703125 0,001425150 8 0,5625 0,5664062 −0,0035782720 ... ... ... ... Das heißt, die Näherungswerte konvergieren relativ langsam gegen eine Nullstelle. Nach acht Iterationen erhält man, dass im Intervall (0,5625; 0,5664062) eine Nullstelle x liegen muss. Wählt man nach der achten Iteration als Näherungswert mit x8 := 0,5625+0,56640622 = 0,5644531 die Mitte des Intervalls (0,5625; 0,5664062), dann beträgt der Fehler maximal 0,5664062−0,56252 ≈ 0,002. Weitere Iterationen zeigen, dass – bis auf acht Nachkommastellen genau – durch x = 0,56585152 eine Nullstelle von f gegeben ist. 800 Kapitel 2626.3 Regula-falsi-Verfahren b) Es soll eine Nullstelle der stetigen reellen Funktion f : [1, 2] −→ R, x %→ f (x) = 1 x ex 2−1 − 5 bestimmt werden, wobei der maximale Fehler 0,01 betragen darf. Es gilt f (1) = −4 und f (2) = 5,042768. Mit dem Intervallhalbierungsverfahren erhält man die Werte in der folgenden Tabelle: n an bn f ( an+bn 2 ) 0 1 2 −2,67310500 1 1,5 2 −0,50536610 2 1,75 2 1,59964800 3 1,75 1,875 0,42191540 4 1,75 1,8125 −0,06902766 5 1,78125 1,8125 0,16916270 6 1,78125 1,796875 0,04830675 ... ... ... ... Das heißt, die Näherungswerte konvergieren wieder relativ langsam gegen eine Nullstelle und nach sechs Iterationen erhält man, dass im Intervall (1,78125; 1,796875) eine Nullstelle x liegen muss. Wählt man nach der sechsten Iteration als Näherungswert die Mitte x6 := 1,796875+1,781252 = 1,789062 des Intervalls (1,78125; 1,796875), dann beträgt der Fehler maximal 1,796875−1,781252 ≈0,008. Weitere Iterationen zeigen, dass – bis auf sechs Nachkommastellen genau – durch x = 1,785874 eine Nullstelle von f gegeben ist. 26.3 Regula-falsi-Verfahren Zwei Seiten der „Liber Abaci“ Das Regula-falsi-Verfahren ist ein weiteres einfaches numerisches Verfahren zur Berechnung von Nullstellen einer stetigen reellen Funktion f : [a, b]−→R mit der Eigenschaft (26.3), wobei ohne Beschränkung der Allgemeinheit wieder (26.4) angenommen werden kann. Bei diesem Verfahren handelt es sich um eine bereits sehr alte Methode zur Berechnung von Nullstellen. Es wurde erstmals in der indischen Schrift „Vaishali Ganit“ (ca. 3. Jh. v. Chr.) erwähnt und ist darüber hinaus zum Beispiel auch in dem 1202 veröffentlichten Buch „Liber Abaci“ des bedeutenden italienischen Mathematikers Leonardo von Pisa (1180– 1241), der vor allem unter dem Namen Fibonacci bekannt wurde, zu finden. Die Bezeichnung „Regula falsi“ kommt dabei aus dem Lateinischen und bedeutet soviel wie „Regel vom Falschen ausgehend“ und trägt der Tatsache Rechnung, dass bei diesem Verfahren der Graph der Funktion f durch eine „falsche Kurve“, nämlich durch eine Sekante, ersetzt wird. Analog zum Intervallhalbierungsverfahren in Abschnitt 26.2 kann auch das Regula-falsi-Verfahren unter sehr allgemeinen Voraussetzungen angewendet werden. Im Gegensatz zum Intervallhalbierungsverfahren berücksichtigt es jedoch die Sekantensteigungen der betrachteten Funktion f , weshalb die Näherungswerte oftmals deutlich schneller gegen eine Nullstelle x ∈ (a, b) konvergieren (vgl. Beispiel 26.4b)). Bei der numerischen Berechnung einer Nullstelle x von f im Intervall [a, b] mittels des Regula-falsi-Verfahrens werden die beiden Intervallgrenzen a und b als Startwerte verwendet. Anschließend wird diejenige Stelle x0 ∈ (a, b) ermittelt, an der die Sekante durch die beiden Punkte (a, f (a)) und (b, f (b)) des Graphen von f , d. h. die Gerade f (a)+ f (b)− f (a) b − a (x − a), die x-Achse schneidet. Das heißt, der Wert x0 ist definiert durch x0 := a − b − a f (b)− f (a)f (a), wobei f (a) = f (b) gilt (vgl. (26.3)). Entsprechend verfährt man anschließend mit demjenigen der beiden Teilintervalle [a, x0] oder [x0, b], an dessen Intervallgrenzen die Werte von f verschiedene Vorzeichen aufweisen. Dieses Teilintervall wird mit [a1, b1] bezeichnet und man berechnet für die Sekante durch die beiden Punkte (a1, f (a1)) und (b1, f (b1)), also für die Gerade f (a1)+ f (b1)− f (a1) b1 − a1 (x − a1), die Schnittstelle x1 ∈ (a1, b1) mit der x-Achse. Der Näherungswert x1 ist somit definiert durch x1 := a1 − b1 − a1 f (b1)− f (a1)f (a1). 801 Kapitel 26 Intervallhalbierungs-, Regula-falsi- und Newton-Verfahren a b 0 f (x) l ll a0 l ll x b0 = b1x0 = a1 x1 = b2 x2 = a2 Abb. 26.2: Näherungsweise Berechnung der Nullstelle x einer stetigen reellen Funktion f : [a, b] −→ R mit f (a)f (b) < 0 mittels Regula-falsi-Verfahren Dieses Vorgehen wird fortgesetzt, wobei man wieder [a0, b0] := [a, b] setzt. Man erhält dann für die Intervallenden der resultierenden Teilintervalle [an, bn] sowie die Nullstellen xn der zugehörigen Sekanten das Rekursionsschema xn : = an − bn − an f (bn)− f (an)f (an) (26.8) mit an+1 := { xn falls f (xn) ≤ 0 an falls f (xn) > 0 und bn+1 := { bn falls f (xn) ≤ 0 xn falls f (xn) > 0 (26.9) für alle n ∈ N0 (vgl. Abbildung 26.2). Wie der folgende Satz zeigt, konvergieren die so ermittelten Näherungswerte (xn)n∈N0 gegen eine Nullstelle x von f : Satz 26.3 (Konvergenz Regula-falsi-Verfahren) Es sei f : [a, b]−→R eine stetige reelle Funktion mit der Eigenschaft f (a)f (b) < 0. Dann konvergiert eine mittels des Regula-falsi-Verfahrens ermittelte Folge von Näherungswerten (xn)n∈N0 gegen eine Nullstelle x ∈ (a, b) von f . Beweis: Es sei ohne Beschränkung der Allgemeinheit wieder (26.4) angenommen. Für die Folgen (an)n∈N0 und (bn)n∈N0 gilt per Konstruktion f (an) ≤ 0 < f (bn) (26.10) für alle n ∈ N0. Ferner sind die Folgen (an)n∈N0 und (bn)n∈N0 monoton wachsend bzw. fallend sowie durch b und a nach oben bzw. nach unten beschränkt. Mit Satz 11.23 folgt daher, dass die Folgen (an)n∈N0 und (bn)n∈N0 gegen Grenzwerte α bzw. β konvergieren. Ferner erhält man mit Satz 11.41 und (15.2), dass für diese Grenzwerte a ≤ α ≤ β ≤ b und f (α) ≤ 0 ≤ f (β) gilt. Die Folge (sn)n∈N0 der Sekantensteigungen sn := f (bn)− f (an) bn − an (26.11) ist monoton wachsend mit sn > 0 für alle n ∈ N0 (vgl. Abbildung 26.3). Daher ist die Folge ( 1 sn ) n∈N0 monoton fallend mit 1 sn > 0 für alle n ∈ N0. Erneute Anwendung des Satzes 11.23 liefert somit, dass die Folge ( 1 sn ) n∈N0 konvergiert. Wegen xn = an − bn − an f (bn)− f (an)f (an) = an − f (an) sn (26.12) impliziert dies jedoch auch die Konvergenz der Näherungswerte (xn)n∈N0 gegen einen Grenzwert x. Aus den Definitionen (26.9) folgt, dass für diesen Grenzwert x = α oder x = β 802 Kapitel 2626.3 Regula-falsi-Verfahren 0 f (x) ll an l bn l x0 l x1 0 f (x) ll an l bn l x0 l x1 Abb. 26.3: Monoton wachsende Sekantensteigungen sn beim Regula-falsi-Verfahren gilt. Ohne Beschränkung der Allgemeinheit sei x = α angenommen (den Fall x = β zeigt man analog). Falls α = β gilt, impliziert dies f (α) = f (β) = 0 (vgl. (26.10)) und damit auch f (x) = 0. Im Falle von α = β existiert lim n→∞ 1 sn =: t = 0 (vgl. (26.11)) und zusammen mit (26.12) und den Rechenregeln für Grenzwerte folgt daher α = lim n→∞ xn = α − f (α)t. Dies impliziert jedoch f (α)t = 0 bzw. f (α) = 0 und damit insbesondere f (x) = 0. Damit ist insgesamt gezeigt, dass die Folge (xn)n∈N0 gegen ein x ∈ (a, b) mit f (x) = 0 konvergiert. Das Regula-falsi-Verfahren ist ein beliebtes numerisches Verfahren zur Berechnung von Nullstellen. Denn es kann unter sehr allgemeinen Voraussetzungen angewendet werden und im Vergleich zum Intervallhalbierungsverfahren weist es oftmals bessere Konvergenzeigenschaften auf, obwohl es nur einen relativ geringen Rechenaufwand je Iteration erfordert. Trotzdem kann es vorkommen, dass die Näherungswerte xn beim Intervallhalbierungsverfahren schneller gegen eine Nullstelle x von f konvergieren als beim Regula-falsi- Verfahren (vgl. Beispiel 26.2a) und Beispiel 26.4a)). Beispiel 26.4 (Regula-falsi-Verfahren) a) Betrachtet wird die stetige Funktion f in Beispiel 26.2a). Mit dem Regula-falsi-Verfahren erhält man für eine Nullstelle x von f im Intervall [0, 1] die folgenden Näherungswerte xn: n an bn f (an) f (bn) xn 0 0 1 −0,25 2,412 0,09391435 1 0,09391435 1 −0,32834956 2,412 0,20248182 2 0,20248182 1 −0,37435923 2,412 0,30963179 3 0,30963179 1 −0,36141640 2,412 0,39959678 4 0,39959678 1 −0,29490905 2,412 0,46500879 5 0,46500879 1 −0,20832215 2,412 0,50754192 6 0,50754192 1 −0,13231338 2,412 0,53315150 7 0,53315150 1 −0,07838018 2,412 0,54784471 8 0,54784471 1 −0,04451526 2,412 0,55603835 ... ... ... ... ... ... Das heißt, die Näherungswerte xn konvergieren noch langsamer gegen die Nullstelle x = 0,56585152 als beim Intervallhalbierungsverfahren in Beispiel 26.2a). Nach acht Iterationen erhält man als Näherungswert x8 = 0,55603835 und der Fehler beträgt dann 0,56585152 − 0,55603835 ≈ 0,01. 803 Kapitel 26 Intervallhalbierungs-, Regula-falsi- und Newton-Verfahren b) Betrachtet wird die stetige Funktion f in Beispiel 26.2b) und es soll wieder eine Nullstelle x von f im Intervall [1, 2] berechnet werden. Mit dem Regulafalsi-Verfahren erhält man die folgenden Näherungswerte xn: n an bn f (an) f (bn) xn 0 1 2 −4 5,04276846 1,44234241 1 1,44234241 2 −2,95768664 5,04276846 1,64850273 2 1,64850273 2 −1,62061473 5,04276846 1,73399109 3 1,73399109 2 −0,70994589 5,04276846 1,76681940 4 1,76681940 2 −0,27687895 5,04276846 1,77895607 5 1,77895607 2 −0,10282754 5,04276846 1,78337333 6 1,78337333 2 −0,10282754 5,04276846 1,78497150 . . . . . . . . . . . . . . . . . . Das heißt, die Näherungswerte xn konvergieren deutlich schneller gegen die Nullstelle x = 1,785874 als beim Intervallhalbierungsverfahren in Beispiel 26.2b). Nach sechs Iterationen erhält man als Näherungswert x6 = 1,7849715 und der Fehler beträgt dann 1,785874 − 1,7849715 ≈ 0,001. 26.4 Newton-Verfahren Titelseite der „Principia Mathematica“ Ein schnelles und bekanntes numerisches Verfahren zur Bestimmung von Nullstellen ist das nach dem bedeutenden englischen Physiker und Mathematiker Isaac Newton (1643–1727) benannte Newton-Verfahren. Es hat sich als ein mathematisches Standardverfahren zur numerischen Lösung von nichtlinearen Gleichungen der Form f (x) = 0 etabliert. Wegen seiner außergewöhnlichen wissenschaftlichen Leistungen auf den Gebieten der Physik und der Mathematik gilt Newton unumstritten als einer der bedeutendsten Wissenschaftler aller Zeiten. In seinem 1687 veröffentlichten Hauptwerk, den „Principia Mathematica“, vereint er die Forschungsergebnisse von Galileo Galilei (1564–1642) zur Beschleunigung von Körpern und die Resultate von Johannes Kepler (1571–1630) zur Planetenbewegung zu einer einheitlichen Theorie der Gravitation. Mit seiner Arbeit legte Newton den Grundstein für die klassische Mechanik, und die „Principia Mathematica“ sind damit eines der wichtigsten wissenschaftlichen Werke überhaupt. Im Vergleich zum Intervallhalbierungsverfahren in Abschnitt 26.2 und dem Regula-falsi-Verfahren in Abschnitt 26.3 macht das Newton-Verfahren von den Möglichkeiten der Differentialrechnung Gebrauch. Denn die grundlegende Idee des Newton-Verfahrens ist es, die Funktion f in einem Ausgangspunkt (x0, f (x0)) des Graphen von f zu „linearisieren“. Für die Anwendung des Newton-Verfahrens müssen daher aber auch stärkere Voraussetzungen als bei dem Intervallhalbierungsverfahren und dem Regula-falsi- Verfahren erfüllt sein. Falls jedoch diese Voraussetzungen gegeben sind, ist eine deutlich schnellere Konvergenz der Näherungswerte xn gegen eine Nullstelle von f zu beobachten. Im Folgenden sei f : [a, b] −→ R eine stetig differenzierbare reelle Funktion mit f ′(x) = 0 für alle x ∈ [a, b] (d. h. f ist insbesondere streng monoton wachsend oder streng monoton fallend, vgl. Satz 16.31c) und d)) und der Eigenschaft (26.3), wobei ohne Beschränkung der Allgemeinheit wieder (26.4) angenommen werden kann. Das Newton-Verfahren basiert dann auf der folgenden einfachen geometrischen Überlegung: Ausgehend von einem Startwert x0, d. h. einem ersten Näherungswert, für eine Nullstelle von f – z. B. ermittelt durch Sachüberlegungen, Probieren, Skizzieren des Graphen von f , Intervallhalbierungsverfahren usw. – wird an den Graphen von f im Punkt (x0, f (x0)) die Tangente f (x0)+ f ′(x0)(x − x0) angelegt und deren Schnittstelle x1 mit der x-Achse berechnet. Das heißt, der Wert x1 ist durch die lineare Gleichung f (x0)+ f ′(x0)(x − x0) = 0 eindeutig festgelegt und das Auflösen dieser Gleichung nach x liefert für x1 den Ausdruck x1 = x0 − f (x0) f ′(x0) . Entsprechend verfährt man mit dem neuen Näherungswert x1. Das heißt, an den Graphen von f wird im Punkt (x1, f (x1)) die Tangente f (x1)+ f ′(x1)(x − x1) 804 Kapitel 2626.4 Newton-Verfahren 0 f (x) x0x1x2x3x4 l lllll x Abb. 26.4: Näherungsweise Berechnung der Nullstelle x einer stetig differenzierbaren reellen Funktion f : [a, b] −→ R mit f (a)f (b) < 0 mittels Newton-Verfahren angelegt und durch Nullsetzen sowie anschließendes Auflösen der Gleichung nach x resultiert für x2 der Ausdruck x2 = x1 − f (x1) f ′(x1) . Wird dieses Vorgehen fortgesetzt, dann erhält man zur Berechnung von Näherungswerten xn+1 für eine Nullstelle von f die Rekursionsformel xn+1 = xn − f (xn) f ′(xn) (26.13) für alle n ∈ N0 (vgl. Abbildung 26.4). Die Formel (26.13) und die mit ihr ermittelte Folge (xn)n∈N0 von Näherungswerten wird häufig als Newton-Iteration bzw. Newton-Folge bezeichnet. Ist die Folge (xn)n∈N0 konvergent, d. h. gilt lim n→∞ xn = x (26.14) für ein x ∈ R, dann ist der Grenzwert x eine Nullstelle von f . Denn aus (26.13)–(26.14) sowie der Stetigkeit von f und f ′ folgt für n → ∞ x = x − f (x) f ′(x) (26.15) (vgl. Definition 15.2). Das heißt, es gilt f (x) = 0 (26.16) und die Folge (xn)n∈N0 konvergiert somit gegen eine Nullstelle x von f . Globale Konvergenz des Newton-Verfahrens Der folgende Satz formuliert Voraussetzungen, die hinreichend dafür sind, dass eine reelle Funktion f genau eine Nullstelle x besitzt und die mittels der Newton-Iteration (26.13) berechneten Näherungswerte (xn)n∈N0 monoton gegen diese Nullstelle konvergieren: Satz 26.5 (Konvergenz Newton-Verfahren – global) Es sei f : [a, b] −→ R eine zweimal stetig differenzierbare reelle Funktion mit den Eigenschaften f (a)f (b) < 0 und f ′(x) = 0 für alle x ∈ [a, b]. Dann besitzt f genau eine Nullstelle x ∈ (a, b) und die mittels der Newton- Iteration (26.13) und dem Startwert x0 ermittelte Folge von Näherungswerten (xn)n∈N0 konvergiert monoton a) wachsend gegen x für x0 ∈ [a, x], falls f (a) < 0 und f ′′(x) ≤ 0 für alle x ∈ [a, b], b) wachsend gegen x für x0 ∈ [a, x], falls f (a) > 0 und f ′′(x) ≥ 0 für alle x ∈ [a, b], c) fallend gegen x für x0 ∈ [x, b], falls f (a) < 0 und f ′′(x) ≥ 0 für alle x ∈ [a, b] und d) fallend gegen x für x0 ∈ [x, b], falls f (a) > 0 und f ′′(x) ≤ 0 für alle x ∈ [a, b]. 805 Kapitel 26 Intervallhalbierungs-, Regula-falsi- und Newton-Verfahren Dabei gilt für alle n ∈ N0 die Fehlerabschätzung |xn − x| ≤ |f (xn)| min x∈[a,b] |f ′(x)| = { |f (xn)| |f ′(a)| in den Fällen c) und d) |f (xn)| |f ′(b)| in den Fällen a) und b) (26.17) und es gibt ein K > 0, so dass |xn − x| ≤ K(xn−1 − x)2 (26.18) für alle n ∈ N gilt. Das heißt, die Folge (xn)n∈N0 konvergiert quadratisch gegen x. Beweis: Siehe z. B. Heuser [25], Seiten 407–409. Die Annahmen, unter denen der Satz 26.5 gültig ist, sind restriktiver als die Annahmen des Satzes 26.1 (Intervallhalbierungsverfahren) und des Satzes 26.3 (Regula-falsi- Verfahren), da sie voraussetzen, dass die Funktion f sowohl streng monoton als auch konvex oder konkav ist. Dafür stellen diese Annahmen aber auch sicher, dass die Funktion f genau eine Nullstelle x im Intervall (a, b) besitzt und die Folge der Näherungswerte (xn)n∈N0 monoton gegen diese Nullstelle konvergiert. Dieser Sachverhalt bedeutet jedoch nicht, dass bei Verletzung der Annahmen von Satz 26.5 das Newton-Verfahren nicht angewendet werden kann. Das Newton-Verfahren kann zur Berechnung von Nullstellen prinzipiell bei jeder stetig differenzierbaren reellen Funktion f : [a, b] −→ R herangezogen werden, die mindestens eine Nullstelle x besitzt. Denn dann können mittels der Newton-Iteration (26.13) Näherungswerte xn berechnet werden und im Falle der Konvergenz der Folge (xn)n∈N0 ist sichergestellt, dass dieser Grenzwert von (xn)n∈N0 eine Nullstelle von f ist (vgl. (26.15)–(26.16)). Allerdings ist in einer solchen Situation Vorsicht geboten. Denn es ist dann auch möglich, dass bei „unglücklicher Wahl“ des Startwerts x0, d. h. bei einem Startwert, der zu weit von der gesuchten Nullstelle x entfernt ist, eines der folgenden drei Szenarien eintritt: a) Die Folge (xn)n∈N0 ist unbeschränkt und der Abstand der Näherungswerte xn zur Nullstelle x wächst damit über alle Grenzen. b) Die Folge (xn)n∈N0 ist beschränkt, aber nicht konvergent. Dies ist z. B. der Fall, wenn (xn)n∈N0 zwischen zwei Werten oszilliert (vgl. Beispiel 26.8). c) Die Folge (xn)n∈N0 ist konvergent und liefert damit eine Nullstelle von f . Allerdings kann dies bei der Existenz von mehreren Nullstellen auch eine andere als die gesuchte Nullstelle x sein. Lokale Konvergenz des Newton-Verfahrens In der Praxis geht man daher häufig so vor, dass für eine stetig differenzierbare reelle Funktion f : [a, b] −→ R auf die explizite Überprüfung der Voraussetzungen von Satz 26.5 verzichtet wird und ausgehend von einem Startwert x0 mittels der Newton-Iteration (26.13) sukzessive Näherungswerte x1, x2, . . . berechnet werden. Es ist dann allerdings von entscheidender Bedeutung, dass der Startwert x0 der Newton- Iteration (26.13) bereits hinreichend nahe bei der gesuchten Nullstelle x liegt (vgl. auch Beispiel 26.8). Es gilt z. B. der folgende Satz, der ganz ohne Konvexitäts- oder Konkavitätsbedingungen auskommt und besagt, dass das Newton- Verfahren „funktioniert“, wenn nur der Startwert x0 „gut genug“ ist: Satz 26.6 (Konvergenz Newton-Verfahren – lokal) Es sei f : [a, b] −→ R eine zweimal stetig differenzierbare reelle Funktion mit f ′(x) = 0 für alle x ∈ [a, b] und einer Nullstelle bei x ∈ (a, b). Dann gibt es ein δ > 0, so dass die mittels der Newton-Iteration (26.13) ermittelte Folge von Näherungswerten (xn)n∈N0 für jeden beliebigen Startwert x0 ∈ [x − δ, x + δ] gegen die Nullstelle x konvergiert. Beweis: Die reelle Funktion f ist gemäß Annahme zweimal stetig differenzierbar und besitzt die Nullstelle x. Für die Funktion g : [a, b] −→ R, x %→ g(x) := x − f (x) f ′(x) folgt somit, dass sie stetig differenzierbar ist und g(x) = x gilt. Das heißt, dass x ein Fixpunkt von g ist, und für die erste Ableitung von g erhält man g′(x) = 1 − ( f ′(x) )2 − f (x)f ′′(x) (f ′(x))2 = f (x)f ′′(x) (f ′(x))2 und damit insbesondere g′(x) = 0. Daraus folgt zusammen mit der Stetigkeit von g′, dass es ein q < 1 und ein δ > 0 gibt, so dass |g′(x)| ≤ q für alle x ∈ [x− δ, x+ δ] gilt. Zusammen mit 806 Kapitel 2626.4 Newton-Verfahren dem Mittelwertsatz der Differentialrechnung (vgl. Satz 16.28) impliziert dies die Abschätzung |g(x)− x| = |g(x)− g(x)| ≤ max x∈[x−δ,x+δ] |g′(x)| · |x − x| ≤ q|x − x| für alle x ∈ [x − δ, x+δ]. Es gilt somit g(x) ∈ [x−δ, x+δ] für alle x ∈ [x − δ, x + δ] und die Funktion g|[x−δ,x+δ], d. h. die Restriktion von g auf das Intervall [x − δ, x + δ] ist damit eine Kontraktion mit der Kontraktionskonstanten q. Mit dem Fixpunktsatz von Banach (vgl. Satz 15.32) folgt daher, dass die Folge (xn)n∈N0 mit xn+1 = g(xn) = xn − f (xn)f ′(xn) für jeden beliebigen Startwert x0 ∈ [x − δ, x + δ] gegen den Fixpunkt x von g|[x−δ,x+δ], also die Nullstelle von f , konvergiert. Wie der Satz 26.6 zeigt, ist das Newton-Verfahren ohne zusätzliche Konvexitäts- oder Konkavitätsannahmen wenigstens noch ein lokal konvergentes Verfahren. Das heißt, die Konvergenz der Folge (xn)n∈N0 gegen eine Nullstelle der Funktion f ist garantiert, wenn der Startwert x0 nur hinreichend nahe bei der Nullstelle liegt. Die eigentliche „Kunst“ der Anwendung des Newton-Verfahrens besteht somit darin, einen Startwert x0 zu finden, der bereits nahe genug bei der gesuchten Nullstelle liegt. Wie bereits erwähnt, kann ein solcher erster Näherungswert x0 z. B. durch Sachüberlegungen, Probieren, Skizzieren des Graphen von f oder das Intervallhalbierungsverfahren bestimmt werden. Falls dann die aus dem Startwert x0 mittels der Newton-Iteration (26.13) resultierende Folge (xn)n∈N0 konvergiert, ist ihr Grenzwert die gesuchte Nullstelle x von f . Bei praktischen Anwendungen wird man das Newton- Verfahren abbrechen, wenn ein vorgegebenes Abbruchkriterium – wie z. B. |f (xn)| < ε oder |xn+1 − xn| < ε für ein hinreichend kleines ε > 0 – erfüllt ist. Zum Beispiel würde das Abbruchkriterium |xn+1 − xn| < 5 · 10−9 bedeuten, dass die beiden hintereinanderfolgenden Näherungswerte xn+1 und xn – und damit näherungsweise auch xn und die gesuchte Nullstelle x – auf acht Dezimalstellen übereinstimmen. Falls die Folge (xn)n∈N0 konvergiert, liegt quadratische Konvergenz vor (vgl. (26.18)). Das heißt, mit jedem Iterationsschritt verdoppelt sich die Anzahl der korrekten Nachkommastellen der Näherungswerte xn. Daher liefert das Newton- Verfahren im Konvergenzfall deutlich schneller gute Näherungswerte als das Intervallhalbierungsverfahren (vgl. Abschnitt 26.2) oder das Regula-falsi-Verfahren (vgl. Abschnitt 26.3). In der Praxis wird man daher das Newton-Verfahren vorziehen, wenn die Funktion f : [a, b] −→ R zweifach stetig differenzierbar und die Berechnung der Ableitungswerte f ′(xn) nicht zu aufwendig ist. Eine weitere Stärke des Newton-Verfahrens ist, dass kleine Rundungsfehler bei der Berechnung der Näherungswerte xn keinen entscheidenden Einfluss auf die Konvergenz des Verfahrens haben. Denn jeder Wert in der Nähe eines Näherungswertes xn kann als neuer Startwert aufgefasst werden. Man sagt daher, das Newton- Verfahren ist selbstkorrigierend. Beispiel 26.7 (Berechnung interner Zinsfuß bei diskreten Auszahlungen) Betrachtet wird eine Investition I mit den vier Auszahlungen 3€, 3€, 3€, 103€ zu den Zeitpunkten t = 1, 2, 3, 4 und den Aufwendungen 98€ zum Zeitpunkt t = 0. Der interne Zinsfuß dieser Investition ist durch den Zinssatz ρ > 0 gegeben, für den der Barwert der Auszahlungen gleich den Aufwendungen zum Zeitpunkt t = 0 ist. Das heißt, bei diskreter Verzinsung berechnet sich der interne Zinsfuß ρ > 0 der Investition I als Lösung der Gleichung 3€ · (1 + ρ)−1 + 3€ · (1 + ρ)−2 + 3€ · (1 + ρ)−3 + 103€ · (1 + ρ)−4 = 98€ und bei stetiger Verzinsung als Lösung der Gleichung 3€ · e−ρ+3€ · e−2ρ+3€ · e−3ρ+103€ · e−4ρ=98€ (vgl. Beispiel 11.46 und Beispiel 14.33). Die Newton- Iterationen zur numerischen Lösung dieser beiden Gleichungen lauten ρn+1 = ρn − f (ρn) f ′(ρn) = ρn− 3(1+ρn)−1+3(1+ρn)−2+3(1+ρn)−3+103(1+ρn)−4−98 −3(1+ρn)−2−6(1+ρn)−3−9(1+ρn)−4−412(1+ρn)−5 bzw. ρn+1 = ρn − f (ρn) f ′(ρn) = ρn − 3e −ρn + 3e−2ρn + 3e−3ρn + 103e−4ρn − 98 −3e−ρn − 6e−2ρn − 9e−3ρn − 412e−4ρn . 807 Kapitel 26 Intervallhalbierungs-, Regula-falsi- und Newton-Verfahren diskrete Verzinsung stetige Verzinsung n f (ρn) f ′(ρn) ρn f (ρn) f ′(ρn) ρn 0 −1,629895 −354,434852 0,04 −1,916711 −367,486591 0,04 1 0,017903 −362,255564 0,035401 0,019753 −375,087189 0,034784 2 0,000002 −362,170412 0,035451 0,000002 −375,009659 0,034837 3 0,000000 −362,170402 0,035451 0,000000 −375,009651 0,034837 Tabelle 26.1: Näherungswerte für das Beispiel 26.7. Mit dem Startwert ρ0 = 4% erhält man für den internen Zinsfuß ρ die Näherungswerte in Tabelle 26.1. Bei dieser Investition beträgt bei diskreter Verzinsung der interne Zinsfuß ρ = 3,545% und bei stetiger Verzinsung ρ = 3,484%. Der interne Zinsfuß ist ein Hilfsmittel bei der Entscheidung, ob eine Investition vorteilhaft ist oder nicht. In der Investitionsrechnung wird eine Investition in der Regel als vorteilhaft beurteilt, wenn der interne Zinsfuß höher ist als der Kalkulationszinssatz (d. h. die subjektive Mindestverzinsungsforderung eines Anlegers an seine Investition). Für die Berechnung des internen Zinsfußes bei einem kontinuierlichen Auszahlungsstrom und einer stetigen Verzinsung mittels Newton-Verfahren siehe Beispiel 19.8b). Das folgende Beispiel zeigt, dass die Konvergenz des Newton-Verfahrens bei Verletzung der Konvexitäts- oder Konkavitätsvoraussetzungen von Satz 26.5 entscheidend von der Qualität des Startwerts x0 abhängt: Beispiel 26.8 (Wahl des Startwertes beim Newton-Verfahren) Die Gleichung x3 − 2x + 2 = 0 besitzt als Gleichung dritten Grades mindestens eine reelle Lösung (vgl. Folgerung 4.5). Mit f (x) := x3 −2x+2 und f ′(x) = 3x2 − 2 erhält man die Newton-Iteration xn+1 = xn − x 3 n − 2xn + 2 3x2n − 2 für alle n ∈ N0 und bei Wahl des Startwerts x0 = 0 resultieren die Näherungswerte x1 = 1, x2 = 0, x3 = 1, x4 = 0, x5 = 1, . . . usw. Das heißt, bei dem Startwert x0 = 0 erhält man bei Verwendung des Newton-Verfahrens eine divergente, zwischen den Werten 0 und 1 oszillierende Folge von Näherungswerten x0, x1, x2, . . .. Eine analoge Aussage gilt für den Startwert x0 = 1. Wählt man hingegen mit x0 = −1,2 einen näher bei der Nullstelle liegenden Startwert, dann konvergiert die Folge (xn)n∈N0 gegen die Nullstelle. Man erhält die folgenden Näherungswerte: Newton-Verfahren n f (xn) f ′(xn) xn 0 2,672 2,32 −1,2 1 −6,30301234 14,5918193 −2,35172414 2 −1,23579499 9,05653822 −1,91976893 3 −0,10469481 7,54064335 −1,78331558 4 −0,00102862 7,39266359 −1,76943151 5 −0,00000010 7,39118645 −1,76929237 6 0,00000000 7,39118630 −1,76929235 7 0,00000000 7,39118630 −1,76929235 Bei Wahl des Startwerts x0 = −1,2 konvergieren die Näherungswerte xn schnell gegen die Nullstelle. Nach sechs Iterationen resultiert mit x = −1,76929235 ein bis auf acht Nachkommastellen genauer Näherungswert (vgl. Abbildung 26.5). 26.5 Sekantenverfahren und vereinfachtes Newton-Verfahren Das „größte Problem“ bei der Anwendung des Newton- Verfahrens besteht oftmals in der Berechnung der ersten Ableitungswerte der Funktion f . In der Praxis wird deshalb häufig die Ableitung f ′(xn) durch den Differenzenquotienten f (xn)− f (xn−1) xn − xn−1 (26.19) approximiert. Geometrisch bedeutet dies, dass die Tangente im Punkt (xn, f (xn)) durch die Sekante durch die Punkte (xn−1, f (xn−1)) und (xn, f (xn)) ersetzt und anstelle der 808 Kapitel 2626.5 Sekantenverfahren und vereinfachtes Newton-Verfahren −2 −1 1 2 −6 −4 −2 2 4 6 f (x) x0 x1 x2 x3 x4 l l l −2 −1 1 2 −6 −4 −2 2 4 6 f (x) x0x1 x2 x3 x4 l ll l Abb. 26.5: Divergenz des Newton-Verfahrens bei der Lösung der Gleichung x3 −2x+2 = 0 mit dem Startwert x0 = 0 (links) und Konvergenz des Newton-Verfahrens bei Verwendung des Startwerts x0 = −1,2 (rechts) Newton-Iteration (26.13) die Rekursionsformel xn+1 = xn − f (xn)f (xn)−f (xn−1) xn−xn−1 = xn − xn − xn−1 f (xn)− f (xn−1)f (xn) = f (xn)xn−1 − f (xn−1)xn f (xn)− f (xn−1) für alle n ∈ N mit den beiden Startwerten x0 und x1 verwendet wird. Diese Methode weist große Ähnlichkeit zum Regula-falsi-Verfahren auf (vgl. (26.8)) und anstelle von Newton-Verfahren spricht man von Sekantenverfahren (vgl. Beispiel 26.9)). Eine andere Möglichkeit zur Verminderung des Rechenaufwands beim Newton-Verfahren besteht darin, dass die erste Ableitung nur an der Stelle x0 berechnet und in jedem Iterationsschritt f ′(x0) anstelle von f ′(xn) verwendet wird. Geometrisch bedeutet dies, dass die Tangente im Punkt (xn, f (xn)) durch die Gerade durch den Punkt (xn, f (xn))mit der Steigung f ′(x0) ersetzt und anstelle der Newton-Iteration (26.13) die Rekursionsformel xn+1 = xn − f (xn) f ′(x0) für alle n ∈ N verwendet wird. Dieses Vorgehen wird als vereinfachtes Newton-Verfahren bezeichnet. Bei der Verwendung des Sekantenverfahrens und des vereinfachten Newton-Verfahrens ist zu beachten, dass sich bei einer Approximation der Ableitung f ′(xn) durch den Differenzenquotienten (26.19) bzw. die Ableitung f ′(x0) die Konvergenzgeschwindigkeit im Vergleich zum Newton- Verfahren oftmals deutlich verringert (vgl. Beispiel 26.9 und Beispiel 26.10). Beispiel 26.9 (Newton- und Sekantenverfahren) Gegeben sei die stetig differenzierbare reelle Funktion f : [0, 2] −→ R, x %→ ex − 2 mit f (0) < 0 und f (2) > 0. Das heißt, die Funktion f besitzt im Intervall [0, 2] eine Nullstelle. Wegen f ′(x)=ex ist die Newton-Iteration gegeben durch xn+1 = xn − e xn − 2 exn für alle n ∈ N0 und für das Sekantenverfahren erhält man die Rekursionsformel xn+1 = xn − xn − xn−1 exn − exn−1 e xn für alle n ∈ N. Mit dem Startwert x0 = 2 für das Newton- Verfahren und den beiden Startwerten x0 = 2 und x1 = 1 809 Kapitel 26 Intervallhalbierungs-, Regula-falsi- und Newton-Verfahren Newton-Verfahren Sekantenverfahren n f (xn) f ′(xn) xn f (xn) xn 0 5,38905610 7,38905610 2 5,38905610 2 1 1,56324115 3,56324115 1,27067057 0,71828183 1 2 0,29781186 2,29781186 0,83195730 0,33081461 0,84621782 3 0,01849177 2,01849177 0,70235058 0,04402427 0,71492055 4 0,00008445 2,00008445 0,69318940 0,00323930 0,69476552 5 0,00000000 2,00000000 0,69314718 0,00003510 0,69316473 6 0,00000000 2,00000000 0,69314718 0,00000003 0,69314719 7 0,00000000 2,00000000 0,69314718 0,00000000 0,69314718 Tabelle 26.2: Näherungswerte für das Beispiel 26.9. für das Sekantenverfahren erhält man die Näherungswerte in der Tabelle 26.2. Man erkennt, dass die Näherungswerte xn bei beiden Verfahren relativ schnell konvergieren und man beim Newton-Verfahren bereits nach fünf Iterationen und beim Sekantenverfahren nach sechs Iterationen mit x = 0,69314718 einen bis auf acht Nachkommastellen genauen Näherungswert für die gesuchte Nullstelle erhält (vgl. auch Abbildung 26.6). 1 2 −2 2 4 6 f (x) x0x1x2x3x4x5 l lll 1 2 −2 2 4 6 f (x) x0x1x2x3x4x5 l llll Abb. 26.6: Berechnung der Nullstelle der reellen Funktion f : [0, 2] −→ R, x %→ ex − 2 mittels Newton-Verfahren mit Startwert x0 = 2 (links) und dem Sekantenverfahren mit den Startwerten x0 = 2 und x1 = 1 (rechts) Beispiel 26.10 (Newton- und vereinfachtes Newton-Verfahren) Zu berechnen seien die Schnittstellen der beiden stetig differenzierbaren Funktionen g(x) = x2 und h(x) = sin(x) im Intervall [0, 3]. Das heißt, es sind die Lösungen der Gleichung g(x)− h(x) = x 2 − sin(x) = 0 bzw. die Nullstelle der Funktion f (x) := x2 − sin(x) im Intervall [0, 3] zu berechnen. Offensichtlich ist der Wert 0 bereits eine Nullstelle von f . Wegen f ′(x) = 12 −cos(x) 810 Kapitel 2626.5 Sekantenverfahren und vereinfachtes Newton-Verfahren 1 2 3 −0.5 0 0.5 1 1.5 f (x) x0x1x2x3x4x5 l ll 1 2 3 −0.5 0 0.5 1 1.5 f (x) x0x1x2x3x4x5 l llll Abb. 26.7: Berechnung der Schnittstelle der beiden reellen Funktionen g(x) = x2 und h(x) = sin(x) im Intervall [0, 3] mittels Newton-Verfahren mit Startwert x0 = 3 (links) und vereinfachtem Newton-Verfahren mit Startwert x0 = 3 (rechts) Newton-Verfahren Vereinfachtes Newton-Verfahren n f (xn) f ′(xn) xn f (xn) xn 0 1,35887999 1,48999250 3 1,35887999 3 1 0,17479021 0,99444751 2,08799541 0,17479021 2,08799541 2 0,01383880 0,83483765 1,91222926 0,06423901 1,97068595 3 0,00012971 0,81917261 1,89565263 0,02675846 1,92757231 4 0,00000001 0,81902254 1,89549428 0,01165830 1,90961352 5 0,00000000 0,81902252 1,89549427 0,00517439 1,90178912 6 0,00000000 0,81902252 1,89549427 0,00231513 1,89831636 7 0,00000000 0,81902252 1,89549427 0,00103953 1,89676257 Tabelle 26.3: Näherungswerte für das Beispiel 26.10. ist die Newton-Iteration gegeben durch xn+1 = xn − xn 2 − sin(xn) 1 2 − cos(xn) für alle n ∈ N0, und für das vereinfachte Newton- Verfahren erhält man die Rekursionsformel xn+1 = xn − xn 2 − sin(xn) 1 2 − cos(x0) für alle n ∈ N0. Mit dem Startwert x0 = 3 erhält man für das Newton-Verfahren und das vereinfachte Newton- Verfahren die Näherungswerte in der Tabelle 26.3. Die Näherungswerte xn beim Newton-Verfahren konvergieren schnell und bereits nach fünf Iterationen erhält man mit x = 1,89549427 einen bis auf acht Nachkommastellen genauen Näherungswert für die gesuchte Nullstelle. Dagegen konvergiert das vereinfachte Newton-Verfahren viel langsamer. Nach sieben Iterationen stimmen erst zwei Nachkommastellen mit der richtigen Lösung überein und ein bis auf acht Nachkommastellen genauer Näherungswert resultiert erst nach 23 Iterationen (vgl. auch Abbildung 26.7). 811

Chapter Preview

References

Zusammenfassung

"uneingeschränkt zu empfehlen, [...] insbesondere als Einstiegslektüre im Bachelor-Studium". In: Studium, 2013.

So zentral die Rolle der Mathematik in der Ökonomie ist, so schwer tun sich die Studierenden mit mathematischen Methoden und Konzepten. Umso wichtiger ist es, die Studierenden bei ihrem aktuellen Wissensstand abzuholen und vorsichtig an den Stoff heranzuführen. Diesem Ziel verschreibt sich dieses Lehrbuch. Es führt mit vielen interessanten Beispielen aus der Ökonomie, kurzen Anekdoten und einem modernen mehrfarbigen Design in die zentralen mathematischen Methoden für ein erfolgreiches Wirtschaftsstudium ein, ohne dabei auf mathematische Klarheit sowie die notwendige Formalität und Stringenz zu verzichten. Auch nach dem Studium ist dieses Buch ein wertvoller Begleiter bei der mathematischen Lösung wirtschaftswissenschaftlicher Problemstellungen.

Aus dem Inhalt:

* Mathematische Grundlagen

* Lineare Algebra

* Matrizentheorie

* Folgen und Reihen

* Reellwertige Funktionen in einer und mehreren Variablen

* Differential- und Integralrechnung

* Optimierung mit und ohne Nebenbedingungen

* Numerische Verfahren

Dozenten finden auf der Website zum Buch unter www.vahlen.de zusätzliche Materialien zum Download.

"Indem Sie den Lehrstoff schrittweise aufbereiten und den Leser bei seinem aktuellen Wissenstand abholen, gelingt es ihnen [den Autoren], auch komplexe Zusammenhänge leicht nachvollziehbar zu vermitteln. Geschickt bauen sie immer wieder kurze Anekdoten, historische Ereignisse und überraschende Erkenntnisse in den Text ein". In: Studium, 2013.

Prof. Dr. Michael Merz ist Inhaber des Lehrstuhls für Mathematik und Statistik in den Wirtschaftswissenschaften an der Universität Hamburg. Prof. Dr. Mario V. Wüthrich forscht und lehrt am Department für Mathematik der ETH Zürich.