形式幂级数的牛顿迭代

多项式的牛顿迭代,是借助泰勒展开进行的一种对于形式幂级数的常规操作,解决的主要问题是:
$$
G(F) \equiv 0~(\bmod x^n)
$$
给定形式幂级数$G$,求解$F$。

而解决途径则是通过对降半次的$F_0$向上迭代解决的。

$1$

假设我们现在已经求出了$G(F_0)\equiv 0~(\bmod~x^{\frac{n}{2}})$

首先之前标准的式子左边在$F_0(x)$处进行泰勒展开,可以得到:
$$
\begin{aligned} G(F(x)) &=G\left(F_{0}(x)\right) \\ &+\frac{G^{\prime}\left(F_{0}(x)\right)}{1 !}\left(F(x)-F_{0}(x)\right) \\ &+\frac{G^{\prime \prime}\left(F_{0}(x)\right)}{2 !}\left(F(x)-F_{0}(x)\right)^{2} \\ &+\cdots (\mod ~x^n)\end{aligned}
$$

但是我们考虑在$\mod ~x^n$意义下,$F$和$F_0$的最后$\frac{n}{2}$项相同,所以在上面的式子,$(F-F_0)^k,~k>2$时,最低次项的次数一定会大于$2\cdot\lfloor \frac{n}{2}\rfloor$,也就是说在$\mod~x^n$意义下都是全0项。那么我们就可以得到:

$$
G(F(x)) \equiv G\left(F_{0}(x)\right)+G^{\prime}\left(F_{0}(x)\right)\left(F(x)-F_{0}(x)\right) \quad\left(\bmod x^{n}\right)
$$
然后因为$G(F)=0~(\bmod~x^n)$,所以我们可以得到:
$$
F(x)\equiv F_0(x) - \frac{G(F_0(x))}{G^{\prime}\left(F_{0}(x)\right)} \quad\left(\bmod x^{n}\right)
$$
于是直接递推就好。

$2$

接下来看几个课后练习

$(1)~~~G^2\equiv F~(\bmod~x^n)$

$$
\begin{aligned}
G^2&=F\\
G^2-F&=0\\
\end{aligned}
$$
令$T(G)=G^2-F$,套用公式可以得到:
$$
\begin{aligned}
T(G)&=G^2-F,F\Longleftrightarrow \mathbb{C} \\
G &= G_h-\frac{T(G_h)}{T’(G_h)}\\
\Longrightarrow G&=G_h-\frac{G_h^2-F}{2G_h}\\
\Longrightarrow G&=\frac{G_h^2+F}{2G_h}
\end{aligned}
$$

$(2)~G\equiv e^{F}~(\bmod ~x^n)$

按照套路应该两边同时取$\ln$:
$$
\ln G=F~(\bmod~x^n)
$$
之后我们令$T(G)=\ln G-F$,套用公式可以得到
$$
\begin{aligned}
G &= G_h - \frac{T(G_h)}{T’(G_h)}\\
\Longrightarrow G &= G_h-\frac{\ln G_h -F}{\frac{1}{G_h}}\\
\Longrightarrow G &=G_h-G_h\ln G_h+G_hF\\
\Longrightarrow G &=G_h(1-\ln G_h+F)\\
\end{aligned}
$$

$(3)~G^k\equiv F~(\bmod ~x^n)$

$$
T(G) = G^k-F=0
$$

套用公式可以得到
$$
\begin{aligned}
G &= G_h - \frac{T(G_h)}{T’(G_h)}\\
\Longrightarrow G &= G_h-\frac{G_h^k-F}{kG_h^{k-1}}\\
\Longrightarrow G &=\frac{(k-1)G_h^k+F}{kG_h^{k-1}}
\end{aligned}
$$
然后就算这个东西就变成$\log^3~\text{or}~\log^2$可以算的东西了。

$(4)~2G \ln G\equiv F~(\bmod x^n)$

$$
T(G)\equiv 2G\ln G-F~(\bmod~x^n)
$$

同样的台词……
$$
\begin{aligned}
G &= G_h - \frac{T(G_h)}{T’(G_h)}\\
\Longrightarrow G &= G_h-\frac{2G_h\ln G_h-F}{2\ln G_h+2G_h\cdot \frac{1}{G_h}}\\
\Longrightarrow G &=\frac{2G_h\ln G_h-F}{(2\ln+1)G_h}
\end{aligned}
$$
然后这东西好像是可以$\log^2$做的……不过有些小朋友特别喜欢出无脑的多项式板子,像这种东西就很没有意思qaq。