把 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。