Interpolation (Mathematik)

Der Begriff Interpolation bezeichnet eine Klasse von Problemen und Verfahren aus der numerischen Mathematik. Zu gegebenen diskreten Daten (z.B. Messwerte) soll eine kontinuierliche Funktion (die sogenannte Interpolante) gefunden werden, die diese Daten abbildet. Man sagt dann, die Funktion interpoliert die Daten, im Gegensatz zur Approximation, bei der die Daten nur angenähert werden. Bei dem verwandten Problem der Extrapolation werden Werte abgeschätzt, die über den Definitionsbereich der Daten hinausgehen.

Interpolationsprobleme

Das allgemeine Interpolationsproblem

Gegeben seien Paare von reellen oder komplexen Zahlen $(x_{i},\,f_{i})$, die man als Stützstellen bezeichet. 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.

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.

Nichtlineare Interpolationsprobleme

Zu den wichtigsten nichtlinearen Interpolationsproblemen zählt

• das trigonometrische: $\Phi (x,\,a_{0},\ldots ,a_{n})=a_{0}+a_{1}e^{x_{i}}+a_{2}e^{2x_{i}}+\cdots +a_{n}e^{nx_{i}}$

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

Interpolationsverfahren

Lineare Interpolation

Am einfachsten und wohl auch in der Praxis am häufigsten benutzt wird die lineare Interpolation, bei der zwei gegebene Datenpunkte $f_{0}$ und $f_{1}$ durch eine Strecke verbunden werden. Als Faustregel merkt man sich

$f(x)=f_{0}+{{f_{1}-f_{0}} \over {x_{1}-x_{0}}}\,(x-x_{0})$. Dies entspricht einer Konvexkombination der Endpunkte $(x_{0},\,f_{0})$ und $(x_{1},\,f_{1})$.

Höhergradige Polynome

Der Fundamentalsatz der Algebra garantiert, dass man zu $n$ Datenpunkten genau ein Interpolationspolynom $n$-ten Grades finden kann. Die Bestimmung der Koeffizienten erfordert die Lösung eines linearen Gleichungssystems. Man erhält das Interpolationspolynom z.B. mit Hilfe der Formel von Lagrange:

$f(x)=\sum _{i=o}^{n}\,f_{i}\prod _{k=0,k\neq i}^{n}{x-x_{k} \over x_{i}-x_{k}}$

Weitere Verfahren zur Polynominterpolation siehe dort.

Stückweise Interpolation

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

Hermite-Interpolation

Sind zusätzlich zu den Stützstellen $(f_{i},\,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.

Trigonometrische Interpolation

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

$g(x)={1 \over 2}a_{0}+\sum _{k=1}^{N-1}(a_{k}\cos kx+b_{k}\sin kx)+{1 \over 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 {2 \over n}\sum _{i=1}^{n}f(x_{i})\cos kx_{i}$ und $b_{k}\approx {2 \over n}\sum _{i=1}^{n}f(x_{i})\sin kx_{i}$.

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

Anwendungen

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.

Bildverarbeitung

Datei:Bild interpolation.png

In der Bildverarbeitung 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 dem bekannten "Treppchen-Effekt". Das Phänomen ist allgemein auch als Aliasing 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.

In gängigen Bildverarbeitungssystemen wird häufig bilineare oder bikubische Interpolation verwendet. Die Interpolationsverfahren sind meist in Form von digitalen Filtern implementiert (Gauß-Filter, Lanczos-Filter).

Siehe auch

• Approximation, Extrapolation

Literatur

• Josef Stoer, Numerische Mathematik 1, 8. Auflage, Springer 1999