第 15–16 章 · Lanczos 与 Arnoldi：大规模时代的答案

矩阵大到一个 $O(n^2)$ 的化简都存不下时，特征值与线性方程问题都转向同一个思路：只做矩阵-向量乘，在低维子空间里逼近答案。这两章是这个思想的完整展开。

Lanczos：对称阵的三对角投影

从初始向量 $\mathbf{b}$ 出发，反复"乘 + 正交化"，生成子空间 $\mathcal{K}_k(A,\mathbf{b})$ 的标准正交基；对称性让递推只剩三项：

投影矩阵 $T_k$ 是三对角的——它的特征值（Ritz 值）以惊人的速度逼近 $A$ 的极端特征值（Kaniel-Paige 收敛理论，速度由特征值分布的 gap 决定）。数值隐患：浮点下舍入让基逐渐失去正交性（"幽灵"重特征值出现），补救：完全再正交化（贵）或选择性再正交化（监控正交损失，触发才做）。

Arnoldi：非对称的推广

失去对称性后递推变长（每步与全部已有向量正交化），投影矩阵 $H_k$ 是上海森堡——它的特征值同样是 Ritz 逼近。加上隐式重启（IRAM：子空间满了压缩掉不重要方向、保留重要方向续跑），就是 ARPACK 的算法核心，求 $k$ 个极端特征值的事实标准。

与线性方程的合流

Lanczos 生成三对角阵的过程同时就是 CG 方法（把极小化性质加上就是共轭梯度）；Arnoldi + 残差极小化就是 GMRES。"子空间方法"统一了特征值与方程组两个问题——这是本书最有启发性的统一观点。

老师的提醒

• 求内部特征值（谱中部）时 Krylov 方法慢：用谱变换（shift-invert：解 $(A-\sigma I)\mathbf{v}=\mathbf{w}$）把内部特征值变成极端特征值，代价是每步解一个方程组——结合直接分解或内层 CG。
• 收敛监视用残差 $\|A\mathbf{q}-\theta\mathbf{q}\|$，别用 Ritz 值的变化幅度自欺。

自检

• Lanczos 三项递推从对称性哪里来？
• 失去正交性会引发什么症状？两种补救的取舍？
• shift-invert 为什么能"搬动"要找的特征值？

更深一层：Krylov 方法的"存储经济学"

Lanczos/Arnoldi 的账本要按存储算而不是按 flop 算：每步存储 $O(nk)$（$k$ 为子空间维数）——$n = 10^7$、$k = 100$ 时是 $10^9$ 个 double = 8 GB。内存才是大规模特征值问题的第一约束，这解释了三个工程变体的存在：完全再正交化贵但干净（中小 $k$）；选择性再正交化（监控正交损失、触发才补）省算力；隐式重启（IRAM）干脆固定子空间上限、满了就压缩保留有用方向——ARPACK 的生存之道。 Restart 的思想还有个更深的解读：Krylov 子空间是一种"要维护状态的算法"，重启是状态管理——这个视角把 ARPACK、GMRES(m)、甚至深度学习的训练循环串成一条线。

正交性丢失的病理也值得记：浮点误差让基向量逐渐"合并"，本应分离的特征值出现幽灵重根（同一特征值被"发现"多次），Ritz 收敛被破坏。诊断信号：相同 Ritz 值成对出现。处方按预算选：完全再正交化（$O(nk^2)$）或 Paulechius-Scott 的部分再正交化。

推导细读：收敛率为什么由"谱间隙"决定

Lanczos 求最大特征值的收敛率 $\sim e^{-ck}$，$c$ 由 $\lambda_1$ 与"次近邻簇"的间隙决定——Kaniel-Paige 理论的核心不等式把误差界写成特征值间隙比的多项式。直觉版：Krylov 多项式要在"压低其他方向"的同时保住目标方向，其他特征值越分散越好压、越挤越难。推论一：重谱问题（特征值扎堆）Krylov 天然慢——谱变换（shift-invert）把内部特征值搬到边界、或用多项式滤波把间隙拉大。推论二：Cluster 里加一个"挑拨离间"的位移常比增加迭代数划算——这是谱变换工程化的动机。

在真实世界里：shift-invert 的实现细节决定成败

求内部特征值的标准操作 $(A - \sigma I)^{-1}$ 每步要解线性方程组——实现选择立刻分裂：小中型直接分解一次（LU of $A - \sigma I$）反复用（投资-变现模式再次登场）；超大规模 → 内层迭代解方程（inexact shift-invert， Jacobi-Davidson 类方法的理论温床）。$\sigma$ 的选取也是手艺：放在目标特征值附近（用已有估计）而非区间中心。电子结构计算（DFT）每天在全球超算上跑的就是这套东西的精细版——Krylov + shift-invert + 好预条件 = 大规模内部特征值的工业答案。

专题深入：Lanczos 的"幽灵特征值"与再正交化

Lanczos 的数值隐患值得单独展开：浮点误差让基向量逐渐"合并"（失去正交性），本应分离的特征值出现幽灵重根（同一特征值被"发现"多次）——Ritz 收敛被破坏。诊断信号：相同 Ritz 值成对出现。处方：完全再正交化（$O(nk^2)$，贵但干净）或选择性再正交化（监控正交损失、触发才补）。"正交性丢失是 Lanczos 的原罪"——这个警示让每一个 Krylov 实现者保持警觉。

隐式重启（IRAM）是 Lanczos 的内存救赎：子空间满了压缩掉不重要方向、保留重要方向续跑——ARPACK 的算法核心，求 $k$ 个极端特征值的事实标准。

数学细节展开：谱变换——"搬动"要找的特征值

求内部特征值（谱中部）时 Krylov 方法慢——shift-invert（解 $(A - \sigma I)\mathbf{v} = \mathbf{w}$）把内部特征值变成极端特征值。代价是每步解一个方程组——结合直接分解（$A - \sigma I$ 的 LU 一次分解反复用）或内层 CG。谱变换的工程含义：目标特征值的位置决定算法——极端特征值用 Lanczos/Arnoldi、内部特征值用 shift-invert、全部特征值用稠密 QR。

工程案例细节：ARPACK 的"接口哲学"

ARPACK（隐式重启 Arnoldi 的包）的接口哲学值得学：反向通信（库不直接算矩阵-向量乘，而是"告诉用户该乘哪个向量"，用户用自己的矩阵算子回调）——这个设计让 ARPACK 与任何矩阵表示（稀疏、隐式、分布）兼容。"库不拥有数据结构，只拥有算法"是科学计算库的最高设计原则——它让库的生命力远超任何特定的数据格式。

常见误区与辨析（补充）

• "Krylov 方法不需要矩阵"：只需要矩阵-向量乘——隐式矩阵（如矩阵函数、积分算子）天然适配。
• "shift-invert 免费"：每步解方程组的成本被"目标近位移"的收敛加速补偿——权衡是位移越近越贵但收敛越快。