Schreiben Sie ein m-File („u41.m“), in dem Sie ein Newton-Verfahren zur iterativen Lösung einer nichtlinearen Gleichung programmieren. Die Funktion, die das Newton-Verfahren enthält, soll folgende Struktur haben:
function [x, it] = newton(x_0, tol, maxstep, f) % % x : approximierte Nullstelle % it : Anzahl der Iterationen % x_0 : Startwert der Iteration % tol: Toleranz % f : Funktion, deren Nullstelle bestimmt werden soll
Der Rückgabewert muss dann erfüllen. Die als Parameter übergebene Funktion
wird in einem eigenen m-File realisiert. Sie bekommt die Auswertungsstelle(n) als Eingabe und gibt Funktionswert(e) und Ableitung(en) zurück. Der Aufruf erfolgt über newton(x_0, tol, maxstep, @f). Es hilft auch der feval-Befehl
Testen Sie das Programm für
a)
b)
Verwenden Sie zur Auswertung der Polynome das Horner-Schema. Beobachten Sie das Konvergenzverhalten, indem Sie sich den absoluten Fehler nach 1, 2, …, 10 Iterationen ausgeben lassen. Was fällt dabei auf? Wie können Sie die Konvergenz für verbessern?
Lösung
Umstellen der Polynome:
Ableitungen:
Matlab-Code
u41.m
format long; [x1, it1] = newton(2, eps, 20, @p1)
newton.m
function [x, it] = newton(x_0, tol, maxstep, f) % % x: approx. Nullstelle % it: Anzahl Iterationen % x_0: Startwert der Iteration % tol: Toleranz % f: Funktion, deren Nullstelle bestimmt werden soll x1 = x_0; it = 0; dev = zeros(10, 1); gamma = 1; % mit Korrektur für p2 while (it < maxstep) && (abs(f(x1)) > tol) it = it + 1; [y, dy] = f(x1); x = x1 - gamma * y / dy; if (it <= 10) dev(it) = x - 1.5; % dev(it) = x + 1; end x1 = x; end dev
p1.m
function [y, dy] = p1(x) y = -45/16 + x * (9/2 + x * (7/2 - x * (2 + x))); dy = 9/2 + x * (7 - x * (6 + 4 * x));
p2.m
function [y, dy] = p2(x) y = 2 + x * (5 + x * (4 + x)); dy = 5 + x * (8 + 3 * x);
Test für das erste Polynom
Verwendete Parameter:
Ergebnis:
Entwicklung des absoluten Fehlers:
Beobachtung: Die Konvergenz ist quadratisch.
Test 1 für das zweite Polynom
Verwendete Parameter:
Ergebnis:
Entwicklung des absoluten Fehlers:
Beobachtung: Die Konvergenz ist nur linear. Das liegt daran, dass die Steigung der Funktion in der Umgebung der Nullstelle sehr klein ist:
Zur Verbesserung der Konvergenz kann man das Newton-Verfahren abwandeln:
Dann gilt für die Konvergenz:
Dabei ist die Vielfachheit der Nullstelle.
Faktorisierung des gegebenen Polynoms:
Die Nullstelle ist also doppelt. Die Konvergenz ist am schnellsten, wenn gilt:
Test 2 für das zweite Polynom
Verwendete Parameter:
Ergebnis:
Entwicklung des absoluten Fehlers:
Beobachtung: Die Konvergenz des abgewandelten Verfahrens ist quadratisch.