Décomposition QR

Un article de Wikipédia, l'encyclopédie libre.

Cet article est une ébauche à compléter concernant l'algèbre, vous pouvez partager vos connaissances en le modifiant.

En algèbre linéaire, la décomposition QR (appelée aussi, décomposition QU) d'une matrice $A$ est une décomposition de la forme

A = Q R

où $Q$ est une matrice orthogonale ( $Q Q T = I$ ), et $R$ une matrice triangulaire supé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 Givens où $Q$ est obtenue par produits successifs de matrices de rotation plane
la méthode de 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).

Sommaire

1 Méthode de Householder
- 1.1 Exemple
- 1.2 Coût et avantages
2 Voir aussi

[modifier] Méthode de Householder

Soit x un vecteur colonne arbitraire de dimension m et de longueur |α| (Pour des raisons de stabilité du calcul, α doit être du signe du premier élément de x et la longueur étant la somme de tout les éléments de x). Toutefois, plusieurs versions semblent exister à propos de α, ici, vous est présenté la version de l'article anglais. D'autres utilisent la norme || ||₂ plutôt que la longueur.

Soit e₁ le vecteur (1,0,...,0)^T, et || || la norme euclidienne, définissons

$\mathbf{u} = \mathbf{x} - \alpha\mathbf{e}_1,$

$\mathbf{v} = {\mathbf{u}\over||\mathbf{u}||},$

$Q = I - 2 \mathbf{v}\mathbf{v}^T.$ .

$Q$ est la matrice de Householder ou matrice orthogonale élémentaire et

$Qx = (\alpha\ , 0, \cdots, 0)^T$ .

Nous pouvons 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 Q₁ 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 α.

$Q_1A = \begin{bmatrix} \alpha_1&\star&\dots&\star\\ 0 & & & \\ \vdots & & A' & \\ 0 & & & \end{bmatrix}$

Ceci doit être réitéré pour A' qui va être multiplié par Q'₂ (Q'₂ est plus petite que Q₁). Si toutefois, vous souhaiteriez utiliser Q₁A plutôt que A', vous deviez remplir la matrice de Householder avec des 1 dans le coin supérieur gauche :

$Q_k = \begin{pmatrix} I_{k-1} & 0\\ 0 & Q_k'\end{pmatrix}$

Après $t$ itérations, $t = m i n (m - 1, n)$ ,

$R = Q_t \cdots Q_2Q_1A$

est une matrice triangulaire supérieure. Si $Q = Q_1Q_2 \cdots Q_t$ alors $A = Q R$ est la décomposition QR de $A$ .

[modifier] Exemple

Calculons la décomposition QR de

$A = \begin{pmatrix} 12 & -51 & 4 \\ 6 & 167 & -68 \\ -4 & 24 & -41 \end{pmatrix}$

On choisit donc le vecteur $a 1 = (12,6, - 4) T$ . On a donc $\| a_1 \| =\sqrt{12^2+6^2+(-4)^2}=14$ . Ce qui nous conduit à écrire $\|a_1\| e_1 = (14, 0, 0)^T$ .

Le calcul nous ammène a $u = ( - 2,6, - 4) T$ et $v = 14^{-{1 \over 2}}(-1, 3, -2)^T$ . La première matrice de Householder vaut

$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}$

Observons que:

$Q_1A = \begin{pmatrix} 14 & 21 & -14 \\ 0 & -49 & -14 \\ 0 & 168 & -77 \end{pmatrix}$

Nous avons maintenant sous la diagonale uniquement des zéros dans la 1ère colonne.

Pour réitérer le processus, on prend la sous matrice principale

$A' = M_{11} = \begin{pmatrix} -49 & -14 \\ 168 & -77 \end{pmatrix}$

Par la même méthode, on obtient la 2ème matrice de Householder

$Q_2 = \begin{pmatrix} 1 & 0 & 0 \\ 0 & -7/25 & 24/25 \\ 0 & 24/25 & 7/25 \end{pmatrix}$

Finalement, on obtient

$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}$

$R=Q^\top A=\begin{pmatrix} 14 & 21 & -14 \\ 0 & 175 & -70 \\ 0 & 0 & -35 \end{pmatrix}$

La matrice Q est orthogonale et R est triangulaire supérieure, par conséquent, on obtient la décomposition A = QR.

[modifier] Coût et avantages

Le coût de cette méthode pour une matrice n*n est en : $\frac{4}{3} \times n^3$ Ce coût est relativement élevé (la méthode de Cholesky, pour les matrices symétriques défnies positives est en $\frac{1}{3} \times n^3$ ). 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 d'avantage de stabilité.