algorithme de Gram-Schmidt

Imaginez deux flèches obliques tracées sur une feuille. Pour rendre la seconde perpendiculaire à la première, on lui retire toute la part qui pointe dans la direction de la première. La flèche restante forme alors un angle droit avec elle.

Gram-Schmidt répète ce geste avec chaque nouveau vecteur : il soustrait ses ombres sur les directions déjà construites. On obtient des vecteurs non nuls et orthogonaux, donc indépendants les uns des autres. En ajustant ensuite chacun à une longueur de 1, la famille devient orthonormée.

Dans un espace vectoriel réel muni d'un produit scalaire, considérons une famille ordonnée de vecteurs linéairement indépendants, notés u₁, …, u_n. L'algorithme de Gram-Schmidt construit des vecteurs v₁, …, v_n deux à deux orthogonaux. Il conserve en outre les sous-espaces successifs engendrés : pour chaque indice k, les k premiers vecteurs u et les k premiers vecteurs v engendrent le même sous-espace.

Le premier vecteur est conservé. Pour chaque indice k à partir de 2, on retire à u_k sa projection sur chacune des directions v déjà obtenues : $v_k=u_k-{\sum }_{j=1}^{k-1}\frac{⟨u_k,v_j⟩}{⟨v_j,v_j⟩}{v}_{j}v\_k=u\_k-\backslash sum\_\{j=1\}^\{k-1\}\backslash frac\{\backslash langle\; u\_k,v\_j\backslash rangle\}\{\backslash langle\; v\_j,v\_j\backslash rangle\}v\_j$. Le nombre $\frac{⟨u_k,v_j⟩}{⟨v_j,v_j⟩}\backslash frac\{\backslash langle\; u\_k,v\_j\backslash rangle\}\{\backslash langle\; v\_j,v\_j\backslash rangle\}$ est le coefficient scalaire de projection ; multiplié par v_j, il donne la composante projetée de u_k dans cette direction.

L'indépendance linéaire garantit que chaque v_k est non nul. Si l'on divise ensuite chaque v_k par sa norme, on obtient un vecteur q_k de longueur 1 et une famille orthonormée : $q_k=\frac{v_k}{\parallel v_k\parallel }q\_k=\backslash frac\{v\_k\}\{\backslash lVert\; v\_k\backslash rVert\}$. L'ordre des vecteurs d'entrée fait partie des données : le changer peut produire une autre famille orthogonale, tout en conservant le même espace final.

Soit une famille ordonnée et libre (u₁, …, u_n) dans un espace réel muni d'un produit scalaire.

1. Poser v₁ = u₁.
2. Pour chaque indice k de 2 à n, calculer $v_k=u_k-{\sum }_{j=1}^{k-1}\frac{⟨u_k,v_j⟩}{⟨v_j,v_j⟩}{v}_{j}v\_k=u\_k-\backslash sum\_\{j=1\}^\{k-1\}\backslash frac\{\backslash langle\; u\_k,v\_j\backslash rangle\}\{\backslash langle\; v\_j,v\_j\backslash rangle\}v\_j$.
3. Si une famille orthonormée est souhaitée, poser $q_k=\frac{v_k}{\parallel v_k\parallel }q\_k=\backslash frac\{v\_k\}\{\backslash lVert\; v\_k\backslash rVert\}$ pour chaque indice k.

À l'issue du procédé, les vecteurs v sont non nuls et deux à deux orthogonaux ; les vecteurs q sont en plus de norme 1.

Le procédé demande un espace muni d'un produit scalaire, car les projections et les normes en dépendent. La famille d'entrée doit être ordonnée et linéairement indépendante. Avec ces données, chaque dénominateur est strictement positif et le résultat contient autant de vecteurs que la famille initiale.

Ces conditions se contrôlent pendant le calcul : avant de normaliser v_k, sa norme doit être non nulle. Dans un calcul approché, les vecteurs doivent aussi être suffisamment éloignés de la dépendance linéaire pour que les soustractions ne détruisent pas la précision.

Par exemple, si u₂ = 2u₁, sa projection sur v₁ est u₂ tout entier : le second résidu vaut zéro et sa normalisation est impossible. Il faut alors supprimer le vecteur redondant ou extraire d'abord une famille libre.

Orthogonalisons deux vecteurs du plan avec le produit scalaire usuel.
Données :
Le premier vecteur est u₁ = (1, 1).
Le second vecteur est u₂ = (1, 0).
La famille est libre, car les deux vecteurs ne sont pas colinéaires.

1. Le premier vecteur est conservé : v₁ = u₁ = (1, 1). Son produit scalaire avec lui-même vaut 2.

2. La projection de u₂ sur v₁ est $p=\frac{⟨u_2,v_1⟩}{⟨v_1,v_1⟩}{v}_1=\frac{1}{2}(1,1)=(\frac{1}{2},\frac{1}{2})p=\backslash frac\{\backslash langle\; u\_2,v\_1\backslash rangle\}\{\backslash langle\; v\_1,v\_1\backslash rangle\}v\_1=\backslash frac\{1\}\{2\}(1,1)=\backslash left(\backslash frac\{1\}\{2\},\backslash frac\{1\}\{2\}\backslash right)$.

