多项式牛顿迭代

描述

给定多项式 $G(x,y)$，已知多项式 $f\left(x\right)$ 满足：

$$G(x,f\left(x\right))\equiv 0(\mathrm{mod}{x}^n)$$

且存在数值 $f_1$ 使 $G(x,y)$ 满足以下条件：

• $G(0,f_1)=0$；
• ${\displaystyle \frac{\partial G}{\partial y}}(0,f_1)\ne 0$。

求出模 $x^n$ 意义下的 $f\left(x\right)$。

Newton's Method

考虑倍增。

首先当 $n=1$ 时，$\left[x^0\right]G(x,f\left(x\right))=0$ 的解需要单独求出，假设中的 $f_1$ 即为一个解。

假设现在已经得到了模 $x^{\lceil \frac{n}{2}\rceil }$ 意义下的解 $f_{\lceil \frac{n}{2}\rceil }\left(x\right)$，要求模 $x^n$ 意义下的解 $f\left(x\right)=f_n\left(x\right)$。

将 $G(x,f(x))$ 对 $f(x)$ 在 $f(x)=f_{\lceil \frac{n}{2}\rceil }\left(x\right)$ 处进行泰勒展开，有：

$$\sum _{i=0}^{+\mathrm{\infty }}\frac{\frac{{\partial }^{i}G}{\partial y^i}(x,f_{\lceil \frac{n}{2}\rceil }\left(x\right))}{i!}{(f\left(x\right)-f_{\lceil \frac{n}{2}\rceil }\left(x\right))}^i\equiv 0(\mathrm{mod}{x}^n)$$

因为 $f\left(x\right)-f_{\lceil \frac{n}{2}\rceil }\left(x\right)$ 的最低非零项次数最低为 $\lceil \frac{n}{2}\rceil$，故有：

$$\mathrm{\forall }2⩽i:{(f\left(x\right)-f_{\lceil \frac{n}{2}\rceil }\left(x\right))}^i\equiv 0(\mathrm{mod}{x}^n)$$

则：

$$\begin{array}{rl}\sum _{i=0}^{+\mathrm{\infty }}\frac{\frac{{\partial }^{i}G}{\partial y^i}(x,f_{\lceil \frac{n}{2}\rceil }\left(x\right))}{i!}{(f\left(x\right)-f_{\lceil \frac{n}{2}\rceil }\left(x\right))}^i& \equiv G(x,f_{\lceil \frac{n}{2}\rceil }\left(x\right))+\frac{\partial G}{\partial y}(x,f_{\lceil \frac{n}{2}\rceil }\left(x\right))[f\left(x\right)-f_{\lceil \frac{n}{2}\rceil }\left(x\right)]\\ & \equiv 0(\mathrm{mod}{x}^n)\end{array}$$

$$f_n\left(x\right)\equiv f_{\lceil \frac{n}{2}\rceil }\left(x\right)-\frac{G(x,f_{\lceil \frac{n}{2}\rceil }\left(x\right))}{\frac{\partial G}{\partial y}(x,f_{\lceil \frac{n}{2}\rceil }\left(x\right))}(\mathrm{mod}{x}^n)$$

或者

$$f_{2n}\left(x\right)\equiv f_n\left(x\right)-\frac{G(x,f_n\left(x\right))}{\frac{\partial G}{\partial y}(x,f_n\left(x\right))}(\mathrm{mod}{x}^{2n})$$

例题

多项式求逆

设给定函数为 $h\left(x\right)$，有：

$$G(x,y)=\frac{1}{y}-h\left(x\right)$$

应用 Newton's Method 可得：

$$\begin{array}{rlr}{f}_{2n}\left(x\right)& \equiv f_n\left(x\right)-\frac{1/f_n\left(x\right)-h\left(x\right)}{-1/f_n^2\left(x\right)}& (\mathrm{mod}{x}^{2n})\\ & \equiv 2f_n\left(x\right)-f_n^2\left(x\right)h\left(x\right)& (\mathrm{mod}{x}^{2n})\end{array}$$

时间复杂度

$$T\left(n\right)=T\left(\frac{n}{2}\right)+O(n\log n)=O(n\log n)$$

多项式开方

设给定函数为 $h\left(x\right)$，有：

$$G(x,y)=y^2-h\left(x\right)\equiv 0$$

