10.6 Décomposition QR

Soit une matrice \(\mathbf{A} \in \mathbb{R}^{m\times n}\) de rang \(n.\) (Alors \(m \geq n\).) En utilisant le procédé de Gram-Schmidt avec le produit scalaire usuel, nous obtenons une base orthonormée \(\{ \mathbf{q}^{(1)}, \ldots, \mathbf{q}^{(n)}\}\) de \({\operatorname{Col}({\mathbf{A}})}.\) Cette base est telle que \(\operatorname{Vect}\left ({\{ \mathbf{q}^{(1)}, \ldots, \mathbf{q}^{(i)}\}} \right) = \operatorname{Vect}\left ({\{ \mathbf{a}^{(1)}, \ldots, \mathbf{a}^{(i)}\}} \right)\), pour chaque \(i = 1,\ldots,n,\) où \(\mathbf{a}^{(i)}\) est la \(i\)-ième colonne de \(\mathbf{A}\). Ainsi, pour chaque \(i = 1,\ldots,n\), nous avons \[\mathbf{a}^{(i)} = \langle { \mathbf{a}^{(i)} },{ \mathbf{q}^{(1)} } \rangle \mathbf{q}^{(1)}+\cdots+ \langle { \mathbf{a}^{(i)} },{ \mathbf{q}^{(i)} } \rangle \mathbf{q}^{(i)}.\]

