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

牛顿迭代法

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

首先考虑对于$n=1$,$G(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)$

发表评论

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