动机
对大型稀疏线性系统,存储稠密分解可能比矩阵乘向量昂贵得多。迭代方法改用矩阵–向量乘积构造一系列近似。共轭梯度法利用此前收集的信息选择新搜索方向,而不是在每步应用一个固定的定常迭代矩阵。
它的特殊结构依赖矩阵性质。对实对称正定矩阵,求解 等价于最小化严格凸二次函数。共轭梯度法在矩阵给出的能量内积下选择两两正交的方向,并在逐渐扩大的 Krylov 空间中给出最佳近似。这些是精确算术定理;实际实现还需处理停止、尺度和舍入误差。
能量视角
定义 3.2.1
(对称正定性与能量范数)
令 对称正定(SPD):,且对每个非零 有 。定义
唯一解 是 的唯一最小点。事实上,对 ,
残差 是 的负梯度,满足 。
小残差和小解误差是不同结论。在 Euclidean 范数下,;病态矩阵可能放大残差。能量范数则依 对不同方向赋予不同权重。因此,能量误差最小化定理不能被说成每一步的每个 Euclidean 误差分量都下降。
定义 3.2.2
(Krylov 空间与共轭性)
从 和 出发,定义
非零向量 若在 时满足 ,则称它们 共轭。正定性使 共轭族线性无关。仿射空间 包含将次数小于 的 的多项式作用于初始残差所构造的全部修正。
算法及其保证
若 ,则 已经是解,不需要迭代。否则令 。对 ,只要 ,便计算
若 则停止;否则取
矩阵通过 使用,不必构造 。终止之前, 正定且搜索方向非零,故分母为正;下文归纳证明会证明方向非零。精确解已得到时,停止检查可避免后续零分母。
定理 3.2.3
(正交性、最小化与有限步终止)
在精确算术中,终止之前残差 两两 Euclidean 正交,方向 两两 共轭。若未提前终止,经过 步后,
并且 在 上唯一最小化 。算法至多经过 步到达精确解。
定理 3.2.4
(条件数收敛界)
令 为 的极端特征值,且 。在精确算术中,对终止之前每个 ,
若 , 是单位矩阵的正数倍,共轭梯度法至多一步终止。上式是最坏情况界,不是说实际误差每步都恰好乘以该因子。
概念视角分析
同一个迭代值:最优多项式
记 ,则 。 中每一点的误差都是 ,其中 是次数至多为 、且 的多项式;反过来,每个这样的多项式都会出现。因此 就是在此约束下使 最小的多项式所对应的点。在标准正交的特征基下,设 ,这个量等于 。所以共轭梯度法是在 的谱上的多项式逼近问题:约束是 ,并要求 在 中有分量的特征值处很小。
短递推为何有效
证明
(正交性与能量最小化)
我们同时归纳这些关系。第 步的不变量是: 非零且两两 共轭; 与先前方向正交;;所有已构造的 属于 。初始时 ,共轭性及与先前方向的正交性为空条件,,且两个向量均在 中。特别地 。假设第 步的不变量成立。当 ,由 得 。因此所选步长满足
对于 ,归纳假设给出 。每个先前残差是相应方向及前一个方向的线性组合,所以 也与 正交。
更新也保持真实残差恒等式:。为了检查下一方向的共轭性,使用 。当 ,残差正交性给出 ,且 。当 ,
所选 使这两项在 中相消。当 ,由于 ,所以 。归纳完成,并证明每个分母在终止前为正。
Krylov 归属关系同样由归纳得到:;若 ,则 ,且 。前 个方向线性无关,又位于维数至多为 的 ,所以该空间维数为 并由它们张成。所以 ,且 。对任意 ,
内积的勾股恒等式说明,给 加上任何非零 都会增大能量误差,故最小点唯一。非零共轭方向至多有 个;经过 步后,残差与整个 正交,因而为零。若更早为零,则已得到精确解。
证明透视
为什么只需要前一个方向?
一般投影方法可能需要消去沿所有先前方向的分量。这里 把较旧方向的共轭条件转化为残差正交性。只有最近一个方向需要显式的 修正。这种简洁来自对称性与相互配合的不变量,并非任意迭代方法的共同性质。
证明
(从 Krylov 最小值到谱界)
令 。由于 , 中任意修正都给出 形式的误差,其中 次数至多为 且 ;反过来,每个这样的多项式都给出 Krylov 空间中的修正。在正交归一特征向量基下写 。由 ,且谱位于 中,
最小化定理对每个符合条件的多项式给出 ,所以任取一个即可得到上界。当 ,取
其中 。在谱区间上分子的绝对值至多为一,且 。对 ,写 ,则 。在分母参数处,,因此分母倒数至多为 ,证明该界。特征值聚集或初始误差在困难特征方向上没有分量时,谱区间界可能较保守。事实上,若 只在 个不同特征值 的特征空间上有非零分量,则 满足 。Krylov 最优性因而迫使算法至多 步精确终止,也可能更早。这个更精细的结论同样依赖精确算术。
例题
例题 3.2.5
(对角系统上的两步迭代)
取 、、。于是 ,且
因此 ,并满足 。下一步 ,得到
残差也正交:。精确两步终止说明了维数定理;浮点算术中,两步后计算的残差未必恰好为零。
例题 3.2.6
(重复特征值可能提前终止)
设 , 和 任意。若 ,则 ,且 。不论维数多大,一步就能解出系统。更一般地,若 Krylov 空间提前包含所需解修正,算法可能早于 步终止;单纯统计不同特征值并不是浮点算术下的迭代保证。
例题 3.2.7
(能量误差与残差)
取 ,假设候选误差为 。则 ,、、。另一个误差 的残差范数也是一,但 Euclidean 误差和能量误差都为一。残差相对于谱的方向很重要;未经尺度调整的一个残差范数不能直接报告逐坐标误差。
反例模式
对称但非正定并不足够
取 、、。系统有唯一解 ,但 给出 ,所以共轭梯度法第一步就没有定义。此二次函数不定且无下界;该解是鞍点而非最小点。非奇异性和对称性不能替代正定性。
常见错误
常见错误
(将有限步终止当作浮点保证)
正交性、精确零残差及 步终止都使用精确算术。舍入可能破坏共轭性,也可能使递推更新的残差与显式计算的 不同。实际停止准则应考虑尺度及残差与误差的差别;精确证明本身不能提供通用浮点停止容差。
常见错误
(对任意非对称系统套用定理)
这里的算法与能量论证要求 对称正定。其他 Krylov 方法处理其他矩阵,但具有不同不变量和收敛结论。预条件也需要自己的假设:即使相关矩阵都是 SPD,左预条件后的算子在普通 Euclidean 内积下也未必对称。
总结
共轭梯度法通过短递推组合矩阵–向量乘积。在精确算术中,残差正交与 共轭性给出每个 Krylov 空间上的能量最小点,并保证至多 步终止。谱界解释条件数的作用,实现及舍入行为则需另行分析。
练习
快速检查
(取 、、。计算第一次共轭梯度步,包括 和 。)
从 开始。
解答 · 答案
,所以 。因此 ,。
快速检查
(取 、、,已知第一步为 、。求 和 ,并验证 。)
利用 。
解答 · 答案
,。它与 的 内积为 。又 ,所以 。因此 ,即精确解。
快速检查
(某 SPD 矩阵的 。计算 步时能量界的因子,并解释为何它未必是实际误差比。)
先算比值 。
解答 · 答案
此时 ,所以上界因子为 。实际比值取决于特征值、初始误差和精确算术;该不等式对具体实例不一定达到等号。
快速检查
(令 ,其中 ,残差为 。求相应误差 并解释 的作用。)
利用 。
解答 · 答案
由 ,误差为 。残差范数为 ,但误差范数为一。小特征值可以使很小的残差对应大得多的误差。