插值法

简单来说，插值法是通过已知的离散的数据来推测未知数据的一种方法。

举个例子：我现在有这么一组数据

$x$	$1$	$2$	$3$	$4$
$y$	$3$	$?$	$6$	$7$

在 $x=2$ 时的值缺失了，不见了，被墨水挡上了😢。如何来使用已知的离散数据点来预测 $y$ 呢？或许我们可以用数据健全的四个点来拟合出一个多项式函数 $p(x)$，再将 $x=2$ 代入，求得 $p(2)$，用它来预测缺失值，这样问题就解决啦！有了这条曲线，我们不仅可以来近似的填补空缺，还可以来近似我想知道的任意一个比如 $x = 3.5$ 时的 $y$。

接下来介绍的就是如何来求解这样一个多项式函数 $p(x)$，至于拉格朗日插值或者牛顿插值的区别，只是求解方法的不同。

拉格朗日插值

我现在有三个已知点 $(1, 3),(3, 6),(4, 7)$，通过代入下面这个有三个未知系数的二次多项式的假设：

$$p(x) = a + bx + cx^2$$

形成如下的方程组：

$$\begin{cases} 3 = a + b + c\\ 6 = a + 3b + 9c\\ 7 = a + 4b +16c \end{cases}$$

只要求解出 $a,b,c$，就能得出过已知点的二次多项式，这样就可以填补空缺值了。实际上，拉格朗日想了一个更好的办法不用去求解上面的方程组，而是通过用以下的方式来进行求解的。

拉格朗日想通过三个较为简单的二次函数相加来达到目标。

• 第一个函数 $p_1(x)$ 在 $x_1=1$ 处的值为 $1$，在 $x_2,x_3$ 处的值为 $0$。
• 第二个函数 $p_2(x)$ 在 $x_2=3$ 处的值为 $1$，在 $x_1,x_3$ 处的值为 $0$。
• 第三个函数 $p_3(x)$ 在 $x_3=4$ 处的值为 $1$，在 $x_1,x_2$ 处的值为 $0$。

这样，只要用每个 $y$ 去乘对应的 $p_i(x)$，再把三个函数加起来：

$$p(x) = 3p_1(x) + 6p_2(x) + 7p_3(x)$$

这样就可以得到我们想要拟合的函数啦！

接下来的问题就是如何来求解 $p_i(x)$ 了。

为了一般化表示，我们不妨将三个已知的点表示成 $(x_1,y_1),(x_2,y_2),(x_3,y_3)$。而 $p_1(x)$ 可以构造为

$$p_1(x) = \frac{(x-x_2)(x-x_3)}{(x_1-x_2)(x_1-x_3)}$$

如果已知的点数为 $n$，可记作通式

$$p_i(x) = \prod_{j\neq i}^{1\leq j\leq n}\frac{(x-x_j)}{(x_i-x_j)}$$

最终的多项式结果为

$$p(x) = \sum_{i=1}^ny_ip_i(x)$$

其中 $p_i(x)$ 被称作 $2$ 次插值基函数。

牛顿插值

在已知的数据点新增时，拉格朗日插值似乎需要对每个基函数需要修改，在维数过高的时候会耗费较大的计算量。牛顿插值法解决了这个问题。

如果我们现在有两个已知点 $(x_1,y_1),(x_2,y_2)$ 过函数 $p(x)$，我们可以用一个函数 $p_1(x)$ 来表示

$$p_1(x) = y_1 + c(x-x_1)$$

其中 $c$ 为一个常数。这个函数显然在 $x=x_1$ 时 $p_1(x_1)=y_1$，若想令在 $x=x_2$ 时 $p_1(x_2)=y_2$，代入即可求处 $c$：

$$c=\frac{p(x_2)-p(x_1)}{x_2-x_1}$$

如果新增一个点 $(x_3,y_3)$，我们可以用一个二次函数 $p_2(x)$ 来表示

$$p_2(x) = p_1(x) + c_2(x-x_1)(x-x_2)$$

想令在 $x=x_3$ 时 $p_2(x_3)=y_3$，代入即可求处 $c_2$

$$c_2 = \frac{\left[\frac{p(x_3)-p(x_2)}{x_3-x_2}\right] - \left[\frac{p(x_2)-p(x_1)}{x_2-x_1}\right]}{x_3-x_1}$$

我们引入均差这一概念：

一阶均差：

$$p[x_i,x_j] = \frac{p(x_i)-p(x_j)}{x_i-x_j},\quad i\neq j$$

二阶均差

$$p[x_i,x_j,x_k] = \frac{p[x_i,x_j]-p[x_j,x_k]}{x_i-x_k},\quad i\neq j\neq k$$

关于均差，看一下下面的均差表可以直观不少:

$x$	$p(x)$	一阶均差	二阶均差	三阶均差	$\cdots$
$x_1$	$p(x_1)$
$x_2$	$p(x_2)$	$p[x_2,x_1]$
$x_3$	$p(x_3)$	$p[x_3,x_2]$	$p[x_3,x_2,x_1]$
$x_4$	$p(x_4)$	$p[x_4,x_3]$	$p[x_4,x_3,x_2]$	$p[x_4,x_3,x_2,x_1]$	$\cdots$

以此类推，我们就可以得到牛顿插值法的通式：

$$\begin{align} p(x) = p(x_1)+p[x_1,x_2](x-x_1) + p[x_1,x_2,x_3](x-x_1)(x-x_2) \end{align}$$

这样，在引入新的已知点 $(x_4,y_4)$ 拟合新的公式的时候，只用计算新的三阶均差 $p[x_4,x_3,x_2,x_1]$ 即可，而不需要重新计算所有的基函数。

范德蒙行列式

回到最初我们需要对付的那个方程组：

$$\begin{cases} y_1 = a + bx_1 + cx^2_1\\ y_2 = a + bx_2 + cx^2_2\\ y_3 = a + bx_3 + cx^2_3 \end{cases}$$

可以将其写成矩阵形式：

$$\begin{pmatrix} y_1\\y_2\\y_3 \end{pmatrix} = \begin{pmatrix} 1 & x_1 & x_1^2\\ 1 & x_2 & x_2^2\\ 1 & x_3 & x_3^2 \end{pmatrix} \begin{pmatrix} a\\b\\c \end{pmatrix}$$

其中系数矩阵

$$A=\begin{pmatrix} 1 & x_1 & x_1^2\\ 1 & x_2 & x_2^2\\ 1 & x_3 & x_3^2 \end{pmatrix}$$

便是范德蒙矩阵。我们都知道，范德蒙行列式

$$\begin{align} \det(A)=&\prod_{1\leq j< i\leq 3}(x_i-x_j)\\ =&(x_3-x_1)(x_3-x_2)(x_2-x_1) \end{align}$$

当 $A$ 为非奇异矩阵时，方程组只有唯一解。也就是说，只要 $x_1,x_2,x_3$ 两两不同，则拉格朗日插值法与牛顿插值法所得到的插值函数便会完全一样。

除了这些插值方法，还有 Hermit 插值、分段线性插值、样条插值，如果有用到会继续写，嘻嘻🤭。