附录 A：核心推导与算法选择

本附录把全课反复出现的证明套路、算法不变量与选择逻辑放在一起。遇到新问题时，先识别结构，再判断应当维持什么关系。

A.1 五种核心不变量

不变量	典型算法	保证了什么
等价变换 $PA=LU$	Gaussian 消元	新系统与原系统有同一解
正交相似 $T=Q^{\ast }AQ$	Hessenberg、QR、Schur	特征值保持，2-范数不放大
正交投影 $r\perp \mathcal{V}$	最小二乘、FOM、Rayleigh-Ritz、CG	低维空间内的一阶最优性
残差最小 $min|r|$	GMRES、MINRES	当前搜索空间中的可计算最优解
矩阵分裂 $A=M-N$	Jacobi、GS、预条件	把难求逆的 $A$ 替换为易求解的 $M$

A.2 后向误差证明模板

浮点算法的局部运算先写成

$$\mathrm{fl}(a\circ b)=(a\circ b)(1+\delta ),|\delta |\le u.$$

然后把每一步误差吸收到当前输入，得到邻近问题。例如三角求解最终满足

$$(T+\mathrm{\Delta }T)\hat{x}=b,|\mathrm{\Delta }T|\le {\gamma }_n|T|.$$

再用问题的扰动界把 $\mathrm{\Delta }T$ 转化为前向误差。证明时应始终分开：局部舍入模型、算法后向误差、问题条件数。

A.3 Schur 补推导模板

许多分解都来自分块消元：

$$\left(\begin{array}{cc}{A}_{11}& A_{12}\\ A_{21}& A_{22}\end{array}\right)=\left(\begin{array}{cc}I& 0\\ A_{21}{A}_{11}^{-1}& I\end{array}\right)\left(\begin{array}{cc}{A}_{11}& A_{12}\\ 0& S\end{array}\right),$$

其中

$$S=A_{22}-A_{21}{A}_{11}^{-1}{A}_{12}.$$

LU、Cholesky、块消元、约束系统和分治谱算法都能看到 Schur 补。实际计算中不要形成 $A_{11}^{-1}$，而应解线性方程。

A.4 投影法推导模板

选试探空间 $\mathcal{V}=\mathrm{range}(V)$，写近似量为 $x=x_0+Vy$。再选测试空间 $\mathcal{W}=\mathrm{range}(W)$，施加

$$W^{\ast }(b-Ax)=0.$$

于是大问题化为小问题

$$W^{\ast }AVy=W^{\ast }{r}_0.$$

• $W=V$：Galerkin，如 FOM、CG、Rayleigh-Ritz；
• $W=AV$：残差最小条件，如 GMRES 的正规方程解释；
• 试探空间取 Krylov 空间：只需矩阵-向量乘法即可逐步扩张。

A.5 多项式收敛模板

许多迭代误差可写成

$$e_k=p_k(A)e_0\text{或}{r}_k=p_k(A)r_0,p_k(0)=1.$$

于是收敛问题变成：在谱或伪谱上寻找一个低次多项式，使其在目标区域尽量小。幂法、Chebyshev 加速、CG、GMRES、Lanczos 和隐式重启都可由这一视角联系起来。

A.6 结构化算法选择

1. 先看矩阵类别：一般、Hermite、正定、带状、稀疏、低秩。
2. 再看输出规模：完整分解、少量特征对、单个右端项、多个右端项或 $f(A)b$。
3. 再看精度目标：前向误差、后向误差、相对小奇异值精度或不变子空间精度。
4. 最后看硬件成本：内存、通信、稀疏填充、并行性与预处理构造。

A.7 证明与验收应成对出现

理论关系	程序验收量
$PA=LU$	$|PA-LU|/(|A|)$
$A=QR$，$Q^{\ast }Q=I$	分解残差与正交误差同时检查
$A=QT{Q}^{\ast }$	相似残差、正交误差、Schur 结构
$Ax\approx b$	相对残差与后向误差
$Ax\approx \lambda x$	特征残差及目标谱 gap
$A{V}_m=V_{m+1}{\overline{H}}_m$	Arnoldi 关系残差与基正交性

A.8 考前最小闭环

每个算法至少能回答：输入需要什么结构、一步做什么、保持什么不变量、为何稳定或收敛、单步与总复杂度如何、怎样从输出计算可靠性指标。