第 13–14 章 · 特征值问题的重机器

这两章是稠密特征值算法的完整工程学：海森堡化、QR 算法实现、对称/非对称的各路变体、平衡与预处理。比 Trefethen 版多出的是实现级的每一步细节。

非对称问题的标准流水线

• 化简 $10n^3/3$；每步 QR 迭代在海森堡形上 $O(n^2)$（Francis 双重位移避免复运算）。
• 特征向量由 Schur 形反代恢复，累计 $O(n^3)$。
• 平衡（balancing）：先做对角相似缩放 $D^{-1}AD$ 降低范数失衡，常大幅提高精度——处理"有的元素是 1e6 有的 1e-6"的矩阵的第一步。

对称问题的多路选择

• 对称 QR / 三对角 QR：教科书主力。
• 分而治之：分裂-递归-缝合，最快，LAPACK 默认。
• MRRR：多重重现精度，只求特征向量时最快。
• Jacobi：一串平面旋转把非对角元扫没，慢 2-10 倍，但高相对精度，可并行。

扰动理论：结果可信吗

对称问题：特征值扰动 $\le \|E\|_2$（Weyl），特征向量扰动 $\sim \frac{\|E\|_2}{\text{gap}}$。非对称问题：特征值条件数 $\frac{1}{|\mathbf{y}^T\mathbf{x}|}$（左乘右特征向量的夹角）——非正规矩阵的特征值可以极敏感（伪谱理论的动机）。报告特征值时附上条件数/gap，是专业与业余的分水岭。

老师的提醒

• 非对称矩阵结果诡异，先查条件数与伪谱，再怪算法——非正规问题本质上敏感。
• 大规模情形别直接上稠密 QR：先做稀疏迭代（Lanczos/Arnoldi，第 9-10 章），稠密方法只用于化简后的小投影矩阵。

自检

• 特征值流水线的四步各干什么？
• 平衡处理针对什么病？
• 对称与非对称特征值扰动的关键差别？

更深一层：特征值算法的"流水线经济学"

非对称特征值的四步流水线（海森堡化 → 带位移 QR → Schur 形 → 反代特征向量）每步都有明确的价签：化简 $10n^3/3$（一次付清）、QR 迭代每步 $O(n^2)$（海森堡结构红利）、特征向量恢复累计 $O(n^3)$。经济学结论：只要特征值不要特征向量，省一半；只要前 $k$ 个特征对且 $n$ 巨大 → 别走稠密流水线，直接 Lanczos/Arnoldi（第 15-16 章）。这个"全谱 vs 部分谱"的分岔是特征值计算的第一决策点——工程上 90% 的问题（模态分析取低阶、PageRank 取最大、谱聚类取最前几个）只要部分谱。

平衡（balancing）这一步的性价比也值得单说：对角相似缩放几乎免费（$O(n^2)$），却能把"元素尺度失衡"矩阵的特征值精度提升几个数量级——花小钱办大事的典型，LAPACK 默认开启是行业共识。

推导细读：为什么对称问题有" VIP 待遇"

对称问题的算法菜单（分而治之、MRRR、Jacobi）比非对称丰富得多，根源是两条结构性特权：特征值全实（谱在实轴上，序结构可用——可分而治之）与正交特征基（扰动理论干净：特征值扰动 $\le \|E\|$、向量扰动 $\propto 1/\text{gap}$）。非对称矩阵两条全无：复特征值成对、条件数 $1/|\mathbf{y}^T\mathbf{x}|$ 可以任意大（左乘右特征向量近垂直）——非正规矩阵的特征值本质敏感，伪谱（$\|(A - zI)^{-1}\|$ 的等高线）是描述这种敏感性的现代语言。工程含义：非对称特征值结果"每次算不一样"时，先画伪谱再怀疑算法——敏感是问题属性，不是求解器 bug。

在真实世界里：广义特征值才是工业常态

纯 $A\mathbf{x} = \lambda\mathbf{x}$ 在工程里反而是特例，主流是广义问题 $\mathbf{K}\phi = \omega^2\mathbf{M}\phi$（刚度-质量）。标准做法：Cholesky 分解 $\mathbf{M} = LL^T$ 后化标准问题 $L^{-1}\mathbf{K}L^{-T}\phi = \omega^2\phi$——但要注意质量阵须 SPD（集中质量阵对角正定最省事）。振动工程的完整配方：Lanczos 求低阶模态 + Sturm 序列检验（区间内模态数不漏数）+ 质量参与因子报告（截断是否充分）。特征值问题的工程报告三要素：频率、振型、参与质量——算法只是前两步的生产线。

专题深入：特征值流水线的"四步解剖"

非对称特征值的四步流水线值得逐步解剖：化简（Householder 海森堡化，$10n^3/3$ 一次付清）→ 迭代（带位移 QR，每步 $O(n^2)$——海森堡结构红利）→ Schur 形（收敛后的准上三角）→ 特征向量恢复（反代）。只要特征值不要特征向量，省一半——接口里"只要特征值"的开关就是为这设计的。

对称问题的 VIP 待遇：对称阵上海森堡形退化为三对角，QR 迭代更便宜；分而治之（分裂-递归-缝合）最快，是 LAPACK 对称特征值的默认；MRRR 只求特征向量时最快。Jacobi（一串平面旋转把非对角元扫没）慢但惊人准——高相对精度的场合（结构化学）不可替代。

数学细节展开：扰动理论的"条件数 vs 伪谱"

对称问题的扰动理论干净：特征值扰动 $\le \|E\|_2$（Weyl）、特征向量扰动 $\sim \|E\|_2/\text{gap}$。非对称问题：特征值条件数 $\frac{1}{|\mathbf{y}^T\mathbf{x}|}$（左乘右特征向量的夹角）——非正规矩阵的特征值可以极敏感。伪谱（$\|(A - zI)^{-1}\|$ 的等高线）是描述这种敏感性的现代语言——报告特征值时附上条件数/gap，是专业与业余的分水岭。

工程案例细节：广义特征值问题才是工业常态

纯 $A\mathbf{x} = \lambda\mathbf{x}$ 在工程里反而是特例，主流是广义问题 $\mathbf{K}\phi = \omega^2\mathbf{M}\phi$（刚度-质量）。标准做法：Cholesky 分解 $\mathbf{M} = LL^T$ 后化标准问题——质量阵须 SPD（集中质量阵对角正定最省事）。振动工程的完整配方：Lanczos 求低阶模态 + Sturm 序列检验（区间内模态数不漏数）+ 质量参与因子报告（截断是否充分）。特征值问题的工程报告三要素：频率、振型、参与质量。

常见误区与辨析（补充）

• "重特征值只是'普通情况乘二'"：重根自带新的动力学成分（$t^ke^{\lambda t}$ 型解）——Jordan 块尺寸控制多项式增长。
• "非对称矩阵结果诡异就怪算法"：先查条件数与伪谱——非正规问题本质上敏感。