非线性方程Steffensen方法的零成本增强

《Mathematics》：Zero-Cost Enhancement of the Steffensen Method for Nonlinear Equations

　　

Steffensen方法是一种非常有效的求根过程，用于数值求解形如 ??(??)=0 的非线性方程。当 ?? 的根为单根（simple root）时，该方法具有 2 阶收敛。基于对其收敛性分析的批判性回顾，本研究给出了Steffensen方法的一种带记忆（with memory）修正，使其在每次迭代中不增加函数求值次数的前提下，实现显著高于 2 的收敛阶。具体而言，对于任意固定整数 ??≥1 以及初始近似 ??₀,??₁,…,??_??，该修正方法通过
??_??+1=??_?????(??_??)/??[??_??,??_??]，??=??,??+1,…
生成方程 ??(??)=0 的解的近似序列，其中
??_??=??_?????(??_??)/??′_??,??(??_??)，
且 ??_??,??(??) 是在节点 ??_??,??_???1,…,??_????? 处对 ??(??) 的插值多项式（interpolation polynomial）。与原始方法相同，该修正方法仅使用 ??(??)，不需要 ??(??) 的导数。研究证明：当 ??=1 时，该方法的收敛阶为 1+√2≈2.414；随着 ?? 的增大，收敛阶可提升并趋近于 (3+√5)/2≈2.618。（例如，当 ??=6 时，该方法的收敛阶已达到 2.617?。）

该文发表于《Mathematics》，围绕非线性方程数值求解中的经典Steffensen方法展开，核心目标是在不增加单步函数求值成本的条件下，提高方法的局部收敛阶与效率指数。研究背景在于：Steffensen方法作为一种无需导数的经典迭代算法，对于单根问题具有二阶收敛性，且每步仅需两次函数求值，因此在实际计算中具有较高性价比。然而，其理论收敛阶固定为2，限制了其在高精度求根任务中的效率提升空间。已有若干带记忆方法可推广Steffensen方法并改善精度与效率，但如何在“零额外函数求值成本”的约束下系统提升其收敛阶，仍然是一个具有理论与方法学意义的问题。因此，研究人员对Steffensen方法的收敛机制进行了重新审视，并据此构造了一个新的带记忆迭代方法族。

论文首先回顾了Steffensen方法的标准形式，并将其嵌入一个更一般的迭代框架中分析。通过差商（divided difference）表达式与误差递推关系，研究人员重新梳理了该方法达到二阶收敛的根本原因，并指出：若能够以零成本方式构造对导数 ??′(??_??) 更精确的替代量，则有可能提升Steffensen方法的收敛阶。基于这一观察，论文从Traub提出的思想出发，先讨论了一种需要额外一次导数求值的增强版本，该版本可将收敛阶提高到3；继而提出一种真正“零成本”的替代策略，用前一步迭代信息构造导数近似，将收敛阶提升至 1+√2。随后，作者进一步将该思路推广到任意固定整数 ??≥1 的情形，以最近 ??+1 个迭代点上的插值多项式导数 ??′_??,??(??_??) 逼近 ??′(??_??)，建立了新的方法族 SSteff。该方法族每步仍仅需两次函数求值，不需任何导数信息，却能使收敛阶随 ?? 增大而迅速提高，并趋于上界 (3+√5)/2≈2.618，这一结果显著优于经典Steffensen方法的2阶收敛。

从研究意义看，该工作实现了“零成本增强（zero-cost enhancement）”：在保持与Steffensen方法相同单步计算代价的同时，提高了收敛阶和效率指数（efficiency index，用于衡量每次函数求值对应的有效收敛能力）。因此，这不仅是对Steffensen方法局部理论的深化，也为无导数非线性方程迭代法设计提供了一个具有推广价值的框架。论文还给出了完整而细致的收敛理论，并通过数值算例验证理论预测，说明该方法在实践上同样稳定有效。

就主要技术方法而言，研究人员首先利用一般迭代格式与差商恒等式建立Steffensen方法的统一误差分析框架；其次，以插值多项式（interpolation polynomial） ??_??,??(??) 的导数 ??′_??,??(??_??) 近似真实导数 ??′(??_??)，构造带记忆的零成本修正；再次，借助误差递推、极限分析和特征多项式根分析，严格证明收敛阶满足特定多项式方程，并随 ?? 单调增加且趋向 (3+√5)/2；最后，采用 1000 位高精度算术对三个具有单根的非线性方程进行数值实验，通过误差与观测收敛阶 ??_?? 的计算验证理论结论。文中未涉及样本队列，研究对象均为解析数值算例。

以下结合正文各部分小标题，对论文结果进行凝练解读。

1. Introduction and Background
本节介绍了研究问题与总体目标。研究对象是方程 ??(??)=0 的单根数值求解问题，其中 ?? 在含根区间内至少二次连续可微。作者指出，Steffensen方法是无需导数的高效算法，每步两次函数求值、局部二阶收敛。本文的目标并非讨论重根、全局收敛或吸引域，而是专注于单根情形下的局部收敛阶提升。研究人员明确提出：希望构造一个带记忆方法族，在不增加每步函数求值次数的前提下，实现至少高于2的收敛阶，并使该收敛阶尽可能接近3。为此，论文安排了方法回顾、方法构造、严格收敛性证明以及数值验证四个层面的内容。

