Dividierte Differenzen

Dividierte Differenzen

Das Verfahren von Neville/Aitken kann zur Berechnung von Koeffizienten zur Polynominterpolation verwendet werden.

Für die numerische Berechnung ist dieser Algorithmus zu aufwändig. Das Verfahren der Dividierten Differenzen, welches weiter unten behandelt wird, ist für die numerische Berechnung deutlich besser geeignet.

Inhaltsverzeichnis

Lemma von Aitken

Es bezeichne p(f | xi...xi + k)(x) das eindeutig bestimmte Polynom k-ten Grades, das an den angegebenen Stellen xj die jeweiligen Werte fj annimmt. Dann gilt:

p(f|x_0...x_n)(x) = \frac {(x_0 - x)\, p(f|x_1...x_n)(x) - (x_n - x) \,p(f|x_0...x_{n-1})(x)}{x_0-x_n}

Der Beweis erfolgt durch Einsetzen von xi, wodurch man verifiziert, dass die rechte Seite der Gleichung die Interpolationsbedingung erfüllt. Die Eindeutigkeit des Interpolationspolynoms liefert dann die Behauptung.

Schema von Neville

Da p(f|x_i)(x) \equiv f_i ein eindeutiges und bekanntes konstantes Polynom darstellt, lässt sich die Auswertung von p(f | x0...xn)(x) mit Hilfe des Lemmas von Aitken an einer Stelle x rekursiv berechnen. Dieses Schema wird als "Schema von Neville" bezeichnet.

Datei:Polynominterpolation_Schema_von_Neville.jpg

Eine Auswertung benötigt also O\left({n(n+1)}\right) Operationen. Dies ist bei vielen Funktionsauswertungen des interpolierten Polynoms noch nicht optimal.

Dividierte Differenzen

Eine bessere Darstellung erreicht man durch sogenannte dividierte Differenzen. Es sei p(f | xi...xi + k)(x) wieder das eindeutige Interpolationspolynom vom Grade k. Dann bezeichne den höchsten Koeffizienten dieses Polynoms mit [xi...xi + k]f und bezeichne ihn als "dividierte Differenz".

Mit Hilfe der Newton-Basis N_{k}(x) = \begin{cases} 1 & : k=0 \\ \prod_{j=0}^{k-1}(x-x_{j}) & : k\ge1 \end{cases} lässt sich das Interpolationspolynom eindeutig darstellen mittels

p(f|x_{0}...x_{n})(x) = \sum_{k=0}^{n} [x_0...x_k]f \, N_k(x),

wie man mittels vollständiger Induktion beweisen kann.

Schema der dividierten Differenzen

Die Auswertung des Polynoms dargestellt in der Newton-Basis kann sehr effizient mit dem Horner-Schema durchgeführt werden. Es bleibt, die dividierten Differenzen als Koeffizienten zu berechnen. Aus dem Lemma von Aitken folgt direkt die dazu benötigte Rekursionsformel (i > j):

[x_i,...,x_j]f = \frac {[x_i,...,x_{j-1}]f-[x_{i+1},...,x_{j}]f}{x_i - x_j}

Da [xi]f = fi gilt, lässt sich die Berechnung rekursiv durch das Schema der dividierten Differenzen durchführen:

Datei:Polynominterpolation_Schema_dividierte_Differenzen.jpg

Literatur

  • Hans R. Schwarz, Norbert Köckler: Numerische Mathematik, 5. Aufl., Teubner, Stuttgart 2004, ISBN 3-519-42960-8.

Weblinks


Wikimedia Foundation.

Игры ⚽ Нужна курсовая?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Aitken-Neville-Schema — Das Verfahren von Neville/Aitken kann zur Berechnung von Koeffizienten zur Polynominterpolation verwendet werden. Für die numerische Berechnung ist dieser Algorithmus zu aufwändig. Das Verfahren der Dividierten Differenzen, welches weiter unten… …   Deutsch Wikipedia

  • Neville-Aitken-Schema — Das Verfahren von Neville/Aitken kann zur Berechnung von Koeffizienten zur Polynominterpolation verwendet werden. Für die numerische Berechnung ist dieser Algorithmus zu aufwändig. Das Verfahren der Dividierten Differenzen, welches weiter unten… …   Deutsch Wikipedia

  • Neville-Schema — Das Verfahren von Neville/Aitken kann zur Berechnung von Koeffizienten zur Polynominterpolation verwendet werden. Für die numerische Berechnung ist dieser Algorithmus zu aufwändig. Das Verfahren der Dividierten Differenzen, welches weiter unten… …   Deutsch Wikipedia

  • Polynominterpolation — Interpolationspolynom 7. Grades In der numerischen Mathematik versteht man unter Polynominterpolation die Suche nach einem Polynom, welches exakt durch vorgegebene Punkte (z. B. aus einer Messreihe) verläuft. Dieses Polynom wird… …   Deutsch Wikipedia

  • Interpolationspolynom — Unter Polynominterpolation versteht man die Lösung der Aufgabe, ein Polynom zu finden, das exakt durch vorgegebene Stützstellen verläuft und diese damit interpoliert. Für n + 1 gegebene Wertepaare mit paarweise verschiedenen xi gibt es genau ein… …   Deutsch Wikipedia

  • Lagrange-Basis — Unter Polynominterpolation versteht man die Lösung der Aufgabe, ein Polynom zu finden, das exakt durch vorgegebene Stützstellen verläuft und diese damit interpoliert. Für n + 1 gegebene Wertepaare mit paarweise verschiedenen xi gibt es genau ein… …   Deutsch Wikipedia

  • Lagrange-Polynom — Unter Polynominterpolation versteht man die Lösung der Aufgabe, ein Polynom zu finden, das exakt durch vorgegebene Stützstellen verläuft und diese damit interpoliert. Für n + 1 gegebene Wertepaare mit paarweise verschiedenen xi gibt es genau ein… …   Deutsch Wikipedia

  • Newton-Basis — Unter Polynominterpolation versteht man die Lösung der Aufgabe, ein Polynom zu finden, das exakt durch vorgegebene Stützstellen verläuft und diese damit interpoliert. Für n + 1 gegebene Wertepaare mit paarweise verschiedenen xi gibt es genau ein… …   Deutsch Wikipedia

  • Newton-Darstellung — Unter Polynominterpolation versteht man die Lösung der Aufgabe, ein Polynom zu finden, das exakt durch vorgegebene Stützstellen verläuft und diese damit interpoliert. Für n + 1 gegebene Wertepaare mit paarweise verschiedenen xi gibt es genau ein… …   Deutsch Wikipedia

  • Newton-Polynom — Unter Polynominterpolation versteht man die Lösung der Aufgabe, ein Polynom zu finden, das exakt durch vorgegebene Stützstellen verläuft und diese damit interpoliert. Für n + 1 gegebene Wertepaare mit paarweise verschiedenen xi gibt es genau ein… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”