Spline

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.

Datei:Spline interpolation.png

Beispiel eines Splines

Splines werden vor allem zur Interpolation benutzt, wo dann an den Verklebungsstellen Bedingungen gestellt werden, etwa das 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), 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.

Siehe auch: Faltung (Mathematik)

Definition eines B-Splines

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 definiert durch die Rekursionsformel von de Boor/Cox/Mansfield:

$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.

Definition einer B-Spline-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.

Definition einer B-Spline-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

Weblinks

• Java-Applet zum Berechnen von kubischen Splines