Spline

Ein Spline ist ein Begriff aus der numerischen Mathematik und bezeichnet ein stückweises Polynom, das für Polynome n-ten Grades an den Punkten, an denen jeweils zwei Polynome aufeinandertreffen, n-1 Mal stetig differenzierbar ist. Splines werden zur (Spline-)Interpolation benutzt und stellen eine Variante der Polynominterpolation dar. Durch die stückweise Definition wird der unangenehme Effekt der Polynominterpolation beseitigt, dass für n Stützpunkte ein Polynom n-ten Grades zur Interpolation benötigt wird. Dies führt u.A. zu starken Abweichungen von der zu interpolierenden Funktion in den Randbereichen.

Datei:Spline interpolation.png

Beispiel eines Splines

Sind die einzelnen Polynome alle linear, so nennt man den Spline linear, analog gibt es quadratische, kubische usw. Splines. Der Begriff stammt aus dem Schiffbau: eine lange dünne Latte (Straklatte), 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 nicht Null. Änderungen der Koeffizienten wirken sich also nur lokal aus. Splines, die in dieser Basis dargestellt werden, nennt man B-Splines. Sie werden vor allem zur Interpolation von Funktionen benutzt.

Siehe auch: Spline-Interpolation, Faltung (Mathematik)

Mathematische Definition

Die B-Spline-Basisfunktionen $N_{i,p,\tau }\ (i=1,\ldots ,n-p)$ der Ordnung $p$ mit Knotenvektor

\tau =(\tau _{1},\ldots ,\tau _{n})\quad (n\geq 2\,p)

werden rekursiv definiert durch

N_{i,1,\tau }(u)={\begin{cases}1,&u\in \left[\tau _{i},\tau _{i+1}\right]\\0,&{\mbox{sonst}}\end{cases}}

und

N_{i,p+1,\tau }(u)={\frac {u-\tau _{i}}{\tau _{i+p}-\tau _{i}}}\,N_{i,p,\tau }(u)+{\frac {\tau _{i+p+1}-u}{\tau _{i+p+1}-\tau _{i+1}}}\,N_{i+1,p,\tau }(u)

.

Die Elemente des Knotenvektors heißen auch Knotenpunkte (im engl. breakpoints) und müssen die Bedingungen $\tau _{i}\leq \tau _{i+1}{\mbox{ und }}\tau _{i}<\tau _{i+p}$ 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,\tau }(u)\geq 0$
Lokaler Träger: $N_{i,p,\tau }(u)=0{\mbox{ falls }}u\not \in [\tau _{i},\tau _{i+p}]$
Zerlegung der Eins: $\sum _{i=0}^{n}N_{i,p,\tau }(u)=1,u\in [\tau _{p},\tau _{n-p+1}]$

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.

Mathematische Definition: Kurve

Eine B-Spline-Kurve $C(u),\ u\in [\tau _{p},\tau _{n-p+1}]$ der Ordnung $p$ mit Knotenvektor $\tau$ (s.o.) und Kontrollpunkten $P_{i}\ (i=1,\ldots ,n-p)$ (auch De Boor Punkte genannt) wird definiert durch

$C(u)=\sum _{i=1}^{n-p}\;P_{i}\,N_{i,p,\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 $[\tau _{i},\tau _{i+p}]$

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

Mathematische Definition: Fläche

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

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

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

Eigenschaften

Lokalität: Der Kontrollpunkt $P_{ij}$ beeinflusst die Fläche nur im Rechteck $[\tau _{i},\tau _{i+p}]\times [\mu _{j},\mu _{j+q}]$

Endpunktinterpolation: Werden die ersten $p$ Knotenpunkte in $\tau$ auf den gleichen Wert gesetz, die letzten $p$ Knotenpunkte in $\tau$ auf den gleichen Wert gesetz, die ersten $q$ Knotenpunkte in $\mu$ auf den gleichen Wert gesetz und die letzten $q$ Knotenpunkte in $\mu$ auf den gleichen Wert gesetz dann gilt die Endpunktinterpolation, d.h. $P_{1,1}=C(\tau _{p},\mu _{q})$ , $P_{1,m-q}=C(\tau _{p},\mu _{m-q+1})$ , $P_{n-p,1}=C(\tau _{n-p+1},\mu _{q})$ und $P_{n-p,m-q}=C(\tau _{n-p+1},\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

Siehe auch