2. Review of the Steffensen Method
2.1. The Steffensen Method as a Special Case of a General Iterative Method
本小节将Steffensen方法写入一般迭代公式中，并借助差商表示推导出统一误差关系式。结论是，Steffensen方法可视为某个一般迭代法在特定辅助点选择下的特例。这一重构为后续比较不同辅助点构造方式、统一分析各种增强版本奠定了基础。

2.2. Analysis of the Steffensen Method
本小节利用前述一般误差公式，专门分析经典Steffensen方法。研究人员证明，当根为单根且 ??′(α)≠0 时，误差主导项为二次项，因此该方法的局部收敛阶为2。此处的分析不仅回顾了经典结果，也揭示了收敛阶受限的关键误差来源。

2.3. Can the Steffensen Method Be Enhanced?
本小节提出核心问题：是否可以在零额外成本下增强Steffensen方法。作者指出，若能在理论上令某个误差主项消失，便可使方法达到高于2的收敛阶。Traub的思路是将Steffensen方法作用于一个变换后的方程，但这一过程需要真实导数或其替代。由此，问题转化为：如何构造低成本且高精度的导数近似。

3. Preliminary Improvement of the Steffensen Method
3.1. An Expensive Choice
本小节先给出一种“非零成本”改进，用真实导数 ??′(??_??) 参与构造辅助点。研究人员证明，该策略本质上相当于先对相关方程执行一步Newton–Raphson方法，再代回Steffensen框架，因此可将收敛阶提高到3。但由于每步额外需要一次导数求值，这种方法虽具有启发意义，却不符合本文“零成本增强”的目标。

3.2. A Preliminary Zero-Cost Choice
本小节提出一个初步零成本版本，用已有迭代点形成的线性插值导数近似真实导数。研究人员证明，这一方法无需增加函数求值或导数求值，且其收敛阶提升为 1+√2≈2.414。该结果表明，仅通过记忆先前迭代信息就能够打破经典Steffensen方法的二阶限制，说明“零成本增强”是可行的。

4. SSteff: General Enhancement of the Steffensen Method
4.1. Generalization of
本小节将前述线性插值思想推广至高阶插值。研究人员在点 ??_??,??_???1,…,??_????? 上构造插值多项式 ??_??,??(??)，并以其导数 ??′_??,??(??_??) 近似 ??′(??_??)，从而定义新方法 SSteff。由于所需函数值均来自当前步与历史步，因此该方法仍保持每步两次函数求值。作者还给出初值 ??₀,…,??_?? 的系统生成方式：先由Steffensen方法得到 ??₁，再逐步利用较低阶 SSteff 产生后续初值，保证初始序列本身就是有效根近似。

4.2. Analysis of Convergence of SSteff
这是全文的理论核心。定理1证明：当初值彼此不同且足够接近单根 α 时，SSteff 生成的序列收敛到 α，并满足渐近误差关系。更关键的是，方法的收敛阶 ?? 是多项式
??^??+1?∑_??=0^????^??=0
的唯一正根，且 ??>2。研究人员进一步证明，随 ?? 增大，该正根单调上升并趋于
(3+√5)/2≈2.618。
这意味着，增加记忆长度可持续提升方法的局部收敛效率，但其极限并非3，而是稳定逼近约 2.618。论文还说明，??=6 时收敛阶已达 2.617?，实际上已经非常接近理论上限。该节同时比较了效率指数：在每步仍只有两次函数求值的情况下，SSteff 的效率指数明显高于Steffensen方法，并优于若干相关经典方法。

5. Numerical Examples
本节通过三个具有单根的非线性方程检验理论结果。研究人员对固定 ?? 的情形定义误差 ??_?? 与观测收敛阶 ??_??，并使用 1000 位高精度算术计算，以避免有限精度过早掩盖渐近行为。
Example 1：对方程 ??(??)=???e^???，从给定初值出发，方法对所有测试的 ?? 都平稳收敛，观测阶逐渐逼近理论阶。
Example 2：对第二个非线性方程，方法同样表现出快速收敛，且在较少步数后误差已低于工作精度，显示出高阶方法的高效性。
Example 3：对方程 ??(??)=??e^???1，方法依然对所有 ?? 平稳收敛，观测阶与理论值高度吻合。作者还指出，该方程与Lambert方程相关，其根可由Lambert W-函数的主支表示，从而为算例提供了解析背景。整体而言，数值实验清楚证明了理论分析关于收敛阶、渐近行为及有限精度饱和现象的判断。

讨论部分的核心在于，研究人员并未试图通过增加函数或导数求值来换取更高阶数，而是利用带记忆机制与插值导数逼近，在相同单步代价下获得更高收敛效率。这种改进具有明显的方法学价值：一方面，它保持了Steffensen方法“无导数、低代价”的优点；另一方面，它通过系统利用历史迭代点的信息，建立了一条可控、可证明、可数值验证的高效增强路径。论文同时谨慎指出，研究范围局限于单根的局部收敛理论，不讨论重根、全局收敛及吸引域，因此其结论具有清晰边界。

研究结论可概括为：本文提出了一类Steffensen方法的带记忆零成本修正方法。该方法每步仅需两次函数求值，不需要导数计算；当 ??=1 时，收敛阶为 1+√2≈2.414；随着 ?? 增大，收敛阶单调提高并趋近于 (3+√5)/2≈2.618。理论分析与高精度数值实验一致表明，该方法族在保持与经典Steffensen方法相同计算成本的同时，实现了更高的收敛阶和效率指数，因此构成了对Steffensen方法的一种有效而严格的零成本增强。