13-核心概念-算法收敛速度

知识点：算法收敛速度

知识点概述

算法收敛速度是衡量迭代算法效率的重要指标，它描述了迭代序列接近最优解的速度。常见的收敛速度有Q-线性、Q-超线性、Q-二次和次线性收敛。

教材原文

对于同一个优化问题，其求解算法可以有很多。在设计和比较不同的算法时，另一个重要的指标是算法的渐进收敛速度。… 设 {x^k} 为算法产生的迭代点列且收敛于 x^* ，若对充分大的 k 有

$$\frac{\Vert x^{k+1}-x^{\ast }\Vert }{\Vert x^k-x^{\ast }\Vert }⩽a,a\in (0,1),$$

则称算法（点列）是Q-线性收敛的…

详细解释

• Q-收敛速度 (Quotient-convergence): 关注相邻两次迭代误差的比值。
  • Q-线性收敛: $\frac{\Vert x^{k+1}-x^{\ast }\Vert }{\Vert x^k-x^{\ast }\Vert }\to a\in (0,1)$。误差每步按固定比例减少，像等比数列。梯度下降法通常是线性收敛。
  • Q-超线性收敛: $\frac{\Vert x^{k+1}-x^{\ast }\Vert }{\Vert x^k-x^{\ast }\Vert }\to 0$。误差减少的比例越来越小。拟牛顿法通常是超线性收敛。
  • Q-二次收敛: $\frac{\Vert x^{k+1}-x^{\ast }\Vert }{\Vert x^k-x^{\ast }{\Vert }^2}\le a$。误差的量级每步都在平方，收敛极快。牛顿法在解附近是二次收敛。
  • Q-次线性收敛: $\frac{\Vert x^{k+1}-x^{\ast }\Vert }{\Vert x^k-x^{\ast }\Vert }\to 1$。收敛非常慢，例如误差为 $1/k$ 的序列。次梯度法通常是次线性收敛。
• R-收敛速度 (Root-convergence): 关注误差序列是否被一个已知收敛速度的序列所上界控制。
• 复杂度: 达到 $\epsilon$ 精度所需的迭代次数，如 $\mathcal{O}(1/\epsilon )$ 或 $\mathcal{O}(\log (1/\epsilon ))$。线性收敛对应对数复杂度，次线性收敛对应多项式复杂度。

学习要点

• 理解不同收敛速度的排序：二次 > 超线性 > 线性 > 次线性。
• 能够根据误差序列的递推关系判断收敛类型。
• 将常见算法（梯度法、牛顿法等）与其典型的收敛速度对应起来。

实践应用

• 选择算法时，需要在收敛速度和单步计算成本之间做权衡。牛顿法收敛快，但每步需要计算和求逆海瑟矩阵，成本高。梯度下降法收敛慢，但每步计算简单。

关联知识点

• 前置知识: 12-核心概念-迭代算法
• 后续知识: 57-理论方法-梯度下降法, 60-理论方法-牛顿法, 61-理论方法-拟牛顿法
• 相关知识: 无