lagrange 插值笔记

· · 算法·理论

lagrange 插值

问题

给定 n 个数据点 (x_1,y_1),(x_2,y_2),\dots,(x_n,y_n)（满足 x_1<x_2<\cdots<x_n），你需要构造一个的多项式 f 满足 \forall i，f(x_i) = y_i。

朴素 lagrange 插值

首先，我们构造 n 个多项式 g_1,g_2,\dots,g_n，其中，g_i 满足：

g_i(x_j) = \begin{cases} y_i & \text{if } j = i\\ 0 & \text{otherwise} \end{cases}

这样，只需要将 g_1,g_2,\dots,g_n 全加起来，就是满足要求的 f 了。

为了构造 g_i，我们要给它分配 n - 1 个零点 x_1,x_2,\dots,x_n。不妨先待定系数 a_i，则有：

g_i(x) = a_i\prod_{j\neq i}(x - x_j)

又因为 g_i(x_i) = y_i，所以可以解得：

a_i = \frac{y_i}{\prod\limits_{j \neq i} (x_i - x_j)}

所以可得：

g_i(x) = y_i\prod_{j\neq i}\frac{x - x_j}{x_i - y_j}

最终，构造出的 f 为：

f(x) = \sum_{i = 1} ^ n y_i \prod_{j\neq i}\frac{x - x_j}{x_i - y_j}

这样复杂度为 O(n ^ 2)。

线性复杂度插值

如果给定的数据点具有特殊性质，那么可以做更低的复杂度。

此处举例特殊性质：\forall i，x_i = i。

这时，构造出的多项式变为：

f(x) = \sum_{i = 1} ^ n y_i \prod_{1\leq j\leq n,\ j\neq i}\frac{x - j}{i - j}

可以化简为：

f(x) = \sum_{i = 1} ^ n\frac{\displaystyle (-1) ^ {n - i}y_i\left(\prod_{j = 1} ^ {i-1}(x - j)\right)\left(\prod_{j = i+1} ^ {n}(x - j)\right)}{(n - i)! (i - 1)!}

做一下预处理复杂度为 O(n)。