用 C 写 Gram–Schmidt:49 行代码里的内积、归一化与列主序
项目仓库:https://github.com/yicongl1/Linear-Algebra-Gram-Schmidt
MATLAB 写 Gram–Schmidt 只需要几行,因为 dot、norm 和整列运算都是现成的。换到 C 里,所有东西都要自己落地:矩阵怎么存、内积怎么写、归一化怎么避免除零、输出怎么和 MATLAB 对齐。
仓库里的 main.c 只有 49 行,但正好把“数学公式变成可执行程序”的几步都走了一遍。
输入与存储
程序先读两个整数:
int x, y;
scanf("%d%d", &x, &y);
约定 x 是列数,y 是行数。接下来逐行读入矩阵:
for (int i = 1; i <= y; i++)
for (int j = 1; j <= x; j++)
scanf("%lf", a[j] + i);
注意这里存的是 a[j][i],不是 a[i][j]:第一个下标是列,第二个是行。也就是说,读入时顺手转置了。这样 a[i] 指向的是第 i 列,列内的 x 个元素在内存里连续,后面按列做内积和减法时循环顺序更自然。
代价是下标必须从 1 开始,a[0] 那一行/列空着不用;对于 100×100 的 double,两个数组约占 160 KB,放在栈上不算小,但在这个规模下能跑。
两个子程序
内积:
double produitscalaire(double a[], double b[], int l) {
double s = 0;
for (int i = 1; i <= l; i++) s += a[i] * b[i];
return s;
}
归一化:
void norme1(double a[], int l) {
double s = 0;
for (int i = 1; i <= l; i++) s += a[i] * a[i];
s = sqrt(s);
for (int i = 1; i <= l; i++) a[i] /= s;
}
两个函数都接收“一个列向量 + 长度”。C 没有向量类型,所以列向量就是一个 double*,长度单独传。这样的接口很原始,但足够清楚。
主循环
对每一列 i:
- 把原始列复制到输出矩阵
b; - 对之前每一列
j < i,减去b[i]在b[j]上的投影; - 归一化。
for (int i = 1; i <= y; i++) {
for (int j = 1; j <= x; j++) b[i][j] = a[i][j];
for (int j = 1; j < i; j++) {
double ps = produitscalaire(a[i], b[j], x);
for (int k = 1; k <= x; k++)
b[i][k] -= ps * b[j][k];
}
norme1(b[i], x);
}
这里有一个关键细节:内积用的是 a[i],也就是原始列。所以这份 C 代码实现的是经典 Gram–Schmidt(CGS),不是修正版。如果把 produitscalaire(a[i], ...) 改成 produitscalaire(b[i], ...),每次投影都用更新后的向量,就得到 MGS——和 MATLAB 那边只差一个字母的改动完全对应。
另外,b[i][j] = a[i][j] 这一行在方阵下成立;如果 x != y,列数和行数的循环边界会不一致。当前实现要求方阵,最大 100×100。
输出
最后再转置回去:
for (int i = 1; i <= y; i++) {
for (int j = 1; j <= x; j++)
printf("%10lf", b[j][i]);
printf("\n");
}
%10lf 给每个数固定 10 个字符宽度,方便肉眼对齐。对前面那个 3×3 例子:
gcc -O2 -Wall -o gs main.c -lm
printf "3 3\n1 2 3\n2 -1 2\n1 1 2\n" | ./gs
输出:
0.408248 0.759072 0.507093
0.816497 -0.552052 0.169031
0.408248 0.345033 -0.845154
和 MATLAB 的 Q 一致。这一步很重要:数值代码如果没有一个已知正确的参照,很容易把转置、下标或归一化顺序写错,却看起来“跑通了”。
这份实现的问题
- 没有除零保护:如果某一列在正交化后变成零向量(列向量线性相关),
norme1会除以 0,输出nan或inf; - 没有列主元:CGS 本身对列顺序敏感,交换列可能改变数值结果;
- 固定 100×100:没有动态分配,也没有越界检查;
- 1-based 下标:数学上自然,C 里容易越界;所有循环都必须从 1 开始,
[0]永远空着; - 栈上大数组:160 KB 在桌面没问题,在嵌入式环境可能直接爆栈。
这些不是“写错了”,而是课程作业的边界:目标是验证算法和输出,不是做一个通用数值库。如果要做通用实现,至少应该动态分配、检查零范数、提供 m×n 非方阵支持,并考虑 Householder QR。
小结
49 行 C 代码把 Gram–Schmidt 拆成了三个可验证的部分:内积、归一化、按列消去。真正容易错的不是公式,而是存储顺序和下标——只要把“列主序”想清楚,后面的循环就是自然结果。
源码、MATLAB 对照与报告:https://github.com/yicongl1/Linear-Algebra-Gram-Schmidt
相关技能
- MATLAB
- 学术写作