数值计算之 插值法（3）多项式插值法的解，范德蒙矩阵，龙格现象

前言

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

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

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

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

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

未知表达式的函数 f ( x ) f(x) f(x)满足 y 0 = f ( x 0 ) , y 1 = f ( x 1 ) , y 2 = f ( x 2 ) , … , y n = f ( x n ) y_0=f(x_0),y_1=f(x_1),y_2=f(x_2),\dots,y_n=f(x_n) y0​=f(x0​),y1​=f(x1​),y2​=f(x2​),…,yn​=f(xn​)，插值多项式的形式表示为： P ( x ) = a 0 + a 1 x + a 2 x 2 + ⋯ + a n x n P(x)=a_0+a_1x+a_2x^2+\dots+a_nx^n P(x)=a0​+a1​x+a2​x2+⋯+an​xn

如果直接使用方程组求解，则有以下方程组： P ( x 0 ) = a 0 + a 1 x 0 + a 2 x 0 2 + ⋯ + a n x 0 n = y 0 P ( x 1 ) = a 0 + a 1 x 1 + a 2 x 1 2 + ⋯ + a n x 1 n = y 1 P ( x 2 ) = a 0 + a 1 x 2 + a 2 x 2 2 + ⋯ + a n x 2 n = y 2 … P ( x n ) = a 0 + a 1 x n + a 2 x n 2 + ⋯ + a n x n n = y n P(x_0)=a_0+a_1x_0+a_2x_0^2+\dots+a_nx_0^n=y_0 \\ P(x_1)=a_0+a_1x_1+a_2x_1^2+\dots+a_nx_1^n=y_1 \\ P(x_2)=a_0+a_1x_2+a_2x_2^2+\dots+a_nx_2^n=y_2 \\ \dots \\ P(x_n)=a_0+a_1x_n+a_2x_n^2+\dots+a_nx_n^n=y_n \\ P(x0​)=a0​+a1​x0​+a2​x02​+⋯+an​x0n​=y0​P(x1​)=a0​+a1​x1​+a2​x12​+⋯+an​x1n​=y1​P(x2​)=a0​+a1​x2​+a2​x22​+⋯+an​x2n​=y2​…P(xn​)=a0​+a1​xn​+a2​xn2​+⋯+an​xnn​=yn​ 用矩阵方程表示： X α = γ [ 1 x 0 x 0 2 … x 0 n 1 x 1 x 1 2 … x 1 n 1 x 2 x 2 2 … x 2 n … … … … … 1 x n x n 2 … x n n ] [ a 0 a 1 a 2 … a n ] = [ y 0 y 1 y 2 … y n ] X\alpha = \gamma \\ \quad \\ \begin{bmatrix} 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{bmatrix}\begin{bmatrix} a_0 \\ a_1 \\ a_2 \\ \dots \\ a_n \\ \end{bmatrix} =\begin{bmatrix} y_0 \\ y_1 \\ y_2 \\ \dots \\ y_n \\ \end{bmatrix} Xα=γ⎣⎢⎢⎢⎢⎡​111…1​x0​x1​x2​…xn​​x02​x12​x22​…xn2​​……………​x0n​x1n​x2n​…xnn​​⎦⎥⎥⎥⎥⎤​⎣⎢⎢⎢⎢⎡​a0​a1​a2​…an​​⎦⎥⎥⎥⎥⎤​=⎣⎢⎢⎢⎢⎡​y0​y1​y2​…yn​​⎦⎥⎥⎥⎥⎤​ 其中，矩阵 X X X是范德蒙矩阵，其行列式 ∣ X ∣ = ∏ 0 ≤ j < i ≤ n ( x i − x j ) |X|=\prod_{0\le j