多项式牛顿迭代

描述

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

G (x, f (x)) \equiv 0 (\mod x^{n})

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

$G (0, f_{1}) = 0$ ；
$\frac{\partial G}{\partial y} (0, f_{1}) \neq 0$ 。

求出模 $x^{n}$ 意义下的 $f (x)$ 。

Newton's Method

考虑倍增。

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

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

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

\sum_{i = 0}^{+ \infty} \frac{\frac{\partial^{i} G}{\partial y^{i}} (x, f_{⌈ \frac{n}{2} ⌉} (x))}{i!} {(f (x) - f_{⌈ \frac{n}{2} ⌉} (x))}^{i} \equiv 0 (\mod x^{n})

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

\forall 2 ⩽ i : {(f (x) - f_{⌈ \frac{n}{2} ⌉} (x))}^{i} \equiv 0 (\mod x^{n})

则：

\begin{aligned} \sum_{i = 0}^{+ \infty} \frac{\frac{\partial^{i} G}{\partial y^{i}} (x, f_{⌈ \frac{n}{2} ⌉} (x))}{i!} {(f (x) - f_{⌈ \frac{n}{2} ⌉} (x))}^{i} & \equiv G (x, f_{⌈ \frac{n}{2} ⌉} (x)) + \frac{\partial G}{\partial y} (x, f_{⌈ \frac{n}{2} ⌉} (x)) [f (x) - f_{⌈ \frac{n}{2} ⌉} (x)] \\ \equiv 0 (\mod x^{n}) \end{aligned}

f_{n} (x) \equiv f_{⌈ \frac{n}{2} ⌉} (x) - \frac{G (x, f_{⌈ \frac{n}{2} ⌉} (x))}{\frac{\partial G}{\partial y} (x, f_{⌈ \frac{n}{2} ⌉} (x))} (\mod x^{n})

或者

f_{2 n} (x) \equiv f_{n} (x) - \frac{G (x, f_{n} (x))}{\frac{\partial G}{\partial y} (x, f_{n} (x))} (\mod x^{2 n})

例题

多项式求逆

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

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

应用 Newton's Method 可得：

\begin{aligned} f_{2 n} (x) & \equiv f_{n} (x) - \frac{1 / f_{n} (x) - h (x)}{- 1 / f_{n}^{2} (x)} & (\mod x^{2 n}) \\ \equiv 2 f_{n} (x) - f_{n}^{2} (x) h (x) & (\mod x^{2 n}) \end{aligned}

时间复杂度

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

多项式开方

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

G (x, y) = y^{2} - h (x) \equiv 0

应用 Newton's Method 可得：

\begin{aligned} f_{2 n} (x) & \equiv f_{n} (x) - \frac{f_{n}^{2} (x) - h (x)}{2 f_{n} (x)} & (\mod x^{2 n}) \\ \equiv \frac{f_{n}^{2} (x) + h (x)}{2 f_{n} (x)} & (\mod x^{2 n}) \end{aligned}

时间复杂度

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

多项式指数函数

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

G (x, y) = \ln y - h (x)

应用 Newton's Method 可得：

\begin{aligned} f_{2 n} (x) & \equiv f_{n} (x) - \frac{\ln f_{n} (x) - h (x)}{1 / f_{n} (x)} & (\mod x^{2 n}) \\ \equiv f_{n} (x) (1 - \ln f_{n} (x) + h (x)) & (\mod x^{2 n}) \end{aligned}

时间复杂度

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

手算演示

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

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

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

我们有方程：

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

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

G (f (x)) = \sum_{i = 0}^{+ \infty} \frac{G^{(i)} (f_{0} (x))}{i!} {(f (x) - f_{0} (x))}^{i} = G (f_{0} (x)) + 2 f_{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 (\mod x^{2^{j}})$ 的一个复数多项式，且为了唯一性它同时满足以下两个条件：

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

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

G (f_{j + 1} (x)) = G (f_{j} (x)) + 2 f_{j} (f_{j + 1} (x) - f_{j} (x)) + (f_{j + 1} (x) - f_{j} (x))^{2} \equiv 0 (\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)}{2 f_{j} (x)} \equiv \frac{f_{j} (x)^{2} + h (x)}{2 f_{j} (x)} (\mod x^{2^{j + 1}})

