Numerik I Wintersemester 97/98 Dr. Walter Oevel 18. 11. 1997

Ü b u n g s b l a t t 5

Aufgabe 14: (Geometrische Konstruktion eines kubisches Verfahrens)

a) Sei x_{i} ein Punkt in der Nähe einer einfachen Nullstelle von f(x). Approximiere f(x) durch das Taylor-Polynom T (x) := f(x_{i})+f′(x_{i}) (x−x_{i})+ \frac{1}{2} f′′(x_{i}) (x−x_{i})^{2}. Wähle als Nachfolger x_{i+1} die “richtige” Nullstelle von T (x) (unter der Voraussetzung f′′(x_{i}) ≠ 0). Zeige, daß die Abbildung Φ : x_{i} → x_{i+1} gegeben ist durch

Φ(x) = x − \frac{f′(x)}{f′′(x)} (1 − \sqrt{1 − \frac{2 f(x) f′′(x)}{f′(x)^{2}}} ) .  (2)

b) Zeige, daß dieses Verfahren mindestens quadratisch gegen einfache Nullstellen konvergiert. (3)

Anmerkung: es konvergiert sogar kubisch, die Berechnung von Φ′′ ist aber sehr mühselig.

c) Entwickle die Wurzel (\sqrt{1 − ϵ} = 1 − ϵ/2 − ϵ^{2}/8 − ⋯). Welches Verfahren ergibt sich durch \sqrt{1 − ϵ} ≈ 1 − ϵ/2 ? Zeige, daß das sich in der nächsten Approximation ergebende Verfahren

Φ(x) = x − \frac{f(x)}{f′(x)} − \frac{1}{2} \frac{f(x)^{2}f′′(x)}{f′(x)^{3}}

kubisch konvergiert. Anmerkung: effizient differenzieren ! (3)

Aufgabe 15: (Zur Konvergenzordnung des Sekantenverfahrens) Die Fehlerschranken E_{i} ≥ |x_{i} − x^{∗}| des Sekantenverfahrens pflanzen sich nach Vorlesung mittels E_{i+1} = C E_{i} E_{i−1} mit einer Konstanten C fort. Es sei p der “goldene Schnitt” p = (\sqrt{5}+1)/2 ≈ 1.618... mit der Eigenschaft p − 1 = 1/p.

a) Transformiere die Konstante C fort, indem statt der E_{i} die skalierten Fehler Ẽ_{i} = CE_{i} betrachtet werden. Es folgt Ẽ_{i+1} = Ẽ_{i}Ẽ_{i−1} . Setze a_{i} = ln(Ẽ_{i+1}/Ẽ_{i}^{p}) und zeige a_{i} = −a_{i−1}/p. Schließe, daß die Folge (a_{i}) für jeden Startwert a_{0} gegen Null konvergiert. (2)

b) Folgere lim_{i→∞} Ẽ_{i+1}/Ẽ_{i}^{p} = 1 , sodaß sich für großes i mit E_{i+1} ≈ C^{p−1}E_{i}^{p} als Konvergenzordnung

des Sekantenverfahrens der goldene Schnitt p ergibt. (1)

Aufgabe 16: (Zum Newton- und Sekantenverfahren) Das Sekantenverfahren zur Bestimmung der Nullstellen einer Funktion führt auf die Iteration

x_{i+1} = \frac{x_{i} x_{i−1} + 1}{x_{i} + x_{i−1} − 1} .

a) Zu welcher Iteration würde das Newton-Verfahren für diese Funktion führen? (2)

b) Was sind die Nullstellen dieser Funktion? (2)

c) Bestimme die Funktion bis auf eine multiplikative Konstante. (2)

Die Fragen a) und b) können leicht beantwortet werden, ohne die Funktion zu kennen.

Aufgabe 17: (Zum Horner-Schema) Zeige, daß für das Polynom p(x) = a_{0} x^{n} + ⋯ + a_{n} mit den im Horner-Schema

b_{0} := a_{0} ; for i := 1 to n do b_{i} := x_{0} b_{i−1} + a_{i} ;

definierten Größen b_{i} gilt: \frac{p(x) − p(x_{0})}{x − x_{0}} = b_{0} x^{n−1} + b_{1} x^{n−2} + ⋯ + b_{n−2} x + b_{n−1} . (3)

Anleitung: Multiplikation mit x − x_{0} und Koeffizientenvergleich.

Abgabe: Mittwoch, 26. 11. 97, in den Übungsgruppen