Décomposition QR
Source: Wikipédia sous licence CC-BY-SA 3.0.
La liste des auteurs de cet article est disponible ici.

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 = QR

Q est une matrice orthogonale (QQT = I), et R une matrice triangulaire (En algèbre linéaire, les matrices triangulaires sont des matrices carrées dont une partie triangulaire des valeurs, délimitée par la diagonale principale, est nulle.) 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 plane est un outil pour le travail du bois. Elle est composée d'une lame semblable à celle d'un couteau, munie de deux poignées, à chaque extrémité de la lame....)
  • la méthode de Schmidt

Chacune d'entre elles a ses avantages et ses inconvénients. (La décomposition QR (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) n'étant pas unique, les différentes méthodes produiront des résultats différents).

Méthode de Householder

Soit x un vecteur (En mathématiques, un vecteur est un élément d'un espace vectoriel, ce qui permet d'effectuer des opérations d'addition et de multiplication par un scalaire. Un n-uplet peut constituer un exemple de vecteur,...) colonne arbitraire de dimension (Dans le sens commun, la notion de dimension renvoie à la taille ; les dimensions d'une pièce sont sa longueur, sa largeur et sa profondeur/son épaisseur, ou bien son diamètre si c'est une pièce de révolution.) m et de longueur (La longueur d’un objet est la distance entre ses deux extrémités les plus éloignées. Lorsque l’objet est filiforme ou en forme de lacet, sa...) |α| (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 (Le tout compris comme ensemble de ce qui existe est souvent interprété comme le monde ou l'univers.) 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 (Une norme, du latin norma (« équerre, règle ») désigne un état habituellement répandu ou moyen considéré le plus souvent comme une...) || ||2 plutôt que la longueur.

Soit e1 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 (Une matrice carrée A (n lignes, n colonnes) à coefficients réels est dite orthogonale si elle vérifie :) é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 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 α.

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'2 (Q'2 est plus petite que Q1). Si toutefois, vous souhaiteriez utiliser Q1A 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 = min(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 = QR est la décomposition (En biologie, la décomposition est le processus par lequel des corps organisés, qu'ils soient d'origine animale ou végétale dès l'instant qu'ils sont privés de vie, dégénèrent sous l'action de facteurs...) QR de A.

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 a1 = (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 (On appelle diagonale d'un polygone tout segment reliant deux sommets non consécutifs (non reliés par un côté). Un polygone à n côtés possède diagonales.) 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.

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éfinies 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 davantage de stabilité.

Page générée en 0.231 seconde(s) - site hébergé chez Amen
Ce site fait l'objet d'une déclaration à la CNIL sous le numéro de dossier 1037632
Ce site est édité par Techno-Science.net - A propos - Informations légales
Partenaire: HD-Numérique