Algorithme de Gram-Schmidt

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 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é

Précisément, en notant Modèle:Math avec Modèle:Mvar dans Modèle:Math : Modèle:Théorème

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 Modèle:Math son projeté orthogonal sur le sous-espace engendré par Modèle:Math. 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.

Applications

• Le procédé d'orthonormalisation de Gram-Schmidt donne constructivement l'existence de bases orthonormées pour tout espace euclidien ou hermitien. Cet algorithme est ainsi souvent utilisé en informatique pour effectuer des rendus 3D.
• 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.

Procédé de Gram-Schmidt

Nous définissons l'opérateur de projection orthogonale sur une droite vectorielle dirigée par le vecteur Modèle:Math par :

${\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{j}}_{𝐮}(𝐯)=\frac{⟨𝐮,𝐯⟩}{⟨𝐮,𝐮⟩}𝐮.$

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

Les deux premières étapes du procédé de Gram–Schmidt.

	${𝐮}_1={𝐯}_1,$		${𝐞}_1=\frac{{𝐮}_1}{\Vert {𝐮}_1\Vert }$
	${𝐮}_2={𝐯}_2-{\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{j}}_{{𝐮}_1}({𝐯}_2),$		${𝐞}_2=\frac{{𝐮}_2}{\Vert {𝐮}_2\Vert }$
	${𝐮}_3={𝐯}_3-{\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{j}}_{{𝐮}_1}({𝐯}_3)-{\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{j}}_{{𝐮}_2}({𝐯}_3),$		${𝐞}_3=\frac{{𝐮}_3}{\Vert {𝐮}_3\Vert }$
	$⋮$		$⋮$
	${𝐮}_k={𝐯}_k-\sum _{j=1}^{k-1}{\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{j}}_{{𝐮}_j}({𝐯}_k),$		${𝐞}_k=\frac{{𝐮}_k}{\Vert {𝐮}_k\Vert }$

Avec :

• Modèle:Math, le produit scalaire dans l'espace considéré
• Modèle:Math, un ensemble de vecteurs non liés
• Modèle:Math, un ensemble de vecteurs orthogonaux deux à deux
• Modèle:Math, l'ensemble de vecteurs orthonormaux deux à deux recherché