Splines

474_Spline_interpolation.png
Beispiel eines Splines mit 8 Knoten
Ein Spline nn-ten Grades ist eine Funktion, die stückweise aus Polynomen mit maximalem Grad nn zusammengesetzt ist. Dabei werden an den Stellen, an denen zwei Polynomstücke zusammenstoßen (man spricht auch von Knoten) bestimmte Bedingungen gestellt, etwa dass der Spline (n−1n-1) mal stetig differenzierbar ist.
Splines werden vor allem zur Interpolation und Approximation benutzt. Durch die stückweise Definition vermeidet man die starke Oszillation von Polynomen höheren Grades und deren Unbeschränktheit, die bei der Polynominterpolation entstehen können (Runges Phänomen).
Handelt es sich bei dem Spline um eine stückweise lineare Funktion, so nennt man den Spline linear (es handelt sich dann um einen Polygonzug), analog gibt es quadratische, kubische usw. Splines.
 
 

B-Splines

Für eine numerisch stabile Spline-Interpolation haben sich die sogenannten B-Splines als Basisfunktionen bewährt.

Definition

Die B-Spline-Basisfunktionen Ni,p,τ (i=1,…,n−p)N_{i,p,\tau}\ (i=1,\ldots,n-p) der Ordnung pp mit Knotenvektor τ=(τ1,…,τn)\tau = (\tau_1,\ldots,\tau_n) (n≥2 p) (n\ge 2\,p) werden durch die folgende Rekursionsformel von de Boor/Cox/Mansfield definiert:
Ni,1,τ(u)={1,u∈[τi,τi+1]0,sonstN_{i,1,\tau}(u) = \begin{cases} 1, & u\in\left[\tau_i,\tau_{i+1}\right] \\ 0, & \text{sonst} \end{cases}
und
Ni,p+1,τ(u)=u−τiτi+p−τi Ni,p,τ(u)  +  τi+p+1−uτi+p+1−τi+1 Ni+1,p,τ(u)N_{i,p+1,\tau}(u) = \dfrac{u-\tau_{i}}{\tau_{i+p}-\tau_{i}}\,N_{i,p,\tau}(u) \;+\; \dfrac{\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 τi≤τi+1\tau_{i}\le\tau_{i+1} und τi<τi+p\tau_{i} < \tau_{i+p} erfüllen.

Eigenschaften

  • Nicht-Negativität: Ni,p,τ(u)≥0N_{i,p,\tau}(u)\ge 0
  • Lokaler Träger: Ni,p,τ(u)=0N_{i,p,\tau}(u)= 0 falls u∉[τi,τi+p] u\notin [\tau_{i},\tau_{i+p}]
  • Zerlegung der Eins: ∑i=0n−pNi,p,τ(u)=1\sum\limits_{i=0}^{n-p} N_{i,p,\tau}(u) = 1, u∈[τp,τn−p+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)C(u), u∈[τp,τn−p+1]u\in [\tau_{p},\tau_{n-p+1}] der Ordnung pp mit Knotenvektor τ\tau und Kontrollpunkten Pi (i=1,…,n−p)P_i\ (i=1,\ldots,n-p) (auch De-Boor-Punkte genannt) wird definiert durch
C(u)=∑i=1n−p  Pi Ni,p,τ(u)C(u) = \sum\limits_{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 PiP_i beeinflusst die Kurve nur im Intervall [τi,τi+p][\tau_{i},\tau_{i+p}]
  • Endpunkt-Interpolation: Es ist P1=C(τp)P_1 = C(\tau_{p}), falls der erste Knotenpunkt pp-mal wiederholt wird und Pn−p=C(τn−p+1)P_{n-p} = C(\tau_{n-p+1}), falls der letzte Knotenpunkt pp-mal wiederholt wird.

Definition einer B-Spline-Fläche

Eine B-Spline-Fläche der Ordnung pp und qq mit Knotenvektor τ=(τ1,…,τn)\tau = (\tau_{1},\ldots,\tau_{n}) (n≥2p)(n\ge 2p) und μ=(μ1,…,μm)\mu = (\mu_{1},\ldots,\mu_{m}) (m≥2q)(m\ge 2q) und Kontrollpunkten (bzw. De Boor Punkten) PijP_{ij} wird definiert durch
C(u,v)=∑i=1n−p∑j=1m−q  Pij Ni,p,τ(u) Nj,q,μ(v)C(u,v) = \sum\limits_{i=1}^{n-p} \sum\limits_{j=1}^{m-q}\; P_{ij}\,N_{i,p,\tau}(u)\,N_{j,q,\mu}(v)
Die Fläche ist definiert über dem Rechteck [τp,τn−p+1]×[μq,μm−q+1][\tau_{p},\tau_{n-p+1}] \times [\mu_{q},\mu_{m-q+1}].
Eigenschaften:
  • Lokalität: Der Kontrollpunkt PijP_{ij} beeinflusst die Fläche nur im Rechteck [τi,τi+p]×[μj,μj+q][\tau_{i},\tau_{i+p}]\times [\mu_{j},\mu_{j+q}]
  • Endpunktinterpolation: Werden die ersten pp Knotenpunkte in τ\tau auf den gleichen Wert gesetzt, die letzten pp Knotenpunkte in τ\tau auf den gleichen Wert gesetzt, die ersten qq Knotenpunkte in μ\mu auf den gleichen Wert gesetzt und die letzten qq Knotenpunkte in μ\mu auf den gleichen Wert gesetzt, dann gilt die Endpunktinterpolation, d. h. P1,1=C(τp,μq), P1,m−q=C(τp,μm−q+1), Pn−p,1=C(τn−p+1,μq)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 Pn−p,m−q=C(τn−p+1,μm−q+1)P_{n-p,m-q}=C(\tau_{n-p+1},\mu_{m-q+1})

Wir Mathematiker sind die wahren Dichter, nur müssen wir das, was unsere Phantasie schafft, noch beweisen.

Leopold Kronecker

Copyright- und Lizenzinformationen: Diese Seite basiert dem Artikel Spline aus der frеiеn Enzyklοpädιe Wιkιpеdιa und stеht unter der Dοppellizеnz GNU-Lιzenz für freie Dokumentation und Crеative Commons CC-BY-SA 3.0 Unportеd (Kurzfassung). In der Wιkιpеdιa ist eine Listе dеr Autorеn des Originalartikels verfügbar. Da der Artikel geändert wurde, reicht die Angabe dieser Liste für eine lizenzkonforme Weiternutzung nicht aus!
Anbieterkеnnzeichnung: Mathеpеdιa von Тhοmas Stеιnfеld  • Dοrfplatz 25  •  17237 Blankеnsее  • Tel.: 01734332309 (Vodafone/D2)  •  Email: cο@maτhepedιa.dе
Datenschutzerklärung

 

Interpolation