Projet de cours en binôme

Orthogonalisation de Gram–Schmidt : une comparaison numérique

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.

Contexte

L’orthogonalisation de Gram–Schmidt existe en deux versions équivalentes sur le papier :

  • classique (CGS) : toutes les projections d’un vecteur sont soustraites en une seule passe ;
  • modifiée (MGS) : chaque projection est appliquée immédiatement, et le vecteur mis à jour sert à la projection suivante.

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.

Les deux algorithmes

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.

Protocole

  1. Calculer Q_CGS et Q_MGS pour une même matrice ;
  2. mesurer l’écart avec la norme de Frobenius ‖Q_CGS − Q_MGS‖_F ;
  3. construire une matrice mal conditionnée contenant un ε très petit pour amplifier les erreurs d’arrondi ;
  4. générer 100 matrices aléatoires 100×100 de conditionnement cond > 10⁶, tracer la courbe conditionnement/erreur et répéter quatre fois.

Résultats

MatriceTaillecond(A)‖Q_CGS − Q_MGS‖_F
A = [[1,2,3],[2,−1,2],[1,1,2]]3×353,945,92×10⁻³¹ (zéro numérique)
B = [[1,1,1],[ε,0,0],[0,ε,0],[0,0,ε]], ε = 10⁻¹⁰4×31,73×10¹⁰0,2679

Les conclusions sont directes :

  • pour un faible conditionnement, les deux algorithmes coïncident numériquement ;
  • pour un conditionnement très élevé, les colonnes sont presque linéairement dépendantes, l’annulation dans le calcul des projections devient sévère, l’erreur de CGS est amplifiée d’une étape à l’autre, tandis que celle de MGS reste locale à chaque projection ;
  • MGS est donc numériquement plus stable, ce qui explique son usage dans les bibliothèques de calcul (ou la factorisation QR de Householder).

Implémentation en C

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.

Limites

  • matrices carrées uniquement, taille maximale 100×100 ;
  • pas de pivotage de colonnes ni de réorthogonalisation : des colonnes linéairement dépendantes provoquent une division par zéro ou une base sans signification ;
  • la version C implémente CGS, pas MGS ; remplacer 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

Notes techniques

01 Gram–Schmidt classique et modifié : pourquoi des formules équivalentes diffèrent de plus de dix ordres de grandeur Ordre des projections, annulation et conditionnement : d'un zéro numérique 3×3 à 0,2679 pour cond 10¹⁰, puis 100 matrices aléatoires mal conditionnées. 02 Écrire Gram–Schmidt en C : produits scalaires, normalisation et logique colonne-major en 49 lignes Entrée transposée, stockage par colonnes, les fonctions produitscalaire et norme1, et comment retrouver exactement la sortie MATLAB.

Compétences associées

  • MATLAB
  • Rédaction scientifique