Das allgemeine Interpolationsproblem

Gegeben seien ${\displaystyle n+1}$ Paare reeller oder komplexer Zahlen ${\displaystyle (x_{i},\,f_{i})}$ als Stützpunkte. Man wählt eine Ansatzfunktion ${\displaystyle \Phi (x,\,a_{0},\ldots ,a_{n})}$, die sowohl von ${\displaystyle x}$ als auch von ${\displaystyle n+1}$ weiteren Parametern ${\displaystyle a_{j}}$ abhängt. Als Interpolationsproblem bezeichnet man die Aufgabe, die ${\displaystyle a_{j}}$ so zu wählen, dass ${\displaystyle \Phi (x_{i},\,a_{0},\ldots ,a_{n})=f_{i}}$ ist.

Das lineare Interpolationsproblem

Man spricht von einem linearen Interpolationsproblem, wenn ${\displaystyle \Phi }$ nur linear von den ${\displaystyle a_{j}}$ abhängt, d. h.

${\displaystyle \Phi (x,\,a_{0},\ldots ,a_{n})=a_{0}+a_{1}\Phi _{1}(x)+a_{2}\Phi _{2}(x)+\cdots +a_{n}\Phi _{n}(x)}$.

Insbesondere die Polynominterpolation ist ein solches lineares Interpolationsproblem. Für die Polynominterpolation gilt

${\displaystyle \Phi (x,\,a_{0},\ldots ,a_{n})=a_{0}+a_{1}x+a_{2}x^{2}+a_{3}x^{3}+\cdots +a_{n}x^{n}}$.

Spezialfälle für ${\displaystyle n=1}$, ${\displaystyle n=2}$ und ${\displaystyle n=3}$ nennt man lineare, quadratische und kubische Interpolation. In zwei Dimensionen spricht man entsprechend von bilinear, biquadratisch und bikubisch.

Des Weiteren ist die trigonometrische Interpolation eine lineare Interpolation:

${\displaystyle \Phi (x,\,a_{0},\ldots ,a_{n})=a_{0}+a_{1}e^{xi}+a_{2}e^{2xi}+\cdots +a_{n}e^{nxi},\quad (i^{2}=-1)}$

Nichtlineare Interpolationsprobleme

Zu den wichtigsten nichtlinearen Interpolationsproblemen zählt

• das rationale: ${\displaystyle \Phi (x,\,a_{0},\ldots ,a_{n},\,b_{0},\ldots ,b_{m})={\frac {a_{0}+a_{1}x+a_{2}x^{2}+a_{3}x^{3}+\cdots +a_{n}x^{n}}{b_{0}+b_{1}x+b_{2}x^{2}+b_{3}x^{3}+\cdots +b_{m}x^{m}}}}$

Abschnittsweise konstante Interpolation

Als einfache Interpolationsmethode kann der nächstgelegenen Datenwert gesucht werden und dem aktuellen Punkt dessen Wert zugewiesen werden. Bei einfachen Problemen ist es unwahrscheinlich, dass diese Methode verwendet wird, da die lineare Interpolation fast genauso einfach ist. Bei höherdimensionalen multivariaten Interpolationen könnte diese Methode aufgrund ihrer Schnelligkeit und Einfachheit dennoch eine gute Wahl sein.

Lineare Interpolation

Die von Isaac Newton begründete lineare Interpolation ist am einfachsten und wird wohl in der Praxis am häufigsten benutzt. Hier werden zwei gegebene Datenpunkte (${\displaystyle x_{0},f_{0}}$) und (${\displaystyle x_{1},f_{1}}$) durch eine Strecke verbunden. Es gilt:

${\displaystyle f(x)=f_{0}+{\frac {f_{1}-f_{0}}{x_{1}-x_{0}}}\,(x-x_{0})=f_{0}{\frac {x_{1}-x}{x_{1}-x_{0}}}+f_{1}{\frac {x-x_{0}}{x_{1}-x_{0}}}\,.}$

Dies entspricht einer Konvexkombination der Endpunkte ${\displaystyle (x_{0},\,f_{0})}$ und ${\displaystyle (x_{1},\,f_{1})}$.

Detaillierte Erläuterungen siehe Allgemeine lineare Interpolation.

Höhergradige Polynome

