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

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

Aufgabe 10: (Zum Newton-Verfahren) Diskutiere das Verhalten der Newton-Iteration für die Funktion f(x) = x/\sqrt{|x|} = sign(x) \sqrt{|x|} . Warum ergibt sich kein Widerspruch zu Satz III.15? (1)

Aufgabe 11: (a priori Abschätzungen beim Newton-Verfahren) Viele Computersprachen benutzen intern zur Berechnung einer Quadratwurzel \sqrt{X} die Newton-Iteration für f(x) = x^{2} − X = 0 , die mit den Grundrechenarten durchgeführt werden kann. Durch sukzessives Multiplizieren mit oder Teilen durch 4 (im Binärsystem sehr einfach durchzuführen) kann dieses Problem auf das Intervall 1 ≤ X ≤ 4 reduziert werden.

a) Zeige durch eine einfache graphische Betrachtung, daß die Newton-Iteration

x → Φ(x) = x − \frac{f(x)}{f′(x)} = \frac{1}{2} ( x + \frac{X}{x} )

für jeden Startwert x_{0} > \sqrt{X} monoton fallend konvergiert. (1)

b) Wähle x_{0} = (X + 1)/2 (dieser Punkt x_{0} = Φ(1) = Φ(X) würde sich als Iterationswert ergeben, wenn man mit einem Randwert des Intervalls 1 ≤ \sqrt{X} ≤ X startet). Die Newton-Iteration x_{i+1} = Φ(x_{i}) vollzieht sich dann auf dem Intervall [\sqrt{X}, (X + 1)/2] . Zeige, daß sich der relative Fehler durch

\frac{|x_{i} − \sqrt{X} |}{\sqrt{X}} ≤ 2 (\frac{(X − 1)^{2}}{8 \sqrt{2 X^{3/2} (X + 1)}})^{(2^{i})} ≤^{(∗)} 2 (\frac{9}{8 \sqrt{80}})^{(2^{i})}

abschätzen läßt. Verwende für (∗) (ohne Beweis), daß g(X) = (X − 1)^{2}/\sqrt{X^{3/2} (X + 1)} für X ≥ 1 monoton in X wächst. (4)

c) Nach wievielen Iterationsschritten kann eine relative Genauigkeit von 16 Dezimalstellen garantiert werden? (1)

d) Führe die Iteration für X = 4 durch und vergleiche die obige a priori Abschätzung mit dem wirklichen Fehler. (2)

Aufgabe 12: (Zum Newton-Verfahren bei mehrfachen Nullstellen) Es sei x^{∗} eine q-fache Nullstelle einer hinreichend glatten Funktion f, d.h., es gelte

f(x^{∗}) = f′(x^{∗}) = … = f^{(q−1)}(x^{∗}) = 0 und f^{(q)}(x^{∗}) ≠ 0 .

a) Zeige (Taylor-Entwicklung): f^{(i)}(x^{∗} + h) = \frac{h^{q−i}}{(q − i)!} (f^{(q)}(x^{∗}) + o(1)) , i = 0,..., q. (2)

Zur Erinnerung: das Landau-Symbol o(1) steht für eine Funktion mit lim_{h→0} o(1) = 0 .

b) Zeige: auf einer Umgebung von x^{∗} ist ψ(x) = f(x)/f′(x) stetig mit ψ(x^{∗}) = lim_{x→x^{∗}} ψ(x) = 0 ,

weiterhin stetig differenzierbar, und es gilt ψ′(x^{∗}) = lim_{x→x^{∗}} ψ′(x) = 1/q . Aufgabenteil a) ist hierbei hilfreich. (2)

c) Folgere, daß das Newton-Verfahren Φ(x) = x−f(x)/f′(x) auch bei q-fach entarteten Nullstellen immer lokal konvergiert, für q > 1 allerdings nur linear. (1)

d) Zeige, daß die Banach-Iteration mit Φ(x) = x − q f(x)/f′(x) (modifiziertes Newton-Verfahren) wieder quadratisch konvergiert. (1)

Aufgabe 13: (Zum Steffensen-Verfahren) Unter welcher Bedingung (an f′(x^{∗})) ist die Differenz im Nenner des Steffensen-Verfahrens x →

x − \frac{f(x)^{2}}{f(x + f(x)) − f(x)} in der Nähe der Lösung x^{∗} durch Auslöschung gefährdet? (2)

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