第 XXXI–XL 讲 · 按需查阅的专题库

最后部分是专题工具箱，按需取用：稠密特征值工业细节、预条件技术、矩阵函数与 Chebyshev 逼近。这一节给一张索引地图。

特征值算法的工业补全

• 分而治之：对称三对角分裂成两半分别解再缝合，速度压过 QR 算法，是 LAPACK 对称特征值默认。
• 隐式重启 Arnoldi（IRAM）：Krylov 子空间满了就"重启"但保留有用方向——ARPACK 的核心，求 $k$ 个极端特征值的事实标准。
• Jacobi 特征值法：慢但惊人准（高相对精度），在结构化学等需要小奇异值高相对精度的场合不可替代。

预条件与分层的思想

• 多重网格：细网格上的低频误差 = 粗网格上的高频误差，来回限制-延拓，收敛步数与网格尺寸无关——$O(n)$ 解椭圆问题的唯一现实途径。
• 不完全分解（ILU/ICT）：LU/Cholesky 填充裁剪版，通用预条件。
• 区域分解：大域切块、块内直接解、界面迭代，天然并行。

矩阵函数与逼近论收束

$f(A)\mathbf{b}$（指数、平方根）用 Krylov + Chebyshev/Padé 逼近计算；全书最后一讲以 Chebyshev 多项式收束——逼近论与数值线性代数在"用低次多项式控制误差"处会师。

老师的提醒

• 决策速查：$n < 10^4$ 直接法（Cholesky/LU）；SPD 大规模 → CG+多重网格；非对称 → GMRES+ILU；要极端特征值 → Lanczos/IRAM。
• 换预条件子前后，记录迭代数-时间曲线：好预条件的判据是总时间，不是迭代数。

自检

• 多重网格为什么能做到收敛步数与网格无关？
• 隐式重启解决 Krylov 方法的什么缺陷？
• 选算法前要回答的矩阵三属性是什么？

更深一层：查表决策的底层是"矩阵的三属性"

书末工具库看似零散，实则由一条主线贯穿：拿到问题先回答矩阵的规模、稀疏性、对称性，答案组合直接映射到算法。$n < 10^4$ + 稠密 → LAPACK 直接法全家桶；$n > 10^6$ + 稀疏 SPD → CG + 多重网格；非对称稀疏 → GMRES/Krylov + ILU；只要极端特征值 → Lanczos/Arnoldi；低秩逼近 → 随机化 SVD。这张决策表背后的深层原则：算法的成本结构必须匹配数据的成本结构——稠密算法浪费在稀疏数据上、迭代法浪费在小问题上。工程师与科学计算的分野也在此：工程师面对的矩阵几乎总带有"来源特征"（有限元 → 大稀疏 SPD；控制 → 小稠密；数据科学 → 高瘦低秩），识别来源就是识别算法。

推导细读：多重网格为什么能"无视网格尺寸"

迭代法（Jacobi/Gauss-Seidel）的致命伤是高频削得快、低频磨不动——误差的高频分量每步衰减剧烈，低频分量几乎不动（低频误差波长长，局部差分"看不见"）。多重网格的洞察：细网格上的低频误差在粗网格上是高频——把残差限制到粗网格、在那儿它变得"好治"、解完延拓回细网格。细粗两层来回，全频段误差都被快速消除；多层嵌套后总成本 $O(n)$，收敛步数与网格尺寸无关。这是数值分析里少有的"复杂度理论突破"级的成果——它把椭圆方程求解从 $O(n\log n)$ 压到 $O(n)$，大规模仿真的经济性由此改写。

在真实世界里：随机化算法的崛起

工具库的现代篇章里，随机化算法是最亮眼的新成员。随机化 SVD：随机矩阵 $\Omega$ 投影 $Y = A\Omega$、对 $Y$ 正交化、在低维空间里精确分解——$O(nnz(A)\cdot k)$ 拿到 top-$k$ 奇异对，比确定性 Krylov 快一个量级且天然并行。随机化数值线性代数（RandNLA）已成数据科学的基础设施：PCA、推荐系统、科学计算的降阶模型都在用。随机性在这里不是妥协而是资源——用概率保证换确定性检验的昂贵妃。传统的"确定性最优"观念正在被"概率性够好 + 便宜一个量级"的工程哲学补充。

常见误区与辨析

• "多重网格万能"：它对椭圆型问题（扩散主导）威力巨大，对流主导、强非线性、不定问题需要专门变体（代数多重网格、全近似格式）——不是 Plug-and-play。
• "随机算法结果不可信"：失败概率可控（失败概率 $e^{-c}$，$c$ 是过采样参数）；"可信度工程化"正是它的卖点。
• "工具库要全学会"：按自己的领域选三四个主力算法吃透，比泛泛通读十八讲有用——工具库的价值在"按需查阅"，这也正是原作者的定位。

专题深入：随机化算法的"概率换效率"哲学

随机化 SVD 的误差保证来自一个概率事实：随机向量以压倒性概率（$1 - c^{-k}$）与任何固定低秩子空间有足够大的投影分量。三个要点：过采样（$k + p$、$p \approx 10$ 列冗余，失败概率指数衰减）；幂迭代（$Y = (AA^T)^qA\Omega$——对奇异值衰减慢的矩阵必要）；正交化防塌缩。成本正比于"你想要的秩"，而非矩阵尺寸——这使它在大数据 PCA（$10^9\times10^4$ 矩阵）、天气降阶、分子动力学的协同振动分析里成为默认答案。"随机性在这里不是妥协而是资源"——用概率保证换确定性检验的昂贵。

数学细节展开：多重网格的"频段分工"原理

多重网格的洞察：细网格上的低频误差在粗网格上是高频——细网格迭代法（Jacobi/Gauss-Seidel）快速削高频、低频磨不动；粗网格上低频变高频就好治了。细粗两层来回，全频段误差都被快速消除；多层嵌套后总成本 $O(n)$，收敛步数与网格尺寸无关。这是数值分析里少有的"复杂度理论突破"级成果——它把椭圆方程求解从 $O(n\log n)$ 压到 $O(n)$，大规模仿真的经济性由此改写。

工程案例细节：工具库的"按需查阅"心法

书末工具库的用法是"按需查阅"：求大规模特征值读 Lanczos 讲、解病态泊松读多重网格与预条件讲、矩阵函数 $f(A)\mathbf{b}$ 读 Krylov + Chebyshev 讲。选择算法前先回答矩阵的三个属性——规模、稀疏性、对称性。这张决策速查表（$n < 10^4$ 直接法；SPD 大规模 CG+多重网格；非对称 GMRES+ILU；要极端特征值 Lanczos/IRAM；低秩逼近随机化 SVD）是数值线性代数的"毕业礼物"——带着它走进任何计算问题，答案自动落位。

常见误区与辨析（补充）

• "多重网格万能"：对流主导、强非线性、不定问题需要专门变体（代数多重网格、全近似格式）——不是 Plug-and-play。
• "随机算法结果不可信"：失败概率可控（$e^{-c}$）——"可信度工程化"正是它的卖点。