3. On retire cette projection : $v_2=u_2-p=(1,0)-(\frac{1}{2},\frac{1}{2})=(\frac{1}{2},-\frac{1}{2})v\_2=u\_2-p=(1,0)-\backslash left(\backslash frac\{1\}\{2\},\backslash frac\{1\}\{2\}\backslash right)=\backslash left(\backslash frac\{1\}\{2\},-\backslash frac\{1\}\{2\}\backslash right)$.

4. Le contrôle d'orthogonalité donne $⟨v_1,v_2⟩=1\times \frac{1}{2}+1\times (-\frac{1}{2})=0\backslash langle\; v\_1,v\_2\backslash rangle=1\backslash times\backslash frac\{1\}\{2\}+1\backslash times\backslash left(-\backslash frac\{1\}\{2\}\backslash right)=0$. Les deux directions sont bien perpendiculaires.

5. En normalisant, on obtient $q_1=(\frac{1}{\sqrt{2}},\frac{1}{\sqrt{2}}),q_2=(\frac{1}{\sqrt{2}},-\frac{1}{\sqrt{2}})q\_1=\backslash left(\backslash frac\{1\}\{\backslash sqrt\{2\}\},\backslash frac\{1\}\{\backslash sqrt\{2\}\}\backslash right),\backslash qquad\; q\_2=\backslash left(\backslash frac\{1\}\{\backslash sqrt\{2\}\},-\backslash frac\{1\}\{\backslash sqrt\{2\}\}\backslash right)$. Chacun a une norme égale à 1. La construction géométrique montre que u₂ se décompose en une projection parallèle à v₁ et un résidu v₂ perpendiculaire.

Pour ajuster un modèle par moindres carrés, on peut orthonormaliser les colonnes indépendantes de la matrice des données. Les vecteurs obtenus forment la matrice Q ; la matrice triangulaire R regroupe les coefficients de projection sur les directions précédentes et, sur sa diagonale, les normes des résidus successifs. Sur des données presque redondantes, une factorisation de Householder est généralement préférée pour mieux préserver la précision numérique.

Dans l'algorithme QR de calcul des valeurs propres, une factorisation orthogonale est répétée à chaque itération. Gram-Schmidt explique la construction de Q, mais les logiciels emploient souvent des transformations de Householder lorsque la stabilité est prioritaire.

À la main, le procédé transforme aussi une base peu commode en directions perpendiculaires pour calculer des coordonnées, des distances ou des projections. Si une seule projection sur un sous-espace déjà orthonormé est recherchée, il suffit de la calculer directement sans reconstruire toute la base.

Famille orthogonale et famille orthonormée. Dans une famille orthogonale, les produits scalaires entre vecteurs distincts sont nuls ; leurs longueurs restent quelconques. Elle est orthonormée seulement si chaque norme vaut aussi 1. Les vecteurs v₁ et v₂ de l'exemple sont orthogonaux, tandis que q₁ et q₂ sont orthonormés.

Gram-Schmidt et projection orthogonale. Une projection donne la composante d'un vecteur sur un sous-espace fixé. Gram-Schmidt enchaîne plusieurs projections et soustractions afin de construire de nouvelles directions. Dans l'exemple, la projection orthogonale de u₂ sur la droite engendrée par v₁ donne le vecteur p ; le passage de la famille (u₁, u₂) à (v₁, v₂) est le procédé complet.

Famille orthonormée et matrice orthogonale. Une matrice carrée réelle est orthogonale lorsque ses colonnes forment une base orthonormée, ce qui se teste par Q^TQ = I. Une famille orthonormée de deux vecteurs dans un espace de dimension trois ne forme pas, à elle seule, une matrice orthogonale carrée.

Dépendance exacte. Si un nouveau vecteur appartient au sous-espace déjà construit, toutes ses composantes sont retirées et le résidu vaut exactement zéro. La division par sa norme est alors impossible. Il faut écarter ce vecteur ou sélectionner une sous-famille libre.

Ordre des entrées. Le sous-espace final ne change pas, mais la base produite peut changer. Avec u₁ = (1, 1) puis u₂ = (1, 0), l'exemple donne deux directions diagonales. Dans l'ordre inverse, le procédé donne les directions (1, 0) et (0, 1). Il faut donc conserver un ordre imposé par le problème.

Vecteurs presque dépendants en machine. Des soustractions entre nombres très proches peuvent faire perdre des chiffres significatifs ; des produits scalaires censés valoir 0 deviennent visiblement non nuls. Il n'existe pas de seuil universel, car il dépend de l'échelle et de la précision. Il faut employer Gram-Schmidt modifié, réorthogonaliser ou préférer des transformations de Householder.

produit scalaire. Précise l'opération qui mesure les composantes projetées et certifie l'orthogonalité.

famille libre. Explique la condition qui empêche un résidu de devenir nul pendant le procédé.

matrice orthogonale. Relie une base orthonormée aux matrices Q utilisées dans les factorisations numériques.

valeur propre. Présente la notion recherchée par l'algorithme QR, auquel l'orthogonalisation contribue.