Projet de cours en binôme
Université de Shanghai · projet du cours Algèbre linéaire II (2022)
Implémentation de Gram–Schmidt classique (CGS) et modifié (MGS) en MATLAB et en C, comparaison des deux bases orthonormées en norme de Frobenius sur des matrices mal conditionnées et 100 matrices aléatoires 100×100, et explication de la séparation de formules équivalentes sur le papier.
L’orthogonalisation de Gram–Schmidt existe en deux versions équivalentes sur le papier :
En arithmétique exacte, les deux produisent la même base orthonormée. En virgule flottante, l’ordre des opérations décide si les erreurs d’arrondi sont amplifiées par les étapes suivantes. Le projet cherchait à mesurer l’écart, à identifier quand il apparaît et à l’expliquer.
Chen Nuo et moi avons réalisé le projet : implémentations MATLAB des deux algorithmes et expériences, reproduction indépendante en C, puis matrices mal conditionnées et aléatoires pour quantifier l’écart.
La version classique retire toutes les projections en une fois :
u_k = v_k - Σ_{j<k} <v_k, u_j> u_j
La version modifiée les applique successivement, en mettant à jour le vecteur entre chaque :
v_k ← v_k - <v_k, u_j> u_j, j = 1..k-1
Dans le code, la différence tient à un indice : CGS utilise toujours la colonne d’origine a(:,i) pour le produit scalaire, MGS utilise la colonne déjà mise à jour b(:,i). Toute l’expérience repose sur cette ligne.
Q_CGS et Q_MGS pour une même matrice ;‖Q_CGS − Q_MGS‖_F ;ε très petit pour amplifier les erreurs d’arrondi ;100×100 de conditionnement cond > 10⁶, tracer la courbe conditionnement/erreur et répéter quatre fois.| Matrice | Taille | cond(A) | ‖Q_CGS − Q_MGS‖_F |
|---|---|---|---|
A = [[1,2,3],[2,−1,2],[1,1,2]] | 3×3 | 53,94 | 5,92×10⁻³¹ (zéro numérique) |
B = [[1,1,1],[ε,0,0],[0,ε,0],[0,0,ε]], ε = 10⁻¹⁰ | 4×3 | 1,73×10¹⁰ | 0,2679 |
Les conclusions sont directes :
main.c transforme l’algorithme en programme exécutable : produitscalaire calcule un produit scalaire, norme1 normalise, et la boucle principale orthonormalise colonne par colonne. L’entrée donne le nombre de colonnes, le nombre de lignes, puis la matrice ligne par ligne ; l’implémentation actuelle exige une matrice carrée d’au plus 100×100.
gcc -O2 -Wall -o gs main.c -lm
printf "3 3\n1 2 3\n2 -1 2\n1 1 2\n" | ./gs
La sortie coïncide avec la matrice Q de MATLAB. Le code transpose volontairement à l’entrée et à la sortie — il stocke a[j][i] — pour que chaque colonne soit contiguë en mémoire et que les boucles sur les vecteurs-colonnes aient un ordre d’accès naturel.
a[i] par b[i] dans le produit scalaire donne MGS, mais le dépôt conserve la version classique du rapport.Pour un calcul réel, la factorisation QR de Householder est plus sûre, ou Gram–Schmidt suivi d’une passe de réorthogonalisation.
Scripts MATLAB, implémentation C, rapport français et figures : https://github.com/yicongl1/Linear-Algebra-Gram-Schmidt