Spline interpolation.png Spline ist die Bezeichnung für bestimmte Funktionen aus der Analysis mit Anwendungen in der numerischen Mathematik. Ein Spline n-ten Grades ist eine Funktion, die stückweise aus Polynomen mit maximalem Grad n zusammengesetzt ist.

Splines werden vor allem zur Interpolation benutzt, wo dann an den Verklebungsstellen Bedingungen gestellt werden, etwa dass der Spline (n-1) mal stetig differenzierbar ist. Durch die stückweise Definition wird der unangenehme Effekt der Polynominterpolation beseitigt, dass für n+1 Stützpunkte ein Polynom n-ten Grades zur Interpolation benötigt wird. Dies führt unter anderem zu starken Abweichungen von der zu interpolierenden Funktion in den Randbereichen. Die Spline-Interpolation hat diese Probleme nicht.

Sind die einzelnen Polynome alle linear, so nennt man den Spline linear (es handelt sich dann um einen Polygonzug), analog gibt es quadratische, kubische usw. Splines. Der Begriff stammt aus dem Schiffbau: eine lange dünne Latte (Straklatte, englisch spline), die an einzelnen Punkten durch Nägel fixiert wird, biegt sich genau wie ein kubischer Spline mit natürlicher Randbedingung.

B-Splines

Wie auch der Raum der Polynome ist der Raum der stückweisen Polynome ein Vektorraum und hat eine Basis. Im Kontext numerischer Verfahren, wo Splines häufig eingesetzt werden, ist die Wahl der Basis entscheidend für eventuelle Rundungsfehler und damit für die praktische Einsetzbarkeit. Eine bestimmte Basis hat sich hier als am besten geeignet herausgestellt: sie ist numerisch stabil und erlaubt die Berechnung von Werten der Spline-Funktion mittels einer Drei-Term-Rekursion. Diese so genannten B-Spline-Basisfunktionen haben einen kompakten Träger, sie sind nur auf einem kleinen Intervall von Null verschieden. Änderungen der Koeffizienten wirken sich also nur lokal aus. Splines, die in dieser Basis dargestellt werden, nennt man B-Splines.

Siehe auch: Faltung (Mathematik)

Definition eines B-Splines

Die B-Spline-Basisfunktionen $N\_\{i,p,\backslash tau\}\backslash \; (i=1,\backslash ldots,n-p)$ der Ordnung $p$ mit Knotenvektor $\backslash tau\; =\; (\backslash tau\_1,\backslash ldots,\backslash tau\_n)\; \backslash quad\; (n\backslash ge\; 2\backslash ,p)$ werden durch die Rekursionsformel von de Boor/Cox/Mansfield definiert:

$N\_\{i,p+1,\backslash tau\}(u)\; =\; \backslash frac\{u-\backslash tau\_\{i\}\}\{\backslash tau\_\{i+p\}-\backslash tau\_\{i\}\}\backslash ,N\_\{i,p,\backslash tau\}(u)\; \backslash ;+\backslash ;\; \backslash frac\{\backslash tau\_\{i+p+1\}-u\}\{\backslash tau\_\{i+p+1\}-\backslash tau\_\{i+1\}\}\backslash ,N\_\{i+1,p,\backslash tau\}(u)$.

Die Elemente des Knotenvektors heißen auch Knotenpunkte (im engl. breakpoints) und müssen die Bedingungen $\backslash tau\_\{i\}\backslash le\backslash tau\_\{i+1\}$ und erfüllen.

Im CAD werden fast immer die ersten $p$ und letzten $p$ Knotenpunkte auf den gleichen Wert gesetzt.

Eigenschaften

• Nicht-Negativität: $N\_\{i,p,\backslash tau\}(u)\backslash ge\; 0$
• Lokaler Träger: $N\_\{i,p,\backslash tau\}(u)=\; 0\backslash mbox\{\; falls\; \}u\backslash not\backslash in*$
• Zerlegung der Eins: $\backslash sum\_\{i=0\}^\{n-p\}\; N\_\{i,p,\backslash tau\}(u)\; =\; 1,\; u\backslash in*$

Kurven

Splines lassen sich auch gut benutzen, um Kurven darzustellen. Hier finden sie Einsatz im CAD. Eine Spline-Kurve, deren Darstellung auf B-Splines beruht, nennt man B-Spline-Kurve. Bestimmt wird die Kurve durch so genannte De-Boor-Punkte, mit denen sich das Aussehen der Kurve leicht steuern lässt: Die Kurve liegt immer in der konvexen Hülle der De Boor Punkte, wird also von ihnen eingeschlossen.

