- 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 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:
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 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.
Eine Auswertung benötigt also 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 lässt sich das Interpolationspolynom eindeutig darstellen mittels
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):
Da [xi]f = fi gilt, lässt sich die Berechnung rekursiv durch das Schema der dividierten Differenzen durchführen:
Literatur
- Hans R. Schwarz, Norbert Köckler: Numerische Mathematik, 5. Aufl., Teubner, Stuttgart 2004, ISBN 3-519-42960-8.
Weblinks
Wikimedia Foundation.