Macierz P.
W matematyce , A -Matrix lub matryca jest prawdziwe kwadratowych macierzy , którego głównym nieletni są ściśle dodatni . Niektórzy autorzy określają te macierze jako całkowicie pozytywne .
P.{\ displaystyle \ mathbf {P}}P.{\ displaystyle \ mathbf {P}}
W -matrices udział w badaniu problemów liniowych komplementarności .
P.{\ displaystyle \ mathbf {P}}
Podobnym pojęciem jest -matrix .
P.0{\ displaystyle \ mathbf {P_ {0}}}
Notacje
Zauważamy
-
[[1,nie]]: ={1,...,nie}{\ Displaystyle [\! [1, n] \!]: = \ {1, \ ldots, n \}}zbiór pierwszych liczb całkowitych,nie{\ displaystyle n}
-
u⋅v{\ displaystyle u \ cdot v}produkt Hadamarda z dwóch wektorów a , który jest określony przez dla każdego wskaźnika ,u{\ displaystyle u}v{\ displaystyle v}(u⋅v)ja=ujavja,{\ displaystyle (u \ cdot v) _ {i} = u_ {i} v_ {i},}ja{\ displaystyle i}
-
Mjajot{\ displaystyle M_ {IJ}}podmacierz utworzona przez jej elementy z indeksami wierszy w i indeksami kolumn w .M{\ displaystyle M}ja{\ displaystyle I}jot{\ displaystyle J}
Definicje
Pojęcie -matrix można zdefiniować na różne sposoby, oczywiście równoważne.
P.{\ displaystyle \ mathbf {P}}
P.{\ displaystyle \ mathbf {P}}-macierz - mówimy, że prawdziwa macierz kwadratowa jest -matrycą, jeśli zachodzi jedna z następujących równoważnych właściwości:
M∈Rnie×nie{\ Displaystyle M \ in \ mathbb {R} ^ {n \ razy n}}P.{\ displaystyle \ mathbf {P}}
- Wszystkie główne nieletni z są absolutnie pozytywne: za każdy niepusty,M{\ displaystyle M}ja⊂{1,...,nie}{\ Displaystyle I \ podzbiór \ {1, \ ldots, n \}}detMjaja>0,{\ displaystyle \ det M_ {II}> 0,}
- każdy spełniający wektor równa się zero,x∈Rnie{\ Displaystyle x \ in \ mathbb {R} ^ {n}}x⋅(Mx)⩽0{\ Displaystyle x \ cdot (Mx) \ leqslant 0}
- dla każdej niepusty, rzeczywiste wartości własne miejsca są absolutnie pozytywne.ja⊂{1,...,nie}{\ Displaystyle I \ podzbiór \ {1, \ ldots, n \}}Mjaja{\ displaystyle M_ {II}}
Oznaczamy zbiór -matrices dowolnej kolejności. -Matyczność nazywamy właściwością macierzy, do której ma należećP.{\ displaystyle \ mathbf {P}}P.{\ displaystyle \ mathbf {P}}P.{\ displaystyle \ mathbf {P}}P..{\ displaystyle \ mathbf {P}.}
Nazwę tych matryc zaproponowali Fiedler i Pták (1966). Równoważność między definicjami 1 i 2 wynika z Fiedler i Pták (1962).
Natychmiastowe właściwości
Wyprowadzamy to z definicji 1
-
M∈P.{\ displaystyle M \ in \ mathbf {P}}jeśli i tylko wtedy ,M⊤∈P.{\ displaystyle M ^ {\ top \!} \ in \ mathbf {P}}
- jeśli jest symetryczny, to wtedy i tylko wtedy, gdy jest określony dodatnio ,M{\ displaystyle M}M∈P.{\ displaystyle M \ in \ mathbf {P}}M{\ displaystyle M}
-
P.∩Rnie×nie{\ Displaystyle \ mathbf {P} \ czapka \ mathbb {R} ^ {n \ razy n}}jest otwarta z .Rnie×nie{\ displaystyle \ mathbb {R} ^ {n \ razy n}}
Wyprowadzamy to z definicji 2
- jeśli jest określony pozytywnie , toM+M⊤{\ displaystyle M + M ^ {\! \ top \!}}M∈P..{\ Displaystyle M \ in \ mathbf {P}.}
Inne właściwości
Liniowa komplementarność
Liniowy problem komplementarności polega na znalezieniu takiego wektora , że iw tej definicji jest transpozycją, a nierówności muszą być rozumiane składnik po składniku. Ten problem jest czasami zauważany zwięźle w następujący sposób
x⩾0,{\ displaystyle x \ geqslant 0,}Mx+q⩾0{\ displaystyle Mx + q \ geqslant 0}x⊤(Mx+q)=0.{\ Displaystyle x ^ {\! \ top \!} (Mx + q) = 0}M∈Rnie×nie,{\ Displaystyle M \ in \ mathbb {R} ^ {n \ razy n},} q∈Rnie,{\ Displaystyle q \ in \ mathbb {R} ^ {n},} x⊤{\ Displaystyle x ^ {\! \ do góry \!}}x{\ displaystyle x}
CL(M,q)0⩽x⊥(Mx+q)⩾0.{\ Displaystyle {\ mbox {CL}} (M, q) \ qquad 0 \ leqslant x \ perp (Mx + q) \ geqslant 0.}
Istnienie i niepowtarzalność rozwiązania
Znaczenie -macierzy w zagadnieniach liniowej komplementarności wynika z następującego wyniku istnienia i wyjątkowości.
P.{\ displaystyle \ mathbf {P}}
P.{\ displaystyle \ mathbf {P}}-macierz i problem komplementarności liniowej - W przypadku macierzy następujące właściwości są równoważne:
M∈Rnie×nie{\ Displaystyle M \ in \ mathbb {R} ^ {n \ razy n}}
-
M∈P.{\ displaystyle M \ in \ mathbf {P}},
- dla dowolnego wektora problem liniowej komplementarności ma jedno i tylko jedno rozwiązanie.q∈Rnie{\ displaystyle q \ in \ mathbb {R} ^ {n}}CL(M,q){\ displaystyle {\ mbox {CL}} (M, q)}
Dlatego też, jeśli istnieje taki wektor , że zachodzi jedna z dwóch wykluczających się sytuacji:
M∉P.{\ displaystyle M \ notin \ mathbf {P}}q∈Rnie{\ displaystyle q \ in \ mathbb {R} ^ {n}}
- albo nie ma rozwiązania,CL(M,q){\ displaystyle {\ mbox {CL}} (M, q)}
- lub ma więcej niż jedno rozwiązanie.CL(M,q){\ displaystyle {\ mbox {CL}} (M, q)}
Nie można jednak stwierdzić, że dla macierzy , nawet symetrycznej i nie zdegenerowanej , istnieje taki wektor , że zachodzi pierwsza z dwóch powyższych sytuacji. Więc
M∉P.{\ displaystyle M \ notin \ mathbf {P}}q{\ displaystyle q}
M=(1221){\ displaystyle M = {\ początek {pmatrix} 1 i 2 \\ 2 i 1 \ koniec {pmatrix}}}
nie jest matrycą, ale problem ma jakieś rozwiązanieP.{\ displaystyle \ mathbf {P}}CL(M,q){\ displaystyle {\ mbox {CL}} (M, q)}q.{\ displaystyle q.}
Charakterystyka algorytmiczna
Komplementarność liniowa oferuje inną charakterystykę -macierzy, pod względem właściwości algorytmu do rozwiązywania tych problemów, algorytmu Newtona-min . Jest to dobrze określone, gdy matryca nie jest zdegenerowana . Do takiej matrycy i danym wektorze , można skojarzyć z zestawu wskaźników , a oznaczony węzła , który jest unikalne rozwiązanie układu liniowego
P.{\ displaystyle \ mathbf {P}}M{\ displaystyle M}q{\ displaystyle q}ja⊂[[1,nie]]{\ Displaystyle I \ podzbiór [\! [1, n] \!]}x(ja){\ Displaystyle x ^ {(I)}}x{\ displaystyle x}
xjavs=0i(Mx+q)ja=0.{\ displaystyle x_ {ja ^ {c}} = 0 \ qquad {\ mbox {i}} \ qquad (Mx + q) _ {I} = 0}
Zauważyliśmy uzupełnienie w . Krótko mówiąc, algorytm Newtona-min jest półgładkim algorytmem Newtona do rozwiązywania równania liniowego fragmentarycznie
javs: =[[1,nie]]∖ja{\ Displaystyle I ^ {c}: = [\! [1, n] \!] \ setminus I}ja{\ displaystyle I}[[1,nie]]{\ Displaystyle [\! [1, n] \!]}
min(x,Mx+q)=0,{\ Displaystyle \ min (x, Mx + q) = 0,}
co jest równoznaczne z problemem . W wersji, która ma znaczenie w poniższym wyniku, algorytm Newtona-min najpierw określa, w bieżącym momencie , zbiór wskaźników
CL(M,q){\ displaystyle {\ mbox {CL}} (M, q)}x∈Rnie{\ Displaystyle x \ in \ mathbb {R} ^ {n}}
ja={ja∈[[1,nie]]:xja>(Mx+q)ja}{\ Displaystyle I = \ {i \ w [\! [1, n] \!]: x_ {i}> (Mx + q) _ {i} \}}
a następnie oblicza następną iterację . Mamy następującą charakterystykę (Twierdzenie 4.2 w []).
x+=x(ja){\ Displaystyle x ^ {+} = x ^ {(I)}}
P.{\ displaystyle \ mathbf {P}}-macierz i algorytm Newtona-min - W przypadku macierzy niezdegenerowanej następujące właściwości są równoważne:
M∈Rnie×nie{\ Displaystyle M \ in \ mathbb {R} ^ {n \ razy n}}
-
M∈P.{\ displaystyle M \ in \ mathbf {P}},
- Niezależnie od tego algorytm Newtona-min opisany powyżej nie przełącza się między dwoma węzłami, gdy jest używany do rozwiązywania .q{\ displaystyle q}CL(M,q){\ displaystyle {\ mbox {CL}} (M, q)}
Rozdzielczość czasowa wielomianu?
Nie znamy algorytmu, który pozwoliłby rozwiązać problem w czasie wielomianowym, kiedy , ale niektórzy zaproponowali argumenty przemawiające za taką możliwością.
CL(M,q){\ displaystyle {\ mbox {CL}} (M, q)}M∈P.{\ displaystyle M \ in \ mathbf {P}}
Sprawdź macierz P.
Sprawdzenie, czy macierz podana w jest -macierz jest problemem co-NP-zupełnym .
Qnie×nie{\ displaystyle \ mathbb {Q} ^ {n \ razy n}}P.{\ displaystyle \ mathbf {P}}
Oczywistym sposobem sprawdzenia matyczności P danej macierzy jest obliczenie jej głównych nieletnich ( test głównych nieletnich ), co wymaga operacji. Rump (2003) wykazał, że niezależnie od tego, co niepuste, możemy znaleźć macierz taką, która i dla każdego niepustego i różnego od , tak, że główny test podrzędny nie może pominąć żadnego z drugorzędnych.
M{\ displaystyle M}2nie-1{\ Displaystyle 2 ^ {n} -1}O(nie32nie){\ Displaystyle O (n ^ {3} \, 2 ^ {n})}ja⊂[[1,nie]]{\ Displaystyle I \ podzbiór [\! [1, n] \!]}M∈Rnie×nie{\ Displaystyle M \ in \ mathbb {R} ^ {n \ razy n}}detMjaja<0{\ displaystyle \ det M_ {II} <0}detMjotjot>0{\ displaystyle \ det M_ {JJ}> 0}jot⊂[[1,nie]]{\ Displaystyle J \ podzbiór [\! [1, n] \!]}ja{\ displaystyle I}
Tsatsomeros i Li (2000) zaproponowali test oparty na uzupełnieniu Schura , który redukuje liczbę operacji do . Test nadal wymaga tej wykładniczej liczby operacji, jeśli macierz jest macierzą P , ale może wymagać znacznie mniej , ponieważ tylko jedna ujemna liczba mniejsza jest wystarczająca, aby wykazać brak członkostwa.
72nie{\ Displaystyle 7 \, 2 ^ {n}}M∉P.{\ displaystyle M \ notin \ mathbf {P}}
Rump (2003) zaproponował pierwszy test, który niekoniecznie wymaga wykładniczej liczby operacji w celu zweryfikowania P- matyczności.
Przykłady
- Cauchy- matryca jest kwadratem rzeczywistym macierzy, którego elementem jest przezVS∈Rnie×nie{\ Displaystyle C \ in \ mathbb {R} ^ {n \ razy n}}(ja,jot){\ displaystyle (i, j)}
VSjajot=1wja+bjot,{\ Displaystyle \ Displaystyle C_ {ij} = {\ Frac {1} {a_ {i} + b_ {j}}},}
gdzie . Macierz Cauchy'ego jest -matrycą, jeśli i jeśli sekwencje i są ściśle rosnące. W szczególności macierz Hilberta jest -matrycą (jest to macierz Cauchy'ego ze wszystkim ).wja+bjot≠0{\ displaystyle a_ {i} + b_ {j} \ neq 0}P.{\ displaystyle \ mathbf {P}}w1+b1>0{\ displaystyle a_ {1} + b_ {1}> 0}{wja}{\ displaystyle \ {a_ {i} \}}{bjot}{\ displaystyle \ {b_ {j} \}}P.{\ displaystyle \ mathbf {P}}wja=bja=ja-1/2{\ displaystyle a_ {i} = b_ {i} = i-1/2}ja∈[[1,nie]]{\ Displaystyle ja \ w [\! [1, n] \!]}
- Rozważmy krążącą macierz zdefiniowaną przezM∈Rnie×nie,{\ Displaystyle M \ in \ mathbb {R} ^ {n \ razy n},} nie⩾2,{\ displaystyle n \ geqslant 2,}
M=(1αα ⋱ ⋱ 1α1){\ Displaystyle M = {\ rozpocząć {pmatrix} 1 &&& \ alpha \\\ alpha & ~~~ \ ddots ~~~ && \\ & ~~~ \ ddots ~~~ & 1 & \\ && \ alpha & 1 \ end {pmatrix}}}
a dokładniej przez to , czy , jeśli i jeśli nie. WięcMjajot=1{\ displaystyle M_ {ij} = 1}ja=jot{\ displaystyle i = j}Mjajot=α{\ displaystyle M_ {ij} = \ alpha}ja=(jotmodnie)+1{\ Displaystyle i = (j \ mod n) +1}Mjajot=0{\ displaystyle M_ {ij} = 0}
- Jeśli jest parzysta, to wtedy i tylko wtedy , gdynie{\ displaystyle n}M∈P.{\ displaystyle M \ in \ mathbf {P}}|α|<1{\ Displaystyle | \ alfa | <1}
- jeśli jest dziwne, to wtedy i tylko wtedy, gdy .nie{\ displaystyle n}M∈P.{\ displaystyle M \ in \ mathbf {P}}α>-1{\ displaystyle \ alpha> -1}
- Rozważmy krążącą macierz zdefiniowaną przezM∈Rnie×nie,{\ Displaystyle M \ in \ mathbb {R} ^ {n \ razy n},} nie⩾3,{\ Displaystyle n \ geqslant 3,}
M=(1β αα ⋱ ββ ⋱ 1 ⋱ α 1 β α 1){\ Displaystyle M = {\ rozpocząć {pmatrix} 1 &&& \ beta ~~~ & \ alpha \\\ alpha & ~~~ \ ddots ~~~ &&& \ beta \\\ beta & ~~~ \ ddots ~~~ & 1 ~~~ & \\ & ~~~ \ ddots ~~~ & \ alpha ~~~ & 1 ~~~ \\ && \ beta ~~~ & \ alpha ~~~ & 1 \ end {pmatrix}} }
a dokładniej przez
Mjajot={1gdyby ja=jotαgdyby ja=(jotmodnie)+1βgdyby ja=((jot+1)modnie)+10Jeśli nie.{\ Displaystyle M_ {ij} = \ lewo \ {{\ początek {tablica} {ll} 1 & {\ mbox {si}} ~ i = j \\\ alfa i {\ mbox {si}} ~ i = ( j \ mod n) +1 \\\ beta & {\ mbox {si}} ~ i = ((j + 1) \ mod n) +1 \\ 0 & {\ mbox {w przeciwnym razie}}. \ end {array }} \ right.}
Więc jeśli lub jeśli .M∈P.{\ displaystyle M \ in \ mathbf {P}}|α|-1<β<|α|/4{\ Displaystyle | \ alfa | -1 <\ beta <| \ alfa | / 4}α2+8(β-12)2<2{\ Displaystyle \ alpha ^ {2} +8 (\ beta - {\ textstyle {\ Frac {1} {2}}}) ^ {2} <2}
Załączniki
Uwagi
-
Definicja 1.12, strona 20, w: Berman i Shaked-Monderer (2003).
-
(w) Pan Fiedler, Pták V. (1966). Pewne uogólnienia pozytywnej określoności i monotoniczności. Numerische Mathematik , 9, 163–172.
-
(w) Pan Fiedler, Pták V. (1962). Na macierzach z niepozytywnymi elementami poza przekątnymi i głównymi nieletnimi. Czechoslovak Mathematics Journal , 12, 382–400.
-
(w) H. Samelson, RM Thrall, Wesler O. (1958). Twierdzenie o podziale dla euklidesowej przestrzeni n. Proceedings of the American Mathematical Society , 9, 805–807.
-
(w) I. Ben Gharbia, J.Ch. Gilbert (2012). Algorytmiczna charakterystyka -materii. SIAM Journal on Matrix Analysis and Applications (w przygotowaniu). Raport badawczy INRIA RR-8004 .P.{\ displaystyle \ mathbf {P}}
-
(w) W. Morris (2002). Randomizowane algorytmy pivot dla problemów liniowej komplementarności macierzy P.
Programowanie matematyczne , 92A, 285–296. doi
-
(en) N. Megiddo (1988). Uwaga na temat złożoności LCP macierzy P i obliczania równowagi. Raport techniczny RJ 6439 (62557). IBM Research, Almaden Research Center, 650 Harry Road, San Jose, Kalifornia, USA.
-
(w) D. Solow R. Stone, CA Tovey (1987). Rozwiązywanie LCP na matrycach P prawdopodobnie nie jest NP-trudne. Niepublikowana notatka.
-
(w) GE Coxson (1994). Problem macierzy P jest co-NP-kompletny. Programowanie matematyczne , 64, 173–178. doi
-
Twierdzenie Rump'a 2.2 (2003).
-
MJ Tsatsomeros, L. Li (2000). Test rekurencyjny dla macierzy P. MOP , 40, 410–414.
-
Przykład 1.7, strona 20, w: Berman i Shaked-Monderer (2003).
-
(en) I. Ben Gharbia, J.Ch. Gilbert (2012). Niezbieżność zwykłego algorytmu Newtona-min dla problemów liniowej komplementarności z macierzą P. Programowanie matematyczne , 134, 349–364. link doi Zentralblatt MATH
Powiązane artykuły
Bibliografia
-
(en) A. Berman, N. Shaked-Monderer (2003). Matryce całkowicie pozytywne . World Scientific, River Edge, NJ, USA.
-
(en) RW Cottle, J.-S. Pang, RE Stone (2009). Problem liniowej komplementarności . Classics in Applied Mathematics 60. SIAM, Filadelfia, PA, USA.
-
(en) RA Horn, Ch. R. Jonhson (1991). Tematy w analizie macierzy . Cambridge University Press, Nowy Jork, NY, USA.
-
(en) SM Rump (2003). Mamy matryce P. Algebra liniowa i jej zastosowania , 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;">