Décomposition d'une matrice

factoriser une matrice en produit de plusieurs matrices

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 modifier

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  , 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   et   nécessitent moins d'additions et de multiplications pour être résolus, par rapport au système d'origine  , 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   est résolu par  , et le système   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 modifier

Décomposition du bloc LU modifier

Réduction LU modifier

Décomposition LU modifier

Factorisation des rangs modifier

  • Applicable à un matrice A de taille   de rang  .
  • Décomposition :  C est une matrice de rang de colonne maximal   et F est une matrice de rang de ligne maximal  .
  • 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  .

Décomposition de Cholesky modifier

  • Applicable à un matrice   carrée, hermitienne, définie positive  .
  • Décomposition :  , où   est triangulaire supérieur avec de réelles entrées diagonales positives.
  • Commentaire : si la matrice   est hermitienne et semi-définie positive, alors elle a une décomposition de la forme   si les entrées diagonales de   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   est réelle et symétrique,   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 modifier

  • Applicable à une matrice     avec colonnes linéairement indépendantes.
  • Décomposition :    est une matrice unitaire de taille  , et   est une matrice triangulaire supérieure de taille  .
  • Unicité : En général, ce n’est pas unique, mais si   est de rang maximal ( ), alors il existe une seule matrice   qui a tous ses éléments diagonaux positifs. Si   est carré,   aussi est unique.
  • Commentaire : La décomposition   fournit un moyen efficace de résoudre le système d'équations  . Le fait que   soit orthogonale signifie que  , de sorte que   est équivalent à  , ce qui est très simple à résoudre puisque   est triangulaire.

Factorisation RRQR modifier

Décomposition interpolative modifier

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

Décomposition en éléments propres modifier

  • Aussi appelée décomposition spectrale.
  • Applicable à une matrice carrée   avec des vecteurs propres linéairement indépendants (valeurs propres pas nécessairement distinctes).
  • Décomposition:  , où D est une matrice diagonale formée à partir des valeurs propres de A, et les colonnes de   sont les vecteurs propres correspondants de  .
  • Existence : une matrice     a toujours   valeurs propres (complexes), qui peuvent être ordonnées (de plusieurs manières) pour former une matrice diagonale     et une matrice correspondante de colonnes non nulles   qui satisfait l'équation des valeurs propres  .   est inversible si et seulement si les   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  , où   est la transconjuguée de  ) 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 ( ) et la décomposition sera  . En particulier, toutes les matrices unitaires, hermitiennes ou antihermitienne (dans le cas des réel, 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  , 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   à partir de la condition initiale   est résolu par  , ce qui équivaut à  , 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  , 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 modifier

Décomposition réelle de Schur modifier

  • Applicable à une matrice carrée A.
  • Décomposition : Il s'agit d'une version de la décomposition de Schur où   et   ne contiennent que des nombres réels. On peut toujours écrire  P est une matrice orthogonale réelle,   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   (auquel cas ils représentent des valeurs propres réelles) ou   (auquel cas ils sont dérivés de paires de valeurs propres conjuguées complexes).

Décomposition QZ modifier

  • Aussi appelé : 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) :   et  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,  , sont les valeurs propres généralisées qui résolvent le problème des valeurs propres généralisées   (où   est un scalaire inconnu et   est un vecteur inconnu non nul).
  • Décomposition (version réelle) :   et  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  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   ou  .

Factorisation de Takagi modifier

  • Applicable à une matrice carrée, complexe et symétrique A.
  • Décomposition :  , où D est une matrice diagonale réelle non négative et P est unitaire.   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  .
  • 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   au lieu de  . De plus, si A n’est pas réel, il n’est pas hermitien et la forme utilisant   ne s’applique pas non plus.

Décomposition en valeurs singulières modifier

  • Applicable à une matrice A de taille  .
  • Décomposition:  , où D est une matrice diagonale non négative, et U et V satisfont  . Ici   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   sont toujours déterminés de manière unique.   et   ne sont pas nécessairement uniques.

