Decomposition QR


Decomposition QR

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

A = QR

Q est une matrice orthogonale (QQT = 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).

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 tous 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 || ||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 é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_1^T Q_2^T \cdots Q_t^T alors A = QR est la décomposition QR de A.

Calculons la décomposition QR de

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

On choisit donc le vecteur (cet exemple contient beaucoup d'erreurs alors faites attention) 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 amène à 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& -271/7 & -14 \\
0 & 911/7 & -14 \\
0 & 1803/7& -77 \end{pmatrix}

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

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

A' = M_{11} = \begin{pmatrix}
911/7 & -14 \\
1803/7 & -77 \end{pmatrix}

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

Q_2 = \begin{pmatrix}
1&0&0\\
0&-((911 (-911 + \sqrt{4080730}))/(-4080730 + 911 \sqrt{4080730})) & -(( 1803 (-911 + \sqrt{4080730}))/(-4080730 + 911 \sqrt{4080730}))\\
0&-((1803 (-911 + \sqrt{4080730}))/(-4080730 + 911 \sqrt{4080730}))&  1 + 3250809/(-4080730 + 911 \sqrt{4080730})
\end{pmatrix}

Finalement, on obtient

Q=Q_1^\top Q_2^\top=\begin{pmatrix}
6/7& (873 (-911 + \sqrt{4080730}))/(
  7 (-4080730 + 911 \sqrt{4080730}))& -((
   1033 (-911 + \sqrt{4080730}))/(-4080730 + 911 \sqrt{4080730}))\\
3/7& -((8996 (-911 + \sqrt{4080730}))/(
   7 (-4080730 + 911 \sqrt{4080730})))& (
  1296 (-911 + \sqrt{4080730}))/(-4080730 + 911 \sqrt{4080730})\\
-2/7& -((10875 (-911 + \sqrt{4080730}))/(
   7 (-4080730 + 911 \sqrt{4080730})))& -((
   1155 (-911 + \sqrt{4080730}))/(-4080730 + 911 \sqrt{4080730})))
\end{pmatrix}
R=Q^\top A=\begin{pmatrix}
14& -271/7& -14\\
0& -((4080730 (-911 + \sqrt{4080730}))/(7 (-4080730 + 911 \sqrt{4080730})))& ( 151585 (-911 + \sqrt{4080730}))/(-4080730 + 911 \sqrt{4080730})\\
  0& 0& -((44905 (-911 + \sqrt{4080730}))/(-4080730 +  911 \sqrt{4080730}))
\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é.

Voir aussi

  • Portail des mathématiques Portail des mathématiques
Ce document provient de « D%C3%A9composition QR ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Decomposition QR de Wikipédia en français (auteurs)

Regardez d'autres dictionnaires:

  • décomposition — [ dekɔ̃pozisjɔ̃ ] n. f. • 1694; de décomposer, d apr. composition 1 ♦ Séparation (d un corps, d une substance) en ses éléments. ⇒ division, séparation. Décomposition chimique. Décomposition de la lumière par le prisme. Math. Décomposition d une… …   Encyclopédie Universelle

  • Decomposition LU — Décomposition LU En algèbre linéaire, la décomposition LU est une méthode de décomposition d une matrice en une matrice triangulaire inférieure L (comme Low , bas) et une matrice triangulaire supérieure U (comme Up , haut). Cette décomposition… …   Wikipédia en Français

  • Décomposition lu — En algèbre linéaire, la décomposition LU est une méthode de décomposition d une matrice en une matrice triangulaire inférieure L (comme Low , bas) et une matrice triangulaire supérieure U (comme Up , haut). Cette décomposition est utilisée en… …   Wikipédia en Français

  • Decomposition — Décomposition Pour les articles homonymes, voir décomposition (homonymie). En biologie, la décomposition est le processus par lequel de la matière autrefois vivante dégénère pour atteindre une forme plus simple de matière (la matière minérale).… …   Wikipédia en Français

  • décomposition — DÉCOMPOSITION. sub. f. Terme de Chimie. Dissolution, résolution d un corps mixte dans ses principes. La décomposition d un corps mixte. f♛/b] On dit aussi au figuré, La décomposition d une idée, d un discours.[b]Décomposition, en Mécanique. On… …   Dictionnaire de l'Académie Française 1798

  • Decomposition — De*com po*si tion, n. [Pref. de (in sense 3 intensive) + composition: cf. F. d[ e]composition. Cf. {Decomposition}.] 1. The act or process of resolving the constituent parts of a compound body or substance into its elementary parts; separation… …   The Collaborative International Dictionary of English

  • decomposition — decomposition; pho·to·decomposition; …   English syllables

  • decomposition — Decomposition. s. f. v. Terme de Chymie. Dissolution, resolution d un corps mixte dans ses principes. La decomposition d un corps mixte …   Dictionnaire de l'Académie française

  • decomposition — index consumption, destruction, deterioration, dissolution (disintegration), spoilage Burton s Legal Thesaurus. William C. Burton …   Law dictionary

  • decomposition — 1762, from DE (Cf. de ) + COMPOSITION (Cf. composition). An earlier word in the same form meant further compounding of already composite things (1650s) …   Etymology dictionary