Bei der Spline Interpolation versucht man gegebene Stutzstellen auch Knoten genannt mit Hilfe stuckweiser Polynome niedrigen Grades zu interpolieren Wahrend das Ergebnis einer Polynominterpolation durch unvorteilhaft festgelegte Stutzstellen oft bis zur Unkenntlichkeit oszilliert liefert die Splineinterpolation brauchbare Kurvenverlaufe und Approximationseigenschaften Rungephanomen Die Spline Interpolation lasst sich mit geringem linearem Aufwand berechnen liefert aber im Vergleich zur Polynominterpolation eine geringere Konvergenzordnung Beispiel eines Splines mit 8 KnotenVorlage fur 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 Krummungen Wahrend bei der Straklatte die Wendestellen Orte maximaler Linearitat und minimaler Biegeenergie in der Regel zwischen den Stutzstellen liegen und die Stutzstellen selbst Orte maximaler Krummung sind Orte maximaler Kraft durch Fixierung liegen die Wendestellen bei der Polynomeninterpolation nahe an den Stutzstellen bei der polynomialen Bestapproximation sogar in den Stutzstellen Die Begriffe Splineinterpolation bzw Splinefunktion ohne weitere Zusatze bezeichnen immer die Splineinterpolation bzw Splinefunktion dritten Grades Beide Begriffe werden zumeist synonym verwendet Der Begriff Spline wird jedoch zunehmend als Abkurzung fur B Spline seltener auch fur andere splineartige Linien wie die Bezierkurven benutzt Smoothing Splines sind Splines die nicht durch jeden Datenpunkt verlaufen mussen und konnen zur Signalglattung benutzt werden Inhaltsverzeichnis 1 Gegebenheiten 2 Linear einfacher Streckenzug 3 Kubisch Polynome 3 Grades 3 1 Der kubische C Spline 3 1 1 Konstruktion 3 1 2 Randbedingungen 3 1 3 Optimierung des Rechenaufwands 3 1 4 Minimalitatseigenschaft der zweiten Ableitung 3 2 Bikubischer C2 Spline 3 2 1 Konstruktion 3 2 2 Beispiel 4 Interpolation mit Formerhaltung 5 Siehe auch 6 Literatur 7 Weblinks 8 EinzelnachweiseGegebenheiten BearbeitenGegeben eine naturliche Zahl n N displaystyle n in mathbb N nbsp und n 1 displaystyle n 1 nbsp Stutzstellen x 0 lt x 1 lt lt x n 1 lt x n R displaystyle x 0 lt x 1 lt dotsb lt x n 1 lt x n in mathbb R nbsp sowie n 1 displaystyle n 1 nbsp Funktionswerte y 0 y 1 y n 1 y n R displaystyle y 0 y 1 dotsc y n 1 y n in mathbb R nbsp Gesucht ist eine stuckweise polynomiale Funktion ein Spline S x 0 x n R displaystyle S colon x 0 x n to mathbb R nbsp mit S x i y i displaystyle S x i y i nbsp fur i 0 n displaystyle i 0 dotsc n nbsp bei der fur i 0 n 1 displaystyle i 0 dotsc n 1 nbsp die Einschrankungen s i S x i x i 1 x i x i 1 R displaystyle s i S x i x i 1 colon x i x i 1 to mathbb R nbsp auf die Teilintervalle x i x i 1 displaystyle x i x i 1 nbsp Polynome sind Linear einfacher Streckenzug BearbeitenDie 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 s x m x b y 2 y 1 x 2 x 1 m x y 1 y 2 y 1 x 2 x 1 x 1 b y 1 m x 1 displaystyle begin aligned s x amp m cdot x b amp 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 aligned nbsp oder auch s x x 2 x x 2 x 1 y 1 x x 1 x 2 x 1 y 2 displaystyle s x frac x 2 x x 2 x 1 cdot y 1 frac x x 1 x 2 x 1 cdot y 2 nbsp Diese einfachen Spline Polynome konnen wie oben angesprochen sehr ungenau sein Wesentlich bessere Ergebnisse liefern kubische Spline Polynome Kubisch Polynome 3 Grades BearbeitenBei der Verbindung von Punkten mit Polynomen hoheren Grades mussen zusatzlich zu den Stutzstellen Eigenschaften definiert werden wie die Polynome ineinander ubergehen Fur kubische Splines sind in einer Dimension 4 Koeffizienten zu bestimmen und zwei weitere Bedingungen sind zu definieren Der kubische C Spline Bearbeiten C2 fordert dass die zusammengesetzte Funktion S displaystyle S nbsp aus allen Einschrankungen Teilintervallen s i displaystyle s i nbsp zweimal stetig differenzierbar ist Dafur wird gefordert dass die erste und zweite Ableitung der Einschrankungen an den Stutzstellen s i x i s i 1 x i displaystyle s i x i s i 1 x i nbsp und s i x i s i 1 x i displaystyle s i x i s i 1 x i nbsp fur i 1 n 1 displaystyle i 1 dotsc n 1 nbsp ubereinstimmen Prinzipiell gilt dass sich eine Anderung einer Stutzstelle x i y i displaystyle x i y i nbsp stets global auf den gesamten Spline S displaystyle S nbsp auswirkt jedoch wird der Einfluss der Anderung mit zunehmender Distanz zu x i displaystyle x i nbsp anders als bei Interpolationspolynomen stark gedampft Kubische Splines neigen daher weniger zum Uberschwingen Der kubische C2 Spline erfullt eine Minimalitatseigenschaft der zweiten Ableitung was ihn gegenuber anderen Interpolationen besonders interessant macht Konstruktion Bearbeiten Es ist ersichtlich dass die zweite Ableitung von S displaystyle S nbsp ein linearer Spline ist Diese kann daher wie oben beschrieben durch folgende Form beschrieben werden s i x x i 1 x h i M i x x i h i M i 1 displaystyle s i x frac x i 1 x h i cdot M i frac x x i h i cdot M i 1 nbsp mit h i x i 1 x i displaystyle h i x i 1 x i nbsp fur i 0 n 1 displaystyle i 0 dotsc n 1 nbsp M i displaystyle M i nbsp sind die sogenannten Momente 1 welche den Werten von S x i displaystyle S x i nbsp an den Stutzstellen entsprechen und im Folgenden zu berechnen sind Durch zweifache Integration und geschickte Umformung entstehen aus diesen Gleichungen Polynome dritten Grades mit zwei weiteren Parametern c i displaystyle c i nbsp und d i displaystyle d i nbsp der Form 1 6 x i 1 x 3 h i M i x x i 3 h i M i 1 c i x x i d i displaystyle 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 nbsp Um die Stetigkeitsbedingungen s i x i y i displaystyle s i x i y i nbsp und s i x i 1 y i 1 displaystyle s i x i 1 y i 1 nbsp zu erfullen wahlen wir 2 d i y i h i 2 6 M i displaystyle d i y i frac h i 2 6 cdot M i nbsp und c i y i 1 y i h i h i 6 M i 1 M i displaystyle c i frac y i 1 y i h i frac h i 6 cdot M i 1 M i nbsp Mit diesem Ansatz stimmen bereits die nullten und die zweiten Ableitungen der Einschrankungen s i displaystyle s i nbsp an den Stutzstellen uberein Die Momente sind so zu wahlen dass auch die ersten Ableitungen an den Stutzstellen gleich sind Mit s i x 1 2 x i 1 x 2 h i M i x x i 2 h i M i 1 c i displaystyle 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 nbsp und s i x i s i 1 x i displaystyle s i x i s i 1 x i nbsp lassen sich folgende Gleichungen aufstellen h i 1 6 M i 1 h i 1 h i 3 M i h i 6 M i 1 y i 1 y i h i y i y i 1 h i 1 displaystyle 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 nbsp fur i 1 n 1 displaystyle i 1 dots n 1 nbsp Fur i 0 displaystyle i 0 nbsp und i n displaystyle i n nbsp fehlen hier zwei Gleichungen welche sich aus den Randbedingungen ergeben Dieses lineare Gleichungssystem kann auch durch folgende tridiagonale streng diagonaldominante Matrix ausgedruckt werden m 0 l 0 h 0 6 h 0 h 1 3 h 1 6 h i 1 6 h i 1 h i 3 h i 6 l n m n M 0 M 1 M i M n b 0 y 2 y 1 h 1 y 1 y 0 h 0 y i 1 y i h i y i y i 1 h i 1 b n displaystyle begin bmatrix mu 0 amp lambda 0 amp amp amp amp frac h 0 6 amp frac h 0 h 1 3 amp frac h 1 6 amp amp amp amp ddots amp ddots amp ddots amp amp amp amp frac h i 1 6 amp frac h i 1 h i 3 amp frac h i 6 amp amp amp amp ddots amp ddots amp ddots amp amp amp amp lambda n amp 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 nbsp Die Werte fur die l i m i b i displaystyle lambda i mu i b i nbsp hangen von den Randbedingungen ab Zur Losung kann hier auf den komplizierten Gauss Algorithmus verzichtet werden und z B ein einfacher Vorwarts Durchlauf zur Elimination der Elemente unter der Hauptdiagonalen mit anschliessender Ruckwartssubstitution verwendet werden Thomas Algorithmus Randbedingungen Bearbeiten Prinzipiell gibt es ein Interpolationsintervall weniger als Stutzstellen Zaunpfahlproblem Das heisst dass zwei Gleichungen zur Bestimmung aller Koeffizienten fehlen Diese ergeben sich aus den Randbedingungen Typische Randbedingungen sind Naturliche Randbedingungen auch freier Rand Bedingung s 0 x 0 0 displaystyle s 0 x 0 0 nbsp s n 1 x n 0 displaystyle s n 1 x n 0 nbsp Bedeutung Das Spline schliesst mit Wendepunkten ab Berechnung l 0 l n b 0 b n 0 displaystyle lambda 0 lambda n b 0 b n 0 nbsp und m 0 m n 1 displaystyle mu 0 mu n 1 nbsp Hermite Randbedingungen auch eingespannter Rand Bedingung s 0 x 0 f a displaystyle s 0 x 0 f a nbsp s n 1 x n f b displaystyle s n 1 x n f b nbsp Bedeutung f a displaystyle f a nbsp und f b displaystyle f b nbsp sind vorgegeben normalerweise entweder durch die Ableitung einer zu interpolierenden Funktion f displaystyle f nbsp oder durch eine Approximation derselben Berechnung l 0 h 0 6 m 0 h 0 3 b 0 y 1 y 0 h 0 f a l n h n 1 6 m n h n 1 3 b n y n y n 1 h n 1 f b displaystyle begin matrix lambda 0 frac h 0 6 amp mu 0 frac h 0 3 amp b 0 frac y 1 y 0 h 0 f a lambda n frac h n 1 6 amp mu n frac h n 1 3 amp b n frac y n y n 1 h n 1 f b end matrix nbsp dd periodische RandbedingungenBedingung Intervall x 0 x n 1 displaystyle x 0 x n 1 nbsp y 0 y n 1 displaystyle y 0 y n 1 nbsp s 0 x 0 s n x n 1 displaystyle s 0 x 0 s n x n 1 nbsp s 0 x 0 s n x n 1 displaystyle s 0 x 0 s n x n 1 nbsp Bedeutung Nullte erste und zweite Ableitung von S displaystyle S nbsp am Anfang und am Ende des Intervalls sind gleich Berechnung Es wird eine zusatzliche Stutzstelle x n 1 displaystyle x n 1 nbsp eingefuhrt welche das Intervall begrenzt Die Anzahl der Gleichungen zur Berechnung der Momente und die Grosse der Matrix bleibt jedoch gleich da M n 1 M 0 displaystyle M n 1 M 0 nbsp bereits gegeben ist damit die zweiten Ableitungen ubereinstimmen Fur die erste und letzte Zeile der Matrix gilt m 0 h n h 0 3 l 0 h 0 6 b 0 y 1 y 0 h 0 y 0 y n h n m n h n 1 h n 3 l n h n 1 6 b n y 0 y n h n y n y n 1 h n 1 displaystyle begin matrix mu 0 frac h n h 0 3 amp lambda 0 frac h 0 6 amp 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 amp lambda n frac h n 1 6 amp b n frac y 0 y n h n frac y n y n 1 h n 1 end matrix nbsp dd Ausserdem sind die Ecken der Matrix abseits der Hauptdiagonalen hier nicht Null m 0 n m n 0 h n 6 displaystyle m 0 n m n 0 frac h n 6 nbsp dd Die Losung dieses Systems ist daher komplizierter Im Falle aquidistanter Stutzstellen lasst sich fur diesen Fall eine Transformation anwenden not a knot RandbedingungenBedingung s 0 x 1 s 1 x 1 displaystyle s 0 x 1 s 1 x 1 nbsp s n 2 x n 1 s n 1 x n 1 displaystyle s n 2 x n 1 s n 1 x n 1 nbsp Bedeutung Die ausseren drei Punkte werden je durch ein gemeinsames Polynom interpoliert was zum Beispiel durch Gleichsetzen der dritten Ableitungen erfolgen kann Fur Splines bis einschliesslich vier Stutzstellen geht der not a knot Spline daher in ein gewohnliches Interpolationspolynom uber Verwendet wird der not a knot Spline zum Beispiel vom Programm Matlab Berechnung Es gelte n gt 4 displaystyle n gt 4 nbsp Fur die Vorwartssubstitution wird zunachst die Randbedingung an x 0 displaystyle x 0 nbsp betrachtet Hierfur konnen folgende Werte verwendet werden m 0 1 l 0 h 1 2 h 0 h 1 h 0 b 0 6 h 0 h 1 2 h 0 2 y 2 y 1 h 1 y 1 y 0 h 0 displaystyle begin matrix mu 0 1 amp lambda 0 frac h 1 2 cdot h 0 h 1 h 0 amp 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 nbsp dd Falls h 1 h 0 displaystyle h 1 h 0 nbsp 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 m 2 1 0 m 2 2 h 1 h 2 3 m 2 3 h 2 6 b 2 y 3 y 2 h 2 y 2 y 1 h 1 y 2 2 y 1 y 0 6 h 0 displaystyle begin matrix m 2 1 0 amp m 2 2 frac h 1 h 2 3 amp m 2 3 frac h 2 6 amp 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 nbsp dd Gelost wird nun lediglich die Untermatrix beginnend bei m 2 2 displaystyle m 2 2 nbsp und das Randpolynom p s 0 s 1 displaystyle p s 0 s 1 nbsp auf dem Intervall x 0 x 2 displaystyle x 0 x 2 nbsp wird durch eine zusatzliche Polynominterpolation bestimmt sodass p x 1 y 1 displaystyle p x 1 y 1 nbsp p x 2 y 2 displaystyle p x 2 y 2 nbsp p x 2 s 2 x 2 displaystyle p x 2 s 2 x 2 nbsp p x 2 s 2 x 2 displaystyle p x 2 s 2 x 2 nbsp p x 0 y 0 displaystyle p x 0 y 0 nbsp ist dadurch bereits erfullt Nach dem Vorwartsdurchlauf zur Elimination der Elemente unter der Diagonalen wird nun die Randbedingung an x n displaystyle x n nbsp betrachtet m n 1 l n 0 b n b n 1 m n 2 n 1 b n 2 m n 1 n 1 b n 1 m n 2 n 2 h n 1 b n 1 m n 2 n 2 h n 2 m n 2 n 1 m n 2 n 2 m n 1 n h n 1 m n 2 n 2 m n 1 n m n 2 n 2 m n 1 n 1 h n 2 displaystyle begin matrix mu n 1 amp lambda n 0 amp 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 nbsp dd Weitere Randbedingungen sind gebrauchlich wie etwa integrale Randbedingungen 3 oder die im Folgenden vorgestellte symmetrische Verlangerung Optimierung des Rechenaufwands Bearbeiten Bei aquidistanten Stutzstellen mit konstantem Abstand h displaystyle h nbsp vereinfacht sich das Gleichungssystem zu M i 1 4 M i M i 1 6 y i 1 2 y i y i 1 h 2 displaystyle M i 1 4 cdot M i M i 1 6 frac y i 1 2 cdot y i y i 1 h 2 nbsp fur i 1 n 1 displaystyle i 1 dots n 1 nbsp Mit der symmetrischen Verlangerung m 0 m n 4 displaystyle mu 0 mu n 4 nbsp und l 0 l n 1 displaystyle lambda 0 lambda n 1 nbsp entsteht daraus eine sogenannte Tridiagonal Toeplitz Matrix welche besonders effizient auch parallel gelost werden kann Fur die rechte Seite kann hier b 0 y 1 2 h displaystyle b 0 tfrac y 1 2 cdot h nbsp und b n y n 1 2 h displaystyle b n tfrac y n 1 2 cdot h nbsp angesetzt werden Mit A 6 h M displaystyle A tfrac 6 h cdot M nbsp lasst sich schreiben A 4 1 0 0 0 0 1 4 1 0 0 0 0 1 4 0 0 0 0 0 0 4 1 0 0 0 0 1 4 1 0 0 0 0 1 4 R n 1 n 1 displaystyle A begin bmatrix 4 amp 1 amp 0 amp cdots amp 0 amp 0 amp 0 1 amp 4 amp 1 amp cdots amp 0 amp 0 amp 0 0 amp 1 amp 4 amp cdots amp 0 amp 0 amp 0 vdots amp vdots amp vdots amp ddots amp vdots amp vdots amp vdots 0 amp 0 amp 0 amp cdots amp 4 amp 1 amp 0 0 amp 0 amp 0 amp cdots amp 1 amp 4 amp 1 0 amp 0 amp 0 amp cdots amp 0 amp 1 amp 4 end bmatrix in mathbb R n 1 times n 1 nbsp Diese hat die Inverse B b n 1 1 b n b 0 b n 1 b 0 1 n 1 b 1 b 0 1 n b 0 b 0 b n 1 b 0 b n 1 b 1 1 n b 1 b 1 1 n 1 b 0 b 1 1 n 1 b 1 b 0 1 n b 1 b 1 b 1 b n 1 b 0 b n 1 1 n b 0 b 0 1 n 1 b 0 b 1 b 0 b n 1 b 0 b n displaystyle B b n 1 1 begin bmatrix b n b 0 amp b n 1 b 0 amp cdots amp 1 n 1 b 1 b 0 amp 1 n b 0 b 0 b n 1 b 0 amp b n 1 b 1 amp cdots amp 1 n b 1 b 1 amp 1 n 1 b 0 b 1 vdots amp vdots amp ddots amp vdots amp vdots 1 n 1 b 1 b 0 amp 1 n b 1 b 1 amp cdots amp b 1 b n 1 amp b 0 b n 1 1 n b 0 b 0 amp 1 n 1 b 0 b 1 amp cdots amp b 0 b n 1 amp b 0 b n end bmatrix nbsp mit Koeffizienten b i displaystyle b i nbsp die den Gleichungen b 0 1 displaystyle b 0 1 nbsp b 1 4 displaystyle b 1 4 nbsp der Rekursion b i 4 b i 1 b i 2 displaystyle b i 4b i 1 b i 2 nbsp und explizit der Formel b i 3 2 3 i 1 3 2 3 i 1 6 displaystyle b i sqrt 3 2 sqrt 3 i 1 sqrt 3 2 sqrt 3 i 1 6 nbsp genugen Minimalitatseigenschaft der zweiten Ableitung Bearbeiten Unter allen zweimal stetig differenzierbaren Funktionen die alle Stutzstellen innerhalb eines Intervalls a b displaystyle a b nbsp miteinander verbinden hat unter Verwendung naturlicher periodischer oder Hermite Randbedingungen der kubische Spline die geringste Krummung a b f x 2 d x a b S x 2 d x displaystyle int a b f x 2 mathrm d x geq int a b S x 2 mathrm d x nbsp wobei f displaystyle f nbsp hier eine beliebige Funktion auf a b displaystyle a b nbsp aus C2 ist die alle Stutzstellen schneidet Anschaulich folgt daraus dass ein zu volles Glas Wasser das wahrend einer Zugfahrt auf dem Tisch steht am wenigsten uberschwappt wenn der Streckenzug der Schienenfuhrung mithilfe kubischer Splines parametrisiert wurde Diese sogenannte Identitat von Holladay wurde im Jahr 1957 von Holladay 4 bewiesen Sei mit C 2 a b displaystyle C 2 a b nbsp der Raum der zweimal differenzierbaren Funktionen bezeichnet fur welche die nullte und erste Ableitung absolutstetig sind und die zweite Ableitung in L 2 a b displaystyle L 2 a b nbsp liegt Sei nun S displaystyle S nbsp eine interpolierende Splinefunktion zu einer beliebigen Funktion f C 2 a b displaystyle f in C 2 a b nbsp und displaystyle nbsp die L 2 displaystyle L 2 nbsp Norm so gilt f S 2 f 2 S 2 2 D displaystyle f S 2 f 2 S 2 2D nbsp mit D f x S x S x a b i 1 n f x S x S x i 1 x i displaystyle 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 nbsp Erfullt die Splinefunktion die naturlichen periodischen oder vollstandigen Randbedingungen so ist D 0 displaystyle D 0 nbsp also f S 2 f 2 S 2 0 f 2 S 2 displaystyle f S 2 f 2 S 2 geq 0 Rightarrow f 2 geq S 2 nbsp Damit gilt nun f S 2 min T C 2 f T 2 displaystyle f S 2 min T in C 2 f T 2 nbsp Bikubischer C2 Spline Bearbeiten Der bikubische C2 Spline ist die Verallgemeinerung des einfachen kubischen C2 Splines auf zwei Dimensionen man spricht hierbei auch von multivariater Interpolation Dafur mussen die zu interpolierenden Punkte zij in einem rechteckigen Gitter angeordnet sein 5 Jede zwischen vier Punkten aufgespannte Flache Aij wird durch ein zweidimensionales Polynom von 16 Koeffizienten charakterisiert z A i j x y k 0 3 l 0 3 a k l i j x k y l a 0 0 i j a 1 0 i j x a 2 0 i j x 2 a 3 0 i j x 3 a 0 1 i j y a 1 1 i j x y a 2 1 i j x 2 y a 3 1 i j x 3 y a 0 2 i j y 2 a 1 2 i j x y 2 a 2 2 i j x 2 y 2 a 3 2 i j x 3 y 2 a 0 3 i j y 3 a 1 3 i j x y 3 a 2 3 i j x 2 y 3 a 3 3 i j x 3 y 3 displaystyle z A ij x y sum k 0 3 sum l 0 3 a k l ij cdot x k cdot y l begin matrix a 0 0 ij amp amp a 1 0 ij cdot x amp amp a 2 0 ij cdot x 2 amp amp a 3 0 ij cdot x 3 amp a 0 1 ij cdot y amp amp a 1 1 ij cdot x cdot y amp amp a 2 1 ij cdot x 2 cdot y amp amp a 3 1 ij cdot x 3 cdot y amp a 0 2 ij cdot y 2 amp amp a 1 2 ij cdot x cdot y 2 amp amp a 2 2 ij cdot x 2 cdot y 2 amp amp a 3 2 ij cdot x 3 cdot y 2 amp a 0 3 ij cdot y 3 amp amp a 1 3 ij cdot x cdot y 3 amp amp a 2 3 ij cdot x 2 cdot y 3 amp amp a 3 3 ij cdot x 3 cdot y 3 amp end matrix nbsp Fur einen zweidimensionalen C2 Spline mussen die Koeffizienten so gewahlt werden dass die aus allen Flachen zusammengesetzte Funktion S x y R 2 R displaystyle S x y mathbb R 2 rightarrow mathbb R nbsp zweimal stetig in x und y Richtung differenzierbar ist Das heisst neben S selbst sind die folgenden Ableitungen stetig auf ganz R 2 displaystyle mathbb R 2 nbsp S x y x S x y y 2 S x y x 2 2 S x y y 2 2 S x y x y 3 S x y x 2 y 3 S x y x y 2 4 S x y x 2 y 2 displaystyle begin matrix frac partial S x y partial x amp frac partial S x y partial y amp frac partial 2 S x y partial x 2 amp frac partial 2 S x y partial y 2 amp frac partial 2 S x y partial x partial y amp frac partial 3 S x y partial x 2 partial y amp frac partial 3 S x y partial x partial y 2 amp frac partial 4 S x y partial x 2 partial y 2 end matrix nbsp Konstruktion Bearbeiten nbsp Veranschaulichung zur Konstruktion eines bikubischen SplinesEs ist ersichtlich dass jeder Schnitt durch eine Teilflache A i j displaystyle A i j nbsp parallel zur x displaystyle x nbsp oder y displaystyle y nbsp Achse eine eindimensionale Kurve liefert welche durch ein kubisches Polynom von vier Koeffizienten beschrieben werden kann Daraus folgt dass die vier Rander jeder Teilflache solche Polynome sind Um die geforderte zweifach stetige Differenzierbarkeit zu erhalten konnen zunachst alle Punkte entlang der Gitterlinien eindimensional interpoliert werden Das bikubische Spline erbt dabei die verwendeten Randbedingungen der eindimensionalen Splines Nun stehen zu jedem zweidimensionalen Polynom A i j displaystyle A i j nbsp mit 16 Koeffizienten vier eindimensionale Randpolynome s x i j displaystyle s x i j nbsp s x i j 1 displaystyle s x i j 1 nbsp s y i j displaystyle s y i j nbsp s y i 1 j displaystyle s y i 1 j nbsp mit je 4 Koeffizienten zur Verfugung Hierbei kennzeichnet der erste Index der s zu welcher Achse sie parallel verlaufen Um diese Randpolynome zu A i j displaystyle A i j nbsp zusammenzurechnen ist ein System von 16 linearen Gleichungen aufzustellen Vier Gleichungen ergeben sich aus der Forderung dass S an den Gitterpunkten genau die Werte z i j displaystyle z i j nbsp annimmt 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 displaystyle begin matrix A i j x i y j z i j amp A i j x i 1 y j z i 1 j amp A i j x i y j 1 z i j 1 amp A i j x i 1 y j 1 z i 1 j 1 end matrix nbsp Weitere vier Gleichungen ergeben sich aus der Ableitung der zur x displaystyle x nbsp Achse parallelen Randpolynome nach x displaystyle x nbsp A i j x i y j x s x i j x i x A i j x i 1 y j x s x i j x i 1 x A i j x i y j 1 x s x i j 1 x i x A i j x i 1 y j 1 x s x i j 1 x i 1 x displaystyle begin matrix frac partial A i j x i y j partial x frac partial s x i j x i partial x amp frac partial A i j x i 1 y j partial x frac partial s x i j x i 1 partial x amp frac partial A i j x i y j 1 partial x frac partial s x i j 1 x i partial x amp 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 nbsp Weitere vier Gleichungen aus der Ableitung der zur y displaystyle y nbsp Achse parallelen Randpolynome nach y displaystyle y nbsp A i j x i y j y s y i j y j y A i j x i 1 y j y s y i 1 j y j y A i j x i y j 1 y s y i j y j 1 y A i j x i 1 y j 1 y s y i 1 j y j 1 y displaystyle begin matrix frac partial A i j x i y j partial y frac partial s y i j y j partial y amp frac partial A i j x i 1 y j partial y frac partial s y i 1 j y j partial y amp frac partial A i j x i y j 1 partial y frac partial s y i j y j 1 partial y amp 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 nbsp Nun ergibt sich das Problem dass entlang jedem der vier Rander zwei Punkte und zwei Ableitungen gegeben sind Damit ist ein Polynom von Grad 3 entlang des jeweiligen Randes eigentlich vollstandig spezifiziert Das hinzunehmen z B der zweiten Ableitungen an den Eckpunkten oder weiterer Funktionswerte entlang der Randpolynome wurde eine lineare Abhangigkeit im Gleichungssystem erzeugen Mit den gegebenen Gleichungen lassen sich jedoch nur 12 der 16 Koeffizienten bestimmen Ein nicht linear abhangiges System ergibt sich durch Hinzunahme der gemischten Ableitungen nach x und y Setzt man diese in den Eckpunkten etwa auf null so ist S displaystyle S nbsp nur in den Eckpunkten zweimal stetig differenzierbar Entlang der Rander ergeben sich in den zweiten Ableitungen jedoch Sprunge Aus den Randpolynomen lassen sich die gemischten Ableitungen jedoch nicht direkt berechnen Um nun korrekte Werte fur diese gemischten Ableitungen zu erhalten welche auch entlang der Rander stetige zweite Ableitungen von S displaystyle S nbsp liefern kann wie folgt vorgegangen werden Entlang der Gitterlinien welche parallel zur x displaystyle x nbsp Achse verlaufen werden weitere eindimensionale Splines s d displaystyle s d nbsp gebildet Diese interpolieren statt der z displaystyle z nbsp Werte die Ableitungen von s y displaystyle s y nbsp an deren Schnittpunkten mit den x displaystyle x nbsp Gitterlinien Die s d displaystyle s d nbsp Splines konnen nun nach x displaystyle x nbsp abgeleitet werden Daraus ergeben sich die gemischten Ableitungen 2 A i j x i y j x y s d i j x i x 2 A i j x i 1 y j x y s d i j x i 1 x 2 A i j x i y j 1 x y s d i j 1 x i x 2 A i j x i 1 y j 1 x y s d i j 1 x i 1 x displaystyle 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 amp 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 amp 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 amp 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 nbsp Wie beim eindimensionalen C2 Spline wirkt sich auch beim bikubischen Spline eine Anderung in einer Stutzstelle Datenpunkt generell auf alle Teilflachen aus Dies veranschaulicht warum eine Konstruktion alleine aus den Randpolynomen s x displaystyle s x nbsp und s y displaystyle s y nbsp fehlschlagt Diese andern sich nur wenn ein Datenwert welcher parallel in x displaystyle x nbsp oder y displaystyle y nbsp Richtung zur betrachteten Teilflache liegt geandert wird In der Abbildung rechts hat eine Anderung von z 3 0 displaystyle z 3 0 nbsp keinen Einfluss auf die 1D Splines welche den Rand von A 1 1 displaystyle A 1 1 nbsp bilden Erst die erneute Interpolation durch s d displaystyle s d nbsp erzeugt eine Abhangigkeit zwischen diesem Punkt und der Flache Beispiel Bearbeiten nbsp Beispiel fur bikubische Interpolation 6 Ein Datenblock aus 6x6 Werten links wird bikubisch interpoliert Mitte Dabei wurden naturliche Randbedingungen angenommen die zweite Ableitung auf den Randpunkten ist null Die Farben zwischen linkem und mittlerem Bild wurden synchronisiert und beschreiben die Funktionswerte ahnlich der Farben auf einer Landkarte zur Illustration der Hohe Um die Korrektheit der Interpolation zu verdeutlichen wird rechts die zweite Ableitung 4 S x 2 y 2 displaystyle frac partial 4 S partial x 2 partial y 2 nbsp gezeigt Diese besteht aus linearen Funktionen und ist immer noch stetig Interpolation mit Formerhaltung BearbeitenSplines 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 f a b R displaystyle f colon a b to mathbb R nbsp erbt Nichtnegativitat f x 0 displaystyle f x geq 0 nbsp fur alle x displaystyle x nbsp Monotonie f x f y displaystyle f x leq f y nbsp fur a x y b displaystyle a leq x leq y leq b nbsp Konvexitat f l x 1 l y l f x 1 l f y displaystyle f lambda x 1 lambda y leq lambda f x 1 lambda f y nbsp fur alle x y a b displaystyle x y in a b nbsp und l 0 1 displaystyle lambda in 0 1 nbsp Hier zeigt sich dass klassische Splines etwas schlechtere Eigenschaften haben als Bezierkurven Zunachst stellt sich die Frage wann ein interpolierender Spline konvex ist Fur klassische Splines gilt dass die Menge moglicher Splines auf dem Intervall a b displaystyle a b nbsp zum Gitter D a x 0 lt x 1 lt lt x n b displaystyle Delta a x 0 lt x 1 lt dots lt x n b nbsp ein endlichdimensionaler Vektorraum ist Fur die Interpolation werden nicht notwendig mit dem Gitter zusammenfallenden Knoten a t 0 lt t 1 lt lt t m b displaystyle a t 0 lt t 1 lt dots lt t m b nbsp und zugehorige Ordinaten f 0 f m R displaystyle f 0 dots f m in mathbb R nbsp vorgegeben und gefordert dass der Spline s displaystyle s nbsp stetig differenzierbar in a b displaystyle a b nbsp ist und daruber hinaus s t k f k displaystyle displaystyle s t k f k nbsp fur k 0 1 m displaystyle k 0 1 dots m nbsp gilt Fordert man zusatzlich die Konvexitat des interpolierenden Splines und geringe technische Annahmen so stellt man fest dass die Menge Y displaystyle Y nbsp aller Ordinatentupel f 0 f m displaystyle f 0 dots f m nbsp fur die ein solcher Spline existiert abgeschlossen ist 7 Das hat weitreichende Konsequenzen Y displaystyle Y nbsp ist eine echte Teilmenge des R m 1 displaystyle mathbb R m 1 nbsp falls m 2 displaystyle m geq 2 nbsp da die Eingangsdaten nicht in konvexer Lage zu sein brauchen Bei Vorgabe eines Tupels auf dem Rand von Y displaystyle Y nbsp kann infolge Rechenungenauigkeiten oder anderer Storungen die Menge Y displaystyle Y nbsp verlassen worden sein so dass trotz Losbarkeit des Ausgangsproblems keine Losung gefunden wird Die andere Folgerung des Satzes ist noch schlimmer Dazu seien funf Punkte in Form des Zeichens displaystyle lor nbsp 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 gehort das 5 Tupel zum Komplement von Y displaystyle Y nbsp 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 geringfugig nach oben ohne die Umgebung zu verlassen dann erhalt man folglich funf Punkte in streng konvexer Lage zu denen dennoch die Interpolationsaufgabe keine Losung besitzt Da dieser Effekt bei Vorgabe vieler Interpolationspunkte zunimmt bleibt nur ein Ausweg die Losbarkeit fur Eingangsdaten in streng konvexer Lage zu gewahrleisten namlich die Voraussetzungen des Satzes zu verletzen Die Menge aus der die Splines entnommen werden durfen soll kein endlichdimensionaler Vektorraum sein Dafur bieten sich u a an gebrochen rationale Splines Splines mit frei wahlbaren Zwischenknoten Exponentialsplines lakunare luckenhafte SplinesSiehe auch BearbeitenAkima Interpolation Ein Spezialfall der Spline InterpolationLiteratur BearbeitenStoer Bulirsch Numerische Mathematik 1 10 Auflage Springer Verlag Berlin Heidelberg New York 2007 ISBN 978 3 540 45389 5 2 5 Spline Interpolation S 112 148 mit Beispielen Beweisen Ubungsaufgaben und umfangreichen Angaben zu weiterer speziellerer Literatur Weblinks BearbeitenOnline Tool zur Kubischen Spline Interpolation mit Visualisierung und JavaScript Quellcode Skript zur Spline Interpolation Uni GottingenEinzelnachweise Bearbeiten Robert Plato Numerische Mathematik kompakt 4 Auflage Seite 27 Bemerkung 2 11 Josef Stoer Numerische Mathematik 1 9 Auflage Abschnitt 2 4 2 Seite 109 Lebesgue und Birkhoff Handbook of Splines Abschnitt 1 9 Seite 56 Takeo Akasaki William F Donoghue Jr George S McCarty John C Holladay 1928 1986 In Memoriam University of California 1986 abgerufen am 22 Januar 2021 Lebesgue und Birkhoff Handbook of Splines Abschnitt 2 2 Seite 82 Die Beispielinterpolation wurde erstellt mit Programm Numeric Collection von Mitja Stachowiak Jochen W Schmidt Staircase Algorithm and Construction of Convex Spline Interpolants up to the Continuity C 3 displaystyle C 3 nbsp In Computers and Mathematics with Applications Volume 31 Number 4 February 1995 pp 67 79 Abgerufen von https de wikipedia org w index php title Spline Interpolation amp oldid 234508045