Eine ähnliche Darstellung haben Bézier-Kurven. Diese basieren nicht auf der oben genannten Basis, sondern auf den Bernsteinpolynomen. Genau wie bei B-Spline-Kurven die De-Boor-Punkte gibt es hier die Bézier-Punkte, die das so genannte Kontrollpolygon bilden und mit denen man die Kurve leicht graphisch darstellen kann.

Mathematisch analog lassen sich auf beide Weisen nicht nur Kurven, sondern auch Flächen beschreiben.

Definition einer B-Spline-Kurve

Eine B-Spline-Kurve $C(u),\backslash \; u\backslash in*$ der Ordnung $p$ mit Knotenvektor $\backslash tau$ (s. o.) und Kontrollpunkten $P\_i\backslash \; (i=1,\backslash ldots,n-p)$ (auch De Boor Punkte genannt) wird definiert durch

$C(u)\; =\; \backslash sum\_\{i=1\}^\{n-p\}\backslash ;\; P\_i\backslash ,N\_\{i,p,\backslash tau\}(u)$.

Für Kurven in der Ebene sind die Kontrollpunkte 2-dimensional, für Kurven im Raum 3-dimensional.

Eigenschaften

• Lokalität: Der Kontrollpunkt $P\_i$ beeinflusst die Kurve nur im Intervall $*$

• Endpunkt-Interpolation: Es ist $P\_1\; =\; C(\backslash tau\_\{p\})$, falls der erste Knotenpunkt $p$-mal wiederholt wird und $P\_\{n-p\}\; =\; C(\backslash tau\_\{n-p+1\})$, falls der letzte Knotenpunkt $p$-mal wiederholt wird.

Definition einer B-Spline-Fläche

Eine B-Spline-Fläche der Ordnung $p$ und $q$ mit Knotenvektor $\backslash tau\; =\; (\backslash tau\_\{1\},\backslash ldots,\backslash tau\_\{n\})\backslash \; (n\backslash ge\; 2p)$ und $\backslash mu\; =\; (\backslash mu\_\{1\},\backslash ldots,\backslash mu\_\{m\})\backslash \; (m\backslash ge\; 2q)$ und Kontrollpunkten (bzw. De Boor Punkten) $P\_\{ij\}$ wird definiert durch

$C(u,v)\; =\; \backslash sum\_\{i=1\}^\{n-p\}\; \backslash sum\_\{j=1\}^\{m-q\}\backslash ;\; P\_\{ij\}\backslash ,N\_\{i,p,\backslash tau\}(u)\backslash ,N\_\{j,q,\backslash mu\}(v)$

Die Fläche ist definiert über dem Rechteck $\backslash times\; [\backslash mu\_\{q\},\backslash mu\_\{m-q+1\}$.

Eigenschaften

• Lokalität: Der Kontrollpunkt $P\_\{ij\}$ beeinflusst die Fläche nur im Rechteck $[\backslash mu\_\{j\},\backslash mu\_\{j+q\}$

• Endpunktinterpolation: Werden die ersten $p$ Knotenpunkte in $\backslash Tau$ auf den gleichen Wert gesetzt, die letzten $p$ Knotenpunkte in $\backslash tau$ auf den gleichen Wert gesetzt, die ersten $q$ Knotenpunkte in $\backslash mu$ auf den gleichen Wert gesetzt und die letzten $q$ Knotenpunkte in $\backslash mu$ auf den gleichen Wert gesetzt, dann gilt die Endpunktinterpolation, d. h. $P\_\{1,1\}=C(\backslash tau\_p,\backslash mu\_q)$, $P\_\{1,m-q\}=C(\backslash tau\_p,\backslash mu\_\{m-q+1\})$, $P\_\{n-p,1\}=C(\backslash tau\_\{n-p+1\},\backslash mu\_q)$ und $P\_\{n-p,m-q\}=C(\backslash tau\_\{n-p+1\},\backslash mu\_\{m-q+1\})$

Literatur

• Carl de Boor: A practical guide to splines. Springer Verlag, New York 1978 ISBN 0-387-90356-9 und ISBN 3-540-90356-9 (Rev. Aufl. von 2001 ISBN 0-387-95366-3)
• Gerald Farin: Curves and Surfaces for CAGD. A practical guide. 5. Aufl. Academic Press, San Diego 2002 ISBN 1-55860-737-4

Weblinks

• Java-Applet zum Berechnen von kubischen Splines

Numerische Mathematik | Mathematische Funktion

C2 kubická interpolace | Spline (mathematics) | Spline | Spline | Spline | Spline | Spline | Сплайн | Zlepek | 样条