M-matrice

En mathématiques, une M-matrice est une matrice carrée réelle qui est à la fois une P-matrice et une Z-matrice, ce qui signifie que tous ses mineurs principaux sont strictement positifs et que ses éléments extra-diagonaux sont négatifs. D'autres caractérisations peuvent être utilisées, dont certaines sont données ci-dessous.

Ces matrices interviennent dans l'étude des problèmes de complémentarité linéaire et dans certaines discrétisations d'opérateurs différentiels, en particulier ceux obéissant à un principe du maximum, comme le laplacien.

Cette classe de matrices semble avoir été introduite par Alexander Ostrowski en référence à Hermann Minkowski[1].

Définitions

La notion de M-matrice peut se définir de différentes manières, bien sûr équivalentes. On utilise ci-dessous les notions de Z-matrice, de P-matrice et de S-matrice.

M-matrice — On dit qu'une matrice carrée réelle M ∈ R n × n {\displaystyle M\in \mathbb {R} ^{n\times n}} est une M-matrice si c'est une Z-matrice et si l'une des propriétés équivalentes suivantes est vérifiée, équivalentes sous l'hypothèse que M ∈ Z {\displaystyle M\in \mathbf {Z} }  :

  1. M ∈ P {\displaystyle M\in \mathbf {P} } ,
  2. M ∈ S {\displaystyle M\in \mathbf {S} } ,
  3. M {\displaystyle M} est inversible et M − 1 ⩾ 0 {\displaystyle M^{-1}\geqslant 0} (tous les éléments de son inverse sont positifs),
  4. toutes les valeurs propres de M {\displaystyle M} ont une partie réelle strictement positive.

On note M l'ensemble des M-matrices d'ordre quelconque. On appelle M-matricité la propriété d'une matrice d'appartenir à M.

Propriétés

Algèbre linéaire

Les facteurs LU d'une M-matrice existent et peuvent être calculés de manière stable, sans pivotage. Cette propriété a également lieu pour la factorisation LU incomplète.

Complémentarité linéaire

Un problème de complémentarité linéaire consiste à trouver un vecteur x ⩾ 0 , {\displaystyle x\geqslant 0,} tel que M x + q ⩾ 0 {\displaystyle Mx+q\geqslant 0} et x ⊤ ( M x + q ) = 0. {\displaystyle x^{\!\top \!}(Mx+q)=0.} Dans cette définition, M ∈ R n × n , {\displaystyle M\in \mathbb {R} ^{n\times n},} q ∈ R n , {\displaystyle q\in \mathbb {R} ^{n},} x ⊤ {\displaystyle x^{\!\top \!}} est le transposé de x {\displaystyle x} et les inégalités doivent se comprendre composante par composante. Ce problème est parfois noté de manière compacte comme suit

CL ( M , q ) 0 ⩽ x ⊥ ( M x + q ) ⩾ 0. {\displaystyle {\mbox{CL}}(M,q)\qquad 0\leqslant x\perp (Mx+q)\geqslant 0.}

L'ensemble admissible de ce problème est noté

Adm ( M , q ) := { x ∈ R n : x ⩾ 0 ,   M x + q ⩾ 0 } . {\displaystyle {\mbox{Adm}}(M,q):=\{x\in \mathbb {R} ^{n}:x\geqslant 0,~Mx+q\geqslant 0\}.}

L'importance des M-matrices dans les problèmes de complémentarité linéaire provient du résultat suivant.

M-matrice et problème de complémentarité linéaire — Pour une matrice M ∈ R n × n {\displaystyle M\in \mathbb {R} ^{n\times n}} , les propriétés suivantes sont équivalentes :

  1. M ∈ M {\displaystyle M\in \mathbf {M} } ,
  2. pour tout q {\displaystyle q} , Adm ⁡ ( M , q ) {\displaystyle \operatorname {Adm} (M,q)} contient un minimum (pour l'ordre ⩽ {\displaystyle \leqslant } de R n {\displaystyle \mathbb {R} ^{n}} ) qui est l'unique solution de CL ⁡ ( M , q ) {\displaystyle \operatorname {CL} (M,q)} ,
  3. pour tous vecteurs q 1 ⩽ q 2 {\displaystyle q^{1}\leqslant q^{2}} , les solutions x ¯ i {\displaystyle {\bar {x}}^{i}} de CL ⁡ ( M , q i ) {\displaystyle \operatorname {CL} (M,q^{i})} vérifient x ¯ 1 ⩾ x ¯ 2 {\displaystyle {\bar {x}}^{1}\geqslant {\bar {x}}^{2}} .

Annexes

Notes

  1. ↑ (en) Pages 134, 161 (théorème 2.3 et note 6.1 du chapitre 6) chez Bermon et Plemmons (1994).

Articles connexes

Bibliographie

  • (en) A. Bermon, R.J. Plemmons (1994). Nonnegative Matrices in the Mathematical Sciences. Society for Industrial and Applied Mathematics, Philadelphie, USA. (ISBN 0898713218).
  • (en) R. W. Cottle, J.-S. Pang, R. E. Stone (2009). The linear complementarity problem. Classics in Applied Mathematics 60. SIAM, Philadelphia, PA, USA.
  • (en) R. A. Horn, Ch. R. Jonhson (1991). Topics in Matrix Analysis. Cambridge University Press, New York, NY, USA.
  • icône décorative Portail des mathématiques