应用 Newton's Method 可得：

$$\begin{array}{rlr}{f}_{2n}\left(x\right)& \equiv f_n\left(x\right)-\frac{f_n^2\left(x\right)-h\left(x\right)}{2f_n\left(x\right)}& (\mathrm{mod}{x}^{2n})\\ & \equiv \frac{f_n^2\left(x\right)+h\left(x\right)}{2f_n\left(x\right)}& (\mathrm{mod}{x}^{2n})\end{array}$$

时间复杂度

$$T\left(n\right)=T\left(\frac{n}{2}\right)+O(n\log n)=O(n\log n)$$

多项式指数函数

设给定函数为 $h\left(x\right)$，有：

$$G(x,y)=\ln y-h\left(x\right)$$

应用 Newton's Method 可得：

$$\begin{array}{rlr}{f}_{2n}\left(x\right)& \equiv f_n\left(x\right)-\frac{\ln f_n\left(x\right)-h\left(x\right)}{1/f_n\left(x\right)}& (\mathrm{mod}{x}^{2n})\\ & \equiv f_n\left(x\right)(1-\ln f_n\left(x\right)+h\left(x\right))& (\mathrm{mod}{x}^{2n})\end{array}$$

时间复杂度

$$T\left(n\right)=T\left(\frac{n}{2}\right)+O(n\log n)=O(n\log n)$$

手算演示

为了方便理解，这里举几个例子演示一下算法流程。

复数多项式模多项式的平方根

假设 $h$ 是一个不被 $x$ 整除（有常数项）的复数多项式，求它对模 $x^n$ 的平方根。

我们有方程：

$$G(f(x))=f^2(x)-h(x)\equiv 0(\mathrm{mod}{x}^n)$$

Taylor 展开 $G$ 得到下式。注意这里是对 $f$ 的展开，所以导数都是对 $f$ 的偏导数，$x$ 在这里是当成常数算的。

$$G(f(x))=\sum _{i=0}^{+\mathrm{\infty }}\frac{G^{\left(i\right)}(f_0(x))}{i!}{(f(x)-f_0(x))}^i=G(f_0(x))+2f_0(x)(f(x)-f_0(x))+(f(x)-f_0(x){)}^2$$

用倍增计算。假设倍增中的中间结果是 $f_0(x),f_1(x),\dots ,f_j(x)$，或者数学严谨地说 $f_j(x)$ 是满足 $G(f_j(x))\equiv 0(\mathrm{mod}{x}^{2^j})$ 的一个复数多项式，且为了唯一性它同时满足以下两个条件：

• $f_j(x)$ 次数不超过 $x^{2^j}$；
• $f_{j+k}(x)-f_j(x)\equiv 0(\mathrm{mod}{x}^{2^j})$，对所有 $k$。

把 $f_{j+1}(x)$ 和 $f_j(x)$ 代入上面的式子就有：

$$G(f_{j+1}(x))=G(f_j(x))+2f_j(f_{j+1}(x)-f_j(x))+(f_{j+1}(x)-f_j(x){)}^2\equiv 0(\mathrm{mod}{x}^{2^{j+1}})$$

显然 $f_{j+1}(x)-f_j(x)$ 必然是 $x^{2^j}$ 的倍数。于是得到

$$f_{j+1}(x)\equiv f_j(x)-\frac{f_j^2(x)-h(x)}{2f_j(x)}\equiv \frac{f_j(x{)}^2+h(x)}{2f_j(x)}(\mathrm{mod}{x}^{2^{j+1}})$$

如果 $f_j(x)$ 存在，那么 $2f_j(x)$ 不被 $x$ 整除（有常数项），所以必然有模 $x^{2^{j+1}}$ 的逆元。因此数列 $f_0,f_1\dots ,f_j$ 存在当且仅当 $f_0$ 存在。不被 $x$ 整除的复数多项式 $h(x)$ 模 $x$ 的平方根是一定存在的，因为 $h(x)$ 模掉 $x$ 就是个普通非零复数，一定有两个平方根。所以可以对所有有常数项的 $h(x)$ 用这个算法。

选 $h(x)=x+1$ 举例计算如下：

