多项式插值

                     

贡献者: addis

预备知识 范德蒙矩阵、范德蒙行列式

   若有 $n$ 个数据点 $x_1, \dots, x_n$,$y_1, \dots, y_n$($x_i$ 互不相等),使用多项式

\begin{equation} p_{m-1}(x) = c_0 + c_1 x + \dots, c_{m-1}x^{m-1}~. \end{equation}
插值。需要用 $m-1$ 阶多项式插值,可以列出线性方程组
\begin{equation} \begin{pmatrix}1 & x_1 & x_1^2 & \dots & x_1^{m-1}\\ 1 & x_2 & x_2^2 & \dots & x_2^{m-1}\\ 1 & x_3 & x_3^2 & \dots & x_3^{m-1}\\ \vdots & \vdots & \vdots & \ddots & \vdots\\ 1 & x_n & x_n^2 & \dots & x_n^{m-1}\end{pmatrix} \begin{pmatrix}c_0\\ c_1\\ c_2\\ \vdots \\ c_{m-1}\end{pmatrix} = \begin{pmatrix}y_0\\ y_1\\ y_2\\ \vdots \\ y_{m-1}\end{pmatrix} ~. \end{equation}
现在来讨论什么时候该方程有唯一解。事实上系数矩阵就是范德蒙矩阵,当 $x_i$ 互不相等时,它的秩等于 $\min \left\{m, n \right\} $。所以当 $m > n$ 时,存在无穷个解;当 $n > m$ 时一般无解(见超定方程组);当 $n = m$ 时能确保有且仅有唯一解,因为此时系数矩阵是满秩矩阵。

  

未完成:例程

1. 龙格现象

  1若点的个数较多,做多项式插值时会出现龙格现象(Runge's phenomenon),即多项式在两个端点处剧烈振动。一种解决方法是使用多个低阶多项式插值(未完成:splint interp)。另一种方法是不用插值而改为拟合,当多项式阶数 $m-1 < 2\sqrt{n}$ 时,就不会出现龙格现象。


1. ^ 参考 Wikipedia 相关页面

                     

© 小时科技 保留一切权利