Polynominterpolation

Unter Polynominterpolation versteht man die Lösung der Aufgabe, ein Polynom zu finden, das n+1 gegebene Zuordnungen enthält und damit interpoliert. Für n+1 gegebene Punkte gibt es nach dem Fundamentalsatz der Algebra genau ein Polynom n-ten Grades, das diese erfüllt. Jenes nennen wir das Interpolations-Polynom.

Ein Polynom n-ten Grades hat n+1 Koeffizienten, also ebenso viele Freiheitsgrade. Die Lösung des Interpolationsproblems kann also durch ein lineares Gleichungssystem bestimmt werden. Wie dieses Gleichungssystem genau aussieht, hängt von der gewählten Darstellung beziehungsweise Basis ab.

Einführendes Beispiel: Lagrange-Interpolation

Das folgende Beispiel soll für n=2 die Idee der Polynominterpolation durch Lagrange-Polynome erläutern.

Wir wollen eine Funktion f durch ein Interpolationspolynom 2-ten Grades, also durch eine Parabel, interpolieren. Dazu müssen drei Punkte, die auf dem Graphen von f liegen, bekannt sein:

$(a,f(a)),(b,f(b)),(c,f(c))\,$

Unser noch zu bestimmendes Interpolationspolynom p habe die Form

$p(x)=k_{2}x^{2}+k_{1}x+k_{0};\,$

Die Funktion f durch das Polynom p zu interpolieren, bedeutet - anschaulich gesprochen - das Polynom p so zu bestimmen, dass es die obigen drei Punkte von f enthält. Um also die unbekannten Koeffizienten $k_{0},k_{1},k_{2}\,$ der Parabel zu ermitteln, muss demnach das folgende lineare Gleichungssystem gelöst werden:

$p(a)=f(a);\,$

$p(b)=f(b);\,$

$p(c)=f(c);\,$

oder ausformuliert:

$k_{2}a^{2}+k_{1}a+k_{0}=f(a);\,$

$k_{2}b^{2}+k_{1}b+k_{0}=f(b);\,$

$k_{2}c^{2}+k_{1}c+k_{0}=f(c);\,$

Das mag zwar kein prinzipielles Problem darstellen, aber spätestens ab n=3 kommmt da wenig Freude auf, wenn man die Lösungen zu Fuß ausrechnen soll.

Viel schneller und eleganter geht es mit der Technik der Lagrange-Polynome: Wir konstruieren drei Lagrange-Polynome $L_{0},L_{1},L_{2}\,$ mit folgenden Eigenschaften:

$L_{0}(a)=1;L_{0}(b)=0;L_{0}(c)=0;\,$

$L_{1}(a)=0;L_{1}(b)=1;L_{1}(c)=0;\,$

$L_{2}(a)=0;L_{2}(b)=0;L_{2}(c)=1;\,$

Diese zu konstruieren, geht ganz einfach:

$L_{0}(x):={\frac {(x-b)(x-c)}{(a-b)(a-c)}};\,$

$L_{1}(x):={\frac {(x-a)(x-c)}{(b-a)(b-c)}};\,$

$L_{2}(x):={\frac {(x-a)(x-b)}{(c-a)(c-b)}};\,$

Wer scharf hinguckt, sieht sofort, dass unsere drei Lagrange-Polynome tatsächlich die erwünschten Eigenschaften besitzen.

Und jetzt kommt der eigentliche Knüller:

Unsere gesuchte Parabel p ist nichts weiter als die folgende Summe:

$p(x)=f(a)\cdot L_{0}(x)+f(b)\cdot L_{1}(x)+f(c)\cdot L_{2}(x)=f(a)\cdot {\frac {(x-b)(x-c)}{(a-b)(a-c)}}+f(b)\cdot {\frac {(x-a)(x-c)}{(b-a)(b-c)}}+f(c)\cdot {\frac {(x-a)(x-b)}{(c-a)(c-b)}};\,$

Denn:

