双人课程项目(2 人)

施密特正交化:两种算法的数值比较

上海大学 · 线性代数 II 课程项目(2022)

用 MATLAB 与 C 分别实现经典 Gram–Schmidt(CGS)与修正版(MGS),在病态矩阵和 100 个随机 100×100 矩阵上比较两种标准正交基的 Frobenius 误差,解释理论上等价的公式为什么在浮点运算下分出稳定性。

项目背景

Gram–Schmidt 正交化有两个理论上等价的版本:

  • 经典版本(CGS):每个向量一次性减去它在所有已构造正交向量上的投影;
  • 修正版本(MGS):每做一次投影就立即更新当前向量,再进入下一次投影。

在精确算术下,两者得到同一个标准正交基。但在浮点运算下,运算顺序决定了舍入误差会不会被后续步骤放大。这个课程项目要回答的就是:差异有多大、什么时候出现、为什么。

我和陈诺两人完成了这个项目:MATLAB 实现两个算法与实验,C 语言独立复现,最后用病态矩阵和随机矩阵量化差异。

两种算法

经典版对第 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

代码上的差别只有一个下标:CGS 的内积始终用原始矩阵 a(:,i),MGS 用已经更新过的 b(:,i)。整个项目的实验都围绕这一行展开。

实验设计

  1. 对同一矩阵分别运行 CGS 与 MGS,得到 Q_CGS、Q_MGS;
  2. 用 Frobenius 范数 ‖Q_CGS − Q_MGS‖_F 作为差异度量;
  3. 构造含极小量 ε 的病态矩阵,放大舍入误差;
  4. 随机生成 100 个 100×100、cond > 10⁶ 的矩阵,绘制“条件数—误差”曲线,重复四次独立运行。

结果

矩阵规模cond(A)‖Q_CGS − Q_MGS‖_F
A = [[1,2,3],[2,−1,2],[1,1,2]]3×353.945.92×10⁻³¹(数值上为 0)
B = [[1,1,1],[ε,0,0],[0,ε,0],[0,0,ε]],ε = 10⁻¹⁰4×31.73×10¹⁰0.2679

结论很直接:

  • 条件数小时,两种算法在数值上几乎一致;
  • 条件数极大时,列向量接近线性相关,投影计算出现严重的相消,CGS 的误差被逐步放大,MGS 的误差被限制在每次投影内部;
  • 因此 MGS 的数值稳定性优于 CGS,这也是数值计算库普遍采用 MGS(或 Householder QR)的原因。

C 实现

main.c 把算法写成可执行程序:produitscalaire 算内积,norme1 做归一化,主循环按列正交化。输入是列数、行数,然后逐行给出矩阵元素;当前实现要求方阵,最大 100×100。

gcc -O2 -Wall -o gs main.c -lm
printf "3 3\n1 2 3\n2 -1 2\n1 1 2\n" | ./gs

输出与 MATLAB 的 Q 一致。代码里有一个刻意的转置:读入时存成 a[j][i],输出时再转回来,这样每一列在内存里是连续的,列向量运算的循环顺序更自然。

局限

  • 只处理方阵,最大 100×100;
  • 没有列主元,也没有再正交化,列向量线性相关时会除零或产生无意义的基;
  • C 版本实现的是 CGS,不是 MGS;把内积里的 a[i] 换成 b[i] 就能得到 MGS,但代码保留了课程报告里的经典版本。

如果要用于实际计算,更稳妥的选择是 Householder QR,或者在 Gram–Schmidt 之后再做一次 reorthogonalization。

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

技术文章

01 经典 Gram–Schmidt 与修正版:同样的公式,误差为什么差十几个数量级 投影顺序、相消误差与条件数;从 3×3 的“数值零”到 cond 10¹⁰ 的 0.2679,再到 100 个随机病态矩阵。 02 用 C 写 Gram–Schmidt:49 行代码里的内积、归一化与列主序 转置读入、列向量存储、produitscalaire 与 norme1 两个子程序,以及和 MATLAB 输出逐位对齐的方法。

相关技能

  • MATLAB
  • 学术写作