Polynominterpolation

Die Polynominterpolation konstruiert das eindeutige Polynom vom Grad höchstens n, das durch n+1 gegebene Datenpunkte verläuft, und bildet eine Grundlage für die Differenzierung, Integration und Approximation von Funktionen.

Definition

Polynominterpolation ist die Bestimmung des Polynoms geringsten Grades, das mit vorgegebenen Werten (und möglicherweise Ableitungen) an einer gegebenen Menge von Punkten, den Interpolationsknoten, übereinstimmt.

Scope

Dieses Thema behandelt die Existenz und Eindeutigkeit des interpolierenden Polynoms, die Lagrange- und Newton-Darstellungen mit dividierten Differenzen, die baryzentrische Form zur stabilen Auswertung, die Interpolationsfehlerformel und das Runge-Phänomen, das Chebyshev-Punktverteilungen motiviert.

Core questions

• Warum ist das interpolierende Polynom durch n+1 verschiedene Punkte eindeutig, und wie wird es dargestellt?
• Wie vergleichen sich die Lagrange- und Newton-Formen, und warum wird die baryzentrische Form zur Auswertung bevorzugt?
• Was besagt die Interpolationsfehlerformel über die Genauigkeit, und wie beeinflusst die Knotenplatzierung diese?
• Warum versagt die Interpolation an äquidistanten Punkten bei hohen Graden, und wie beheben Chebyshev-Knoten dies?

Key theories

Existenz und Eindeutigkeit

Für n+1 verschiedene Knoten gibt es genau ein Polynom vom Grad höchstens n, das mit den vorgegebenen Werten übereinstimmt, eine Folge der Nichtsingularität des Vandermonde-Systems; die Lagrange- und Newton-Formen liefern zwei konstruktive Darstellungen desselben Polynoms.

Interpolationsfehler und Knotenauswahl

Der Interpolationsfehler ist die dividierte Differenz der Ordnung n+1 mal dem Knotenpolynom; die Minimierung des Maximums des Knotenpolynoms führt zur Wahl von Chebyshev-Knoten, die das Runge-Phänomen unterdrücken und eine nahezu optimale Genauigkeit ergeben.

Mechanisms

Die Newton-Form konstruiert den Interpolanten inkrementell unter Verwendung dividierter Differenzen, sodass das Hinzufügen eines Knotens nur einen zusätzlichen Term erfordert. Die baryzentrische Form schreibt den Lagrange-Interpolanten mit vorab berechneten Gewichten um, wodurch der Interpolant in linearer Zeit pro Punkt mit ausgezeichneter numerischer Stabilität ausgewertet werden kann. Die Fehlerformel drückt die Differenz zwischen Funktion und Interpolant durch eine Ableitung höherer Ordnung und das Produkt der Abstände zu den Knoten aus, das im Inneren klein und an den Enden für äquidistante Knoten groß ist – die Ursache des Runge-Phänomens –, aber für Chebyshev-Knoten gleichmäßig begrenzt ist.

Clinical relevance

Polynominterpolation ist der Baustein für numerische Differenzierungs- und Integrationsformeln, für die Konstruktion von Quadratur- und Finite-Differenzen-Schablonen, für Spektralmethoden und für die Auswertung tabellierter Funktionen; ihre Fehleranalyse gibt Aufschluss darüber, wie dicht und wo Daten für eine genaue Rekonstruktion abgetastet werden sollten.

History

Interpolationsformeln gehen auf Newton und Lagrange zurück, aber das moderne Verständnis wurde durch Runges Beispiel von 1901, das Divergenz an äquidistanten Punkten zeigte, und durch die Erkenntnis des zwanzigsten Jahrhunderts geschärft, dass Chebyshev-Knoten und die stabile baryzentrische Form eine Interpolation hohen Grades sowohl genau als auch praktisch machen.

Key figures

• Joseph-Louis Lagrange
• Isaac Newton
• Carl Runge
• Pafnuty Chebyshev

Seminal works

• trefethen2013
• powell1981

Frequently asked questions

Ist ein interpolierendes Polynom höheren Grades immer genauer?

Nicht unbedingt. Bei äquidistanten Knoten kann eine Erhöhung des Grades zu großen Oszillationen nahe den Intervallenden (dem Runge-Phänomen) führen und die Genauigkeit verringern. Die Verwendung von Chebyshev-verteilten Knoten oder stückweiser (Spline-)Interpolation stellt eine zuverlässige Konvergenz wieder her.

Welche Darstellung des Interpolanten sollte in der Praxis verwendet werden?

Die baryzentrische Form wird im Allgemeinen bevorzugt: Sobald ihre Gewichte berechnet sind, wertet sie den Interpolanten schnell aus und ist numerisch stabil, im Gegensatz zur direkten Lösung des Vandermonde-Systems, das schlecht konditioniert ist.