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

多项式的多点求值(multi-point evaluation)是给出一个多项式 A(x),和 n 个点 x_0, x_1, \cdots, x_{n-1},要求求出 A(x_0), A(x_1), \cdots, A(x_{n-1})

相反的,多项式的插值(interpolation)是给出 n+1 个点 (x_0, y_0), (x_1, y_1), \cdots, (x_n, y_n),求出一个 n 次多项式,使得这些点都在这个多项式上

这两个问题实际上是在多项式的点值表示(point-value representation)和系数表示(coefficient representation)之间转换的方法,在快速傅里叶变换中由于带入值的特殊性质,可以在 \mathcal O(n\log n) 的之间内将两种东西互相转换,但是,如果是任意给定点要求求值或者插值,就没有比较好的性质可以利用,但是仍然有比较快速的方法来计算它们

多项式的多点求值

给出一个多项式 A(x),和 n 个点 x_0, x_1, \cdots, x_{n-1},如果要求 A(x) 在各个点处的值直接处理肯定是比较慢的,而且似乎也没有什么优化的空间,现在试试看能不能像在进行快速傅里叶变换的时候一样,用分治来把问题规模减少

有两种方法,一是先把系数分成两半,另一种是先把要求的值分成两半,但是最后要求的是两个都要分成两半才可以把问题的规模减半。我们把要求的值分成两半

 \begin{eqnarray*} X^{[0]} &=& \{x_0, x_1, \cdots, x_{\lfloor \frac{n}{2} \rfloor}\} \\ X^{[1]} &=& \{x_{\lfloor \frac{n}{2} \rfloor+1},x_{\lfloor \frac{n}{2} \rfloor+2}, \cdots, x_{n-1}\} \end{eqnarray*}

现在考虑的是如何才可以把系数减半,我们来想想倒过来的过程,现在已经求出了这 \lfloor \frac{n}{2} \rfloor 个值,如果插值回来的话,得到的多项式的次数是 \lfloor \frac{n}{2} \rfloor,我们记用 X^{[0]}, X^{[1]} 插值得到的多项式为 A^{[0]}(x), A^{[1]}(x),这样的话如果可以求出它们,就可以把整个问题的规模减半了

考虑这两个多项式

 \begin{eqnarray*} P^{[0]}(x) &=& \prod_{i=0}^{\lfloor \frac{n}{2} \rfloor} (x-x_i) \\ P^{[1]}(x) &=& \prod_{i=\lfloor \frac{n}{2} \rfloor+1}^{n-1} (x-x_i) \end{eqnarray*}

这两个多项式分别在 x \in X^{[0]}x \in x^{[1]} 的时候为 0,而且次数都是我们要求的 \lfloor \frac{n}{2} \rfloor,现在可以把 A(x) 表示成这样

 A(x) = D(x)P^{[0]}(x) + A^{[0]}(x)

这样得到的 A^{[0]}(x) 满足在 x \in x^{[0]} 的时候 D(x)P^{[0]}(x)0,这样的话 A(x) = A^{[0]}(x),因此就表示出了 A^{[0]}(x)

再看这个式子,相当于是多项式的求模(不会看我这篇文章),也就是

 A^{[0]}(x) \equiv A(x) \pmod {P^{[0]}(x)}

对于 X^{[1]} 的部分,处理方法也是一样的

最后多项式求模的时间复杂度是 \mathcal O(n \log n),那么多项式多点求值的时间复杂度就是

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

多项式的快速插值

好,现在来看多项式的插值,给出了 n + 1 个点的集合

X = \{(x_i, y_i) : 0 \leq i \leq n\}

现在要求一个 n 次多项式 A(x) 满足 \forall (x, y) \in X, A(x) = y

如果直接用 Lagrange 插值公式来进行插值,那么时间复杂度是 \mathcal O(n^2) 的,现在再来考虑分治方法,我们把要插值的点分成两半

 \begin{eqnarray*} X^{[0]} &=& \{(x_i, y_i) : 0 \leq i \leq \lfloor \frac{n}{2} \rfloor \} \\ X^{[1]} &=& \{(x_i, y_i) : \lfloor \frac{n}{2} \rfloor < i \leq n\} \end{eqnarray*}

现在假设已经求出了 X^{[0]} 的插值多项式 A^{[0]}(x),考虑如何修改它使得它变成 A(x),假设

 P(x) = \prod_{i=0}^{\lfloor \frac{n}{2} \rfloor} (x-x_i)

那么构造 A(x),使其满足

 A(x) = A^{[1]}(x)P(x) + A^{[0]}(x)

其中 A^{[1]}(x) 是一个未知的多项式,由于 \forall (x, y) \in X^{[0]}, P(x) = 0, A^{[0]}(x) = y,这样的话就满足 X^{[0]} 的点都在 A(x) 上,问题就变成要将 X^{[1]} 内的点插值,使得

 \forall (x_i, y_i) \in X^{[1]}, y_i = A^{[1]}(x_i)P(x_i) + A^{[0]}(x_i)

化简之后得到

 A^{[1]}(x_i) = \frac{A^{[0]}(x_i)-y_i}{P(x_i)}

这样就得到了新的待插值点,利用同样的方法求出插值出 A^{[1]} 然后合并就可以了

由于每一次都要多点求值求出 X^{[1]}P(x)A^{[0]}(x) 的值,最终复杂度是

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

代码?我还没写出来有空再贴QAQ

Miskcoo's Space,版权所有丨如未注明,均为原创
转载请注明转自:http://blog.miskcoo.com/2015/05/polynomial-multipoint-eval-and-interpolation

miskcoo

顺利从福州一中毕业!感觉大学周围都是聚聚十分可怕QAQ 想要联系的话欢迎发邮件:miskcoo [at] gmail [dot] com

2 thoughts on “多项式的多点求值与快速插值

Leave a Reply

Your email address will not be published. Required fields are marked *

NOTE: If you want to add mathematical formulas, use $$ to wrap them. For example, use $$x_0$$ to get $$x_0$$.

If you want to get a newline, hit Enter twice, that is, use double newlines to get a newline.