拉格朗日插值法学习笔记

古人说过：\(n + 1\) 个点可以确定一个 \(n\) 次多项式。

然而通过解方程求出这个多项式显然不优雅；
\(Lagrange\) 插值法可以通过这 \(n+1\) 个点来求出多项式在 \(x\) 处的取值。

已知信息：\(n + 1\) 个点 \((x_i, y_i)\)；

所以要想办法构造出一个函数使得它过这些点；

考虑这样一个函数：
\[ l_i(x) = \Pi_{i = 1,i \ne j}^{n + 1}\frac{x-x_j}{x_i-x_j} \]
可以发现函数 \(l_i\) 在 \(x \in {x_i}\) 的取值有如下规律：
当 \(x = x_i\) 时，\(l_i(x) = 1\)；否则，\(l_i(x) = 0\)。这一点是显然的。

接着构造如下函数：
\[ f(x)=\Sigma_{i = 1}^{n + 1}y_i \times l_i(x) \]
这样一来，函数 \(f(x)\) 就必过已知的 \(n + 1\) 个点。

按柿子直接算，时间复杂度：\(O(n^2)\)

这大概就是我关于 \(Lagrange\) 插值法一些浅显的认识，下面是在 \(OI\) 中的应用。

重心拉格朗日插值

我们需要进行插值的次数可能会比较多，这时候上述做法可能并不能满足，需要一些优化。

我们观察函数
\[ f(x)=\Sigma_{i = 1}^{n + 1}y_i \times l_i(x) \\ l_i(x)=\Pi_{i = 1,i \ne j}^{n + 1}\frac{x-x_j}{x_i-x_j} \]
可以发现 \(l_i\) 的分母是可以预处理的，复杂度 \(O(n^2)\)；
其次，\(l_i\) 的分子在每次插值之前也可以处理：求出 \(\Pi_{i = 1,i \ne j}^{n + 1}x - x_i\)，把多的除掉。

预处理复杂度 \(O(n^2)\)，单次计算复杂度 \(O(n)\)，(可能会多一个逆元的\(log\))。

当 \(x_i\) 是一段整数区间时

那么 \(l_i(x)\) 中，分母就是 \(fac_{i - 1} \times fac_{n - i}\) ，在 \(n - i\) 为奇数时会有一个负号，(符号和边界问题看代码)；
同时，记：
\[ pre_i=\Pi_{i = 0}^{i - 1} x - x_i \\ suf_i=\Pi_{i = i + 1}^{n + 1} x - x_i \]
那么：
\[ f(x) = \Sigma_{i = 0}^{n + 1} y_i \times \frac{pre_{i - 1}suf_{i + 1}}{fac_{i - 1}fac_{n - i}} \]
(待续，，， )