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

多项式的多点求值

描述

给出一个多项式 $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& =\left\{x_1,x_2,\dots ,x_{\lfloor \frac{n}{2}\rfloor }\right\}\\ X_1& =\left\{x_{\lfloor \frac{n}{2}\rfloor +1},x_{\lfloor \frac{n}{2}\rfloor +2},\dots ,x_n\right\}\end{array}$$

构造多项式

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

则有 $\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))$$

则有 $\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\left(n\log n\right)=O\left(n{\log }^{2}n\right)$$

多项式的快速插值

描述

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

$$X=\left\{\left(x_0,y_0\right),\left(x_1,y_1\right),\dots ,\left(x_n,y_n\right)\right\}$$

求一个 $n$ 次多项式 $f\left(x\right)$ 使得其满足 $\forall \left(x,y\right)\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)$。