把 QR 做对：Householder 与 Givens

为何 Gram-Schmidt 不够

在第一卷里，你用 Gram-Schmidt 过程构建 QR：逐个把 A 的列正交化得到正交矩阵 Q，投影系数构成上三角的 R。数学上完美；数值上脆弱。在有限精度下，每次相减都漏出一点误差，算出的 Q 各列会慢慢偏离正交——恰恰在各列近乎相关、你最需要精度的时候。

专业的 QR 分解反转了策略。它不去*构建*正交列再指望它们保持正交，而是*施加*一连串精确正交的操作——反射与旋转——把 A 碾压成三角形式。这样正交性是工具的属性，而不是脆弱的输出。这两个工具就是 Householder 反射与 Givens 旋转。

Householder：一击清零整列

Householder 反射是镜映 H = I - 2 v v^T / (v^T v)。它把每个向量关于垂直于 v 的超平面作镜像，并且由构造即对称且正交（H^T H = I，H = H^T）。诀窍在于：给定一列 x，选取 v 使反射后的 x 恰好落在某条坐标轴上——即 Hx = (∓ ||x||, 0, 0, ..., 0)。一次反射就一举消掉对角线以下的整列。

# Goal: zero everything below the first entry of x = (3, 4)^T.
# ||x|| = 5.  Pick the sign to avoid cancellation: target = (-5, 0)^T.
x     = [ 3 ; 4 ]
v     = x - target = [ 3 - (-5) ; 4 - 0 ] = [ 8 ; 4 ]
H     = I - 2 v v^T / (v^T v)     # v^T v = 64 + 16 = 80
H @ x = [ -5 ; 0 ]                # the 4 is gone, in one reflection

# Apply H1 to A's first column, H2 to the trailing 2nd column, ...
# Q = H1 H2 ... Hn-1 (orthogonal),  R = (last H ... H1) A (upper-tri).

一步 Householder 把一列反射到坐标轴上——所有次对角元一并消失。

Givens：精准清零单个元素

Givens 旋转是只触及两行的平面旋转。取旋转角使 c = a/r、s = b/r（其中 r = sqrt(a^2 + b^2)），就把数对 (a, b) 旋到 (r, 0)，恰好清掉一个元素，而矩阵其余部分纹丝不动。Householder 清掉整列，Givens 则是手术刀——当 A 已有结构（它是稀疏的，或你只需修掉几个零散元素）时尤为理想。

要用上方第 k 行清掉元素 (i, j)，看数对 (a, b) = (A_kj, A_ij)。
构造 r = sqrt(a^2 + b^2)，c = a/r，s = b/r——这就是把 (a, b) -> (r, 0) 的旋转。
只对第 k 行与第 i 行施加 2x2 旋转 [c, s; -s, c]；元素 (i, j) 变为 0。

反射与旋转都是正交的，故它们的乘积也是正交的——这个乘积*就是* Q^T。由此得到的 QR 远比 Gram-Schmidt 的精确，这正是为什么每一个严肃的最小二乘求解器、以及后面指南里的特征值机器都建立在它之上。稠密一击式工作用 Householder；想保稀疏或并行化时用 Givens。