Lagrange插值_成型笔记

$\rm Lagrange$ 插值

补知识点。

多项式的点值表示法与系数表示法

这个应该很容易理解。

多项式的系数表示法就是 $f(x)=\sum_{i= 0}^na_ix^i$，这可以决定一个 $n$ 次多项式，多项式“次数”的定义也来源于此。

多项式的点值表示法是给出 $n+1$ 个多项式所经过的点 $(x_i,y_i)$，满足 $x_i$ 两两互不相同，可以确定一个 $n$ 次多项式。

$\rm Proof$：

考虑列方程：$\forall k\in[0,n],\sum_{i=0}^na_ix_k^i=y_k$，把 $a$ 看作变量，考虑这个方程组的系数矩阵：

$$\begin{bmatrix}1 & x_0 & x_0 ^ 2 & \cdots & x_0 ^ {n } \\1 & x_1 & x_1 ^ 2 & \cdots & x_1 ^ {n } \\1 & x_2 & x_2 ^ 2 & \cdots & x_2 ^ {n } \\\vdots & \vdots & \vdots & \ddots & \vdots \\1 & x_{n } & x_{n } ^ 2 & \cdots & x_{n } ^ {n } \\\end{bmatrix}$$

由于 $x_k$ 两两不同，故该矩阵的各行向量线性无关，$a_i$ 有唯一解，类似的可证它无法确定一个更高次多项式。

上述矩阵也被称为这个点值表示法的 范德蒙德矩阵。

插值就是点值表示法转化成系数表示法的过程。

朴素的插值算法正如刚刚所见，对范德蒙德矩阵高斯消元即可。

$\rm Lagrange$ 插值

任意情况插值

我们发现套用定义解决这个问题实在是太笨蛋了，有没有什么更优秀的做法呢？

$\rm Lagrange$ 插值做的事情类似 $\rm CRT$，对每个 $i\in[0,n]$，求出一个多项式 $f_i$ 使得 $f_i(x_j)=[i=j]y_i$，那么 $f=\sum_if_i$，根据上面的论证我们可以知道必定存在这样 $n$ 个多项式。

由于 $\forall i\ne j,f_i(x_j)=0$，所以 $f_i$ 的分解因式中必定含有 $(x-x_j)$ 这一项。

而我们又要保证 $f_i(x_i)=y_i$，我们可以对 $\prod_{j\ne i}(x-x_j)$ 的结果微调，使得其最后等于 $y_i$，简单的构造我们得到了 $\rm Lagrange$ 插值公式：

$$\begin{aligned}f_i(x)=y_i\prod_{j\ne i}\frac{x-x_j}{x_i-x_j}\\f(x)=\sum_iy_i\prod _{j\ne i}\frac{x-x_j}{x_i-x_j}\end{aligned}$$

在计算上，我们可以暴力求出 $\prod_j({x-x_j})$，然后对于每一个 $i$ 暴力多项式除法除掉 $(x-x_i)$，最后对每个 $i$ 乘上 $y_i\prod_{j\ne i}(x_i-x_j)^{-1}$，然后把所有多项式加起来即可。

预处理逆元，我们得到一个 $\cal O(n^2)$ 的算法。

多项式科技已经可以实现 $\cal O(n\log^2 n)$ 的快速插值，但那超出了我的能力范围。

连续取值插单点值

对于更常见的情况，例如我们想暴力求矩阵的特征多项式 $\det(xI-A)$，我们是可以自由选择若干 $x$ 代入的，而此时如果我们选择了 $x_i=i$，我们的插值可以变得更为迅速：

$$f(x)=\sum_iy_i\prod _{j\ne i}\frac{x-j}{i-j}$$

你可能会疑惑：这用多项式运算不还是 $\cal O(n^2)$ 的吗。

的确如此，但如果我们的所求只是某个点的值，情况就不一样了。

$$f(k)=\sum_iy_i\prod_{j\ne i}\frac{k-j}{i-j}$$

把 $\prod$ 中的分子分母分开考虑，预处理出 $p_j=\prod_{i=0}^{j-1}(k-i),s_k=\prod_{i=j+1}^{n}(k-i)$，则分子为 $p_is_i$。

分母不考虑符号的话是两个阶乘拼起来，考虑一下符号变成最终的式子：

$$f(n)=\sum_iy_i\frac{p_is_i}{(-1)^{n-i}{\rm fac}_{i}{\rm fac}_{n-i}}$$

预处理阶乘的逆元，复杂度 $\cal O(n)$。

其实我们如果不是带着强烈的求多项式系数的目的求出多项式，而只是为了求出一个多项式用于代入计算，那么连续点值 $\rm Lagrange$ 插值计算和代入多项式计算二者的复杂度并无区别，所以点值表示法作为一种表示法，做基本的求一个点处值还是很轻松的。

P4781 【模板】拉格朗日插值

大多数题不会难为你让你求系数表示法的，真求了就变成 $\rm OGF$ 大混战。

本题也是求单点值。

CF622F The Sum of the k-th Powers

求 $\sum_{i=0}^n i^k$，$n\le 10^9,k\le 10^6$。

考虑到 $k$ 很小，我们可以将 $\sum_{i=0}^ni^k$ 视作一个关于 $n$ 的 $k+1$ 次多项式 $f(n)$，求其前 $\cal O(k)$ 项都是简单的，暴力累加即可。

然后插值。

参考资料

多项式 I：拉格朗日插值与快速傅里叶变换