Décomposition d'une matrice

En algèbre linéaire, une décomposition matricielle ou factorisation matricielle est une factorisation de matrice en un produit de matrices. Il existe de nombreuses décompositions matricielles différentes ; chacune trouvant son utilité dans une classe particulière de problèmes.

Exemple

En analyse numérique, différentes décompositions sont utilisées pour mettre en œuvre des algorithmes matriciels efficaces : par exemple une complexité moindre ou moins d'erreurs d'arrondis.

Par exemple, lors de la résolution d'un système d'équations linéaires ${\displaystyle Ax=b}$, la matrice A peut être décomposée via la décomposition LU (pour Low / Up en anglais). La décomposition LU factorise une matrice en une matrice triangulaire inférieure L et une matrice triangulaire supérieure U . Les systèmes ${\displaystyle L(Ux)=b}$ et ${\textstyle Ux=L^{-1}b}$ nécessitent moins d'additions et de multiplications pour être résolus, par rapport au système d'origine ${\displaystyle Ax=b}$, bien que l'on puisse avoir besoin de beaucoup plus de chiffres lors d'une résolution numérique utilisant la virgule flottante comme représentation des nombres.

De même, la décomposition QR exprime A sous la forme QR avec Q une matrice orthogonale et R une matrice triangulaire supérieure. Le système ${\textstyle Q(Rx)=b}$ est résolu par ${\textstyle Rx=Q^{T}b=c}$, et le système ${\textstyle Rx=c}$ est résolu en « remontant » les équations obtenues. Le nombre d'additions et de multiplications requis est environ le double de celui de l'utilisation de la décomposition LU, mais aucun chiffre supplémentaire n'est requis en arithmétique inexacte car la décomposition QR est numériquement stable.

Décompositions liées à la résolution de systèmes d'équations linéaires

Décomposition du bloc LU

• Souvent utilisé pour une matrice carrée ${\displaystyle A}$, bien qu'il existe une version pour les matrices triangulaires^{[1],[nb 1]}.
• Décomposition : ${\displaystyle A=LU}$, où L est triangulaire inférieur et U est triangulaire supérieur.
• Similairement : la décomposition LDU est ${\displaystyle A=LDU}$, où L est triangulaire inférieure avec des uns sur la diagonale, U est triangulaire supérieure avec les uns sur la diagonale et D est une matrice diagonale.
• Aussi : la décomposition PLU est ${\displaystyle A=PLU}$, où L est triangulaire inférieure, U est triangulaire supérieure et P est une matrice de permutation.
• Existence : Une décomposition PLU existe pour toute matrice carrée A . Lorsque P est une matrice identité, la décomposition PLU se réduit à la décomposition LU.
• Commentaires : Les décompositions PLU et LU sont utiles pour résoudre un système ${\textstyle n\times n}$ d'équations linéaires. ${\textstyle Ax=b}$. Ces décompositions résument le processus d'élimination gaussienne sous forme matricielle. La matrice P représente tous les échanges de lignes effectués dans le processus d'élimination gaussienne. Si l’élimination gaussienne produit la forme échelonnée de lignes sans nécessiter d’échanges de lignes, alors ${\textstyle P=I_{n}}$, donc une décomposition LU existe.

Réduction LU

Décomposition LU

Factorisation des rangs

• Applicable à un matrice A de taille ${\displaystyle m\times n}$ de rang ${\displaystyle r}$.
• Décomposition : ${\displaystyle A=CF}$ où C est une matrice de rang de colonne maximal ${\displaystyle m\times r}$ et F est une matrice de rang de ligne maximal ${\displaystyle r\times n}$.
• Commentaire : La factorisation de rang peut être utilisée pour calculer le pseudo-inverse de Moore – Penrose de A^[2], que l'on peut appliquer pour obtenir toutes les solutions du système linéaire ${\textstyle Ax=b}$.

Décomposition de Cholesky