$p(a)=f(a)\cdot L_{0}(a)+f(b)\cdot L_{1}(a)+f(c)\cdot L_{2}(a)=f(a)+0+0=f(a);\,$

$p(b)=f(a)\cdot L_{0}(b)+f(b)\cdot L_{1}(b)+f(c)\cdot L_{2}(b)=0+f(b)+0=f(b);\,$

$p(c)=f(a)\cdot L_{0}(c)+f(b)\cdot L_{1}(c)+f(c)\cdot L_{2}(c)=0+0+f(c)=f(c);\,$

Wir haben nun also die Funktion f durch das Interpolationspolynom p 2-ten Grades interpoliert. Für n>2 funktioniert das Verfahren analog.

Newton-Basis

Die so genannte Newton-Basis hat sich hier bewährt:

$N_{k}(x)={\begin{cases}1&:k=0\\\prod _{j=0}^{k-1}(x-x_{j})&:k\geq 1\end{cases}}$

Das Interpolationspolynom wird gegeben durch

$P(x)=\sum _{k=0}^{n}c_{k}N_{k}(x).$

Die unbekannten Koeffizienten $c_{k}$ können hier mittels des Neville-Aitken-Schemas (auch „Aitken-Neville-Schema“ oder „Schema der dividierten Differenzen“ genannt) effizient und stabil berechnet werden.

Wenn das Feld x die Stützstellen x(1)...x(n) und das Feld y die Stützwerte y(1) bis y(n) enthält, dann liefert der folgende BASIC-Algorithmus die Koeffizienten $c_{0},c_{1},...,c_{n}$. Die Programmsequenz verändert dazu das Feld y derart, dass der Koeffizient $c_{1}$ in y(1) steht, $c_{2}$ in y(2) bis $c_{n}$ in y(n).

   For i = 1 To n
       For j = n To i + 1 Step -1
           y(j) = (y(j) - y(j-1)) / (x(j) - x(j-i))
       Next j
   Next i

Das folgende Programm liefert, ausgehend von den oben berechneten Koeffizienten und Stützstellen, den Wert der Interpolationsfunktion an der Stelle x_Wert.

   y_Wert = 0
   For i = n To 1 Step -1
       y_Wert = y_Wert * (x_Wert - x(i)) + y(i)
   Next i

Ferner ist die Auswertung eines Polynoms in Newton-Darstellung mittels des Horner-Schemas in linearem Zeitaufwand möglich.

Lagrange-Basis

Eher für theoretische Betrachtungen günstig ist eine Darstellung in der Lagrange-Basis. Hier nennt man die Basisfunktionen Lagrange-Polynome:

$\ell _{i}(x)=\prod _{j=0,j\neq i}^{n}{\frac {x-x_{j}}{x_{i}-x_{j}}}.$

Die Lösung des Interpolationsproblems lässt sich dann einfach angeben als

$P(x)=\sum _{i=0}^{n}f(x_{i})\ell _{i}(x).$

Der große Vorteil der Newton-Basis ist, dass sich dort neue Punkte sehr leicht einfügen lassen, indem man einfach am Ende noch einen Term anhängt. Bei der Lagrange-Basis muss man alle Basisfunktionen komplett neu berechnen.

Probleme

Polynome haben den Nachteil, dass sie viele Extrema haben und deswegen bei hohem Polynomgrad recht stark schwingen, weswegen es manchmal vorteilhaft ist, das Interpolationspolynom aus Teil-Polynomen zusammenzusetzen (siehe Runges Phänomen und Spline-Interpolation).

Anwendungen

Polynome lassen sich sehr leicht integrieren und ableiten. Deswegen tauchen interpolierende Polynome an vielen Stellen in der numerischen Mathematik auf, beispielsweise bei der numerischen Integration und entsprechend bei Verfahren zur numerischen Lösung gewöhnlicher Differentialgleichungen.

Weblinks

• Seite zu Newton, Lagrange und Cubic Spline mit Java Applet