数值线代 III · Krylov方法、重启与真实残差

本页问题：同样的条件数，为什么CG可能走出完全不同的轨迹？一个叫“最小残差”的算法，究竟把哪一种残差变小了？

前置：SVD、QR与后向误差、特征值迭代与残差证据、正定矩阵与正交投影。先在小矩阵上看清几何，再讨论大规模计算的成本。

1. 乘出来的子空间：先说明允许使用什么信息

求解 \(Ax=b\)，给定起点 \(x_0\) 与初始残差 \(r_0=b-Ax_0\)。第 \(k\) 个Krylov空间为

设算法从这一个残差出发，只反复应用同一个固定算子 \(A\)，并对已有向量作线性组合，那么它得到的修正就落在相应Krylov空间中。这是关于具体运算模型的说明，不是“任何只调用矩阵乘向量的程序”都必须满足的普遍断言。额外起点、块方法、非线性操作或变化的预条件器都会改变讨论对象。

小空间的意义在于：不必先求整个逆矩阵，就能在

中挑选一个有明确最优性的候选解。不同方法的区别，首先在于“最优”指什么。

对大型问题，稀疏矩阵乘向量、正交化、内存和通信都可能是主要成本。稀疏直接分解的成本还取决于填充、排列和结构，不能一律按稠密 \(O(n^3)\) 判出局。

2. CG最小化的是能量误差

设 \(A=A^T\succ0\)，定义

将 \(x=x_*+h\) 代入，利用 \(Ax_*=b\)，交叉项消失：

因此在一个仿射空间 \(x_0+\mathcal S\) 上最小化二次函数，就等价于最小化能量误差。沿任意 \(v\in\mathcal S\) 的导数为

极小点满足残差的Galerkin条件

严格正定性保证这个极小点唯一。CG在精确算术中取 \(\mathcal S=\mathcal K_k(A,r_0)\)，所以

空间随 \(k\) 嵌套，最小能量误差自然不增。但 \(r_k=A(x_*-x_k)\)，不同特征方向会被不同的特征值再次放大；这没有推出 \(\|r_k\|_2\) 同样单调。

3. 短递推怎样保持搜索方向

标准CG从 \(p_0=r_0\) 开始，使用

这些系数不是经验学习率。假设前面的搜索方向已经 \(A\)-共轭，即 \(p_i^TAp_j=0\)（\(i\ne j\)），并且残差正交于已搜索空间。沿 \(p_k\) 作精确线搜索给出

由于 \(p_k=r_k+\beta_{k-1}p_{k-1}\) 且 \(r_k\perp p_{k-1}\)，分子恰为 \(r_k^Tr_k\)。这一步让新残差与 \(p_k\) 正交，同时由共轭性保持它与更早方向正交。

再要求 \(p_{k+1}^TAp_k=0\)，得到

利用 \(Ap_k=(r_k-r_{k+1})/\alpha_k\) 与 \(r_{k+1}\perp r_k\)，就化为上面的残差平方比。对更早的 \(p_j\)，有 \(Ap_j\in\mathcal K_{j+2}\)；新残差对已搜索空间的正交性，加上已有方向之间的共轭性，使这些更早的共轭条件继续成立。由此完成逐步归纳，而不必每轮存下并正交化全部历史方向。

浮点计算中的正交与共轭只会近似保持。实验记录每个实际 \(x,r,z,p,Ap,\alpha,\beta\)，并另报方向的归一化共轭内积，不能把理论上的零直接填进表格。

4. 把误差变成多项式问题

空间中的修正可写成 \(q_{k-1}(A)r_0\)，其中多项式次数至多 \(k-1\)。因为 \(r_0=Ae_0\)，\(e_0=x_*-x_0\)，所以

在正交特征基中写 \(e_0=\sum_i c_iv_i\)，便有

这解释了同一个条件数为什么可以对应不同轨迹：实际问题同时取决于离散谱点的位置和初始方向权重。

若有效误差只覆盖 \(d\) 个不同的正特征值，选择

就能把这些方向全部消去。因此精确算术至多需要 \(d\) 步，一般有 \(d\le n\)。但“只分布在三个点”与“挤在三个有宽度的簇中”不是同一件事：在簇中心取零，不能把簇内所有不同谱点精确消灭。