• Applicable à un matrice ${\displaystyle A}$ carrée, hermitienne, définie positive ${\displaystyle A}$.
• Décomposition : ${\displaystyle A=U^{*}U}$, où ${\displaystyle U}$ est triangulaire supérieur avec de réelles entrées diagonales positives.
• Commentaire : si la matrice ${\displaystyle A}$ est hermitienne et semi-définie positive, alors elle a une décomposition de la forme ${\displaystyle A=U^{*}U}$ si les entrées diagonales de ${\displaystyle U}$ sont autorisés à être nuls.
• Unicité : pour les matrices définies positives, la décomposition de Cholesky est unique. Cependant, ce n'est pas vrai dans le cas semi-défini positif.
• Commentaire : si ${\displaystyle A}$ est réelle et symétrique, ${\displaystyle U}$ a tous ses éléments réels.
• Commentaire : Une alternative est la décomposition LDL, qui permet d'éviter l'extraction des racines carrées.

Décomposition QR

• Applicable à une matrice ${\displaystyle m\times n}$ ${\displaystyle A}$ avec colonnes linéairement indépendantes.
• Décomposition : ${\displaystyle A=QR}$ où ${\displaystyle Q}$ est une matrice unitaire de taille ${\displaystyle m\times m}$, et ${\displaystyle R}$ est une matrice triangulaire supérieure de taille ${\displaystyle m\times n}$.
• Unicité : En général, ce n’est pas unique, mais si ${\displaystyle A}$ est de rang maximal (${\displaystyle \mathrm {rg} (A)=n}$), alors il existe une seule matrice ${\displaystyle R}$ qui a tous ses éléments diagonaux positifs. Si ${\displaystyle A}$ est carré, ${\displaystyle Q}$ aussi est unique.
• Commentaire : La décomposition ${\displaystyle QR}$ fournit un moyen efficace de résoudre le système d'équations ${\displaystyle A\mathbf {x} =\mathbf {b} }$. Le fait que ${\displaystyle Q}$ soit orthogonale signifie que ${\displaystyle Q^{\mathrm {T} }Q=I}$, de sorte que ${\displaystyle Ax=b}$ est équivalent à ${\displaystyle Rx=Q^{T}b}$, ce qui est très simple à résoudre puisque ${\displaystyle R}$ est triangulaire.

Factorisation RRQR

Décomposition interpolative

Décompositions basées sur les valeurs propres et concepts associés

Décomposition en éléments propres

