数值线代算法谱系：Gauss 消元到迭代法
本文基于模型知识整理（生成时未联网核对），算法细节建议对照 Trefethen & Bau / Golub & Van Loan 复核。
一句话定义
工程世界的线代运算由一组经典算法承担——LU（解方程）、Cholesky（正定专用，LU 减半）、QR（最小二乘与特征迭代）、Householder/Givens（正交化构件）、QR 迭代/分而治之（特征值）、Golub-Kahan SVD、共轭梯度/LANCZOS（大稀疏迭代）——每族算法 = 结构利用 + 稳定性设计 + 复杂度预算的组合。
为什么重要
np.linalg.solve 背后是这些算法的选择树：稠密还是稀疏？对称正定与否？需要全部特征值还是最大几个？——不懂谱系就只能"默认值跑通"，懂谱系才能按问题规模（n=100 还是 10⁸）、结构（kp-028）、精度需求选对路线。这是从"会调 API"到"会做计算设计"的跃迁。
前置知识
kp-009（消元）、kp-014/015（正交与对称）、kp-023（稳定性）。
核心概念（算法谱系表）
| 任务 | 稠密算法 | 复杂度 | 稀疏/大尺度路线 |
|---|---|---|---|
| 解 $Ax=b$ | Gauss 消元→LU，回代 | O(n³)/2·n³ | CG（对称正定）、GMRES、多重网格 |
| 正定解 | Cholesky $A=LL^\top$ | n³/3（省半，必成功 kp-016） | CG 天然适配 |
| 最小二乘 | Householder QR | 2mn² | LSQR（迭代） |
| 特征值 | QR 迭代（Hessenberg 化+位移）→分而治之 | O(n³) | Lanczos/Arnoldi（取少数端谱） |
| SVD | Golub-Kahan 双对角化+QR 迭代 | O(mn²) | 随机化 SVD（近似，大数据标配） |
| 线性系统（ SPD 算谱） | — | — | 共轭梯度=多项式迭代在 Krylov 空间 |
原理与机制
LU 与消元的等价：高斯消元（kp-009）的矩阵化记录 $PA=LU$——L 记录消元乘子、U 是阶梯形；一次分解多次求解（多右端项只加回代 O(n²)）。行交换（选主元）保证数值安全——"不选主元的消元"在 κ 稍大时就炸（kp-023 的算法面）。
为什么 QR 是"稳定货币"：Householder 反射把列打成坐标轴方向，全程正交变换 → 后向稳定（kp-023）；QR 迭代（反复 QR + 位移）自动把矩阵推向三角/对角——特征值与 SVD 算法的共同引擎。正交性 = 数值线代的防弹材料。
迭代法的生存逻辑：稀疏矩阵连 LU 的填充（fill-in）都放不下——迭代法（CG/GMRES/Lanczos）只做"矩阵乘向量"，在 Krylov 子空间 $\text{span}\{b,Ab,A^2b,\dots\}$ 里找近似解；CG 更借助 A-范数单调下降保证 n 步精确收敛（浮点世界打折扣）。预条件（preconditioning）= 把系统改造得"更圆"以加速收敛（kp-016 的碗性思想）。
随机化 SVD：超大矩阵全分解太贵——随机投影先抓"能量所在"的列空间（kp-018 的低秩赌注），再在小矩阵上精确分解；现代 ML 线代的主力姿势。
图示
选型树:
稠密? ─ 是 → PD? → Cholesky | 一般 → LU(选主元) | 最小二乘 → QR
└ 否(稀疏/大) → SPD → CG(+预条件) | 一般 → GMRES
特征/SVD: Lanczos / 随机化SVD (只取端谱/低秩)
构件: Householder(正交化) | 位移QR迭代(谱) | 三角回代直观类比
算法谱系像工具箱里的扳手组：LU 是通用扳手（谁都能拧），Cholesky 是正定专用套筒（更省力更稳），QR 是精密扭矩扳手（不损伤=不失稳），迭代法是"电动扳手"（大件专用，先装定位销=预条件）。选错工具不是干不动就是拧坏螺帽。
实例或案例
- PageRank：十亿维稀疏 → 幂迭代/Lanczos（kp-013 幂迭代的工业化）。
- 图像去模糊：大稀疏线性系统 → CG + 预条件。
- LLM 权重 SVD 压缩：随机化 SVD/低秩近似（kp-018/031）。
常见误区
- 误区一："算法只看复杂度"。数值稳定性同权：朴素消元（不选主元）复杂度同 LU 却可能灾难（kp-023）；"快而炸"不如"稳而稍慢"。
- 误区二："迭代法是给穷人的降级"。大规模稀疏下直接法在内存层面不可行——迭代法不是退路而是唯一正路。
- 误区三："特征值算法可以自己手写玩玩"。QR 迭代的位移策略、分而治之的稳定性都有十年级打磨；工程上永远用 LAPACK 家族（NumPy 底座），把精力花在结构识别（kp-028）与选型上。
与其他知识点的关系
自测题
- 为什么多右端项场景先做 LU 一次？
答：分解 O(n³) 一次，之后每个 b 只需 O(n²) 回代——摊薄分解成本（对照每 b 重解 O(n³)）。
- CG 适用的两个前提？破坏会怎样？
答：对称正定；不满足则 A-范数理论失效、可能不收敛——非对称走 GMRES/双共轭梯度族。
- 随机化 SVD 为什么可行？
答：大多数矩阵能量集中在低秩子空间（kp-018 谱衰减）——随机投影高概率捕捉该子空间，再对小型投影矩阵精确分解。
延伸阅读
- Trefethen & Bau《Numerical Linear Algebra》（39 讲的最佳入门，含稳定性证明）。
- Golub & Van Loan《Matrix Computations》（算法百科）。
- Saad《Iterative Methods for Sparse Linear Systems》（迭代法权威，免费电子版）。