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 = Q R

où $Q$ est une matrice orthogonale ( $Q Q T = I$ ), et $R$ une matrice triangulaire supérieure.

Ce type de décomposition est souvent utilisée pour le calcul de solutions de systèmes linéaires non carrés, notamment pour déterminer la pseudo-inverse d'une matrice.

Extensions

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.

Exemples

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

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 du premier élément de x.

Soit e₁ le vecteur (1,0,..., 0)^T, et définissons, si x n'est pas colinéaire à e₁ :

$\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$ .

(Si x est colinéaire à e₁, on a le même résultat en prenant pour Q la matrice identité.)

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 souhaitiez 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 = 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 = Q R$ est la décomposition QR de $A$ . De plus, par construction les matrices $Q k$ sont non seulement orthogonales mais aussi symétriques, donc $Q=Q_1Q_2\cdots Q_t$ .

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 amène à $u = 2( - 1,3, - 2) 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^e 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_2Q_1A=Q^T 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é.

Méthode de Schmidt

On considère le procédé de Gram-Schmidt appliqué aux colonnes de la matrice $A=[\mathbf{a}_1, \cdots, \mathbf{a}_n]$ , muni du produit scalaire $\langle \mathbf{v}, \mathbf{w}\rangle = \mathbf{v}^\top \mathbf{w}$ (ou $\langle \mathbf{v}, \mathbf{w}\rangle = \mathbf{v}^* \mathbf{w}$ pour le cas complexe).

On définit la projection :

$\Pi_{\mathbf{e}} \mathbf{a} = \frac{\langle \mathbf{e},\mathbf{a}\rangle}{\langle \mathbf{e},\mathbf{e}\rangle}\mathbf{e}$

puis les vecteurs :

$\begin{align} \mathbf{u}_1 &= \mathbf{a}_1, & \mathbf{e}_1 &= {\mathbf{u}_1 \over \|\mathbf{u}_1\|} \\ \mathbf{u}_2 &= \mathbf{a}_2-\Pi_{\mathbf{e}_1}\,\mathbf{a}_2, & \mathbf{e}_2 &= {\mathbf{u}_2 \over \|\mathbf{u}_2\|} \\ \mathbf{u}_3 &= \mathbf{a}_3-\Pi_{\mathbf{e}_1}\,\mathbf{a}_3-\Pi_{\mathbf{e}_2}\,\mathbf{a}_3, & \mathbf{e}_3 &= {\mathbf{u}_3 \over \|\mathbf{u}_3\|} \\ & \vdots &&\vdots \\ \mathbf{u}_k &= \mathbf{a}_k-\sum_{j=1}^{k-1}\Pi_{\mathbf{e}_j}\,\mathbf{a}_k, &\mathbf{e}_k &= {\mathbf{u}_k\over\|\mathbf{u}_k\|} \end{align}$

On réarrange ensuite les équations de sorte que les $\mathbf{a}_i$ soient à gauche, en utilisant le fait que les $\mathbf{e}_i$ sont des vecteurs unitaires:

$\begin{align} \mathbf{a}_1 &= \langle\mathbf{e}_1,\mathbf{a}_1 \rangle \mathbf{e}_1 \\ \mathbf{a}_2 &= \langle\mathbf{e}_1,\mathbf{a}_2 \rangle \mathbf{e}_1 + \langle\mathbf{e}_2,\mathbf{a}_2 \rangle \mathbf{e}_2 \\ \mathbf{a}_3 &= \langle\mathbf{e}_1,\mathbf{a}_3 \rangle \mathbf{e}_1 + \langle\mathbf{e}_2,\mathbf{a}_3 \rangle \mathbf{e}_2 + \langle\mathbf{e}_3,\mathbf{a}_3 \rangle \mathbf{e}_3 \\ &\vdots \\ \mathbf{a}_k &= \sum_{j=1}^{k} \langle \mathbf{e}_j, \mathbf{a}_k \rangle \mathbf{e}_j \end{align}$

où $\langle\mathbf{e}_i,\mathbf{a}_i \rangle = \|\mathbf{u}_i\|$ . Ceci s'écrit matriciellement :

A = Q R

avec:

$Q = \left[ \mathbf{e}_1, \cdots, \mathbf{e}_n\right] \qquad \text{et} \qquad R = \begin{pmatrix} \langle\mathbf{e}_1,\mathbf{a}_1\rangle & \langle\mathbf{e}_1,\mathbf{a}_2\rangle & \langle\mathbf{e}_1,\mathbf{a}_3\rangle & \ldots \\ 0 & \langle\mathbf{e}_2,\mathbf{a}_2\rangle & \langle\mathbf{e}_2,\mathbf{a}_3\rangle & \ldots \\ 0 & 0 & \langle\mathbf{e}_3,\mathbf{a}_3\rangle & \ldots \\ \vdots & \vdots & \vdots & \ddots \end{pmatrix}.$

Exemple

On reprend la matrice de l'exemple

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

Rappelons qu'une matrice orthogonale $Q$ vérifie

$\begin{matrix} Q^{T}\,Q = I. \end{matrix}$

On peut alors calculer $Q$ par les moyens de Gram-Schmidt comme suit :

