插值法综述

插值法的中心思想就是：

在我们已具备一组 KV 键值对的情况下，如何得出还没被定到的区域的值

使用插值法所建立的函数，在构造的函数中一定要重现原本给定的 KV 键值对，否则就不是插值法而是函数近似或者曲线拟合的问题了

插值的做法，直观来讲就是：

先从 KV 键值对来获得函数 f(x)
用函数 f(x) 求出我们所要的任何特定 x 之 f(x ) 函数值。

然而，比较精密且系统化的数值方法却不是用这两个步骤来进行插值，原因是前述两阶段方法对于插值的精密度并没有控制，效率较差，也比较会有进位误差。一般在做插值法，是从欲插值点 x 附近的几个 KV 键值对 xi 开始，建立插值函数 f(x) ，并且也试着网罗更多 KV 键值对来插值，看随着项数变多误差会不会变小，如此找出最适合的函数 f(x) 。

线性插值法

所有的插值法里面最简单的莫过于线性插值法，任两个相邻的点之间必可以拉一条直线把它们连起来，如此在之间的 x 值就都有线性函数 y(x ) 可以对应到，利用直线上的斜率必为固定值的特性

多项式插值法

现存的各种多项式插值法最终都是通过假设多项式方程求解方程参数的问题，也就是矩阵求解的问题。

线性方程

假设我们现在已知 k 个在二维平面上的点，那么我们可以连立这些点组成一个 k-1 次的方程组，从而解出这个方程组的各个系数。

例如：

$y=Ax^2+Bx+C$

当我们有 3 个点的时候，我们联立的方程是

$\begin{align} Ax_0^2+Bx_0+C&=y_0\\ Ax_1^2+Bx_1+C&=y_1\\ Ax_2^2+Bx_2+C&=y_2 \end{align}$

变为矩阵求解问题，结合克莱姆法则(Cramer‘s Rule) 我们可以很快得出
$A=\frac{\begin{vmatrix} y_0 & x_0 & 1 \\ y_1 & x_1 & 1 \\ y_2 & x_2 & 1 \end{vmatrix}}{\begin{vmatrix} x_0^2 & x_0 & 1 \\ x_1^2 & x_1 & 1 \\ x_2^2 & x_2 & 1 \end{vmatrix}},\ B=\frac{\begin{vmatrix} x_0^2 & y_0 & 1 \\ x_1^2 & y_1 & 1 \\ x_2^2 & y_2 & 1 \end{vmatrix}}{\begin{vmatrix} x_0^2 & x_0 & 1 \\ x_1^2 & x_1 & 1 \\ x_2^2 & x_2 & 1 \end{vmatrix}},\ C=\frac{\begin{vmatrix} x_0^2 & x_0 & y_0 \\ x_1^2 & x_1 & y_1 \\ x_2^2 & x_2 & y_2 \end{vmatrix}}{\begin{vmatrix} x_0^2 & x_0 & 1 \\ x_1^2 & x_1 & 1 \\ x_2^2 & x_2 & 1 \end{vmatrix}}$

以上公式可用的前提是分母不为 0，很多资料中在提到插值算法的时候要求各个点互异也是这个原因。实际上这间接证明了插值函数在一定次数上的解的唯一性，如果我们刚刚假设的是一个 3 次多项式，却只有 3 个点，方程就变为了 3 行 4 列，解是无穷的。因此我们才可以说在 n 个点互异的情况下可以确定唯一一个 n-1 次多项式。

但是线性方程组在实际应用中是有重大缺陷的：

计算量大，如果是几万几十万的数据量，方程组的解将会非常耗时。
如果要新增加一组数据，整个方程组就会发生改变，要重新计算

于是乎，我们引入了牛顿插值法

牛顿插值法

牛顿插值法的特点在于：每增加一个点，不需要推翻之前的计算，只需要计算和新增加的点相关的多项式就可以了。

假设已知 $n+1$ 个点相对多项式函数 $f$ 的值为： $(x_0,f(x_0)),(x_1,f(x_1)),(x_2,f(x_2)), \cdots ,(x_ n,f(x_ n))$ ，求此多项式函数 $f$ 。

先从求满足两个点 $(x_0,f(x_0)),(x_1,f(x_1))$ 的函数 $f_1(x)$ 说起：

假设 $f_1(x)=f(x_0)+b_1(x-x_0)$ ，