• $f_0(x)=1$,$f_1(x)={\displaystyle \frac{1^2+x+1}{2\times 1}}\mathrm{mod}{x}^2={\displaystyle \frac{1}{2}}x+1$,$f_2(x)={\displaystyle \frac{{({\displaystyle \frac{1}{2}}x+1)}^2+x+1}{2\times ({\displaystyle \frac{1}{2}}x+1)}}\mathrm{mod}{x}^4={\displaystyle \frac{1}{16}}{x}^3-{\displaystyle \frac{1}{8}}{x}^2+{\displaystyle \frac{1}{2}}x+1$,$\dots$
• $f_0(x)=-1$,$f_1(x)={\displaystyle \frac{(-1{)}^2+x+1}{2\times (-1)}}\mathrm{mod}{x}^2=-{\displaystyle \frac{1}{2}}x-1$,$\dots$（等于前一个取负）

可以验证两个都是正确的模平方根多项式列。

整数模素数幂的平方根

牛顿迭代算法还可以迁移到整数模素数的幂的情况。 假设 $h$ 是一个不被 3 整除的「方便的」整数。（「方便」指「必然有解」，具体条件后文再言）假设要算 $h$ 在模 $3^n$ 意义下的平方根 $f$。有方程：

$$G\left(f\right)=f^2-h\equiv 0(\mathrm{mod}{3}^n)$$

Taylor 展开 $G$ 得到：

$$G(f)=\sum _{i=0}^{+\mathrm{\infty }}\frac{G^{\left(i\right)}\left(f_0\right)}{i!}{(f-f_0)}^i=G(f_0)+2f_0(f-f_0)+(f-f_0{)}^2$$

用倍增计算。假设倍增中得到的中间结果是 $f_0,f_1,\dots ,f_j$，或者严谨地说 $f_j$ 是满足 $G(f_j)\equiv 0(\mathrm{mod}{3}^{2^j})$ 的一个整数，且为了唯一性它同时满足以下两个条件：

• $0<f_j<3^{2^j}$；
• $f_{j+k}-f_j\equiv 0(\mathrm{mod}{3}^{2^j})$，对所有 $k$。

把 $f_{j+1}$ 和 $f_j$ 代入上面的式子就有：

$$G(f_{j+1})=G(f_j)+2f_j(f_{j+1}-f_j)+(f_{j+1}-f_j{)}^2\equiv 0(\mathrm{mod}{3}^{2^{j+1}})$$

显然 $f_{j+1}-f_j$ 必然是 $3^{2^j}$ 的倍数。于是得到

$$f_{j+1}\equiv f_j-\frac{f_j^2-h}{2f_j}\equiv \frac{f_j^2+h}{2f_j}(\mathrm{mod}{3}^{2^{j+1}})$$

如果 $f_j$ 存在，那么 $2f_j$ 不被 $3$ 整除，所以必然有模 $3^{2^{j+1}}$ 的逆元。因此数列 $f_0,f_1\dots ,f_j$ 存在当且仅当 $f_0$ 存在。不被 3 整除的整数 $h$ 模 $3$ 的平方根要么不存在，要么有两个。所以 $h$ 有模 $3$ 平方根就是整个算法能跑的唯一条件。

这里选 $h=46$ 实际计算示例。

• $f_0=1$,$f_1={\displaystyle \frac{1^2+46}{2\times 1}}\mathrm{mod}9=1$,$f_2={\displaystyle \frac{1^2+46}{2\times 1}}\mathrm{mod}81=64$,$f_3={\displaystyle \frac{{64}^2+46}{2\times 64}}\mathrm{mod}6561=955$,$\dots$
• $f_0=2$,$f_1={\displaystyle \frac{2^2+46}{2\times 2}}\mathrm{mod}9=8$,$f_2={\displaystyle \frac{8^2+46}{2\times 8}}\mathrm{mod}81=17$,$f_3={\displaystyle \frac{{17}^2+46}{2\times 17}}\mathrm{mod}6561=5606$,$\dots$（等于前一个取负）

可以验证一下两个都是正确的模平方根数列。

代数证明

这一节对前文进行引申，用抽象代数的语言证明只要 $f$ 满足初始解条件，牛顿法对所有的 $n$ 都能给出解，并且可以得到全部的解。

有解的证明

证明

对所有 $s\in R$，

