Algorithme de Gram-Schmidt

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

En algèbre linéaire, dans un espace préhilbertien (c'est-à-dire un espace vectoriel sur le corps des réels ou celui des complexes, muni d'un produit scalaire), le procédé ou algorithme de Gram-Schmidt[1] est un algorithme pour construire, à partir d'une famille libre finie, une base orthonormée du sous-espace qu'elle engendre. On peut aussi utiliser le procédé de Gram-Schmidt sur une famille infinie dénombrable de vecteurs. Ceci permet de démontrer l'existence d'une base hilbertienne si l'espace est séparable.

Énoncé[modifier | modifier le code]

Précisément, en notant N= [0,p]\, ou ℕ :

Théorème — Si (x_n)_{n \in N}\, est une famille libre d'un espace préhilbertien, il existe une et une seule famille orthonormée (e_n)_{n \in N}\, telle que :

  • {\rm Vect}(e_0, \ldots, e_n) = {\rm Vect}(x_0, \ldots, x_n)\, pour tout n\,
  • les produits scalaires (e_n|x_n)\, sont strictement positifs pour tout n\,

On oublie souvent la seconde condition, qui assure l'unicité. Elle permet de parler de la famille orthonormalisée de Gram-Schmidt associée à (x_n)_{n \in N}\,.

L'étape générale de l'algorithme consiste à soustraire au vecteur v_{j+1} son projeté orthogonal sur le sous-espace engendré par v_0,\ldots,v_j. On s'appuie sur la famille orthonormale déjà construite pour le calcul de ce projeté.

Cette méthode a été publiée par Jørgen Pedersen Gram en 1883 et reformulée par Erhard Schmidt en 1907, mais on la trouve déjà dans des travaux de 1816 de Laplace[2].

Applications[modifier | modifier le code]

  • Le procédé d'orthonormalisation de Gram-Schmidt donne (constructivement !) l'existence de bases orthonormées pour tout espace euclidien ou hermitien.
  • On peut aussi orthonormaliser la base canonique (1,X, …) de ℝ[X] et obtenir ainsi une famille de polynômes orthogonaux.
  • Le procédé de Schmidt peut être utilisé dans la décomposition QR d'une matrice[3].

Procédé de Gram-Schmidt[modifier | modifier le code]

Nous définissons l'opérateur de projection orthogonale sur une droite vectorielle dirigée par le vecteur u par[4] :

\mathrm{proj}_{\mathbf{u}}\,(\mathbf{v}) = {\langle\mathbf{u},\mathbf{v}\rangle\over\langle\mathbf{u},\mathbf{u}\rangle}\mathbf{u}.

Le procédé de Gram-Schmidt est alors :

Les deux premières étapes du procédé de Gram–Schmidt.
\mathbf{u}_1 = \mathbf{v}_1, \mathbf{e}_1 = {\mathbf{u}_1 \over ||\mathbf{u}_1||}
\mathbf{u}_2 = \mathbf{v}_2-\mathrm{proj}_{\mathbf{u}_1}\,(\mathbf{v}_2), \mathbf{e}_2 = {\mathbf{u}_2 \over ||\mathbf{u}_2||}
\mathbf{u}_3 = \mathbf{v}_3-\mathrm{proj}_{\mathbf{u}_1}\,(\mathbf{v}_3)-\mathrm{proj}_{\mathbf{u}_2}\,(\mathbf{v}_3), \mathbf{e}_3 = {\mathbf{u}_3 \over ||\mathbf{u}_3||}
\vdots \vdots
\mathbf{u}_k = \mathbf{v}_k-\sum_{j=1}^{k-1}\mathrm{proj}_{\mathbf{u}_j}\,(\mathbf{v}_k), \mathbf{e}_k = {\mathbf{u}_k\over||\mathbf{u}_k||}

Avec :

< , > produit scalaire dans l'espace considéré

V1...Vk ensemble de vecteurs non liées

U1...Uk ensemble de vecteurs orthogonaux deux à deux

e1...ek ensemble de vecteurs orthonormaux deux à deux

Notes et références[modifier | modifier le code]

  1. Mathématiques Tout-en-un. 2e année MP, Dunod,‎ 2004, 2e éd. (ISBN 2-10-007576-4), p. 569
  2. (en) Gram-Schmidt orthogonalization, dans Earliest Known Uses of Some of the Words of Mathematics (G)
  3. A. Quarteroni, R. Sacco, F. Saleri, Méthodes numériques pour le calcul scientifique, Programmes en Matlab, éd. Springer, 2000, p. 83 et suiv. Lire en ligne
  4. La convention choisie pour le produit scalaire hermitien étant ici : linéarité à droite et semi-linéarité à gauche.