12.7 Le procédé d'orthogonalisation de Gram-Schmidt

Les sections précédentes ont montré tout l'avantage de travailler avec une base orthogonale (ou orthonormale) pour un sous-espace \(W\), puisque cela permet par exemple d'accéder directement aux composantes d'un vecteur relativement à cette base, ou de calculer plus facilement des projections orthogonales sur \(W\).

Mais il se peut que le sous-espace \(W\) soit défini dès le départ par une base \(\mathcal{B}\) qui n'est pas orthogonale. Pour profiter des avantages décrits ci-dessus, il est donc naturel de chercher une autre base de \(W\), \(\mathcal{B}'\), qui soit elle orthogonale.

Nous allons voir qu'une telle base existe toujours, et nous verrons comment la construire en modifiant la base de départ, par un algorithme appelé le procédé d'orthogonalisation de Gram-Schmidt.

L'idée est de ''tordre'' un à un les vecteurs de \(\mathcal{B}\), de façon à les rendre progressivement orthogonaux deux-à-deux, et en garantissant qu'ils engendrent toujours \(W\).

Voyons comment faire sur un exemple très simple d'une base ne contenant que deux vecteurs.

L'idée, sur un exemple où \(\dim(W)=2\)

Considérons le plan de \(\mathbb{R}^3\), \(W=\mathrm{Vect}\{\boldsymbol{w}_1,\boldsymbol{w}_2\}\), où \[ \boldsymbol{w}_1= \begin{pmatrix} 3\\-1 \\2 \end{pmatrix}\,,\qquad \boldsymbol{w}_2= \begin{pmatrix} 1\\ 2 \\1 \end{pmatrix}\,. \] La paire \(\mathcal{B}=(\boldsymbol{w}_1,\boldsymbol{w}_2)\) est une base de \(W\), mais elle n'est pas orthogonale car \[\boldsymbol{w}_1\cdotp\boldsymbol{w}_2=3\neq 0\,.\] Voyons comment modifier \(\mathcal{B}\) de façon à la transformer en une autre base pour \(W\), orthogonale cette fois.

La nouvelle base sera \(\mathcal{B}'=(\boldsymbol{v}_1,\boldsymbol{v}_2)\), avec \[\begin{aligned} \boldsymbol{v}_1&:= \boldsymbol{w}_1\,,\\ \boldsymbol{v}_2&:= \boldsymbol{w}_2-\alpha \boldsymbol{w}_1\,. \end{aligned}\] Voyons ce qui se passe lorsque \(\alpha\) varie:

Remarquons que l'on ''tord'' \(\boldsymbol{w}_2\) en lui rajoutant un multiple de \(\boldsymbol{w}_1\), ce qui fait que \(\boldsymbol{v}_2\) reste dans le plan \(W\)!

C'est évident sur l'animation ci-dessus, mais écrivons-le explicitement:

Lemme: Peu importe la valeur du scalaire \(\alpha\), \(\mathcal{B}'=(\boldsymbol{v}_1,\boldsymbol{v}_2)\) est toujours une base de \(W\).

(en exercice)

Il s'agit ensuite de choisir \(\alpha\) de façon à ce que \(\mathcal{B}'\) soit orthogonale. Or la seule condition à satisfaire est que \[ \boldsymbol{v}_1\cdotp\boldsymbol{v}_2=0\,, \] qui se traduit par \[ \boldsymbol{w}_1\cdotp(\boldsymbol{w}_2-\alpha\boldsymbol{w}_1)=0\,, \] et qui implique \[ \alpha= \frac{\boldsymbol{w}_1\cdotp\boldsymbol{w}_2}{\|\boldsymbol{w}_1\|^2} \] Ainsi, \(\alpha\boldsymbol{w}_1=\frac{\boldsymbol{w}_1\cdotp\boldsymbol{w}_2}{\|\boldsymbol{w}_1\|^2} \boldsymbol{w}_1\), qui n'est autre que la projection de \(\boldsymbol{w}_2\) sur \(\boldsymbol{w}_1\) (c'est-à-dire sur \(\boldsymbol{v}_1\)). En résumé, on a pris \(\mathcal{B}'=(\boldsymbol{v}_1,\boldsymbol{v}_2)\), où \[\begin{aligned} \boldsymbol{v}_1&:= \boldsymbol{w}_1\,,\\ \boldsymbol{v}_2&:= \boldsymbol{w}_2-\mathrm{proj}_{\boldsymbol{v}_1}(\boldsymbol{w}_2)\,, \end{aligned}\] qui donne \[ \boldsymbol{v}_1=\begin{pmatrix} 3\\ -1\\ 2 \end{pmatrix}\,,\qquad \boldsymbol{v}_2=\frac{1}{14} \begin{pmatrix} 5\\ 31\\ 8 \end{pmatrix}\,. \] Maintenant, \(\mathcal{B}'=(\boldsymbol{v}_1,\boldsymbol{v}_2)\) est orthogonale puisque \(\boldsymbol{v}_1\cdotp\boldsymbol{v}_2=0\).

