Algorithmensammlung: Numerik: Dividierte Differenzen

Aus Wikibooks

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  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