Décompositions invariantes par dilatation modifier

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  .
  • Décomposition en valeurs singulières invariantes par dilatation unitaire :  , où S est une matrice diagonale non négative unique de valeurs singulières invariantes d'échelle, U et V sont des matrices unitaires,   est la transposée-conjuguée de V et des matrices diagonales positives D et E.
  • Commentaire : 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 : 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   (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 modifier

  • Applicable à une matrice carrée A.
  • Décomposition:    est la matrice de Hessenberg et   est une matrice unitaire.
  • Commentaire : souvent la première étape de la décomposition de Schur.

Décomposition orthogonale complète modifier

  • Également connu sous le nom de : décomposition UTV, décomposition ULV, décomposition URV.
  • Applicable à une matrice A de taille  .
  • Décomposition :  , 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 modifier

Décomposition polaire modifier

  • Applicable à : toute matrice complexe carrée A.
  • Décomposition :   (décomposition polaire droite) ou   (décomposition polaire gauche), où U est une matrice unitaire et P et P' sont des matrices hermitiennes semi-définies positives.
  • Unicité :   est toujours unique et égal à   (qui est toujours hermitienne et semi-définie positive). Si   est inversible, alors   est unique.
  • Commentaire : Puisque toute matrice hermitienne admet une décomposition spectrale avec une matrice unitaire,   peut s'écrire comme  . Comme   est semi-définie positive, tous les éléments de   sont non négatifs. Puisque le produit de deux matrices unitaires est unitaire, en prenant   on peut écrire   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 modifier

  • Applicable à : matrice carrée, complexe et non singulière A[3].
  • Décomposition :  , où Q est une matrice orthogonale complexe et S est une matrice symétrique complexe.
  • Unicité : Si   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 à   étant semblable à  [5].
  • Commentaire : Une variante de cette décomposition est  , où R est une matrice réelle et C est une matrice circulaire[4].

Décomposition de Mostow modifier

  • Applicable à : matrice carrée, complexe et non singulière A[6].
  • Décomposition :  , 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  , où U 2 est unitaire, M 2 est réel anti-symétrique et S 2 est réel symétrique[4].

Forme normale de Sinkhorn modifier

  • Applicable à : matrice réelle carrée A avec éléments strictement positifs.
  • Décomposition:  , où S est doublement stochastique et D 1 et D 2 sont de vraies matrices diagonales avec des éléments strictement positifs.

Décomposition « sectorielle » modifier

  • Applicable à : matrice carrée et complexe A avec plage numérique contenue dans le secteur  .
  • Décomposition:  , où C est une matrice complexe inversible et   avec tous les  [7],[8].

Forme normale de Williamson modifier

  • Applicable à : matrice réelle carrée définie positive A d'ordre  .
  • Décomposition :  , où   est une matrice symplectique et D est une matrice diagonale n par n non négative[9].

Racine carrée matricielle modifier

  • Décomposition :  , n'est pas unique en général.
  • Dans le cas où   est semi-définie positive, il existe une unique matrice semi-définie positive   tel que  .

Généralisations modifier

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 modifier

Notes modifier

  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 modifier

  1. (en) David C. Lay, Linear algebra and its applications, Harlow, Fifth Global, , 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, no 3,‎ , p. 193 (DOI 10.2307/2690882, JSTOR 2690882)
  3. Choudhury et Horn 1987, p. 219–225
  4. a b et c (en) Rajendra Bhatia, « The bipolar decomposition », Linear Algebra and Its Applications, vol. 439, no 10,‎ , 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, , 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, no 10,‎ , 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, no 10,‎ , 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,‎ , p. 45–58 (DOI 10.1016/j.laa.2017.03.013, arXiv 1609.01338, S2CID 119578994)
  10. Townsend et Trefethen 2015

Voir aussi modifier

Bibliographie modifier

  • Choudhury et Horn, « A Complex Orthogonal-Symmetric Analog of the Polar Decomposition », SIAM Journal on Algebraic and Discrete Methods, vol. 8, no 2,‎ , 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,‎ , p. 43–92 (DOI 10.1016/0024-3795(93)00056-6)
  • C. Simon et L. Blume, Mathematics for Economists, Norton, (ISBN 978-0-393-95733-4)

Articles connexes modifier

Liens externes modifier