Improvements of the Modified Anderson-Björck (modAB) Root-Finding Algorithm

paper root-finding bracketing bisection Anderson-Björck NonlinearSolve.jl

Authors: Nedelcho Ganchovski, Oscar Smith, Christopher Rackauckas, Lachezar Tomov, Alexander Traykov

Source: Preprints.org, 27 March 2026 · DOI: 10.20944/preprints202603.2190.v1

Affiliations: Proektsoft (Bulgaria) · JuliaHub · MIT · New Bulgarian University

问题

一维求根（找 f(x)=0 的 x）看似简单，实际上所有方法都在速度和鲁棒性之间做取舍：

Bisection：最可靠，但每步只减半一次区间——慢
False position / Illinois：对光滑函数快得多，但有「固定端点」问题——一端永远不动，导致病态函数上极慢
Brent / ITP / Ridders：各种组合策略，试图兼顾两者

2022 年提出的 modAB（Modified Anderson-Björck）用一个线性度检测来决定何时从 bisection 切换到 Anderson-Björck 插值。初始版本表现不错，但有几个已知缺陷：偏差因子 k 固定为 0.25、bisection fallback 策略太保守、终止条件对平坦函数不可靠、benchmark 只有 21 个函数。

翻译

一个类比：自动挡和手动挡的切换

Bisection = 一档爬坡（慢但稳）

每一步把搜索区间砍一半。n 步后区间缩小 2ⁿ 倍。不需要了解函数形状——只要知道两端异号就行。

Anderson-Björck = 高档巡航（快但可能打滑）

用线性插值预测根的位置，然后修正固定端点。对近线性函数收敛极快，但对弯曲函数可能退化。

modAB = 自动变速箱

在每一步检测函数「有多直」（线性度）。接近直线→切换到 AB 高档；弯曲太多→降回 bisection 一档。关键在于何时换挡和换挡失败时如何回退。

本文的三个改进全部围绕「换挡策略」：(1) 偏差因子 k 根据端点对称性自适应 (k=r²)；(2) bisection fallback 从固定步数改为实际性能对比；(3) 终止条件从步长检查改为区间宽度检查。

架构

三个改进

4.1 自适应偏差因子 k

原始版本 k = 0.25（固定值）。新版本引入对称因子 r：

$$r = 1 - \left|\frac{y_m}{y_2 - y_1}\right|, \quad k = r^2$$

r = 1（端点完全对称）→ k = 1 → 更容易切换到 AB（因为对称函数上 AB 表现好）
r → 0（端点高度不对称）→ k → 0 → 更倾向 bisection（因为不对称时 AB 容易走偏）
关系是二次而非线性的——因为对称性对收敛速度的影响是超线性的

4.2 自适应 Bisection Fallback

原始版本：AB 跑固定步数后无条件回退到 bisection。新版本：实时比较 AB 的实际区间缩小速度与 bisection 的理论速度——

$$W(t) > T(t), \quad T(t) = C \cdot \frac{W_0}{2^t}$$

C = 16（允许 4 步延迟），每步更新 T_t = T_t-1/2。如果 AB 比 bisection 收缩得慢，才回退。

4.3 新终止条件

原始版本：|x_n - x_n-1| < ε（步长检查）——对平坦函数失效（步长小但距根远）。新版本：

$$b_n - a_n < \varepsilon_{\text{abs}} + \varepsilon_{\text{rel}} \cdot |x_n|$$

区间宽度检查——不受函数形状影响，代价是可能多 1-2 步（等另一端也收缩）。

关键结果

92 函数 Benchmark

