附录 B：复杂度与稳定性速查

下表给出主阶量级。常数会随是否累积变换、矩阵结构和实现方式改变，因此复习时先记“规模如何增长”，再记有用的精确系数。

常见算法成本

任务	时间复杂度	额外存储	备注
稠密三角求解	$O(n^2)$	$O(n)$	单个右端项
稠密 LU 分解	约 $\frac{2}{3}{n}^3$	$O(n^2)$	实际应配合选主元
稠密 Cholesky 分解	约 $\frac{1}{3}{n}^3$	$O(n^2)$	对称正定
$m\times n$ Householder QR	$O(m{n}^2)$	$O(mn)$	$m\ge n$，主项约 $2m{n}^2-\frac{2}{3}{n}^3$
稠密 Hessenberg 化	$O(n^3)$	$O(n^2)$	一次性预处理
Hessenberg QR 单次扫描	$O(n^2)$	$O(n^2)$	利用带状结构
对称三对角 QR 单次扫描	$O(n)$	$O(n)$	不含特征向量累积成本
稠密 SVD	$O(m{n}^2)$	$O(mn)$	假设 $m\ge n$
稀疏矩阵—向量乘法	$O(\mathrm{nnz}(A))$	$O(n)$	Krylov 方法的核心操作
Arnoldi $k$ 步	$O(k\mathrm{nnz}(A)+k^{2}n)$	$O(kn)$	第二项来自正交化
CG $k$ 步	$O(k\mathrm{nnz}(A))$	$O(n)$	不含预处理成本

稳定性与条件数

概念	回答的问题	典型表达
条件数	问题本身是否敏感？	$\kappa (A)=|A||A^{-1}|$
前向误差	算出的解离真解多远？	$|\hat{x}-x|/|x|$
后向误差	算出的解对应多小的数据扰动？	寻找最小 $\mathrm{\Delta }A,\mathrm{\Delta }b$ 使 $(A+\mathrm{\Delta }A)\hat{x}=b+\mathrm{\Delta }b$
残差	当前解满足方程到什么程度？	$r=b-A\hat{x}$
后向稳定	算法是否精确解了邻近问题？	数据扰动与机器精度同阶

小残差不自动意味着小前向误差。粗略地说，前向误差上界通常还会乘上条件数；病态问题即使由稳定算法求解，也可能对输入扰动非常敏感。

方法选择速记

问题结构	首选思路	避免的常见绕路
稠密一般线性系统	带选主元 LU	显式求逆后乘 $b$
稠密对称正定系统	Cholesky	忽略结构使用一般消去
长方形最小二乘	Householder QR；高精度需求可用 SVD	盲目形成 $A^{\ast }A$
一般稠密特征值	Hessenberg + Francis QR	对每个特征值单独做高成本迭代
对称稠密特征值	三对角化 + 对称谱算法	丢弃对称性
大规模 SPD 系统	预条件 CG	存储完整 Krylov 基
大规模非对称系统	预条件 GMRES/其他结构化 Krylov 法	不监控真实残差
少量对称特征值	Lanczos / 重启方法	求完整特征分解
少量奇异值或最小二乘	Golub–Kahan、LSQR	显式构造 $A^{\ast }A$

高频实现陷阱

1. 显式计算逆矩阵，而不是解线性方程。
2. 只报告迭代次数，不报告相对残差和运行成本。
3. 用绝对阈值判断消去，忽略矩阵尺度。
4. 理论上应正交的向量在有限精度下失去正交，却没有检测。
5. 稀疏矩阵中形成稠密中间量，或让分解产生严重填充。
6. 只比较特征值，不检查特征残差、正交性或分解残差。

一句话总纲

先识别结构，再选择变换；先估计敏感性，再解释误差；先写残差或不变量，再相信输出。