插值

在數學的數值分析領域中，內插，或稱插值（Interpolation），是一種通過已知的、離散的數據點，在範圍內推求新數據點的過程或方法。求解科學和工程的問題時，通常有許多數據點藉由採樣、實驗等方法獲得，這些數據可能代表了有限個數值函數，其中自變量的值。而根據這些數據，我們往往希望得到一個連續的函數（也就是曲線）；或者更密集的離散方程與已知數據互相吻合，這個過程叫做擬合。

與插值密切相關的另一個問題是通過簡單函數逼近複雜函數。假設給定函數的公式是已知的，但是太複雜以至於不能有效地進行評估。來自原始函數的一些已知數據點，或許會使用較簡單的函數來產生插值。當然，若使用一個簡單的函數來估計原始數據點時，通常會出現插值誤差；然而，取決於該問題領域和所使用的插值方法，以簡單函數推得的插值數據，可能會比所導致的精度損失更大。

內插是曲線必須通過已知點的擬合。參見擬合條目。

例如，已知數據：

- $x_1=1$，$y_1=2$。
- $x_2=2$，$y_2=3$。
- $x_3=4$，$y_3=6$。

求：

當$x=3$時的y值。

## 定義

給定$n$個離散數據點（稱為節點）$(x_k, y_k)$，$k=1,2,...,n$。對於$x,(x\neq x_k, k=1,2,...n)$，求$x$所對應的$y$的值稱為內插。

$f(x)$為定義在區間$[a,b]$上的函數。$x_1,x_2,x_3...x_n$為$[a,b]$上n個互不相同的點，$G$為給定的某一函數類。若$G$上有函數$g(x)$滿足：

```
 <math>g(x_i)=f(x_i),k=1,2,...n</math>
```

則稱$g(x)$為$f(x)$關於節點$x_1,x_2,x_3...x_n$在$G$上的插值函數。

## 示例

舉例假設我們有這樣如下列一個表，它給出了某個未知函數$f$的值

<image>

$x$｜$f(x)$

0｜0

1｜0｜.｜8415

2｜0｜.｜9093

3｜0｜.｜1411

4｜−0｜.｜7568

5｜−0｜.｜9589

6｜−0｜.｜2794

插值提供了估算中間點函數的方法，如$x=2.5$。

有許多不同的插值方法，其中一些在下面描述。在選擇適當的演算法時需要考慮的一些問題是：方法有多準確？它的計算成本有多高？插值有多平滑？需要多少數據點？

## 方法

### 片段插值

<image>

最簡單的插值方法是找到最近的數據值，並分配相同的值。這種方法又稱為最近鄰插值。在簡單的問題中，不太可能使用這種方法，因為線性插值（見下一小節）幾乎一樣容易，但在高維度的多變量插值中，這可能是衡量速度和簡單性的有利選擇。

### 線性插值

<image>

考慮上面估計 f(2.5) 的例子。由於 2.5 在 2 和 3 之間，所以在 f(2) = 0.9093 和 f(3) = 0.1411 之間，取中間的 f(2.5) 是合理的，得到 0.5252。

一般來說，線性插值採用兩個數據點，例如 (xa,ya) 和 (xb,yb)。

則線性插值的公式為

$$y = y_a + \left( y_b-y_a \right) \frac{x-x_a}{x_b-x_a} \text{ 在 點 } \left( x,y \right)$$

$$\frac{y-y_a}{y_b-y_a} = \frac{x-x_a}{x_b-x_a}$$

$$\frac{y-y_a}{x-x_a} = \frac{y_b-y_a}{x_b-x_a}$$

上面公式中的方程式表明，$(x_a,y_a)$和 $(x,y)$ 的斜率，與 $(x_a,y_a)$ 和 $(x_b,y_b)$ 之間的斜率相同，線性插值是快速簡單的，但不是很精確。另一個缺點是在插值點 xk 不是可微分的。

以下誤差估計顯示線性插值不是很精確。用 g 表示我們要插入的函數，假設 x 位於 xa 和 xb，而 g 是連續可微的。那麼線性插值的誤差是

$$|f(x)-g(x)| \le C(x_b-x_a)^2 \quad\text{where}\quad C = \frac18 \max_{r\in[x_a,x_b]} |g''(r)|.$$

換言之，誤差與數據點之間的距離的平方成正比。包括多項式插值和樣條插值（見下一小節）在內的其他一些方法中的誤差與數據點之間距離的較高冪成正比。這些方法也產生更平滑的插值。

### 多項式插值

<image>

多項式插值是線性插值的推廣。線性插值是一個線性函數。我們現在用一個更高階的多項式代替這個插值。

再考慮一下上面給出的問題。以下的六次多項式經歷了所有七個點：

$$f(x) = -0.0001521 x^6 - 0.003130 x^5 + 0.07321 x^4 - 0.3577 x^3 + 0.2255 x^2 + 0.9038 x.$$