Zu ${\displaystyle n+1}$ paarweise verschiedenen Datenpunkten gibt es genau ein Interpolationspolynom ${\displaystyle n}$-ten Grades, das an den vorgegebenen Stützstellen mit den vorgegebenen Stützwerten übereinstimmt. Die Bestimmung der Koeffizienten erfordert die Lösung eines linearen Gleichungssystems. Die Existenz eines solchen Interpolationspolynoms sieht man z. B. mit Hilfe der Formel von Lagrange

${\displaystyle p(x)=\sum _{i=0}^{n}\,f_{i}\prod _{k=0,k\neq i}^{n}{\frac {x-x_{k}}{x_{i}-x_{k}}}}$.

Die Eindeutigkeit folgt aus der bekannten Tatsache, dass ein Polynom ${\displaystyle n}$-ten Grades höchstens ${\displaystyle n}$ Nullstellen besitzt.

Weitere Verfahren zur Polynominterpolation siehe dort.

Stückweise Interpolation

Da Polynome mit zunehmendem Grad immer instabiler werden, d. h. stark zwischen den Interpolationspunkten schwingen, werden in der Praxis Polynome mit einem Grad größer als 5 kaum eingesetzt. Stattdessen interpoliert man einen großen Datensatz stückweise. Im Fall der linearen Interpolation wäre das ein Polygonzug oder linearer Spline, bei stückweise Polynomen höheren Grades spricht man auch von Spline-Interpolation. Bei abschnittsweise definierten Interpolanten ist die Frage der Stetigkeit und Differenzierbarkeit an den Stützstellen von großer Bedeutung.

Im mehrdimensionalen Fall basiert insbesondere die Methode der finiten Elemente für elliptische Probleme zweiter Ordnung auf dem Einsatz stetiger Splines, oft auf Dreiecksgittern. Fehlerabschätzungen für die Finite-Element-Methode basieren auf entsprechenden Abschätzungen des Interpolationsfehlers.

Hermiteinterpolation

Sind zusätzlich zu den Stützstellen ${\displaystyle x_{i}}$ auch noch die ${\displaystyle k}$-Ableitungen ${\displaystyle f^{(k)}(x_{i})=f_{i}^{(k)}}$ zu interpolieren, so spricht man von einem Hermite-Interpolationsproblem. Die Lösung dieses Problems lässt sich analog zum Lagrange-Verfahren ebenfalls in geschlossener Form angeben.

Im mehrdimensionalen Fall basiert insbesondere die Methode der finiten Elemente für elliptische Probleme vierter Ordnung auf dem Einsatz stetig differenzierbarer Splines. Auf Dreiecksgittern ist deren Konstruktion nicht so einfach.

Trigonometrische Interpolation

Wählt man als Ansatzfunktion ein trigonometrisches Polynom, so erhält man eine trigonometrische Interpolation. Die Interpolationsformel

${\displaystyle g(x)={\frac {1}{2}}a_{0}+\sum _{k=1}^{N-1}(a_{k}\cos kx+b_{k}\sin kx)+{\frac {1}{2}}a_{N}\cos Nx\,,\quad N=n/2}$

entspricht einer Fourier-Entwicklung der unbekannten Interpolanten. Die Fourier-Koeffizienten ${\displaystyle a_{k}}$ und ${\displaystyle b_{k}}$ berechnen sich zu

${\displaystyle a_{k}\approx {\frac {2}{n}}\sum _{i=1}^{n}f(x_{i})\cos kx_{i}}$ und ${\displaystyle b_{k}\approx {\frac {2}{n}}\sum _{i=1}^{n}f(x_{i})\sin kx_{i}}$.

Dabei wird angenommen, dass die Stützstellen ${\displaystyle x_{i}}$ im Intervall ${\displaystyle [0;\,2\pi ]}$ äquidistant verteilt sowie außerhalb dieses Intervalls periodisch sind. Die Koeffizienten können effizient mit Hilfe der schnellen Fourier-Transformation berechnet werden.

Logarithmische Interpolation

Vermutet bzw. weiß man, dass den Daten eine logarithmische Funktion zugrunde liegt, so empfiehlt sich dieses Verfahren.

Bei der logarithmischen Interpolation werden zwei bekannte Datenpunkte ${\displaystyle (x_{0},f_{0})}$ und ${\displaystyle (x_{1},f_{1})}$ durch eine logarithmische Kurve verbunden. Es gilt:

${\displaystyle {\frac {\ln f-\ln f_{0}}{\ln f_{1}-\ln f_{0}}}={\frac {x-x_{0}}{x_{1}-x_{0}}}}$

Oder anders formuliert:

${\displaystyle f(x)=f_{0}\cdot \exp \left({\frac {(x-x_{0})(\ln f_{1}-\ln f_{0})}{x_{1}-x_{0}}}\right)}$

Beispiel: χ²-Test

Gaußprozess-Regression (Kriging)

Ein sehr vielseitiges und universelles Interpolationsverfahren ist die Gaußprozess-Regression bzw. das Kriging-Verfahren. Damit können sowohl Interpolationen als auch Glättungen in beliebigen Dimensionen und auf unregelmäßigen Stützstellen durchgeführt werden. Mithilfe einer sogenannten Kovarianzfunktion können speziellen Eigenschaften der Daten beschrieben werden (z. B. die Korrelationsläge oder eine Periodizität), um damit die für das Problem optimale Interpolation durchzuführen.

Eigenschaften der Interpolationsmethode:

• Geeignet für unregelmäßige Stützstellen
• Interpolation in beliebigen Dimensionen (z. B. Flächen-Interpolation)
• Optimale Interpolation von glatten, periodischen oder verrauschten Kurven
• Vorhersage des Vertrauensintervalls der Interpolation

Beispiele

• Mit vorgegebenen Stützstellen ${\displaystyle \{x_{1},\dotsc ,x_{N}\}}$ und einer reellen Funktion ${\displaystyle h}$ mit ${\displaystyle h(0)=0}$, ${\displaystyle h'(0)\neq 0}$ kann die Funktion ${\displaystyle H(x):=h(x-x_{1})\dotsm h(x-x_{N})}$ gebildet werden. Dann erhält man

${\displaystyle L_{k}(x)={\frac {h(x-x_{k})}{h'(0)(x-x_{k})}}\cdot \prod _{j\neq k}{\frac {h(x-x_{j})}{h(x_{k}-x_{j})}}}$.

Das aus ${\displaystyle h(x)=x}$ resultierende Interpolationsverfahren ist die Lagrange-Interpolation. Andere Beispiele sind ${\displaystyle h(x)=x/(1+x^{2})}$ für nach Unendlich gegen Null fallende Interpolationsfunktionen oder ${\displaystyle h(x)=\sin(x)}$ für eine beschränkte Interpolationsfunktion mit übersichtlicher Berechnungsformel.

• Mit dem Kreisteilungspolynom ${\displaystyle H(x):=x^{N}-1}$, d. h. den ${\displaystyle N}$-ten Einheitswurzeln ${\displaystyle x_{k}:=\exp(i2\pi \,k/N)}$, ${\displaystyle k=1,\dots ,N}$, als Stützstellen, ergibt sich die Diskrete Fourier-Transformation als Verfahren zur Berechnung der Koeffizienten des Interpolationspolynoms. Es gilt ${\displaystyle L_{N}(x)={\frac {1}{N}}(1+x+\dotsb +x^{N-1})}$ und allgemein ${\displaystyle L_{k}(x)=L_{N}({\bar {x}}_{k}\,x)}$, so dass

${\displaystyle F(x)=\sum _{n=0}^{N-1}x^{n}\cdot {\frac {1}{N}}\sum _{k=1}^{N}f_{k}{\bar {x}}_{k}^{n}}$ ist.

• Mit ${\displaystyle H(x):=\sin(\pi x)}$ und den Nullstellen ${\displaystyle x_{k}=k}$, ${\displaystyle k\in \mathbb {Z} }$, ergibt sich als Interpolationsfunktion die Kardinalreihe

${\displaystyle F(x)=\sum _{k\in \mathbb {Z} }f_{k}{\frac {\sin(\pi x)}{(-1)^{+}k\pi (x-k)}}=\sum _{k\in \mathbb {Z} }f_{k}{\frac {\sin(\pi (x-k))}{\pi (x-k)}}}$.

Diese spielt eine zentrale Rolle im Nyquist-Shannon-Abtasttheorem. Die Konvergenzbedingung lautet

${\displaystyle \sum _{k\in \mathbb {Z} }\left|{\frac {f_{k}}{1+|k|}}\right|<\infty }$.