Taylor 展开
对于一个函数\(f(x),\)如果我们知道它在\(x_0\)处的各阶导数,那么:
\[f(x)=\sum_{i=0}^n \frac{f^{(i)}(x_0)(x-x0)^i}{i!} \]即 我们在\(x_0\)处逼近了\(f(x).\)
牛顿迭代
考虑求:
\[G(F(x))\equiv 0(\bmod x^n) \]对于\(n=1\)特殊求出来
考虑已经解决了:
\[G(F_0(x))\equiv 0(\bmod x^{\left\lceil \frac{n}{2}\right \rceil} ) \]考虑如何拓展到\(x^n.\)
在这里泰勒展开一下:
\[G(F(x))=\sum_{i=0}^\infty \frac{G^{(i)}(F_0(x))(F(x)-F_0(x))^i}{i!} \]注意到当\(i\ge 2\)时 \((F(x)-F_0(x))^i\)的最低非\(0\)次项的次数是严格大于\(2\left\lceil\frac{n}{2}\right\rceil,\)所以:
\[G(F(x))\equiv G(F_0(x))+(F(x)-F_0(x))G'(F_0(x))(\bmod x^n) \]注意到由题设得:
\[G(F(x))\equiv 0(\bmod x^n) \]所以:
\[G(F_0(x))+(F(x)-F_0(x))G'(F_0(x))\equiv 0(\bmod x^n) \]整理可以得到:
\[F(x)\equiv F_0(x)-\frac{G(F_0(x))}{G'(F_0(x))}(\bmod x^n) \]