迭代算法从入门到调参：不动点、牛顿法、梯度下降与共轭梯度实战

1. 从“迭代”这个词被用烂说起“迭代算法”这四个字大概是计算机和数学交叉领域里被引用次数最多、也被误解得最深的词之一。我在过去几年里带过不少刚入行的朋友发现一个很普遍的现象很多人第一次听到“迭代算法”脑子里浮现的是“敏捷开发里的迭代”“产品版本迭代”甚至有人以为是某种代码重构技巧。这其实不怪他们因为“迭代”在日常语境里已经被泛化成了“反复改进”的意思而它在算法层面的含义要精确得多也硬核得多。先把话说清楚迭代算法不是某一种具体的算法而是一大类求解策略的总称。它的核心思想非常朴素——当我们没办法一步到位算出精确解时就从一个初始猜测出发按照某个固定的规则反复修正这个猜测让每一次修正后的结果都比上一次更接近我们想要的答案直到满足某个停止条件为止。这个“反复修正”的过程就是迭代那个“固定的修正规则”就是迭代公式而“停止条件”则决定了我们什么时候认为已经足够好了。它解决的问题也很明确大量现实中的方程、优化问题、线性系统、特征值问题根本不存在解析解或者解析解的形式复杂到没有实用价值。比如你要求解一个非线性方程组或者要在一个高维空间里找函数的最小值点直接求解几乎不可能但迭代法可以一步步逼近。适合学习这套内容的人包括但不限于做数值计算的工程师、搞机器学习的算法从业者、做图形学和物理仿真的开发者以及任何需要处理“无法直接求解”问题的技术人。我写这篇东西的目的不是给你复述教科书上的收敛性定理而是把迭代算法从“知道有这么回事”讲到“能自己选、能自己调、能自己判断什么时候它不靠谱”。下面会从最基础的不动点迭代一路聊到牛顿法、梯度下降、共轭梯度中间穿插我自己踩过的坑和调参经验。你不需要有很深的数学背景但至少要能看懂函数和导数。2. 不动点迭代所有迭代算法的原型2.1 把方程改写成 x g(x) 的那一步才是关键不动点迭代是整个迭代算法家族里最基础、最容易理解的一个。它的思路是如果你要求解方程 f(x) 0先想办法把它改写成 x g(x) 的形式然后从一个初始值 x₀ 出发反复计算 x_{k1} g(x_k)。如果这个序列收敛它的极限就是方程的解也就是 g 的不动点。听起来简单得不像话但真正动手做过的人都知道难点根本不在迭代本身而在于怎么把 f(x) 0 改写成 x g(x)。同一个方程可以有无数种改写方式不同的改写方式对应不同的 g(x)而不同的 g(x) 收敛性可能天差地别——有的飞快收敛有的慢如蜗牛有的干脆发散。举个具体的例子。假设要求解 x³ - x - 1 0 在 1 附近的根。你可以改写成 x x³ - 1也可以改写成 x (x 1)^(1/3)。前者对应的 g(x) 3x²在 x ≈ 1.3 附近 g(x) ≈ 5远大于 1迭代必然发散。后者对应的 g(x) 1/(3(x1)^(2/3))在同一个点附近大约 0.2 左右小于 1迭代稳定收敛。这就是不动点迭代的收敛判据在不动点附近如果 |g(x)| 1迭代局部收敛|g(x)| 越小收敛越快。我刚开始学的时候总觉得这个判据是“事后验证”——你得先知道不动点在哪才能算 g(x)。后来才想明白实际使用中你确实需要先对解的位置有个粗略估计然后在这个估计点附近检查 |g(x)|。如果大于 1就换一种改写方式。这个“换改写方式”的过程本质上就是在构造一个收缩映射而压缩映射原理保证了这个映射存在唯一不动点且迭代收敛。2.2 收敛速度的量化线性收敛到底有多慢不动点迭代通常是线性收敛的意思是误差每迭代一次大约缩小一个固定比例。如果 |g(x*)| c 1那么 e_{k1} ≈ c · e_k也就是说每步误差乘以 c。c 0.5 意味着每步误差减半大约 10 步能缩小到千分之一c 0.9 意味着每步只缩小 10%要 60 多步才能达到同样的精度。这个差异在实际计算中非常致命。我曾经用不动点迭代解一个热传导方程离散化后的非线性系统一开始选的改写方式收敛因子大约 0.95跑了上千次迭代才勉强达到 1e-6 的残差。后来换了一种改写方式收敛因子降到 0.3 左右同样的精度只需要二十几次迭代。计算时间直接从分钟级降到秒级。这件事给我的教训是迭代算法的性能瓶颈往往不在单步计算量而在收敛速度。单步再快收敛慢也是白搭。提示判断一个不动点迭代是否值得用先估算收敛因子。如果 |g(x*)| 接近 1别犹豫换方法。牛顿法或者松弛迭代通常是更好的选择。2.3 松弛因子一个简单但极其有效的加速手段当你发现不动点迭代收敛太慢但又不想换整个方法时松弛迭代是一个成本极低的改进方案。它的做法是在原始迭代公式上加一个松弛因子 ωx_{k1} (1 - ω) x_k ω g(x_k)。当 ω 1 时就是原始迭代ω 1 叫欠松弛通常用于不稳定情况ω 1 叫过松弛用于加速收敛。松弛因子的选取没有万能公式但有一个经验范围对于线性收敛的不动点迭代最优松弛因子通常在 1 到 2/(1 sqrt(1 - c²)) 之间其中 c 是原始迭代的收敛因子。实际使用中我一般会先试 ω 1.2 到 1.5观察残差下降曲线如果下降变快就继续微调如果出现震荡就减小。这里有个坑值得单独说松弛因子不是越大越好。过大的 ω 会让迭代震荡甚至发散。我见过有人为了“加速”直接把 ω 设成 1.9结果残差在几个值之间来回跳永远不收敛。正确的做法是从小到大逐步试探找到那个让残差单调下降的最大值。3. 牛顿法用切线代替曲线用二阶换速度3.1 从几何直觉到迭代公式牛顿法也叫牛顿-拉弗森法是不动点迭代的一个特例但它的构造方式完全不同。它的几何直觉是在当前点 x_k 处用函数的切线来近似原函数然后取切线与 x 轴的交点作为下一个迭代点。因为切线是直线求交点非常容易所以每一步的计算量很小。把几何直觉翻译成公式切线方程是 y f(x_k) f(x_k)(x - x_k)令 y 0 解出 x得到 x_{k1} x_k - f(x_k) / f(x_k)。这就是牛顿法的迭代公式。它要求 f 可导且 f(x_k) ≠ 0。牛顿法最吸引人的地方是它的收敛速度在单根附近它是二次收敛的。意思是误差的平方量级决定下一步误差e_{k1} ≈ C · e_k²。如果当前误差是 0.1下一步大约是 0.01 量级再下一步就是 0.0001 量级。有效数字大约每步翻倍。这和不动点迭代的线性收敛完全不是一个量级。我第一次真正体会到二次收敛的威力是在解一个非线性方程组的时候。用不动点迭代跑了 200 多步才到 1e-8换成牛顿法之后 5 步就到了 1e-12。当时的感觉就是原来算法选对了计算量可以差这么多。3.2 牛顿法的三个致命弱点但牛顿法不是万能的它有三个非常现实的弱点每一个我都亲身踩过。第一个弱点是对初始值极其敏感。牛顿法只在根的附近才保证二次收敛如果初始值离根太远迭代可能发散也可能跑到另一个根上去。我做过一个测试对 f(x) arctan(x)从 x₀ 1.5 出发牛顿法会直接飞到 x ≈ -1.5 附近然后来回震荡永远不收敛。原因是 arctan 在远处的导数趋近于 0切线几乎水平交点跑到无穷远去了。第二个弱点是需要计算导数。对于简单的函数导数可以手算但对于复杂的工程问题导数可能根本写不出解析表达式。这时候要么用数值差分近似导数会损失一些精度和收敛速度要么用割线法用两点连线代替切线不需要导数但收敛阶降到 1.618 左右。第三个弱点是每次迭代的计算成本高。对于多维问题牛顿法需要计算雅可比矩阵并求解线性方程组单步计算量是 O(n³)。如果维度很高单步成本可能高到无法接受。这就是为什么深度学习里几乎不用牛顿法而是用各种一阶方法。3.3 阻尼牛顿法与线搜索让牛顿法变得可靠针对初始值敏感的问题最常用的改进是阻尼牛顿法。它的思路很简单牛顿方向 d -f(x_k)/f(x_k) 本身是一个很好的下降方向但不一定适合走满步。于是引入一个步长因子 α_k让 x_{k1} x_k α_k · d其中 α_k 通过线搜索确定保证 f(x_{k1}) 比 f(x_k) 有足够下降。线搜索的常用准则是 Armijo 条件f(x_k α d) ≤ f(x_k) c · α · f(x_k) · d其中 c 是一个小常数通常取 1e-4。实际操作中我会从 α 1 开始如果条件不满足就减半直到满足为止。这个“回溯线搜索”实现简单效果稳定是我在工程代码里最常用的策略。注意阻尼牛顿法虽然更稳定但线搜索本身也有成本。如果函数求值很贵线搜索的额外开销可能抵消掉牛顿法收敛快的优势。这种情况下可以考虑固定小步长或者用更高效的线搜索策略。4. 梯度下降及其变体高维优化的主力4.1 为什么梯度下降在深度学习里无可替代梯度下降是迭代算法在优化领域最广为人知的应用。它的迭代公式简单到不能再简单x_{k1} x_k - η · ∇f(x_k)其中 η 是学习率∇f 是梯度。它的物理意义是沿着函数下降最快的方向走一小步然后重新计算梯度再走一步。和牛顿法相比梯度下降只用到一阶信息单步计算量是 O(n)远低于牛顿法的 O(n³)。虽然收敛速度只是线性收敛但在高维问题里单步成本的优势远远压倒了收敛速度的劣势。这就是为什么深度学习模型动辄上亿参数却依然用梯度下降及其变体来训练。但梯度下降有一个非常现实的问题学习率 η 的选取极其困难。η 太小收敛慢到让人怀疑人生η 太大残差震荡甚至发散。更麻烦的是最优学习率取决于函数的曲率而曲率在不同方向上可能差异巨大。这就是所谓的“病态条件”问题。4.2 动量法用历史信息平滑更新方向动量法Momentum是梯度下降最经典的改进之一。它的做法是引入一个速度变量 v让 v_{k1} β · v_k ∇f(x_k)然后 x_{k1} x_k - η · v_{k1}。其中 β 是动量系数通常取 0.9 左右。动量法的直观理解是如果梯度方向在连续几步里保持一致速度会累积步长变大加速收敛如果梯度方向来回震荡速度会相互抵消步长变小抑制震荡。这就像给优化过程加了一个“惯性”让它能冲过平坦区域也能在峡谷地形里减少左右摇摆。我在实际调参中发现动量系数 β 0.9 是一个很稳的默认值但在某些问题上 0.95 甚至 0.99 效果更好。判断标准是看损失曲线的平滑程度如果曲线震荡明显增大 β如果曲线过于平滑但下降慢减小 β。4.3 Adam 优化器自适应学习率的工程实践AdamAdaptive Moment Estimation是目前工程中最常用的优化器之一。它同时维护梯度的一阶矩估计均值和二阶矩估计方差然后用这两个估计来调整每个参数的学习率。具体来说每个参数的学习率会根据它的历史梯度大小自动缩放梯度大的参数学习率小梯度小的参数学习率大。Adam 的默认超参数是学习率 0.001、β₁ 0.9、β₂ 0.999、ε 1e-8。这套默认值在大多数问题上都能工作得不错这也是它流行的原因之一。但我必须说Adam 不是万能的。在某些问题上精心调参的带动量 SGD 最终能达到更好的泛化性能而 Adam 虽然收敛快但可能收敛到不那么好的解。我自己的经验是做原型和快速实验用 Adam追求最终性能时用 SGD 动量 学习率衰减。这个策略在多个项目里都验证过虽然不是绝对规律但作为一个起点是合理的。优化器收敛速度调参难度内存开销适用场景朴素梯度下降慢高低教学、简单问题动量法中等中低一般优化问题Adam快低中深度学习原型牛顿法很快高高低维、二阶可导5. 共轭梯度法解大型线性系统的利器5.1 从最速下降的“锯齿”现象说起共轭梯度法Conjugate Gradient, CG是迭代算法在数值线性代数里最重要的成果之一。它解决的问题是求解线性方程组 Ax b其中 A 是对称正定矩阵。这个问题看起来简单但当 A 的维度达到百万级时直接求逆或者做 LU 分解的计算量是天文数字而 CG 可以在几十到几百步内给出足够好的近似解。CG 的动机来自最速下降法的一个缺陷。最速下降法就是梯度下降在线性系统上的版本在求解 Ax b 时每一步的搜索方向是当前残差 r_k b - Ax_k。这个方向在相邻两步之间是正交的导致迭代路径呈现“锯齿”形状——在狭长的椭圆等高线里来回横跳收敛极慢。CG 的改进思路是不要用残差方向而是构造一组关于 A 共轭的方向。两个方向 p_i 和 p_j 关于 A 共轭的意思是 p_i^T A p_j 0。在共轭方向下每一步的搜索不会“破坏”之前方向的进展因此理论上 n 步就能精确求解 n 维线性系统。实际中由于浮点误差通常需要更多步但收敛速度仍然远快于最速下降。5.2 CG 的实现细节与预处理技术CG 的迭代公式不长但实现时有几个细节容易出错。首先是初始残差的计算r₀ b - Ax₀初始方向 p₀ r₀。然后是每步的更新α_k (r_k^T r_k) / (p_k^T A p_k)x_{k1} x_k α_k p_kr_{k1} r_k - α_k A p_kβ_k (r_{k1}^T r_{k1}) / (r_k^T r_k)p_{k1} r_{k1} β_k p_k。这里有一个数值稳定性上的坑r_{k1} 理论上应该等于 b - Ax_{k1}但实际计算中由于舍入误差两者会逐渐偏离。如果直接用递推公式更新 r误差会累积如果每步重新计算 b - Ax计算量会翻倍。工程上的折中方案是每隔一定步数重新计算一次残差或者用更稳定的递推公式。预处理技术是 CG 实用化的关键。原始 CG 的收敛速度取决于 A 的条件数 κ(A)条件数越大收敛越慢。预处理的思想是找一个容易求逆的矩阵 M使得 M⁻¹A 的条件数远小于 A然后在预处理后的系统上跑 CG。常用的预处理子包括对角预处理Jacobi、不完全 Cholesky 分解、代数多重网格等。我做过一个对比实验对一个条件数约 10⁶ 的稀疏矩阵原始 CG 跑了 3000 多步才收敛加上对角预处理后降到 800 步用不完全 Cholesky 预处理后只要 150 步。预处理子的选择对性能的影响往往比 CG 本身的实现优化大得多。5.3 CG 的适用边界什么时候不该用它CG 虽然强大但它有明确的适用边界。首先它要求 A 是对称正定的。如果 A 不对称需要用 BiCGSTAB、GMRES 等变体如果 A 对称但不定CG 可能 breakdown。其次CG 适合稀疏矩阵因为它的核心操作是矩阵-向量乘法稀疏矩阵的乘法成本是 O(nnz)远低于稠密矩阵的 O(n²)。如果 A 是稠密的CG 的单步成本会很高可能不如直接分解。还有一个容易被忽略的点CG 的收敛性依赖于特征值的分布。如果 A 的特征值集中在几个簇里CG 收敛很快如果特征值均匀分布在一个大区间里CG 收敛很慢。这就是为什么预处理如此重要——它本质上是在改变特征值分布把分散的特征值聚拢起来。6. 迭代算法的收敛判断与停止准则6.1 残差、误差与它们之间的微妙区别迭代算法必须有一个停止准则否则会无限循环下去。最常用的停止准则是残差范数小于某个阈值||r_k|| tol。但这里有一个微妙的问题残差小不等于误差小。残差是 b - Ax_k误差是 x_k - x*两者之间差了一个 A 的条件数||x_k - x*|| ≤ ||A⁻¹|| · ||r_k||。如果 A 的条件数很大残差很小的时候误差可能依然很大。我在实际项目中遇到过这种情况残差已经降到 1e-10但解的实际误差还有 1e-3。原因是矩阵条件数达到了 1e7残差的缩小并没有等比例地反映到误差上。后来我改用相对残差 ||r_k|| / ||b|| 作为准则并且结合对解的先验估计来判断是否真的收敛。另一个常用的准则是步长准则||x_{k1} - x_k|| tol。这个准则在梯度下降里很常见但它也有问题如果步长很小但方向一直在变可能并没有真正收敛。我一般会同时监控残差和步长两者都满足才认为收敛。6.2 最大迭代次数一个必须设置的保险无论收敛准则多么合理都必须设置一个最大迭代次数。原因很简单有些问题就是不收敛或者收敛速度慢到不可接受。如果没有最大迭代次数程序可能永远卡在那里。最大迭代次数的设定需要结合问题规模和预期收敛速度。对于 CG 解线性系统一个常用的经验值是 10n 到 20n其中 n 是矩阵维度。对于梯度下降我一般设 10000 到 100000 步具体取决于单步成本。如果达到最大迭代次数还没收敛就应该输出警告信息并返回当前最好的结果而不是直接报错退出。提示在生产代码里我习惯把迭代历史残差、步长、目标函数值记录下来收敛后画一条曲线看看。这条曲线能告诉你很多信息收敛是线性的还是超线性的有没有震荡有没有平台期。这些信息对调参和诊断问题非常有用。7. 我踩过的那些坑与调参心得7.1 初始值选不好后面全白搭迭代算法对初始值的依赖程度怎么强调都不为过。牛顿法初始值离根太远会发散梯度下降初始值落在鞍点附近会停滞CG 初始值太差会需要更多迭代。我吃过最大的亏是在解一个非线性最小二乘问题时随手把初始值设成了全零向量。结果迭代了 5000 步还没收敛后来换了一个基于物理直觉的初始值50 步就搞定了。选初始值的经验法则能用量级估计就用能用物理直觉就用实在没有就用多个随机起点试。对于优化问题多个随机起点不仅能避免局部极小还能帮你判断问题的非凸程度。如果不同起点收敛到完全不同的解说明问题非凸严重需要更谨慎地处理。7.2 学习率不是玄学但确实需要耐心学习率的调整是梯度下降类算法最耗时的部分。我的做法是先用一个较大的学习率比如 0.1跑几步观察损失是否发散如果发散就除以 10直到不发散为止。然后在这个基础上做精细调整通常取不发散的最大学习率的一半左右。对于带动量的 SGD学习率可以比朴素梯度下降稍大一些因为动量有平滑效果。对于 Adam默认的 0.001 通常是个不错的起点但在某些问题上 0.0001 或 0.01 效果更好。我一般会跑一个学习率扫描取几个对数等距的值1e-4, 3e-4, 1e-3, 3e-3, 1e-2各跑少量步数看哪个损失下降最快。7.3 收敛曲线会说话关键是你得会听迭代算法的收敛曲线是最重要的诊断工具。一条健康的收敛曲线应该是单调下降的可能前期快后期慢但不应该有明显的上升段或剧烈震荡。如果曲线出现上升说明步长太大或者方向有问题如果曲线出现平台期说明可能陷入了鞍点或者局部极小如果曲线震荡剧烈说明学习率太大或者问题条件数太高。我习惯在训练过程中定期打印残差和步长并且用对数坐标画出来。对数坐标下的线性收敛表现为一条直线超线性收敛表现为向下弯曲的曲线。如果直线斜率很平说明收敛因子接近 1需要考虑加速如果曲线向下弯曲说明收敛速度在加快是好现象。8. 迭代算法的选型决策框架8.1 从问题结构出发选择算法面对一个具体问题怎么选迭代算法我的决策框架是这样的首先看问题类型。如果是求解 f(x) 0 且 f 可导优先考虑牛顿法或割线法如果是求解 min f(x) 且维度不高牛顿法或拟牛顿法BFGS、L-BFGS是好选择如果是高维优化梯度下降及其变体更合适如果是求解 Ax b 且 A 对称正定CG 是首选。然后看计算资源。如果单步计算成本很高比如每次迭代都要解一个偏微分方程就应该选择收敛速度快的算法哪怕单步成本高一些。如果单步成本低但维度很高就应该选择单步成本低的算法哪怕需要更多迭代。最后看实现复杂度。牛顿法需要计算 Hessian 矩阵实现复杂且容易出错梯度下降只需要梯度实现简单CG 介于两者之间。如果项目时间紧从简单方法开始不够用再升级通常比一开始就上复杂方法更稳妥。8.2 混合策略先用慢方法探路再用快方法冲刺一个在实践中非常有效的策略是混合使用不同算法。比如先用梯度下降跑几百步让参数进入一个较好的区域然后切换到牛顿法或 L-BFGS 做精细收敛。这样既避免了牛顿法对初始值的敏感性又利用了它的快速收敛。另一个常见的混合策略是在 CG 里用预处理。预处理子本身可能是一个简单的迭代方法比如几步 Jacobi 或 SSOR它的作用是改善条件数让 CG 更快收敛。这种“迭代套迭代”的结构在数值计算里非常普遍设计得当的话效果很好。8.3 什么时候该放弃迭代改用直接法迭代算法不是万能的。如果问题规模很小比如 n 1000直接法LU 分解、Cholesky 分解、QR 分解可能更快更可靠。直接法没有收敛性问题一次分解就能得到精确解在浮点精度范围内。迭代法的优势只在大规模稀疏问题上才体现出来。我的一般原则是n 1000 用直接法n 10000 用迭代法中间地带看稀疏性和条件数。当然这只是粗略估计具体问题还要具体分析。如果矩阵是稠密的且 n 5000直接法的 O(n³) 大约是 1.25e11 次浮点运算现代 CPU 几秒钟能完成而 CG 如果条件数很大可能需要几千步每步 O(n²) 2.5e7总共 1e11 次运算差不多。这种情况下直接法反而更省心。9. 写在最后迭代思维比迭代算法更重要聊了这么多具体算法我想最后说一个更本质的东西。迭代算法的核心不是某个公式而是一种思维方式当直接求解不可能时用一系列简单操作的重复来逼近答案。这种思维方式的价值远远超出了数值计算本身。我在做工程系统设计时经常用迭代思维来拆解问题先做一个能跑通的最简版本然后根据反馈逐步改进而不是一开始就追求完美方案。这和不动点迭代的逻辑是一样的——先有一个粗糙的初始猜测然后每一步都让它更好一点直到足够好为止。当然迭代思维也有它的代价你需要有耐心需要能接受“暂时不完美”需要知道什么时候该停止。这些判断力比记住几个迭代公式重要得多。公式可以查但判断力只能靠实践积累。我到现在也不敢说自己对迭代算法的理解有多深每次遇到新问题还是会有“这个初始值该怎么选”“这个学习率合不合适”的犹豫。但至少我知道犹豫是正常的迭代本来就是一步步试出来的。