为什么要改变方程组?
有限元网格细化可以改善近似,却也可能令刚度矩阵的条件数变差。共轭梯度法(CG)只需矩阵向量乘法便可求解对称正定方程组,但迭代次数仍可能随特征值的分散程度增长。预处理改变求解的几何,使特征值可能较集中;只有当变换本身的成本低于所节省的工作时,它才有实际价值。
设 对称正定,,预处理矩阵 固定且对称正定。写 表示求解 ,无须构造逆矩阵。令 为 的解。下文恒等式和终止结论均采用精确算术;前文的 CG 结果使用能量范数 。
定义 1.5.1
(对称预处理)
有对称正定平方根。令
则 等价于 。对任何非零 ,有 ,故 亦对称正定。
这是用来推导的变换;实现时只需作用 及求解与 相关的方程,无须形成 。矩阵 与 相似,因此特征值都是正实数,但它一般并非欧氏(Euclidean)内积下的对称矩阵。不改变内积便直接把普通 CG 递推套于它,并无上述理论保证。
推导可实现的递推
写 、。若 ,初始向量已是解;否则设 、。当 ,计算
若 就停止;否则解 ,再设
这个递推就是 的普通 CG,改用原变量写出。
引理 1.5.2
(与变换后系统上的 CG 等价)
对 从 开始执行普通 CG,其残差为 ,搜索方向为 。则在终止前的每个 ,
两种方法使用相同的 与 ,并在同一步终止。
证明
(对三个变换量作归纳)
当 ,,且 。设三个关系在第 步成立,则
所以普通 CG 的步长等于 (1) 中的 。于是 ,而 。由于 可逆, 当且仅当 ,故两者的终止时刻相同。否则普通系数 等于 (2) 中的 ,并且 。
证明透视
递推从何而来
归纳同时处理三个关系,而它们以两种不同方式变换:迭代值与搜索方向乘上 ,残差则乘上 。正是这种不对称使方法能够实现。普通 CG 需要的每个内积,即 与 ,都变成 或 ,其中平方根互相抵消;唯一新增的运算是为求 而解一次与 相关的方程。
的对称正定性用了两次:一是使实对称平方根存在,二是使 时 为正,从而 有定义。论证之所以能够完成,是因为 可逆,两个终止事件完全相同,所以等价性对整个计算成立,而不只是到某一步为止。
正定保证非零残差有 ; 正定和 CG 的构造保证终止前 ,故上述除法有效。除向量运算和内积外,每个未终止步骤需要一次 乘法和一次 求解。稠密或昂贵的预处理可以抵消减少迭代的好处。
定理 1.5.3
(最小化、终止与条件数界)
固定的 均对称正定且 时,预处理 CG 在终止前给出下列仿射空间中 的唯一最小值:
它至多 步到达 。设 ;若 ,则
若 ,一步便足够。
证明
(先转移,再用切比雪夫(Chebyshev)多项式)
上述等价性把普通 CG 的 Krylov 空间最小化和有限终止结果由 移到 ,因为 。为证 (3),CG 在所有 中最小化,其中 、。将 正交对角化,可用 乘初始 范数来估计误差,这里 、。取缩放的切比雪夫(Chebyshev)多项式
利用 上 ,以及 时分母等于 ,便得 (3)。若 ,则 ,首次直线最小化即得解。这个界只用到两端的特征值;特征值集中时它可能偏悲观,也不能保证总计算时间较短。
完整的两步计算
例题 1.5.4
(对角预处理)
取 、、 和 。则 、、、。故 ,而
解 方程得 及 ,故 、。现在 ,所以 、。直接相乘确认 。此处 的条件数为 ,而 的为 。
初始搜索方向一般不是初始残差,而是预处理后的残差。每步最小化的是误差的 范数,一般不是残差的欧氏范数。变换后条件数较小,本身并不说明 的求解成本。下面两个例子说明条件数度量什么、不度量什么。
例题 1.5.5
(耦合矩阵的 Jacobi 缩放)
设 ,取对角(Jacobi)预处理矩阵 。 的特征值为 与 ,所以 。由 得
(3) 中的因子由 降到 ,而作用 只需每个分量一次除法。由于 ,精确算术下两种方法都至多两步终止;能推广到大型矩阵的是因子的比较。
例题 1.5.6
(两个不同特征值使上界失效)
取 、、、。此时 ,(3) 中的因子为 ,所以两步后 (3) 只保证 ,没有提供任何信息。然而 。由定理, 在所有满足 、次数不超过二的多项式上最小化 ;多项式 在两个特征值处都为零,所以 ,最小值为零。具体来说,,,,;第二步便到达 。上界只看到两端的特征值,因此看不见特征值的聚集。
常见错误
(用预处理残差作停止判据会受 的尺度影响)
反正要计算,所以人们容易在 很小时就停止。但把 换成 ()时,每个迭代值 都不变, 却除以 ;同一个迭代值能否通过固定容差,竟取决于一个任意的尺度。应以 为基准检验 ,或者只在已知 的有效下界时使用 ,如下面的残差证书。
反例模式
预处理矩阵为何要正定
取 、、。虽然 ,却有 。公式 (1) 已失去 CG 推导所依赖的正量; 可逆及对称并不足够。
练习与解答
快速检查
(精确预处理:若 ,从任意 出发最多需要多少步?)
先计算 。
解答 · 答案
,故至多一步。也可以看出 ,而 ,所以 。这通常不划算,因为求解预处理方程就是原问题。
快速检查
(缩放:以 代替 ,其中 。变换后的条件数和迭代值如何改变?)
跟踪 、 与 的变化。
解答 · 答案
变为 ,所有特征值都乘 ,比值不变。精确算术下 的迭代值也相同:新的 是原来的 倍, 除以 ,每个 是原来的 倍,所以 不变;每个 也不变。
快速检查
(残差证书:证明 。)
用 变换误差。
解答 · 答案
设 、,则左边为 。由 ,又有 。对角化得 ,因为每个特征值都满足 。要得到实用的数值证书,必须有有效的最小特征值下界。
快速检查
(左乘的陷阱:若 、,计算 。)
把 的每一行除以 相应的对角元。
解答 · 答案
结果是 ,不是对称矩阵,尽管 都对称正定。须使用对称变换或等价的预处理递推。
本分析假设固定对称正定的 被精确作用,且使用精确算术。舍入误差、不精确或变动的内层求解、实际停止规则、可扩展预处理的构造和实测性能都需要另外分析。