樣條插值

在數值分析這個數學分支中，樣條插值是使用一種名為樣條的特殊分段多項式進行插值的形式。由於樣條插值可以使用低階多項式樣條實現較小的插值誤差，這樣就避免了使用高階多項式所出現的龍格現象，所以樣條插值得到了流行。

樣條插值

使用多項式插值，對給定數據集進行插值的n階多項式就被給定數據點所唯一地定義出來。但是，對同樣的數據進行插值的n階樣條並不是唯一的，為了構建一個唯一的樣條插值式它還必須滿足另外n-1個自由度。

線性樣條插值

線性樣條插值是最簡單的樣條插值。數據點使用直線進行連接，結果樣條是一個多邊形。

從代數的角度來看，每個S_i 都是一個如下

${\displaystyle S_{i}(x)=y_{i}+{\frac {y_{i+1}-y_{i}}{x_{i+1}-x_{i}}}(x-x_{i})}$

的線性函數。 樣條在每個數據點都必須連續，即

${\displaystyle S_{i}(x_{i+1})=S_{i+1}(x_{i+1})\qquad {\mbox{ , }}i=1,\ldots n-1}$

我們很容易得到

${\displaystyle S_{i-1}(x_{i})=y_{i-1}+{\frac {y_{i}-y_{i-1}}{x_{i}-x_{i-1}}}(x-x_{i-1})=y_{i}}$

${\displaystyle S_{i}(x_{i})=y_{i}+{\frac {y_{i+1}-y_{i}}{x_{i+1}-x_{i}}}(x-x_{i})=y_{i}}$

所以以上論述成立。

二次樣條插值

二次樣條插值可以構建為

${\displaystyle S_{i}(x)=y_{i}+z_{i}(x-x_{i})+{\frac {z_{i+1}-z_{i}}{2(x_{i+1}-x_{i})}}(x-x_{i})^{2}}$

通過選擇${\displaystyle z_{0}}$，然後用遞推關係就可以得到係數：

${\displaystyle z_{i+1}=-z_{i}+2{\frac {y_{i+1}-y_{i}}{x_{i+1}-x_{i}}}}$

三次樣條插值

對於${\displaystyle n+1}$給定點的數據集${\displaystyle \{x_{i}\}}$，我們可以用${\displaystyle n}$段三次多項式在數據點之間構建一個三次樣條。如果