代入 x = 2.5，我們發現 f(2.5) = 0.5965。

一般情況下，如果我們有 n 個數據點，那麼在所有的數據點中只有一個最多 n-1 次多項式。插值誤差與數據點與冪次 n 之間的距離成正比。此外，插值是一個多項式，因此是無限可微的。所以我們看到多項式插值克服了線性插值的大部分問題。但是，多項式插值也有一些缺點。與線性內插相比，計算內插多項式的成本是昂貴的（參見計算複雜度）。此外，多項式插值可能會出現振盪偽像，特別是在端點（見龍格現象）。

與線性插值不同，多項式插值可以估計樣本範圍之外的局部最大值和最小值。例如，上面的插值在 x ≈ 1.566 處有一個局部最大值，f(x) ≈ 1.003，在 x ≈ 4.708 處有一個局部最小值，f(x) ≈ −1.003。然而，這些最大值和最小值可能會超出函數的理論範圍 - 例如，一個總是正的函數可能有一個負值的插值，因此它的逆值包含假垂直漸近線。

更一般地說，所得曲線的形狀，特別是對於獨立變量的非常高或低的值，可能與常識相反，即與已經產生數據點的實驗系統已知的情況相反。通過使用樣條插值或限制對切比雪夫多項式的注意可以減少這些缺點。

### 樣條曲線插值

<image>

線性插值對每個區間 xk,xk+1 使用線性函數。樣條插值在每個間隔中使用低階多項式，並選擇多項式以使它們平滑地吻合在一起。結果函數被稱為樣條曲線。

例如，三次樣條是分片段立方，兩次連續可微。此外，它的二階導數在終點為零。在上表中插入點的三次樣條函數由下式給出

$$f(x) = \begin{cases} -0.1522 x^3 + 0.9937 x, & \text{if } x \in [0,1], \\ -0.01258 x^3 - 0.4189 x^2 + 1.4126 x - 0.1396, & \text{if } x \in [1,2], \\ 0.1403 x^3 - 1.3359 x^2 + 3.2467 x - 1.3623, & \text{if } x \in [2,3], \\ 0.1579 x^3 - 1.4945 x^2 + 3.7225 x - 1.8381, & \text{if } x \in [3,4], \\ 0.05375 x^3 -0.2450 x^2 - 1.2756 x + 4.8259, & \text{if } x \in [4,5], \\ -0.1871 x^3 + 3.3673 x^2 - 19.3370 x + 34.9282, & \text{if } x \in [5,6]. \end{cases}$$

在這種情況下，我們得到 f(2.5) = 0.5972。

與多項式插值的方法相比較，樣條跟多項式一樣，其插值誤差會小於線性插值，而且插值更平滑；使用樣條會比使用高階多項式更容易評估。它也不會受到龍格現象的影響。

## 以高斯過程處理的插值

其他形式的插值可以通過選擇不同的插值類來構造。例如，有理插值是使用Padé逼近的有理函數插值，而三角插值是使用傅立葉級數的三角多項式插值。另一種可能是使用小波。

如果數據點的數量是無限的，則可以使用Whittaker-Shannon插值公式。

有時候，我們不僅知道我們想插入的函數的值，而且也知道它的導數。這導致Hermite插值問題。

當每個數據點本身就是一個函數時，將插值問題看作是每個數據點之間的局部對流問題是有用的。這個想法導致了運輸理論中使用的位移插值問題。

## 數位訊號處理的插值

在數位訊號處理領域，插值是指使用各種數字濾波器（例如帶限脈衝信號）提高數位訊號（例如語音信號）的採樣率（即升採樣）。在升採樣的過程中，原始信號的諧波成分需要在不產生高於原始信號奈奎斯特頻率（原始信號採樣率的一半）的混疊諧波的情況下保留。Rabiner和Crochiere的書Multirate Digital Signal Processing對此進行了討論。

## 相關概念

術語外推用於找到已知數據點範圍之外的數據點。

在曲線擬合問題中，插值必須準確穿過數據點的約束被放寬。只需要盡可能接近數據點（在一些其他限制內）。這需要參數化潛在的插值並且有一些測量誤差的方法。在最簡單的情況下，這導致最小二乘法逼近。

近似理論研究如何從某個預定的類別的另一個函數找到給定函數的最佳逼近，以及這個近似值有多好。這明顯產生了內插函數可以近似未知函數的界限。

## 公式

本章內容參考了《數學手冊》。

- 牛頓第一內插公式（牛頓向前內插公式）
- 牛頓第二內插公式（牛頓向後內插公式）
- 斯特林內插公式
- 貝塞耳內插公式
- 拉格朗日內插多項式
- 三次樣條內插公式
- 埃爾米特內插公式（Hermite）
- 二元內插公式
- 一元三點內插公式

## 外部連結

- 談補間法
- Sol Tutorials - Interpolation Tricks