Soit \(\mathbf{R}' \in \mathbb{R}^{n \times n}\) la matrice dont les éléments \((i,j)\) sont donnés par \[r_{ij} = \begin{cases} \langle { \mathbf{a}^{(j)} },{ \mathbf{q}^{(i)} } \rangle & \text{si } i \leq j, \\ 0 & \text{autrement.} \end{cases}\] Notons que \(\mathbf{R}'\) est une matrice triangulaire supérieure, et que \[\begin{bmatrix} \mathbf{q}^{(1)} & \ldots & \mathbf{q}^{(n)}\end{bmatrix} \mathbf{R}' = \mathbf{A}.\]

On construit \(\mathbf{q}^{(n+1)}, \ldots, \mathbf{q}^{(m)}\) tels que \(\{ \mathbf{q}^{(1)}, \ldots, \mathbf{q}^{(n)}\}\) est une base orthonormée de \(\mathbb{R}^m.\) Soit \(\mathbf{Q}\) la matrice carrée \(\begin{bmatrix} \mathbf{q}^{(1)} & \ldots & \mathbf{q}^{(m)}\end{bmatrix}.\) Alors \[\mathbf{A} = \mathbf{Q} \mathbf{R},\] où \(\mathbf{R} = \begin{bmatrix} \mathbf{R}' \\ \mathbf{0}_{(m-n)\times n}\end{bmatrix}.\) Ce produit est une décomposition QR de \(\mathbf{A}\).

Exemple 10.6 Calculons une décomposition QR de \(\mathbf{A} = \begin{bmatrix} -4 & 5 & 1 \\ -2 & 7 & -1 \\ 4 & 4 & 2 \end{bmatrix}.\)

En appliquant le procédé de Gram-Schmidt aux colonnes de la matrice \(\mathbf{A},\) on obtient la matrice orthogonale \[\mathbf{Q} = \begin{bmatrix} -\frac{2}{3} & \frac{1}{3} & \frac{2}{3} \\ -\frac{1}{3} & \frac{2}{3} & -\frac{2}{3} \\ \frac{2}{3} & \frac{2}{3} & \frac{1}{3} \\ \end{bmatrix},\] d’où \[\mathbf{R} = \mathbf{Q}^\mathsf{T}\mathbf{A} = \begin{bmatrix} 6 & -3 & 1 \\ 0 & 9 & 1 \\ 0 & 0 & 2 \end{bmatrix},\] et \(\mathbf{A} = \mathbf{Q}\mathbf{R}\).

En général, on peut décomposer chaque matrice \(\mathbf{A} \in \mathbb{R}^{m\times n}\) à l’aide d’un produit matriciel \(\mathbf{Q}\mathbf{R},\) où \(\mathbf{Q} \in \mathbb{R}^{m\times m}\) est orthogonale et \(\mathbf{R} \in \mathbb{R}^{m\times n}\) est triangulaire supérieure. Notons qu’une telle décomposition existe sans restriction sur la dimension ou le rang de \(\mathbf{A}\). Nous laissons la démonstration de ce résultat en exercice. Considérons tout de même l’exemple suivant.

Exemple 10.7 Obtenons une décomposition QR pour \(\mathbf{A} = \begin{bmatrix} 1 & 2 & 0 & 1 \\ -1 & 0 & 1 & 0 \\ -1 & -2 & 0 & -1 \\ 1 & 0 & -1 & -2 \end{bmatrix}.\) Notons que \(\mathbf{A}\) n’a pas de plein rang puisque sa forme échelonnée réduite est \(\begin{bmatrix} 1 & 0 & -1 & 0 \\ 0 & 1 & \frac{1}{2} & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 \end{bmatrix}.\) On en déduit que la première, la deuxième et la quatrième colonne de \(\mathbf{A}\) sont linéairement indépendantes. De plus, la troisième colonne de \(\mathbf{A}\) est une combinaison linéaire des deux premières colonnes : \(\mathbf{A}_3 = -\mathbf{A}_1 + \frac{1}{2} \mathbf{A}_2.\)

En appliquant le procédé de Gram-Schmidt à \(\mathbf{A}_1,\) \(\mathbf{A}_2,\) et \(\mathbf{A}_4,\) on obtient \(\begin{bmatrix} \frac{1}{2} \\ -\frac{1}{2} \\ -\frac{1}{2} \\ \frac{1}{2} \\ \end{bmatrix},\) \(\begin{bmatrix} \frac{1}{2} \\ \frac{1}{2} \\ -\frac{1}{2} \\ -\frac{1}{2} \end{bmatrix},\) et \(\begin{bmatrix} 0 \\ -\frac{1}{\sqrt{2}} \\ 0 \\ \frac{1}{\sqrt{2}} \end{bmatrix}.\) On obtient une base orthonormée de \(\mathbb{R}^4\) en ajoutant \(\begin{bmatrix} \frac{1}{\sqrt{2}} \\ 0 \\ \frac{1}{\sqrt{2}} \\ 0 \end{bmatrix}\) à ces vecteurs.

Ainsi, \[\begin{align*} \begin{bmatrix} \mathbf{A}_1 & \mathbf{A}_2 & \mathbf{A}_4 \end{bmatrix} & = \begin{bmatrix} 1 & 2 & 1 \\ -1 & 0 & 0 \\ -1 & -2 & -1 \\ 1 & 0 & -2 \end{bmatrix} \\ & = \begin{bmatrix} \frac{1}{2} & \frac{1}{2} & 0 & \frac{1}{\sqrt{2}} \\ -\frac{1}{2} & \frac{1}{2} & -\frac{1}{\sqrt{2}} & 0 \\ -\frac{1}{2} & -\frac{1}{2} & 0 & \frac{1}{\sqrt{2}} \\ \frac{1}{2} & -\frac{1}{2} & -\frac{1}{\sqrt{2}} & 0 \end{bmatrix} \begin{bmatrix} 2 & 2 & 0 \\ 0 & 2 & 2 \\ 0 & 0 & \sqrt{2} \\ 0 & 0 & 0 \end{bmatrix}. \end{align*}\] Ainsi, \[\begin{align*} \mathbf{A}_3 & = -\mathbf{A}_1 + \frac{1}{2} \mathbf{A}_2. \\ & = \begin{bmatrix} \mathbf{A}_1 & \mathbf{A}_2 & \mathbf{A}_4 \end{bmatrix} \begin{bmatrix} -1 \\ \frac{1}{2} \\ 0 \end{bmatrix} \\ & = \begin{bmatrix} \frac{1}{2} & \frac{1}{2} & 0 & \frac{1}{\sqrt{2}} \\ -\frac{1}{2} & \frac{1}{2} & -\frac{1}{\sqrt{2}} & 0 \\ -\frac{1}{2} & -\frac{1}{2} & 0 & \frac{1}{\sqrt{2}} \\ \frac{1}{2} & -\frac{1}{2} & -\frac{1}{\sqrt{2}} & 0 \end{bmatrix} \begin{bmatrix} 2 & 2 & 0\\ 0 & 2 & 2\\ 0 & 0 & \sqrt{2} \\ 0 & 0 & 0 \end{bmatrix} \begin{bmatrix} -1 \\ \frac{1}{2} \\ 0 \end{bmatrix} \\ & = \begin{bmatrix} \frac{1}{2} & \frac{1}{2} & 0 & \frac{1}{\sqrt{2}} \\ -\frac{1}{2} & \frac{1}{2} & -\frac{1}{\sqrt{2}} & 0 \\ -\frac{1}{2} & -\frac{1}{2} & 0 & \frac{1}{\sqrt{2}} \\ \frac{1}{2} & -\frac{1}{2} & -\frac{1}{\sqrt{2}} & 0 \end{bmatrix} \begin{bmatrix} -1 \\ 1 \\ 0 \\ 0 \end{bmatrix}, \end{align*}\] d’où \[\mathbf{A} = \begin{bmatrix} \frac{1}{2} & \frac{1}{2} & 0 & \frac{1}{\sqrt{2}} \\ -\frac{1}{2} & \frac{1}{2} & -\frac{1}{\sqrt{2}} & 0 \\ -\frac{1}{2} & -\frac{1}{2} & 0 & \frac{1}{\sqrt{2}} \\ \frac{1}{2} & -\frac{1}{2} & -\frac{1}{\sqrt{2}} & 0 \end{bmatrix} \begin{bmatrix} 2 & 2 & -1 & 0 \\ 0 & 2 & 1 & 2\\ 0 & 0 & 0 & \sqrt{2} \\ 0 & 0 & 0 & 0 \end{bmatrix},\] ce qui donne une décomposition QR de \(\mathbf{A}.\)

Remarque. Même si, en théorie, la décomposition QR peut être obtenue en utilisant le procédé de Gram-Schmidt, les calculs numériques qui sous-tendent une telle décomposition sont assez compliqués. Pour plus d’informations, consulter Golub et Van Loan (1996).

Exercices

1. Soit \(\mathbf{A} = \begin{bmatrix} 1 & 2 \\ 1 & 1 \end{bmatrix}.\) Obtenez une décomposition QR de \(\mathbf{A}.\)

2. Démontrez que chaque matrice \(\mathbf{A} \in \mathbb{R}^{m\times n}\), peut être décomposée selon le produit matriciel \(\mathbf{Q}\mathbf{R},\) où \(\mathbf{Q} \in \mathbb{R}^{m\times m}\) est une matrice orthogonale et \(\mathbf{R} \in \mathbb{R}^{m\times n}\) est une matrice triangulaire supérieure.

Solutions

1. En appliquant le procédé de Gram-Schmidt aux colonnes de \(\mathbf{A},\) nous obtenons la matrice orthogonale \[\mathbf{Q} = \begin{bmatrix} \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \\ \frac{1}{\sqrt{2}} & -\frac{1}{\sqrt{2}} \end{bmatrix}.\] En prenant \[\mathbf{R} = \mathbf{Q}^\mathsf{T}\mathbf{A} = \begin{bmatrix} \sqrt{2} & \frac{3}{\sqrt{2}} \\ 0 & \frac{1}{\sqrt{2}} \end{bmatrix},\] on obtient \(\mathbf{A} = \mathbf{Q}\mathbf{R},\) une décomposition QR de \(\mathbf{A}.\)

2. Indice : Appliquez le procédé de Gram-Schmidt aux colonnes de \(\mathbf{A}\) qui correspondent aux pivots de la forme échelonnée réduite de \(\mathbf{A}.\) Notez que les colonnes libres peuvent être exprimées par une combinaison linéaire des colonnes précédentes.

Bibliographie

Golub, G.H., et C.F. Van Loan. 1996. Matrix Computations. Johns Hopkins Studies in the Mathematical Sciences. Johns Hopkins University Press.