方法	总评估数	平均	vs modAB²	Best (#)	Worst (#)
Bisection	4498	48.9	2.50×	11	40
False position	8200	89.1	4.56×	7	44
Illinois	2975	32.3	1.66×	7	6
Anderson-Björck	3162	34.4	1.76×	45	7
ITP	2732	29.7	1.52×	15	1
Ridders	2256	24.5	1.26×	5	1
Brent	2972	32.3	1.65×	13	1
modAB¹ (2022)	1857	20.2	1.03×	31	0
modAB² (本文)	1797	19.5	1.00×	31	0

核心数据：

总评估数最少（1797），比 Ridders 少 20%，比 Brent 少 40%，比 ITP 少 34%
最差表现函数数 = 0——没有任何函数上是最差的（唯一做到这点的方法）
最佳表现 31 个函数（与 modAB¹ 并列第一，但总成本更低 3%）
几何平均 15.6 vs Ridders 19.6 vs ITP 23.4 vs Brent 19.1

评价

⚖️ 一个扎实的增量改进——92 函数 benchmark 上一致优于所有经典方法且无最差表现。但核心贡献是工程改进（adaptive k, adaptive fallback, better termination），没有新的理论洞察。

亮点：92 函数 benchmark 是该领域最全面的（之前 modAB¹ 只有 21 个）；Worst=0 的鲁棒性令人印象深刻；已集成到 NonlinearSolve.jl（Rackauckas 是共同作者）、ROOT.CERN 等主流库；代码完整附在 Appendix。

局限：只测了函数评估次数，没测挂钟时间（modAB 每步的 overhead 比 bisection 大）；benchmark 全是一维标量函数，不涉及方程组；没有收敛阶的理论分析；k=r² 的二次关系是经验选择，没有理论论证。

博导审稿

🎓 「这篇我快速过了一遍。」

——一位带了 20 年数值计算方向研究生的博导

选题眼光

一维求根看起来是「已解决的问题」，但实际上 Brent (1973) 之后 50 年内几乎没有实质性改进——ITP (2021) 才打破了沉寂。modAB 试图在这条缝里挤出更多性能。选题不是原创性问题，而是实用工程改进。

方法成熟度

三个改进都是 engineering refinement，不是 algorithmic innovation。adaptive k = r² 没有理论依据（为什么二次而不是三次？）；adaptive fallback threshold 的 C=16 也是经验选择。方法有效但缺乏深度——一个好的审稿人会问「你能证明收敛阶吗？」答案大概是不能。

实验诚意

很好。92 函数 benchmark 从 6 个独立来源收集，包括 SciML Benchmarks suite——这比大多数求根论文用的 5-20 个函数强得多。用函数评估数而非迭代次数作为 metric 是正确的（Ridders 每步 2 次评估）。代码完整公开（Appendix A）。唯一缺憾：没有 wall-clock 时间——modAB 每步的分支判断和对称因子计算有 overhead。

写作功力

写得简洁直接——12 页把问题、缺陷、改进、benchmark 全讲清楚了。Table 2 的 92 函数大表虽然占了 3 页但信息量极高。Section 3 对原始 modAB 缺陷的自我批评很诚实。不过 Section 4.1 的对称性论证偏 hand-wavy——「relationship between symmetry and convergence is rather quadratic than linear」需要更多支撑。

影响力预判

实际影响力可能超过学术引用量——因为代码已经集成到 NonlinearSolve.jl（Julia 生态标准求根库）和 ROOT.CERN（粒子物理标准分析框架）。每次有人在这些库中调用求根，用的就是 modAB。预计 3 年内 15-30 次引用，但代码使用量可能远超论文引用。

📋 Weak Accept

实验全面（92 函数 benchmark）、Worst=0 的鲁棒性令人印象深刻、代码已集成到主流库。但方法贡献是工程改进而非算法创新——没有收敛阶分析、adaptive k 的二次关系缺乏理论支撑。对于 Preprints.org 的定位（快速分享实用成果）完全合适。如果投到 ACM TOMS 或 Numerical Algorithms，需要补充理论分析。

一句话总结

通过自适应偏差因子（k=r²）、实时性能对比的 bisection fallback、和区间宽度终止条件，改进版 modAB 在 92 函数 benchmark 上以最低总评估数（1797）和零最差表现击败所有经典一维求根方法——代码已集成到 NonlinearSolve.jl 和 ROOT.CERN。