拉格朗日插值法学习笔记

拉格朗日插值法是个好东西。

它能干什么呢？

比如说你有一个未知的$N$次多项式，并且你有$N+1$ 个点值，那么你可以$\mathcal{O}(N^2)$地求出它的系数。

（高斯消元就不说了）

我们考虑怎么做，

先考虑一个问题，如果你有一个未知的$N$次多项式并且你有$N+1$ 个点值，那么再给你一个$x$，你能不能求出它所对应的函数值。

（编不下去了）直接看公式

$$f(x_0)=\sum_{i=1}^{n+1}\frac{\prod\limits_{i!=j}(x_0-x_j)}{\prod\limits_{i!=j}(x_i-x_j)} \times f(x_i)$$

考虑这个式子的正确性，我们带入已知的点值，比如说$x_3$，那么只有当$i=3$时，前面的分式值为一，其余时候，前面的分式值为$0$。所以这个式子是对的。（记住就好了）

那这只是带一个值进去的时候，我如果想求多项式怎么办？

$$f(x)=\sum_{i=1}^{n+1}\frac{\prod\limits_{i!=j}(x-x_j)}{\prod\limits_{i!=j}(x_i-x_j)} \times f(x_i)$$

这就是我们求多项式时的公式，那我们应该怎么算？

不难发现，真正难算的地方时分子部分，分母部分是一个实数。

那我们应该怎么处理？

不难发现，对于所有$i$，分子的形式很相像，那我们不妨先算出$\prod\limits_{i=1}^{n}(x-x_i)$，然后再除一下就行了。

暴力计算显然是$\mathcal{O}(N^3)$的。

So?

假设我们已经求完了前$i-1$项（记为$f’(x)$），现在要求第$i$项，那我们应该怎么做？

我们要算$f’(x) \times (x-x_i)$。

$$\begin{align} Ans & =f'(x) \times (x-x_i) \\ & =f'(x) \times x-f'(x) \times x_i \\ \end{align}$$

我们不难发现，答案是先将自己乘$-x_i$，然后将自己加到下一位。

我们就可以从高向低枚举次数，然后做转移即可。

那除法也一样，逆序操作即可。

那么我们就算出来了这个多项式的各个系数。

总复杂度$\mathcal{O}(N^2)$