多项式牛顿迭代

用于寻找多项式(0)点

已知多项式(G)，求多项式(F)满足(G(F(x))≡0(mod\, x^n))

套路地考虑，假设我们已经求出了(G(F_0(x))≡0(mod\, x^{frac{n}{2}}))

我们把(G(F_0(x)))在(F_0(x))这里泰勒展开得到

(G(F_0(x))=sumlimits_{n=0}^{infty}frac{G^{(n)}(F_0(x))}{n!}(F(x)-F_0(x))^n(mod\, x^n))

由于(F(x)≡F_0(x)(mod\, frac{n}{2}))

所以(F(x)-F_0(x))得到的最低次项系数至少是(frac{n}{2})

所以在泰勒展开式中，(nge 2)的项全部被(x^n)模掉了，只考虑前两项就好

得到(G(F(x))=G(F_0(x))+frac{G'(F_0(x))}{1!}(F(x)-F_0(x))(mod\, x^n))

由于

(G(F(x))≡0(mod\, x^n))

所以

(G(F_0(x))+frac{G'(F_0(x))}{1!}(F(x)-F_0(x))(mod\, x^n)≡0)

然而我们要求(F(x))，变形一下得到结论：

(F(x)=F_0(x)-frac{G(F_0(x))}{G'(F_0(x))}(mod\, x^n))

然后当然是背过啊