Interpolation

aus Freepedia, der freien Wissensdatenbank

Der Begriff Interpolation bezeichnet eine Klasse von Problemen und Verfahren aus der numerischen Mathematik. Zu gegebenen diskreten Daten (z.B. Messwerten) soll eine kontinuierliche Funktion (die so genannte Interpolante) gefunden werden, die diese Daten abbildet. Man sagt dann, die Funktion interpoliert die Daten.

Inhaltsverzeichnis 1 Einführung 2 Interpolationsprobleme 2.1 Das allgemeine Interpolationsproblem 2.2 Das lineare Interpolationsproblem 2.3 Nichtlineare Interpolationsprobleme 3 Interpolationsverfahren 3.1 Lineare Interpolation 3.2 Höhergradige Polynome 3.3 Stückweise Interpolation 3.4 Hermite-Interpolation 3.5 Trigonometrische Interpolation 3.6 Logarithmische Interpolation 4 Allgemeine lineare Interpolation 5 Stützstellendarstellung von Polynomen 6 Anwendungen 6.1 Bildverarbeitung 7 Literatur 8 Weblinks

Einführung

Bild:Punkte Interpolation.png

Manchmal kennen wir von einer Funktion nur einzelne Punkte, 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 <math> f </math> benötigt. Diese ergeben sich auch bei Unkenntnis von <math> f </math> 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.

Interpolationsprobleme

Das allgemeine Interpolationsproblem

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

Das lineare Interpolationsproblem

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

<math>\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)</math>.

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

<math>\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</math>.

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

<math>\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)</math>

Nichtlineare Interpolationsprobleme

Zu den wichtigsten nichtlinearen Interpolationsproblemen zählt

• das rationale: <math>\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}}</math>

Interpolationsverfahren

Lineare Interpolation

Am einfachsten und wohl auch in der Praxis am häufigsten benutzt wird die von Isaac Newton begründete lineare Interpolation, bei der zwei gegebene Datenpunkte <math>f_0</math> und <math>f_1</math> durch eine Strecke verbunden werden. Es gilt:

<math>f(x) = f_0 + {{f_1-f_0}\over{x_1-x_0}}\,(x-x_0)</math>. Dies entspricht einer Konvexkombination der Endpunkte <math>(x_0,\,f_0)</math> und <math>(x_1,\,f_1)</math>.

Detaillierte Erläuterungen siehe Allgemeine lineare Interpolation

Höhergradige Polynome

Bild:Polynom interpolation.png

Der Fundamentalsatz der Algebra garantiert, dass man zu <math>n+1</math> Datenpunkten genau ein Interpolationspolynom <math>n</math>-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:

<math>p(x)=\sum_{i=0}^{n}\,f_i\prod_{k=0,k\neq i}^n{x-x_k \over x_i-x_k}</math>

Weitere Verfahren zur Polynominterpolation siehe dort.

Stückweise Interpolation

Bild:Linear interpolation.png Bild:Spline interpolation.png

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 <math>(f_i,\,x_i)</math> auch noch die <math>k</math>-Ableitungen <math>f^{(k)}(x_i) = f^{(k)}_i</math> 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

<math>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</math>

entspricht einer Fourier-Entwicklung der unbekannten Interpolanten. Die Fourier-Koeffizienten <math>a_k</math> und <math>b_k</math> berechnen sich zu

<math>a_k\approx {2\over n}\sum_{i=1}^n f(x_i)\cos kx_i</math> und <math>b_k\approx {2\over n}\sum_{i=1}^n f(x_i)\sin kx_i</math>.

Dabei wird angenommen, dass die Stützstellen <math>x_i</math> im Intervall <math>[0;\,2\pi]</math> ä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 <math>f_0(x_0)</math> und <math>f_1(x_1)</math> durch eine logarithmische Kurve verbunden. Es gilt:

<math>\frac{ \ln f- \ln f_0}{ \ln f_1- \ln f_0} = \frac{x-x_0}{x_1-x_0}</math>

Oder anders formuliert:

<math>f(x) = f_0 \cdot \exp \left\lbrace \frac{(x-x_0)( \ln f_1- \ln f_0)}{x_1-x_0} \right\rbrace</math>

Beispiel: χ²-Test

Allgemeine lineare Interpolation

Es sei <math> H(x) </math> eine reelle oder komplexe stetig differenzierbare Funktion mit Nullstellenmenge <math> \{ x_k: k\, \mathrm{aus}\, I\} </math>, wobei alle Nullstellen einfach sein müssen. Dabei kann <math> I </math> eine endliche Menge, wie z.B. <math> I= \{1,\dots,N\} </math>, oder eine abzählbare Menge, <math> I=\mathbb{R} </math> oder <math> I= \mathbb{Z} </math> sein. Damit sind die Interpolationskerne gegeben als

