🔢 mathematics

A root finding method with arbitrary order of convergence

本文提出了一种仅通过多项式运算即可实现任意收敛阶数的算法，用于计算正实数 $a$ 的 $M$ 次方根。

原作者： Alois Schiessl

发布于 2026-02-10

📖 1 分钟阅读🧠 深度阅读

原作者： Alois Schiessl

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

标题：数学界的“超级加速器”：如何用最简单的工具，瞬间锁定无限精确的答案

1. 背景：我们在玩什么游戏？

想象一下，你面前有一个巨大的迷宫，迷宫的中心藏着一个宝藏（这个宝藏就是我们要算的**“根”**，比如 $\sqrt[M]{a}$ ）。

目前，数学家们最常用的方法叫“牛顿法”。牛顿法就像是一个经验丰富的探险家，他每走一步，都会根据地形的变化来调整方向。虽然很厉害，但他有一个特点：他的进步速度是**“翻倍”**的。也就是说，如果他现在知道小数点后 2 位是对的，下一步大约能知道 4 位，再下一步 8 位。这叫“二次收敛”。

2. 论文的核心发现：定制你的“加速引擎”

作者 Alois Schiessl 提出了一个更疯狂的想法：“既然翻倍不够快，那我们能不能让它‘翻三倍’、‘翻四倍’，甚至‘翻一百倍’呢？”

他发明了一种新的方法，这个方法的核心工具非常简单——多项式（Polynomials）。

比喻：

牛顿法像是一辆性能稳定的家用轿车，每次加速都很稳，但速度有上限。
作者的方法则像是一台可定制的火箭引擎。你可以根据需要，通过调整一个参数（论文里的 $P$ $P$ ），来决定这枚火箭的“加速等级”。
- 如果你把 $P$ 设为 1，它就是一辆跑车（二次收敛）；
- 如果你把 $P$ 设为 3，它就是一枚火箭（四次收敛），每走一步，正确答案的位数会直接翻四倍！

3. 这个“火箭”是怎么造出来的？（原理简述）

作者并没有使用复杂的函数，而是通过一个巧妙的数学公式（积分和多项式组合），构造了一个特殊的“引力场”（固定点函数 $F(x)$ ）。

这个引力场有一个神奇的特性：它在宝藏所在的位置非常“平滑”。
在普通的算法里，当你接近宝藏时，地形可能还是起伏的；但在作者设计的这个引力场里，宝藏周围的地面被“磨平”了，而且磨平的程度完全由你设定的 $P$ 决定。 $P$ 越大，地面就越平，你滑向宝藏的速度就越恐怖。

4. 实战演练：从“秒杀”到“百万级精度”

论文里展示了两个非常震撼的实验：

实验一：算 $\sqrt[3]{10}$
用这个新方法，只需要走几步，精度就达到了惊人的程度。这证明了“火箭引擎”确实比“家用轿车”快。
实验二：挑战极限——计算 $\sqrt{2}$ 的一百万位小数
这是全篇的高潮。计算一个数字的一百万位小数，通常需要极其庞大的计算量和漫长的时间。
但作者展示了：利用这个“四倍加速”的引擎，仅仅用了 9 步迭代，就在短短 3 秒钟内，就锁定了 $\sqrt{2}$ 的一百万位小数！

想象一下： 别人还在用步行的速度一点点丈量大地，你已经坐着超音速飞机，在 9 次跳跃中，直接从家门口飞到了月球，而且降落时精准到了毫米级。

5. 总结：为什么这很重要？

虽然这个方法看起来只是在算数学题，但它的意义在于：

极高的效率：它证明了我们不需要复杂的工具，只要通过巧妙的数学设计，就能实现“指数级”的进步。
高度的可定制性：你想算多快，全看你给这个算法分配多少“能量”（即参数 $P$ ）。
纯粹的力量：它只使用了最基础的多项式运算，这对于计算机来说是非常容易处理的，这让它在实际应用中非常强大。

一句话总结：作者为数学计算提供了一套“变速箱”，让你能根据任务的难度，随心所欲地切换从“慢跑”到“超光速”的模式。

这是一篇关于数值分析领域中根寻找（Root-finding）算法的研究论文。以下是对该论文的详细技术总结：

1. 研究问题 (Problem)

