路径： 本科数学/ 进阶数学/ 矩阵分析与谱图论/数值线性代数进阶：条件数、迭代法与特征值算法
33

数值线性代数进阶：条件数、迭代法与特征值算法

Numerical Linear Algebra · 大矩阵怎么高效解

【章首引子】矩阵一万阶，高斯消元要 O(n³)，慢到不可用。数值线性代数的答案是：迭代法（反复改进近似解）和矩阵无关算法（只借矩阵乘向量）。本章讲条件数（系统有多病态）、雅可比/高斯-赛德尔/SOR、共轭梯度 CG、GMRES，以及 QR 算法怎么求特征值。

卡必背公式 / 记忆口诀
条件数 κ(A)=‖A‖·‖A⁻¹‖
收敛看谱半径 ρ(B)<1
CG：Krylov 子空间最优
QR 算法：A=QR，迭代 RQ
口诀：病态看 κ，收敛看 ρ，大规模用 Krylov

① 是什么：条件数与迭代法

啥为什么直接法不够

① 条件数：κ(A)=‖A‖·‖A⁻¹‖（2-范数下=σ_max/σ_min）。κ≫1 时右端 b 的微小扰动被放大成解 x 的巨大误差——病态矩阵。深度学习里权重矩阵条件数大 = 梯度易爆炸/消失。

② 古典迭代法：把 A 拆成 A=D+L+U（对角、严格下三角、严格上三角）。雅可比：x^{(k+1)}=D⁻¹(b−(L+U)x^{(k)})。高斯-赛德尔：立刻用新值，x^{(k+1)}=(D+L)⁻¹(b−Ux^{(k)})。SOR：带松弛因子 ω 加速：x^{(k+1)}=(D+ωL)⁻¹[(1−ω)D−ωU]x^{(k)}+ω(D+ωL)⁻¹b。

③ 收敛判据：写成 x^{(k+1)}=B x^{(k)}+c，收敛 ⟺ 谱半径 ρ(B)<1（B 的最大特征值绝对值 <1）。ρ 越小收敛越快。

图 33.1：迭代误差随步数衰减——ρ(B) 越小衰减越快
k err ρ=0.5（快） ρ=0.9（慢） ρ≥1（发散）

② 现代 Krylov 子空间方法

证CG、GMRES 与预条件

① 共轭梯度 CG：只适用于对称正定 A。在 Krylov 子空间 Kₖ(A,r₀)=span{r₀,Ar₀,…,A^{k−1}r₀} 中找使二次型 φ(x)=½xᵀAx−bᵀx 最小的点。理论上 ≤n 步收敛，但实际对良条件问题极快（O(√κ) 步）。② GMRES：非对称 A 的 CG 推广，在 Krylov 子空间最小残差 ‖Ax−b‖。③ 预条件子 M：解 M⁻¹Ax=M⁻¹b，使 κ(M⁻¹A)≪κ(A)。常用 Jacobi 预条件（M=diag(A)）、不完全 Cholesky（IC）。④ QR 算法求特征值：反复 Aₖ=QₖRₖ，再令 A_{k+1}=RₖQₖ（=QₖᵀAₖQₖ 正交相似），Aₖ 收敛到上三角（实特征值）或拟上三角（Schur 形）。

CG 为什么快：CG 误差范数满足 ‖eₖ‖_A ≤ 2((√κ−1)/(√κ+1))ᵏ‖e₀‖_A。κ=100 时 (9/11)^k，几十步即收敛；κ=10⁶ 时慢得多——所以预条件子把 κ 压小是关键。

QR 算法直觉：QR 迭代是"幂迭代"的批量正交版本：每一步把当前矩阵做 QR 分解再逆序相乘，相当于反复把"最大特征方向"分离出来，最终露出三角结构，对角线即特征值。

③ 例题

