形式陈述
预条件共轭梯度法(PCG)求解 ,其中 。除矩阵—向量乘 外,算法需要一个固定的线性接口
这里的Hermitian 正定理路正定与半正定矩阵Positive definite matrix · Positive semidefinite matrix · PSD matrix由二次能量严格为正或非负定义的实对称与复 Hermitian 矩阵。条件同时约束原矩阵与预条件器。实现可以只提供 apply,不显式存储 或其逆;所提供的映射必须在所有迭代中保持同一个线性、自伴、正定算子。 近似 是为了改善收敛, 易于计算则是获得实际加速的前提。
给定 ,先计算真实残差 。若它已满足停止准则,就直接返回 ;否则初始化
第 步先计算
再更新
若新近似通过真实残差检查,则结束;若继续迭代,则计算
精确算术中,只要尚未得到解,、,步长和继续迭代时的 都是正实数;复数数据必须使用共轭转置。 时,这些公式逐项退化为普通共轭梯度法理路共轭梯度法Conjugate gradient method · CG method在 Hermitian 正定系统的 Krylov 子空间中最小化能量误差,以三项递推获得共轭方向和短存储迭代。。两处标量递推都使用 ,不能只把方向中的 换成 ,却保留普通 CG 的 。
接口还应接受非负的绝对、相对容差和工作预算,并返回原变量 、真实残差、迭代次数、 与 apply 的调用次数及退出状态。本文采用的成功准则是
这一定义对 仍有意义;若此时也取 ,要求的便是零残差。内部的 不是这个停止量。
直觉
预条件理路预条件Preconditioning · Preconditioner用易应用的近似逆改变等价线性系统的尺度与 Krylov 几何,并计入构造、存储和每步应用成本。改变 CG 观察问题的坐标。取分解 ,令
非奇异,且对非零 有
所以 仍是 Hermitian 正定矩阵,可以对 应用普通 CG。以下推导使用普通 CG 已有的正交性与最小化定理,证明它如何成为上述 PCG;并不另行重证普通 CG 定理。
记变换坐标中的残差和搜索方向为 ,映回原变量时定义
普通 CG 的初始方向 因而给出
它的步长分子和分母分别变成
因此 正好给出 PCG 的步长。对普通更新 左乘 ,便得到原变量的 更新;对 左乘 ,便得到 。剩下两条普通 CG 递推为
第二式左乘 后成为 ,完整解释了 apply 和方向更新的来源。 只用于证明,执行算法不必构造或调用它。
同一映射也确定了正确的内积几何理路内积空间Inner product space带正定对称双线性形式或正定 Hermitian 半双线性形式的向量空间。。普通 CG 的 与 分别给出
原残差在 内积中正交,搜索方向仍在原来的 内积中共轭。通常并没有 ;把普通 CG 的 Euclidean 残差正交性直接搬到原变量,会遗漏整个坐标变化。
令 。它通常不是 Euclidean Hermitian 矩阵,因为 ;但它在 内积中满足
此外 ,故 与正定矩阵 相似,具有相同的正特征值。PCG 的几何来自这种带权自伴性,不能由“左乘以后看起来更好解”替代。
例子与边界
取一个只需二阶块求解和一次缩放的预条件器:
令
的特征值为 ,所以 均正定。这里 ,且 、,两者并不交换;因而此例保留了左预条件算子不对称的真实情形。对向量 ,apply 明确为
以下均为精确分数,表中三元组表示列向量。先列出每个时刻的解、残差和预条件残差:
|
|
|
|
| 0 |
|
|
|
| 1 |
|
|
|
| 2 |
|
|
|
| 3 |
|
|
无须计算 |
产生这些状态的三个搜索方向及其矩阵乘积为
标量更新与误差检查单独列出。最后一行的 是由零残差得出的值,不需要再执行 apply。
|
|
|
|
|
|
| 0 |
|
|
|
|
|
| 1 |
|
|
|
|
|
| 2 |
|
|
停止 |
|
|
| 3 |
|
— |
— |
|
|
例如第二步的分母为 ,所以 ;它把 更新为 。第三步的分母为 ,所以 ,直接得到 。这完整执行了三步递推,而非仅展示初始与最终状态。
这个历史同时区分了三种量。首先 ,但 ,正交性确实依赖权重。其次,第二步的原残差范数由 增到 ,能量误差平方却由 降到 。最后, 与能量误差平方的数值也不相同;本例中二者恰好都下降,不能据此把预条件残差当作能量误差。
谱改善也可以精确检查:
原矩阵的坐标 Rayleigh 商给出 、,从而 。廉价块预条件确实缩小了谱跨度;它没有把 变成单位阵,也没有消除所有耦合。
固定线性正定的 apply 是上述推导的边界。若每一步改变内层求解容差,或使用依赖输入的非线性近似过程,就不再有同一个 和同一个 ;普通 公式因而失去这里给出的依据。即使每次返回的向量都看似合理,也需要适用于该变化方式的算法分析。
推论与应用
令 。坐标映射保持能量误差,因为
又因 且 ,有
将普通 CG 的最小化定理沿这两个等式映回,就得到 PCG 在原变量中的精确结论:
因此能量误差随嵌套的Krylov 子空间理路Krylov 子空间Krylov subspace从初始向量反复施加矩阵,生成只依赖矩阵—向量乘法的递增子空间及其 Arnoldi、Lanczos 正交基。单调不增。若 关于 的最小多项式次数为 ,精确算术中至多 步终止;浮点运算中不保证第 步得到零残差。
对整数 且 ,普通 CG 的谱界同样映回为
若已精确停止,后续近似保持为真解; 直接使用初始误差。 时 ,非零初始残差下至多一次更新即精确结束,不使用退化区间的 Chebyshev 公式。这里使用对称正定 的条件数理路线性方程组的条件数与扰动Conditioning of linear systems · Matrix condition number把一般问题条件性具体化为可逆线性系统的右端、系数矩阵与联合扰动界。。虽然 与 的特征值相同,非酉相似一般不保持奇异值,因此不能把上式中的 换成 Euclidean 奇异值条件数 。该界只使用谱端点;特征值聚集与初始误差的分量还会影响实际迭代数。
对大型稀疏 SPD 系统,标准 PCG 每个继续迭代的周期需要一次 乘法、一次 apply、两个主要内积和 向量更新;除算子及预条件结构外,只需常数个长向量。若完成 次更新并在最后一次更新后直接停止,apply 的调用数是初始一次加中间 次,共 次。初始残差计算和另行重算真实残差所需的 乘法也必须记录;已知 时可省略初始的零向量乘法。
把设置、应用和检查分开,总成本可写为
其中 包含初始及验证残差的矩阵乘法, 是实际 apply 次数, 计入额外范数与通信归约。预条件器的因子、填充或层级存储也属于成本。比较方法时,应同时报告设置时间与总求解时间;多个右端能摊销设置,而一次短求解未必能回本。
有限精度会使递推残差偏离 ,并使精确正交性逐渐丢失。可以用递推残差筛选候选停止点,再以重算的真实残差决定成功;长迭代也可定期检查漂移。如果把重算残差替换进迭代并继续,应重新设置 、、,作为一次重启,而不是保留旧方向并继续声称完整共轭性。
非零残差下的 、 或非有限输出,与精确固定 SPD 合约不相容,实际实现应停止并报告数值故障或接口失败;达到预算上限则返回未收敛状态及真实残差。初始零残差是正常成功路径,须在任何 apply 或步长除法之前处理。这样,理论中的有限步终止、用户要求的原系统精度和机器上的实际退出原因才有各自明确的含义。
多重网格 V-cycle理路多重网格 V-cycleMultigrid V-cycle递归求解残差方程,逐层展开七节点链的一次完整 V-cycle,并证明对称稳定平滑如何给出可供 PCG 使用的固定正定应用。可以提供一个具体 apply:固定 Galerkin 层级,以零初值执行一轮,并对预后平滑作转置配对。在平滑对称化部分正定、粗应用正定时,逐层展开能证明整个循环仍为固定线性 SPD 算子;随输入改变内层停止次数则需另行分析。
参考资料