令 $f_1(x_1)=f(x_1)$ ：

$\begin{align*} & \implies b_1=\frac{f(x_1)-f(x_0)}{x_1-x_0} \\ & \implies f_1(x)=f(x_0)+\frac{f(x_1)-f(x_0)}{x_1-x_0}(x-x_0) \end{align*}\\$

现在我们增加一个点， $(x_0,f(x_0)),(x_1,f(x_1)),(x_2,f(x_2))$ ，求满足这三个点的函数 $f_2(x)$ ：

假设 $f_2(x)=f_1(x)+b_2(x-x_0)(x-x_1)$ ，

令 $f_2(x_2)=f(x_2)$ ：

$\begin{align*} & \implies b_2=& & \frac{[\frac{f(x_2) - f(x_1)}{x_2 - x_1}] - [\frac{f(x_1) - f(x_0)}{x_1 - x_0}]}{x_2 - x_0} \\ & \implies f_2(x) = & & f(x_0)+\frac{f(x_1)-f(x_0)}{x_1-x_0}(x-x_0) \\ & & & +\frac{[\frac{f(x_2) - f(x_1)}{x_2 - x_1}] - [\frac{f(x_1) - f(x_0)}{x_1 - x_0}]}{x_2 - x_0}(x-x_0)(x-x_1) \end{align*}\\$

$b_1,b_2$ 看起来蛮有特点的，我们把特点提炼一下。

一阶均差：

$f[x_ i,x_ j]=\frac{f(x_ i)-f(x_ j)}{x_ i-x_ j},i\ne j\\$

二阶均差是一阶均差的均差：

$f[x_ i,x_ j,x_ k]=\frac{f[i,j]-f[j,k]}{x_ i-x_ k},i\ne j\ne k\\$

三阶均差就是二阶均差的均差，以此类推，我们得到牛顿插值法为：

$\begin{align*} f(x) =& f({x_0}) + f[{x_0},{x_1}](x - {x_0}) \\ & + f[{x_0},{x_1},{x_2}](x - {x_0})(x - {x_1}) +\cdots \\ & + f[{x_0},{x_1}, \cdots ,{x_{n - 2}},{x_{n - 1}}](x - {x_0})(x - {x_1}) \cdots (x - {x_{n - 2}})(x - {x_{n - 1}}) \\ & + f[{x_0},{x_1}, \cdots ,{x_{n - 1}},{x_ n}](x - {x_0})(x - {x_1}) \cdots (x - {x_{n - 1}})(x - {x_ n}) \end{align*}\\$

计算通过下面这个示意图进行，就会很简单：

新增一个点就只需要计算相关的差分就可以了：

拉格朗日插值法

Lagrange在构造函数的时候就是利用了零点的特性，用基函数的现行组合来实现。

通常我们说基的时候是在说组成空间的不相同的元素，比如基向量组成向量空间，那么基函数的线型组合就构成了一个函数空间。
$L(x)=a_0l_0(x)+a_1l_1(x)+a_2l_2(x)+\cdots+a_nl_n(x)$

其中 $l_i(x)$ 为基函数 $a_i$ 为常数

如果我们让 $a_i$ 直接等于 $y_i$ 那我们就只需要构造对应的 $l_i(x_i)=1,l_i(x_j)=0$ 就好了
一次的条件下 $(x-x_j)$ 满足等于0的条件，二次的条件下 $(x-x_{j1})(x-x_{j2})$ 同理。加上对应的分母就可以满足条件一。*

$\begin{align} l_i(x)&=\prod_{j=0,j\not = i}^n\frac{(x-x_j)}{(x_i-x_j)}\\ L(x)&=\sum_{i=0}^ny_i\prod_{j=0,j\not = i}^n\frac{(x-x_j)}{(x_i-x_j)} \end{align}$

如果要找到某种和唯一解的对应关系，我们看一下克莱姆法则中的A的分母，是个范德蒙(Vandermonde)行列式，可以展开成 $V=\prod{n\ge i\gt j\ge 0}^n(xi-xj)$ , 如果我们找到所有 $x$ 的二次项，加在一起，将分母变成V，就会发现分子是 $\begin{vmatrix} y_0 & x_0 & 1 \\ y_1 & x_1 & 1 \\ y_2 & x_2 & 1 \end{vmatrix}$ 行列式按第一列展开而已。