<math>L_k(x):=\frac{H(x)}{H'(x_k)(x-x_k)}=\frac{G(x,x_k)}{G(x_k,x_k)}</math> bei <math> x \neq x_k </math>

und stetig mit dem Wert 1 an der Stelle <math> x=x_k </math> fortgesetzt. Die Hilfsfunktion <math> G(x,y) </math> ist außerhalb der Diagonalen <math> x=y </math> definiert als

<math>G(x,y):=\frac{H(x)-H(y)}{x-y}</math> und stetig fortgesetzt zu <math>G(x,x):=H'(x)</math>.

Nun sieht man leicht, dass auf den Nullstellen <math>L_k(x_j)=\delta_{k,j}</math> gilt, wobei das Kronecker-Delta verwendet wurde.

Sind jetzt Werte <math> f_k </math> für jedes <math> k \isin I </math> vorgegeben, so ist eine Interpolationsfunktion definiert durch

<math>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</math>.

Im Falle einer abzählbaren Nullstellenmenge muss die Konvergenzbedingung

<math>\sum_{k\in I}\left|\frac{f_k}{H'(x_k)(1+|x_k|)}\right|<\infty</math>

erfüllt sein.

Beispiele:

• Mit vorgegebenen Stützstellen <math> \{x_1,\dots,x_N\} </math> und einer reellen Funktion <math> h </math> mit <math> h(0)=0 </math> , <math> h'(0)\neq 0 </math> kann die Funktion <math> H(x):=h(x-x_1) \dots h(x-x_N) </math> gebildet werden. Dann erhält man

<math>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)}</math>.

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

• Mit dem Kreisteilungspolynom <math> H(x):=x^N-1 </math>, d.h. den <math> N </math>-ten Einheitswurzeln <math>x_k:=\exp(i2\pi\,k/N)</math>, <math> k=1,\dots,N </math>, als Stützstellen, ergibt sich die Diskrete Fourier-Transformation als Verfahren zur Berechnung der Koeffizienten des Interpolationspolynoms. Es gilt <math>L_N(x)=\frac1N(1+x+\dots+x^{N-1})</math> und allgemein <math>L_k(x)=L_N(\bar x_k\,x)</math>, so dass

<math>F(x)=\sum_{n=0}^{N-1}x^n\cdot\frac1N\sum_{k=1}^N f_k\bar x_k^n</math> ist.

• Mit <math> H(x):=\sin(\pi x) </math> und den Nullstellen <math> x_k=k </math>, <math>k \isin \mathbb{Z} </math>, ergibt sich als Interpolationsfunktion die Kardinalreihe

<math>

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)} </math>. Diese spielt eine zentrale Rolle im Nyquist-Shannon-Abtasttheorem. Die Konvergenzbedingung lautet

<math>\sum_{k\in\mathbb Z}\left|\frac{f_k}{1+|k|}\right|<\infty</math>.

Stützstellendarstellung von Polynomen

Sei <math>p(x) = a_0 + a_1x + a_2x^2 + ... + a_{n-1}x^{n-1} </math> ein Polynom. Dieses Polynom lässt sich in der sogenannten Koeffizientendarstellung durch die Angabe des Vektors <math>(a_0,...,a_{n-1})</math> darstellen. Eine alternative Darstellung, die ohne die Koeffizienten <math>a_0,...,a_{n-1}</math> auskommt, besteht in der Stützstellendarstellung. Dabei wird das Polynom für <math> n </math> Werte <math>x_i</math> mit <math>0 \le i \le n-1</math> und <math>i \in \mathbb{N}</math> ausgewertet, d.h. es werden die Funktionswerte <math>p(x_i)=y_i</math> berechnet. Das Paar von Vektoren <math>((x_0,...,x_{n-1}),(y_0,...,y_{n-1}))</math> bezeichnet man als die Stützstellendarstellung des Polynoms <math> p </math>. Ein wesentlicher Vorteil dieser Darstellung besteht darin, dass zwei Polynome in Stützstellendarstellung in <math> \Theta(n) </math> Schritten multipliziert werden können. In Koeffizientendarstellung werden hingegen <math> \Theta(n^2) </math> 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

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.

Bildverarbeitung

Bild: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).

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

• Seite zur Interpolation mit Java Applet (ganz unten - Start Button)