Décomposition QR
Modèle:Sources à lier {{#invoke:Bandeau|ébauche}} En algèbre linéaire, la décomposition QR (appelée aussi, factorisation QR ou décomposition QU) d'une matrice Modèle:Mvar est une décomposition de la formeModèle:Centrer où Modèle:Mvar est une matrice orthogonale (Modèle:Math), et Modèle:Mvar une matrice triangulaire supérieure.
Ce type de décomposition est souvent utilisé pour le calcul de solutions de systèmes linéaires non carrés, notamment pour déterminer la pseudo-inverse d'une matrice.
En effet, les systèmes linéaires Modèle:Mvar peuvent alors s'écrire : Modèle:Math ou Modèle:Math.
Ceci permettra une résolution rapide du système sans avoir à calculer la matrice inverse de Modèle:Mvar.
Extensions
Il est possible de calculer une décomposition RQ d'une matrice, ou même des décompositions QL et LQ, où la matrice Modèle:Mvar est triangulaire inférieure.
Méthodes
Il existe plusieurs méthodes pour réaliser cette décomposition :
- la méthode de Householder où Modèle:Mvar est obtenue par produits successifs de matrices orthogonales élémentaires
- la méthode de Modèle:Lien où Modèle:Mvar est obtenue par produits successifs de matrices de rotation plane
- la méthode de Gram-Schmidt
Chacune d'entre elles a ses avantages et ses inconvénients. La décomposition QR n'étant pas unique, les différentes méthodes produiront des résultats différents.
Méthode de Householder
Soient Modèle:Math un vecteur colonne arbitraire de dimension m et Modèle:Math, où || || désigne la norme euclidienne. Pour des raisons de stabilité du calcul, Modèle:Math doit de plus être du signe opposé au premier élément de Modèle:Math.
Soit Modèle:Math le vecteur (1, 0, ..., 0)T, et définissons, si Modèle:Math n'est pas colinéaire à e1 :
- <math>\mathbf{u} = \mathbf{x} - \alpha\mathbf{e}_1,</math>
- <math>\mathbf{v} = {\mathbf{u}\over||\mathbf{u}||},</math>
- <math>Q_1 = I - 2 \mathbf{v}\mathbf{v}^T.</math>
- Modèle:Mvar1 est la matrice de Householder ou matrice orthogonale élémentaire et
- <math>Q_1x = (\alpha\ , 0, \cdots, 0)^T.</math>
(Si Modèle:Math est colinéaire à Modèle:Math, on a le même résultat en prenant pour Modèle:Mvar la matrice identité.)
On peut utiliser ces propriétés pour transformer une matrice Modèle:Mvar de dimension m×n en une matrice triangulaire supérieure. Tout d'abord, on multiplie Modèle:Mvar par la matrice de Householder Modèle:Math en ayant pris le soin de choisir pour x la première colonne de Modèle:Mvar. Le résultat est une matrice Modèle:Mvar avec des zéros dans la première colonne excepté du premier élément qui vaudra α.
- <math>Q_1A = \begin{pmatrix}
\alpha_1&\star&\dots&\star\\
0 & & & \\
\vdots & & A' & \\
0 & & & \end{pmatrix}</math>
Ceci doit être réitéré pour Modèle:Mvar qui va être multipliée par Modèle:Math (Modèle:Math est plus petite que Modèle:Math). Si toutefois, on souhaite utiliser Modèle:Math plutôt que Modèle:Mvar, il faut remplir la matrice de Householder avec des 1 dans le coin supérieur gauche :
- <math>Q_k = \begin{pmatrix}
I_{k-1} & 0\\
0 & Q_k'\end{pmatrix}</math>
Après Modèle:Mvar itérations, Modèle:Math,
- <math> R = Q_t \cdots Q_2Q_1A</math>
est une matrice triangulaire supérieure. Si Modèle:Math alors Modèle:Math est la décomposition QR de Modèle:Mvar. De plus, par construction les matrices Modèle:Mvar sont non seulement orthogonales mais aussi symétriques, donc Modèle:Math.
Exemple
Calculons la décomposition QR de
- <math>A = \begin{pmatrix}
12 & -51 & 4 \\ 6 & 167 & -68 \\ -4 & 24 & -41 \end{pmatrix}</math>
On choisit donc le vecteur Modèle:Math. On a donc Modèle:Math. Ce qui conduit à écrire Modèle:Math.
Le calcul amène à Modèle:Math et <math>v = {1 \over 14^Modèle:1 \over 2 } (-1, 3, -2)^T</math>. La première matrice de Householder vaut
- <math>\begin{align}Q_1&= I - {2 \over 14} \begin{pmatrix} -1 \\ 3 \\ -2 \end{pmatrix}\begin{pmatrix} -1 & 3 & -2 \end{pmatrix}\\
&=I - {1 \over 7}\begin{pmatrix} 1 & -3 & 2 \\ -3 & 9 & -6 \\ 2 & -6 & 4 \end{pmatrix} =\begin{pmatrix} 6/7 & 3/7 & -2/7 \\ 3/7 &-2/7 & 6/7 \\ -2/7 & 6/7 & 3/7 \\ \end{pmatrix}.\end{align}</math>
On observe alors que
- <math>Q_1A = \begin{pmatrix}
14 & 21 & -14 \\ 0 & -49 & -14 \\ 0 & 168 & -77 \end{pmatrix}.</math>
ce qui était l'objectif désiré : on a bien maintenant sous la diagonale uniquement des zéros dans la Modèle:1re.
Pour réitérer le processus, on prend la sous-matrice principale
- <math>A' = M_{11} = \begin{pmatrix}
-49 & -14 \\ 168 & -77 \end{pmatrix}</math>
Par la même méthode, on obtient
- <math>\alpha_2=\sqrt{(-49)^2+168^2}=175,\quad u_2=(-224,168)^T,\quad v_2=(-4/5,3/5)^T,\quad Q'_2=\begin{pmatrix}-7/25&24/25\\24/25&7/25\end{pmatrix}.</math>
La Modèle:2e de Householder est donc
- <math>Q_2 = \begin{pmatrix}
1 & 0 & 0 \\ 0 & -7/25 & 24/25 \\ 0 & 24/25 & 7/25 \end{pmatrix}.</math>
Finalement, on obtient
- <math>Q=Q_1Q_2=\begin{pmatrix}
6/7 & -69/175 & 58/175\\ 3/7 & 158/175 & -6/175 \\ -2/7 & 6/35 & 33/35 \end{pmatrix} </math>
- <math>R=Q_2Q_1A=Q^T A=\begin{pmatrix}
14 & 21 & -14 \\ 0 & 175 & -70 \\ 0 & 0 & -35 \end{pmatrix}.</math>
La matrice Modèle:Mvar est orthogonale et Modèle:Mvar est triangulaire supérieure, par conséquent, on obtient la décomposition Modèle:Math.
Coût et avantages
Le coût de cette méthode pour une matrice n×n est en : Modèle:Math Ce coût est relativement élevé (la méthode de Cholesky, pour les matrices symétriques définies positives est en Modèle:Math). Cependant, la méthode de Householder présente l'avantage considérable d'être beaucoup plus stable numériquement, en limitant les divisions par des nombres petits. La méthode de Givens, malgré un coût encore supérieur à celui-ci, offrira encore davantage de stabilité.
Méthode de Schmidt
On considère le procédé de Gram-Schmidt appliqué aux colonnes de la matrice <math>A=[\mathbf{a}_1, \cdots, \mathbf{a}_n]</math>, muni du produit scalaire <math>\langle \mathbf{v}, \mathbf{w}\rangle = \mathbf{v}^\top \mathbf{w}</math> (ou <math>\langle \mathbf{v}, \mathbf{w}\rangle = \mathbf{v}^{\dagger} \mathbf{w}</math> pour le cas complexe). L'algorithme présenté ci-dessous convient à une matrice de rang <math>n</math>. Pour des matrices de rang inférieur, il est à adapter à chaque fois que le vecteur <math>\mathbf{u}_i</math>obtenu est nul.
On définit la projection :
- <math>\Pi_{\mathbf{e}} \mathbf{a}
= \frac{\langle \mathbf{e},\mathbf{a}\rangle}{\langle \mathbf{e},\mathbf{e}\rangle}\mathbf{e} </math>
puis les vecteurs :
- <math>
\begin{align}
\mathbf{u}_1 &= \mathbf{a}_1,
& \mathbf{e}_1 &= {\mathbf{u}_1 \over \|\mathbf{u}_1\|} \\
\mathbf{u}_2 &= \mathbf{a}_2-\Pi_{\mathbf{e}_1}\,\mathbf{a}_2,
& \mathbf{e}_2 &= {\mathbf{u}_2 \over \|\mathbf{u}_2\|} \\
\mathbf{u}_3 &= \mathbf{a}_3-\Pi_{\mathbf{e}_1}\,\mathbf{a}_3-\Pi_{\mathbf{e}_2}\,\mathbf{a}_3,
& \mathbf{e}_3 &= {\mathbf{u}_3 \over \|\mathbf{u}_3\|} \\
& \vdots &&\vdots \\
\mathbf{u}_k &= \mathbf{a}_k-\sum_{j=1}^{k-1}\Pi_{\mathbf{e}_j}\,\mathbf{a}_k,
&\mathbf{e}_k &= {\mathbf{u}_k\over\|\mathbf{u}_k\|}.
\end{align} </math>
On réarrange ensuite les équations de sorte que les Modèle:Mvar soient à gauche, en utilisant le fait que les Modèle:Math sont des vecteurs unitaires :
- <math>
\begin{align}
\mathbf{a}_1 &= \langle\mathbf{e}_1,\mathbf{a}_1 \rangle \mathbf{e}_1 \\
\mathbf{a}_2 &= \langle\mathbf{e}_1,\mathbf{a}_2 \rangle \mathbf{e}_1
+ \langle\mathbf{e}_2,\mathbf{a}_2 \rangle \mathbf{e}_2 \\
\mathbf{a}_3 &= \langle\mathbf{e}_1,\mathbf{a}_3 \rangle \mathbf{e}_1
+ \langle\mathbf{e}_2,\mathbf{a}_3 \rangle \mathbf{e}_2
+ \langle\mathbf{e}_3,\mathbf{a}_3 \rangle \mathbf{e}_3 \\
&\vdots \\
\mathbf{a}_k &= \sum_{j=1}^{k} \langle \mathbf{e}_j, \mathbf{a}_k \rangle \mathbf{e}_j
\end{align} </math>
où <math>\langle\mathbf{e}_i,\mathbf{a}_i \rangle = \|\mathbf{u}_i\|</math>. Ceci s'écrit matriciellement :
- <math> A = Q R </math>
avec
- <math>Q = \left[ \mathbf{e}_1, \cdots, \mathbf{e}_n\right] \qquad \text{et} \qquad
R = \begin{pmatrix} \langle\mathbf{e}_1,\mathbf{a}_1\rangle & \langle\mathbf{e}_1,\mathbf{a}_2\rangle & \langle\mathbf{e}_1,\mathbf{a}_3\rangle & \ldots \\ 0 & \langle\mathbf{e}_2,\mathbf{a}_2\rangle & \langle\mathbf{e}_2,\mathbf{a}_3\rangle & \ldots \\ 0 & 0 & \langle\mathbf{e}_3,\mathbf{a}_3\rangle & \ldots \\ \vdots & \vdots & \vdots & \ddots \end{pmatrix}.</math>
Exemple
On reprend la matrice de l'exemple
- <math>A =
\begin{pmatrix} 12 & -51 & 4 \\ 6 & 167 & -68 \\ -4 & 24 & -41 \end{pmatrix} .</math>
Rappelons qu'une matrice orthogonale Modèle:Mvar vérifie
- <math>
\begin{matrix}
Q^T\,Q = I.
\end{matrix} </math>
On peut alors calculer Modèle:Mvar par les moyens de Gram-Schmidt comme suit :
- <math>
U = \begin{pmatrix} \mathbf u_1 & \mathbf u_2 & \mathbf u_3 \end{pmatrix} = \begin{pmatrix} 12 & -69 & -58/5 \\ 6 & 158 & 6/5 \\ -4 & 30 & -33 \end{pmatrix}; </math>
- <math>
Q = \begin{pmatrix} \frac{\mathbf u_1}{\|\mathbf u_1\|} & \frac{\mathbf u_2}{\|\mathbf u_2\|} & \frac{\mathbf u_3}{\|\mathbf u_3\|} \end{pmatrix} = \begin{pmatrix}
6/7 & -69/175 & -58/175 \\
3/7 & 158/175 & 6/175 \\
-2/7 & 6/35 & -33/35
\end{pmatrix}. </math>
Dans ce cas, on a :
- <math>
\begin{matrix}
Q^{T} A = Q^{T}Q\,R = R;
\end{matrix} </math>
- <math display="inline">
\begin{matrix}
R = Q^{T}A =
\end{matrix} \begin{pmatrix}
14 & 21 & -14 \\ 0 & 175 & -70 \\ 0 & 0 & 35
\end{pmatrix}. </math>
Relation avec la décomposition RQ
La décomposition RQ transforme une matrice Modèle:Mvar en produit d'une matrice triangulaire supérieure Modèle:Mvar et une matrice orthogonale Modèle:Mvar. La seule différence avec la décomposition QR est l'ordre de ces matrices.
La décomposition QR est l'application du procédé de Gram-Schmidt sur les colonnes de Modèle:Mvar, en partant de la première colonne ; la décomposition RQ est l'application du procédé de Gram-Schmidt sur les lignes de Modèle:Mvar, en partant de la dernière ligne.
Méthode de Givens
Dans cette méthode, la matrice Modèle:Mvar utilise des Modèle:Lien. Chaque rotation annule un élément de la partie triangulaire inférieure stricte de la matrice, construisant la matrice Modèle:Mvar, tandis que la concaténation des rotations engendre la matrice Modèle:Mvar.
Dans la pratique, les rotations de Givens ne sont pas effectivement assurées par la construction d'une matrice pleine et une multiplication matricielle. Une procédure de rotation de Givens est utilisé à la place qui est l'équivalent de la multiplication par une matrice de Givens creuse, sans efforts supplémentaires de la manipulation des éléments non nuls. La procédure de rotation de Givens est utile dans des situations où seul un nombre relativement restreint hors éléments diagonaux doivent être remis à zéro, et est plus facilement parallélisée que les transformations de Householder.
Exemple
Reprenons le même exemple
- <math>A = \begin{pmatrix}
12 & -51 & 4 \\ 6 & 167 & -68 \\ -4 & 24 & -41 \end{pmatrix}.</math>
On doit d'abord construire une matrice de rotation qui annulera l'élément le plus bas de la colonne de gauche, Modèle:Math, qu'on construit par une méthode de rotation de Givens. On appelle cette matrice Modèle:Math. On va d'abord faire une rotation du vecteur (6,-4), pour le ramener sur l'axe X. Ce vecteur forme un angle Modèle:Math. La matrice Modèle:Math est donc donnée par :
- <math>G_1 = \begin{pmatrix}
1 & 0 & 0 \\ 0 & \cos(\theta) & -\sin(\theta) \\ 0 & \sin(\theta) & \cos(\theta) \end{pmatrix}</math>
- <math>\approx \begin{pmatrix}
1 & 0 & 0 \\ 0 & 0{,}83205 & -0{,}55470 \\ 0 & 0{,}55470 & 0{,}83205 \end{pmatrix}.</math>
Le produit Modèle:Math annule le coefficient Modèle:Math :
- <math>G_1A \approx \begin{pmatrix}
12 & -51 & 4 \\ 7{,}21110 & 125{,}6396 & -33{,}83671 \\ 0 & 112{,}6041 & -71{,}83368 \end{pmatrix}.</math>
Par suite, on construit des matrices de Givens Modèle:Math et Modèle:Math, qui vont respectivement annuler Modèle:Math et Modèle:Math, engendrant la matrice Modèle:Mvar. La matrice orthogonale Modèle:Mvar est formée de la concaténation de toutes les matrices de Givens créées Modèle:Math.
Applications
Résolution d'un système d'équations linéaires
Cette factorisation matricielle permet de résoudre des systèmes d'équations linéaires où les coefficients des inconnues sont les mêmes, mais avec plusieurs seconds membres différents. Soit à déterminer le vecteur Modèle:Formule d'inconnues associé au second membre Modèle:Formule :
- <math>A x= b</math>.
Ce problème est donc équivalent à la résolution de
- <math> QR x= b.</math>
que l'on peut mettre sous la forme :
- <math> Rx= Q^{-1}b = Q^Tb</math>.
On retrouve ainsi une résolution similaire à celle de la décomposition LU, où l'étape de résolution par descente est remplacée par une opération de transposition, et seule reste l'étape de remontée.
Décomposition en valeurs singulières d'une matrice
La décomposition QR est une méthode de calcul de la décomposition en valeurs singulières d'une matrice, en l'appliquant deux fois : une première fois sur Modèle:Mvar pour obtenir la matrice unitaire des vecteurs de sortie (Modèle:Math), puis une deuxième fois sur Modèle:Math pour la matrice unitaire des vecteurs d'entrée (Modèle:Math).
Calcul d'un déterminant
Si Modèle:Formule est sous forme Modèle:Formule, son déterminant se calcule facilement :
- <math>\det(A)=\det(Q)\det(R) = (\pm 1)\times \prod r_{ii}.</math>
Le déterminant de Modèle:Mvar vaut Modèle:Math selon que la base de ses vecteurs colonne est directe ou non, et le déterminant de Modèle:Mvar est égale au produit de ses coefficients diagonaux.
