Direkt zum Inhalt

Lexikon der Mathematik: Spline-Interpolation

Theorie der Interpolation mit Splinefunktionen.

Es seien k, m natürliche Zahlen, a = x0< x1< … < xk< xk+1 = b, eine Knotenmenge und es bezeichne Sm(x1, …, xk) den (m + k + 1)-dimensionalen Raum der Splinefunktionen, d. h. die Menge der (m − 1)-fach differenzierbaren stückweisen Polynome vom Grad m.

Eine Basis {Bim−1, i = 1, …, m + k + 1} von Sm(x1, …, xk) erhält man, indem man zusätzliche Knoten xm< … < x−1< a, b< xk+2< … < xk+m+1 festlegt, und die entsprechenden B-Splinefunktionen (B-Splines) Bim−1, i = 1, …, m + k + 1, definiert. Eine Menge \begin{eqnarray}T=\{t_j:j=1,\ldots,m+k+1\}\subseteq[a,b]\end{eqnarray} von m + k + 1 Punkten mit der Eigenschaft \begin{eqnarray}t_j\lt t_{j+1}, \,\,\, j=1,\ldots,m+k,\end{eqnarray} heißt Lagrange-Interpolationsmenge für Sm(x1, …, xk), falls für jede beliebig vorgegebene stetige Funktion f auf [a, b] stets ein eindeutig bestimmter Spline sfSm(x1, …, xk) existiert mit der Eigenschaft \begin{eqnarray}s_f(t_j)=f(t_j),\,\,\,j=1,\ldots,k.\end{eqnarray} Interpolation mit Splines hat im Gegensatz zur polynomialen Interpolation den Vorteil, daß bei fixiertem Grad m die Anzahl der Freiheitsgrade durch das Einfügen von zusätzlichen Knoten erhöht werden kann. Jedoch ist das Interpolationsproblem für Splines nicht immer lösbar, denn die Punkte von T müssen in geeigneter Weise über [a, b] verteilt sein. Dies ist der Inhalt der folgende Charakterisierungsaussage für Interpolation mit Splines, welche von I.J. Schoenberg und A. Whitney im Jahr 1953 erstmalig formuliert wurde.

