Přeskočit na obsah

Sylvesterovo kritérium

Z Wikipedie, otevřené encyklopedie
Podrobnější informace naleznete v článku Pozitivně definitní matice.
Symetrická matice je pozitivně definitní, právě když ona i všechny její vedoucí hlavní podmatice mají kladný determinant

Sylvesterovo kritérium pozitivní definitnosti, pojmenované po Jamesi Sylvesterovi, uvádí nutnou a postačující podmínku pro rozhodnutí, zda je komplexní hermitovská matice pozitivně definitní.

Kritérium je možné zobecnit pro určení definitnosti matic, tj. pro rozpoznání pozitivně semidefinitních, negativně definitních, negativně semidefinitních i indefinitních matic.

Znění kritéria[editovat | editovat zdroj]

Hermitovská matice je pozitivně definitní právě když má všechny vedoucí hlavní subdeterminanty kladné.

Konkrétně, pro matici

mají být kladné determinanty:

.

Kritérium platí v nezměněné formě pro reálné symetrické matice, protože tyto matice jsou speciálním případem hermitovských matic.

Použitím vhodné permutace na řádky i sloupce matice lze ukázat, je pozitivně definitní, právě když subdeterminanty v libovolné posloupnosti do sebe vnořených hlavních podmatic matice jsou všechny kladné.

Ukázky[editovat | editovat zdroj]

Reálná symetrická matice

je pozitivně definitní, protože

a .

Namísto všech vedoucích hlavních podmatic by bylo možné použít i jinou posloupnost tří do sebe vnořených hlavních podmatic, např.

a .

Naopak matice

není pozitivně definitní, protože alespoň jeden z determinantů vedoucích hlavních podmatic není kladný:

a

Matice zároveň ilustruje nutnost vzít do sebe vnořené hlavní podmatice. Kdyby namísto uvedené matice řádu 2 byla použita jiná hlavní podmatice, jejíž determinant je:

,

byly by všechny determinanty tří hlavních podmatic různých řádů kladné, ale přesto matice není pozitivně definitní.

Zobecnění[editovat | editovat zdroj]

Pozitivně semidefinitní matice[editovat | editovat zdroj]

Pozitivně semidefinitní matice lze charakterizovat analogicky:

Hermitovská matice je pozitivně semidefinitní, právě když má všechny hlavní subdeterminanty nezáporné.

Oproti pozitivně definitním maticím nestačí uvážit pouze hlavních vedoucích subdeterminantů, ale je třeba otestovat všech vedoucích subdeterminantů.

Ukázky[editovat | editovat zdroj]

Reálná symetrická matice

je pozitivně semidefinitní, protože

a .

Reálná symetrická matice.

má hodnoty vedoucích hlavních subdeterminantů nezáporné:

a

Tento výpočet ovšem není dostatečný pro test pozitivní semidefinitnosti matice . Pro vektor platí: , čili matice není pozitivně semidefinitní.

Negativně (semi)definitní matice[editovat | editovat zdroj]

Hermitovská matice je negativně definitní právě když znaménko každého vedoucího hlavního subdeterminantu řádu je .

U negativně semidefinitních matic je třeba otestovat všech vedoucích subdeterminantů, jejichž znaménko musí být buď nebo , kde je řád subdeterminantu.

V ostatních případech je matice indefinitní.

Idea důkazu[editovat | editovat zdroj]

Dopřednou implikaci lze dokázat například následujícím způsobem: Je-li hermitovská řádu pozitivně definitní a je její vedoucí hlavní podmatice řádu , potom je také pozitivně definitní, protože libovolný nenulový vektor lze doplnit nulami na nenulový vektor , pro nějž pak platí:

Pozitivně definitní matice mají kladný determinant, kupříkladu protože mají všechna vlastní čísla kladná anebo protože mají své odmocniny (viz. též Choleského rozklad).

Pro obrácenou implikaci je možné využít algoritmus pro výpočet Choleského rozkladu . Ten by selhal jen v případě, kdy by některý prvek na diagonále byl dán odmocninou z nekladného čísla . V tuto chvíli vypočtený rozklad by měl splňovat i pro vedoucí hlavní podmatice matic a řádu . Pokud by , nastal by v takovém případě spor s předpokladem, že matice má kladný determinant, protože jej lze podle věty o determinantu součinu matic vyjádřit výrazem:

Kromě uvedeného argumentu lze podat i přímý ale pracný důkaz matematickou indukcí, jenž je založen na výpočtu signatury kvadratické formy Gaussovou eliminací upravenou pro řádky i sloupce.

Numerické záležitosti[editovat | editovat zdroj]

Při výpočtu všech determinantů zároveň Gaussovou eliminací, při níž je zakázáno měnit pořadí řádků, lze spočítat všechny determinanty v čase , což je asymptoticky stejně rychlé jako test pozitivní definitnosti pomocí Choleského rozkladu.

Pokud by byl každý determinant počítán zvlášť, vychází časová složitost pro test pozitivně definitních matic.

Složitost testu pozitivně semidefinitních matic prostřednictvím Sylvestreova kritéria je , a proto je vhodnější použít jiné postupy.

Odkazy[editovat | editovat zdroj]

Reference[editovat | editovat zdroj]

V tomto článku byly použity překlady textů z článků Sylvestrovo kritérium na slovenské Wikipedii a Sylvester's criterion na anglické Wikipedii.

Literatura[editovat | editovat zdroj]

  • BEČVÁŘ, Jindřich. Lineární algebra. 1. vyd. Praha: Matfyzpress, 2019. 436 s. ISBN 978-80-7378-392-1. 
  • HLADÍK, Milan. Lineární algebra (nejen) pro informatiky. 1. vyd. Praha: Matfyzpress, 2019. 328 s. ISBN 978-80-7378-378-5. 
  • OLŠÁK, Petr. Lineární algebra [online]. Praha: 2007 [cit. 2023-02-20]. Dostupné online. 
  • JUKL, Marek. Bilineární a kvadratické formy. In: Olomouc: Univerzita Palackého, Přírodovědecká fakulta, 2000. Dostupné online. ISBN 80-244-0170-3. S. 53–57.

Související články[editovat | editovat zdroj]