En algèbre linéaire, la décomposition QR (appelée aussi, factorisation QR ou décomposition QU) d'une matrice est une décomposition de la forme où est une matrice orthogonale (), et 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 peuvent alors s'écrire : ou .
Ceci permettra une résolution rapide du système sans avoir à calculer la matrice inverse de .
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 est triangulaire inférieure.
Origine de l'appellation Le R dans QR vient de l'anglais "Right triangular matrix" désignant une matrice triangulaire supérieure. L'explication retenue communément pour la lettre Q est le fait qu'elle précède le R dans l'alphabet.
Méthodes
Il existe plusieurs méthodes pour réaliser cette décomposition : la méthode de Householder où est obtenue par produits successifs de matrices orthogonales élémentaires la méthode de où 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 un vecteur colonne arbitraire de dimension m et , où || || désigne la norme euclidienne. Pour des raisons de stabilité du calcul, lors de la première itération (uniquement), doit de plus être du signe opposé au premier élément de .
Soit le vecteur (1, 0, ..., 0)T, et définissons, si n'est pas colinéaire à e1 :
1 est la matrice de Householder ou matrice orthogonale élémentaire et
(Si est colinéaire à , on a le même résultat en prenant pour la matrice identité.)
On peut utiliser ces propriétés pour transformer une matrice de dimension m×n en une matrice triangulaire supérieure. Tout d'abord, on multiplie par la matrice de Householder en ayant pris le soin de choisir pour x la première colonne de . Le résultat est une matrice avec des zéros dans la première colonne excepté du premier élément qui vaudra α.
Ceci doit être réitéré pour qui va être multipliée par ( est plus petite que ). Si toutefois, on souhaite utiliser plutôt que , il faut remplir la matrice de Householder avec des 1 dans le coin supérieur gauche :
Après itérations, ,
est une matrice triangulaire supérieure. Si alors est la décomposition QR de . De plus, par construction les matrices sont non seulement orthogonales mais aussi symétriques, donc .
Exemple
Calculons la décomposition QR de
On choisit donc le vecteur . On a donc . Ce qui conduit à écrire .
Le calcul amène à et . La première matrice de Householder vaut
On observe alors que
ce qui était l'objectif désiré : on a bien maintenant sous la diagonale uniquement des zéros dans la .
Pour réitérer le processus, on prend la sous-matrice principale
Par la même méthode, on obtient
La de Householder est donc
Finalement, on obtient
La matrice est orthogonale et est triangulaire supérieure, par conséquent, on obtient la décomposition .
Coût et avantages
Le coût de cette méthode pour une matrice n×n est en : Ce coût est relativement élevé (la méthode de Cholesky, pour les matrices symétriques définies positives est en ). 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 , muni du produit scalaire (ou pour le cas complexe). L'algorithme présenté ci-dessous convient à une matrice de rang . Pour des matrices de rang inférieur, il est à adapter à chaque fois que le vecteur obtenu est nul.
On définit la projection :
puis les vecteurs :
On réarrange ensuite les équations de sorte que les soient à gauche, en utilisant le fait que les sont des vecteurs unitaires :
où . Ceci s'écrit matriciellement :
avec
Exemple On reprend la matrice de l'exemple
Rappelons qu'une matrice orthogonale vérifie
On peut alors calculer par les moyens de Gram-Schmidt comme suit :
Dans ce cas, on a :
Relation avec la décomposition RQ La décomposition RQ transforme une matrice en produit d'une matrice triangulaire supérieure et une matrice orthogonale . 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 , en partant de la première colonne ; la décomposition RQ est l'application du procédé de Gram-Schmidt sur les lignes de , en partant de la dernière ligne.
Méthode de Givens Dans cette méthode, la matrice utilise des . Chaque rotation annule un élément de la partie triangulaire inférieure stricte de la matrice, construisant la matrice , tandis que la concaténation des rotations engendre la matrice .
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
On doit d'abord construire une matrice de rotation qui annulera l'élément le plus bas de la colonne de gauche, , qu'on construit par une méthode de rotation de Givens. On appelle cette matrice . On va d'abord faire une rotation du vecteur (6,-4), pour le ramener sur l'axe X. Ce vecteur forme un angle . La matrice est donc donnée par :
Le produit annule le coefficient :
Par suite, on construit des matrices de Givens et , qui vont respectivement annuler et , engendrant la matrice . La matrice orthogonale est formée de la concaténation de toutes les matrices de Givens créées .
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 d'inconnues associé au second membre : . Ce problème est donc équivalent à la résolution de
que l'on peut mettre sous la forme : .
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 pour obtenir la matrice unitaire des vecteurs de sortie (), puis une deuxième fois sur pour la matrice unitaire des vecteurs d'entrée ().
Calcul d'un déterminant
Si est sous forme , son déterminant se calcule facilement :
Le déterminant de vaut selon que la base de ses vecteurs colonne est directe ou non, et le déterminant de est égale au produit de ses coefficients diagonaux.
Références
Voir aussi
Articles connexes Décomposition LU Factorisation de Cholesky Algorithme de Bartels-Stewart Algorithme QR Bibliographie
Crédit d'auteurs
Decomposition QR Catégorie:Algèbre bilinéaire