拉格朗日插值法笔记

由于是为了补题才学这个，所以介绍的是最简单的拉格朗日插值法。

引入

一个 $n$ 次多项式（其实也就是函数） $f (x)$ ，只要知道其中 $n + 1$ 个自变量和对应的因变量，就能解出这个多项式每一项的系数。比如解一次函数 / 二次函数，用待定系数法只需要分别知道两个点 / 三个点就能解二元 / 三元一次方程组解出来。

解线性方程组的方法有高斯消元，但其时间复杂度为 $O (n^{3})$ ，而拉格朗日插值法面对这种问题只需要 $O (n^{2})$ 。

设要求的多项式是 $f (x)$ ，给出在其图像上 $n$ 个的坐标 $(x_{i}, y_{i})$ ，需要求这个多项式自变量为 $k$ 时的取值，则有：

f (k) = \sum_{i = 1}^{n} y_{i} \prod_{i \neq j} \frac{k - x_{j}}{x_{i} - x_{j}}

假设这三个点的坐标是 $(1, 4), (2, 9), (3, 16)$ ，将式子展开：

f (k) = 4 \times \frac{(k - 2) (k - 3)}{(1 - 2) (1 - 3)} + 9 \times \frac{(k - 1) (k - 3)}{(2 - 1) (2 - 3)} + 16 \times \frac{(k - 1) (k - 2)}{(3 - 1) (3 - 2)}

将 $x_{1}$ 代入，会发现除了和 $y_{1}$ 相乘的那项以外，每一项都出现了一个 $(k - p) = 0$ ，所以那一项乘起来也是 $0$ ，而对于和 $y_{1}$ 相乘那一项，乘上的东西变成 $1$ 了，所以就是 $y_{1}$ 。

严格证明不会。

然后这个式子就可以 $O (n^{2})$ 暴力求。