P-matrice

În matematică , o -matrice sau matrice este o matrice pătrată reală a cărei minori principal sunt strict pozitive . Unii autori califică aceste matrice ca fiind total strict pozitive .

Cele -matrices implicate în studiul problemelor liniare complementaritate .

O noțiune înrudită este aceea de -matrix .

Notări

Observăm

Definiții

Noțiunea de -matrice poate fi definită în diferite moduri, desigur echivalent.

-matrix  -  Spunem că o matrice pătrată reală este o -matrix dacă deține una dintre următoarele proprietăți echivalente:

  1. toate minorii majore ale sunt strict pozitive: pentru orice non-gol,
  2. orice vector care îndeplinește este zero,
  3. pentru orice non-gol, valorile proprii reale ale sunt strict pozitive.

Notăm setul de -matrici de orice ordine. Numim -matricitate proprietatea unei matrice de a aparține

Numele acestor matrice a fost propus de Fiedler și Pták (1966). Echivalența dintre definițiile 1 și 2 se datorează lui Fiedler și Pták (1962).

Proprietăți imediate

Din definiția 1, deducem că

Din definiția 2, deducem că

Alte proprietăți

Complementaritatea liniară

O problemă de complementaritate liniară constă în găsirea unui vector astfel încât și În această definiție, este transpunerea și inegalitățile trebuie înțelese componentă cu componentă. Această problemă este uneori observată compact, după cum urmează

Existența și unicitatea soluției

Importanța -matricelor în problemele de complementaritate liniară provine din următoarea existență și rezultat unic.

-problema de complementaritate matricială și liniară  -  Pentru o matrice , următoarele proprietăți sunt echivalente:

  • ,
  • pentru orice vector , problema complementarității liniare are o singură soluție.

Prin urmare, dacă există un vector astfel încât să apară una dintre următoarele două situații exclusive:

  • fie nu are nicio soluție,
  • sau are mai multe soluții.

Cu toate acestea, nu se poate afirma că, pentru o matrice , chiar simetrică și nu degenerată , există un vector astfel încât să aibă loc prima dintre cele două situații de mai sus. Asa de

nu este o matrice, dar problema are orice soluție

Caracterizarea algoritmică

Complementaritatea liniară oferă o altă caracterizare a -matricilor, în termeni de proprietate a unui algoritm pentru rezolvarea acestor probleme, algoritmul Newton-min . Acest lucru este bine definit atunci când matricea nu este degenerată . Pentru o astfel de matrice și un vector dat, se poate asocia cu un set de indici , un nod notat care este soluția unică a sistemului liniar

Am remarcat complementul in . Pe scurt, algoritmul lui Newton-min este algoritmul lui Newton semi-neted pentru a rezolva ecuația liniară în bucăți

ceea ce echivalează cu problema . În versiunea care contează în rezultatul de mai jos, algoritmul Newton-min determină mai întâi, la punctul curent , setul de indici

și apoi calculează următoarea iterație . Avem următoarea caracterizare (Teorema 4.2 în []).

-matricea și algoritmul lui Newton-min  -  Pentru o matrice nedegenerată , următoarele proprietăți sunt echivalente:

  • ,
  • Indiferent , algoritmul Newton-min descris mai sus nu circulă între două noduri atunci când este utilizat pentru a rezolva .
Rezoluția timpului polinomial?

Nu știm un algoritm care să permită rezolvarea problemei în timp polinomial , dar unii au propus argumente în favoarea acestei posibilități.

Verificați matricea P

Verificarea că o matrice dată în este un -matrix este o problemă de co-NP-complete .

O modalitate evidentă de a verifica matricitatea P a unei matrici date este calcularea minorilor săi principali ( testul minorilor majori ), care necesită operații. Rump (2003) a arătat că, indiferent de non - gol, putem găsi o matrice astfel încât și pentru orice non-vid și diferită de , astfel încât testul principal minor nu poate neglija niciun minor.

