选择、更新与扩展分解

一张决策图

你现在有了一个工具箱；真正的本领是把工具配给矩阵。选择正确的分解从一个问题开始：A 有什么结构？对称性、正定性、稀疏性，以及你是需要特征值还是仅需求解，都会把你推向不同的分解。把这一步做对，你可以比通用求解器快一个数量级、精度也更高。

1. 对称正定？用 Cholesky——最快、最稳定。
2. 对称但不定？用 LDL^T——保留对称性，免开方。
3. 一般方阵求解？用 带部分选主元的 LU。
4. 最小二乘 / 高瘦矩阵 / 精度关键？用经 Householder 的 QR。
5. 需要特征值？用 Schur（对称则 -> 谱分解）；需要几何 / 条件信息 -> SVD 或极分解。

分块与 Schur 补

真实矩阵是巨大的，而同样的分解既适用于标量也适用于分块。把 A 划分成 A = [A, B; C, D] 并消去左上块：右下块被换成 Schur 补 S = D - C A^-1 B。这种分块分解是缓存高效的 LAPACK 内核、PDE 求解器中的区域分解、以及高斯推断中边缘化步骤背后的引擎——Schur 补其实就是一块在给定另一块条件下的协方差。

[ A  B ]   =   [ I        0 ] [ A   0 ] [ I   A^-1 B ]
[ C  D ]       [ C A^-1   I ] [ 0   S ] [ 0      I   ]

# S = D - C A^-1 B   is the Schur complement of A.
# det([A B; C D]) = det(A) * det(S).
# block-LU = recurse the same idea on A and on S.

稀疏性与填入

大多数大矩阵几乎全是零。天真地分解它们是一场灾难：消元会在 A 原本为零处制造出新的非零元——填入——这能把一个 99% 为空的矩阵变成稠密、撑爆内存的 L。良方是重排序：置换行列（如近似最小度、嵌套剖分），使消元引入尽可能少的填入。一个好的排序，常常就是问题能否装进内存的分水岭。

更新而非重新分解

最终的收获，正是分解之所以主宰计算的原因：当 A 略有变化时，你不必从头再来。低秩更新以 O(n^2) 修改现有分解，而不是以 O(n^3) 从头重新分解。若 A 变为秩一扰动 A + u v^T，则 Sherman-Morrison-Woodbury 公式直接由旧分解再加一次额外求解，给出新的逆——以及新的解。

Sherman-Morrison (rank-one update of the inverse):

(A + u v^T)^-1  =  A^-1  -  (A^-1 u)(v^T A^-1) / (1 + v^T A^-1 u)

# You already have A = LU, so A^-1 u and v^T A^-1 are two cheap solves.
# No O(n^3) refactor. Woodbury is the same idea for a rank-k update U V^T.
# Used in: recursive least squares, Kalman filters, quasi-Newton (BFGS).

这就是整条学习线的全貌：矩阵很少只是一格格数字。按它的对称性、稀疏性、几何来分解它，你就揭示出恰好所需的结构：一次快速求解、一个特征值、一个旋转、一个条件界。你所选的分解，是矩阵借以告诉你它是什么的透镜。有意识地挑选这面透镜，你便同时读懂了问题，以及求解它的机器。