拉格朗日插值学习笔记
Published:
在 Lagrange 之前，不妨先看看 CRT。
CRT
问题
\[\begin{cases} x \equiv r_1 \pmod {m_1} \\ x \equiv r_2 \pmod {m_2} \\ \vdots \\ x \equiv r_n \pmod {m_n} \end{cases}\]其中 $m_{1 \sim n}$ 两两互质。
解法
定义 $e_i$ 为满足 $e_i \equiv 1 \pmod {m_i}$ 且对于任意 $j \ne i$ 有 $e_i \equiv 0 \pmod {m_j}$ 的数。
那么 $x$ 就可以表示为 $e_{1 \sim n}$ 的线性组合：$\sum\limits_{i=1}^n r_i e_i$。
问题变为求解 $e_i$。
令 $M_i = \prod\limits_{j \ne i} m_j$。$e_i = M_i \times [M_i]^{-1}_{\bmod m_i}$ 就是一个合理的构造。
Lagrange
已知 $n$ 个点，插一个 $n-1$ 次多项式：
\[f(k) = \sum\limits_{i=1}^n y_i \prod\limits_{j \ne i} \frac {k - x_j} {x_i - x_j}\]时间复杂度 $O(n^2)$。
推导
即求解：
\[\begin{cases} f(x) \equiv y_1 \pmod {x - x_1} \\ f(x) \equiv y_2 \pmod {x - x_2} \\ \vdots \\ f(x) \equiv y_n \pmod {x - x_n} \end{cases}\]直接抄上中国剩余定理的推导：
定义 $e_i$ 为满足 $e_i \equiv 1 \pmod {x - x_i}$ 且对于任意 $j \ne i$ 有 $e_i \equiv 0 \pmod {x - x_j}$ 的数。
那么 $x$ 就可以表示为 $e_{1 \sim n}$ 的线性组合：$\sum\limits_{i=1}^n y_i e_i$。
问题变为求解 $e_i$。
令 $M_i = \prod\limits_{j \ne i} (x - x_j)$。$e_i = M_i \times [M_i]^{-1}_{\bmod (x - x_i)}$ 就是一个合理的构造。
问题变为求解 $[M_i]^{-1}_{\bmod (x - x_i)}$。
注意到一些多项式运算的性质：
\[x \equiv a \pmod {x-a}\]两边同时取 $n$ 次方有：
\[x^n \equiv a^n \pmod {x-a}\]不同的 $n$ 次方线性组合，有：（令 $f$ 为多项式函数）
\[f(x) \equiv f(a) \pmod {x-a}\]常数的模意义下倒数就是它正常的倒数，有：
\[(f(x))^{-1} \equiv \frac 1 {f(a)} \pmod {x-a}\]因此：
\[\left(\prod\limits_{j \ne i} (x - x_j)\right)^{-1} \equiv \frac 1 {\prod\limits_{j \ne i} (x_i - x_j)} \pmod {x - x_i}\]代回去：
\[f(x) = \sum\limits_{i=1}^n y_i \prod\limits_{j \ne i} \frac {x - x_j} {x_i - x_j}\]把变量名换的清楚一点，即：
\[f(k) = \sum\limits_{i=1}^n y_i \prod\limits_{j \ne i} \frac {k - x_j} {x_i - x_j}\]扩展：连续点值的 Lagrange 插值
即对于每个 $i$ 都有 $(x_i, y_i) = (i, f(i))$。
\[f(k) = \sum\limits_{i=1}^n y_i \frac {\prod\limits_{j=1}^{i-1} (k-j) \times \prod\limits_{j=i+1}^n (k-j)} {(-1)^{n-i} (i-1)! (n-i)!}\]分子上两个 $\prod$ 都能线性预处理，时间复杂度 $O(n)$。