【学习笔记】形式幂级数的牛顿迭代

多项式的牛顿迭代,是借助泰勒展开进行的一种对于形式幂级数的常规操作,解决的主要问题是:

给定形式幂级数$G$,求解$F$。

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

$1$

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

首先之前标准的式子左边在$F_0(x)$处进行泰勒展开,可以得到:

但是我们考虑在$\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)=0~(\bmod~x^n)$,所以我们可以得到:

于是直接递推就好。

$2$

接下来看几个课后练习

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

令$T(G)=G^2-F$,套用公式可以得到:

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

按照套路应该两边同时取$\ln$:

之后我们令$T(G)=\ln G-F$,套用公式可以得到

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

套用公式可以得到

然后就算这个东西就变成$\log^3~\text{or}~\log^2$可以算的东西了。

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

同样的台词……

然后这东西好像是可以$\log^2$做的……不过有些小朋友特别喜欢出无脑的多项式板子,像这种东西就很没有意思qaq。