牛顿迭代法求多项式域上函数的零点

牛顿迭代法

牛顿迭代法使用泰勒级数的前若干项求出函数零点的近似解。

令 $x_0$ 为我们选定的一个接近函数 $f(x)$ 零点的横坐标。则我们进行若干次迭代。有 $$x_{n+1}=x_n-\dfrac{f(x_n)}{f'(x_n)}$$

若 $x_0$ 选择得足够接近根 $\alpha$，迭代若干次就可以得到近似解。实际上，每进行一次迭代，解的精度变为原来的 $2$ 倍。

在多项式域上函数的推广

多项式域

（下文是我略微了解抽象代数并以之思考多项式上牛顿迭代正确性的结果。如果有任何勘误，恳请指正。）

在OI中，我们常遇到“（系数等）对某质数 $p$ 取模”的要求。我们使用的运算系统确实是自洽的，因为就像普通实数域一样，整数模 $p$ 构成的元素确实也自成一个域。它具有封闭性；具有单位元 $1$，零元 $0$，所有元素具有乘法逆元 $a^{-1}$，有 $a\cdot a^{-1}=1$，这也就对所有非零元素定义了除法；具有加法逆元 $p-a$，乘法加法满足交换律、结合律、分配律；等等。所以在一般实数域上的很多运算和规律，我们都可直接推广。

我们在OI中讨论的多项式，指的就是由整数模 $p$ 域 $\mathbb{Z}/p\mathbb{Z}$ 中的数作系数的多项式环 $\mathbb{Z}/p\mathbb{Z}[x]$ 的元素。

我们还定义了多项式的加减乘除运算，且满足数域上四则运算的一般规律，例如乘法和加法的交换律、乘法对加法的分配律，单位元 $f(x)=1$，零元 $f(x)=0$等。所以可以认为，同数域一样，有多项式域。

因此就像在数域上一样，我们完全可以在多项式域上定义函数，也可以推广积分、求导等运算，其各种运算法则均在该域上适用。比如定义 $f(g(x))=2x+2+a^2(x)g(x)+g^2(x)$，其中 $a(x)$ 是某个已知的多项式；$(2x+2)$ 确实是一个多项式，但在该多项式域上的函数中作为系数存在；该函数的参数为 $g(x)$。该函数的(关于 $g(x)$ 的，而非关于 $x$ 的）导数为 $f'(g(x))=a^2(x)+2g(x)$。更进一步地，我们甚至还可以定义多项式环 $(\mathbb{Z}/p\mathbb{Z}[x])[x]$，也即以整数模 $p$ 域 $\mathbb{Z}/p\mathbb{Z}$ 中的数作系数的多项式作系数的多项式构成的环。

牛顿迭代法的推广

现在已知多项式域上的函数 $F(g(x))$，求满足 $F(g(x))\equiv 0\space (\bmod x^n)$ 的 $g (x)\space (\bmod x^n)$。

我们可以将牛顿迭代法推广到多项式域上，结合倍增的思想，快速求出目标多项式也即 $F(g(x))$ 的零点。

下文记 $\bmod x^{2^n}$ 意义下的某个函数为 $g_{n}$，也即只考虑该函数 $0,1,\cdots,2^{n}-1$ 项的系数。

引理1：有 $[x^k]g_{n}(x)=[x^k]g_{n+1}(x),\forall k \in \{0, 1, \cdots, 2^n-1\}$。

这是因为，在 $\bmod{x^{n+1}}$ 意义下考虑 $x^k, k \in [0, 2^n)$ 的贡献，若满足次数 $i+j=k$，则必然有 $i\leq k, j \leq k$，不可能由 $g_{n+1}(x)$ 的更高次项和 $F$ 各项多项式系数的更高次项向低位贡献。因此上述结论成立。

引理2：不论在何处展开，都有一个 $n$ 次多项式函数的 $k \leq n$ 阶泰勒展开为其自身。

笔者水平有限，无法给出详细证明。似乎可以通过各项系数的累乘与二项式系数证明。（若感性理解，则可以认为“使用几个次数为 $0\sim n$ 的多项式逼近 $n$ 次多项式，结果也必然为其本身”）因此我们可以放心大胆地在函数某一点对其展开后直接求出另一点的精确值。

假如我们现在求出 $g_{n}(x)$。于是可以考虑在 $g_{n}(x)$ 对 $F_{n+1}(g_{n}(x))$ 作泰勒展开： $$F_{n+1}(g_{n+1}(x))=\sum_{k=0}^{+\infty}\dfrac{F_{n+1}^{(k)}(g_{n}(x))}{k!}(g_{n+1}(x)-g_{n}(x))^k\space (\bmod x^{2^{n+1}})$$

根据引理1，有且仅有 $[x^k](g_{n+1}(x)-g_{n}(x)), k\in [2^n, 2^{n+1})$ 不为 $0$。因此在 $(\bmod x^{2^{n+1}})$ 意义下，求和式第 $k,k \geq 2$ 项无意义。所以我们化简整理得到 $$\begin{aligned} {\color{blue}F_{n+1}(g_{n+1}(x))} & =F_{n+1}(g_{n}(x))+F_{n+1}'(g_{n}(x))(g_{n+1}(x)-g_n(x))\\ {\color{blue}0}-F_{n+1}(g_{n}(x)) & =F_{n+1}'(g_{n}(x))(g_{n+1}(x)-g_n(x))\\ g_n(x)-\dfrac{F_{n+1}(g_{n}(x))}{{\color{red}\dfrac{\mathrm{d}}{\mathrm{d}g_{n}(x)}}F_{n+1}(g_{n}(x))}& =g_{n+1}(x) \end{aligned}$$

是的没错，这玩意的形式与通常意义下的牛顿迭代惊人地一致。但需要注意每个函数都是在 $\bmod x^{2^{n+1}}$ 意义下计算系数的。

应用举例

求多项式乘法逆

现在有 $F(G(x))=a(x)g(x)-1$，其中 $a(x)$ 是需要求逆的多项式。代入即可得到： $$\begin{aligned} g_{0}(x)&=1\\ g_{n+1}(x)&=g_n(x)-\dfrac{F_{n+1}(g_{n}(x))}{F_{n+1}'(g_{n}(x))}\\ & =g_n(x)-\dfrac{{\color{red}a_{n+1}(x)}g_{n}(x)-1}{\color{red}a_{n+1}(x)} \end{aligned}$$

麻烦出现了。假如我们强行约分，会得到类似于 $g_{n+1}(x)=g_{n+1}(x)$ 的恒等式。但是别慌！我们注意到，我们需要乘上在 $\bmod x^{2^{n+1}}$ 意义下 $a_{n+1}(x)$ 的逆元，也就是 $g_{n+1}(x)$；并且由引理1可以得到，分子的式子在 $\bmod x^{2^{n}}$ 意义下等于 $0$。这也就说明，有 $({\color{red}a_{n+1}(x)}G_{n}(x)-1)a_{n+1}^{-1}(x)\space (\bmod x^{2^{n+1}})$ 的结果中，只有 $[x^k]a_{n+1}^{-1}(x), k\in [0, 2^{n})$ 会造成贡献——也就等价于 $a_{n}^{-1}(x)=g_{\color{red}n}(x)$！所以就有 $$g_{n+1}(x)=2g_{n}(x)-a_{n+1}(x)g_{n}^2(x)$$

食用 FFT/NTT 即可加速多项式乘法。时间复杂度 $T(n)=T(\dfrac{n}{2})+\mathrm{O}(n\log n)=\mathrm{O}(n \log n)$。