【学习笔记】拉格朗日插值

其实好久之前就学过了, 但是好像有些操作并不是很清楚, 那就给它记录一下吧.

---

拉格朗日插值法

众所周知, $n+1$ 个点可以确定 $n$ 次多项式(貌似所有博客都是这句话开的头).

求这个多项式无脑的办法是高斯消元, 时间复杂度 $\mathcal{O}(n^3)$ , 拉格朗日插值则可以做到 $\mathcal{O}(n^2)$ .

假设多项式为 $f(x)$ , 第 $i$ 个点的坐标为 $(x_i,y_i)$ , 我们要求这个多项式在 $x$ 处的取值.

根据拉格朗日插值法,

$$f(x) = \sum_{i=0}^{n}{y_i\prod_{i \not = j}{\frac{x-x_j}{x_i-x_j}}}$$

直观好像不好理解, 但其实带入个值展开你就会发现, 如果我们带入了 $x_i$ 那么, 后面的连乘的值就会是 $1$ , 否则是 $0$ , 因此正确性得以保证.

接下来拓展一点东西.

在 $x$ 的取值连续时的做法

在 $x$ 的取值连续的时候式子可以改写成 $f(x) = \sum\limits_{i=0}^{n}{y_i}\prod\limits_{i \not= j}{\frac{x-j}{i-j}}$ .

考虑如何快速计算 $\prod\limits_{i \not= j}{\frac{x-j}{i-j}}$ .

对于分子来说, 维护关于 $x$ 的前缀积后缀积即可, 也就是 $pre_i = \prod\limits_{j=0}^{i}{x-j},suf_i = \prod\limits_{j=i}^{n}{x-j}$ .

对于分母来说就是阶乘的形式, 那么式子就变成了.

$$f(x) = \sum_{i=0}^{n}{y_i\frac{pre_{i-1} \times suf_{i+1}}{(i-1)!(n-i)!}}$$

注意这可能会有符号问题, 当 $n-i$ 为奇数的时候, 分母应该取负号.

时间复杂度 $\mathcal{O}(n)$ .

重心拉格朗日插值法

再看看前面的式子,

$$f(x) = \sum_{i=0}^{n}{y_i\prod_{i\not=j}{\frac{x-x_j}{x_i-x_j}}}$$

设 $g=\prod\limits_{i=0}^{n}{x-x_i}$ ,

$$f(x) = g\sum_{i=0}^{n}{\prod_{i\not=j}{\frac{y_i}{(x-x_i)(x_i-x_j)}}}$$

设 $h_i=\dfrac{y_i}{\prod\limits_{i\not=j}{x_i-x_j}}$ ,

$$f(x) = g\sum_{i=0}^{n}{\frac{h_i}{x-x_i}}$$

这样每次新加入一个点的时候只需要新计算它的 $h_i$ 即可, 其实重心的定义是 $w_i = \dfrac{1}{\prod\limits_{i\not=j}{x_i-x_j}}$ .

对比原拉格朗日插值法的优势是, 对于一个新增的点, 拉格朗日插值需要 $\mathcal{O}(n^2)$ 的重新计算, 而重心拉格朗日插值法只需要将每一个 $h_i$ 除以 $x_{n+1}-x_j$ , 重新定义重心, 就可以在 $\mathcal{O}(n)$ 的时间复杂度内计算完成.

拉格朗日插值法插出系数

再接着看拉格朗日插值法的式子,

$$f(x) = \sum_{i=0}^{n}{y_i\prod_{i\not=j}{\frac{x-x_j}{x_i-x_j}}}$$

首先提出常数部分,

$$a_i = \frac{y_i}{\prod\limits_{i\not=j}{x_i-x_j}}$$

可以 $\mathcal{O}(n^2)$ 的求出每一个 $a_i$ .

然后求出一个多项式 $g(x) = \prod\limits_{i=0}^{n}{x-x_i}$ .

可以发现,

$$f(x)=\sum_{i=0}^{n}{a_i\frac{g(x)}{x-x_i}}$$

考虑如何快速求出后面的 $\dfrac{g(x)}{x-x_i}$ .

设 $h(x) = \dfrac{g(x)}{x-c}$ , 可以得到 $(x-c)h(x)=g(x)$ , 提取两边系数得到,

$$[x^{i-1}]h-c[x^i]h = [x^i]g\\ [x^i]h = \frac{[x^i]g-[x^{i-1}]h}{-c}$$

递推即可.

当然, 其实可以再无脑一点, 每次线性除以一个一次的多项式, 最后加和即可.