Décomposition QR
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).