Tsatsomeros și Li (2000) au propus un test, bazat pe complementul lui Schur , care reduce numărul de operații la . Testul necesită în continuare acest număr exponențial de operații dacă matricea este o matrice P , dar poate necesita mult mai puțin dacă , pentru că este suficient doar un minor negativ pentru a arăta această neacțiune.

Rump (2003) a propus primul test care nu necesită în mod necesar un număr exponențial de operații pentru a verifica matricitatea P.

Exemple

  1. O matrice Cauchy este o matrice pătrată reală al cărei element este dat de unde . O matrice Cauchy este o matrice dacă și dacă secvențele și sunt strict în creștere. În special, o matrice Hilbert este o matrice (este o matrice Cauchy cu pentru toate ).
  2. Luați în considerare matricea circulantă definită de sau mai exact prin dacă , dacă și dacă nu. Asa de
    • Dacă este egal, atunci dacă și numai dacă ,
    • dacă este ciudat, atunci dacă și numai dacă .
  3. Luați în considerare matricea circulantă definită de sau mai precis de Deci dacă sau dacă .

Anexe

Note

  1. Definiție 1.12, pagina 20, în Berman și Shaked-Monderer (2003).
  2. (în) Domnul Fiedler, Pták V. (1966). Unele generalizări ale definirii și monotoniei pozitive. Numerische Mathematik , 9, 163–172.
  3. (în) Domnul Fiedler, Pták V. (1962). Pe matrici cu elemente non-pozitive în afara diagonalei și minori principali. Jurnalul cehoslovac de matematică , 12, 382–400.
  4. (în) H. Samelson, RM Thrall, Wesler O. (1958). O teoremă de partiție pentru spațiul n euclidian. Proceedings of the American Mathematical Society , 9, 805–807.
  5. (în) I. Ben Gharbia, J.Ch. Gilbert (2012). O caracterizare algoritmică a -matricității. SIAM Journal on Matrix Analysis and Applications (viitoare). Raport de cercetare INRIA RR-8004 .
  6. (în) W. Morris (2002). Algoritmi pivot aleatori pentru probleme de complementaritate liniară cu matrice P. Programare matematică , 92A, 285–296. doi
  7. (ro) N. Megiddo (1988). O notă despre complexitatea LCP cu matrice P și calculul unui echilibru. Raport tehnic RJ 6439 (62557). IBM Research, Almaden Research Center, 650 Harry Road, San Jose, CA, SUA.
  8. (în) D. Solow R. Stone, CA Tovey (1987). Rezolvarea LCP pe matrice P nu este probabil NP-hard. Notă nepublicată.
  9. (în) GE Coxson (1994). Problema matricei P este co-NP-completă. Programare matematică , 64, 173–178. doi
  10. Teorema lui Rump 2.2 (2003).
  11. MJ Tsatsomeros, L. Li (2000). Un test recurciv pentru matrice P. OIM , 40, 410–414.
  12. Exemplul 1.7, pagina 20, în Berman și Shaked-Monderer (2003).
  13. (ro) I. Ben Gharbia, J.Ch. Gilbert (2012). Non-convergența algoritmului simplu Newton-min pentru probleme de complementaritate liniară cu o matrice P. Programare matematică , 134, 349-364. doi Zentralblatt link   MATH

Articole similare

Bibliografie

  • (ro) A. Berman, N. Shaked-Monderer (2003). Matrice complet pozitive . World Scientific, River Edge, NJ, SUA.
  • (ro) RW Cottle, J.-S. Pang, RE Stone (2009). Problema complementarității liniare . Clasici în matematică aplicată 60. SIAM, Philadelphia, PA, SUA.
  • (ro) RA Horn, Ch. R. Jonhson (1991). Subiecte în analiza matricială . Cambridge University Press, New York, NY, SUA.
  • (ro) SM Rump (2003). Noi P-matrici. Algebra liniară și aplicațiile sale , 363, 237–250.
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">