Spline Interpolation 的數學概念

        Spline Interpolation演算法，其精神就是在兩相鄰點間，找出一合理的三次多項式。在給定的Ｎ個座標點（Ｘ1,Ｙ1）、（Ｘ2,Ｙ2）、…、（ＸN,ＹN），（Ｘ1,Ｙ1）和（Ｘ2,Ｙ2）間的多項式記作S1，（Ｘ2,Ｙ2）和（Ｘ3,Ｙ3）間的多項式記作Ｓ2，……，（ＸN-1,ＹN-1）和（ＸN,ＹN）間的多項式記作ＳN-1。即在（Ｘi,Ｙi）和（Ｘi+1,Ｙi+1）間，找出

Ｓi(X)＝ａiＸ^3+ｂiＸ^2+ｃiＸ+ｄi，i=1∼N-1。

        每兩個相鄰點就有一個多項式，每個多項式有a、b、c、d4個未知數，共有N-1道多項式，所以共4N-4個未知數。我們只要把這4N-4個未知數求出來即大功告成。

1.曲線必通過座標點

Ｓi(Xi)＝Ｙi，Ｓi(Xi+1)＝Ｙi+1，i=1∼N-1。

共2N-2個式子。

2.曲線的銜接點必須平滑，及一階導函數和二階導函數值相等。

Ｓ'i-1(Xi)＝Ｓ'i(Xi)，i=2∼N-1。

Ｓ''i-1(Xi)＝Ｓ''i(Xi)，i=2∼N-1。

共2N-4個式子。

3.兩端點的二階導函數給定初值

        給定初值的方法很多，我們採用natural spline的方式，令Ｓ''1(X1)＝0，Ｓ''N-1(XN)＝0。共2個式子。

　

        由以上1、2、3我們可得到4N-4個式子，即可求出全部的4N-4個變數。在此，我們不直接解方程式，而改用比較有效率的方法。假設所有的二階導函數在銜接點的值為已知，以Ｐi(i=2∼N-1)表示，則前面2、3可以改成

Ｓ''i-1(Xi)＝Ｓ''i(Xi)，i=2∼N-1。

Ｐ1＝ＰN＝0

對兩個相鄰點而言，

Ｓi(Xi)＝Ｙi

Ｓi(Xi+1)＝Ｙi+1

Ｓ''i(Xi)＝Ｐi

Ｓ''i(Xi+1)＝Ｐi+1

所以我們只要把Ｐ2∼ＰN-1求出來就可以了。我們先對Ｓ''i做變數轉換，令ｔ＝(X-Xi)/(Xi+1-Xi)，則

Ｓi(t) ＝  tＹi+1  +  (1-t)Ｙi  +  (Xi+1-Xi)^2  ×〔(t^3-t)Ｐi+1 + ((1-t)^3-(1-t)) ×Ｐi〕/ 6

　

Ｓ'i(t) ＝ Zi + (Xi+1-Xi)〔(3t^2-1)Ｐi+1 + (1-3(1-t)^2)Ｐi〕/ 6   －－ヾ

其中Zi ＝(Ｙi+1  - Ｙi ) / (Ｘi+1-Ｘi)。

又Ｓ'i-1(1) ＝Ｓ'i(0) ，∴ヾ式可化成

(Xi-Xi-1)Ｐi-1+2 * (Xi+1-Xi-1)Ｐi + (Xi+1-Xi)Ｐi+1 ＝ 6 * (Zi-Zi-1)   －－ゝ

ゝ式可再化簡成

Ｕi-1Ｐi-1＋ｄiＰi＋ＵiＰi+1＝Ｗi，i=2∼N-1。   －－ゞ

這是一個聯立方程組，寫成矩陣後會變成所謂的『tridiagonal matrix』

   ＝

再利用高斯消去法，即可求得 P2P3…PN-1之值。如此即可求得相鄰點間的三次曲線函數。