多项式多点求值|快速插值

多项式的多点求值

描述

给出一个多项式 $f (x)$ 和 $n$ 个点 $x_{1}, x_{2}, \dots, x_{n}$ ，求

f (x_{1}), f (x_{2}), \dots, f (x_{n})

解法

考虑使用分治来将问题规模减半。

将给定的点分为两部分：

\begin{aligned} X_{0} & = {x_{1}, x_{2}, \dots, x_{⌊ \frac{n}{2} ⌋}} \\ X_{1} & = {x_{⌊ \frac{n}{2} ⌋ + 1}, x_{⌊ \frac{n}{2} ⌋ + 2}, \dots, x_{n}} \end{aligned}

构造多项式

g_{0} (x) = \prod_{x_{i} \in X_{0}} (x - x_{i})

则有 $\forall x \in X_{0} : g_{0} (x) = 0$ 。

考虑将 $f (x)$ 表示为 $g_{0} (x) Q (x) + f_{0} (x)$ 的形式，即：

f_{0} (x) \equiv f (x) (\mod g_{0} (x))

则有 $\forall x \in X_{0} : f (x) = g_{0} (x) Q (x) + f_{0} (x) = f_{0} (x)$ ， $X_{1}$ 同理。

至此，问题的规模被减半，可以使用分治 + 多项式取模解决。

时间复杂度

T (n) = 2 T (\frac{n}{2}) + O (n \log n) = O (n \log^{2} n)

多项式的快速插值

描述

给出一个 $n + 1$ 个点的集合

X = {(x_{0}, y_{0}), (x_{1}, y_{1}), \dots, (x_{n}, y_{n})}

求一个 $n$ 次多项式 $f (x)$ 使得其满足 $\forall (x, y) \in X : f (x) = y$ 。

解法

考虑拉格朗日插值公式

f (x) = \sum_{i = 1}^{n} \prod_{j \neq i} \frac{x - x_{j}}{x_{i} - x_{j}} y_{i}

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

\prod_{j \neq i} (x_{i} - x_{j}) = lim_{x \to 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 \neq i} (x - x_{j})

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

我们令 $v_{i} = \frac{y_{i}}{M^{'} (x_{i})}$ ，接下来考虑计算出 $f (x)$ 。对于 $n = 1$ 的情况，有 $f (x) = v_{1}, M (x) = x - x_{1}$ 。否则令

\begin{aligned} f_{0} (x) & = \sum_{i = 1}^{⌊ \frac{n}{2} ⌋} v_{i} \prod_{j \neq i \land j \leq ⌊ \frac{n}{2} ⌋} (x - x_{j}) \\ M_{0} (x) & = \prod_{i = 1}^{⌊ \frac{n}{2} ⌋} (x - x_{i}) \\ f_{1} (x) & = \sum_{i = ⌊ \frac{n}{2} ⌋ + 1}^{n} v_{i} \prod_{j \neq i \land ⌊ \frac{n}{2} ⌋ < j \leq n} (x - x_{j}) \\ M_{1} (x) & = \prod_{i = ⌊ \frac{n}{2} ⌋ + 1}^{n} (x - x_{i}) \end{aligned}

可得 $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^{2} n)$ 。

本页面最近更新：2025/9/7 21:50:39，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：fps5283, TrisolarisHD, Enter-tainer, EntropyIncreaser, H-J-Granger, ImpleLee, Ir1d, Tiphereth-A, ZnPdCo
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用