学习笔记:拉格朗日插值法

参考文献

oi-wiki 插值

oi-wiki 多项式快速插值

前置知识

多项式基础

洛必达法则

引入

当我们面临一个问题：

有 $n$ 个点 $(x_1,y_1),(x_2,y_2),\cdots,(x_n,y_n)$，求一个经过所有点的函数 $f(x)$ 的函数表达式。

我们可以通过一定的拟合方式找出这个函数。

比如用分段线性函数拟合 $f(x)$，这种方法被称作线性插值。

又或者用多项式拟合 $f(x)$，这种方法被称作多项式插值。

多项式插值的其中一种方式就是拉格朗日插值法

Lagrange 插值法

首先设第 $i$ 个点 $p_i$ 在 $x$ 轴上的投影 $p_i'=(x_i,0)$。

考虑构造 $n$ 个函数 $f_1(x),f_2(x),\cdots,f_n(x)$，满足其图像经过 $\begin{cases} p_j'(x_j,0),j\not=i\\ p_i(x_i,y_i) \end{cases}$，则可以得到 $\displaystyle f(x)=\sum_{i=1}^nf_i(x)$。

可以设 $f_i(x)=a\cdot\prod_{j\not=i}(x-x_j)$，将点 $p_i(x_i,y_i)$ 代入可以知道，$a=\frac{y_i}{\prod_{j\not=i}(x_i-x_j)}$，所以

$$f_i(x)=y_i\cdot\frac{\prod_{j\not=i}(x-x_j)}{\prod_{j\not=i}(x_i-x_j)}=y_i\cdot\prod_{j\not=i}\frac{(x-x_j)}{(x_i-x_j)}$$

因此我们就可以得到拉格朗日插值法形如：

$$f_(x)=\sum_{i=1}^ny_i\cdot\prod_{j\not=i}\frac{(x-x_j)}{(x_i-x_j)}$$

朴素实现的时间复杂度为 $O(n\log n)$。

多项式快速插值

记多项式 $M(x)=\prod_{i=1}^n(x-x_i)$，由洛必达法则可知：

$$\prod_{j\not=i}(x_i-x_j)=\lim_{x\rightarrow x_i}\frac{\prod_{j=1}^n(x-x_j)}{x-x_i}=M'(x_i)$$

因此可以将多项式表示为

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

首先通过分治计算出 $M(x)$ 的系数表示，接着可以通过多点求值在 $O(n\log^2n)$ 时间内计算出所有的 $M'(x_i)$。

令 $v_i=\frac{y_i}{M'(x_i)}$，考虑计算 $f(x)$，对于 $n=1$ 的情况，有 $f(x)=v_1,M(x)=x-x_1$。

否则令：

$$f_0(x)=\sum_{i=1}^{\lfloor\frac n2\rfloor}v_i\prod_{j\not=i\land\lfloor\frac n2\rfloor<j\leq n}(x-x_j)\\ M_0(x)=\prod_{i=1}^{\lfloor\frac n2\rfloor}(x-x_i)\\ f_1(x)=\sum_{i=\lfloor\frac n2\rfloor+1}^nv_i\prod_{j\not=i\land\lfloor\frac n2\rfloor<j\leq n}(x-x_j)\\ M_1(x)=\prod_{i=\lfloor\frac n2\rfloor+1}^{n}(x-x_i)$$

可得 $f(x)=f_0(x)M_1(x)+f_1(x)M_0(x),M(x)=M_0(x)M_1(x)$，因此可以分治计算，复杂度 $O(n\log n)$。