牛顿迭代法以及其的应用(多项式$exp$,多项式$ln$,多项式开方)

牛顿迭代法

对于一个已知的函数G(x),我们要求一个多项式F(z)\pmod {z^n},满足方程
$$
G(F(z))\equiv0\pmod{z^n}
$$
牛顿迭代法是一个倍增解决的过程。

首先考虑对于n=1G(F(z))\equiv0\pmod{z},可以直接求出。

现在我们考虑n>1,假设对于\lceil{\frac{n}{2}}\rceil已经求出F_0(z)
$$
G(F_0(z))\equiv0\pmod{\lceil\frac{n}{2}\rceil}\
$$
要扩展到\bmod {z^n}下,我们考虑G(F(z))F'(z)处泰勒展开。(也就是把F(z)看成x,把已知多项式F_0(z)看成常数x_0,然后用泰勒展开,)
$$
G(F(z))=G(F_0(z))+G'(F(z)-F_0(z))+G^{(2)}(F(z)-F_0(z))^2+\cdots
$$
由于F(z)F_0(z)的最后\lceil \frac{n}{2} \rceil项相同,所以F(z)-F_0(z)的最后\lceil \frac{n}{2} \rceil项相同,所以上式等式右边只有前两项在\bmod{z^n}意义下为0。故,上式化为
$$
G(F(z))\equiv G(F_0(z))+G'(F_0(z))(F(z)-F_0(z))\pmod{z^n}
$$
又由于有条件G(F(z))\equiv0\pmod{z^n}​,整理得
$$
F(z)\equiv \frac{G'(F_0(z))F_0(z)-G(F_0(z))}{G'(F_0(z))}\pmod{z^n}
$$
也就是说
$$
F(z)\equiv F_0(z)-\frac{G(F_0(z))}{G'(F_0(z))}\pmod{z^n}
$$
牛顿迭代法在多项式中有广泛的运用,包括我们熟悉的多项式求逆,以及下面将介绍的多项式开方和多项式exp等。

多项式开方

对于多项式A(z),求一个B(z)满足B^2(z)=A(z)\pmod{z^n}

令牛顿迭代法中的G(F(z))=F^2(z)-A(z)

通过上述方法,我们先要求出G(F(z))\equiv 0\pmod{z}

注意,如果在模意义下,我们要求出a_0的二次剩余。

然后套用上面的牛顿迭代方法即可,最后整理出来
$$
F(z)\equiv \frac{F_0^2(z)+A(z)}{2F_0(z)}\pmod{z^n}
$$
复杂度T(n)=T(n/2)+O(nlogn)=O(nlogn)

多项式ln与多项式exp

定义

多项式的ln可以用ln(1-x)x_0=0处的泰勒展开(麦克劳林级数,Maclaurin series)定义。令f(x)=ln(1-x),不难得到
$$
\begin{aligned}
f(x)&=f(0)+f'(0)\frac{-x}{1!}+f”(0)\frac{(-x)^2}{2!}+\cdots\\
&=ln(1)+(-1)1^{-1}\cdot\frac{x}{1!}+(-1)^2(-1)1^{-2}\cdot\frac{x^2}{2!}+(-1)^3(-1)(-2)1^{-3}\cdot\frac{x^3}{3!}\cdots\\
&=-\sum_{i\geq 1}\frac{x}{i}
\end{aligned}
$$
也就是说
$$
ln(1-F(x))=-\sum_{i\geq 1}\frac{F^i(x)}{i}
$$
同样的,我们也可以定义多项式exp
$$
exp(F(z))=e^{F(z)}=\sum_{i\geq 0}\frac{F^i(z)}{i!}
$$

多项式ln

对于一个多项式F(z)=1+\sum_{i\geq 1}a_ix^i,现在要计算其对数lnF(z),注意到这里的F(x)是上述中的1-F(x)

我们考虑求导过后的结果
$$
(lnF(z))’=\frac{F'(z)}{F(z)}
$$
也就是说
$$
lnF(z)=\int\frac{F'(z)}{F(z)}
$$
其中多项式的求导和积分都可以在线性时间内完成,还需要一次多项式求逆,可以在O(nlogn)时间内完成。

所以总时间复杂度O(nlogn)

多项式exp

对于一个多项式A(z)=\sum_{i\geq1}a_iz^i,现在要计算其指数e^{A(z)}
$$
F(z)=e^{A(z)}
$$
也就是说
$$
lnF(z)-A(z)=0
$$
我们再次运用牛顿迭代法,令G(F(z))=lnF(z)-A(z),有初值
$$
G(F(z))\equiv 0\pmod{z}
$$
此时F(z)=[z^0]A(z),由于要求lnF(z),所以[z^0]F(z)=1,同时就限定了[z^0]A(z)=1

运用牛顿迭代,整理得
$$
F(z)=F_0(z)-F_0(z)lnF_0(z)+F_0(z)A(z)=F_0(z)(1-lnF_0(z)+A(z)) \pmod{z^n}
$$
复杂度T(n)=T(\frac{n}{2})+O(nlogn)=O(nlogn)

发表评论

电子邮件地址不会被公开。 必填项已用*标注