迭代收敛阶

形式陈述 ​

设迭代序列 $x_k$ 收敛到 $x_{\ast }$，并用已经说明的距离或范数定义误差

$$e_k=d(x_k,x_{\ast }).$$

若存在 $p\ge 1$ 与 $C\in (0,\mathrm{\infty })$ 使

$$\underset{k\to \mathrm{\infty }}{lim}\frac{e_{k+1}}{e_k^p}=C,$$

则称该序列以 Q-阶 $p$ 收敛，$C$ 是渐近误差常数。$p=1$ 且 $0<C<1$ 称 Q-线性收敛；若 $e_{k+1}/e_k\to 0$，称 Q-超线性收敛；$p=2$ 是 Q-二次收敛。这里的误差必须遵守明确的误差度量公理库误差度量：绝对、相对与分量误差Error measures · Absolute and relative error用绝对、相对、范数型与逐分量尺度准确说明近似量偏离真值的程度。，否则 $C$ 与实验比较都没有确定含义。

Q-收敛逐步约束真实误差，要求较强。若存在正序列 $v_k\to 0$，使 $e_k\le v_k$ 最终成立，而 $v_k$ 具有 Q-阶 $p$，则称 $x_k$ 至少以 R-阶 $p$ 收敛。二分法的区间半径严格按 $1/2$ 缩小，因此能给出 R-线性保证；实际中点误差可能因根在区间内的位置而上下波动，不必逐步满足同一个 Q-比值。

知道真解时，可以用

$${\hat{p}}_k=\frac{\log \left(e_{k+1}/e_k\right)}{\log \left(e_k/e_{k-1}\right)}$$

估计渐近阶。真解未知时，常以连续三段更新量代替误差：

$${\hat{p}}_k=\frac{\log (\Vert x_{k+1}-x_k\Vert /\Vert x_k-x_{k-1}\Vert )}{\log (\Vert x_k-x_{k-1}\Vert /\Vert x_{k-1}-x_{k-2}\Vert )}.$$

这个估计要求各比值为正、分母不接近零、迭代已进入渐近区，而且更新量确实与真误差同阶。它是一项实验诊断，不是由少数数据点自动生成的收敛证明。

直觉 ​

收敛阶描述“已经靠近答案以后，旧误差如何变成新误差”。线性收敛大致每步乘一个固定比例；二次收敛大致每步把误差平方，所以足够接近根后正确位数会近似翻倍。这里的“足够接近”不可省略：算法起步时可能绕行、阻尼或暂时停留，只有尾部误差才受渐近关系支配。

阶数与单步成本共同决定实际速度。二次方法若每步需要昂贵的导数和线性求解，未必总比只做一次函数求值的低阶方法省时间；反过来，一个理论上超线性的方法也可能在进入渐近区前失败。收敛阶只回答局部误差缩减规律，不替代总工作量、稳定性和鲁棒性分析。

例子与边界 ​

二分法公理库二分求根法Bisection method以端点异号区间为不变量，给出可验证误差界、对数成本和有限精度停止条件。每步把含根区间的宽度减半，给出线性包络。对简单根，Newton 法公理库Newton 非线性方程法Newton's method · Newton-Raphson method · Newton method for nonlinear systems在当前点解一阶线性化方程来修正非线性方程的近似解，并分析其局部二次收敛与失效边界。在标准光滑性和近初值条件下满足 $e_{k+1}\approx C{e}_k^2$，因而是二次收敛。割线法公理库割线法Secant method用最近两点的割线斜率近似导数，在无导数的一维求根中取得局部超线性收敛。的局部误差近似满足 $e_{k+1}\approx C{e}_k{e}_{k-1}$；若假设 $e_{k+1}$ 与 $e_k^p$ 同阶，就得到 $p^2=p+1$，即黄金比例

$$p=\frac{1+\sqrt{5}}{2}\approx 1.618.$$

有限步恰好到达真解时，后续 $e_k=0$，上述比值成为 $0/0$，不能硬说阶数为无穷。误差交替、偶尔抵消或在浮点精度平台上变成零，也会令实验估阶剧烈跳动。应先绘制误差或更新历史，确认存在稳定渐近区，再解释拟合出的斜率。

还要区分三种相似说法：迭代 Q-阶研究 $k\to \mathrm{\infty }$ 时的 $e_k$；离散化误差 $O(h^p)$ 研究步长 $h\to 0$；复杂度中的 $O(n^p)$ 研究问题规模增长。它们都出现幂次，却控制不同变量，不能因符号相似就互相替换。

推论与应用 ​

序列收敛公理库序列收敛Convergence of a sequence序列项最终任意接近某个极限值。只保证误差最终趋于零，本页进一步描述趋零速度。Newton、割线与不动点迭代可以共享这套语言，但每个算法仍要分别证明其光滑性、非退化和初值条件；一句“二次收敛”若没有这些条件，只是缺少适用范围的宣传语。

实验比较应同时报告所用范数、参考真值或高精度解、迭代区间和舍入平台。若只能观察残差，还必须说明残差如何控制真误差；否则从残差斜率推断解误差阶，可能把问题条件性带来的放大误认为算法性质。

参考资料

• NIST Digital Library of Mathematical Functions, §3.8 Nonlinear Equations.
• J. M. Ortega and W. C. Rheinboldt, Iterative Solution of Nonlinear Equations in Several Variables, SIAM, 2000, rates and orders of convergence.
• C. T. Kelley, Iterative Methods for Linear and Nonlinear Equations, SIAM, 1995, Chs. 4–5.