拉格朗日插值法(Lagrange interpolation)
起源
现实生活中许多实际问题都用函数来表示各种变量之间的内在联系或规律。比如通过观察一个APP在一天中不同时间段的在线用户数量，可以反映出来该APP的用户更喜欢在什么时间段使用APP。如果我们通过反复观测统计得到了不同时间段在线用户数量，拉格朗日插值法就可以根据这些观测值，找到一个多项式，其恰好在各个观测点取到对应的观测值。这个多项式就叫做拉格朗日多项式(Lagrange polynomial)。
对于给定的 $n+1$个点$(x_0,y_0),(x_1,y_1),\dots,(x_n,y_n)$，可以找到一个次数不超过$n$的拉格朗日多项式$L$，并且只有一个。 如果计入次数更高的多项式，则有无数个,因为所有与$L$相差 $\lambda (x-x_0)(x-x_1)\dots (x-x_n)$的多项式都满足条件。
定义
给定$k+1$个取值点： $(x_0,y_0),\dots,(x_k,y_k)$, 其中的 $x_j$为自变量的位置，$y_j$为函数在这个位置的取值。假设任意两个$x_j$都互不相同（一个x不能对应两个y）,那么拉格朗日插值多项式为:
$L(x)= \sum_{j=0}^k{y_j\ell_j(x)}$
其中的每个 $\ell_j(x)$为拉格朗日基本多项式（或称插值基函数）:
$\ell_j(x)=\prod_{i=0,i\neq j}^k \frac{x-x_i}{x_j-x_i}=\frac{(x-x_0)}{(x_j-x_0)}\dots \frac{(x-x_{j-1})}{(x_j-x_{j-1})} \frac{(x-x_{j+1})}{(x_j-x_{j+1})} \dots \frac{(x-x_k)}{(x_j-x_k)}$
拉格朗日基本多项式的$\ell_j(x)$的特点是在$x_j$上的取值为1,在其他的点$x_i,i\neq j$上取值为0。
思路
对于给定的$k+1$个点：$(x_0,y_0),\dots,(x_k,y_k)$，拉格朗日插值法的思路是找到一个在点$x_j$处取值为1，而在其他点处取值都为0的多项式$\ell_j(x)$,这样多项式$y_j\ell_j(x)$在点$x_j$处点取值为$y_j$,而在其他点处点取值都为0，于是:
$L(x_j)=\sum_{i=0}^k{y_j\ell_i{(x_j)}}=0+0+\dots+y_j+\dots+0=y_j$
在其他点处取值为0点多项式容易找到，比如：
$other_0=(x-x_0)\dots (x-x_{j-1})(x-x_{j+1})\dots (x-x_k)$
上面的多项式在$x_j$的取值为：$other_0j=(x_j-x_0)\dots (x_j-x_{j-1})(x_j-x_{j+1})\dots (x_j-x_k)$
由于已经假设任何两个$x_i$不相同，因此other_0j取值不等于0，于是将other_0除以other_0j，就能得到一个“在$x_j$处取值为1，在其他点取值都为0的多项式”:
$\ell_j(x)=\prod_{i=0,i\neq j}^k \frac{x-x_i}{x_j-x_i}=\frac{(x-x_0)}{(x_j-x_0)}\dots \frac{(x-x_{j-1})}{(x_j-x_{j-1})} \frac{(x-x_{j+1})}{(x_j-x_{j+1})} \dots \frac{(x-x_k)}{(x_j-x_k)}$
这就是拉格朗日基本多项式。通过拉格朗日基本多项式我们可以推导出，最终通过插值生成的拉格朗日多项式的次数不大于k(对于给定k+1个点的情况)。
唯一性的证明
次数不超过k的拉格朗日多项式至多只有一个。
假设有两个次数不超过k的拉格朗日多项式：$L_1, L_2$。
$diff=L_1-L_2$
由于对于任意的点$x\in[x_0,\dots,x_k]$, $L_1(x)=L_2(x)$
所以对于任意的点$x\in[x_0,\dots,x_k], diff=0$
因为 diff 在所有 k+1 个点上的取值都为0，
因此$diff=\lambda(x-x_0)(x-x_1)\dots(x-x_k)$
如果要使得 $diff\neq 0$, 那么diff的次数就一定不小于 k+1
又由于拉格朗日多项式的次数不超过k,所以diff的次数不超过k
所以推导出在次数不超过k情况下，diff必然等于0，也就是说 $L_1=L_2$