例1：对角阵的雅可比迭代
【审题】A=diag(4,1)，b=(4,1)，真解 x=(1,1)。
思路：雅可比立刻收敛。
逐步：B_J=D⁻¹(L+U)=0（对角阵非对角为 0），所以 x^{(1)}=D⁻¹b=(1,1)，一步到位。启示：对角占优矩阵迭代快；非对角强耦合时慢。
例2：条件数放大误差
【审题】A=diag(100,0.01)，b 相对扰动 1%。
思路：‖δx‖/‖x‖≤κ·‖δb‖/‖b‖。
逐步：κ=100/0.01=10⁴。b 扰动 1% ⇒ x 相对误差可达 10⁴×1%=100%——解彻底失真。工程：深度学习里对权重做谱归一化/批归一化，本质就是压条件数。
例3：QR 算法第一步
【审题】A=[[2,1],[1,2]]，QR 分解。
思路：Gram-Schmidt。
逐步：列 a₁=(2,1)，‖a₁‖=√5，q₁=(2/√5,1/√5)。a₂ 投影：a₂−(a₂·q₁)q₁=(1,2)−(4/√5)(2/√5,1/√5)=(1−8/5,2−4/5)=(−3/5,6/5)，归一化 q₂=(−1,2)/√5。R=[[√5,4/√5],[0,3/√5]]。A₁=RQ，迭代下去对角线会收敛到特征值 3 和 1。
数值线性代数核心公式 条件数 κ(A)=‖A‖·‖A⁻¹‖=σ_max/σ_min；误差放大 ~κ
雅可比 x⁺=D⁻¹(b−(L+U)x)；GS 用新值；SOR 带 ω
收敛 ⟺ ρ(B)<1；CG：‖eₖ‖_A≤2((√κ−1)/(√κ+1))ᵏ‖e₀‖
QR 算法：A=QR→A₁=RQ 正交相似迭代，收敛到 Schur 形

④ AI 落点

稳定性
AI 落点 1：训练病态与归一化

损失曲面 Hessian 条件数大导致梯度下降走"狭长谷"。BatchNorm、谱归一化、LARS 都是在数值上压 κ。

算法
AI 落点 2：稀疏线性系统

GNN 传播、PDE 离散、图拉普拉斯求解都是稀疏大矩阵，用 CG/GMRES + 不完全 Cholesky 预条件，O(n) 而非 O(n³)。

算法
AI 落点 3：特征值与 PCA

PCA 的主成分是协方差矩阵最大特征方向；大规模时不做全 QR，用 Lanczos（对称 Krylov）只求前 k 个特征值。

优化
AI 落点 4：二阶方法

牛顿法要解 Hessian 线性系统；L-BFGS 用有限记忆近似 Hessian，是 CG 在优化里的近亲。

⑤ 延展

展知识衔接地图

往本科走：矩阵特征值、高斯消元、LU 分解是直接法基础。

往算法走：CG → 优化二阶方法；GMRES → 非对称 PDE 求解；QR → 特征值与 SVD 的数值计算。

思维陷阱

条件数大就一定不能解。条件数大只是"对扰动敏感"，配合预条件、高精度、正则化仍可解；不是无解。

CG 直接用于非对称矩阵。CG 要求对称正定；非对称要用 GMRES / BiCGStab / LSQR，否则搜索方向不再共轭。

以为迭代法一步到位。ρ(B)<1 才收敛；ρ≥1 发散，必须换分裂（如 SOR 选最优 ω）或预条件。

练习

【基础】A=diag(1000,1) 的条件数？

查看解答κ=σ_max/σ_min=1000/1=1000。
【自评反馈】对 → 下一题。

【进阶】雅可比迭代矩阵 B 的谱半径 ρ=0.8，误差每步衰减多少倍？

查看解答‖e_{k+1}‖≈ρ‖e_k‖=0.8‖e_k‖，每步剩 80%；10 步后约 0.8¹⁰≈0.107。
【自评反馈】对 → 下一题。

【挑战】为什么对称正定矩阵 CG 在 ≤n 步必收敛？

查看解答Krylov 子空间维度 ≤n，且 CG 在 Kₖ 上极小化二次型；到 k=n 时 Kₙ=ℝⁿ，全局最小点必被找到，故 ≤n 步收敛（精确算术下）。
记
小结卡

① 条件数 κ=σ_max/σ_min 衡量病态；迭代收敛 ⟺ 迭代矩阵谱半径 ρ(B)<1。

② 古典迭代：雅可比/高斯-赛德尔/SOR；现代：CG（对称正定）、GMRES（非对称），配预条件子。

③ QR 算法反复 QR→RQ 正交相似，收敛到 Schur 形读出特征值。

← 上一节 研究生数学总览