双人课程项目(2 人)
上海大学 · 线性代数 II 课程项目(2022)
用 MATLAB 与 C 分别实现经典 Gram–Schmidt(CGS)与修正版(MGS),在病态矩阵和 100 个随机 100×100 矩阵上比较两种标准正交基的 Frobenius 误差,解释理论上等价的公式为什么在浮点运算下分出稳定性。
Gram–Schmidt 正交化有两个理论上等价的版本:
在精确算术下,两者得到同一个标准正交基。但在浮点运算下,运算顺序决定了舍入误差会不会被后续步骤放大。这个课程项目要回答的就是:差异有多大、什么时候出现、为什么。
我和陈诺两人完成了这个项目: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)。整个项目的实验都围绕这一行展开。
Q_CGS、Q_MGS;‖Q_CGS − Q_MGS‖_F 作为差异度量;ε 的病态矩阵,放大舍入误差;100×100、cond > 10⁶ 的矩阵,绘制“条件数—误差”曲线,重复四次独立运行。| 矩阵 | 规模 | cond(A) | ‖Q_CGS − Q_MGS‖_F |
|---|---|---|---|
A = [[1,2,3],[2,−1,2],[1,1,2]] | 3×3 | 53.94 | 5.92×10⁻³¹(数值上为 0) |
B = [[1,1,1],[ε,0,0],[0,ε,0],[0,0,ε]],ε = 10⁻¹⁰ | 4×3 | 1.73×10¹⁰ | 0.2679 |
结论很直接:
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],输出时再转回来,这样每一列在内存里是连续的,列向量运算的循环顺序更自然。
a[i] 换成 b[i] 就能得到 MGS,但代码保留了课程报告里的经典版本。如果要用于实际计算,更稳妥的选择是 Householder QR,或者在 Gram–Schmidt 之后再做一次 reorthogonalization。
MATLAB 脚本、C 实现、法语报告与实验图:https://github.com/yicongl1/Linear-Algebra-Gram-Schmidt