实验同时保留重复三值谱与有宽度的近簇谱；初值为零的方向记为无可定义的误差比，不因其分量很小就擅自删除。对角系统的参考解由实际 \(b_i/\lambda_i\) 单独计算，生成数据时使用的向量另列，避免不一致的“已知解”冒充参考。

5. Chebyshev界：只知道谱区间时的保证

设谱位于 \([a,b]\)，\(0\lt a\lt b\)，\(\kappa=b/a\)。CG的最优性给出

选取归一化Chebyshev多项式

分母使 \(p(0)=1\)，分子的自变量在谱区间内落于 \([-1,1]\)，因此其绝对值不超过1。令

当 \(z=(\kappa+1)/(\kappa-1)>1\) 时，

从而得到

再结合嵌套空间的不增性，可以显示 \(\min\{1,2q^k\}\)。这是精确算术的区间比较界，不是具体求解器的步数预测，也不是全部浮点舍入都被包括的误差界。

边界要分开：\(k=0\) 时归一误差为1；\(\kappa=1\) 时对称正定矩阵是标量乘单位阵，非零误差一步消去；\(e_0=0\) 时一开始就是答案。接近1并不等于1，不能把一个正的小界直接改成0。

6. 预条件CG：改变几何也要保留正定性

取容易求解的 \(M=M^T\succ0\)。对称变换

保持正定性，并且

把变换后系统的CG写回原变量，就得到PCG：

以及 \(\alpha_k=\rho_k/(p_k^TAp_k)\)、\(\beta_k=\rho_{k+1}/\rho_k\)、\(p_{k+1}=z_{k+1}+\beta_kp_k\)。

一般情形不能把 \(M^{-1}A\) 当成欧氏内积下的对称矩阵。用于CG区间界的是与它相似的对称正定矩阵 \(\widetilde A\) 的谱比。只有本页对角模型中，才可直接写

分组预条件器明确选择 \(m_i=\lambda_i/\nu_i\)，让 \(\nu_i\) 取三个指定值。这是用于观察有效谱的教学构造，不是处理未知大矩阵的通用方案。Jacobi取原矩阵对角；在已经对角的模型里它本身就完成了主要求解工作，不能据此宣称“免费一步求解”。

预条件器也可能无益甚至使迭代更多。把 \(M\) 整体乘一个正数虽然不改变有效谱的条件数，却会改变 \(\rho_k\) 的大小；因此不能拿 \(\rho_k\) 与原始残差的阈值直接比较。Netlib的说明也将预条件的变换、构建与应用成本分别讨论。

7. Arnoldi：把大残差问题投影成小问题

令 \(\beta=\|r_0\|_2\)，\(v_1=r_0/\beta\)。Arnoldi每轮先算 \(w=Av_j\)，再消去它沿已有基的投影：

剩余向量的长度给出 \(h_{j+1,j}\)，归一化后得到下一根基向量。把所有步骤放在一起，

其中 \(\overline H_k\) 是 \((k+1)\times k\) 的上Hessenberg矩阵。此处的等式先在精确算术中理解；实验执行两遍改良Gram–Schmidt，并记录两遍的每个投影及剩余向量。

候选解写成 \(x=x_0+V_ky\)，于是

若 \(V_{k+1}\) 列正交，范数被保留：

原来的大空间最小残差问题，就变成只有 \(k\) 个未知量的小最小二乘。GMRES在这里用QR求解；本页逐步执行实际Givens旋转，并保存旋转前后矩阵、右端和三角解，没有形成 \(\overline H_k^T\overline H_k\)。

8. 重启GMRES：节约历史信息也会失去它的好处

完整GMRES保留整个基。经过 \(k\) 步，存储基的成本约为 \(O(nk)\)，正交化总工作量通常随 \(k\) 增长。重启GMRES\((m)\)每做至多 \(m\) 步，就以当前解重新计算残差、建立新的基。

它仍在当前周期的小空间中最小化残差，但不再是全部历史 \(k\) 维空间中的最优解。重启长度的选择牵涉内存与收敛，不能从“矩阵可逆”推断任意小的 \(m\) 都有效。Netlib的GMRES讨论明确保留了重启过短导致停滞的情形。

一个不需要大数据的反例是

GMRES第一步只能试 \(x=\alpha e_1\)，于是

