Interpolation (Mathematik)

In der numerischen Mathematik bezeichnet der Begriff Interpolation (aus lateinisch inter = dazwischen und polire = glätten, schleifen) eine Klasse von Problemen und Verfahren. Zu gegebenen diskreten Daten (z. B. Messwerten) soll eine stetige Funktion (die sogenannte Interpolante oder Interpolierende) gefunden werden, die diese Daten abbildet. Man sagt dann, die Funktion interpoliert die Daten.

Zu interpolierende Punkte

Einführung

Manchmal sind von einer Funktion nur einzelne Punkte bekannt, aber keine analytische Beschreibung der Funktion, durch die sie an beliebigen Stellen ausgewertet werden könnte. 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. In anderen Fällen soll eine schwierig handhabbare Funktion näherungsweise durch eine einfachere dargestellt werden. 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 der Ausgleichungsrechnung wird nicht gefordert, dass die Messdaten exakt wiedergegeben werden. Dadurch unterscheiden sich diese Verfahren von der Interpolation. Bei dem verwandten Problem der Extrapolation werden Werte geschätzt, die über den Definitionsbereich der Daten hinausgehen.

Interpolationsprobleme

Das allgemeine Interpolationsproblem

Gegeben seien $n+1$ Paare reelle oder komplexer Zahlen $(x_{i},\,f_{i})$ als Stützpunkte. Man wählt 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.

Das lineare Interpolationsproblem

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

$\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

$\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 $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:

$\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: $\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}}}$

Interpolationsverfahren

Lineare Interpolation

Stückweise durchgeführte 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 ($x_{0},f_{0}$) und ($x_{1},f_{1}$) durch eine Strecke verbunden. Es gilt:

$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 $(x_{0},\,f_{0})$ und $(x_{1},\,f_{1})$.

Detaillierte Erläuterungen siehe Allgemeine lineare Interpolation.

Höhergradige Polynome

Interpolationspolynom 7. Grades

Zu $n+1$ paarweise verschiedenen Datenpunkten gibt es genau ein Interpolationspolynom $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

$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 $n$-ten Grades höchstens $n$ Nullstellen besitzt.

Weitere Verfahren zur Polynominterpolation siehe dort.

Stückweise Interpolation

Kubische Spline-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 $x_{i}$ auch noch die $k$-Ableitungen $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

$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 $a_{k}$ und $b_{k}$ berechnen sich zu

$a_{k}\approx {\frac {2}{n}}\sum _{i=1}^{n}f(x_{i})\cos kx_{i}$ und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle b_k\approx \frac{2}{n}\sum_{i=1}^n f(x_i)\sin kx_i} .

Dabei wird angenommen, dass die Stützstellen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x_i} im Intervall Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (x_0, f_0)} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (x_1, f_1)} durch eine logarithmische Kurve verbunden. Es gilt:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \frac{ \ln f- \ln f_0}{ \ln f_1- \ln f_0} = \frac{x-x_0}{x_1-x_0}}

Oder anders formuliert:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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)

Gaußprozess-Interpolation (blau) und geschätztes Vertrauensintervall (grau) einer Lücke zwischen zwei Kurven (schwarz) von sehr gemischten Eigenschaften.

Ein sehr vielseitiges und universelles Interpolationsverfahren ist die Gaußprozess-Regression bzw. das Kriging-Verfahren. Damit können sowohl glatte, wie auch periodische Interpolationen oder Glättungen in beliebigen Dimensionen durchgeführt werden. Mithilfe einer sogenannten Kovarianzfunktion können die speziellen Eigenschaften der Daten beschrieben werden, um 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 Vertrauensintervals der Interpolation

Allgemeine lineare Interpolation

