插值

在数学的数值分析领域中，内插，或称插值（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