${\displaystyle S(x)=\left\{{\begin{matrix}S_{0}(x),\ x\in [x_{0},x_{1}]\\S_{1}(x),\ x\in [x_{1},x_{2}]\\\cdots \\S_{n-1}(x),\ x\in [x_{n-1},x_{n}]\end{matrix}}\right.}$

表示對函數${\displaystyle f}$進行插值的樣條函數，那麼需要：

• 插值特性，${\displaystyle S(x_{i})=f(x_{i})}$
• 樣條相互連接，${\displaystyle S_{i-1}(x_{i})=S_{i}(x_{i}),i=1,\ldots ,n-1}$
• 兩次連續可導，${\displaystyle S'_{i-1}(x_{i})=S'_{i}(x_{i})}$ 以及 ${\displaystyle S''_{i-1}(x_{i})=S''_{i}(x_{i}),i=1,\ldots ,n-1}$.

由於每個三次多項式需要四個條件才能確定曲線形狀，所以對於組成${\displaystyle S}$的${\displaystyle n}$個三次多項式來說，這就意味着需要${\displaystyle 4n}$個條件才能確定這些多項式。但是，插值特性只給出了${\displaystyle n+1}$個條件，內部數據點給出${\displaystyle n+1-2=n-1}$個條件，總計是${\displaystyle 4n-2}$個條件。我們還需要另外兩個條件，根據不同的因素我們可以使用不同的條件。

其中一項選擇條件可以得到給定${\displaystyle u}$與${\displaystyle v}$的鉗位三次樣條，

${\displaystyle S'(x_{0})=u\,\!}$

${\displaystyle S'(x_{k})=v\,\!}$

另外，我們可以設

${\displaystyle S''(x_{0})=S''(x_{n})=0\,\!}$.

這樣就得到自然三次樣條。自然三次樣條幾乎等同於樣條設備生成的曲線。

在這些所有的二次連續可導函數中，鉗位與自然三次樣條可以得到相對於待插值函數f的最小震盪。

如果選擇另外一些條件，

${\displaystyle S(x_{0})=S(x_{n})\,\!}$

${\displaystyle S'(x_{0})=S'(x_{n})\,\!}$

${\displaystyle S''(x_{0})=S''(x_{n})\,\!}$

可以得到周期性的三次樣條。

如果選擇，

${\displaystyle S(x_{0})=S(x_{n})\,\!}$

${\displaystyle S'(x_{0})=S'(x_{n})\,\!}$

${\displaystyle S''(x_{0})=f'(x_{0}),\quad S''(x_{n})=f'(x_{n})\,\!}$

可以得到complete三次樣條。

三次樣條的最小性

三次樣條有另外一個非常重要的解釋，實際上它是在索伯列夫空間${\displaystyle H^{2}([a;b])}$最小化泛函

${\displaystyle J(f)=\int _{a}^{b}|f''(x)|^{2}dx}$

的函數。

泛函${\displaystyle J}$包含對於函數${\displaystyle f(x)}$全部曲率${\displaystyle \left|{\frac {f''(x)}{(1+f'(x)^{2})^{\frac {3}{2}}}}\right|}$的近似，樣條是${\displaystyle f(x)}$最小曲率的近似。

由於彈性條的總體能量與曲率成比例，所以樣條是受到${\displaystyle n}$個點約束的彈性條的最小能量形狀。樣條也是基於彈性條設計的工具。

使用自然三次樣條的插值

它可以定義為

${\displaystyle S_{i}(x)={\frac {z_{i+1}(x-x_{i})^{3}+z_{i}(x_{i+1}-x)^{3}}{6h_{i}}}+\left({\frac {y_{i+1}}{h_{i}}}-{\frac {h_{i}}{6}}z_{i+1}\right)(x-x_{i})+\left({\frac {y_{i}}{h_{i}}}-{\frac {h_{i}}{6}}z_{i}\right)(x_{i+1}-x)}$

以及

${\displaystyle h_{i}=x_{i+1}-x_{i}\,\!}$.

通過解下面的方程可以得到它的係數。

${\displaystyle \left\{{\begin{matrix}z_{0}=0\\h_{i-1}z_{i-1}+2(h_{i-1}+h_{i})z_{i}+h_{i}z_{i+1}=6\left({\frac {y_{i+1}-y_{i}}{h_{i}}}-{\frac {y_{i}-y_{i-1}}{h_{i-1}}}\right)\\z_{n}=0\end{matrix}}\right.}$

示例

線性樣條插值

假設要為帶有節點

${\displaystyle (x_{0},f(x_{0}))=(x_{0},y_{0})=\left(-1,\ e^{-1}\right)\,\!}$

${\displaystyle (x_{1},f(x_{1}))=(x_{1},y_{1})=\left(-{\frac {1}{2}},\ e^{-{\frac {1}{4}}}\right)\,\!}$

${\displaystyle (x_{2},f(x_{2}))=(x_{2},y_{2})=\left(0,\ 1\right)\,\!}$

${\displaystyle (x_{3},f(x_{3}))=(x_{3},y_{3})=\left({\frac {1}{2}},\ e^{-{\frac {1}{4}}}\right)\,\!}$

${\displaystyle (x_{4},f(x_{4}))=(x_{4},y_{4})=\left(1,\ e^{-1}\right)\,\!}$

的函數

${\displaystyle f(x)=e^{-x^{2}}}$

找一個線性樣條。直接代入樣條公式，我們得到如下樣條：

${\displaystyle S(x)=\left\{{\begin{matrix}e^{-1}+2(e^{-{\frac {1}{4}}}-e^{-1})(x+1)&x\in [-1,-{\frac {1}{2}}]\\e^{-{\frac {1}{4}}}+2(1-e^{-{\frac {1}{4}}})(x+{\frac {1}{2}})&x\in [-{\frac {1}{2}},0]\\1+2(e^{-{\frac {1}{4}}}-1)x&x\in [0,{\frac {1}{2}}]\\e^{-{\frac {1}{4}}}+2(e^{-1}-e^{-{\frac {1}{4}}})(x-{\frac {1}{2}})&x\in [{\frac {1}{2}},1]\\\end{matrix}}\right.}$

樣條函數（藍線）以及所近似的函數（紅點）如下圖所示：

二次樣條插值

下圖是一個k=4的樣條函數（藍線）與所近似的函數（紅線）的例子：

參見

• 三次埃爾米特樣條
• NURBS