为什么不求逆矩阵?
大型最小二乘问题或正则化模型可能产生方程组 :矩阵 的维数很大,但计算它与向量的乘积仍然可行。即使 很稀疏,显式存储 也可能不可行。共轭梯度法(CG)只用矩阵向量乘法、向量更新和内积来构造近似解,不必保存逆矩阵。它的保证要求一类特定的矩阵;推导先假定精确算术,再另行讨论有限精度。
定义 4.5.1
(对称正定矩阵与 -内积)
若实矩阵 满足 ,且对每个非零 都有 ,则称 为对称正定(SPD)。对 SPD 矩阵 ,-内积为 ;若 ,则称 -正交(共轭)。
线性方程组等价于最小化一个二次函数,而这一改写推动了方法的每一步。
引理 4.5.2
(把方程组化为二次最小化)
设 对称正定,,。则 ,且对每个 ,
因此 是 的唯一最小点,而残差 是负梯度。
证明
(配方)
由对称性,,所以 。利用 及 ,
由正定性,除非 ,右边都为正。
若每次都只沿残差移动,就是最速下降法,后续步骤可能抵消先前的进展。CG 选取互相 -正交的方向;沿新方向最小化时,不会破坏先前方向上的驻点条件。
递推公式
从任意 出发,令 、。若 就停止;否则计算
若 就停止;否则令
由正定性,非零方向满足 ;分母不是可以随意调节的参数。残差递推来自 ,因此初始化后每一步只需一次新的乘积 。这一说法不包括生成或存储 的成本,也不包括分布式内积所需的通信。
定理 4.5.3
(精确算术下的 CG)
设 对称正定。停止之前,各方向非零且两两 -正交, 与此前所有方向正交。 是 上 的唯一最小点。该方法至多经过 次迭代得到精确解。
证明
(对方向作归纳)
归纳假设 两两 -正交,且 与 正交。当 时 ,所以 ; 时也成立。 的导数为 ,在 处为零。并且
若尚未停止,则 非零:否则它与 的内积为零,但这个内积等于 。当 时,由 ,再利用 与此前方向正交,可知 ,因为右边两个残差都属于此前方向张成的空间。当 时,同一递推与残差正交性给出 。又 ,故上述 使 ;当 时, 的两项都为零。归纳完成。
由于 与所述空间的一组基正交, 沿该空间的方向导数都为零;严格正定性保证它是唯一最小点。非零且两两 -正交的向量线性无关,因此至多有 个方向。若已走过 个方向,残差与 的一组基正交,必为零。
证明每一步只显式强制一个正交条件,却得到与所有更早方向的正交性。
证明透视
一次修正换来全部旧的正交性
正定性用了两次:它使每个步长的分母为正,并把搜索空间上的驻点变成唯一最小点。对称性使条件可以按任意次序读取,于是两个方向的 -正交只是一个条件而不是两个。关键一步是恒等式 :它把 乘以旧方向写成两个旧残差之差。这两个残差都位于更早方向张成的空间中,而新残差已与该空间正交,所以新方向自动与除最近一个之外的所有方向共轭;系数 只需消去那一个分量。这就是 CG 只需短递推、而无须对已存储的方向做完整 Gram–Schmidt 扫描的原因。论证以计数收尾:非零共轭方向线性无关,至多有 个;与 个线性无关向量都正交的残差必为零。
例题 4.5.4
(两个方向,而非两次独立猜测)
取 ,,。于是 ,,,得到 、。接着 ,。检验得 。由于 ,故 ,得到 ,。确实 。
次迭代只是上界;下例只需一步就停止。
例题 4.5.5
(一步即终止)
取 、、。则 ,,,所以 、。更新残差为 ,真实残差 也是零。方法在此停止: 会把 除以 ,得到无意义的方向 ,所以不计算它。提前停止是因为 是 的特征向量,第一次线搜索已经到达 。
概念视角代数
CG 是最优多项式
由递推式归纳可知,在终止之前,方向 张成 Krylov 空间 。因此 ,其中 是次数至多为 且 的多项式;由引理,CG 选取的恰是使 最小的 。若 只在 的 个特征空间中有分量,由这些特征值构成的多项式 给出零误差,因此 CG 至多 步就停止,正如上一个例子和 的情形。
该方法从不需要矩阵本身,只需要一个作用该矩阵的程序。
例题 4.5.6
(无须存储矩阵的正则化算子)
令 ,即列线性相关的单独一行,并取 ,于是 对称正定,尽管 奇异。用 来作用它。以 、 求解 。
第一步:,,,,,,。
第二步:,,,。检验 。于是 ,,,。直接计算也得到 。
成本、停止条件和假设
对 的 CSR 矩阵,若存有 个条目,一次乘积需要 运算,存储需要 个数组元素。CG 保留常数个长度为 的向量,故在单位成本模型下一次迭代需要 运算。实际系统还可能有显著的同步、内存传输和预条件器成本。若使用无需显式存储矩阵的算子,则应用该算子的成本和内存取代上述 CSR 数字。精确算术定理只保证终止,并不保证扫描 次很便宜。
常见的实际准则是重新计算真实残差 ,并在 时停止,其中非负容差依应用选择。舍入会使递推更新的残差偏离真实残差。残差小也不自动意味着前向误差同样小:由 ,有 ;病态性可以放大误差。有限精度还可能破坏精确共轭性及至多 步终止的保证。应定期及退出时检查真实残差、设定迭代上限;若意外出现非正的 ,应调查算子或数值失效,而不是宣布收敛。运行中替换递推残差会改变后续算法,需要恰当的实现策略。
常见错误
(只凭更新残差停止)
循环中的 由 产生,而不是计算 。精确算术下两者相同;浮点运算中两者会逐渐分离,真实残差停滞之后,更新残差仍可能继续变小。若只因 很小就报告收敛,而退出时不重新计算 ,就可能认证一个未达到容差的迭代值。
常见错误
(恰好跑 次迭代就停止)
“至多 步”是精确算术下的终止结论。浮点运算中方向会失去共轭性,所以 步后残差未必为零;当 很大时,本来的用法是依据残差测试远早于此就停止。应使用基于残差的停止准则并配合迭代上限,而不是以维数作为停止准则。
对最小二乘,若 ,则 对称正定;可用 而不形成 。这可能节省存储,但正规方程可能恶化条件数,不能因此省略精度检查。固定的 SPD 预条件器可能改善变换后系统,但构造和应用它均有成本,而且需要相应的预条件递推。
反例模式
仅有对称性并不足够
取 、、。则 ,尽管 ,仍有 ,所以第一个步长就要除以零。这个矩阵对称且可逆,解为 ,却是不定的。修正后的假设是正定性,它保证每个非零方向都有 。
练习与解答
快速检查
(设 、、。比较 和 。)
先求 。
解答 · 答案
解为 ,故 ,但 。这恰好达到上界 。绝对残差小并不能单独保证同样小的误差。
快速检查
(证明对任意实矩阵 和 , 对称正定,即使 的列线性相关也是如此。)
展开 。
解答 · 答案
它是对称的;对非零 ,有 。当 时第一项可以为零;正则项提供严格正性。
快速检查
(在 的例子中,验证第二步保留沿 的零方向导数。)
利用残差递推及共轭性 。
解答 · 答案
第一步后 。由于 ,有 。 沿 的方向导数是 ,所以仍为零。这正是保留先前进展的机制。
快速检查
(对 、任意 及 ,CG 需要多少次迭代?)
计算 。
解答 · 答案
一次。此时 ,,所以 ,。每个非零向量都是 的特征向量,因此第一次线搜索已经是精确的。