Es sei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle H(x) } eine reelle oder komplexe stetig differenzierbare Funktion mit Nullstellenmenge Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \{ x_k: k\, \mathrm{aus}\, I\} } , wobei alle Nullstellen einfach sein müssen. Dabei kann die Indexmenge Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle I } eine endliche Menge, wie z. B. Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle I= \{1,\dots,N\} } , oder eine abzählbare Menge, wie Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle I= \mathbb{N} } oder Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle I= \mathbb{Z} } , sein. Damit sind die Interpolationskerne gegeben als

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle L_k(x):=\frac{H(x)}{H'(x_k)(x-x_k)}=\frac{G(x,x_k)}{G(x_k,x_k)}}

und stetig mit dem Wert 1 an der Stelle Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x=x_k } fortgesetzt. Die Hilfsfunktion Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle G(x,y) } ist außerhalb der Diagonalen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x=y } definiert als

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle G(x,y):=\frac{H(x)-H(y)}{x-y}} und stetig fortgesetzt zu Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle G(x,x):=H'(x)} .

Auf den Nullstellen gilt Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle L_k(x_j)=\delta_{k,j}} , wobei das Kronecker-Delta verwendet wurde.

Sind jetzt Werte Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f_k } für jedes Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle k \isin I } vorgegeben, so ist eine Interpolationsfunktion definiert durch

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle F(x):=\sum_{k\in I}f_k\cdot L_k(x)=\sum_{k\in I}\frac{G(x,x_k)}{G(x_k,x_k)}f_k} .

Im Falle einer abzählbaren Nullstellenmenge muss die Konvergenzbedingung

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \sum_{k\in I}\left|\frac{f_k}{H'(x_k)(1+|x_k|)}\right|<\infty}

erfüllt sein.

Beispiele

• Mit vorgegebenen Stützstellen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \{x_1,\dotsc,x_N\} } und einer reellen Funktion Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle h } mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle h(0)=0 } , Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle h'(0)\neq 0 } kann die Funktion Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle H(x):=h(x-x_1) \dotsm h(x-x_N) } gebildet werden. Dann erhält man

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle L_k(x)=\frac{h(x-x_k)}{h'(0)(x-x_k)}\cdot\prod_{j\ne k}\frac{h(x-x_j)}{h(x_k-x_j)}} .

Das aus Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle h(x)=x } resultierende Interpolationsverfahren ist die Lagrange-Interpolation. Andere Beispiele sind Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle h(x)=x/(1+x^2) } für nach Unendlich gegen Null fallende Interpolationsfunktionen oder Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle h(x)=\sin(x) } für eine beschränkte Interpolationsfunktion mit übersichtlicher Berechnungsformel.

• Mit dem Kreisteilungspolynom Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle H(x):=x^N-1 } , d. h. den Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle N } -ten Einheitswurzeln Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x_k:=\exp(i2\pi\,k/N)} , Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle k=1,\dots,N } , als Stützstellen, ergibt sich die Diskrete Fourier-Transformation als Verfahren zur Berechnung der Koeffizienten des Interpolationspolynoms. Es gilt Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle L_N(x)=\frac1N(1+x+\dotsb+x^{N-1})} und allgemein Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle L_k(x)=L_N(\bar x_k\,x)} , so dass

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle F(x)=\sum_{n=0}^{N-1}x^n\cdot\frac1N\sum_{k=1}^N f_k\bar x_k^n} ist.

• Mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle H(x):=\sin(\pi x) } und den Nullstellen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x_k=k } , Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle k \isin \mathbb{Z} } , ergibt sich als Interpolationsfunktion die Kardinalreihe

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \sum_{k\in\mathbb Z}\left|\frac{f_k}{1+|k|}\right|<\infty} .

Stützstellendarstellung von Polynomen

