5. Interpolation

In diesem Kapitel wollen wir uns mit Interpolationsproblemen aus Sicht der numerischen Mathematik beschäftigen. Bei der Interpolation versucht man im Allgemeinen eine Approximation einer unbekannten Funktion zu finden, die durch eine endliche Anzahl gegebener Datenpunkte exakt verläuft und dazwischen sinnvoll interpoliert. Je nach Anwendung kann man verschiedene Bedingungen an die interpolierende Lösung stellen, so dass es eine Vielzahl von Methoden zur Interpolation gibt.

Bevor wir uns der mathematischen Formulierung des Problems widmen wollen wir ein einführendes Beispiel zur Motivation geben.

Beispiel 5.1 (Interpolation für Bildskalierung)

Ein mögliches Einsatzgebiet von zweidimensionaler Interpolation ist das Skalieren von digitalen Bildern in der mathematischen Bildverarbeitung. Beim Vergrößern eines Bildes mit niedriger Auflösung in Abbildung Abb. 5.1 werden die Pixelwerte auf ein Pixelgitter mit höherer Auflösung projiziert. Die dabei entstehenden Lücken im Bild mit höherer Auflösung müssen durch Interpolation aufgefüllt werden. Je nach Interpolationsmethode erhält man ein Ergebnis mit klaren Kanten, jedoch blockartigen Strukturen (siehe Abbildung Abb. 5.2) oder verwaschenen Kanten, jedoch glatten Strukturen (siehe Abbildung Abb. 5.3).

Abb. 5.1 Computergrafik mit ursprünglicher Skalierung

\

Abb. 5.2 Nearest-Neighbor Interpolation

Abb. 5.3 Bikubische Interpolation

\

Abb. 5.4 Digitales Foto mit ursprünglicher Skalierung

\

Abb. 5.5 Nearest-Neighbor Interpolation

Abb. 5.6 Bikubische Interpolation

Man beachte, dass durch Interpolation keine neuen Informationen über eine den Daten zu Grunde liegende, unbekannte analytische Funktion hinzugewonnen werden können. Vielmehr versucht man eine glatte Fortsetzung der gegebenen Daten zu finden, die plausibel für die Anwendung ist.

Definition 5.1 (Interpolationsproblem)

Wir betrachten im Folgenden eine Menge mit \(n+1 \in \mathbb{N}\) Datenpunkten

\[(x_i, f_i) \in \mathbb{R}^2, \quad i=0,\ldots,n.\]

Hierbei geht man davon aus, dass die gegebenen Stützwerte \(f_i\) die beobachteten Funktionswerte einer unbekannten, kontinuierlichen Funktion \(f \colon \mathbb{R} \rightarrow \mathbb{R}\) an den Stützstellen \(x_i\) darstellen.

Das allgemeine Interpolationsproblem besteht nun darin eine Ansatzfunktion

\[g \colon \mathbb{R} \times \mathbb{R}^{n+1} \rightarrow \mathbb{R},\]

mit freien Parametern \(a_0,\ldots,a_n \in \mathbb{R}\) zu finden, so dass diese die gegebenen Daten interpoliert, d.h.,

(5.1)\[g(x_i;a_0,\ldots,a_n) \ = \ f_i, \qquad i=0,\ldots,n.\]

Das heißt wir sind interessiert an einer Funktion \(g\), die die gegeben Daten exakt repräsentiert und zwischen den Daten sinnvoll (möglichst stetig) verläuft. Mögliche Beispiele für die Wahl von \(g\) sind Polynomfunktionen, trigonometrische Funktionen oder Splines.

Wenn man diese Aufgabe mit dem Ziel der linearen Ausgleichsrechnung in Über- und unterbestimmte lineare Gleichungssysteme vergleicht, so stellt man fest, dass die Forderungen an eine interpolierende Funktion restriktiver sind. Der Grund hierfür ist, dass im Fall der linearen Ausgleichsrechnung eine Approximation der gegebenen Daten gesucht wird, die die Werte nicht exakt trifft, jedoch die Verteilung der Daten gut annähert und dabei den unvermeidbaren Fehler minimiert.

Ein Spezialfall des allgemeinen Interpolationsproblems in Definition 5.1 ist die lineare Interpolation mit der wir uns in diesem Kapitel hauptsächlich beschäftigen möchten.

Definition 5.2 (Lineares Interpolationsproblem)

Wir nennen ein Interpolationsproblem linear falls die Ansatzfunktion \(g\) in (5.1) nur linear von den Parametern \(a_0,\ldots,a_n\) abhängt, d.h. es gilt

(5.2)\[g(x; a_0, \ldots, a_n) \ \coloneqq \ a_0g_0(x) + a_1g_1(x) + \ldots + a_ng_n(x).\]

Die Funktionen \(g_k \colon \R \rightarrow \R, k = 0,\ldots,n\) werden in der Regel als Basisfunktionen des Funktionenraumes gewählt in dem die Ansatzfunktion \(g\) zu bestimmen ist.

Das lineare Interpolationsproblem kann also als ein lineares Gleichungssystem der Form \(Ax = b\) dargestellt werden mit:

(5.3)\[A \ \coloneqq \ \begin{pmatrix} g_0(x_0) & \cdots & g_n(x_0) \\ \vdots & \ddots & \vdots \\ g_0(x_n) & \cdots & g_n(x_n) \end{pmatrix}, \qquad x \ \coloneqq \ \begin{pmatrix} a_0 \\ \vdots\\ a_n \end{pmatrix}, \qquad b \ \coloneqq \ \begin{pmatrix} f_0 \\ \vdots \\ f_n \end{pmatrix}.\]

Jetzt wird der Zusammenhang zwischen linearer Ausgleichsrechnung und linearer Interpolation deutlich. Da wir \(n+1\) gemessene Datenpunkte vorliegen haben und wir \(n+1\) unbekannte Variablen suchen ist klar, dass wir es mit einem linearen Ausgleichsproblem mit quadratischer Matrix \(A \in \mathbb{R}^{(n+1) \times (n+1)}\) zu tun haben. Das lineare Interpolationsproblem (5.2) ist also ein Spezialfall des linearen Ausgleichsproblems (3.2).

Bemerkung 5.1 (Wahl der Basisfunktionen)

Wir werden im folgenden Abschnitt erkennen, dass auch bei unterschiedlicher Wahl der Basisfunktionen \(g_k \colon \R \rightarrow \R, k = 0,\ldots,n\) in Definition 5.2 eine eindeutige Ansatzfunktion \(g\) als Lösung des linearen Interpolationsproblems bestimmt ist.

Dennoch spielt die Wahl dieser Basisfunktionen \(g_i\) eine entscheidende Rolle für die Numerik, da sie Auswirkungen auf den Rechenaufwand und die Entwicklung von numerischen Fehlern hat.