Two-person course project
Shanghai University · Linear Algebra II course project (2022)
Implemented classical Gram–Schmidt (CGS) and the modified version (MGS) in MATLAB and C, compared the two orthonormal bases in Frobenius norm on ill-conditioned matrices and 100 random 100×100 matrices, and explained why formulas that are equivalent on paper separate in floating point.
Gram–Schmidt orthogonalisation comes in two versions that are equivalent on paper:
In exact arithmetic both produce the same orthonormal basis. In floating point, the order of operations decides whether rounding errors are amplified by later steps. The project asked how large the difference is, when it appears, and why.
Chen Nuo and I completed the project: MATLAB implementations of both algorithms and the experiments, an independent C reproduction, and ill-conditioned and random matrices to quantify the gap.
Classical Gram–Schmidt subtracts every projection in one pass:
u_k = v_k - Σ_{j<k} <v_k, u_j> u_j
The modified version splits the projections, updating the vector between them:
v_k ← v_k - <v_k, u_j> u_j, j = 1..k-1
In code the difference is one index: CGS always uses the original column a(:,i) for the dot product, while MGS uses the already updated b(:,i). The whole experiment turns on that line.
Q_CGS and Q_MGS;‖Q_CGS − Q_MGS‖_F;ε to amplify rounding errors;100×100 matrices with cond > 10⁶, plot the condition-number/error curve, and repeat the experiment four times.| Matrix | Size | cond(A) | ‖Q_CGS − Q_MGS‖_F |
|---|---|---|---|
A = [[1,2,3],[2,−1,2],[1,1,2]] | 3×3 | 53.94 | 5.92×10⁻³¹ (numerically zero) |
B = [[1,1,1],[ε,0,0],[0,ε,0],[0,0,ε]], ε = 10⁻¹⁰ | 4×3 | 1.73×10¹⁰ | 0.2679 |
The conclusions are direct:
main.c turns the algorithm into an executable: produitscalaire computes a dot product, norme1 normalises, and the main loop orthonormalises column by column. The input is the number of columns, the number of rows, then the matrix row by row; the current implementation requires a square matrix of at most 100×100.
gcc -O2 -Wall -o gs main.c -lm
printf "3 3\n1 2 3\n2 -1 2\n1 1 2\n" | ./gs
The output matches MATLAB’s Q. The code deliberately transposes on input and output — it stores a[j][i] — so that each column is contiguous in memory and the column-vector loops have a natural access order.
a[i] with b[i] in the dot product gives MGS, but the repository keeps the classical version used in the report.For real computation, Householder QR is the safer choice, or Gram–Schmidt followed by a reorthogonalisation pass.
MATLAB scripts, C implementation, French report and experiment figures: https://github.com/yicongl1/Linear-Algebra-Gram-Schmidt