第 VII–VIII 讲 · QR 分解的三种做法

QR 分解 $A = QR$（$Q$ 正交、$R$ 上三角）是数值线性代数里"稳定"的代名词。同一目标有三种实现，性格迥异——Gram-Schmidt、Householder、Givens，理解它们的差别是工程判断力的起点。

经典与修正 Gram-Schmidt

经典 GS（CGS）把每列减掉它在已有方向上的投影：

浮点下投影算不准，产生严重正交性损失。修正 GS（MGS）把投影改为逐步做（每算出一个 $q_i$ 立刻从后续所有列里减掉），正交性损失降一个量级。MGS 算得的 $Q$ 虽非完美正交，但 $Q$ 的列空间极准——这个不对称性让 MGS 能胜任最小二乘（配合"对 $A$ 做一次、对 $A$ 的共轭做一次"的双 GS 技巧）。

Householder：镜面反射，工业标准

构造 Householder 镜面 $H = I - 2\mathbf{v}\mathbf{v}^T/\mathbf{v}^T\mathbf{v}$，把一整列映成 $\|\cdot\|_2 e_1$：一次反射消灭一列的 $n-1$ 个元素。逐列反射，$n-1$ 次后 $A$ 变上三角：

关键工程细节：$Q$ 不显式存，存各 $\mathbf{v}_k$（紧贴 $R$ 下三角的下带），要用时再回乘。代价 $2mn^2 - \frac{2}{3}n^3$ flop，且向后稳定——LAPACK 的 QR 就是它。

Givens：旋转，稀疏的选择

Givens 旋转是 $2\times2$ 平面正交阵，一次只消灭一个元素。便宜、局部、易并行，是稀疏矩阵 QR 与快速 Givens 变体（避免开方）的基石。

老师的提醒

• 稠密问题选 Householder；每次只改一两个元素的更新（递推最小二乘）选 Givens；教学与推导选 GS。
• 检验正交性损失：随机矩阵算 $\|Q^TQ - I\|_F$，MGS 应在 $10^{-13}$ 量级、CGS 可能烂到 $10^{-2}$。

自检

• MGS 比 CGS 好在哪？代价是什么？
• Householder 为什么不显式构造 Q？
• 三种 QR 各自的典型应用场景？

更深一层：三种 QR 是"同一定理的三种实现"

Gram-Schmidt、Householder、Givens 都实现 $A = QR$，本质都是"用正交变换逐步把列空间正交化"。差异在变换的组织方式：GS 按列正交化（正交三角化视角）、Householder 按整列反射（消元视角）、Givens 按单元素旋转（逐个消灭视角）。视角决定场景：需要 $Q$ 显式正交基 → GS/两次 Householder；只需要解最小二乘 → Householder 紧凑存法；流式更新（新数据来一行）→ Givens 一行消化。定理是同一个，工程形态由使用模式决定——这种"一理三形"的现象在数值线性代数里反复出现（三种 SVD 算法、多种 Cholesky 变体），识别它们是读算法文献的基本功。

GS 家族内部还有个易被忽略的细节：修正 GS 与经典 GS 在精确算术下完全等价，差异纯粹来自浮点求和顺序。这提醒我们：数值算法的"性格"（稳定域、精度损失模式）往往由看似无害的实现细节决定——两个数学等价的公式可以有截然不同的数值命运。

推导细读：为什么 MGS 的 Q "行空间准、列空间欠"

MGS 的正交性损失是不对称的，这个不对称性值得算一遍小例子（$2\times2$、严重共线的两列）来体感：MGS 先正交化第一列（精度好），第二列减去的投影用的是已算出的 $q_1$（精度好），但后续列的正交化残差会累积误差。净效果：$q_1$ 准确、靠后的 $q_j$ 略欠正交；但 $q_j$ 张成的行空间（即 $\text{span}$ 本身）非常准。Björck 的著名结论由此而来：MGS-QR 解最小二乘时，$Q$ 的前 $n$ 列行空间极准 → 一次 MGS 分解后直接回代即可，或做"MGS 两次"（对 $A$ 与 $A^T$ 各一次）达到完全 QR 等价。理解"哪个空间准"比记住"用哪种 GS"更重要——换一个应用场景，答案就换。

