Spline

Från Wikipedia
Hoppa till: navigering, sök

Spline är ett begrepp inom numerisk analys.

En kontinuerlig funktion f säges vara en spline om den är styckvis polynom och har kontinuerlig förstaderivata. Särskilt vanliga är kubiska splines, dvs funktioner som är styckvis polynom av grad högst tre.

kvadratisk spline med 6 noder i rött

Allmänt[redigera | redigera wikitext]

Splines används framförallt för approximering inom analysen. Approximation med hjälp av polynom sker antingen genom att höja polynomets gradtal dvs. exponenten, eller genom att dela in funktionen i mindre intervall. Splines utnyttjar den senare varianten. Styckvis polynom av bestämd grad med en kontinuerlig förstaderivata delas in på intervall som tillsammans ger en kontinuerlig kurva. Med detta tillvägagångssätt måste visserligen beaktas vilket intervall som varje polynom är bestämt på, men fördelen är att polynomen förblir av låg grad. På så sätt kan vi använda oss av simpla matematiska metoder så som interpolation mellan noder för att bestämma polynomen på varje enskilt delintervall. Ytterligare en fördel är att avvikelser på något av polynomet endast påverkar hela funktionen lokalt och inte globalt eftersom den bara definieras på ett visst intervall.[1]

Ordet spline härstammar från skeppsbygget där tunna elastiska material med en skåra (på engelska så kallade “splines”) användes vid planritningar och modellbygge. Dessa kunde böjas efter speciella vikter för att skapa kontinuerliga kurvor som användes som underlag för planritningar och till modellbygget. Spline-funktionen infördes för första gången av Schoenberg.[2]

Definition[redigera | redigera wikitext]

Om x1, x2, ... ,xn är en strängt växande serie nummer och om x1, x2, ... ,xn är noderna, har en spline-funktion S(x) följande egenskaper:

  1. På varje intervall (xi,xi+1) för i = 0,1, ... ,n bestäms S(x) av ett polynom med grad m eller lägre
  2. S(x) och dess derivata av grad 1,2, ... , m-1 är kontinuerliga på hela intervallet för S(x)[3]

Varianter[redigera | redigera wikitext]

Kubiska splines[redigera | redigera wikitext]

Kubiska splines är en av de mest använda formen av splines. Den utgörs av polynom av högst tredje graden, vilket innebär att den är både lätthanterlig och ger en relativt exakt approximation samt en jämn, slät kurva.

B-splines[redigera | redigera wikitext]

B-spline är en förkortning för bas-spline och beskriver en spline som inte nödvändigtvis måste gå genom noderna utan som kan approximeras så att funktionen går igenom gränspunkterna men inte punkterna däremellan.[4]

Exempel[redigera | redigera wikitext]

Konstruera en kubisk spline S(x) som går igenom punkterna [5]

 (3,6) (5,1) (7,4)

och slutar vid intervallgränserna.


Det kommer att behövas 2 delintervall och därmed 2 polynom p1 och p2:


 p_1(x) = a_1 + b_1(x-3)+c_1(x-3)^2+d_1(x-3)^3

p_2(x) = a_2 + b_2(x-5)+c_2(x-5)^2+d_2(x-5)^3



Detta ger 8 obekanta, vilket innebär att 8 ekvationer behövs för att lösa ekvationssystemet.

Splinen måste stämma överens med funktionerna i noderna vilket ger:


 
6=p_1(3)=a_1

1=p_1(5)=a_1 +2b_1+4c_1+8d_1

1=p_2(5)=a_2

4=p_2(7)=a_2+2b_2+4c_2+8d_2


Dessutom måste första och andra derivatan av p1 och p2 stämma överens med den gemensamma noden x=5:


 
p'_{1}\left( x \right)=b_{1}+2c_{1}\left( x-3 \right)+3d_{1}\left( x-3 \right)^{2}

p'_2(x)=b_2+2c_2(x-5)+3d_2(x-5)^2


p_1''(x)=2c_1+6d_1(x-3)

p_2''(x)=2c_2+6d_2(x-5)



p_1'(5)=b_1+4c_1+12d_1=b_2=p_2'(5)

p_1''(5)=2c_1+12d_1=2c_2=p_2''(5)



De 2 sista ekvationerna fås av punkterna som utgör intervallgränserna, där funktionernas andraderivata kan användas:



p_1'' (3)= 0 = 2c_1

p_2'' (7)= 0 = 2c_2+12d_2


Tillsammans bildar de 8 ekvationerna följande ekvationssystem:



6=a_1

1=a_1+2b_1+4c_1+8d_1

1=a_2

4=a_2+2b_2+4c_2+8d_2

0=b_1+4c_1+12d_1-b_2

0=2c_1+12d_1-2c_2

0=2c_1

0=2c_2+12d_2


Svaret blir:


En kubisk spline med noderna i blått (ur Exempel)


a_1=6

b_1=-\frac{7}{2}

c_1=0

d_1=\frac{1}{4}

a_2=1

b_2=-\frac{1}{2}

c_2=\frac{3}{2}

d_2=-\frac{1}{4}


Vilket resulterar i:



S(x)=\left\{\begin{matrix}
6-\frac{7}{2}(x-3)+\frac{1}{4}(x-3)^3, 3 \le x \le 5\\ 1-\frac{1}{2}(x-5)+\frac{3}{2}(x-5)^2-\frac{1}{4}(x-5)^3, 5 \le x \le 7\end{matrix}\right.

Referenser[redigera | redigera wikitext]

  1. ^ Davidson, Kenneth och Donsig, Allan “Real Analysis and Applications - Theory in Practice” Springer-Verlag, ISBN 978-0-387-98097-3
  2. ^ Schumaker, Larry “Spline Functions: Basic Theory” Cambridge University Press
  3. ^ Greville, T “Theory and Applications of Spline Functions” Academic Press, 1969
  4. ^ Van Verth, James och Bishop, Lars “Essential Mathematics for Games and Interactive Applications: A Programmer’s Guide” Morgan Kaufmann
  5. ^ Buchanan, Robert “Cubic Spline Interpolation: MATH 375, Numerical Analysis” 2010