La construction décrite dans l'exemple ci-dessus n'a rien de particulier à \(\mathbb{R}^3\), et peut s'utiliser pour orthogonaliser la base de n'importe quel sous-espace de dimension \(2\):

Exemple: Considérons le plan de \(\mathbb{R}^5\) engendré par \[ \boldsymbol{w}_1= \begin{pmatrix} 1\\ 0\\ 1\\ -1\\ 0 \end{pmatrix}\,,\qquad \boldsymbol{w}_2= \begin{pmatrix} 0\\ -2\\ 0\\ 1\\ 1 \end{pmatrix}\,. \] La base \(\mathcal{B}=(\boldsymbol{w}_1,\boldsymbol{w}_2)\) de ce plan n'est pas orthogonale, mais en prenant \(\boldsymbol{v}_1:= \boldsymbol{w}_1\), et \[ \boldsymbol{v}_2:= \boldsymbol{w}_2-\mathrm{proj}_{\boldsymbol{w}_1}(\boldsymbol{w}_2) = \begin{pmatrix} 0\\ -2\\ 0\\ 1\\ 1 \end{pmatrix} -\frac{-1}{3} \begin{pmatrix} 1\\ 0\\ 1\\ -1\\ 0 \end{pmatrix} = \begin{pmatrix} 1/3\\ -2\\ 1/3\\ 2/3\\ 1 \end{pmatrix}\,, \] on obtient une base \(\mathcal{B}'=(\boldsymbol{v}_1,\boldsymbol{v}_2)\) orthogonale.

Cas général

Dans le cas général, considérons un sous-espace \(W\) de \(\mathbb{R}^3\), de dimension \(k\leqslant n\), muni d'une base (a priori pas orthogonale) \[ \mathcal{B}=(\boldsymbol{w}_1,\dots,\boldsymbol{w}_k)\,, \] et voyons comment l'utiliser pour construire une nouvelle base de \(W\), \[ \mathcal{B}'=(\boldsymbol{v}_1,\dots,\boldsymbol{v}_k)\,, \] qui soit orthogonale. Cette construction est le procédé d'orthogonalisation de Gram-Schmidt.

L'idée est de procéder de manière inductive, le \(j\)-ème vecteur \(\boldsymbol{v}_j\) de \(\mathcal{B}'\) étant construit à partir des \(j\) premiers vecteurs de \(\mathcal{B}\), de façon à ce que pour tout \(j=1,\dots,k\), deux conditions soient satisfaites:

La vérification de ces conditions implique qu'à la fin, lorsque \(j=k\), on a bien construit une famille \(\{\boldsymbol{v}_1,\dots,\boldsymbol{v}_k\}\) qui est orthogonale (et donc libre), et qui engendre \(W\).

