Interpolation

Bei der Interpolation soll zu gegebenen diskreten Daten (z.B. Messwerten) eine kontinuierliche Funktion gefunden werden, die diese Daten abbildet. Man sagt dann, die Funktion interpoliert die Daten.

Manchmal sind von einer Funktion nur einzelne Punkte bekannt, aber keine analytische Beschreibung der Funktion, um sie an beliebigen Stellen auswerten zu können. Ein Beispiel sind Punkte als Resultat einer physikalischen Messung. Könnte man die Punkte durch eine (eventuell glatte) Kurve verbinden, so wäre es möglich, die unbekannte Funktion an den dazwischenliegenden Stellen zu schätzen. Ein anderes Szenario besteht aus einer schwierig handhabbaren Funktion, die man durch eine einfachere approximativ darstellen will. Eine Interpolationsfunktion kann diese Anforderung der Einfachheit erfüllen.

Diese Aufgabe bezeichnet man als Interpolationsproblem. Es gibt für das Problem mehrere Lösungen, der Anwender muss zunächst geeignete Ansatzfunktionen wählen. Je nach Ansatzfunktionen erhalten wir eine andere Interpolante.

Die Interpolation ist eine Art der Approximation: die betrachtete Funktion wird durch die Interpolationsfunktion in den Stützstellen exakt wiedergegeben und in den restlichen Punkten immerhin näherungsweise. Die Approximationsgüte hängt vom Ansatz ab. Um sie zu schätzen, werden Zusatzinformationen über die Funktion $f$ benötigt. Diese ergeben sich auch bei Unkenntnis von $f$ meist in natürlicher Weise: Beschränktheit, Stetigkeit oder Differenzierbarkeit lassen sich häufig voraussetzen.

Bei anderen Approximationsverfahren wie z.B. der Ausgleichungsrechnung wird nicht gefordert, dass die Messdaten exakt wiedergegeben werden; das unterscheidet diese Verfahren von der Interpolation.

Bei dem verwandten Problem der Extrapolation werden Werte geschätzt, die über den Definitionsbereich der Daten hinausgehen.

Gegeben seien $n+1$ Paare von reellen Zahlen $(x_i,\,f_i)$. Hierbei bezeichnet man analog zum Rechnen mit Funktionen die $x_i$ als Stützstellen, die $f_i$ als Stützwerte und die $(x_i,f_i)$ als Stützpunkte. Man wählt nun eine Ansatzfunktion $\Phi(x,\,a_0,\ldots,a_n)$, die sowohl von $x$ als auch von $n+1$ weiteren Parametern $a_j$ abhängt. Als Interpolationsproblem bezeichnet man die Aufgabe, die $a_j$ so zu wählen, dass $\Phi(x_i,\,a_0,\ldots,a_n) = f_i$ ist.

Man spricht von einem linearen Interpolationsproblem, wenn $\Phi$ nur linear von den $a_j$ abhängt, d.h.

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

Spezialfälle für $n=1,\, n=2$ und $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:

Zu den wichtigsten nichtlinearen Interpolationsproblemen zählt das rationale:

Sei $p(x) = a_0 + a_1x + a_2x^2 + \dots + a_{n-1}x^{n-1}$ ein Polynom. Dieses Polynom lässt sich in der sogenannten Koeffizientendarstellung durch die Angabe des Vektors $(a_0,\dots ,a_{n-1})$ darstellen. Eine alternative Darstellung, die ohne die Koeffizienten $a_0,\dots ,a_{n-1}$ auskommt, besteht in der Stützstellendarstellung. Dabei wird das Polynom für $n$ Werte $x_i$ mit $0 \le i \le n-1$ und $i \in \mathbb{N}$ ausgewertet, d.h. es werden die Funktionswerte $p(x_i)=y_i$ berechnet. Das Paar von Vektoren $((x_0,\dots ,x_{n-1}),(y_0,\dots ,y_{n-1}))$ bezeichnet man als die Stützstellendarstellung des Polynoms $p$. Ein wesentlicher Vorteil dieser Darstellung besteht darin, dass zwei Polynome in Stützstellendarstellung in $\Theta(n)$ Schritten multipliziert werden können. In Koeffizientendarstellung werden hingegen $\Theta(n^2)$ Schritte benötigt. Die Transformation von der Koeffizienten- in die Stützstellendarstellung ist daher von spezieller Bedeutung und wird als Fourier-Transformation bezeichnet. Die Rücktransformation wird durch Interpolation erreicht.

In vielen Anwendungen von Interpolationsverfahren wird behauptet, dass durch Interpolation neue Daten aus bestehenden Daten hinzugewonnen werden. Dies ist aber falsch. Durch Interpolation kann nur der Verlauf einer kontinuierlichen Funktion zwischen bekannten Abtastpunkten abgeschätzt werden. Diese Abschätzung basiert meist auf der Annahme, dass der Verlauf einigermaßen "glatt" ist, was in den meisten Fällen zu plausiblen Resultaten führt. Die Annahme muss aber nicht notwendigerweise zutreffen. Höhere Frequenzanteile, die bei der Digitalisierung eines Signals aufgrund des Abtasttheorems verloren gegangen sind, können auch durch anschließende Interpolation nicht wieder rekonstruiert werden.

In der Bildbearbeitung verwendet man Interpolationsverfahren, um gerasterte Bilder zu vergrößern (digitaler Zoom). Da diese Bilder aber nur eine begrenzte Bildauflösung haben, führt die Wiederholung von Bildpunkten zu einem Treppen-Effekt. Das Phänomen ist allgemein auch als Alias-Effekt bekannt. Interpoliert man stattdessen die hinzugefügten Bildpunkte aus den bekannten Nachbarpunkten (Antialiasing), so werden die Kanten glatter, was aber zu Lasten der Bildschärfe geht. Die optische Auflösung des Bildes wird durch die Interpolation nicht vergrößert.