第 I–III 讲 · 线性代数的两种视角

这本的开篇立场很特别：数值线性代数 = 线性代数 + 扰动理论 + 速度。前 3 讲先立起"矩阵-向量乘法的两种读法"，这是全书所有算法的透镜。

两种读法：列组合与行组合

• 列视角：$A\mathbf{x}$ 是 $A$ 各列以 $x_j$ 为权的线性组合——答案是 $A$ 列空间里的向量。
• 行视角：结果的第 $i$ 个分量是第 $i$ 行与 $\mathbf{x}$ 的内积——每行是一个线性度量。

消元法的本质是行变换（行视角），而 QR、SVD 全是列空间的几何（列视角）。两种视角随时切换，是读懂本书的第一能力。

矩阵乘法的四重分解

$AB$ 可以按列组合、行组合、外积之和、分块四种方式读。其中外积视角 $AB = \sum_k \mathbf{a}_k \mathbf{b}_k^T$ 是秩-$k$ 修正的语言，第 1 讲用它重新推导了乘法的计算量为 $2mnp$ flop，也是后文秩一更新的种子。

浮点：一切讨论的背景板

计算机的数是有限精度浮点数，相对误差 $\varepsilon_{mach}\approx 10^{-16}$（双精度）。数值算法的一切设计都在回答：误差在运算传播中被放大还是被抑制？ 第 I 讲给出 flop 计数的习惯（乘加算一次量级）与 $O(n^3)$ 高斯消元的成本印象，为全书"快不快、稳不稳"的两条主线铺路。

老师的提醒

• 拿到任何分解（QR、LU、SVD），先问三个问题：它把矩阵拆成哪几个"简单角色"？各因子怎么算？算的过程中误差怎么放大？
• flop 计数是量级判断，不是运行时间：cache 与并行对常数因子的影响常比阶数更左右实际速度。

自检

• $A\mathbf{x}$ 的列视角与行视角分别是什么？
• 为什么说浮点误差是本书一切分析的背景？
• 矩阵乘法的四种读法各自通向什么算法？

更深一层：flop 数与真实速度隔着三层硬件

本书喜欢数 flop（乘加次数），但现代机器上 flop 数与运行时间之间隔着三层：内存带宽（矩阵乘在 cache 外运行时受制于数据搬运，算术强度 flop/byte 低于机器平衡点的算法是"访存受限"——向量加法每读 16 字节只做 2 flop，永远跑不满峰值）、缓存层次（L1/L2/L3 容量决定分块大小，分块不当则反复从内存拖数据）、并行度（SIMD 宽度 8 个 double、多核线程、分布式通信）。BLAS 三级的划分正对应这个层次：Level-1（向量操作，访存受限）、Level-2（矩阵-向量，仍受限）、Level-3（矩阵-矩阵，计算受限、能逼近峰值）——把算法写成 Level-3 的形式（分块 LU、分块 QR）是 LAPACK 快的根源。

这套硬件意识的工程推论：自己写数值代码前先查 LAPACK/BLAS——手写三对角 Thomas、小矩阵求逆常能超过库（库的通用性有开销），但稠密矩阵乘与分解永远别手写，差 10-50 倍是常态。

推导细读：投影与正交性的"最小性"

第 1-3 讲埋的投影思想在第 4 讲正式兑现，值得把"正交投影是最佳逼近"的证明想透：设 $P_S$ 是到子空间 $S$ 的正交投影，任取 $s' \in S$：

最后一步用了勾股定理——残差 $v - P_Sv$ 垂直于整个子空间，因此与 $P_Sv - s'$ 正交。结论：$s' = P_Sv$ 唯一最小。这个证明干净得像艺术品，而它是傅里叶级数（投影到三角多项式空间）、最小二乘（投影到列空间）、有限元（投影到形函数空间）共同的根。逼近论的三大分支共享同一个投影定理——数学统一性的绝佳标本。

在真实世界里：矩阵视角决定存储格式与算法族

拿到一个真实问题的矩阵，第一动作是分类：稠密还是稀疏（非零元占比 < 5% 走稀疏路线：CSR 存储 + 迭代法/稀疏直接法）；对称与否（对称正定走 Cholesky/CG，省一半存储与算力；对称不定走 Bunch-Kaufman）；结构特征（三对角用 Thomas $8n$ flop、Toeplitz 用 Levinson $O(n^2)$、Hankel/循环矩阵有 FFT 快算法）。特征分类错了，性能差几个数量级——把满阵算法套在三对角问题上是最常见的浪费（$O(n^3)$ vs $O(n)$，$n = 10^5$ 时差 10 个数量级）。

常见误区与辨析

• "flop 少一定快"：访存受限区 flop 数与速度无关；Level-1 操作的 flop 优化是徒劳的。
• "精度问题都是算法问题"：先算条件数——$\kappa = 10^{12}$ 的问题任何算法都只剩 4 位精度，正解是改建模或正则化。
• "正交矩阵贵"：$Q$ 作用在向量上是 $O(n^2)$ 且数值零放大，比"便宜但放大误差"的初等变换划算得多——稳定性与速度不总是敌人。

专题深入：flop 数、访存、并行的"三本账"

数值算法的性能由三本账决定，flop 数只是其中之一。算术强度（flop/byte）是第一条分界线：向量加法（每读 16 字节只做 2 flop）永远跑不满峰值——访存受限；矩阵-矩阵乘（每读一字节做 $O(n)$ flop）是计算受限、能逼近峰值。BLAS 三级的划分正对应这个层次：Level-1（向量，访存受限）、Level-2（矩阵-向量，仍受限）、Level-3（矩阵-矩阵，计算受限）——把算法写成 Level-3 的形式（分块 LU/QR）是 LAPACK 快的根源。并行度（SIMD 宽度、多核线程、分布式通信）是第三本账——通信避免算法（Communication-Avoiding）把这本账从"每步同步"改到"每块同步"。

数学细节展开：范数的"等价但不等效"

所有有限维范数在数学上等价（互相有界），但数值上不等价——$\|x\|_1, \|x\|_2, \|x\|_\infty$ 的常数比随维数增长。工程后果：误差界的范数选择（2-范数给最紧的几何界、$\infty$-范数给逐分量界、1-范数给稀疏界）——选让界最紧的范数是误差分析的隐藏手艺。诱导矩阵范数的对应表（2-范数 = 谱范数 = 最大奇异值、Frobenius = $\sqrt{\sum\sigma_i^2}$）把范数与奇异值连起来——范数 = 奇异值的函数这条线是矩阵分析的总纲。

工程案例细节：正交变换的"零放大"红利

Householder/Givens 的正交变换有一个不可替代的红利：误差在传播中严格不放大（$\|Qx\|_2 = \|x\|_2$——每步的舍入误差范数不变）。对比消元乘子（初等变换）：每步可能被 $\|T_i\|$ 放大。这就是为什么 Householder QR 比 Gram-Schmidt 稳、为什么 Schur 形（正交相似）是特征值算法的终点站。"正交变换是数值安全屋"——付出两倍 flop 换无条件稳定，大多数场景这是最便宜的保险。

常见误区与辨析（补充）

• "flop 少一定快"：访存受限区 flop 数与速度无关；Level-1 操作的 flop 优化是徒劳的。
• "矩阵乘法就是三重循环"：朴素三重循环在缓存外行上慢 10-50 倍——分块 + BLAS3 是工业标准。