Spline-Interpolation
Bei der Spline-Interpolation versucht man, gegebene Stützstellen, auch Knoten genannt, mit Hilfe stückweiser Polynome niedrigen Grades zu interpolieren. Während das Ergebnis einer Polynominterpolation durch unvorteilhaft festgelegte Stützstellen oft bis zur Unkenntlichkeit oszilliert, liefert die Splineinterpolation brauchbare Kurvenverläufe und Approximationseigenschaften (Rungephänomen). Die Spline-Interpolation lässt sich mit geringem, linearem Aufwand berechnen, liefert aber im Vergleich zur Polynominterpolation eine geringere Konvergenzordnung.
Vorlage für die Splineinterpolation (dritten Grades) ist das traditionelle, biegsame Lineal der Schiffbauer, die Straklatte (englisch Spline). Diese wird an beliebig vielen, vom Konstrukteur vorgegebenen Punkten fixiert und verbindet die Punkte dann durch eine glatte und harmonische Biegelinie. Die Straklatte erzeugt so die Linie durch alle Punkte mit minimaler Biegeenergie und kleinsten Krümmungen. Während bei der Straklatte die Wendestellen (Orte maximaler Linearität und minimaler Biegeenergie) in der Regel zwischen den Stützstellen liegen und die Stützstellen selbst Orte maximaler Krümmung sind (Orte maximaler Kraft durch Fixierung), liegen die Wendestellen bei der Polynomeninterpolation nahe an den Stützstellen, bei der polynomialen Bestapproximation sogar in den Stützstellen.
Die Begriffe Splineinterpolation bzw. Splinefunktion ohne weitere Zusätze bezeichnen immer die Splineinterpolation bzw. Splinefunktion dritten Grades. Beide Begriffe werden zumeist synonym verwendet. Der Begriff Spline wird jedoch zunehmend als Abkürzung für B-Spline, seltener auch für andere splineartige Linien wie die Bézierkurven, benutzt.
Smoothing Splines sind Splines, die nicht durch jeden Datenpunkt verlaufen müssen und können zur Signalglättung benutzt werden.
Gegebenheiten
Gegeben: eine natürliche Zahl <math>n\in \N</math> und <math>n+1</math> Stützstellen <math>x_0 < x_1 < \dotsb < x_{n-1} < x_n \in \R</math> sowie <math>n+1</math> Funktionswerte <math>y_0, y_1 \dotsc , y_{n-1}, y_n \in \R</math>. Gesucht ist eine stückweise polynomiale Funktion, ein Spline,
- <math>s \colon [x_0,x_n] \to \R</math>
mit <math>s(x_i) = y_i</math> für <math>i = 0, \dotsc, n</math>, bei der für <math>i = 0, \dotsc, n-1</math> die Einschränkungen
- <math>s_i := s|_{[x_i,x_{i+1}]} \; \colon \; [x_i,x_{i+1}] \to \R</math>
auf die Teilintervalle <math>[x_i,x_{i+1}] </math> Polynome sind.
Linear (einfacher Streckenzug)
Die einfachste Methode ist die Verwendung von Geraden zwischen jeweils zwei benachbarten Punkten, die Berechnung eines einfachen Splines als Streckenzug erfolgt auf dieselbe Weise, mit der man auch den Graphen zwischen zwei Punkten ermittelt:
- <math>\begin{align}
s(x) &= m \cdot x + b \\
&= \underbrace{\frac{y_2 - y_1}{x_2 - x_1}}_{=\,m} \cdot x
+ \underbrace{y_1 - \frac{y_2 - y_1}{x_2 - x_1} \cdot x_1}_{=\,b \,=\, y_{{}_1}-m\cdot x_{{}_1}}
\end{align}</math> oder auch {{#invoke:Vorlage:Anker|f |errCat=Wikipedia:Vorlagenfehler/Vorlage:Anker |errHide=1}}
- <math>s(x) = \frac{x_2 - x}{x_2 - x_1} \cdot y_1 + \frac{x - x_1}{x_2-x_1} \cdot y_2</math>
Konvergenz linear Splines
Seien <math>n+1</math> Stützstellen <math>a = x_0 < x_1 < \dots < x_n = b</math> gegeben und <math>h_i = x_{i+1} - x_{i} </math> die Abstände der Stützstellen für <math>i = 0, \dots, n-1 </math> und <math>h := \max_{i = 0, \dots, n-1} h_i </math> deren Maximum. Für die linear Splinefunktion <math>s(x)</math>, die die Funktion <math>f \in C^2([a, b])</math> interpoliert, d. h. es gilt <math>f(x_i) = s(x_i)</math> für <math>i = 0, 1, dots, n</math>, dann gilt die Fehlerabschätzung<ref name=":0">{{#invoke:Vorlage:Literatur|f}}</ref>
- <math>||f-s||_{L_\infty([a, b])} := \max_{x\in [a, b]} |f(x) - s(x)| \le \frac{h^2}{8} ||f||_{L_\infty([a, b])}. </math>
Damit konvergieren linear Splines quadratisch mit der Gitterweite <math>h </math> gegen die eigentliche Funktion <math>f </math>. Dies steht stark im Kontrast zur Polynominterpolation von <math>f </math> auf dem Intervall <math>[a, b] </math>, die im Allgemeinen nicht konvergiert mit zunehmenden Polynomgrad und stattdessen sogenannte Runge-Oszillationen aufweist.
Linearen Spline-Funktionen sind an den Stützstellen jedoch nicht differenzierbar. Dieses Problem lässt sich durch kubische Splines lösen, welche zweimal stetig differenzierbar sind.
Kubisch (Polynome 3. Grades)
Bei der Verbindung von Punkten mit Polynomen höheren Grades müssen zusätzlich zu den Stützstellen Eigenschaften definiert werden, wie die Polynome ineinander übergehen. Für kubische Splines sind in einer Dimension 4 Koeffizienten zu bestimmen und zwei weitere Bedingungen sind zu definieren.
Der kubische C²-Spline
C2 fordert, dass die zusammengesetzte Funktion <math>S</math> aus allen Einschränkungen (Teilintervallen) <math>s_i</math> zweimal stetig differenzierbar ist. Dafür wird gefordert, dass die erste und zweite Ableitung der Einschränkungen an den Stützstellen
- <math>s'_{i}(x_{i}) := s'_{i-1}(x_{i})</math> und <math>s_{i}(x_{i}) := s_{i-1}(x_{i})</math>
für <math>i = 1, \dotsc, n-1</math> übereinstimmen.
Prinzipiell gilt, dass sich eine Änderung einer Stützstelle <math>(x_i, y_i)</math> stets global auf den gesamten Spline <math>S</math> auswirkt, jedoch wird der Einfluss der Änderung mit zunehmender Distanz zu <math>x_i</math> – anders als bei Interpolationspolynomen – stark gedämpft. Kubische Splines neigen daher weniger zum Überschwingen.
Der kubische C2-Spline erfüllt eine Minimalitätseigenschaft der zweiten Ableitung, was ihn gegenüber anderen Interpolationen besonders interessant macht.
Konstruktion
Es ist ersichtlich, dass die zweite Ableitung von <math>S</math> ein linearer Spline ist. Diese kann daher wie oben beschrieben durch folgende Form beschrieben werden:
- <math>s_i(x) = \frac{x_{i+1} - x}{h_i} \cdot M_i + \frac{x - x_i}{h_i} \cdot M_{i+1}</math> mit <math>h_i = x_{i+1}-x_i</math>
für <math>i = 0, \dotsc, n-1</math>. <math>M_i</math> sind die sogenannten Momente,<ref>Robert Plato: Numerische Mathematik kompakt, 4. Auflage, Seite 27, Bemerkung 2.11</ref> welche den Werten von <math>S(x_i)</math> an den Stützstellen entsprechen und im Folgenden zu berechnen sind. Durch zweifache Integration und geschickte Umformung entstehen aus diesen Gleichungen Polynome dritten Grades mit zwei weiteren Parametern <math>c_i</math> und <math>d_i</math> der Form:
- <math>s_i(x) = \frac{1}{6} \left ( \frac{(x_{i+1} - x)^3}{h_i} \cdot M_i + \frac{(x - x_i)^3}{h_i} \cdot M_{i+1} \right ) + c_i \cdot (x - x_i) + d_i</math> .
Um die Stetigkeitsbedingungen <math>s_i(x_i) = y_i</math> und <math>s_i(x_{i+1}) = y_{i+1}</math> zu erfüllen, wählen wir<ref>Josef Stoer: Numerische Mathematik 1, 9. Auflage, Abschnitt 2.4.2, Seite 109</ref>
- <math>d_i = y_i - \frac{h_i^2}{6} \cdot M_i</math> und <math>c_i = \frac{y_{i+1}-y_i}{h_i} - \frac{h_i}{6} \cdot (M_{i+1} - M_i)</math> .
Mit diesem Ansatz stimmen bereits die nullten und die zweiten Ableitungen der Einschränkungen <math>s_i</math> an den Stützstellen überein. Die Momente sind so zu wählen, dass auch die ersten Ableitungen an den Stützstellen gleich sind. Mit
- <math>s_i'(x) = \frac{1}{2} \left ( - \frac{(x_{i+1}-x)^2}{h_i} \cdot M_i + \frac{(x-x_i)^2}{h_i} \cdot M_{i+1} \right ) + c_i</math> und <math>s_i'(x_i) = s_{i-1}'(x_i)</math>
lassen sich folgende Gleichungen aufstellen:
- <math>\frac{h_{i-1}}{6} \cdot M_{i-1} + \frac{h_{i-1} + h_i}{3} \cdot M_i + \frac{h_i}{6} \cdot M_{i+1} = \frac{y_{i+1} - y_i}{h_i} - \frac{y_i - y_{i-1}}{h_{i-1}}</math> für <math>i = 1, \dots, n-1</math> .
Für <math>i = 0</math> und <math>i = n</math> fehlen hier zwei Gleichungen, welche sich aus den Randbedingungen ergeben.
Dieses lineare Gleichungssystem kann auch durch folgende, tridiagonale, streng diagonaldominante Matrix ausgedrückt werden:
- <math>\begin{bmatrix}
\mu_0 & \lambda_0 & & & & \\ \frac{h_0}{6} & \frac{h_0 + h_1}{3} & \frac{h_1}{6} & & &\\ & \ddots & \ddots & \ddots & & \\ & & \frac{h_{i-1}}{6} & \frac{h_{i-1} + h_i}{3} & \frac{h_i}{6} & \\ & & & \ddots & \ddots & \ddots \\ & & & & \lambda_n & \mu_n \end{bmatrix} \cdot \begin{bmatrix} M_0 \\ M_1 \\ \vdots \\ M_i \\ \vdots \\ M_n \end{bmatrix} = \begin{bmatrix} b_0 \\ \frac{y_2 - y_1}{h_1} - \frac{y_1 - y_0}{h_0} \\ \vdots \\ \frac{y_{i+1} - y_i}{h_i} - \frac{y_i - y_{i-1}}{h_{i-1}} \\ \vdots \\ b_n \end{bmatrix} </math> Die Werte für die <math>\lambda_i, \mu_i, b_i</math> hängen von den Randbedingungen ab.
Zur Lösung kann hier auf den komplizierten Gauss-Algorithmus verzichtet werden und z. B. ein einfacher Vorwärts-Durchlauf zur Elimination der Elemente unter der Hauptdiagonalen mit anschließender Rückwärtssubstitution verwendet werden (Thomas-Algorithmus).
Randbedingungen
Prinzipiell gibt es ein Interpolationsintervall weniger als Stützstellen (Zaunpfahlproblem). Das heißt, dass zwei Gleichungen zur Bestimmung aller Koeffizienten fehlen. Diese ergeben sich aus den Randbedingungen. Typische Randbedingungen sind:
- Natürliche Randbedingungen (auch freier Rand)
- Bedingung: <math>s_0(x_0)=0</math>, <math>s_{n-1}(x_n)=0</math>
- Bedeutung: Der Spline schließt mit Wendepunkten ab.
- Berechnung: <math>\lambda_0 = \lambda_n = b_0 = b_n = 0</math> und <math>\mu_0 = \mu_n = 1</math>
- Hermite Randbedingungen (auch eingespannter Rand)
- Bedingung: <math>s_0'(x_0)=f'(a)</math>, <math>s_{n-1}'(x_n)=f'(b)</math>
- Bedeutung: <math>f'(a)</math> und <math>f'(b)</math> sind vorgegeben, normalerweise entweder durch die Ableitung einer zu interpolierenden Funktion <math>f</math> oder durch eine Approximation derselben.
- Berechnung:
- <math>\begin{matrix}
\lambda_0 = \frac{h_0}{6}, & \mu_0 = \frac{h_0}{3}, & b_0 = \frac{y_1 - y_0}{h_0} - f'(a) \\ \lambda_n = \frac{h_{n-1}}{6}, & \mu_n = \frac{h_{n-1}}{3}, & b_n = - \frac{y_n - y_{n-1}}{h_{n-1}} + f'(b) \end{matrix}</math>
- periodische Randbedingungen
- Bedingung: Intervall <math>[x_0, x_{n+1}]</math>, <math>y_0 =: y_{n+1}</math>, <math>s_0'(x_0) =: s_{n}'(x_{n+1})</math>, <math>s_0(x_0) =: s_{n}(x_{n+1})</math>
- Bedeutung: Nullte, erste und zweite Ableitung von <math>S</math> am Anfang und am Ende des Intervalls sind gleich.
- Berechnung: Es wird eine zusätzliche Stützstelle <math>x_{n+1}</math> eingeführt, welche das Intervall begrenzt. Die Anzahl der Gleichungen zur Berechnung der Momente und die Größe der Matrix bleibt jedoch gleich, da <math>M_{n+1} := M_0</math> bereits gegeben ist, damit die zweiten Ableitungen übereinstimmen. Für die erste und letzte Zeile der Matrix gilt:
- <math>\begin{matrix}
\mu_0 = \frac{h_n + h_0}{3}, & \lambda_0 = \frac{h_0}{6}, & b_0 = \frac{y_1 - y_0}{h_0} - \frac{y_0 - y_n}{h_n} \\ \mu_n = \frac{h_{n-1} + h_n}{3}, & \lambda_n = \frac{h_{n-1}}{6}, & b_n = \frac{y_0 - y_n}{h_n} - \frac{y_n - y_{n-1}}{h_{n-1}} \end{matrix}</math>
- Außerdem sind die Ecken der Matrix abseits der Hauptdiagonalen hier nicht Null:
- <math>m_{0,n} = m_{n,0} = \frac{h_n}{6}</math>
- Die Lösung dieses Systems ist daher komplizierter. Im Falle äquidistanter Stützstellen lässt sich für diesen Fall eine Transformation anwenden.
- not-a-knot Randbedingungen
- Bedingung: <math>s_0(x_1)=s_1(x_1)</math>, <math>s_{n-2}(x_{n-1})=s_{n-1}(x_{n-1})</math>
- Bedeutung: Die äußeren drei Punkte werden je durch ein gemeinsames Polynom interpoliert, was zum Beispiel durch Gleichsetzen der dritten Ableitungen erfolgen kann. Für Splines bis einschließlich vier Stützstellen geht der not-a-knot Spline daher in ein gewöhnliches Interpolationspolynom über. Verwendet wird der not-a-knot-Spline zum Beispiel vom Programm Matlab.
- Berechnung: Es gelte <math>n > 4</math>. Für die Vorwärtssubstitution wird zunächst die Randbedingung an <math>x_0</math> betrachtet. Hierfür können folgende Werte verwendet werden:
- <math>\begin{matrix}
\mu_0 = 1, & \lambda_0 = \frac{h_1 + 2 \cdot h_0}{h_1 - h_0}, & b_0 = \frac{- 6 \cdot h_0}{h_1^2 - h_0^2} \cdot \left ( \frac{y_2 - y_1}{h_1} - \frac{y_1 - y_0}{h_0} \right ). \end{matrix}</math>
- Falls <math>h_1 = h_0</math> entsteht hier eine Division durch Null und es muss eine Grenzwertbildung bis in die dritte Zeile der Matrix (Null ist hier der Index der ersten Zeile/Spalte) erfolgen:
- <math>\begin{matrix}
m_{2,1} = 0, & m_{2,2} = \frac{h_1+h_2}{3}, & m_{2,3} = \frac{h_2}{6}, & b_2 = \frac{y_3-y_2}{h_2} - \frac{y_2-y_1}{h_1} - \frac{y_2 - 2 \cdot y_1 + y_0}{6 \cdot h_0}. \end{matrix}</math>
- Gelöst wird nun lediglich die Untermatrix beginnend bei <math>m_{2,2}</math> und das Randpolynom <math>p = s_0 = s_1</math> auf dem Intervall <math>[x_0, x_2)</math> wird durch eine zusätzliche Polynominterpolation bestimmt, sodass <math>p(x_1) = y_1</math>, <math>p(x_2) = y_2</math>, <math>p'(x_2) = s'_2(x_2)</math>, <math>p(x_2) = s_2(x_2)</math>. <math>p(x_0) = y_0</math> ist dadurch bereits erfüllt.
- Nach dem Vorwärtsdurchlauf zur Elimination der Elemente unter der Diagonalen wird nun die Randbedingung an <math>x_n</math> betrachtet:
- <math>\begin{matrix}
\mu_n = 1, & \lambda_n = 0, & b_n = \frac{(b_{n-1} \cdot m_{n-2,n-1}-b_{n-2} \cdot m_{n-1,n-1}+b_{n-1} \cdot m_{n-2,n-2}) \cdot h_{n-1}+b_{n-1} \cdot m_{n-2,n-2} \cdot h_{n-2}}{(m_{n-2,n-1}+m_{n-2,n-2}) \cdot m_{n-1,n} \cdot h_{n-1}+(m_{n-2,n-2} \cdot m_{n-1,n}+m_{n-2,n-2} \cdot m_{n-1,n-1}) \cdot h_{n-2}}. \end{matrix}</math>
Weitere Randbedingungen sind gebräuchlich, wie etwa integrale Randbedingungen<ref>Lebesgue und Birkhoff: Handbook of Splines, Abschnitt 1.9, Seite 56</ref> oder die im Folgenden vorgestellte, symmetrische Verlängerung.
Optimierung des Rechenaufwands
Bei äquidistanten Stützstellen mit konstantem Abstand <math>h</math> vereinfacht sich das Gleichungssystem zu
- <math>M_{i-1} + 4 \cdot M_i + M_{i+1} = 6 \frac{y_{i+1} - 2 \cdot y_i + y_{i-1}}{h^2}</math> für <math>i=1,\dots,n-1</math>.
Mit der symmetrischen Verlängerung <math>\mu_0 = \mu_n = 4</math> und <math>\lambda_0 = \lambda_n = 1</math> entsteht daraus eine sogenannte Tridiagonal-Toeplitz-Matrix, welche besonders effizient, auch parallel gelöst werden kann. Für die rechte Seite kann hier <math>b_0 = \tfrac{y_1}{2 \cdot h}</math> und <math>b_n = - \tfrac{y_{n-1}}{2 \cdot h}</math> angesetzt werden. Mit <math>A = \tfrac{6}{h} \cdot M</math> lässt sich schreiben:
- <math>A := \begin{bmatrix}
4 & 1 & 0 & \cdots & 0 & 0 & 0\\ 1 & 4 & 1 & \cdots & 0 & 0 & 0\\ 0 & 1 & 4 & \cdots & 0 & 0 & 0\\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots & \vdots\\ 0 & 0 & 0 & \cdots & 4 & 1 & 0\\ 0 & 0 & 0 & \cdots & 1 & 4 & 1\\ 0 & 0 & 0 & \cdots & 0 & 1 & 4\\ \end{bmatrix} \in \R^{(n+1)\times (n+1)}</math> Diese hat die Inverse
- <math>B := b_{n+1}^{-1}\begin{bmatrix}
b_nb_0 & -b_{n-1}b_0 & \cdots & (-1)^{n-1}b_1b_0 & (-1)^nb_0b_0\\ -b_{n-1}b_0 & b_{n-1}b_1 & \cdots & (-1)^nb_1b_1 & (-1)^{n-1}b_0b_1\\ \vdots & \vdots & \ddots & \vdots & \vdots\\ (-1)^{n-1}b_1b_0 & (-1)^nb_1b_1 & \cdots & b_1b_{n-1} & -b_0b_{n-1}\\ (-1)^nb_0b_0 & (-1)^{n-1}b_0b_1 & \cdots & -b_0b_{n-1} & b_0b_n\\ \end{bmatrix}</math> mit Koeffizienten <math>b_i</math>, die den Gleichungen <math>b_0:=1</math>, <math>b_1:=4</math>, der Rekursion <math>b_i:=4b_{i-1}-b_{i-2}</math> und explizit der Formel
- <math>b_i=(\sqrt{3}(2+\sqrt{3})^{i+1}-\sqrt{3}(2-\sqrt{3})^{i+1})/6</math>
genügen.
Minimalitätseigenschaft der zweiten Ableitung
Unter allen zweimal stetig differenzierbaren Funktionen, die alle Stützstellen innerhalb eines Intervalls <math>[a, b]</math> miteinander verbinden, hat unter Verwendung natürlicher, periodischer oder Hermite-Randbedingungen der kubische Spline die geringste Krümmung: <math>\int_a^b f(x)^2 \mathrm{d}x \ge \int_a^b S(x)^2 \mathrm{d}x</math>, wobei <math>f</math> hier eine beliebige Funktion auf <math>[a, b]</math> aus C2 ist, die alle Stützstellen schneidet. Anschaulich folgt daraus, dass ein zu volles Glas Wasser, das während einer Zugfahrt auf dem Tisch steht, „am wenigsten überschwappt“, wenn der Streckenzug der Schienenführung mithilfe kubischer Splines parametrisiert wurde.
Diese sogenannte Identität von Holladay wurde im Jahr 1957 von Holladay<ref>{{#if:|{{#iferror: {{#iferror:{{#invoke:Vorlage:FormatDate|Execute}}|}}| |}}}}{{#if:Takeo Akasaki, William F. Donoghue Jr., George S. McCarty|Takeo Akasaki, William F. Donoghue Jr., George S. McCarty: }}{{#if:|{{#if:John C. Holladay, 1928–1986|[{{#invoke:Vorlage:Internetquelle|archivURL|1={{#invoke:URLutil|getNormalized|1={{{archiv-url}}}}}}} {{#invoke:Vorlage:Internetquelle|TitelFormat|titel=John C. Holladay, 1928–1986}}]{{#if:| ({{{format}}})}}{{#if:In Memoriam| In Memoriam{{#invoke:Vorlage:Internetquelle|Endpunkt|titel=In Memoriam}}}}}}|{{#if:http://texts.cdlib.org/view?docId=hb767nb3z6&doc.view=frames&chunk.id=div00051&toc.depth=1&toc.id=%7C{{#if:{{#invoke:TemplUtl%7Cfaculty%7C}}%7C{{#invoke:Vorlage:Internetquelle%7CTitelFormat%7Ctitel={{#invoke:WLink%7CgetEscapedTitle%7C1=John C. Holladay, 1928–1986}}}}|[{{#invoke:URLutil|getNormalized|1=http://texts.cdlib.org/view?docId=hb767nb3z6&doc.view=frames&chunk.id=div00051&toc.depth=1&toc.id=}} {{#invoke:Vorlage:Internetquelle|TitelFormat|titel={{#invoke:WLink|getEscapedTitle|1=John C. Holladay, 1928–1986}}}}]}}{{#if:| ({{{format}}}{{#if:In MemoriamUniversity of California1986{{#if: 2021-01-22 | {{#if:{{#invoke:TemplUtl|faculty|}}||1}}}}
| )
| {{#if:{{#ifeq:de|de||{{#if:|1}}}}| ;
| )}}}}}}{{#if:In Memoriam| In Memoriam{{#invoke:Vorlage:Internetquelle|Endpunkt|titel=In Memoriam}}}}}}}}{{#if:http://texts.cdlib.org/view?docId=hb767nb3z6&doc.view=frames&chunk.id=div00051&toc.depth=1&toc.id=%7C{{#if:{{#invoke:URLutil%7CisResourceURL%7C1=http://texts.cdlib.org/view?docId=hb767nb3z6&doc.view=frames&chunk.id=div00051&toc.depth=1&toc.id=}}%7C%7C}}}}{{#if:John C. Holladay, 1928–1986|{{#if:{{#invoke:WLink|isValidLinktext|1=John C. Holladay, 1928–1986|lines=0}}||}}}}{{#if: | In: {{#invoke:Vorlage:Internetquelle|TitelFormat|titel={{{werk}}}}}}}{{#if: University of California| University of California{{#if: 1986|,|{{#if: 2021-01-22 | {{#if:{{#invoke:TemplUtl|faculty|}}||,}}}}}}}}{{#if: 1986| {{#if:{{#invoke:DateTime|format|1986|noerror=1}}
|{{#invoke:DateTime|format|1986|T._Monat JJJJ}}
|{{#invoke:TemplUtl|failure|1=Fehler bei Vorlage:Internetquelle, datum=1986|class=Zitationswartung}} }}{{#if: |,|{{#if: 2021-01-22 | {{#if:{{#invoke:TemplUtl|faculty|}}||,}}}}}}}}{{#if: | S. {{{seiten}}}{{#if: |,|{{#if: 2021-01-22 | {{#if:{{#invoke:TemplUtl|faculty|}}||,}}}}}}}}{{#if: {{#invoke:TemplUtl|faculty|}}| {{#if:1986University of California|{{#if:|archiviert|ehemals}}|{{#if:|Archiviert|Ehemals}}}} {{#if:|vom|im}} Vorlage:Referrer{{#if:{{#invoke:TemplUtl|faculty|}}| (nicht mehr online verfügbar)}}{{#if: | am {{#iferror: {{#iferror:{{#invoke:Vorlage:FormatDate|Execute}}|}}|{{{archiv-datum}}}{{#if:120528||(?)}}}}}}{{#if: 2021-01-22|;}}}}{{#if: 2021-01-22| {{#if:1986University of California{{#invoke:TemplUtl|faculty|}}|abgerufen|Abgerufen}} {{#switch: {{#invoke:Str|len| {{#invoke:DateTime|format| 2021-01-22 |ISO|noerror=1}} }}
|4=im Jahr
|7=im
|10=am
|#default={{#invoke:TemplUtl|failure|1=Fehler bei Vorlage:Internetquelle, abruf=2021-01-22|class=Zitationswartung}} }} {{#invoke:DateTime|format|2021-01-22|T._Monat JJJJ}}
| {{#invoke:TemplUtl|failure|1=Vorlage:Internetquelle | abruf=2026-MM-TT ist Pflichtparameter}} }}{{#if:{{#ifeq:de|de||{{#if:|1}}}}|{{#if:In MemoriamUniversity of California1986{{#if: 2021-01-22 | {{#if:{{#invoke:TemplUtl|faculty|}}||1}}}}
| (
| {{#if: | | (}}
}}{{#ifeq:{{#if:de|de|de}}|de||
{{#invoke:Multilingual|format|{{{sprache}}}|slang=!|split=[%s,]+|shift=m|separator=, }}}}{{#if: |{{#ifeq:{{#if:de|de|de}}|de||, }}{{{kommentar}}}}})}}{{#if: 1986{{#if: 2021-01-22 | {{#if:{{#invoke:TemplUtl|faculty|}}||1}} }}|{{#if: |: {{
#if:
| „{{
#ifeq: {{#if:{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|de}} | de
| Vorlage:Str trim
| {{#invoke:Vorlage:lang|flat}}
}}“
| {{#ifeq: {{#if:{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|de}} | de
| „Vorlage:Str trim“
| {{#invoke:Text|quote
|1={{#if:
| {{#invoke:Vorlage:lang|flat}}
| {{#invoke:Vorlage:lang|flat}} }}
|2={{#if: {{#invoke:TemplUtl|faculty|}}|de-CH|de}}
|3=1}} }}
}}{{#if:
| (<templatestyles src="Person/styles.css" />{{#if: | : }}{{#if: | , deutsch: „“ }})
| {{#if:
| ({{#if: | , deutsch: „“ }})
| {{#if: | (deutsch: „“) }}
}}
}}{{#if: {{{zitat}}}
| {{#if:
| {{#if: {{{zitat}}}
| Vorlage:": Text= und 1= gleichzeitig, bzw. Pipe zu viel }} }}
| Vorlage:": Text= fehlt }}{{#if: | {{#if: {{#invoke:Text|unstrip|{{{ref}}}}}
| Vorlage:": Ungültiger Wert: ref=
| {{{ref}}} }}
}}|.{{#if:{{#invoke:TemplUtl|faculty|}}|{{#if:||{{#ifeq: | JaKeinHinweis |{{#switch:
|0|=Vorlage:Toter Link/Core{{#if: http://texts.cdlib.org/view?docId=hb767nb3z6&doc.view=frames&chunk.id=div00051&toc.depth=1&toc.id= | {{#if: | [1] }} (Seite {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar{{#if: | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. Suche im Internet Archive ){{#if: | {{#if: deadurlausgeblendet | | Vorlage:Toter Link/archivebot }} }} | (Seite {{#switch:|no|0|=|#default=dauerhaft }}nicht mehr abrufbar{{#if: | , festgestellt im {{#invoke:DateTime|format||F Y}} }}.) }}{{#switch: |no|0|= |#default={{#if: || }} }}{{#invoke:TemplatePar|check |opt = inline= url= text= datum= date= archivebot= bot= botlauf= fix-attempted= checked= |cat = Wikipedia:Vorlagenfehler/Vorlage:Toter Link |errNS = 0 |template = Vorlage:Toter Link |format = |preview = 1 }}{{#if: http://texts.cdlib.org/view?docId=hb767nb3z6&doc.view=frames&chunk.id=div00051&toc.depth=1&toc.id= | {{#if:{{#invoke:URLutil|isWebURL|http://texts.cdlib.org/view?docId=hb767nb3z6&doc.view=frames&chunk.id=div00051&toc.depth=1&toc.id=}} || {{#if: || }} }} | {{#if: | {{#if: || }} | {{#if: || }} }} }}{{#if: | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}} || {{#if: || }} }} }}{{#switch: deadurl |checked|deadurl|= |#default= {{#if: || }} }}|#default= https://wiki-de.moshellshocker.dns64.de/index.php?title=Wikipedia:Defekte_Weblinks&dwl=http://texts.cdlib.org/view?docId=hb767nb3z6&doc.view=frames&chunk.id=div00051&toc.depth=1&toc.id= Die nachstehende Seite ist {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar]{{#if: | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. (Suche im Internet Archive. ) {{#if: | {{#if: deadurlausgeblendet | | Vorlage:Toter Link/archivebot }} }}Vorlage:Toter Link/Core{{#switch: |no|0|= |#default= {{#if: || }} }}{{#invoke:TemplatePar|check |all = inline= url= |opt = datum= date= archivebot= bot= botlauf= fix-attempted= checked= |cat = Wikipedia:Vorlagenfehler/Vorlage:Toter Link |errNS = 0 |template = Vorlage:Toter Link |format = |preview = 1 }}{{#if: http://texts.cdlib.org/view?docId=hb767nb3z6&doc.view=frames&chunk.id=div00051&toc.depth=1&toc.id= | {{#if:{{#invoke:URLutil|isWebURL|http://texts.cdlib.org/view?docId=hb767nb3z6&doc.view=frames&chunk.id=div00051&toc.depth=1&toc.id=}} || {{#if: || }} }} }}{{#if: | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}} || {{#if: || }} }} }}{{#switch: deadurl |checked|deadurl|= |#default= {{#if: || }} }}[http://texts.cdlib.org/view?docId=hb767nb3z6&doc.view=frames&chunk.id=div00051&toc.depth=1&toc.id= }}|{{#switch: |0|=Vorlage:Toter Link/Core{{#if: http://texts.cdlib.org/view?docId=hb767nb3z6&doc.view=frames&chunk.id=div00051&toc.depth=1&toc.id= | {{#if: | [2] }} (Seite {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar{{#if: | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. Suche im Internet Archive ){{#if: | {{#if: | | Vorlage:Toter Link/archivebot }} }} | (Seite {{#switch:|no|0|=|#default=dauerhaft }}nicht mehr abrufbar{{#if: | , festgestellt im {{#invoke:DateTime|format||F Y}} }}.) }}{{#switch: |no|0|= |#default={{#if: || }} }}{{#invoke:TemplatePar|check |opt = inline= url= text= datum= date= archivebot= bot= botlauf= fix-attempted= checked= |cat = Wikipedia:Vorlagenfehler/Vorlage:Toter Link |errNS = 0 |template = Vorlage:Toter Link |format = |preview = 1 }}{{#if: http://texts.cdlib.org/view?docId=hb767nb3z6&doc.view=frames&chunk.id=div00051&toc.depth=1&toc.id= | {{#if:{{#invoke:URLutil|isWebURL|http://texts.cdlib.org/view?docId=hb767nb3z6&doc.view=frames&chunk.id=div00051&toc.depth=1&toc.id=}} || {{#if: || }} }} | {{#if: | {{#if: || }} | {{#if: || }} }} }}{{#if: | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}} || {{#if: || }} }} }}{{#switch: |checked|deadurl|= |#default= {{#if: || }} }}|#default= https://wiki-de.moshellshocker.dns64.de/index.php?title=Wikipedia:Defekte_Weblinks&dwl=http://texts.cdlib.org/view?docId=hb767nb3z6&doc.view=frames&chunk.id=div00051&toc.depth=1&toc.id= Die nachstehende Seite ist {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar]{{#if: | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. (Suche im Internet Archive. ) {{#if: | {{#if: | | Vorlage:Toter Link/archivebot }} }}Vorlage:Toter Link/Core{{#switch: |no|0|= |#default= {{#if: || }} }}{{#invoke:TemplatePar|check |all = inline= url= |opt = datum= date= archivebot= bot= botlauf= fix-attempted= checked= |cat = Wikipedia:Vorlagenfehler/Vorlage:Toter Link |errNS = 0 |template = Vorlage:Toter Link |format = |preview = 1 }}{{#if: http://texts.cdlib.org/view?docId=hb767nb3z6&doc.view=frames&chunk.id=div00051&toc.depth=1&toc.id= | {{#if:{{#invoke:URLutil|isWebURL|http://texts.cdlib.org/view?docId=hb767nb3z6&doc.view=frames&chunk.id=div00051&toc.depth=1&toc.id=}} || {{#if: || }} }} }}{{#if: | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}} || {{#if: || }} }} }}{{#switch: |checked|deadurl|= |#default= {{#if: || }} }}[http://texts.cdlib.org/view?docId=hb767nb3z6&doc.view=frames&chunk.id=div00051&toc.depth=1&toc.id= }} }}}}}}}}}}{{#if:| {{#invoke:Vorlage:Internetquelle|archivBot|stamp={{{archiv-bot}}}|text={{#if:|Vorlage:Webarchiv/archiv-bot}}
}}}}{{#invoke:TemplatePar|check |all= url= titel= |opt= autor= hrsg= format= sprache= titelerg= werk= seiten= datum= abruf= zugriff= abruf-verborgen= archiv-url= archiv-datum= archiv-bot= kommentar= zitat= AT= CH= offline= |cat= {{#ifeq: 0 | 0 | Wikipedia:Vorlagenfehler/Vorlage:Internetquelle}} |template= Vorlage:Internetquelle |format=0 |preview=1 }}</ref> bewiesen. Sei mit <math>C^2([a,b])</math> der Raum der zweimal differenzierbaren Funktionen bezeichnet, für welche die nullte und erste Ableitung absolutstetig sind und die zweite Ableitung in <math>L^2([a,b])</math> liegt. Sei nun <math>S</math> eine interpolierende Splinefunktion zu einer beliebigen Funktion <math>f \in C^2([a,b])</math> und <math>\|.\|</math> die <math>L^2</math>-Norm, so gilt: <math> \|f - S\|^2 = \| f \|^2 - \|S\|^2 - 2 D</math> mit <math>D := \left. (f'(x) - S'(x))S(x) \right|_a^b - \sum_{i=1}^n \left. (f(x) - S(x)) S' \right|_{x_{i-1}}^{x_i}</math>.
Erfüllt die Splinefunktion die natürlichen, periodischen oder vollständigen Randbedingungen, so ist <math>D = 0 </math>, also: <math> \|f - S\|^2 = \|f\|^2 - \|S\|^2 \geq 0 \Rightarrow \|f\|^2 \geq \|S \|^2.</math>
Damit gilt nun: <math>\|f - S\|^2 = \min_{T \in C^2}\|f - T\|^2.</math>
Hieraus folgt auch die Eindeutigkeit der Splineinterpolation für gegebene Randbedingungen.<ref name=":0" /> Insbesondere hat das lineare Gleichungssystem oben dadurch eine eindeutige Lösung.
Konvergenz
Kubische Splines und zumindest die ersten beiden Ableitungen konvergieren für <math>h := \max_{i = 0, \dots, n-1} h_i \rightarrow 0</math>. Die Konvergenzordnung bzgl. <math>h</math> hängt sowohl von der gewählten Norm, als auch der Differenzierbarkeit von <math>f</math> ab. Man erhält folgende Fehlerschätzungen<ref name=":0" />
- <math>\begin{align}
||f-s||_{L_\infty([a, b])} &\le \sqrt{2} h^{3/2} ||f||_{L_2([a, b])}, \quad ||f-s||_{L_2([a, b])} &\le 2 h^{2} ||f||_{L_2([a, b])} \\ ||f-s||_{L_\infty([a, b])} &\le \sqrt{8} h^{7/2} ||f'||_{L_2([a, b])}, \quad ||f-s||_{L_2([a, b])} &\le 4 h^{4} ||f'||_{L_2([a, b])} \\ ||f-s||_{L_\infty([a, b])} &\le h^{4} ||f'||_{L_\infty([a, b])}, &\\ ||f'-s'||_{L_\infty([a, b])} &\le \sqrt{2} h^{1/2} ||f||_{L_2([a, b])}, \quad ||f'-s'||_{L_2([a, b])} &\le 2 h^{2} ||f||_{L_2([a, b])} \\ ||f'-s'||_{L_\infty([a, b])} &\le \sqrt{8} h^{5/2} ||f'||_{L_2([a, b])}, \quad ||f'-s'||_{L_2([a, b])} &\le 4 h^{3} ||f'||_{L_2([a, b])} \\ ||f-s||_{L_\infty([a, b])} &\le \frac{h^2}{2}||f'||_{L_\infty([a, b])} \\ \end{align}</math>
bzgl. der Normen <math>||f||_{L_\infty([a, b])} = \max_{x\in [a, b]} |f(x)|</math> und <math>||f||^{2}_{L_2([a, b])} = \int_{a}^{b} f(x)^{2} \,\mathrm{d}x</math>. Höhere Differenzierbarkeit von <math>f</math> erhöht also die Konvergenzrate der Splines. Für <math>f \in C^{3}([a, b])</math> erhält man analoge Formeln.
Bikubischer C2-Spline
Der bikubische C2-Spline ist die Verallgemeinerung des einfachen, kubischen C2-Splines auf zwei Dimensionen, man spricht hierbei auch von multivariater Interpolation. Dafür müssen die zu interpolierenden Punkte zij in einem rechteckigen Gitter angeordnet sein.<ref>Lebesgue und Birkhoff: Handbook of Splines, Abschnitt 2.2, Seite 82</ref> Jede zwischen vier Punkten aufgespannte Fläche Aij wird durch ein zweidimensionales Polynom von 16 Koeffizienten charakterisiert:
- <math>z := A_{ij}(x, y) = \sum_{k=0}^{3}\sum_{l=0}^{3}a^{ij}_{k,l} \cdot x^k \cdot y^l = \begin{matrix}
a^{ij}_{0,0} & + & a^{ij}_{1,0} \cdot x & + & a^{ij}_{2,0} \cdot x^2 & + & a^{ij}_{3,0} \cdot x^3 & + \\
a^{ij}_{0,1} \cdot y & + & a^{ij}_{1,1} \cdot x \cdot y & + & a^{ij}_{2,1} \cdot x^2 \cdot y & + & a^{ij}_{3,1} \cdot x^3 \cdot y & + \\
a^{ij}_{0,2} \cdot y^2 & + & a^{ij}_{1,2} \cdot x \cdot y^2 & + & a^{ij}_{2,2} \cdot x^2 \cdot y^2 & + & a^{ij}_{3,2} \cdot x^3 \cdot y^2 & + \\
a^{ij}_{0,3} \cdot y^3 & + & a^{ij}_{1,3} \cdot x \cdot y^3 & + & a^{ij}_{2,3} \cdot x^2 \cdot y^3 & + & a^{ij}_{3,3} \cdot x^3 \cdot y^3 & ~
\end{matrix}</math>
Für einen zweidimensionalen C2-Spline müssen die Koeffizienten so gewählt werden, dass die aus allen Flächen zusammengesetzte Funktion <math>S(x, y): \mathbb{R}^2 \rarr \mathbb{R}</math> zweimal stetig in x- und y-Richtung differenzierbar ist. Das heißt, neben S selbst sind die folgenden Ableitungen stetig auf ganz <math>\mathbb{R}^2</math>:
- <math>\begin{matrix}
\frac{\partial S(x, y)}{\partial x}, & \frac{\partial S(x, y)}{\partial y}, & \frac{\partial^2 S(x, y)}{\partial x^2}, & \frac{\partial^2 S(x, y)}{\partial y^2}, & \frac{\partial^2 S(x, y)}{\partial x \partial y}, & \frac{\partial^3 S(x, y)}{\partial x^2 \partial y}, & \frac{\partial^3 S(x, y)}{\partial x \partial y^2}, & \frac{\partial^4 S(x, y)}{\partial x^2 \partial y^2} \end{matrix}</math>
Konstruktion
{{#invoke:Vorlage:Anker|f |errCat=Wikipedia:Vorlagenfehler/Vorlage:Anker |errHide=1}}
Es ist ersichtlich, dass jeder Schnitt durch eine Teilfläche <math>A_{i,j}</math> parallel zur <math>x</math>- oder <math>y</math>-Achse eine eindimensionale Kurve liefert, welche durch ein kubisches Polynom von vier Koeffizienten beschrieben werden kann. Daraus folgt, dass die vier Ränder jeder Teilfläche solche Polynome sind. Um die geforderte zweifach stetige Differenzierbarkeit zu erhalten, können zunächst alle Punkte entlang der Gitterlinien eindimensional interpoliert werden. Der bikubische Spline erbt dabei die verwendeten Randbedingungen der eindimensionalen Splines.
Nun stehen zu jedem zweidimensionalen Polynom <math>A_{i,j}</math> mit 16 Koeffizienten vier eindimensionale Randpolynome <math>s_{x~i,j}</math>, <math>s_{x~i,j+1}</math>, <math>s_{y~i,j}</math>, <math>s_{y~i+1,j}</math> mit je 4 Koeffizienten zur Verfügung. Hierbei kennzeichnet der erste Index der s, zu welcher Achse sie parallel verlaufen.
Um diese Randpolynome zu <math>A_{i,j}</math> „zusammenzurechnen“ ist ein System von 16 linearen Gleichungen aufzustellen. Vier Gleichungen ergeben sich aus der Forderung, dass S an den Gitterpunkten genau die Werte <math>z_{i,j}</math> annimmt:
- <math>\begin{matrix}
A_{i,j}(x_i, y_j) = z_{i,j}, & A_{i,j}(x_{i+1}, y_j) = z_{i+1,j}, & A_{i,j}(x_i, y_{j+1}) = z_{i,j+1}, & A_{i,j}(x_{i+1}, y_{j+1}) = z_{i+1,j+1} \end{matrix}</math> Weitere vier Gleichungen ergeben sich aus der Ableitung der zur <math>x</math>-Achse parallelen Randpolynome nach <math>x</math>:
- <math>\begin{matrix}
\frac{\partial A_{i,j}(x_i, y_j)}{\partial x} = \frac{\partial s_{x~i,j}(x_i)}{\partial x}, & \frac{\partial A_{i,j}(x_{i+1}, y_j)}{\partial x} = \frac{\partial s_{x~i,j}(x_{i+1})}{\partial x}, & \frac{\partial A_{i,j}(x_i, y_{j+1})}{\partial x} = \frac{\partial s_{x~i,j+1}(x_i)}{\partial x}, & \frac{\partial A_{i,j}(x_{i+1}, y_{j+1})}{\partial x} = \frac{\partial s_{x~i,j+1}(x_{i+1})}{\partial x} \end{matrix}</math> Weitere vier Gleichungen aus der Ableitung der zur <math>y</math>-Achse parallelen Randpolynome nach <math>y</math>:
- <math>\begin{matrix}
\frac{\partial A_{i,j}(x_i, y_j)}{\partial y} = \frac{\partial s_{y~i,j}(y_j)}{\partial y}, & \frac{\partial A_{i,j}(x_{i+1}, y_j)}{\partial y} = \frac{\partial s_{y~i+1,j}(y_j)}{\partial y}, & \frac{\partial A_{i,j}(x_i, y_{j+1})}{\partial y} = \frac{\partial s_{y~i,j}(y_{j+1})}{\partial y}, & \frac{\partial A_{i,j}(x_{i+1}, y_{j+1})}{\partial y} = \frac{\partial s_{y~i+1,j}(y_{j+1})}{\partial y} \end{matrix}</math> Nun ergibt sich das Problem, dass entlang jedem der vier Ränder zwei Punkte und zwei Ableitungen gegeben sind. Damit ist ein Polynom von Grad 3 entlang des jeweiligen Randes eigentlich vollständig spezifiziert. Das hinzunehmen z. B. der zweiten Ableitungen an den Eckpunkten oder weiterer Funktionswerte entlang der Randpolynome würde eine lineare Abhängigkeit im Gleichungssystem erzeugen. Mit den gegebenen Gleichungen lassen sich jedoch nur 12 der 16 Koeffizienten bestimmen. Ein nicht linear abhängiges System ergibt sich durch Hinzunahme der gemischten Ableitungen nach x und y. Setzt man diese in den Eckpunkten etwa auf null, so ist <math>S</math> nur in den Eckpunkten zweimal stetig differenzierbar. Entlang der Ränder ergeben sich in den zweiten Ableitungen jedoch Sprünge. Aus den Randpolynomen lassen sich die gemischten Ableitungen jedoch nicht direkt berechnen.
Um nun korrekte Werte für diese gemischten Ableitungen zu erhalten, welche auch entlang der Ränder stetige, zweite Ableitungen von <math>S</math> liefern, kann wie folgt vorgegangen werden:
- Entlang der Gitterlinien, welche parallel zur <math>x</math>-Achse verlaufen, werden weitere, eindimensionale Splines <math>s_d</math> gebildet
- Diese interpolieren statt der <math>z</math>-Werte die Ableitungen von <math>s_y</math> an deren Schnittpunkten mit den <math>x</math>-Gitterlinien
- Die <math>s_d</math>-Splines können nun nach <math>x</math> abgeleitet werden. Daraus ergeben sich die gemischten Ableitungen
- <math>\begin{matrix}
\frac{\partial^2 A_{i,j}(x_i, y_j)}{\partial x \partial y} = \frac{\partial s_{d~i,j}(x_i)}{\partial x}, & \frac{\partial^2 A_{i,j}(x_{i+1}, y_j)}{\partial x \partial y} = \frac{\partial s_{d~i,j}(x_{i+1})}{\partial x}, & \frac{\partial^2 A_{i,j}(x_i, y_{j+1})}{\partial x \partial y} = \frac{\partial s_{d~i,j+1}(x_i)}{\partial x}, & \frac{\partial^2 A_{i,j}(x_{i+1}, y_{j+1})}{\partial x \partial y} = \frac{\partial s_{d~i,j+1}(x_{i+1})}{\partial x} \end{matrix}</math>
Wie beim eindimensionalen C2-Spline wirkt sich auch beim bikubischen Spline eine Änderung in einer Stützstelle (Datenpunkt) generell auf alle Teilflächen aus. Dies veranschaulicht, warum eine Konstruktion alleine aus den Randpolynomen <math>s_x</math> und <math>s_y</math> fehlschlägt: Diese ändern sich nur, wenn ein Datenwert, welcher parallel (in <math>x</math>- oder <math>y</math>-Richtung) zur betrachteten Teilfläche liegt, geändert wird. In der Abbildung rechts hat eine Änderung von <math>z_{3,0}</math> keinen Einfluss auf die 1D-Splines, welche den Rand von <math>A_{1,1}</math> bilden. Erst die erneute Interpolation durch <math>s_d</math> erzeugt eine Abhängigkeit zwischen diesem Punkt und der Fläche.
Beispiel
Beispiel für bikubische Interpolation:<ref>Die Beispielinterpolation wurde erstellt mit: Programm Numeric Collection von Mitja Stachowiak</ref> Ein Datenblock aus 6x6 Werten (links) wird bikubisch interpoliert (Mitte). Dabei wurden natürliche Randbedingungen angenommen (die zweite Ableitung auf den Randpunkten ist null). Die Farben zwischen linkem und mittlerem Bild wurden synchronisiert und beschreiben die Funktionswerte ähnlich der Farben auf einer Landkarte zur Illustration der Höhe. Um die Korrektheit der Interpolation zu verdeutlichen, wird rechts die zweite Ableitung <math>\frac{\partial^4 S}{\partial x^2 \partial y^2}</math> gezeigt. Diese besteht aus linearen Funktionen und ist immer noch stetig.
Splines höherer Ordnung
Analog zu linearen und kubische Splines lassen sich auch Splines höherer Ordnung mit stückweise Polynomen mit Grad <math>p > 3</math> definieren, auch wenn diese praktisch oft von untergeordnetem Interesse sind. Um die Symmetrie der Randbedingungen zu gewährleisten, beschränkt man sich hierbei auf ungerade Werte für <math>p</math><ref name=":1">{{#if:|{{#iferror: {{#iferror:{{#invoke:Vorlage:FormatDate|Execute}}|}}| |}}}}{{#if:|{{{autor}}}: }}{{#if:|{{#if:LP – Räume von Spline-Funktionen|[{{#invoke:Vorlage:Internetquelle|archivURL|1={{#invoke:URLutil|getNormalized|1={{{archiv-url}}}}}}} {{#invoke:Vorlage:Internetquelle|TitelFormat|titel=LP – Räume von Spline-Funktionen}}]{{#if:| ({{{format}}})}}{{#if:| {{{titelerg}}}{{#invoke:Vorlage:Internetquelle|Endpunkt|titel={{{titelerg}}}}}}}}}|{{#if:https://lp.uni-goettingen.de/get/text/1234%7C{{#if:{{#invoke:TemplUtl%7Cfaculty%7C}}%7C{{#invoke:Vorlage:Internetquelle%7CTitelFormat%7Ctitel={{#invoke:WLink%7CgetEscapedTitle%7C1=LP – Räume von Spline-Funktionen}}}}|[{{#invoke:URLutil|getNormalized|1=https://lp.uni-goettingen.de/get/text/1234}} {{#invoke:Vorlage:Internetquelle|TitelFormat|titel={{#invoke:WLink|getEscapedTitle|1=LP – Räume von Spline-Funktionen}}}}]}}{{#if:| ({{{format}}}{{#if:{{#if: 2025-10-25 | {{#if:{{#invoke:TemplUtl|faculty|}}||1}}}}
| )
| {{#if:{{#ifeq:de|de||{{#if:|1}}}}| ;
| )}}}}}}{{#if:| {{{titelerg}}}{{#invoke:Vorlage:Internetquelle|Endpunkt|titel={{{titelerg}}}}}}}}}}}{{#if:https://lp.uni-goettingen.de/get/text/1234%7C{{#if:{{#invoke:URLutil%7CisResourceURL%7C1=https://lp.uni-goettingen.de/get/text/1234}}%7C%7C}}}}{{#if:LP – Räume von Spline-Funktionen|{{#if:{{#invoke:WLink|isValidLinktext|1=LP – Räume von Spline-Funktionen|lines=0}}||}}}}{{#if: | In: {{#invoke:Vorlage:Internetquelle|TitelFormat|titel={{{werk}}}}}}}{{#if: | {{{hrsg}}}{{#if: |,|{{#if: 2025-10-25 | {{#if:{{#invoke:TemplUtl|faculty|}}||,}}}}}}}}{{#if: | {{#if:{{#invoke:DateTime|format|{{{datum}}}|noerror=1}}
|{{#invoke:DateTime|format|{{{datum}}}|T._Monat JJJJ}}
|{{#invoke:TemplUtl|failure|1=Fehler bei Vorlage:Internetquelle, datum={{{datum}}}|class=Zitationswartung}} }}{{#if: |,|{{#if: 2025-10-25 | {{#if:{{#invoke:TemplUtl|faculty|}}||,}}}}}}}}{{#if: | S. {{{seiten}}}{{#if: |,|{{#if: 2025-10-25 | {{#if:{{#invoke:TemplUtl|faculty|}}||,}}}}}}}}{{#if: {{#invoke:TemplUtl|faculty|}}| {{#if:|{{#if:|archiviert|ehemals}}|{{#if:|Archiviert|Ehemals}}}} {{#if:|vom|im}} Vorlage:Referrer{{#if:{{#invoke:TemplUtl|faculty|}}| (nicht mehr online verfügbar)}}{{#if: | am {{#iferror: {{#iferror:{{#invoke:Vorlage:FormatDate|Execute}}|}}|{{{archiv-datum}}}{{#if:120528||(?)}}}}}}{{#if: 2025-10-25|;}}}}{{#if: 2025-10-25| {{#if:{{#invoke:TemplUtl|faculty|}}|abgerufen|Abgerufen}} {{#switch: {{#invoke:Str|len| {{#invoke:DateTime|format| 2025-10-25 |ISO|noerror=1}} }}
|4=im Jahr
|7=im
|10=am
|#default={{#invoke:TemplUtl|failure|1=Fehler bei Vorlage:Internetquelle, abruf=2025-10-25|class=Zitationswartung}} }} {{#invoke:DateTime|format|2025-10-25|T._Monat JJJJ}}
| {{#invoke:TemplUtl|failure|1=Vorlage:Internetquelle | abruf=2026-MM-TT ist Pflichtparameter}} }}{{#if:{{#ifeq:de|de||{{#if:|1}}}}|{{#if:{{#if: 2025-10-25 | {{#if:{{#invoke:TemplUtl|faculty|}}||1}}}}
| (
| {{#if: | | (}}
}}{{#ifeq:{{#if:de|de|de}}|de||
{{#invoke:Multilingual|format|{{{sprache}}}|slang=!|split=[%s,]+|shift=m|separator=, }}}}{{#if: |{{#ifeq:{{#if:de|de|de}}|de||, }}{{{kommentar}}}}})}}{{#if: {{#if: 2025-10-25 | {{#if:{{#invoke:TemplUtl|faculty|}}||1}} }}|{{#if: |: {{
#if:
| „{{
#ifeq: {{#if:{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|de}} | de
| Vorlage:Str trim
| {{#invoke:Vorlage:lang|flat}}
}}“
| {{#ifeq: {{#if:{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|de}} | de
| „Vorlage:Str trim“
| {{#invoke:Text|quote
|1={{#if:
| {{#invoke:Vorlage:lang|flat}}
| {{#invoke:Vorlage:lang|flat}} }}
|2={{#if: {{#invoke:TemplUtl|faculty|}}|de-CH|de}}
|3=1}} }}
}}{{#if:
| (<templatestyles src="Person/styles.css" />{{#if: | : }}{{#if: | , deutsch: „“ }})
| {{#if:
| ({{#if: | , deutsch: „“ }})
| {{#if: | (deutsch: „“) }}
}}
}}{{#if: {{{zitat}}}
| {{#if:
| {{#if: {{{zitat}}}
| Vorlage:": Text= und 1= gleichzeitig, bzw. Pipe zu viel }} }}
| Vorlage:": Text= fehlt }}{{#if: | {{#if: {{#invoke:Text|unstrip|{{{ref}}}}}
| Vorlage:": Ungültiger Wert: ref=
| {{{ref}}} }}
}}|.{{#if:{{#invoke:TemplUtl|faculty|}}|{{#if:||{{#ifeq: | JaKeinHinweis |{{#switch:
|0|=Vorlage:Toter Link/Core{{#if: https://lp.uni-goettingen.de/get/text/1234 | {{#if: | [3] }} (Seite {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar{{#if: | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. Suche im Internet Archive ){{#if: | {{#if: deadurlausgeblendet | | Vorlage:Toter Link/archivebot }} }} | (Seite {{#switch:|no|0|=|#default=dauerhaft }}nicht mehr abrufbar{{#if: | , festgestellt im {{#invoke:DateTime|format||F Y}} }}.) }}{{#switch: |no|0|= |#default={{#if: || }} }}{{#invoke:TemplatePar|check |opt = inline= url= text= datum= date= archivebot= bot= botlauf= fix-attempted= checked= |cat = Wikipedia:Vorlagenfehler/Vorlage:Toter Link |errNS = 0 |template = Vorlage:Toter Link |format = |preview = 1 }}{{#if: https://lp.uni-goettingen.de/get/text/1234 | {{#if:{{#invoke:URLutil|isWebURL|https://lp.uni-goettingen.de/get/text/1234}} || {{#if: || }} }} | {{#if: | {{#if: || }} | {{#if: || }} }} }}{{#if: | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}} || {{#if: || }} }} }}{{#switch: deadurl |checked|deadurl|= |#default= {{#if: || }} }}|#default= https://wiki-de.moshellshocker.dns64.de/index.php?title=Wikipedia:Defekte_Weblinks&dwl=https://lp.uni-goettingen.de/get/text/1234 Die nachstehende Seite ist {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar]{{#if: | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. (Suche im Internet Archive. ) {{#if: | {{#if: deadurlausgeblendet | | Vorlage:Toter Link/archivebot }} }}Vorlage:Toter Link/Core{{#switch: |no|0|= |#default= {{#if: || }} }}{{#invoke:TemplatePar|check |all = inline= url= |opt = datum= date= archivebot= bot= botlauf= fix-attempted= checked= |cat = Wikipedia:Vorlagenfehler/Vorlage:Toter Link |errNS = 0 |template = Vorlage:Toter Link |format = |preview = 1 }}{{#if: https://lp.uni-goettingen.de/get/text/1234 | {{#if:{{#invoke:URLutil|isWebURL|https://lp.uni-goettingen.de/get/text/1234}} || {{#if: || }} }} }}{{#if: | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}} || {{#if: || }} }} }}{{#switch: deadurl |checked|deadurl|= |#default= {{#if: || }} }}[https://lp.uni-goettingen.de/get/text/1234 }}|{{#switch: |0|=Vorlage:Toter Link/Core{{#if: https://lp.uni-goettingen.de/get/text/1234 | {{#if: | [4] }} (Seite {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar{{#if: | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. Suche im Internet Archive ){{#if: | {{#if: | | Vorlage:Toter Link/archivebot }} }} | (Seite {{#switch:|no|0|=|#default=dauerhaft }}nicht mehr abrufbar{{#if: | , festgestellt im {{#invoke:DateTime|format||F Y}} }}.) }}{{#switch: |no|0|= |#default={{#if: || }} }}{{#invoke:TemplatePar|check |opt = inline= url= text= datum= date= archivebot= bot= botlauf= fix-attempted= checked= |cat = Wikipedia:Vorlagenfehler/Vorlage:Toter Link |errNS = 0 |template = Vorlage:Toter Link |format = |preview = 1 }}{{#if: https://lp.uni-goettingen.de/get/text/1234 | {{#if:{{#invoke:URLutil|isWebURL|https://lp.uni-goettingen.de/get/text/1234}} || {{#if: || }} }} | {{#if: | {{#if: || }} | {{#if: || }} }} }}{{#if: | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}} || {{#if: || }} }} }}{{#switch: |checked|deadurl|= |#default= {{#if: || }} }}|#default= https://wiki-de.moshellshocker.dns64.de/index.php?title=Wikipedia:Defekte_Weblinks&dwl=https://lp.uni-goettingen.de/get/text/1234 Die nachstehende Seite ist {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar]{{#if: | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. (Suche im Internet Archive. ) {{#if: | {{#if: | | Vorlage:Toter Link/archivebot }} }}Vorlage:Toter Link/Core{{#switch: |no|0|= |#default= {{#if: || }} }}{{#invoke:TemplatePar|check |all = inline= url= |opt = datum= date= archivebot= bot= botlauf= fix-attempted= checked= |cat = Wikipedia:Vorlagenfehler/Vorlage:Toter Link |errNS = 0 |template = Vorlage:Toter Link |format = |preview = 1 }}{{#if: https://lp.uni-goettingen.de/get/text/1234 | {{#if:{{#invoke:URLutil|isWebURL|https://lp.uni-goettingen.de/get/text/1234}} || {{#if: || }} }} }}{{#if: | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}} || {{#if: || }} }} }}{{#switch: |checked|deadurl|= |#default= {{#if: || }} }}[https://lp.uni-goettingen.de/get/text/1234 }} }}}}}}}}}}{{#if:| {{#invoke:Vorlage:Internetquelle|archivBot|stamp={{{archiv-bot}}}|text={{#if:|Vorlage:Webarchiv/archiv-bot}}
}}}}{{#invoke:TemplatePar|check |all= url= titel= |opt= autor= hrsg= format= sprache= titelerg= werk= seiten= datum= abruf= zugriff= abruf-verborgen= archiv-url= archiv-datum= archiv-bot= kommentar= zitat= AT= CH= offline= |cat= {{#ifeq: 0 | 0 | Wikipedia:Vorlagenfehler/Vorlage:Internetquelle}} |template= Vorlage:Internetquelle |format=0 |preview=1 }}</ref>, d. h. lineare <math>(p=1) </math>, kubische <math>(p = 3) </math> und quintische <math>(p=5) </math> Splines, usw.
Die meisten Aussagen (Randbedingungen, Eindeutigkeit, Konvergenz) lassen sich analog zu kubischen Splines treffen<ref name=":0" />. Für <math>p = 5 </math> würde man beispielsweise ebenso ein lineares Gleichungssystem für die Bestimmung der Koeffizienten der Splines erhalten. Die Matrix wäre immer noch dünn besetzt, aber nicht mehr tridiagonal wie für kubische Splines.
Erhöht man <math>p </math> zu stark, so können wie bei der Polynominterpolation Runge-Oszillationen auftreten<ref name=":1" />. Deswegen und der Schwierigkeit praktische Randbedingungen zu definieren, sind Splines mit <math>p > 5 </math> praktisch eher selten zu finden.
Interpolation mit Formerhaltung
Splines sind aufgrund ihrer Eigenschaften im CAD weit verbreitet. Es stellt sich die Frage, unter welchen Bedingungen eine Spline-Interpolante eine der folgenden formerhaltenden Eigenschaften der zu interpolierenden Funktion <math>f \colon [a,b]\to\mathbb R</math> erbt:
- Nichtnegativität: <math>f(x)\ge 0</math> für alle <math>x</math>
- Monotonie: <math>f(x)\le f(y)</math> für <math>a\le x\le y\le b</math>
- Konvexität: <math>f(\lambda x+(1-\lambda) y)\le\lambda f(x)+(1-\lambda) f(y)</math> für alle <math>x,y\in[a,b]</math> und <math>\lambda\in[0,\,1]</math>
Hier zeigt sich, dass klassische Splines etwas schlechtere Eigenschaften haben als Bézierkurven. Zunächst stellt sich die Frage, wann ein interpolierender Spline konvex ist.
Für klassische Splines gilt, dass die Menge möglicher Splines auf dem Intervall <math>[a,b]</math> zum Gitter <math>\Delta:a=x_0<x_1<\dots<x_n=b</math> ein endlichdimensionaler Vektorraum ist. Für die Interpolation werden (nicht notwendig mit dem Gitter zusammenfallenden) Knoten <math>a=t_0<t_1<\dots<t_m=b</math> und zugehörige Ordinaten <math>f_0,\dots,f_m\in\mathbb R</math> vorgegeben und gefordert, dass der Spline <math>s</math> stetig differenzierbar in <math>(a,b)</math> ist und darüber hinaus <math>\displaystyle s(t_k)=f_k</math> für <math>k=0,1,\dots,m</math> gilt. Fordert man zusätzlich die Konvexität des interpolierenden Splines und geringe technische Annahmen, so stellt man fest, dass die Menge <math>Y</math> aller Ordinatentupel <math>(f_0,\dots,f_m)</math>, für die ein solcher Spline existiert, abgeschlossen ist.<ref name="Staircase Algorithm">Jochen W. Schmidt: Staircase Algorithm and Construction of Convex Spline Interpolants up to the Continuity <math>C^3</math>. In: Computers and Mathematics with Applications, Volume 31, Number 4, February 1995, pp. 67–79.</ref>
Das hat weitreichende Konsequenzen. <math>Y</math> ist eine echte Teilmenge des <math>{\mathbb R}^{m+1}</math>, falls <math>m\ge 2</math>, da die Eingangsdaten nicht in konvexer Lage zu sein brauchen. Bei Vorgabe eines Tupels auf dem Rand von <math>Y</math> kann infolge Rechenungenauigkeiten oder anderer Störungen die Menge <math>Y</math> verlassen worden sein, so dass trotz Lösbarkeit des Ausgangsproblems keine Lösung gefunden wird. Die andere Folgerung des Satzes ist noch schlimmer. Dazu seien fünf Punkte in Form des Zeichens „<math>\lor</math>“ so angeordnet, dass der mittlere Punkt genau auf der Spitze liegt. Die einzige konvexe Interpolierende ist dann die Betragsfunktion, und diese ist nicht stetig differenzierbar. Also gehört das 5-Tupel zum Komplement von <math>Y</math>, und dieses ist offen. Somit gibt es eine Umgebung des 5-Tupels, in der es ebenfalls keine konvexe, stetig differenzierbare Interpolierende gibt. Verschiebt man den mittleren Punkt geringfügig nach oben, ohne die Umgebung zu verlassen, dann erhält man folglich fünf Punkte in streng konvexer Lage, zu denen dennoch die Interpolationsaufgabe keine Lösung besitzt. Da dieser Effekt bei Vorgabe vieler Interpolationspunkte zunimmt, bleibt nur ein Ausweg, die Lösbarkeit für Eingangsdaten in streng konvexer Lage zu gewährleisten, nämlich die Voraussetzungen des Satzes zu verletzen. Die Menge, aus der die Splines entnommen werden dürfen, soll kein endlichdimensionaler Vektorraum sein. Dafür bieten sich u. a. an:
- (gebrochen-)rationale Splines
- Splines mit frei wählbaren Zwischenknoten
- Exponentialsplines
- lakunäre (lückenhafte) Splines
Siehe auch
- Akima-Interpolation – Ein Spezialfall der Spline-Interpolation
Literatur
- {{#invoke:Vorlage:Literatur|f}}
- {{#invoke:Vorlage:Literatur|f}}
Weblinks
- Online-Tool zur Kubischen Spline-Interpolation mit Visualisierung und JavaScript-Quellcode
- Skript zur Spline-Interpolation, Uni Göttingen
Einzelnachweise
<references />
- Seiten mit defekten Dateilinks
- Wikipedia:Vorlagenfehler/Parameter:URL
- Wikipedia:Vorlagenfehler/Parameter:Linktext
- Wikipedia:Vorlagenfehler/Parameter:Datum
- Wikipedia:Vorlagenfehler/Vorlage:"
- Wikipedia:Weblink offline fix-attempted
- Wikipedia:Vorlagenfehler/Vorlage:Toter Link
- Wikipedia:Vorlagenfehler/Vorlage:Toter Link/URL fehlt
- Numerische Mathematik