• Aussi appelée décomposition spectrale.
• Applicable à une matrice carrée ${\displaystyle A}$ avec des vecteurs propres linéairement indépendants (valeurs propres pas nécessairement distinctes).
• Décomposition: ${\displaystyle A=PDP^{-1}}$, où D est une matrice diagonale formée à partir des valeurs propres de A, et les colonnes de ${\displaystyle P}$ sont les vecteurs propres correspondants de ${\displaystyle A}$.
• Existence : une matrice ${\displaystyle n\times n}$ ${\displaystyle A}$ a toujours ${\displaystyle n}$ valeurs propres (complexes), qui peuvent être ordonnées (de plusieurs manières) pour former une matrice diagonale ${\displaystyle n\times n}$ ${\displaystyle D}$ et une matrice correspondante de colonnes non nulles ${\displaystyle P}$ qui satisfait l'équation des valeurs propres ${\displaystyle AP=PD}$. ${\displaystyle P}$ est inversible si et seulement si les ${\displaystyle n}$ vecteurs propres sont linéairement indépendants (c'est-à-dire que chaque valeur propre a une multiplicité géométrique égale à sa multiplicité algébrique). Une condition suffisante (mais pas nécessaire) pour que cela se produise est que toutes les valeurs propres soient différentes (dans ce cas les multiplicités géométriques et algébriques sont égales à 1).
• Commentaire : toute matrice normale A (c'est-à-dire une matrice pour laquelle ${\displaystyle AA^{*}=A^{*}A}$, où ${\displaystyle A^{*}}$ est la matrice adjointe de ${\displaystyle A}$) peut être décomposée en éléments propres. Pour une matrice normale A (et uniquement pour une matrice normale), les vecteurs propres peuvent également être rendus orthonormés (${\displaystyle PP^{*}=I}$) et la décomposition sera ${\displaystyle A=PDP^{*}}$. En particulier, toutes les matrices unitaires, hermitiennes ou antihermitienne (dans le cas des réels, toutes les matrices orthogonales, symétriques ou antisymétriques, respectivement) sont normales et possèdent donc cette propriété.
• Commentaire : Pour toute matrice symétrique réelle A, la décomposition propre existe toujours et peut s'écrire sous la forme ${\displaystyle A=PDP^{\mathsf {T}}}$, où D et P sont toutes deux réelles.
• Commentaire : la décomposition propre est utile pour comprendre la solution d'un système d'équations différentielles ordinaires linéaires ou d'équations aux différences linéaires. Par exemple, l'équation de différence ${\displaystyle x_{t+1}=Ax_{t}}$ à partir de la condition initiale ${\displaystyle x_{0}=c}$ est résolu par ${\displaystyle x_{t}=A^{t}c}$, ce qui équivaut à ${\displaystyle x_{t}=PD^{t}P^{-1}c}$, où P et D sont les matrices formées à partir des vecteurs propres et des valeurs propres de A . Puisque D est diagonale, l'élever à la puissance ${\displaystyle D^{t}}$, consiste simplement à élever chaque coefficient de la diagonale à la puissance t. C'est beaucoup plus facile à faire et à comprendre que d'élever A à la puissance t, puisque A n'est généralement pas diagonale.

La forme normale de Jordan et la décomposition de Dunford sont :

• Applicables à une matrice carrée A.
• Commentaire : la forme normale de Jordan généralise la décomposition spectrale aux cas où il y a des valeurs propres répétées et ne peuvent pas être diagonalisées, la décomposition de Dunford le fait sans choisir de base.

Décomposition de Schur

• Applicable à une matrice carrée A.
• Décomposition (version complexe) : ${\displaystyle A=UTU^{*}}$, où U est une matrice unitaire, ${\displaystyle U^{*}}$ est la transconjuguée de U, et T est une matrice triangulaire supérieure appelée forme complexe de Schur qui a les valeurs propres de A le long de sa diagonale.
• Commentaire : si A est une matrice normale, alors T est diagonale et la décomposition de Schur coïncide avec la décomposition spectrale.

Décomposition réelle de Schur

• Applicable à une matrice carrée A.
• Décomposition : il s'agit d'une version de la décomposition de Schur où ${\displaystyle P}$ et ${\displaystyle S}$ ne contiennent que des nombres réels. On peut toujours écrire ${\displaystyle A=PSP^{\mathsf {T}}}$ où P est une matrice orthogonale réelle, ${\displaystyle P^{\mathsf {T}}}$ est la transposée de P, et S est une matrice triangulaire supérieure par bloc appelée forme réelle de Schur. Les blocs sur la diagonale de S sont de taille ${\displaystyle 1\times 1}$ (auquel cas ils représentent des valeurs propres réelles) ou ${\displaystyle 2\times 2}$ (auquel cas ils sont dérivés de paires de valeurs propres conjuguées complexes).

Décomposition QZ

• Aussi appelée : décomposition de Schur généralisée.
• Applicable à des matrices carrées A et B.
• Commentaire : il existe deux versions de cette décomposition : complexe et réelle.
• Décomposition (version complexe) : ${\displaystyle A=QSZ^{*}}$ et ${\displaystyle B=QTZ^{*}}$ où Q et Z sont des matrices unitaires, l'exposant * représente la transconjuguée et S et T sont des matrices triangulaires supérieures.
• Commentaire : dans la décomposition complexe QZ, les rapports des éléments diagonaux de S aux éléments diagonaux correspondants de T, ${\displaystyle \lambda _{i}=S_{ii}/T_{ii}}$, sont les valeurs propres généralisées qui résolvent le problème des valeurs propres généralisées ${\displaystyle Av=\lambda Bv}$ (où ${\displaystyle \lambda }$ est un scalaire inconnu et ${\displaystyle v}$ est un vecteur inconnu non nul).
• Décomposition (version réelle) : ${\displaystyle A=QSZ^{\mathsf {T}}}$ et ${\displaystyle B=QTZ^{\mathsf {T}}}$ où A, B, Q, Z, S et T sont des matrices contenant uniquement des nombres réels. Dans ce cas, Q et Z sont des matrices orthogonales, l'exposant ${\displaystyle ^{T}}$représente la transposition et S et T sont des matrices triangulaires supérieures en bloc. Les blocs sur la diagonale de S et T sont de taille ${\displaystyle 1\times 1}$ ou ${\displaystyle 2\times 2}$.

Factorisation de Takagi

• Applicable à une matrice carrée, complexe et symétrique A.
• Décomposition : ${\displaystyle A=PDP^{\mathsf {T}}}$, où D est une matrice diagonale réelle non négative et P est unitaire. ${\displaystyle P^{\mathsf {T}}}$ désigne la transposée matricielle de P.
• Commentaire : les éléments diagonaux de D sont les racines carrées positives des valeurs propres de ${\displaystyle AA^{*}=PD^{2}P^{*}}$.
• Commentaire : P peut être complexe même si A est réel.
• Commentaire : il ne s'agit pas d'un cas particulier de la décomposition propre (voir ci-dessus), qui utilise ${\displaystyle P^{-1}}$ au lieu de ${\displaystyle P^{\mathsf {T}}}$. De plus, si A n’est pas réel, il n’est pas hermitien et la forme utilisant ${\displaystyle P^{*}}$ ne s’applique pas non plus.

Décomposition en valeurs singulières

• Applicable à une matrice A de taille ${\displaystyle m\times n}$.
• Décomposition: ${\displaystyle A=UDV^{*}}$, où D est une matrice diagonale non négative, et U et V satisfont ${\displaystyle U^{*}U=I,V^{*}V=I}$. Ici ${\displaystyle V^{*}}$ est la transconjuguée de V (ou simplement la transposée, si V ne contient que des nombres réels), et I désigne la matrice identité (d'une certaine dimension).
• Commentaire : Les éléments diagonaux de D sont appelés valeurs singulières de A.
• Commentaire : Comme la décomposition spectrale ci-dessus, la décomposition en valeurs singulières implique de trouver des directions de base le long desquelles la multiplication matricielle est équivalente à la multiplication scalaire, mais elle a une plus grande généralité puisque la matrice considérée n'a pas besoin d'être carrée.
• Unicité : les valeurs singulières de ${\displaystyle A}$ sont toujours déterminés de manière unique. ${\displaystyle U}$ et ${\displaystyle V}$ ne sont pas nécessairement uniques.

Décompositions invariantes par dilatation

Fait référence à des variantes de décompositions matricielles existantes, telles que la décomposition en valeurs singulières (SVD), qui sont invariantes par dilatation.

• Applicable à une matrice A de taille ${\displaystyle m\times n}$.
• Décomposition en valeurs singulières invariantes par dilatation unitaire : ${\displaystyle A=DUSV^{*}E}$, où S est une matrice diagonale non négative unique de valeurs singulières invariantes d'échelle, U et V sont des matrices unitaires, ${\displaystyle V^{*}}$ est la transposée-conjuguée de V et des matrices diagonales positives D et E.
• Commentaire : elle est analogue au SVD sauf que les éléments diagonaux de S sont invariants par rapport à la multiplication gauche et/ou droite de A par des matrices diagonales arbitraires non singulières, par opposition au SVD standard pour lequel les valeurs singulières sont invariantes par rapport à la gauche et/ou multiplication à droite de A par des matrices unitaires quelconques.
• Commentaire : elle est une alternative au SVD standard lorsque l'invariance est requise par rapport aux transformations diagonales plutôt qu'unitaires de A.
• Unicité : les valeurs singulières invariantes à l'échelle de ${\displaystyle A}$ (donnés par les éléments diagonaux de S) sont toujours déterminés de manière unique. Les matrices diagonales D et E, et unitaires U et V, ne sont pas nécessairement uniques en général.
• Commentaire : les matrices U et V ne sont pas les mêmes que celles du SVD.

Des décompositions analogues invariantes d'échelle peuvent être dérivées d'autres décompositions matricielles ; par exemple, pour obtenir des valeurs propres invariantes à l'échelle.

Décomposition de Hessenberg

• Applicable à une matrice carrée A.
• Décomposition: ${\displaystyle A=PHP^{*}}$ où ${\displaystyle H}$ est la matrice de Hessenberg et ${\displaystyle P}$ est une matrice unitaire.
• Commentaire : souvent la première étape de la décomposition de Schur.

Décomposition orthogonale complète

• Également connu sous le nom de : décomposition UTV, décomposition ULV, décomposition URV.
• Applicable à une matrice A de taille ${\displaystyle m\times n}$.
• Décomposition : ${\displaystyle A=UTV^{*}}$, où T est une matrice triangulaire, et U et V sont des matrices unitaires.
• Commentaire : similaire à la décomposition en valeurs singulières et à la décomposition de Schur.

Autres décompositions

Décomposition polaire

• Applicable à : toute matrice complexe carrée A.
• Décomposition : ${\displaystyle A=UP}$ (décomposition polaire droite) ou ${\displaystyle A=P'U}$ (décomposition polaire gauche), où U est une matrice unitaire et P et P' sont des matrices hermitiennes semi-définies positives.
• Unicité : ${\displaystyle P}$ est toujours unique et égal à ${\displaystyle {\sqrt {A^{*}A}}}$ (qui est toujours hermitienne et semi-définie positive). Si ${\displaystyle A}$ est inversible, alors ${\displaystyle U}$ est unique.
• Commentaire : Puisque toute matrice hermitienne admet une décomposition spectrale avec une matrice unitaire, ${\displaystyle P}$ peut s'écrire comme ${\displaystyle P=VDV^{*}}$. Comme ${\displaystyle P}$ est semi-définie positive, tous les éléments de ${\displaystyle D}$ sont non négatifs. Puisque le produit de deux matrices unitaires est unitaire, en prenant ${\displaystyle W=UV}$ on peut écrire ${\displaystyle A=U(VDV^{*})=WDV^{*}}$ qui est la décomposition en valeurs singulières. Par conséquent, l’existence de la décomposition polaire équivaut à l’existence de la décomposition en valeurs singulières.

Décomposition polaire algébrique

• Applicable à : matrice carrée, complexe et non singulière A^[3].
• Décomposition : ${\displaystyle A=QS}$, où Q est une matrice orthogonale complexe et S est une matrice symétrique complexe.
• Unicité : Si ${\displaystyle A^{\mathsf {T}}A}$ n’a pas de valeurs propres réelles négatives, alors la décomposition est unique^[4].
• Commentaire : L’existence de cette décomposition équivaut à ${\displaystyle AA^{\mathsf {T}}}$ étant semblable à ${\displaystyle A^{\mathsf {T}}A}$^[5].
• Commentaire : Une variante de cette décomposition est ${\displaystyle A=RC}$, où R est une matrice réelle et C est une matrice circulaire^[4].

Décomposition de Mostow

• Applicable à : matrice carrée, complexe et non singulière A^[6].
• Décomposition : ${\displaystyle A=Ue^{iM}e^{S}}$, où U est unitaire, M est réel anti-symétrique et S est réel symétrique.
• Commentaire : la matrice A peut également être décomposée comme ${\displaystyle A=U_{2}e^{S_{2}}e^{iM_{2}}}$, où U ₂ est unitaire, M ₂ est réel anti-symétrique et S ₂ est réel symétrique^[4].

Forme normale de Sinkhorn

• Applicable à : matrice réelle carrée A avec éléments strictement positifs.
• Décomposition: ${\displaystyle A=D_{1}SD_{2}}$, où S est doublement stochastique et D ₁ et D ₂ sont de vraies matrices diagonales avec des éléments strictement positifs.

Décomposition « sectorielle »

• Applicable à : matrice carrée et complexe A avec plage numérique contenue dans le secteur ${\displaystyle S_{\alpha }=\left\{re^{i\theta }\in \mathbb {C} \mid r>0,|\theta |\leq \alpha <{\frac {\pi }{2}}\right\}}$.
• Décomposition: ${\displaystyle A=CZC^{*}}$, où C est une matrice complexe inversible et ${\displaystyle Z=\operatorname {diag} \left(e^{i\theta _{1}},\ldots ,e^{i\theta _{n}}\right)}$ avec tous les ${\displaystyle \left|\theta _{j}\right|\leq \alpha }$^[7],[8].

Forme normale de Williamson

• Applicable à : matrice réelle carrée définie positive A d'ordre ${\displaystyle 2n\times 2n}$.
• Décomposition : ${\displaystyle A=S^{\mathsf {T}}\operatorname {diag} (D,D)S}$, où ${\displaystyle S\in {\text{Sp}}(2n)}$ est une matrice symplectique et D est une matrice diagonale n par n non négative^[9].

Racine carrée matricielle

• Décomposition : ${\displaystyle A=BB}$, n'est pas unique en général.
• Dans le cas où ${\displaystyle A}$ est semi-définie positive, il existe une unique matrice semi-définie positive ${\displaystyle B}$ tel que ${\displaystyle A=B^{*}B=BB}$.

Généralisations

Il existe des analogues des factorisations SVD, QR, LU et Cholesky pour les quasimatrices et cmatrices ou matrices continues^[10]. Une « quasi-matrice » est, comme une matrice, un schéma rectangulaire dont les éléments sont indexés, mais un indice discret est remplacé par un indice continu. De même, une « cmatrice » est continue dans les deux indices. Comme exemple de cmatrice, on peut penser au noyau d'un opérateur intégral. Ces terminologies proviennent des sources anglophones.

Ces factorisations sont basées sur les premiers travaux de Fredholm (1903), Hilbert (1904) et Schmidt (1907). Pour un compte rendu et une traduction en anglais des articles fondateurs, voir Stewart (2011).

Notes et références

Notes

1. Si la matrice A n'est pas carrée, la matrice U aura la même dimension (rectangulaire) que A. Ainsi, dire que U est triangulaire est incorrect, et le terme serait que U est la forme échelonnée réduite de A. À part cela, il n'y a a pas de différence entre la factorisation LU des matrices carrées et non carrées.

Références

1. (en) David C. Lay, Linear algebra and its applications, Harlow, Fifth Global, 2016, 142 p. (ISBN 978-1-292-09223-2, OCLC 920463015, lire en ligne)
2. (en) R. Piziak et P. L. Odell, « Full Rank Factorization of Matrices », Mathematics Magazine, vol. 72, n^o 3,‎ 1^er juin 1999, p. 193 (DOI 10.2307/2690882, JSTOR 2690882)
3. Choudhury et Horn 1987, p. 219–225
4. (en) Rajendra Bhatia, « The bipolar decomposition », Linear Algebra and Its Applications, vol. 439, n^o 10,‎ 15 novembre 2013, p. 3031–3037 (DOI 10.1016/j.laa.2013.09.006)
5. Horn et Merino 1995, p. 43–92
6. (en) Frank Nielsen et Rajendra Bhatia, Matrix Information Geometry, Springer, 2012, 224 p. (ISBN 9783642302329, DOI 10.1007/978-3-642-30232-9, arXiv 1007.4402, S2CID 118466496)
7. (en) Fuzhen Zhang, « A matrix decomposition and its applications », Linear and Multilinear Algebra, vol. 63, n^o 10,‎ 30 juin 2014, p. 2033–2042 (DOI 10.1080/03081087.2014.933219, S2CID 19437967, lire en ligne)
8. (en) S.W. Drury, « Fischer determinantal inequalities and Highamʼs Conjecture », Linear Algebra and Its Applications, vol. 439, n^o 10,‎ novembre 2013, p. 3129–3133 (DOI 10.1016/j.laa.2013.08.031)
9. (en) Martin Idel, Sebastián Soto Gaona et Michael M. Wolf, « Perturbation bounds for Williamson's symplectic normal form », Linear Algebra and Its Applications, vol. 525,‎ 15 juillet 2017, p. 45–58 (DOI 10.1016/j.laa.2017.03.013, arXiv 1609.01338, S2CID 119578994)
10. Townsend et Trefethen 2015

Voir aussi

Bibliographie

• Choudhury et Horn, « A Complex Orthogonal-Symmetric Analog of the Polar Decomposition », SIAM Journal on Algebraic and Discrete Methods, vol. 8, n^o 2,‎ avril 1987, p. 219–225 (DOI 10.1137/0608019) 
• Horn et Merino, « Contragredient equivalence: A canonical form and some applications », Linear Algebra and Its Applications, vol. 214,‎ janvier 1995, p. 43–92 (DOI 10.1016/0024-3795(93)00056-6)
• C. Simon et L. Blume, Mathematics for Economists, Norton, 1994 (ISBN 978-0-393-95733-4)

Articles connexes

• Analyse en composantes principales

Liens externes

• Calculateur matriciel en ligne
• Calcul de décomposition de la matrice Wolfram Alpha. Décomposition LU et QR
• « Factorisation matricielle », sur l'Encyclopédie Springer des mathématiques
• GraphLab Bibliothèque de filtrage collaboratif GraphLab, implémentation parallèle à grande échelle de méthodes de décomposition matricielle (en C++) pour le multicœur.

• Portail de l’algèbre