论文的核心目标是寻找方程 $t^M - a = 0$ 的实数解，即计算 $M$ 次方根 $\sqrt[M]{a}$ （其中 $a \in \mathbb{R}^+ \setminus \{0\}$ 且 $M \in \mathbb{N}$ ）。

传统的数值方法（如牛顿迭代法）在计算该类根时具有二次收敛性（Order of convergence = 2），这意味着每次迭代大约能使正确数字的位数翻倍。然而，牛顿法在收敛阶数上是固定的。该论文试图解决的问题是如何设计一种仅使用多项式运算，且能够实现任意阶收敛性（Arbitrary order of convergence）的算法。

2. 核心方法论 (Methodology)

作者提出了一种基于**不动点迭代（Fixed-point iteration）**的新方法。

A. 函数构造

首先定义基础函数 $f(t) = 1 - \frac{t^M}{a}$ 。为了实现高阶收敛，作者构造了一个复杂的固定点函数 $F(x)$ ：
$F(x) = \left[ \prod_{\ell=1}^{P} \left( 1 + \frac{1}{\ell \cdot M} \right) \right] x \int_{0}^{x} \left( 1 - \frac{t^M}{a} \right)^P dt$
其中 $P$ 是一个预设的正整数。

B. 多项式化处理

通过对积分项应用二项式定理，作者证明了 $F(x)$ 可以展开为一个多项式：
$F(x) = \sum_{k=0}^{P} c_k \cdot x^{k \cdot M + 1}$
其中系数 $c_k$ 包含了常数项、二项式系数以及 $a$ 和 $M$ 的组合。这意味着计算 $\sqrt[M]{a}$ 的过程被简化为了对一个特定多项式的求值过程。

C. 收敛阶的设计

通过对 $F(x)$ 在不动点 $\sqrt[M]{a}$ 处进行泰勒展开并分析其导数，作者证明了：

当 $1 \le k \le P$ 时，第 $k$ 阶导数 $F^{(k)}(\sqrt[M]{a}) = 0$ 。
第 $P+1$ 阶导数不为零。
根据不动点迭代理论，该序列 $x_{n+1} = F(x_n)$ 的收敛阶恰好为 $P+1$ 。通过调整参数 $P$ ，用户可以人为控制算法的收敛速度。

3. 主要贡献 (Key Contributions)

任意阶收敛性：打破了传统迭代法（如牛顿法）固定收敛阶的限制，通过增加多项式的阶数 $P$ ，可以获得极高的收敛速度。
纯多项式实现：算法完全基于多项式求值（可以使用高效的秦九韶算法/Horner's scheme），这使得该方法在计算机底层实现时非常友好，且易于处理高精度计算。
理论完备性：论文利用贝塔函数（Beta function）和伽马函数（Gamma function）严谨地证明了不动点的存在性、导数的性质以及收敛阶的精确值。

4. 实验结果 (Results)

论文通过两个实例验证了算法的有效性：

示例 1（低阶验证）：计算 $\sqrt[3]{10}$ ，设置 $P=1$ （即二次收敛）。实验结果显示，随着迭代进行，误差的指数呈倍增趋势，验证了二次收敛的特性。
示例 2（高阶与高精度验证）：计算 $\sqrt{2}$ $2$ 达到一百万位精度。设置 $P=3$ $P = 3$ （即四次收敛）。
- 效率：仅需 9 次迭代 即可达到百万位精度。
- 速度：在普通家用 PC（AMD Ryzen 5 5600G）上，使用 MAPLE 软件，3 秒内即可完成计算。
- 观察：误差指数大约每一步变为原来的 4 倍，完美符合四次收敛的理论预测。

5. 研究意义 (Significance)

该研究在数值计算领域具有重要的应用价值：

高精度计算优化：对于需要极高精度（如数百万位有效数字）的科学计算或密码学应用，该方法提供了一种比传统牛顿法更高效的路径。
计算复杂度权衡：它提供了一个明确的权衡机制——通过增加单次迭代的计算量（增加 $P$ 导致多项式项数增加），可以大幅减少所需的迭代次数，从而在总计算时间上实现优化。
算法通用性：该方法不仅适用于平方根，也适用于任何 $M$ 次方根的计算，具有很强的通用性。