L'exemple précédent a suggéré de commencer par modifier \(\boldsymbol{w}_2\) en lui soustrayant sa projection sur \(\boldsymbol{w}_1\). Pour les suivants, on peut continuer à soustraire à chaque vecteur sa projection sur l'espace engendré par les précédents: \[\begin{aligned} \boldsymbol{v}_1&:= \boldsymbol{w}_1\,,\\ \boldsymbol{v}_2&:= \boldsymbol{w}_2-\mathrm{proj}_{\mathrm{Vect}\{\boldsymbol{w}_1\}}(\boldsymbol{w}_2)\,,\\ \boldsymbol{v}_3&:= \boldsymbol{w}_3-\mathrm{proj}_{\mathrm{Vect}\{\boldsymbol{w}_1,\boldsymbol{w}_2\}}(\boldsymbol{w}_3)\,,\\ \vdots&\\ \boldsymbol{v}_j&:= \boldsymbol{w}_j-\mathrm{proj}_{\mathrm{Vect}\{\boldsymbol{w}_1,\dots,\boldsymbol{w}_{j-1}\}}(\boldsymbol{w}_j)\\ \vdots&\\ \boldsymbol{v}_k&:= \boldsymbol{w}_k-\mathrm{proj}_{\mathrm{Vect}\{\boldsymbol{w}_1,\dots\dots,\boldsymbol{w}_{k-1}\}}(\boldsymbol{w}_k)\,. \end{aligned}\] Remarquons que le procédé nécessite, à l'étape \(j\), de calculer la projection sur le sous-espace \(\mathrm{Vect}\{\boldsymbol{w}_1,\dots,\boldsymbol{w}_{j-1}\}\). Or, puisque \[ \mathrm{Vect}\{\boldsymbol{w}_1,\dots,\boldsymbol{w}_{j-1}\}=\mathrm{Vect}\{\boldsymbol{v}_1,\dots,\boldsymbol{v}_{j-1}\}\,, \] on a, pour tout \(j\), \[ \mathrm{proj}_{\mathrm{Vect}\{\boldsymbol{w}_1,\dots,\boldsymbol{w}_{j-1}\}}(\boldsymbol{w}_{j}) = \mathrm{proj}_{\mathrm{Vect}\{\boldsymbol{v}_1,\dots,\boldsymbol{v}_{j-1}\}}(\boldsymbol{w}_{j})\,. \] Maintenant, comme \(\{\boldsymbol{v}_1,\dots,\boldsymbol{v}_{j-1}\}\) est orthogonale, la formule de la section précédente permet d'écrire cette dernière projection comme \[ \mathrm{proj}_{\mathrm{Vect}\{\boldsymbol{v}_1,\dots,\boldsymbol{v}_{j-1}\}}(\boldsymbol{w}_{j}) =\sum_{i=1}^{j-1}\frac{\boldsymbol{w}_{j}\cdotp\boldsymbol{v}_i}{\|\boldsymbol{v}_i\|^2}\boldsymbol{v}_i\,. \] Donc on peut écrire le procédé comme suit: \[\begin{aligned} \boldsymbol{v}_1&:= \boldsymbol{w}_1\,,\\ \boldsymbol{v}_2&:= \boldsymbol{w}_2-\frac{\boldsymbol{w}_2\cdotp\boldsymbol{v}_1}{\|\boldsymbol{v}_1\|^2}\boldsymbol{v}_1\\ \boldsymbol{v}_3&:= \boldsymbol{w}_3-\sum_{i=1}^2\frac{\boldsymbol{w}_3\cdotp\boldsymbol{v}_i}{\|\boldsymbol{v}_i\|^2}\boldsymbol{v}_i\,,\\ \vdots&\\ \boldsymbol{v}_k&:= \boldsymbol{w}_k-\sum_{i=1}^{k-1}\frac{\boldsymbol{w}_k\cdotp\boldsymbol{v}_i}{\|\boldsymbol{v}_i\|^2}\boldsymbol{v}_i\,,\\ \end{aligned}\]

Remarque:

Exemple: Considérons, dans \(\mathbb{R}^4\), le sous-espace \(W\) défini par \[ W=\mathrm{Vect}\{\boldsymbol{w}_1,\boldsymbol{w}_2,\boldsymbol{w}_3\}\,, \] où \[ \boldsymbol{w}_1:= \begin{pmatrix} 1\\ 0\\ 1\\ 0 \end{pmatrix}\,,\quad \boldsymbol{w}_2:= \begin{pmatrix} -1\\ 0\\ 0\\ 1 \end{pmatrix}\,,\quad \boldsymbol{w}_3:= \begin{pmatrix} 0\\ 1\\ -1\\ 0 \end{pmatrix}\,. \] Appliquons le procédé de Gram-Schmidt. D'abord, \(\boldsymbol{v}_1:= \boldsymbol{w}_1\), puis \[\begin{aligned} \boldsymbol{v}_2&:= \boldsymbol{w}_2-\frac{\boldsymbol{w}_2\cdotp\boldsymbol{v}_1}{\|\boldsymbol{v}_1\|^2}\boldsymbol{v}_1\\ &= \begin{pmatrix} -1\\ 0\\ 0\\ 1 \end{pmatrix} -\frac{(-1)}{2} \begin{pmatrix} 1\\ 0\\ 1\\ 0 \end{pmatrix}= \begin{pmatrix} -1/2\\ 0\\ 1/2\\ 1\end{pmatrix}\,, \end{aligned}\] et pour finir \[\begin{aligned} \boldsymbol{v}_3&:= \boldsymbol{w}_3- \frac{\boldsymbol{w}_3\cdotp\boldsymbol{v}_1}{\|\boldsymbol{v}_1\|^2}\boldsymbol{v}_1 - \frac{\boldsymbol{w}_3\cdotp\boldsymbol{v}_2}{\|\boldsymbol{v}_2\|^2}\boldsymbol{v}_2\\ &= \begin{pmatrix} 0\\ 1\\ -1\\ 0 \end{pmatrix} -\frac{-1}{2} \begin{pmatrix} 1\\ 0\\ 1\\ 0 \end{pmatrix} -\frac{-1/2}{3/2} \begin{pmatrix} -1/2\\ 0\\ 1/2\\ 1\end{pmatrix}\\ &= \begin{pmatrix} 1/3\\ 1\\ -1/3\\ 1/3 \end{pmatrix}\,. \end{aligned}\] Remarquons que \(\mathcal{B}'=(\boldsymbol{v}_1,\boldsymbol{v}_2,\boldsymbol{v}_3)\) est bien orthogonale puisque, par construction, \[ \boldsymbol{v}_1\cdotp\boldsymbol{v}_2 =\boldsymbol{v}_1\cdotp\boldsymbol{v}_3 =\boldsymbol{v}_2\cdotp\boldsymbol{v}_3=0\,. \]

Dans ce dernier exemple, on aurait pu remarquer dès le début que \(\boldsymbol{w}_2\perp\boldsymbol{w}_3\), et donc obtenir une base orthogonale \((\boldsymbol{v}_1',\boldsymbol{v}_2',\boldsymbol{v}_3')\), en gardant deux vecteurs inchangés, et en ne modifiant que \(\boldsymbol{w}_1\): \[\begin{aligned} \boldsymbol{v}_2'&:=\boldsymbol{w}_2\,,\\ \boldsymbol{v}_3'&:=\boldsymbol{w}_3\,,\\ \boldsymbol{v}_1'&:= \boldsymbol{w}_1 -\frac{\boldsymbol{w}_1\cdotp\boldsymbol{v}_2'}{\|\boldsymbol{v}_2'\|^2}\boldsymbol{v}_2' -\frac{\boldsymbol{w}_1\cdotp\boldsymbol{v}_3'}{\|\boldsymbol{v}_3'\|^2}\boldsymbol{v}_3'\,. \end{aligned}\] Donc en général, il y a plusieurs façons d'orthogonaliser une base, mais en général, lorsqu'on implémente le procédé de Gram-Schmidt, la convention est de modifier les vecteurs dans l'ordre donné par la base de départ.