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

多项式的多点求值

描述

给出一个多项式 $f\left(x\right)$ 和 $n$ 个点 $x_1,x_2,\dots ,x_n$，求

$$f\left(x_1\right),f\left(x_2\right),\dots ,f\left(x_n\right)$$

解法

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

将给定的点分为两部分：

$$\begin{array}{rl}{X}_0& =\{x_1,x_2,\dots ,x_{\lfloor \frac{n}{2}\rfloor }\}\\ X_1& =\{x_{\lfloor \frac{n}{2}\rfloor +1},x_{\lfloor \frac{n}{2}\rfloor +2},\dots ,x_n\}\end{array}$$

构造多项式

$$g_0\left(x\right)=\prod _{x_i\in X_0}(x-x_i)$$

则有 $\mathrm{\forall }x\in X_0:g_0\left(x\right)=0$。

考虑将 $f\left(x\right)$ 表示为 $g_0\left(x\right)Q\left(x\right)+f_0\left(x\right)$ 的形式，即：

$$f_0\left(x\right)\equiv f\left(x\right)(\mathrm{mod}{g}_0\left(x\right))$$

则有 $\mathrm{\forall }x\in X_0:f\left(x\right)=g_0\left(x\right)Q\left(x\right)+f_0\left(x\right)=f_0\left(x\right)$，$X_1$ 同理。

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

时间复杂度

$$T\left(n\right)=2T\left(\frac{n}{2}\right)+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\left(x\right)$ 使得其满足 $\mathrm{\forall }(x,y)\in X:f\left(x\right)=y$。

解法

考虑拉格朗日插值公式

$$f(x)=\sum _{i=1}^n\prod _{j\ne i}\frac{x-x_j}{x_i-x_j}{y}_i$$

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

$$\prod _{j\ne i}(x_i-x_j)=\underset{x\to x_i}{lim}\frac{\prod _{j=1}^n(x-x_j)}{x-x_i}=M^{\prime }(x_i)$$

因此多项式被表示为

$$f(x)=\sum _{i=1}^n\frac{y_i}{M^{\prime }(x_i)}\prod _{j\ne i}(x-x_j)$$

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

我们令 $v_i=\frac{y_i}{M^{\prime }(x_i)}$，接下来考虑计算出 $f(x)$。对于 $n=1$ 的情况，有 $f(x)=v_1,M(x)=x-x_1$。否则令

$$\begin{array}{rl}{f}_0(x)& =\sum _{i=1}^{\lfloor \frac{n}{2}\rfloor }{v}_i\prod _{j\ne i\wedge j\le \lfloor \frac{n}{2}\rfloor }(x-x_j)\\ M_0(x)& =\prod _{i=1}^{\lfloor \frac{n}{2}\rfloor }(x-x_i)\\ f_1(x)& =\sum _{i=\lfloor \frac{n}{2}\rfloor +1}^n{v}_i\prod _{j\ne i\wedge \lfloor \frac{n}{2}\rfloor <j\le n}(x-x_j)\\ M_1(x)& =\prod _{i=\lfloor \frac{n}{2}\rfloor +1}^n(x-x_i)\end{array}$$

可得 $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)$。

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