Newton-Interpolationspolynom - Datenpunkt ergänzen

Hallo,

ich muss es u.a. ermöglichen, dass man zu einem Interpolationspolynom, geg. als Koeffizientenvektor c und als Vektor der Datenpunkte, nachträglich einen Punkt hinzufügen kann.

Das bereitet mir nun Sorgen. Es gibt ja dieses rekursive Verfahren mit den "divided differences" nach Newton, bei denen man von Zwischenergebnissen die oberste Reihe als Koeffizientenvektor ausmacht, ich hab das auch mal in Scilab implementiert:

// Interpoliert eine gegebene Menge von Datenpunkten unter Verwendung des
// Newton-Interpolationspolynoms.
// x: Ein Vektor mit den x-Werten der Datenpunkte
// y: Ein Vektor mit den y-Werten der Datenpunkte
// c: Die Koeffizienten des Polynoms zur Basis 1, (x - x1), ...
function c = interpolateRecursive(x, y)
	n = length(x);
	c = zeros(n, 1);
	c(1) = y(1);

	if n > 1
		c(2:n) = interpolateRecursive( x(2:n), (y(2:n) - y(1)) ./ (x(2:n) - x(1)) );
	end
endfunction

Ist es möglich, weitere Datenpunkte hinzuzufügen, wenn man am Ende ein Polynom nur noch durch c und seine Datenpunkte gegeben hat? Die ganzen Zwischenergebnisse neu auszurechnen ist sinnlos, weil dann kann ich gleich das ganze Verfahren nochmal neu anwerfen.
Die ganzen Zwischenergebnisse für jedes Polynom zu speichern, um sie nachher verwenden zu können, kann ja auch die Lösung nicht sein.

Ich mach sicherheitshalber noch ne Kurzzusammenfassung: Ich hab ein Interpolationspolynom der Form
c1 + c2(x - x1) + c3(x - x1)(x - x2) + ...
und muss nen Datenpunkt anhängen könen, ohne die ganze Berechnung neu zu machen.

Walli

Ich glaube nicht, dass das möglich ist. Will man mit dem Schema der dividierten Differenzen einen weitere Stützstelle in das Polynom einarbeiten so ist man zumindest auf die "äußeren" Zwischenergebnisse angewiesen. Das wäre ein zusätzlicher Speicheraufwand von O(n) in deinem Fall.

fubar

Doch, ist IMHO ohne Probleme möglich. Willst du einen Punkt hinzufügen, brauchst du in dem Schema der dividierten Differenzen nur die "oberste Zeile", also genau die Koeffizienten c_i.

Walli

Args, hast Recht! Ist mittlerweile über ein Jahr her, dass ich die Newton-Interpolation mit Stift und Papier ausführen durfte. Da musste man immer unten weitermachen weil oben kein Platz mehr war. Irgendwie hat sich das dann bei mir eingebrannt, dass man nicht oben weitermachen darf. Warum auch immer...

fubar schrieb:

Doch, ist IMHO ohne Probleme möglich. Willst du einen Punkt hinzufügen, brauchst du in dem Schema der dividierten Differenzen nur die "oberste Zeile", also genau die Koeffizienten c_i.

Das wollte ich hören.
Jetzt ist mir aber immer noch unbegreiflich, wie das geht. Die unterste Zeile muss ich ja durchrechnen, dabei brauch ich doch jeweils die Zeile drüber, bis zum Ende also alle Zeilen durch. Wie kann ich das ohne die Zwischenwerte machen?

asmodis

Was die Leute meinen:

Angenommen, du hast schon folgendes Differenzenschema ausgerechnet

x1  c1
         c2
x2  y2        c3 ...
         c2
x3  y3        ....

Und hast dir die c's gespeichert.
Neuer Punkt oben anfügen:

xNeu   d1
            d2
x1     c1        d3
            c2        d4....
                 c3

Deine d's sind nun die neuen Koeffizienten.

Woah ich Idiot. Ich hab natürlich genau verkehrt rum gedacht. Wahrscheinlich hab ich mir mein Gehirn weggegrillt. So ist es natürlich klar. Danke schon mal, ich werd das gleich mal ausprobieren.

Walli

Du hast ja die Koeffizienten c_i und deine neue Stützstelle (x,y). Dann musst du nochmal durchgehen und die neuen Koeffizienten bestimmen.

c₀^neu=y
c_i^neu = (c_i-1-c_i-1^neu)/(x_i-x)

EDIT: Mmpf, zu spät.

Ja der Trick war halt, die neuen Koordinaten "oben drauf" zu legen. Ein durchschnittlich intelligenter Mensch wäre da wohl in wenigen Minuten drauf gekommen. *grml*

http://www.michael-firbach.de/garbage/polynominterpolation_suckt.png
sorry, ich konnt's mir nicht verkneifen *g*

Jester

Optimizer schrieb:

http://www.michael-firbach.de/garbage/polynominterpolation_suckt.png
sorry, ich konnt's mir nicht verkneifen *g*

hehe... definitiv.
Sobald der Grad zu hoch wird schwingt's. Wenn Du das vermeiden willst mußte die Interpolationsart ändern oder ne Approximation machen, das geht dann auch mit Polynomen wieder ganz gut.

Vor kurzem haben wir Splines kennengelernt. Das Prinzip klingt sehr vernünftig.

Walli

Jo, Béziérkurven sind je nach Anwendung auch ganz gut, wenn es nicht unbedingt Splines sein müssen.

Kyon

Walli schrieb:

Jo, Béziérkurven sind je nach Anwendung auch ganz gut, wenn es nicht unbedingt Splines sein müssen.

Sind Bezier-Kurven nicht auch Splines, bei denen jedoch Bernsteinpolynome die zugrunde liegende Basis bilden?
Allerdings musst Du dann auf die Interpolationsbedingung verzichten...