多项式牛顿迭代
设
\[f(g(x))\equiv 0 (mod\ x^n)
\]
求出此模意义下的\(g(x)\)
当\(n=1\)时，单独求出\([x^0]f(g(x))\)
假设已经得到了模\(x^{\lceil\frac{n}{2}\rceil}\)意义下的解\(g_0(x)\)，要求模\(x^{n}\)意义下的解\(g(x)\)
将\(f(g(x))\)在\(g_0(x)\)处泰勒展开得到
\[\sum_{n}\frac{f^{(n)}(g_0(x))}{n!}(g(x)-g_0(x))^n\equiv 0\ (mod\ x^n)
\]
因为\(g(x)-g_0(x)\)的最低非零次项的次数为\(\lceil\frac{n}{2}\rceil\)，故有
\[\forall n\geq 2,(g(x)-g_0(x))^n\equiv 0\ (mod\ x^n)
\]
则
\[\sum_{n}\frac{f^{(n)}(g_0(x))}{n!}(g(x)-g_0(x))^n\equiv f(g_0(x))+f‘(g_0(x))(g(x)-g_0(x))\ (mod\ x^n)\g(x)\equiv g_0(x)-\frac{f(g_0(x))}{f‘(g_0(x))}\ (mod\ x^n)\\]
多项式牛顿迭代
原文：https://www.cnblogs.com/knife-rose/p/15345059.html
