Direkt zum Inhalt

Lexikon der Mathematik: Spline-Approximation

Theorie der besten Approximation mit Splinefunktionen.

Die Theorie der Spline-Approximation beschäftigt sich mit Gütefragen der Näherung mit Splines und behandelt Fragen der Charakterisierung, Eindeutigkeit und effizienten Berechnung von besten Approximationen mit Splines. Fragestellungen der letztgenannten Art führen für Splines mit freien Knoten in das Gebiet der nichtlinearen Approximation.

Für Splines mit festen Knoten a = x0 < x1 < ⋯ < xk < xk+1 = b, d. h. Elementen des (m + k + 1)-dimensionalen Raums Sm(x1, …, xk) der (m − 1)-fach differenzierbaren stückweisen Polynome vom Grad m, existieren in der Literatur eine Vielzahl von Approximationsresultaten.

Splines sind Standardräume mit der schwach Tschebyschewschen (schwach Haarschen) Eigenschaft, d. h., jeder nicht-verschwindende Spline besitzt maximal m + k Vorzeichenwechsel in [a, b]. Im Gegensatz zu den Polynomen bilden Splines keinen Haarschen Raum, denn es existieren nichtverschwindende Splines mit unendlich vielen Nullstellen in [a, b]. Damit folgt aus den klassischen Approximationsaussagen für Haarsche Räume, daß für vorgebenes stetiges f auf [a, b] beste Approximationen sfSm(x1, …, xk) hinsichtlich der Maximumnorm || · || nicht durch ein einfaches Alternantenkriterium charakterisiert werden können, und daß diese im allgemeinen nicht eindeutig sind. Der folgende Satz von Rice-Schumaker zeigt, daß beste Approximationen mit Splines durch ein komplexeres Alternantenkriterium charakterisiert werden. Das Resultat wurde von J.R. Rice and L.L. Schumaker Ende der 1960er Jahre unabhängig entdeckt und bewiesen.

Es sei f eine stetige Funktion auf [a, b] und sfSm(x1, …, xk). Dann sind die folgenden Aussagen äquivalent:

  • Der Spline sf ist eine beste Approximation an f.
  • Es existiert ein Intervall [xp, xp+q] ⊆ [a, b], q ≥ 1, welches m + q + 1 Punkte t1 < ··· < tm+q+1enthält mit der Eigenschaft: \begin{eqnarray}{(-1)}^{l}\sigma (f-{s}_{f})({t}_{l})=\parallel f-{s}_{f}{\parallel}_{\infty}\end{eqnarray}für l = 1, …, m + q + 1, wobei σ ∈ {−1, 1}.
  • O. Davydovgab 1993 einen vollständigen Charakterisierungssatz für beste Approximationen durch periodische Splines an. Im nicht schwach-Tschebschewschen Fall gerader Dimension treten hierbei neben den Alternantenbedingungen des obigen Satzes zusätzliche Bedingungen auf.

    Ein Remez-Algorithmus zur Berechnung einer besten Approximation aus Sm(x1, …, xk) wurde von G. Nürnberger und M. Sommer Mitte der 1980er Jahre entwickelt.

    Seit Beginn der 80er Jahre wird die starke Eindeutigkeit bester Approximationen sf für Splineräume untersucht. Der folgende Satz aus dem Jahr 1985 von G. Nürnberger charakterisiert stark eindeutig beste Approximationen aus Sm(x1, …, xk).

    Es sei f eine stetige Funktion auf [a, b] und sfSm(x1, …, xk). Dann sind die folgenden Aussagen äquivalent:

  • Der Spline sf ist eine stark eindeutig beste Approximation an f.
  • Jedes Intervall (xi, xi+m+j), j ≥ 1, enthält j + 1 Punkte t1 < ··· < tj+1mit der Eigenschaft: \begin{eqnarray}{(-1)}^{l}\sigma (f-{s}_{f})({t}_{l})=\parallel f-{s}_{f}{\parallel}_{\infty},\end{eqnarray}für l = 1, …, j + 1, wobei σ ∈ {−1, 1}.
  • F. Zeilfelder gab 1996 einen vollständigen Charakterisierungssatz für die stark eindeutig beste Approximation durch periodische Splines an. Im nicht schwach Tschebschewschen Fall gerader Dimension treten hierbei neben den Alternantenbedingungen des obigen Satzes zusätzliche Bedingungen auf.

    Neben diesen Charakterisierungs- und Eindeutigkeitsresultaten hinsichtlich bester Approximationen mit Splines sind Aussagen über die Güte von Spline-Approximanten von Wichtigkeit. Ist j ∈ {0, …, m} und f eine j-fach auf [a, b] differenzierbare Funktion, so gilt \begin{eqnarray}dist(f,{S}_{m}({x}_{1},\ldots, {x}_{k}))\le K{h}^{j}\omega ({f}^{(j)},h),\end{eqnarray} wobei K > 0 und h = max{|xi+1xi| : i = 0, …, k}. Hierbei ist dist(f, Sm(x1, …, xk)) die Minimalabweichung und ω(., h) der Stetigkeitsmodul. Insbesondere erhält man wegen \begin{eqnarray}\omega ({f}^{(j)},h)\le h\parallel {f}^{(j+1)}{\parallel}_{\infty}\end{eqnarray} für eine (m + 1)-fach differenzierbare Funktion f die folgende Abschätzung: \begin{eqnarray}dist(f,{S}_{m}({x}_{1},\ldots, {x}_{k}))\le K{h}^{m+1}\parallel {f}^{(m+1)}{\parallel}_{\infty}.\end{eqnarray} Splineräume besitzen somit die optimale Approximationsordnung m + 1. Abschätzungen der obigen Art wurden in der Literatur hinsichtlich Lp-Normen und für Funktionen f aus speziellen Klassen von Funktionenräumen wie z. B. Sobolew-Räumen entwickelt.

    Für bivariate Splines \({S}_{m}^{r}(\Delta)\) vom Grad m und Differenzierbarkeit r gilt die obigen Aussage hinsichtlich der Approximationsordnung im allgemeinen nicht mehr. Diese Räume sind für eine gegebene, reguläre Triangulierung Δ (d. h., eine Menge von abgeschlossenen Dreiecken in der Ebene so, daß der Schnitt von je zwei Dreiecken entweder leer, eine gemeinsame Kante oder ein gemeinsamer Eckpunkt ist) eines Grundbereichs Ω 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.

    1988 wurde von C. de Boor und K. Höllig gezeigt, daß die Approximationsordnung von \({S}_{m}^{r}(\Delta)\) stets optimal ist, falls m ≥ 3r + 2 gilt. Im verbleibenden Fall m < 3r + 2 wurde von C. de Boor und Q. Jia Anfang der 90er Jahre nachgewiesen, daß der Raum \({S}_{m}^{r}(\Delta)\) im allgemeinen keine optimale Approximationsordnung besitzt. Neuere Forschungsansätze untersuchen deshalb Klassen von Triangulierungen und Modifikationsstrategien für gegebene Triangulierungen, um diesen Defekt des Raums \({S}_{m}^{r}(\Delta)\) im Fall m < 3r + 2 zu umgehen.

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

    Lesermeinung

    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.

    • Die Autoren
    - Prof. Dr. Guido Walz

    Partnervideos