$$\begin{array}{rl}f(r+sp)& =\sum _{i\ge 0}{a}_i(r+sp{)}^i\\ & =\sum _{i\ge 0}{a}_i{r}^i+sp\sum _{i\ge 1}i{a}_i{r}^{i-1}+s^2{p}^2(\dots )\\ & =f(r)+sp{f}^{\prime }(r)+s^2{p}^2(\frac{f^{″}(r)}{2!}+\cdots ),\end{array}$$

所以

$$f(r+sp)\in R{p}^2⟺f(r)+f^{\prime }(r)sp\in R{p}^2$$

因为 $f(r)\in Rp$，且 $f^{\prime }(r)$ 可逆，所以取 $sp=-{\displaystyle \frac{f(r)}{f^{\prime }(r)}}$ 即可，这里 ${\displaystyle \frac{1}{f^{\prime }(r)}}$ 是模 $p^2$ 意义下的逆元。因为 $f^{\prime }(r)$ 在模 $p$ 意义下可逆，所以它在模 $p^2$ 意义下也必定存在逆元：设有 $a,b,c\in R$ 使 $a{f}^{\prime }(r)=bp+1$ 和 $f(r)=cp$，那么 $(a^2{f}^{\prime }(r)-2)f^{\prime }(r)=b^2{p}^2+1$，故可以取 $s=c(2-a^2{f}^{\prime }(r))$。

对于域 $k$ 上的多项式环 $k[X]$，设有 $G(X,Y)\in k[X,Y]$ 和 $f_n\in k[X]$ 使 $G(X,f_n(X))\in k[X]X^n$，那么应用引理 1 就可得到

$$G(X,f_n(X)-\frac{G(X,f_n(X))}{\frac{\partial G}{\partial Y}(X,f_n(X))})\equiv 0(\mathrm{mod}{X}^{2n})$$

而倍增的初始条件只要有 $f_1\in k$ 使得 $G(X,f_1)\equiv 0(\mathrm{mod}X)$ 和 ${\displaystyle \frac{\partial G}{\partial Y}}(X,f_1)\not\equiv 0(\mathrm{mod}X)$。后一个条件保证了 ${\displaystyle \frac{\partial G}{\partial Y}}$ 有非零常数项，同时因为 $X|{\displaystyle \frac{G(X,f_n(X))}{\frac{\partial G}{\partial Y}(X,f_n(X))}}$，故而对所有的 $n$，${\displaystyle \frac{\partial G}{\partial Y}}(X,f_n)$ 总是模 $X^n$ 意义下可逆的，也就满足了下一次迭代的条件。

得到全部解的证明

引理 2

若 $R$ 为 UFD，$f,r,p$ 定义同引理 1。则引理 1 给出的 $r-{\displaystyle \frac{f(r)}{f^{\prime }(r)}}$ 是模 $p^2$ 意义下唯一满足以下两条件的 $x$ 的值：

• $f(x)\in R{p}^2$
• $x-r\in Rp$

亦即

$$\mathrm{\forall }x\in R,p^2\mid f(x)\wedge p\mid (x-r)⟹x\equiv r-{\displaystyle \frac{f(r)}{f^{\prime }(r)}}(\mathrm{mod}{p}^2)$$

牛顿法可以保证得到模 $X^{2^n}$ 的全部解。假设 $G(X,h)\equiv 0(\mathrm{mod}{X}^{2^n})$，那么令 $h_{2^i}:=h(\mathrm{mod}{X}^{2^i})$，然后取 $f_1=h_1$ 并用牛顿法，根据引理 2 可得 $f_{2^i}\equiv h_{2^i}(\mathrm{mod}{X}^{2^i})$，所以一定有 $f_{2^n}=h$。

上面的论证也说明了，在 ${\displaystyle \frac{\partial G}{\partial y}}(0,y)$ 永远可逆时，$G(X,f)\equiv 0(\mathrm{mod}{X}^n)$ 的解的个数等于 $G(0,f)\equiv 0(\mathrm{mod}X)$ 的解的个数。这个结论并非平凡。请看下面的例子。

本页面最近更新：2025/5/3 19:43:25，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：shuzhouliu, 97littleleaf11, c-forrest, Enter-tainer, fps5283, H-J-Granger, Ir1d, Marcythm, Tiphereth-A, TrisolarisHD, zjkmxy
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用