Spline-Räume - B-Spline-Basen - igpm.rwth-aachen.de · Einige Grundbegri e Splines sind st uckweise Polynome, die eine Kurve anhand gegebener Daten approximieren oder interpolieren

Spline-Raume - B-Spline-Basen

Rene Janssens

4. November 2009

Rene Janssens () Spline-Raume - B-Spline-Basen 4. November 2009 1 / 56

Ubersicht

1 Erster Abschnitt: Raume von SplinefunktionenGrundlegende EigenschaftenEine erste Basis

2 Zweiter Abschnitt: B-SplinesRekursionsformeln fur B-SplinesLinearkombinationen von B-SplinesReproduktion von Polynomen


Einige Grundbegriffe

Splines sind stuckweise Polynome, die eine Kurve anhand gegebenerDaten approximieren oder interpolieren sollen und gewisseGlattheitsbedingungen erfullen.

Die Bruchstellen ξ = (ξ0, . . . , ξl) sind die Punkte, anhand derer derSpline bestimmt werden soll.

Der”Glattheitsvektor“ µ = (µ0, . . . , µl)

T regelt, wie”glatt“ ein

Stuck der Kurve in das nachste ubergehen muss, wobei ein hohererWert eine niedrigere Glattheit bedeutet mit 1 ≤ µj ≤ k − 1 ,j = 1, . . . , l und µ0 = µl = 0.


Definition: Spline-Raum

(1.1) Definition: Spline-Raum

Der Raum der Splines der Ordnung k mit Bruchstellen ξ = (ξ0, . . . , ξl+1)und Glattheit µ ist folgendermaßen definiert:

Πk,µ,ξ := {f : [a, b]→ R |f |(ξj ,ξj+1) ∈ Πk−1, j = 0, . . . , l

, f ∈ C k−1−µj (ξj−1, ξj+1), j = 1, . . . , l}


Definition: Abgebrochene Potenz

(1.2)Definition: Abgebrochene Potenz

Eine abgebrochene Potenz ist definiert durch

(·)m+ : R→ R ; xm

+ =

