拉格朗日插值法

贡献者： addis

预备知识　高斯消元法解线性方程组

　　¹给定 $(x_{1}, y_{1}), \dots, (x_{N}, y_{N})$ ，可以使用一个唯一的 $N - 1$ 阶多项式进行插值

\begin{matrix} (1) & p (x) = c_{0} + c_{1} x + \dots + c_{N - 1} x^{N - 1} . \end{matrix}

要解处系数，可以列

N

元线性方程组

\begin{matrix} (2) & p (x_{i}) = y_{i} (i = 1, \dots, N) . \end{matrix}

方程组的系数矩阵是一个

N \times N

\begin{matrix} (3) & (\begin{matrix} 1 & x_{1} & \dots & x_{1}^{N - 1} \\ 1 & x_{2} & \dots & x_{2}^{N - 1} \\ ⋮ & ⋮ & ⋮ & ⋮ \\ 1 & x_{N} & \dots & x_{N}^{N - 1} \end{matrix}) . \end{matrix}

1. 拉格朗日基底

　　使用拉格朗日基底函数进行插值，可以避免解方程直接得到插值多项式。定义基底函数满足：

\begin{matrix} (4) & l_{i} (x_{j}) = {\begin{aligned} 1 & (j = i) \\ 0 & (j \neq i) \end{aligned} (i, j = 1, \dots, N) . \end{matrix}

容易看出下面的多项式满足该条件

\begin{matrix} (5) & l_{i} (x) = \frac{x - x_{1}}{x_{i} - x_{1}} \frac{x - x_{2}}{x_{i} - x_{2}} \dots \frac{x - x_{i - 1}}{x_{i} - x_{i - 1}} \frac{x - x_{i + 1}}{x_{i} - x_{i + 1}} \dots \frac{x - x_{N}}{x_{i} - x_{N}} . \end{matrix}

　　那么，对任意一组插值点，插值多项式可以表示为拉格朗日基底的线性组合

\begin{matrix} (6) & p (x) = \sum_{i} y_{i} l_{i} (x) . \end{matrix}

1. ^ 参考 Wikipedia 相关页面。