在真实世界里：QR 家族的现代栖息地

• Householder：LAPACK 的 DGEQRF、scipy.linalg.qr 默认——稠密最小二乘、特征值算法的化简器（海森堡化）；
• MGS：稀疏最小二乘（LSQR 的理论基础）、GMRES 内部正交化（标准选择，重正交化两次保正交）；
• Givens：递推最小二乘（RLS，信号处理在线参数估计）、稀疏 QR 的行处理、快速 Givens 免开方变体在硬件实现中常见。

三个家族在同一时刻都活着，各守一个生态位——"过时"从来不是数学方法的历史宿命，只有"用错场景"。

常见误区与辨析

• "GS 不能用于数值计算"：经典 GS 确实危险，修正 GS 在多数应用够用（尤其配合两次技巧）；一刀切的否定错过了它的流式优势。
• "QR 分解后 R 的对角元是奇异值"：不对，那是 R 对角元的绝对值 ≠ 奇异值（除非列正交）；要奇异值请走 SVD。
• "正交化后必须重新正交化"：MGS 在近共线列上确实建议二次正交化（"twice is enough"），但这是条件性建议，不是默认步骤。

专题深入：三种 QR 的"组织方式"决定场景

Gram-Schmidt、Householder、Givens 实现同一定理 $A = QR$，但变换的组织方式决定场景：GS 按列正交化（正交三角化视角）、Householder 按整列反射（消元视角）、Givens 按单元素旋转（逐个消灭视角）。视角决定场景：需要显式正交基 → GS/两次 Householder；只需要解最小二乘 → Householder 紧凑存法；流式更新（新数据来一行）→ Givens 一行消化。定理是同一个，工程形态由使用模式决定——这种"一理三形"的现象在数值线性代数里反复出现。

MGS 的不对称性值得展开：经典 GS 与修正 GS 在精确算术下完全等价，差异纯粹来自浮点求和顺序——数值算法的"性格"（稳定域、精度损失模式）往往由看似无害的实现细节决定。Björck 的结论：MGS 的行空间极准（一次 MGS + 对 $A^T$ 一次 MGS 达完全 QR 等价）——"哪个空间准"比"用哪种 GS"更重要。

数学细节展开：Householder 的"紧凑存储"工艺

Householder QR 的工程精髓是不显式构造 $Q$：$Q$ 由各 $\mathbf{v}_k$ 隐式存（紧贴 $R$ 下三角的下带），要用时再回乘。这个紧凑存储带来三重红利：内存省一半（$Q$ 不占 $n^2$）、flop 更优（回乘比显式乘快）、精度更好（正交性由构造保证而非计算）。"不构造 $Q$、只存 $\mathbf{v}$"是 Householder 的工业秘密——LAPACK 的 DGEQRF 返回的就是这个紧凑格式。

工程案例细节：QR 家族的现代栖息地

三个家族的现代栖息地：Householder → LAPACK DGEQRF、稠密最小二乘与海森堡化简器；MGS → 稀疏最小二乘（LSQR 的理论基础）、GMRES 内部正交化（重正交化两次保正交）；Givens → 递推最小二乘（RLS——信号处理在线参数估计）、稀疏 QR 的行处理。三个家族在同一时刻都活着，各守一个生态位——"过时"从来不是数学方法的历史宿命，只有"用错场景"。

常见误区与辨析（补充）

• "GS 不能用于数值计算"：CGS 确实危险，MGS 在多数应用够用（尤其配合两次技巧）；一刀切否定错过了它的流式优势。
• "QR 分解后 R 的对角元是奇异值"：不对——R 对角元的绝对值 ≠ 奇异值（除非列正交）；要奇异值请走 SVD。