多項式牛頓迭代
描述
給定多項式 \(g\left(x\right)\)，已知有 \(f\left(x\right)\) 滿足：
\[
g\left(f\left(x\right)\right)\equiv 0\pmod{x^{n}}
\]
求出模 \(x^{n}\) 意義下的 \(f\left(x\right)\)。
Newton's Method
考慮倍增。
首先當 \(n=1\) 時，\(\left[x^{0}\right]g\left(f\left(x\right)\right)=0\) 的解需要單獨求出。
假設現在已經得到了模 \(x^{\left\lceil\frac{n}{2}\right\rceil}\) 意義下的解 \(f_{0}\left(x\right)\)，要求模 \(x^{n}\) 意義下的解 \(f\left(x\right)\)。
將 \(g\left(f\left(x\right)\right)\) 在 \(f_{0}\left(x\right)\) 處進行泰勒展開，有：
\[
\sum_{i=0}^{+\infty}\frac{g^{\left(i\right)}\left(f_{0}\left(x\right)\right)}{i!}\left(f\left(x\right)-f_{0}\left(x\right)\right)^{i}\equiv 0\pmod{x^{n}}
\]
因為 \(f\left(x\right)-f_{0}\left(x\right)\) 的最低非零項次數最低為 \(\left\lceil\frac{n}{2}\right\rceil\)，故有：
\[
\forall 2\leqslant i:\left(f\left(x\right)-f_{0}\left(x\right)\right)^{i}\equiv 0\pmod{x^{n}}
\]
則：
\[
\sum_{i=0}^{+\infty}\frac{g^{\left(i\right)}\left(f_{0}\left(x\right)\right)}{i!}\left(f\left(x\right)-f_{0}\left(x\right)\right)^{i}\equiv g\left(f_{0}\left(x\right)\right)+g'\left(f_{0}\left(x\right)\right)\left(f\left(x\right)-f_{0}\left(x\right)\right)\equiv 0\pmod{x^{n}}
\]
\[
f\left(x\right)\equiv f_{0}\left(x\right)-\frac{g\left(f_{0}\left(x\right)\right)}{g'\left(f_{0}\left(x\right)\right)}\pmod{x^{n}}
\]
例題
多項式求逆
設給定函數為 \(h\left(x\right)\)，有方程：
\[
g\left(f\left(x\right)\right)=\frac{1}{f\left(x\right)}-h\left(x\right)\equiv 0\pmod{x^{n}}
\]
應用 Newton's Method 可得：
\[
\begin{aligned}
f\left(x\right)&\equiv f_{0}\left(x\right)-\frac{\frac{1}{f_{0}\left(x\right)}-h\left(x\right)}{-\frac{1}{f_{0}^{2}\left(x\right)}}&\pmod{x^{n}}\\
&\equiv 2f_{0}\left(x\right)-f_{0}^{2}\left(x\right)h\left(x\right)&\pmod{x^{n}}
\end{aligned}
\]
時間複雜度
\[
T\left(n\right)=T\left(\frac{n}{2}\right)+O\left(n\log{n}\right)=O\left(n\log{n}\right)
\]
多項式開方
設給定函數為 \(h\left(x\right)\)，有方程：
\[
g\left(f\left(x\right)\right)=f^{2}\left(x\right)-h\left(x\right)\equiv 0\pmod{x^{n}}
\]
應用 Newton's Method 可得：
\[
\begin{aligned}
f\left(x\right)&\equiv f_{0}\left(x\right)-\frac{f_{0}^{2}\left(x\right)-h\left(x\right)}{2f_{0}\left(x\right)}&\pmod{x^{n}}\\
&\equiv\frac{f_{0}^{2}\left(x\right)+h\left(x\right)}{2f_{0}\left(x\right)}&\pmod{x^{n}}
\end{aligned}
\]
時間複雜度
\[
T\left(n\right)=T\left(\frac{n}{2}\right)+O\left(n\log{n}\right)=O\left(n\log{n}\right)
\]
多項式 exp
設給定函數為 \(h\left(x\right)\)，有方程：
\[
g\left(f\left(x\right)\right)=\ln{f\left(x\right)}-h\left(x\right)\pmod{x^{n}}
\]
應用 Newton's Method 可得：
\[
\begin{aligned}
f\left(x\right)&\equiv f_{0}\left(x\right)-\frac{\ln{f_{0}\left(x\right)}-h\left(x\right)}{\frac{1}{f_{0}\left(x\right)}}&\pmod{x^{n}}\\
&\equiv f_{0}\left(x\right)\left(1-\ln{f_{0}\left(x\right)+h\left(x\right)}\right)&\pmod{x^{n}}
\end{aligned}
\]
時間複雜度
\[
T\left(n\right)=T\left(\frac{n}{2}\right)+O\left(n\log{n}\right)=O\left(n\log{n}\right)
\]
本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用