拉格朗日插值法学习笔记

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

它能干什么呢?

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

(高斯消元就不说了)

我们考虑怎么做,

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

(编不下去了)直接看公式

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

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

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

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

那我们应该怎么处理?

不难发现,对于所有$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)$。

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

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

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

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

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