Sei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p(x) = a_0 + a_1x + a_2x^2 + \dotsb + a_{n-1}x^{n-1} } ein Polynom. Dieses Polynom lässt sich in der sogenannten Koeffizientendarstellung durch die Angabe des Vektors Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (a_0, \dotsc, a_{n-1})} darstellen. Eine alternative Darstellung, die ohne die Koeffizienten Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a_0, \dotsc, a_{n-1}} auskommt, besteht in der Stützstellendarstellung. Dabei wird das Polynom für Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n } Werte Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x_i} mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 0 \le i \le n-1} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle i \in \N} ausgewertet, d. h., es werden die Funktionswerte Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p(x_i)=y_i} berechnet. Das Paar von Vektoren Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle ((x_0, \dotsc, x_{n-1}),(y_0, \dotsc, y_{n-1}))} bezeichnet man als die Stützstellendarstellung des Polynoms Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p } . Ein wesentlicher Vorteil dieser Darstellung besteht darin, dass zwei Polynome in Stützstellendarstellung in Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \Theta(n) } (s. Landau-Symbole) Schritten multipliziert werden können. In Koeffizientendarstellung werden hingegen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \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.

Anwendungen

Interpolation bei der Skalierung eines Bildes

In vielen Anwendungen von Interpolationsverfahren wird behauptet, dass durch Interpolation neue Information aus bestehenden Daten hinzugewonnen wird. 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.

Eine bekannte Anwendung der Interpolation ist die digitale Signalverarbeitung. Bei der Umwandlung eines Signals von einer niedrigen Abtastrate in eine hohe (siehe Abtastratenkonvertierung) werden die Abtastwerte des Ausgabesignals aus denen des Eingabesignals interpoliert. Ein Spezialfall ist die Skalierung von Bildern in der Computergrafik.

Interpolation in höheren Dimensionen

Die oben gezeigten einfachen Verfahren sind meist nur für 1D-Probleme beschrieben. Für höhere Dimensionen geeignet sind Spline-Interpolationen mit z. B. Thinplate-Splines oder anderen Radial-Basisfunktionen oder das Kriging-Verfahren bzw. die Gaußprozessregression. Eine einfache Möglichkeit zur Interpolation von Punkten in höheren Dimensionen (Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \R^2 ,\R^3, ...} ), die in einem regelmäßigen Gitter vorliegen, ist die rekursive Anwendung von 1D-Interpolationen.

Am Beispiel der bilinearen Interpolation sei dieses erläutert.

Gegeben sind Zahlenwerte an den Eckpunkten Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle Q_{11}} , Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle Q_{12}} , Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle Q_{21}} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle Q_{22}} . Gesucht ist der interpolierte Wert an Stelle Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle P} .

Vorgehensweise: Die lineare Interpolation wird zweimal angewendet, z. B. zuerst für die x-Richtung. Es wird Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle R_1} aus Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle Q_{11}} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle Q_{21}} mit der linearen 1D-Interpolation ermittelt. Anschließend wird Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle R_2} auf gleiche Weise bestimmt. Der Wert an Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle P} ergibt sich als lineare 1D-Interpolation in y-Richtung zwischen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle R_1} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle R_2} .

3D: Für eine trilineare Interpolation gibt es Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 2^3} Eckpunkte mit Zahlenwerten. Die erste Interpolation auf der x-Achse ergibt Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 2^2} Zwischenpunkte, die auf einer Ebene senkrecht zu Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x = P_x} liegen. In dieser Ebene wird in y-Richtung interpoliert bei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle y = P_y} und es ergeben sich Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 2^1} Zwischenpunkte auf einer Linie in z-Richtung an Position Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x = P_x, y = P_y} . Die letzte Interpolation auf dieser Linie ergibt schließlich Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 2^0} Punkte, also die gesuchte Lösung.

Für eine beliebige Dimension ist das Verfahren durch sukzessive Rekursion anwendbar.

Literatur

• Josef Stoer: Numerische Mathematik 1. 8. Auflage, Springer 1999.
• Bernd Jähne: Digitale Bildverarbeitung. 4. Auflage, Springer 1997.
• Oppenheim, Schafer: Zeitdiskrete Signalverarbeitung. Oldenbourg 1992.
• Crochiere, Rabiner: Multirate Digital Signal Processing. Prentice Hall 1983.

Weblinks

• Online-Tool für Lineare und Quadratische Interpolation mit Visualisierung
• Seite zu Newton, Lagrange und Cubic Spline ebenfalls mit Java-Applet