Die folgenden Aussagen sind äquivalent:

  • Die Menge T ist eine Interpolationsmenge von Sm(x1, …, xk).
  • Die Matrix ((Bim−1(tj))i,j=1, …, m+k+1ist regulär.
  • Jedes Intervall der Form (xi, xi+m+j), j ≥ 1, enthält mindestens j Punkte von T.
  • Jedes Intervall der Form [xi, xi+j], j ≥ 1, enthält maximal m + j Punkte von T.
  • Es gilt: tj< xj< tj+m+1, j = 1, …, k.

    Analoge Aussagen gelten für Hermite-Interpolation und Splines mit mehrfachen Knoten. Erfüllt eine Punktmenge T eine dieser Bedingungen (und damit alle), so sagt man auch, sie erfüllt die Schoenberg-Whitney-Bedingung.

    Darüber hinaus existieren klassische Ansätze der Interpolation mit Splines aus S2r+1(x1, …, xk), wobei r ≥ 1. Diese gehen von den Interpolationsbedingungen \begin{eqnarray}s_f(x_i)=f(x_i),\,\,\,i=0,\ldots,k+1.\end{eqnarray} aus und fordern zusätzliche Eigenschaften am Rand, sogenannte Randbedingungen. Abhängig von der Art der Randbedingungen spricht man von einem vollständigen, natürlichen, oder periodischen Spline-Interpolationsproblem. Die (r + 1)-te Ableitung \({s}_{f}{}^{(r+1)}\) dieser Spline-Interpolanten besitzt Optimalitätseigenschaften im Sinne der L2-Approximation.

  • Die Theorie der Interpolation mit Splines in einer Variablen gilt im Gegensatz zur Theorie der Interpolation mit bivariaten Splines als nahezu vollständig entwickelt. Bivariate Splines \({S}_{m}^{r}(\Delta)\) vom Grad m mit Differenzierbarkeit r sind hinsichtlich einer regulären Triangulierung Δ (d. h. eine Menge von abgeschlossenen Dreiecken, so daß der Schnitt von je zwei Dreiecken entweder leer, eine gemeinsame Kante oder ein gemeinsamer Eckpunkt ist) eines Grundbereichs Ω der Ebene wie folgt definiert: \begin{eqnarray}{S}_{m}^{r}(\Delta)=\{s\in {C}^{r}(\Omega):s{|}_{T}\in {\Pi}_{m},T\in \Delta \}.\end{eqnarray} Hierbei ist \begin{eqnarray}{\Pi}_{m}=span\{{x}^{i}{y}^{j}:i,j\ge 0,i+j\le m\}\end{eqnarray} der Raum der bivariaten Polynome vom totalen Grad m. Bivariate Splines besitzen eine äußerst komplexe Struktur. So ist beispielsweise die Dimension dieser Räume im Fall m< 3r+2, (m, r) ≠ (4, 1), im allgemeinen nicht bekannt. Für Klassen von Triangulierungen, beispielsweise gleichmäßige Triangulierungen, kennt man jedoch die Dimension der bivariaten Splineräume. Gleichmäßige Triangulierungen entstehen aus gleichmäßigen Rechtecksgittern durch Einfügen einer oder beider Diagonalen in jedes Rechteck (Δ1-Zerlegung, Δ2-Zerlegung).

    Die Untersuchung dieser für Anwendungen in den verschiedensten wissenschaftlichen und technischen Bereichen wichtigen bivariaten Splineräume ist Inhalt aktueller Forschung. Dies gilt insbesondere für die Entwicklung von Interpolationsmethoden für diese Splines.

    Ein klassische Ansatz von Clough und Tocher aus dem Jahr 1965 basiert auf einer Zerlegung jedes Dreiecks von Δ in drei sogenannte Mikro-Dreiecke. Die resultierende Triangulierung ΔCT wird Clough-Tocher-Zerlegung genannt. Eine Hermite-Interpolationsmenge hinsichtlich \({S}_{3}^{1}({\Delta}_{CT})\) erhält man, indem man an jedem Eckpunkt von Δ den Funktionswert und den Gradienten vorschreibt, und zudem im Mittelpunkt jeder Kante e von Δ die Ableitung orthogonal zu e festlegt. Hermite-Interpolation mit differenzierbaren quadratischen Splines wurde 1977 von Powell und Sabin betrachtet. Hierbei zerlegt man jedes Dreieck in geeigneter Weise in sechs Mikrodreiecke und interpoliert an jedem Eckpunkt von Δ den Funktionswert und den Gradienten. Alternative klassische Methoden basieren auf dem Finite-Elemente-Ansatz. Diese Methoden verwenden im allgemeinen Supersplines hohen Grades (m ≥ 4r + 1), benötigen aber keine Unterteilungen der Dreiecke.

    Abbildung 1 zum Lexikonartikel Spline-Interpolation
    © Springer-Verlag GmbH Deutschland 2017
     Bild vergrößern

    Clough-Tocher- und Powell-Sabin-Zerlegung. Die Interpolationsbedingungen sind durch Kreise und Querstriche symbolisiert.

    Diese Interpolationsmethoden sind lokal, d. h. eine Änderung einer einzelnen Interpolationsbedingung hat nur in einer kleinen Umgebung dieser Stelle einen Einfluß auf die interpolierende Splineoberfläche.

    Erst in jüngster Zeit wurden Lagrange-Interpolationsmengen für bivariate Splines konstruiert. Die Untersuchungen von G. Nürnberger, Th. Rießinger und G. Walz behandeln hierbei gleichmäßige Triangulierungen sowie Hermite- und Lagrange-Interpolation für Splines beliebiger Differenzierbarkeitsordnung und beliebigen Grades. O. Davydov, G. Nürnberger und F. Zeilfelder entwickelten Resultate hinsichtlich lokaler Hermite-Interpolation für Splines hohen Grades m ≥ 3r + 2 und beliebiger Differenzierbarkeit r, globaler Lagrange- und Hermite-Interpolation für differenzierbare Splines hinsichtlich beliebiger, und (im Falle kleinen Grades) spezieller Klassen von Triangulierungen, und Methoden zur Konstruktion von für Interpolation mit Splines geeigneten Triangulierungen. Im Jahr 2000 wurden von G. Nürnberger, L.L. Schumaker und F. Zeilfelder die ersten lokalen Lagrange-Interpolationsmethoden für differenzierbare kubische Splines auf Triangulierungen bzw. Rechteckszerlegungen entwickelt. Die Untersuchungen zeigen, daß solche Konstruktionen die Zerlegung von nur einigen Dreiecken bzw. Rechtecken erfordern.

    [1] de Boor, C.: A Practical Guide to Splines. Springer-Verlag New York, 1978.
    [2] Nürnberger, G.: Approximation by Spline Functions. Springer-Verlag Heidelberg/Berlin, 1989.
    [3] Schumaker, L. L.: Spline Functions: Basic Theory. John Wiley & Sons New York, 1981.

    • Die Autoren
    - Prof. Dr. Guido Walz

    Schreiben Sie uns!

    Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

    Partnerinhalte

    Bitte erlauben Sie Javascript, um die volle Funktionalität von Spektrum.de zu erhalten.