科学仿真

正交性与稳定性:为什么 Householder QR 优于 Gram-Schmidt

导读:Trefethen & Bau 第 7-8 讲给出了数值线性代数的核心裁判标准:向后稳定性。经典 Gram-Schmidt 在这里栽了跟头。

正交是数值生命线

正交变换保持 2-范数:$\|Qx\|_2 = \|x\|_2$。用正交矩阵做变换不会放大误差——这就是 QR/SVD 稳定的根源。

经典 Gram-Schmidt(CGS)对接近线性相关的列会失去正交性(损失 $ ilde O(\kappa)$ 级),修正 Gram-Schmidt(MGS)把投影改成「逐列减」,数值行为好一档,但仍不如 Householder。

Householder 镜像

Householder 反射 $H = I - 2vv^T/(v^Tv)$ 把一列向量镜像到坐标轴方向,天然正交、天然稳定。代价是只给出 $QR$ 因子而不能「顺便」提供正交基的逐步信息——MGS 在需要逐列正交基的场景(如 Arnoldi)仍占一席。

向后稳定的裁判语言

称一个算法向后稳定,若它算的是「邻近问题的精确解」。Trefethen 的裁判式:对求 $Ax=b$,看算出的是否满足 $(A+\delta A)\hat x = b+\delta b$ 且 $\delta$ 为机器精度级。Householder QR 过关,CGS 不过关。

常见误区

  • 用 CGS 处理病态矩阵的正交化,然后奇怪为什么结果不正交。
  • 以为 MGS 输出的 $Q$ 是真正的正交阵(其列仅近似正交)。

吃透自检

  • 能写出 CGS 与 MGS 的伪代码并指出差别
  • 能复述向后稳定性定义并举出正反例
  • 能解释 Arnoldi 为什么必须用 MGS 而非 Householder

← 科学仿真 书目精读列表 经典研读