拉格朗日插值法
贡献者： addis
1给定 $(x_1, y_1), \dots, (x_N, y_N)$，可以使用一个唯一的 $N-1$ 阶多项式进行插值
\begin{equation}
p(x) = c_0 + c_1x + \dots + c_{N-1}x^{N-1}~.
\end{equation}
要解处系数，可以列 $N$ 元线性方程组
\begin{equation}
p(x_i) = y_i \qquad (i=1,\dots,N)~.
\end{equation}
方程组的系数矩阵是一个 $N\times N$ 的
范德蒙矩阵、范德蒙行列式
\begin{equation}
\begin{pmatrix}1 && x_1 && \dots && x_1^{N-1}\\
1 && x_2 && \dots && x_2^{N-1}\\
\vdots && \vdots && \vdots && \vdots \\
1 && x_N && \dots && x_N^{N-1}\end{pmatrix} ~.
\end{equation}
1. 拉格朗日基底
使用拉格朗日基底函数进行插值，可以避免解方程直接得到插值多项式。定义基底函数满足：
\begin{equation}
l_i(x_j) = \left\{\begin{aligned}
&1 && (j = i) \\
&0 && (j \ne i)
\end{aligned}\right. \qquad (i,j=1,\dots,N)~.
\end{equation}
容易看出下面的多项式满足该条件
\begin{equation}
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{equation}
那么，对任意一组插值点，插值多项式可以表示为拉格朗日基底的线性组合
\begin{equation}
p(x) = \sum_i y_i l_i(x)~.
\end{equation}
1. ^ 参考 Wikipedia 相关页面。
致读者： 小时百科一直以来坚持所有内容免费无广告，这导致我们处于严重的亏损状态。 长此以往很可能会最终导致我们不得不选择大量广告以及内容付费等。 因此，我们请求广大读者
热心打赏 ，使网站得以健康发展。 如果看到这条信息的每位读者能慷慨打赏 20 元，我们一周就能脱离亏损， 并在接下来的一年里向所有读者继续免费提供优质内容。 但遗憾的是只有不到 1% 的读者愿意捐款， 他们的付出帮助了 99% 的读者免费获取知识， 我们在此表示感谢。