樣條插值

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

## 樣條插值

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

## 線性樣條插值

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

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

$$S_i(x) = y_i + \frac{y_{i+1}-y_i}{x_{i+1}-x_i}(x-x_i)$$

線性函數。

樣條在每個數據點都必須連續，即

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

我們很容易得到

$$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$$

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

所以以上論述成立。

## 二次樣條插值

二次樣條插值可以構建為

$$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$$

通過選擇$z_0$，然後用遞推關係就可以得到係數：

$$z_{i+1} = -z_i + 2 \frac{y_{i+1}-y_i}{x_{i+1}-x_i}$$

## 三次樣條插值

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

$$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.$$

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

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

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

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

$$S'(x_0) = u \,\!$$

$$S'(x_k) = v \,\!$$

另外，我們可以設

$S''(x_0) = S''(x_n) = 0 \,\!$.

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

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

如果選擇另外一些條件。

$$S(x_0) = S(x_n) \,\!$$

$$S'(x_0) = S'(x_n) \,\!$$

$$S''(x_0) = S''(x_n) \,\!$$

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

如果選擇。

$$S(x_0) = S(x_n) \,\!$$

$$S'(x_0) = S'(x_n) \,\!$$

$$S''(x_0) = f'(x_0),\quad S''(x_n)=f'(x_n) \,\!$$

可以得到complete三次樣條。

### 三次樣條的最小性

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

$$J(f)=\int_a^b |f''(x)|^2 dx$$

函數。

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

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

### 使用自然三次樣條的插值

它可以定義為

$$S_i(x) = \frac{z_{i+1} (x-x_i)^3 + z_i (x_{i+1}-x)^3}{6h_i} <pre> + \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) </pre>$$

以及

$h_i = x_{i+1} - x_i \,\!$.

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

$$\left\{\begin{matrix} <pre> 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 </pre> \end{matrix}\right.$$

## 示例

### 線性樣條插值

假設要為帶有節點

$$(x_0,f(x_0)) = (x_0,y_0) = \left(-1,\ e^{-1}\right) \,\!$$

$$(x_1,f(x_1)) = (x_1,y_1) = \left(-\frac{1}{2},\ e^{-\frac{1}{4}}\right) \,\!$$

$$(x_2,f(x_2)) = (x_2,y_2) = \left(0,\ 1\right) \,\!$$

$$(x_3,f(x_3)) = (x_3,y_3) = \left(\frac{1}{2},\ e^{-\frac{1}{4}}\right) \,\!$$

$$(x_4,f(x_4)) = (x_4,y_4) = \left(1,\ e^{-1}\right) \,\!$$

函數

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

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

$$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.$$

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

<image>

### 二次樣條插值

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

<image>