一. 前言
Lagrange插值是利用 n次多项式来拟合 （n+1）个数据点从而得到插值函数的方法。（注意n次多项式的定义是未知数最高次幂为n，但是多项式系数有n+1个，因为还有个常数项）
Lagrange插值和Newton插值本质上相同，都是用(n-1)次多项式来拟合n个数据点。所以这两种插值方法得到的插值函数相同，因为多项式拟合的基本定理：同时通过n个数据点，且最高次幂小于(n-1)的多项式函数唯一。下面顺手证明一下这个重要的定理。
如果已知n+1个数据点((x_0,y_0),(x_1,y_1),(x_2,y_2),\cdots,(x_n,y_n))，假设(L_1=k_0+k_1x+k_2x^2+\cdots+k_nx^n)和(L_2=k_0'+k_1'x+k_2'x^2+\cdots+k_n'x^n)都是通过这n个数据点的插值函数。那么应该有(L_1 - L_2)通过所有((x_1,0),(x_2,0),\cdots,(x_n,0))
代入这些点得到齐次线性方程组：
[\begin{bmatrix} 1 & x_0 & x_0^2 & \cdots & x_0^n\ 1 & x_1 & x_1^2 & \cdots & x_1^n\ \vdots & \vdots & \vdots & & \vdots \ 1 & x_n & x_n^2 & \cdots & x_n^n\ \end{bmatrix} \begin{bmatrix} k_0-k_0'\ k_1-k_1'\ k_2-k_2'\ \vdots \ k_n-k_n'\ \end{bmatrix} = \begin{bmatrix} 0 \ 0 \ 0 \ \vdots \ 0 \end{bmatrix} ]
它的系数行列式是Vandermonde行列式，所以：
[\begin{vmatrix} 1 & x_0 & x_0^2 & \cdots & x_0^n\ 1 & x_1 & x_1^2 & \cdots & x_1^n\ \vdots & \vdots & \vdots & & \vdots \ 1 & x_n & x_n^2 & \cdots & x_n^n\ \end{vmatrix} = \prod_{n\ge i > j \ge 0 }(x_i-x_j) ]
因为每个点都是不同的，所以(x_i \ne x_j,i\ne j)，所以齐次线性方程组的系数行列式不等于0，故方程解唯一且为0解：
[k_i - k_i' = 0\ k_i = k_i' \ L_1 = L_2 ]
证毕。