Blog

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.