{xm, wenn x ≥ 0,0, sonst.


Grundlegende Eigenschaften

(1.3)Bemerkung: Grundlegende Eigenschaften

(i) Πk,µ,ξ ist ein linearer Raum.

(ii) Πk−1 ⊆ Πk,µ,ξ

(iii) (x − ξj)m+ ∈ Πk,µ,ξ fur k − µj ≤ m ≤ k − 1

(iv) dim Πk,µ,ξ = k +∑l

j=1 µj


Eine erste Basis

(1.4)Satz: Eine erste Basis

Die Monome und abgebrochenenen Potenzen bilden eine Basis desSplineraums Πk,µ,ξ mit Koeffizienten aj und cjm aus R.Jedes S ∈ Πk,µ,ξ besitzt die eindeutige Darstellung

S(x) =k−1∑j=0

ajxj +

l∑j=1

k−1∑m=k−µj

cjm(x − ξj)m+


Veranschaulichung: B-Splines als Basis

Abbildung: S(x) = −1 + x +∑4

j=1(−1)j(x − j)+ und

S(x) = −1 + 2x +∑4

j=1(−1)j(x − j)+



Abbildung: S(x) = −1 + x − (x − 0.5)+ + (x − 0.501)+ undS(x) = −1 + x − 10(x − 0.5)+ + 10(x − 0.501)+


Die dividierten Differenzen

(2.1)Bemerkung: Eigenschaften der div. Differenzen

Die dividierten Differenzen zu den Stutzstellen x0 ≤ · · · ≤ xn zu einerFunktion f ∈ Cn(R) besitzen folgende Eigenschaften:

(i) [x0, . . . , xn]P = 0 fur alle P ∈ Πn−1.

(ii) Sei π : {0, . . . , n} → {0, . . . , n} eine beliebige Permutation. Dann gilt[x0, . . . , xn]f = [xπ(0), . . . , xπ(n)]f fur alle f ∈ Cn(R).

(iii) Fur xi 6= xj gilt folgende Rekursionsformel

[x0, . . . , xn]f =[x0, . . . , xi−1, xi+1, . . . , xn]f − [x0, . . . , xj−1, xj+1, . . . , xn]f

xj − xi



(2.1)Bemerkung: Eigenschaften der div. Differenzen (Forts.)

(iv) Fur jedes f ∈ Cn(R) gilt

[x0, . . . , xn]f =

∫Σn

f (n)(λ0x0 + · · ·+ λnxn)dλ1 . . . dλn

wobei Σn := {(λ0, . . . , λn)T :∑n

j=0 λj = 1 , λj ≥ 0 furj = 0, . . . , n} der n-dimensionale Standardsimplex ist.

(v) [x0, . . . , x0︸︷︷︸n+1

]f = f (n)(x0)n!

(vi) [x0, . . . , xn]f = f (n)(x)n! fur ein x ∈ [x0, . . . , xn] (konvexe Hulle der xi )



(2.1)Bemerkung: Eigenschaften der div. Differenzen (Forts.)

(vii) [x0, . . . , xn](fg) =∑n

j=0([x0, . . . , xj ]f )[xj , . . . , xn]g (Leibniz-Regel)

(viii) Fur x0 < · · · < xn gilt

[x0, . . . , xn]f =n∑

j=0

f (xj)∏ni=0i 6=j

xi − xj

(ix) Es existieren stets Konstanten αj = αj(x0, . . . , xn) mitdj = max{r ; xj = xj+r}, so dass gilt

[x0, . . . , xn]f =n∑

j=0

αj f(dj )(xj)



Beweis zu (2.1)

(iv) Beweis per vollstandiger Induktion:(IA): n=1:

[x0, x1]f =f (x1)− f (x0)

x1 − x0

=1

x1 − x0

∫ x1

x0

f ′(ξ)dξ

=

∫ 1

0f ′(x0 + t1(x1 − x0))dt1

(IV) Sei n ∈ N beliebig aber fest und es gelte die Beh. fur dieses.



Beweis zu (2.1) (Fortsetzung)

(IS) n→ n + 1

[x0, . . . , xn+1]f =[x1, . . . , xn+1]f − [x0, . . . , xn]f

xn+1 − x0

=[xn+1, x1, . . . , xn]f − [x0, . . . , xn]f

xn+1 − x0

=1

xn+1 − x0·

·∫ t1

0. . .

∫ tn−1

0(f (n)(t0xn+1 + t1x1 + · · ·+ tnxn)−

−f (n)(t0x0 + · · ·+ tnxn))dt1 . . . dtn




=1

xn+1 − x0·

·∫ t1

0. . .

∫ tn−1

0

∫ t0xn+1+···+tnxn

t0x0+···+tnxn

(f (n+1))(ξ)dξdt1 . . . dtn

=

∫Σn+1

(f (n+1)(t0x0 + · · ·+ tn+1xn+1)dt1 . . . dtn+1




(vii) Beweis per vollstandiger Induktion:(IA): n=1:

[x0, x1](fg) =(fg)(x1)− (fg)(x0)

x1 − x0

=f (x1)g(x1)− f (x0)g(x1) + f (x0)g(x1)− f (x0)g(x0)

x1 − x0

= [x0]f [x0, x1]g + [x0, x1]f [x1]g

(IV) Sei n ∈ N beliebig aber fest und es gelte die Beh. fur dieses.




(IS) n→ n + 1

[x0, . . . , xn+1](fg) =[x1, . . . , xn+1](fg)− [x0, . . . , xn](fg)

xn+1 − x0

=

∑n+1j=1 [x1, . . . , xj ]f [xj , . . . , xn+1]g

xn+1 − x0−

−∑n

j=0[x0, . . . , xj ]f [xj , . . . , xn]g

xn+1 − x0

=n∑

j=0

([x1, . . . , xj+1]f − [x0, . . . , xj ]f )

xn+1 − x0·

·[xj+1, . . . , xn+1]g +

+[x0, . . . , xj ]f ([xj+1, . . . , xn+1]g − [xj , . . . , xn]g)

xn+1 − x0




=n∑

j=0

(xj+1 − x0)[x0, . . . , xj+1]f [xj+1, . . . , xn+1]g

xn+1 − x0+

+[x0, . . . , xj ]f (xn+1 − xj)[xj , . . . , xn+1]g

xn+1 − x0

=n+1∑j=0

[x0, . . . , xj ]f [xj , . . . , xn+1]g ,


Definition: B-Splines

(2.2) Definition B-Splines

Teilfolgen der Folge (an)n∈N sind Sei xi , . . . , xi+k mit xi < xi+k eineAnordnung von Knoten, dann definiere

Ni ,k(t) := (xi+k − xi )[xi , . . . , xi+k ](· − t)k−1+

als den B-Spline k-ter Ordnung bezuglich xi , . . . , xi+k .


Veranschaulichung: B-Splines

Abbildung: B-Splines der Ordnung 1-3


Eigenschaften der B-Splines

(2.3) Bemerkung: B-Spline Eigenschaften

Die B-Splines besitzen folgende Eigenschaften:

(i) supp Ni ,k ⊆ [xi , xi+k ], d.h. Ni ,k(t) = 0 fur t /∈ [xi , xi+k ].

(ii) Ni ,k ist ein stuckweises Polynome vom Grad hochstens k − 1.Genauer: ist xi−1 < xi = · · · = xi+d < xi+d+1, so gilt

Ni ,k ∈ C k−2−d(xi−1, xi+d+1) .

Speziell ist Ni ,k ∈ C k−2(xi−1, xi+1), falls xi−1 < xi < xi+1.


Alternative Charakterisierung der B-Splines

(2.4) Gleichung

Es gilt

1

(k − 1)!

∫ ∞−∞

Ni,k(ξ)f (ξ)dξ = (xi+k − xi )

∫Σn

f (λ0xi + · · ·+ λkxi+k)dλ1 . . . dλk

fur alle f ∈ C k(R).



Herleitung zu 2.4

f (x) =k−1∑j=0

(x − xi )j

j!f (j)(xi ) +

1

(k − 1)!

∫ ∞xi

(x − ξ)k−1+ f (k)(ξ)dξ

[xi , . . . , xi+k ]f (x) =1

(k − 1)!

∫ ∞xi

[xi , . . . , xi+k ](· − ξ)k−1+ f (k)(ξ)dξ

=1

(k − 1)!(xi+k − xi )

∫ ∞xi

Ni ,k(ξ)f (k)(ξ)dξ



Herleitung zu 2.4 (Fortsetzung)

⇒ (xi+k − xi )[xi , . . . , xi+k ]f (x) =1

(k − 1)!

∫ ∞−∞

Ni ,k(ξ)f (k)(ξ)dξ

1

(k − 1)!

∫ ∞−∞

Ni ,k(ξ)f (k)(ξ)dξ = (xi+k − xi ) ·

·∫

Σn

f (k)(λ0xi + · · ·+

+λkxi+k)dλ1 . . . dλk


Nicht-Negativitat der B-Splines

(2.5) Bemerkung: Nicht-Negativitat der B-Splines

Die B-Splines sind nicht-negativ, d.h. Ni ,k(x) ≥ 0 fur alle x ∈ R.


Rekursionsformel zur Ableitung eines B-Splines

(2.6) Gleichung: Rekursionsformel zur Ableitung eines B-Splines

Fur die erste Ableitung des B-Splines k-ter Ordnung zu den Knotenxi , . . . , xi+k gilt

Ni ,k(x) = (k − 1)

(Ni ,k−1(x)

xi+k−1 − xi−

Ni+1,k−1(x)

xi+k − xi+1

).


Rekursionsformel zur Ableitung eines B-Splines

Beweis zu (2.6)

Ni ,k(x) = −(k − 1)(xi+k − xi )[xi , . . . , xi+k ](· − x)k−2+

= −(k − 1)(xi+k − xi )

([xi+1,...,xi+k ](·−x)k−2

+ −[xi ,...,xi+k−1](·−x)k−2+

xi+k−xi

)= (k − 1)

(Ni,k−1(x)xi+k−1−xi

− Ni+1,k−1(x)xi+k−xi+1

)


Rekursionsformel zur Auswertug eines B-Splines

(2.7) Gleichung: Rekursionsformel zur Auswertung eines B-Splines

Fur den B-Spline k-ter Ordnung zu den Knoten xi , . . . , xi+k gilt

Ni ,k(x) =x − xi

xi+k−1 − xiNi ,k−1(x) +

xi+k − x

xi+k − xi+1Ni+1,k−1(x).


Rekursionsformel zur Auswertung eines B-Splines

Beweis zu (2.7)

Ni ,k(x) = (xi+k − xi )[xi , . . . , xi+k ](· − x)k−1+

= (xi+k − xi )[xi , . . . , xi+k ]((· − x)k−2+ (· − x))

= (xi+k − xi )((xi − x)[xi , . . . , xi+k ](· − x)k−2+ +

+[xi , xi+1](· − x)[xi+1, . . . , xi+k ](· − x)k−2+ )


Rekursionsformel zur Auswertung eines B-Splines


Ni ,k(x) = (xi+k − xi )

((xi − x)

[xi , . . . , xi+k−1](· − x)k−2+

xi − xi+k−

−[xi+1, . . . , xi+k ](· − x)k−2

+

xi − xi+k+

1

xi+k − xi+1Ni+1,k−1(x)

)=

x − xi

xi+k−1 − xiNi ,k−1(x) +

xi − x + xi+k − xi


⇒ Ni ,k(x) =x − xi

xi+k−1 − xiNi ,k−1(x) +

xi+k − x



Rekursionsformeln fur B-Splines

(2.8) Beispiel

Sei xi = 0, xi+1 = 0, xi+2 = 2. Bestimme Ni ,2(1) und Ni ,2(1) zu diesenKnoten.

Ni ,2(1) =1− 0

0− 0Ni ,1(1) +

2− 1

2− 0Ni+1,1(1) =

1

2χ[0,2)(1) =

1

2

Ni ,2(1) = (2− 1)Ni+1,k−1(1)

2− 0=

1

2


Definition: Sk(T )

(2.9) Definition: Sk(T )

SeiT := {xi}n+k

i=1 , xi < xi+k fur i = 1, . . . , n

x1 = · · · = xk = a < xk+1 ≤ · · · ≤ xn < b = xn+1 = · · · = xn+k .

Wir definieren den Raum Sk(T ) als das lineare Erzeugnis der B-Splinesk-ter Ordnung auf T:

Sk(T ) := span {Ni ,k : i = 1, . . . , n}


Gleichungen

(2.10) Gleichung

Es gilt fur S ∈ Sk(T )

S(x) =n∑

i=1

ciNi ,k(x)

und insbesondere wegen der Lokalitat der B-Splines

S(x) =

j∑i=j−k+1

ciNi ,k(x) , x ∈ [xj , xj+1).


Gleichungen

(2.11) Gleichung

Es gilt fur die l-te Ableitung von S

S (l)(x) = (k − 1) . . . (k − l)n∑

i=l+1

c(l)i Ni ,k−l(x)

mit

c(l)i =

{ci fur l = 0c

(l−1)i −c

(l−1)i

xi+k−l−xifur l > 0


Gleichungen

Herleitung zu (2.11)

S (l)(x) = (k − 1) . . . (k − l + 1)n∑

i=l

c(l−1)i Ni ,k−l+1(x)

= (k − 1) . . . (k − l)n∑

i=l

c(l−1)i

(Ni ,k−l(x)

xi+k−l − xi−

Ni+1,k−l(x)

xi+k−l+1 − xi+1

)

= (k − 1) . . . (k − l)n∑

i=l+1

c(l−1)i − c

(l−1)i−1

xi+k−l − xiNi ,k−l(x)

= (k − 1) . . . (k − l)n∑

i=l+1

c(l)i Ni ,k−l(x)


Gleichungen

(2.12) Gleichung

Es gilt fur l ≤ k − 1

S(x) =n∑

i=1+l

c[l ]i Ni ,k−l(x)

mit

c[l ]i =

ci fur l = 0

x−xixi+k−l−xi

c[l−1]i (x) +

xi+k−l−xxi+k−l−xi

c[l−1]i−1 (x) fur l > 0

0 fur xi+k−l = xi


Gleichungen

Herleitung zu (2.12)

S(x) =n∑

i=l

c[l−1]i Ni ,k−l+1(x)

=n∑

i=l

c[l−1]i

(x − xi

xi+k−l − xiNi ,k−l(x) +

xi+k−l+1 − x

xi+k−l+1 − xi+1Ni+1,k−l(x)

)

=n∑

i=l+1

(x − xi

xi+k−l − xic

[l−1]i (x) +

xi+k−l − x

xi+k−l − xic

[l−1]i−1 (x)

)Ni ,k−l

=n∑

i=l+1

c[l ]i Ni ,k−l(x)


Gleichungen

(2.13) Gleichung

Fur l = k − 1 in der letzten Rekursionsformel gilt wegen der Lokalitat derB-Splines

S(x) = c[k−1]i (x).


Ein N-A-artiges Schema

(2.14) Ein N-A-artiges Schema

Zur Berechnung der c[k−1]i (x) bietet sich also an:

cj−k+1

↘cj−k+2 → c

[1]j−k+2(x)

↘ ↘cj−k+3 → c

[1]j−k+3(x) → c

[2]j−k+3(x)

......

.... . .

cj → c[1]j (x) → c

[2]j (x) . . . c

[k−1]j (x)



(2.15) Beispiel

Sei k = 5 und T := {xi}13i=1 mit

x1 = · · · = x5 = 0 , x6 = 0, 2 , x7 = 0, 6 , x8 = 0, 9 , 1 = x9 = · · · = x13.Weiter seiS(x) = N4,5(x) + 4N5,5(x) + 3N6,5(x) + N7,5(x) + 8N8,5(x) + . . ..Bestimme S(0, 95).



(2.15) Beispiel (Fortsetzung)

1↘

4 → 0,951 4 + 1−0,95

1 = 3, 85↘ ↘

3 → 3, 0625 → 3, 112↘ ↘ ↘

1 → 1, 25 → 1, 477 → 1, 681↘ ↘ ↘ ↘

8 → 4, 5 → 2, 875 → 2, 176 → 1, 929


Marsden-Identitat

(2.16) Marsden-Identitat

Es gilt fur alle x ∈ [a, b) , σ ∈ R

(x − σ)k−1 =n∑

i=1

k−1∏j=1

(xi+j − σ)Ni ,k(x)

=n∑

i=1

ϕi ,k(σ)Ni ,k(x)

mit

ϕi ,k(x) :=k−1∏j=1

(xi+j − σ).


Marsden-Identitat

Beweis zu (2.16)

per Induktion nach k : Fur k = 1 ist (x − σ)0 = 1 =∑n

i=1 1 · Ni ,1(x) wahrnach Definition. Annahme: Die Behauptung gilt bereits fur l ≤ k − 1 undwir zeigen, dass sie dann auch fur l = k gilt

n∑i=1

ϕi ,k(σ)Ni ,k(x) =n∑

i=2

(x − xi

xi+k−1 − xiϕi ,k(σ)+

+xi+k−1 − x

xi+k−1 − xiϕi−1,k(σ)

)Ni ,k−1(x)

=n∑

i=2

x − xi

xi+k−1 − xi

k−1∏j=1

(xi+j − σ)+

+xi+k−1 − x

xi+k−1 − xi

k−1∏j=1

(xi−1+j − σ)

Ni ,k−1(x)


Marsden-Identitat

Beweis zu (2.16)

=n∑

i=2

k−2∏j=1

(xi+j − σ)

(x − xi

xi+k−1 − xi(xi+k−1 − σ)+

+xi+k−1 − x

xi+k−1 − xi(xi − σ)

)Ni ,k−1(x)

= (x − σ)n∑

i=2

ϕi ,k−1(σ)Ni ,k−1(x)

= (x − σ)(x − σ)k−2

= (x − σ)k−1

nach Induktionsannahme. Also ergibt sich die Behauptung.


B-Splines und Polynome

(2.17) Korollar

Der Raum der Polynome vom Grad k − 1 auf [a, b] ist in dem von denB-Splines aufgespannten Raum enthalten

Πk−1[a, b] ⊆ Sk(T ).



Beweis zu (2.17)

Mit der Marsden-Identitat gilt

n∑i=1

ϕ(l)i ,k(0)Ni ,k(x) =

(ddσ

)l

(x−σ)k−1|σ=0 = (k−1) . . . (k−l)xk−l−1(−1)l

⇒ (k − 1) . . . (k − l)xk−l−1(−1)l =n∑

i=1

ϕ(l)i ,k(0)Ni ,k(x)

⇒n∑

i=1

(−1)k−m−1

(k − 1) . . . (m + 1)ϕ

(k−m−1)i ,k (0)Ni ,k(x) = xm

fur m = k − l − 1 mit l ≤ k − 1, also 0 ≤ m ≤ k − 1.


Zerlegung der Eins

(2.18) Korollar: Zerlegung der Eins

Mit x ∈ R bilden die B-Splines eine Zerlegung der Eins

n∑i=1

Ni ,k(x) = 1 .

Beweis zu (2.18)

Mit

(−1)k−1

(k − 1)!ϕ

(k−1)i ,k (0) =

(−1)k−1

(k − 1)!((−1)k−1σk−1 + . . . )(k−1) = 1

eingesetzt in die Darstellung der Monome aus dem Beweis zu Korollar(2.17) fur m = 0 folgt die Behauptung.



(2.19) Satz

Die Ni ,k sind lokal linear unabhangig, d.h gilt

n∑i=1

ciNi ,k(x) = 0 fur x ∈ (c , d) ⊆ [a, b] ,

dann folgtci = 0 falls (c , d) ∩ (xi , xi+k) 6= ∅ .



Beweis zu (2.19)

(c , d) enthalte keine Knoten.

Polynome vom Grad kleiner k lassen sich durch B-Splines darstellenauf (c , d).

Es verschwinden alle B-Splines auf (c, d) bis auf k Stuck.


B-Splines als Basis

(2.20) Satz

Betrachtea = ξ0 < · · · < ξl+1 = b

mit”Glattheitsvektor“ µ = (µ1, . . . , µl)

T , µj ≤ k − 1 und erweiterterKnotenfolge T gemaß

x1 = · · · = xk = ξ0 , xk+1 = · · · = xk+µ1 =

= ξ1 , . . . , xk+µ1+···+µl +1 = · · · = x2k+µ1+···+µl= ξl+1

Dann giltΠk,µ,ξ = Sk(T ) ,

d.h. die B-Splines der Ordnung k spannen den Raum der Splines Πk,µ,ξ auf.


Grundlegende Eigenschaften (Wiederholung)

(1.3)Bemerkung: Grundlegende Eigenschaften

Fur den Raum der Splines der k-ten Ordnung gilt

(iv) dim Πk.µ,ξ = k +∑l

j=1 µj .


B-Splines als Basis

Beweis zu (2.20)

Die B-Splines sind im Raum der Splines enthalten.

dim Sk(T ) =dim Πk,µ,ξ.



Abbildung: Veranderung der Kurven bei Veranderung der Koeffizienten in derB-Spline-Basis



Abbildung: Die eingebaute Glattheit


Documents

Spline-Räume - B-Spline-Basen - igpm.rwth-aachen.de · Einige Grundbegri e Splines sind st uckweise Polynome, die eine Kurve anhand gegebener Daten approximieren oder interpolieren