拉格朗日插值法

拉格朗日插值法用来在 $O(n ^2)$ 的时间内解决已知多项式点值表达求系数表达的问题。

给定 $n$ 个点 $(x _1, y _1), \dots, (x _n, y _n)$,求出这 $n$ 个点确定的一个 $n - 1$ 次的多项式。

拉格朗日插值法基于这样一个思路:考虑构造出 $n$ 个函数 $f _1(x), f _2(x), \cdots, f _n(x)$,让 $f _i(x)$ 在 $x _i$ 处取值为 $1$,其余处取值为 $0$,最后将这 $n$ 个函数分别乘上 $y _i$ 再加起来就可以得到要求的多项式。

有了这个基本思路,那么 $f _i(x)$ 也不难构造:

$$
f _i(x) = \prod _{j \not = i} \frac {x - x _j} {x _i - x _j}
$$

容易验证,代入 $x _i$ 时式子值为 $1$,其他的则为 $0$。

所以可以得到最终的式子:

$$
f(x) = \sum _{i = 1} ^n y _i \prod _{j \not = i} \frac {x - x _j} {x _i - x _j}
$$

易见复杂度为 $O(n ^2)$。

如果要插系数的话也不难。首先系数可以通过把 $y _i f _i(x)$ 的系数相加得到,所以这里只讲 $f _i(x)$ 的系数怎么求。

观察式子:

$$
f _i(x) = \prod _{j \not = i} \frac {x - x _j} {x _i - x _j}
$$

分母容易算,可以发现分子都是 $\prod _{j = 1} ^n (x - x _j)$ 除掉 $x - x _i$ 的形式。那么先将 $\prod _{j = 1} ^n (x - x _j)$ 的系数 $O(n ^2)$ 地暴力乘出来,然后直接对 $x - x _i$ 做一遍多项式除法就可以得到 $f _i(x)$ 的系数表达。每次做是 $O(n)$ 的,有 $n$ 个 $f _i(x)$,故总复杂度仍为 $O(n ^2)$。