前言

上两篇分别是拉格朗日插值法和牛顿插值法。

拉格朗日插值的思想是将一个多项式拆分为多个多项式，每个多项式完成一个节点插值。

牛顿插值法的思想是一种递推法，当出现新的抽样点时，增量更新一次插值函数。

从形式上来看，两种插值法得到的多项式不同，牛顿插值因为使用增量更新，因此计算量相对较小。

多项式插值法的解与范德蒙矩阵

未知表达式的函数$f(x)$满足$y_0=f(x_0),y_1=f(x_1),y_2=f(x_2),\dots ,y_n=f(x_n)$，插值多项式的形式表示为：
$$P(x)=a_0+a_{1}x+a_2{x}^2+\cdots +a_n{x}^n$$

如果直接使用方程组求解，则有以下方程组：
$$\begin{gathered} P(x_0)=a_0+a_1{x}_0+a_2{x}_0^2+\cdots +a_n{x}_0^n=y_0 \\ P(x_1)=a_0+a_1{x}_1+a_2{x}_1^2+\cdots +a_n{x}_1^n=y_1 \\ P(x_2)=a_0+a_1{x}_2+a_2{x}_2^2+\cdots +a_n{x}_2^n=y_2 \\ \dots \\ P(x_n)=a_0+a_1{x}_n+a_2{x}_n^2+\cdots +a_n{x}_n^n=y_n \end{gathered}$$
用矩阵方程表示：
$$\begin{gathered} X\alpha =\gamma \\ \left[\begin{array}{ccccc}1& x_0& x_0^2& \dots & x_0^n\\ 1& x_1& x_1^2& \dots & x_1^n\\ 1& x_2& x_2^2& \dots & x_2^n\\ \dots & \dots & \dots & \dots & \dots \\ 1& x_n& x_n^2& \dots & x_n^n\end{array}\right]\left[\begin{array}{c}{a}_0\\ a_1\\ a_2\\ \dots \\ a_n\end{array}\right]=\left[\begin{array}{c}{y}_0\\ y_1\\ y_2\\ \dots \\ y_n\end{array}\right] \end{gathered}$$
其中，矩阵$X$是范德蒙矩阵，其行列式$|X|={\prod }_{0\le j<i\le n}(x_i-x_j)$。由于采样点横坐标都不相同，因此$|X|\ne 0$，$X$可逆，则$\alpha$必然是有唯一解的。这说明，同阶多项式插值的解实际上是唯一的，拉格朗日插值和牛顿插值的结果只是形式表达上不相同。

龙格现象

在我们的直觉上，使用多项式插值法时，多项式阶数越高，插值效果越好。但是，当多项式的阶数较大时，可能会出现龙格现象，即在插值区间的边缘，插值结果与真实函数差值巨大。这个现象表明在使用多项式插值时，尽量避免使用阶数过高的多项式。

除了不使用高阶多项式插值外，也可以通过插值节点的选择来避免龙格现象。当均匀取节点时更有可能出现龙格现象，而选择切比雪夫或者高斯节点就可能避免龙格现象。