【学习笔记】牛顿迭代

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) \]

上一篇:最大公约数详解


下一篇:数论之神