Algorithmensammlung: Numerik: Dividierte Differenzen

Aus Wikibooks
Wechseln zu: Navigation, Suche

Algorithmensammlung: Numerik

Dividierte Differenzen[Bearbeiten]

Das Schema der dividierten Differenzen wird in der Polynominterpolation zur Bestimmung der Koeffizienten für den Newtonschen Algorithmus verwendet. Für weitere Informationen siehe Wikipedia-logo-v2.svg Dividierte Differenzen.

Die Auswertung der ermittelten Stützstellen erfolgt mithilfe des Horner-Schemas.

Matlab[Bearbeiten]

Siehe Octave.

Octave[Bearbeiten]

Dies ist eine rekursive Implementierung. Für eine Implementierung mit Schleifen siehe Hermiteinterpolation.

function coeff = divdiff(x, y, x0, x1)
	if ! exist('x0')
		coeff = arrayfun(@(n) divdiff(x, y, 1, n), 1:length(x));
	else if x0 == x1 
		coeff = y(x0);
	else
		coeff = (divdiff(x, y, x0 + 1, x1) - \
			divdiff(x, y, x0, x1 - 1)) / \
			(x(x1) - x(x0));
	end;
end;

Mithilfe der expliziten Formel für dividierte Differenzen kann man auch ganz auf Schleifen und rekursive Aufrufe verzichten:

function coeff = divdiff(x, y)
	divs = repmat(x, length(x), 1);
	divs = divs - divs';
	divs(logical(eye(size(divs)))) = 1;
 
	coeff = arrayfun(@(n) sum(y(1:n) ./ prod(divs(1:n, 1:n), 1)), 1:length(x));
end