如果 $f_{j} (x)$ 存在，那么 $2 f_{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) = \frac{1^{2} + x + 1}{2 \times 1} \mod x^{2} = \frac{1}{2} x + 1$ , $f_{2} (x) = \frac{{(\frac{1}{2} x + 1)}^{2} + x + 1}{2 \times (\frac{1}{2} x + 1)} \mod x^{4} = \frac{1}{16} x^{3} - \frac{1}{8} x^{2} + \frac{1}{2} x + 1$ , $\dots$
$f_{0} (x) = - 1$ , $f_{1} (x) = \frac{(- 1)^{2} + x + 1}{2 \times (- 1)} \mod x^{2} = - \frac{1}{2} x - 1$ , $\dots$ （等于前一个取负）

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

整数模素数幂的平方根

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

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

Taylor 展开 $G$ 得到：

G (f) = \sum_{i = 0}^{+ \infty} \frac{G^{(i)} (f_{0})}{i!} {(f - f_{0})}^{i} = G (f_{0}) + 2 f_{0} (f - f_{0}) + (f - f_{0})^{2}

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

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

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

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

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

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

如果 $f_{j}$ 存在，那么 $2 f_{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} = \frac{1^{2} + 46}{2 \times 1} \mod 9 = 1$ , $f_{2} = \frac{1^{2} + 46}{2 \times 1} \mod 81 = 64$ , $f_{3} = \frac{64^{2} + 46}{2 \times 64} \mod 6561 = 955$ , $\dots$
$f_{0} = 2$ , $f_{1} = \frac{2^{2} + 46}{2 \times 2} \mod 9 = 8$ , $f_{2} = \frac{8^{2} + 46}{2 \times 8} \mod 81 = 17$ , $f_{3} = \frac{17^{2} + 46}{2 \times 17} \mod 6561 = 5606$ , $\dots$ （等于前一个取负）

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

代数证明

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

有解的证明

引理 1

设整环 $R$ 有多项式或形式幂级数 $f (X) = \sum_{i \geq 0} a_{i} X^{i}$ 和 $r, p \in R$ 使得 $f (r) \in R p$ （亦即 $r$ 是 $f (X)$ 在模 $p$ 意义下的根）且 $f^{'} (r) \in R$ 在模 $p$ 意义下是可逆的。这里 $f^{'} (X) := \sum_{i \geq 0} (i + 1) a_{i + 1} X^{i}$ 是 $f (X)$ 的 形式导数。那么 $f (r - \frac{f (r)}{f^{'} (r)}) \equiv 0 (\mod p^{2})$ 。

证明

对所有 $s \in R$ ，

\begin{aligned} f (r + s p) & = \sum_{i \geq 0} a_{i} (r + s p)^{i} \\ = \sum_{i \geq 0} a_{i} r^{i} + s p \sum_{i \geq 1} i a_{i} r^{i - 1} + s^{2} p^{2} (\dots) \\ = f (r) + s p f^{'} (r) + s^{2} p^{2} (\frac{f^{″} (r)}{2!} + \dots), \end{aligned}

所以

f (r + s p) \in R p^{2} ⟺ f (r) + f^{'} (r) s p \in R p^{2}

因为 $f (r) \in R p$ ，且 $f^{'} (r)$ 可逆，所以取 $s p = - \frac{f (r)}{f^{'} (r)}$ 即可，这里 $\frac{1}{f^{'} (r)}$ 是模 $p^{2}$ 意义下的逆元。因为 $f^{'} (r)$ 在模 $p$ 意义下可逆，所以它在模 $p^{2}$ 意义下也必定存在逆元：设有 $a, b, c \in R$ 使 $a f^{'} (r) = b p + 1$ 和 $f (r) = c p$ ，那么 $(a^{2} f^{'} (r) - 2) f^{'} (r) = b^{2} p^{2} + 1$ ，故可以取 $s = c (2 - a^{2} f^{'} (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 (\mod X^{2 n})

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

得到全部解的证明

引理 2

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

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

亦即

\forall x \in R, p^{2} ∣ f (x) \land p ∣ (x - r) ⟹ x \equiv r - \frac{f (r)}{f^{'} (r)} (\mod p^{2})

证明

令 $s = - \frac{f (r)}{f^{'} (r) p}$ 和 $u = r + s p$ ，引理 1 保证 $u$ 满足两个条件，且 $f (r) + f^{'} (r) s p \in R p^{2}$ 。设 $v$ 是满足上述条件的值，则有 $v = r + t p$ 和 $f (r) + f^{'} (r) t p \in R p^{2}$ 。于是有 $f^{'} (r) (t - s) p \in R p^{2}$ 和 $v - u \in R p^{2}$ 。

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

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

牛顿法无效时解的个数随次数而变多的例子

模 $X$ 意义下 $X^{2}$ 的平方根只有 $0$ ，但是模 $X^{4}$ 意义下 $X^{2}$ 的平方根有 $X, - X, X^{3} + X, \dots$ 。

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