动机
消元法通过矩阵分解求解。对于大型稀疏矩阵,因子的存储可能远超原矩阵的非零项,因此值得考虑只用矩阵向量乘积及简单方程求解来逐步改善近似。不过,每一步便宜还不够;若收敛太慢,总成本仍可能很高。
定常方法反复作用同一个误差传播矩阵;Krylov 方法则在矩阵和初始残差生成的逐渐扩大的空间中搜索。对称正定系统的共轭梯度法把第二种观点与能量极小化联系起来。预条件通过一个较易求解的辅助系统改变搜索的几何。
定义
定义 7.1.1
(误差、残差与定常分裂)
设 ,实矩阵 非奇异,解为 。定义误差 及残差 。若 且 非奇异,定常迭代为
逆矩阵是分析记号,实施时解关于 的方程。写 ,分别表示对角、严格下三角及严格上三角部分。Jacobi 取 ;Gauss–Seidel 取 。迭代矩阵分别为 和 。这些定义要求所选对角或三角系统可解。
定义 7.1.2
(谱半径、正定性与能量)
谱半径为 ,最大值遍历全部复特征值。若实对称矩阵对所有非零向量满足 ,称为正定。此时能量范数及能量函数为
定义 7.1.3
(Krylov 空间与 -共轭)
令 ,当 定义
若 ,称两个方向 -共轭。这是能量内积中的正交,不能与普通点积为零混淆。
定理/命题
定理 7.1.4
(定常收敛及范数证书)
定常迭代对每个初值都收敛到 ,当且仅当 。若某诱导矩阵范数满足 ,则
严格按行对角占优给出 Jacobi 的无穷范数证书
定理 7.1.5
(共轭梯度的极小化与收敛)
若 对称正定,精确算术共轭梯度法在第 步得到 在 上的唯一极小点。非零搜索方向彼此 -共轭,残差彼此普通正交。若没有更早结束,最多经过矩阵维数那么多步达到解。
设最小最大特征值为 。当 ,
若 ,非零初始残差只需一步。正交及有限步结束的结论均针对精确算术。
概念视角结构
迭代也在选择几何
定常方法控制同一个误差矩阵的重复作用;CG 在扩大的仿射空间中选能量范数最优点;预条件用便宜的正定度量改变几何。成功的分裂、小残差及有利谱分布因而相关,却是不同证据。
因子二使小步数时的界可能保守;它也没有利用特征值聚集所带来的优势。反过来,正定本身并不能保证任意定常分裂收敛,后面的反例会具体说明。
证明思路或证明
矩阵幂与压缩
证明
(Jordan 块与几何级数)
误差递推给出 。若全部特征值模小于一,复 Jordan 形式中每个块的幂都趋零。非零特征值的块元素是固定次数的 的多项式乘特征值幂,指数衰减胜过多项式增长;零特征值块是幂零矩阵,最终为零。因此 。反之,对所有实初始误差收敛,意味着 每一列趋零,故作用于复向量也趋零。若存在模至少一的特征值,其特征向量立刻产生矛盾。这个证明不要求矩阵可对角化。
范数界由次乘性得到。令 ,有 。收敛给出 ,以几何级数估计便得后验界。Jacobi 的无穷范数恰是各行非对角绝对值之和除对应对角绝对值的最大值。范数证书不成立并不证明发散,只表示这个充分论证无法决定。
共轭梯度短递推为何有效
证明
(对短递推作归纳)
从 、 开始。残差为零便停止,否则使用
正定性保证非零方向的分母为正。归纳假设当前方向张成 且彼此共轭,而 与更早的方向正交,于是 。所选 使新残差与 正交;共轭性又使它与所有更早方向正交。
对 ,利用 ,右边两个残差都在 ,故 。对最后一个方向,
所选 恰使这两个贡献抵消,所以新方向与全部旧方向共轭。新残差属于 ,又与 正交;若它非零,便提供新的独立向量,扩大后的方向张成下一个 Krylov 空间,归纳闭合。这也证明残差彼此正交。
能量梯度为 。残差与搜索空间正交,正是严格凸二次函数在仿射空间上极小化的一阶条件;能量恒等式保证唯一性。非零共轭方向线性无关,数目不能超过维数,所以精确算术下有限步结束。
证明透视
三个不变量,两个系数
归纳同时维持三个命题:方向 张成 、它们两两 -共轭,以及 与 正交。每个系数恰好强制一个新的关系。步长 是唯一使 的选择;与更早方向的正交则由共轭性推出。 的对称性正用在这里:把 读成 。系数 只强制与 共轭。
不显然的一步,是与 的共轭性为何无需额外代价。每个 都是 中两个残差之差,而 与整个空间正交。 把 映入 这个 Krylov 性质,使两项递推可以取代完整的 Gram–Schmidt 正交化。正定性用了两次: 使 有定义,而 的严格凸性使正交条件对应唯一极小点。归纳之所以闭合,是因为非零的 属于 却与 正交,恰好把张成空间扩大一维。
特征值如何控制误差
证明
(平移缩放后的 Chebyshev 多项式)
因为 ,仿射 Krylov 空间中任一点的误差都可写为 ,其中 且 。极小化性质结合正交对角化给出
当 ,取
分子在谱区间绝对值不超过一。对 ,Chebyshev 递推给出 ,其中 。代入分母的参数,得 ,因此分母倒数不超过 ,即所需界。若 ,谱定理给出 ,一步便解出。这个界是上限而非精确的迭代次数预测。
预条件改变能量几何
选容易求解的对称正定 。令 ,变换系统为
变换后仍对称正定。在其中应用 CG,可转写为不需要平方根的预条件递推:解 ,用 、,初始方向为 。相关条件数属于 ,不能随意改成一般不对称的书写形式 的欧氏条件数。好的预条件在简单求解与有利谱结构间权衡。取 虽可一步收敛,却要求先解决原问题,通常没有算法价值。
停止判据需说明尺度及意义。绝对残差容差适合右端单位固定的问题,相对于右端范数的容差便于比较缩放后的系统;右端为零或很小时则需绝对替代。两者都不能绕过逆矩阵信息,直接变成解误差保证。定理中的能量误差适合分析,但计算过程中通常因不知道真解而无法直接求值。
基本 CG 每步需要一次矩阵向量乘积、向量更新及标量内积,预条件版本另需辅助求解。稀疏乘积成本与非零项数有关,并行计算中的内积通信也可能主导成本。因此,少几步不一定总耗时更短。昂贵的预条件分解可能适合多个右端,却不适合单次求解,需用实际成本判断。
例题详解
例题 7.1.6
(一个稀疏二元系统)
设 、,解为 。Jacobi 的 ,。零初值给出 、。Gauss–Seidel 使用刚更新的第一分量,一轮已得 。这只是具体步骤比较,不是两种方法的普遍优劣定理。
例题 7.1.7
(两步 CG 的精确计算)
取 、、。第一步 ,,。接着 ,,第二步长 ,得到 。可分别核验残差的普通点积为零,以及方向的 -内积为零。
例题 7.1.8
(对角预条件的机制)
对同一系统取 ,求解只是逐分量除法,变换矩阵为单位矩阵,故预条件 CG 一步完成。一般稀疏矩阵只用正对角部分,虽便宜,却未必得到单位矩阵或良好条件数。例子说明机制,不能保证对角预条件总有明显收益。
常见错误
反例模式
正定不保证 Jacobi 收敛
取三阶矩阵,对角为一,全部非对角项为 。特征值为 ,所以对称正定。Jacobi 矩阵的对角为零,非对角为 ,特征值为 。沿全一向量的误差每步放大 倍。正定假设适用于 CG 定理,却不能挪作这个 Jacobi 分裂的收敛保证。
常见错误
(把小残差当作小误差)
界 含有条件信息。取 、误差 ,残差 的范数为 ,误差范数却为一,上述界恰好取等。同样,迭代变化量小,也要有压缩证书才成为误差界。
常见错误
(把精确算术的 CG 恒等式当作硬件保证)
浮点 CG 会失去精确正交,可能需要超过维数的步数;递推更新的残差也可能偏离实际的 。应在合理的停止检查点重新计算实际残差;有限步结束定理并非计算机上的步数上限。
总结
定常收敛等价于谱半径小于一,压缩范数给出可计算误差证书。精确 CG 在 Krylov 空间中极小化能量,具有共轭方向及谱收敛界。正定预条件把分析转移到变换系统。判断数值停止是否认证原方程,还需条件及有限精度信息。
练习
快速检查
(对 ,求 Jacobi 矩阵、无穷范数及谱半径。若相邻迭代变化至多 ,求当前误差的压缩上界。)
;把非对角元素除以该行的对角元素。
解答 · 答案
,无穷范数为 。特征值为 ,谱半径为 。当前误差不超过 乘变化量,即 。谱半径虽然更小,却不能直接替换这个特定范数证书中的 。
快速检查
(给出 但 的矩阵,解释其迭代为何仍收敛,以及第一步误差增长为何不矛盾。)
幂零矩阵的谱半径为零。
解答 · 答案
取 ,谱半径为零,无穷范数为二。因为 ,任意误差至多两步消失,某些误差第一步却会增长。谱判据允许暂态放大,而指定范数中的压缩估计不允许。
快速检查
(若正定矩阵特征值在 ,用定理估计六步 CG 后的能量误差比。这个界是否断言等号或有限精度结束?)
时 。
解答 · 答案
,故比值至多 。这是精确算术上界,可能很保守;它不表示等号,也不保证有限精度维持精确残差及共轭恒等式。
快速检查
(取 、,求变换矩阵、条件数及非零残差的精确预条件 CG 步数。为何平方根形式主要用于分析?)
这里 是对角矩阵。
解答 · 答案
,故 。条件数为一,非零残差一步解出。实际算法只解关于 的方程并使用 ,无需构造矩阵平方根。