项目仓库:https://github.com/yicongl1/Linear-Algebra-Gram-Schmidt

Gram–Schmidt 有两个版本。教科书通常先讲经典版(CGS),再提一句“数值上更推荐修正版(MGS)”,然后继续往下写。但这个“更推荐”到底值多少?在什么矩阵上会出事?出事时误差有多大?

这个课程项目用 MATLAB 和 C 把两个版本都实现了一遍,然后用病态矩阵和随机矩阵把差异量出来。结论比“MGS 更稳”具体得多。

两个版本只差一个下标

经典版对第 k 个向量一次性减去它在所有已构造正交向量上的投影:

u_k = v_k - Σ_{j<k} <v_k, u_j> u_j

修正版把投影拆开,每减一次就更新当前向量:

v_k ← v_k - <v_k, u_j> u_j,  j = 1..k-1

精确算术下两者完全等价。MATLAB 代码也只差一个字母:

% CGS:内积始终用原始列 a(:,i)
b(:,i) = b(:,i) - dot(a(:,i), b(:,j)) / dot(b(:,j), b(:,j)) * b(:,j);

% MGS:内积用已经更新过的 b(:,i)
b(:,i) = b(:,i) - dot(b(:,i), b(:,j)) / dot(b(:,j), b(:,j)) * b(:,j);

CGS 的每一次投影都基于“原始向量”,所有投影系数一次性算完;MGS 的每一次投影都基于“被前一次投影修改过的向量”。这个顺序差异,决定了舍入误差会不会被后续步骤放大。

为什么会丢精度

把向量 v_k 投影到已构造的正交基上,本质是在做减法。如果 v_k 与某个 u_j 几乎平行,投影项就非常接近 v_k 本身,两个相近的大数相减会产生严重的相消(cancellation),有效数字大量丢失。

CGS 的问题在于:它用原始 v_k 算完所有投影系数,再一次性减掉。前面步骤产生的误差不会被后续投影“看到”,但它会留在结果里,并在下一步继续累积。MGS 每减一次就更新向量,下一次投影基于更新后的值,误差被限制在当前步骤内,不会跨步传播。

条件数 cond(A) 衡量的是“输入的小扰动会被放大多少”。列向量越接近线性相关,条件数越大,投影中的相消越严重。所以误差不是随机出现的,它和条件数强相关。

实验一:良态矩阵

取一个普通的 3×3 矩阵:

A = [[1, 2, 3],
     [2, -1, 2],
     [1, 1, 2]]

cond(A) ≈ 53.94,两种算法得到的正交基在 Frobenius 范数下相差:

‖Q_CGS − Q_MGS‖_F ≈ 5.92×10⁻³¹

这是双精度下的“数值零”。良态矩阵上,两个版本没有实际差别。

实验二:病态矩阵

构造一个含极小量 ε 的矩阵:

B = [[1, 1, 1],
     [ε, 0, 0],
     [0, ε, 0],
     [0, 0, ε]]

取 ε = 10⁻¹⁰,cond(B) ≈ 1.73×10¹⁰。两种算法得到的基相差:

‖Q_CGS − Q_MGS‖_F ≈ 0.2679

这已经不是“数值零”了:两个标准正交基的差异达到 0.27,说明 CGS 的结果在浮点意义下已经明显偏离正交性。MGS 的结果更接近真正的正交基,但也不是完美的——条件数到了 10¹⁰,任何算法都要付出精度代价。

实验三:100 个随机病态矩阵

为了看趋势,我们随机生成 100 个 100×100 矩阵,只保留 cond > 10⁶ 的样本,分别跑 CGS 和 MGS,画“条件数—误差”散点图,并重复四次独立运行。

结果符合预期:

  • 条件数越大,两种算法的差异越大;
  • CGS 的误差随条件数增长得更快;
  • MGS 的误差也被条件数放大,但斜率更缓;
  • 四次运行的图形状一致,说明这不是某一次随机抽样的偶然。

这也解释了一个常见误解:MGS 不是“没有误差”,而是“误差不跨步传播”。 条件数足够大时,MGS 同样会失去正交性,只是比 CGS 晚。

那实际该用什么

如果只是课程作业或小规模矩阵,CGS 和 MGS 的差别可能看不出来。但只要矩阵条件数上到 10⁸ 以上,MGS 的优势就会显现。更稳妥的选择是:

  • Householder QR:用正交变换而不是投影,数值稳定性更好,是 LAPACK 等库的默认做法;
  • MGS + reorthogonalization:如果必须用 Gram–Schmidt,做两遍正交化,把丢失的正交性补回来;
  • 检查条件数:在调用任何 QR 之前先看 cond(A),条件数过大时,结果本身就不该被无条件信任。

C 版本

仓库里还有一个 49 行的 C 实现,独立复现了 CGS。输入是列数、行数,然后逐行给出矩阵;代码在内存里转置存储,让每一列连续,输出时再转回来。它和 MATLAB 的输出逐位对齐,详细实现写在另一篇《用 C 写 Gram–Schmidt》里。

小结

两个版本的公式只差一个下标,但误差可以差二十多个数量级。原因不是“哪个公式更高级”,而是浮点运算中减法相消和误差传播的物理事实。理解这一点之后,“用 MGS 还是 Householder”就不再是背结论,而是根据条件数和精度要求做选择。

MATLAB 脚本、C 实现、法语报告与实验图:https://github.com/yicongl1/Linear-Algebra-Gram-Schmidt