Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Décomposition QR
Résumé
En algèbre linéaire, la décomposition QR (appelée aussi, factorisation QR ou décomposition QU) d'une matrice A est une décomposition de la forme où Q est une matrice orthogonale (QQ=I), et R 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 AX = Y peuvent alors s'écrire : QRX = Y ou RX = QY.
Ceci permettra une résolution rapide du système sans avoir à calculer la matrice inverse de A.
Il est possible de calculer une décomposition RQ d'une matrice, ou même des décompositions QL et LQ, où la matrice L est triangulaire inférieure.
Il existe plusieurs méthodes pour réaliser cette décomposition :
la méthode de Householder où Q est obtenue par produits successifs de matrices orthogonales élémentaires
la méthode de où Q 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.
Soient x un vecteur colonne arbitraire de dimension m et α = ± x, où || || désigne la norme euclidienne. Pour des raisons de stabilité du calcul, α doit de plus être du signe opposé au premier élément de x.
Soit e1 le vecteur (1, 0, ..., 0)T, et définissons, si x n'est pas colinéaire à e1 :
Q1 est la matrice de Householder ou matrice orthogonale élémentaire et
(Si x est colinéaire à e1, on a le même résultat en prenant pour Q la matrice identité.)
On peut utiliser ces propriétés pour transformer une matrice A de dimension m×n en une matrice triangulaire supérieure. Tout d'abord, on multiplie A par la matrice de Householder Q1 en ayant pris le soin de choisir pour x la première colonne de A. Le résultat est une matrice QA avec des zéros dans la première colonne excepté du premier élément qui vaudra α.
Ceci doit être réitéré pour A' qui va être multipliée par Q’2 (Q’2 est plus petite que Q1).
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.