$U = \begin{pmatrix} \mathbf u_1 & \mathbf u_2 & \mathbf u_3 \end{pmatrix} = \begin{pmatrix} 12 & -69 & -58/5 \\ 6 & 158 & 6/5 \\ -4 & 30 & -33 \end{pmatrix};$

$Q = \begin{pmatrix} \frac{\mathbf u_1}{\|\mathbf u_1\|} & \frac{\mathbf u_2}{\|\mathbf u_2\|} & \frac{\mathbf u_3}{\|\mathbf u_3\|} \end{pmatrix} = \begin{pmatrix} 6/7 & -69/175 & -58/175 \\ 3/7 & 158/175 & 6/175 \\ -2/7 & 6/35 & -33/35 \end{pmatrix}.$

Dans ce cas, on a :

$\begin{matrix} Q^{T} A = Q^{T}Q\,R = R; \end{matrix}$

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

Relation avec la décomposition RQ

La décomposition RQ transforme une matrice A en produit d'une matrice triangulaire supérieure R et une matrice orthogonale Q. La seule différence avec la décomposition QR est l'ordre de ces matrices.

La décomposition QR est l'application du procédé de Gram-Schmidt sur les colonnes de A, en partant de la première colonne ; la décomposition RQ est l'application du procédé de Gram-Schmidt sur les lignes de A, en partant de la dernière ligne.

Méthode de Givens

Dans cette méthode, la matrice Q utilise des rotations de Givens. Chaque rotation annule un élément de la partie triangulaire inférieure stricte de la matrice, construisant la matrice R, tandis que la concaténation des rotations engendre la matrice Q.

Dans la pratique, les rotations de Givens ne sont pas effectivement assurées par la construction d'une matrice pleine et une multiplication matricielle. Une procédure de rotation de Givens est utilisé à la place qui est l'équivalent de la multiplication par une matrice de Givens creuse, sans efforts supplémentaires de la manipulation des éléments non nuls. La procédure de rotation de Givens est utile dans des situations où seul un nombre relativement restreint hors éléments diagonaux doivent être remis à zéro, et est plus facilement parallélisée que les transformations de Householder.

Exemple

Reprenons le même exemple

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

On doit d'abord construire une matrice de rotation qui annulera l'élément le plus bas de la colonne de gauche, $\mathbf{a}_{31} = -4$ , qu'on construit par une méthode de rotation de Givens. On appelle cette matrice $G 1$ . On va d'abord faire une rotation du vecteur $(6, - 4)$ , pour le ramener sur l'axe X. Ce vecteur forme un angle $\theta = \arctan\left({-4 \over 6}\right)$ . La matrice $G 1$ est donc donnée par :

$G_1 = \begin{pmatrix} 1 & 0 & 0 \\ 0 & \cos(\theta) & \sin(\theta) \\ 0 & -\sin(\theta) & \cos(\theta) \end{pmatrix}$

$\approx \begin{pmatrix} 1 & 0 & 0 \\ 0 & 0,83205 & -0,55470 \\ 0 & 0,55470 & 0,83205 \end{pmatrix}$

Le produit $G 1 A$ annule le coefficient $\mathbf{a}_{31}$ :

$G_1A \approx \begin{pmatrix} 12 & -51 & 4 \\ 7,21110 & 125,6396 & -33,83671 \\ 0 & 112,6041 & -71,83368 \end{pmatrix}$

Par suite, on construit des matrices de Givens $G 2$ and $G 3$ , qui vont respectivement annuler $a 21$ et $a 32$ , engendrant la matrice $R$ . La matrice orthogonale $Q T$ est formée de la concaténation de toutes les matrices de Givens créées $Q T = G 3 G 2 G 1$ .

Voir aussi

v · Matrices
Par forme	carrée • triangulaire • diagonale • tridiagonale • élémentaire • échelonnée • creuse • aléatoire • circulante • de Hankel • de Toeplitz • de Vandermonde
Transformée	transposée • conjuguée • adjointe • inverse • comatrice
En relation	équivalentes • semblables • congruentes
Par propriété	inversible • diagonalisable • trigonalisable • symétrique • antisymétrique • hermitienne • normale • orthogonale • unitaire • symplectique • de Hadamard • positive • définie positive • à diagonale dominante • nilpotente
Par famille	identité • de De Casteljau • de Cartan • de Hilbert • de Mueller • de Pauli • de Dirac • de Householder
Particulière	CKM
Associée	de permutation • de passage • compagnon • de Sylvester • d'adjacence • laplacienne • hessienne • jacobienne • génératrice • de contrôle • de corrélation • de Gram • de variance-covariance • d'inertie • de Jones • des gains • stochastique
Résultats	décompositions : LU • QR • Cholesky • polaire • valeurs singulières Diagonalisation • Trigonalisation • Réduction de Jordan • facteurs invariants
Voir aussi	Théorie des matrices • Algèbre linéaire • Algèbre bilinéaire

Portail des mathématiques

Catégories :

Analyse numérique matricielle
Algèbre bilinéaire

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Décomposition 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 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 où Q est une matrice orthogonale (QQT = I), et R une matrice triangulaire supérieure. Il existe… … 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

Dictionnaires et Encyclopédies sur 'Academic'

Décomposition QR

Sommaire

Extensions