04 Householder、Givens 与 QR 分解

1. 为什么正交变换数值安全

酉矩阵 $Q$ 满足 $Q^{\ast }Q=I$，因此

$$\parallel Qx{\parallel }_2=\parallel x{\parallel }_2,{\kappa }_2(Q)=1.$$

它不会放大 2-范数误差。数值线性代数中，许多算法都通过一串正交/酉变换逐步制造零元素，同时保留长度与谱结构。

2. Householder 反射

给定非零向量 $v$，

$$H=I-2\frac{v{v}^{\ast }}{v^{\ast }v}$$

满足 $H^{\ast }=H$、$H^2=I$。它在 $v$ 方向取负，在 $v^{\perp }$ 上保持不变。

为了把 $x$ 映到坐标轴方向，选择

$$v=x-\alpha e_1,|\alpha |=\parallel x{\parallel }_2.$$

$\alpha$ 的相位/符号应避免 $x_1-\alpha$ 发生消去。这一细节决定实现是否稳定。

实数情形可取

$$\alpha =-\mathrm{sign}(x_1)\parallel x{\parallel }_2,v=x-\alpha e_1.$$

这样 $v_1=x_1-\alpha$ 是两个同号量的相加，不会灾难性消去。程序常存储 $\tau =2/(v^{\ast }v)$，通过

$$Hy=y-v(\tau v^{\ast }y)$$

施加反射，而不形成 $H$。

3. Givens 旋转

Givens 旋转只改变两个坐标。实数情形中选择 $c,s$ 使

$$\left(\begin{array}{cc}c& s\\ -s& c\end{array}\right)\left(\begin{array}{c}a\\ b\end{array}\right)=\left(\begin{array}{c}r\\ 0\end{array}\right).$$

不要直接计算 $\sqrt{a^2+b^2}$；应使用缩放良好的 hypot 型实现，避免溢出和下溢。

Householder 一次清除一整段向量，适合稠密批处理；Givens 一次清除一个元素，适合稀疏矩阵、在线更新和 Hessenberg/QR 迭代。

4. Householder QR

对 $A\in {\mathbb{C}}^{m\times n}$、$m\ge n$，依次对每列的活动子向量做反射：

$$H_n\cdots H_{1}A=\left(\begin{array}{c}R\\ 0\end{array}\right).$$

于是

$$A=Q\left(\begin{array}{c}R\\ 0\end{array}\right),Q=H_1\cdots H_n.$$

实际程序通常只存每个 Householder 向量，不显式形成 $H_k$ 或完整 $Q$。

5. Gram-Schmidt 的数值差别

经典 Gram-Schmidt（CGS）用

$$q_k\propto (I-Q_{k-1}{Q}_{k-1}^{\ast })a_k.$$

改进 Gram-Schmidt（MGS）则逐个应用投影修正。精确算术中二者等价；浮点算术中，MGS 通常更能保持正交性。若向量几乎线性相关，可以再正交化一次。

Householder QR 的正交性最可靠；MGS 更适合列向量逐个到达的 Krylov 过程。

更细的典型估计是：CGS 的正交性损失可能达到 $O(u\kappa (A{)}^2)$，MGS 通常为 $O(u\kappa (A))$。做第二遍正交化的 CGS2/MGS2 在未发生数值秩亏时可把正交误差恢复到 $O(u)$ 量级。

6. Arnoldi 是动态 QR

Krylov 子空间

$${\mathcal{K}}_m(A,v)=\mathrm{span}\{v,Av,\dots ,A^{m-1}v\}$$

的幂向量会迅速趋于线性相关。Arnoldi 过程不显式形成这些幂，而是每步计算 $w=A{v}_k$，再对已有基做 MGS，得到

$$A{V}_m=V_{m+1}{\overline{H}}_m=V_m{H}_m+h_{m+1,m}{v}_{m+1}{e}_m^{\ast }.$$

$H_m$ 为上 Hessenberg 矩阵。若 $A=A^{\ast }$，递推缩短为 Lanczos 三项递推。

7. 薄 QR、完整 QR 与唯一性

当 $m\ge n$ 且 $A$ 满列秩时，薄 QR 为

$$A=Q_{1}R,Q_1\in {\mathbb{C}}^{m\times n},Q_1^{\ast }{Q}_1=I.$$

补齐正交基可得完整 $Q=[Q_1,Q_2]$。若要求 $R$ 的对角元为正实数，则薄 QR 唯一；否则每列可以乘一个单位模相位并在 $R$ 中抵消。

Householder QR 的主项运算量为

$$2m{n}^2-\frac{2}{3}{n}^3,$$

而显式形成完整 $Q$ 还会增加成本。许多任务只需要把 $Q^{\ast }$ 作用到一个向量，因此应保留紧凑反射表示。

8. Givens 的稳定构造与局部更新

对 $a,b$，目标是选 $c,s,r$ 使

$$ca+sb=r,-sa+cb=0,c^2+s^2=1.$$

若直接算 $r=\sqrt{a^2+b^2}$，$a^2$ 或 $b^2$ 可能溢出。可先按 $max(|a|,|b|)$ 缩放，或调用 hypot。Givens 只触及两行/两列，所以加入一行观测、删除一个元素或追赶 Hessenberg 凸起时尤其合适。

9. QR 的后向稳定性

Householder QR 的计算结果可以解释为

$$A+\mathrm{\Delta }A=\hat{Q}\hat{R},\parallel \mathrm{\Delta }A\parallel \lesssim u\parallel A\parallel ,$$

且 $\hat{Q}$ 接近正交。需要区分两件事：分解残差小与 $Q$ 正交性好。Gram-Schmidt 可能有很小的 $\parallel A-QR\parallel$，但 $Q^{\ast }Q-I$ 很大；因此测试 QR 实现时必须同时报告两项。

10. 自检

• [ ] 能证明 Householder 矩阵既 Hermite 又酉。
• [ ] 知道构造反射时如何选符号避免消去。
• [ ] 能比较 Householder 与 Givens 的使用场景。
• [ ] 能解释 Arnoldi 为何得到上 Hessenberg 矩阵。
• [ ] 知道 CGS、MGS 与二次正交化的误差差别。
• [ ] 会同时检查 QR 残差和正交性。

下一章：最小二乘与正则化。