最优值出现在 \(\alpha=0\)，完全没有进步。GMRES\((1)\)重启后面对同一个问题，因此精确算术中永久停滞。完整GMRES第二步已经有 \(\operatorname{span}\{e_1,e_2\}\)，能得到 \(x_*=-e_2\)。

这也说明“残差单调不增”与“残差一定趋于0”不同：常数曲线同样不增。

9. 左右预条件：同一个解，不同的最小化范数

左预条件解

将普通GMRES用于这个变换后的系统，最小化的是 \(\|M^{-1}(b-Ax)\|_2\)。它不是原始残差二范数。

右预条件改变量 \(x=M^{-1}y\)，解

在对应的修正空间中，普通GMRES最小化的就是 \(\|b-AM^{-1}y\|_2=\|b-Ax\|_2\)。预条件器改变搜索方向的形成方式，但没有改变这个被最小化的残差。

所以，同一个可逆 \(M\) 可以保留原问题的解，却让两种算法画出不同曲线。左预条件的第一步尤其容易检查。记

试探 \(x=x_0+\alpha d\)，最小化 \(\|d-\alpha g\|_2\) 得到

这个系数只保证加权目标最优，没有保证原始 \(\|r_0-\alpha Ad\|_2\) 下降。实验将两个范数同时保留；即使加权曲线很好看，也使用显式原始残差判断是否满足所声明的停止标准。

10. 浮点停止、递推偏差与实际工作量

本页区分以下量：

短递推可以节省工作，却会积累舍入偏差。只看递推残差或小最小二乘的残差，都可能漏掉原方程里的误差。因此实验每步重算 \(b-Ax_k\)，并公开这些核对的额外成本。

对 \(b\ne0\)，本页停止条件为

真实浮点残差恰为0与达到阈值分开标记。\(b=0\)且零初值的模型直接检查初始残差；不执行会除以0的归一化。小残差仍不自动保证前向误差小，条件数问题可回看第一讲。

Arnoldi剩余向量很小时，实验按明示的机器精度阈值停止扩展，把实际舍去的向量和范数记录下来。只有原始残差也达到要求，才报告成功；否则显示近退化或预算结束。完整 \(n\) 维空间的精确算术结论，不能代替浮点运行中的这一步判断。

成本表统计求解过程实际调用的矩阵乘向量和预条件求解，包括显式残差检查；为展示恒等式而额外重算的诊断不计入求解调用，说明中单列。这个教学实现每一步重新分解小最小二乘，目的是展示过程；它没有实现大型库的增量更新和并行优化，不能拿这些小模型的耗时作性能排行榜。

11. 四道迁移题与完整答案

题一：CG的残差上升是否违反最优性？

取 \(A=\operatorname{diag}(1,100)\)、\(b=(1,1/10)^T\)、\(x_0=0\)。计算第一步，比较残差二范数与能量误差。

题二：三个谱点与三个谱簇有什么不同？

解释为什么只含三个不同正特征值的SPD问题可在精确算术中至多三步结束，而三个窄簇没有同样的三步精确保证。

题三：为何可逆旋转也会使GMRES(1)永久停滞？

对第8节的矩阵，给出每个重启周期的最优系数，以及完整GMRES第二步的解。

题四：预条件后残差很小，应该用哪一个量验收？

左预条件GMRES报告 \(\|M^{-1}r\|_2\) 下降，而 \(\|r\|_2\) 增大。这是否违反最小残差原理？把 \(M\) 整体乘一个很大的常数会带来什么危险？

12. 将小模型的判断带到更大的计算

选择方法时，先确认对称性、正定性、可用的算子操作和要满足的误差标准；再考虑基的存储、预条件器的构建与复用、显式残差检查和并行成本。固定维数不能单独决定哪一种方法总是更快。

随机化低秩分解提供另一条缩小问题的路径：随机试探矩阵作用，构造候选列空间，再处理压缩后的矩阵。Halko、Martinsson与Tropp的原始工作可作为后续阅读。这里不把“高概率接近最佳截断”写成没有采样、超采样、谱尾与概率条件的普适保证；本页的CG和GMRES实验也没有验证随机SVD。

下一门矩阵分析：范数、谱半径与扰动继续追问：不同矩阵范数、谱与条件数之间究竟可以推出什么。遇到“残差很小”的结论时，先保留本页的习惯——它是哪一个残差、怎样算出、与哪个问题有关？