Rozklad matice - Matrix decomposition

V matematickém disciplíny lineární algebry , je matice rozkladu nebo matice faktorizace je faktorizace z matrice na součin matic. Existuje mnoho různých maticových rozkladů; každý najde uplatnění mezi určitou třídou problémů.

Příklad

V numerické analýze se k implementaci efektivních maticových algoritmů používají různé rozklady .

Například při řešení soustavy lineárních rovnic lze matici A rozložit pomocí LU rozkladu . LU rozklad factorizes matrici do dolní trojúhelníkové matice L a horní trojúhelníkovou matici U . Systémy a vyžadují méně sčítání a násobení k vyřešení, ve srovnání s původním systémem , ačkoli jeden může vyžadovat podstatně více číslic v nepřesné aritmetice, jako je plovoucí desetinná čárka .

Podobně, QR rozklad vyjadřuje A jako QR s Q ortogonální matice a R horní trojúhelníkové matice. Systém Q ( R x ) = b je řešen pomocí R x = Q T b = c a systém R x = c je řešen pomocí „ zpětné substituce “. Počet požadovaných sčítání a násobení je přibližně dvojnásobný než při použití řešení LU, ale v nepřesné aritmetice nejsou vyžadovány žádné další číslice, protože rozklad QR je numericky stabilní .

Dekompozice související s řešením soustav lineárních rovnic

LU rozklad

Snížení LU

Blokovat rozklad LU

Faktorizace pořadí

Choleský rozklad

  • Použitelné pro: čtvercová , hermitská , kladná určitá matice A
  • Decomposition:, kde je horní trojúhelníkový se skutečnými kladnými diagonálními položkami
  • Komentář: je-li matice hermitovská a kladná semitečná, má rozklad formy, pokud je možné, aby byly diagonální položky nulové
  • Jedinečnost: pro pozitivní určité matice je Choleský rozklad jedinečný. Není to však ojedinělý případ v pozitivním semi-definitivním případě.
  • Komentář: pokud je A reálné a symetrické, obsahuje všechny skutečné prvky
  • Komentář: Alternativou je rozklad LDL , který může zabránit extrakci druhé odmocniny.

QR rozklad

  • Použitelné pro: m -by- n matice A s lineárně nezávislými sloupci
  • Decomposition: where is a unitary matrix of size m -by- m , and is a upper triangular matrix of size m -by- n
  • Jedinečnost: Obecně to není jedinečné, ale pokud má úplnou hodnost , existuje singl, který má všechny kladné diagonální prvky. Pokud je čtverec, je také jedinečný.
  • Komentář: QR rozklad poskytuje efektivní způsob řešení soustavy rovnic . Skutečnost, že je ortogonální, to znamená , takže je ekvivalentní s , což je velmi snadné vyřešit, protože je trojúhelníkové .

RRQR faktorizace

Interpolační rozklad

Dekompozice založené na vlastních číslech a souvisejících pojmech

Vlastní složení

  • Také se nazývá spektrální rozklad .
  • Platí pro: čtvercová matice A s lineárně nezávislými vlastními vektory (nemusí to být nutně odlišné vlastní hodnoty).
  • Rozklad: , kde D je diagonální matice vytvořeny z čísel z A , a sloupce V jsou příslušné vektory z A .
  • Existence: n -by- n matice má vždy n (komplex) vlastní hodnoty, které mohou být objednány (ve více než jedním způsobem), aby se vytvořil n -by- n diagonální matice D a odpovídající matice nenulové sloupce V, který splňuje vlastní číslo rovnice . je invertibilní právě tehdy, je-li n vlastních vektorů lineárně nezávislých (tj. každá vlastní hodnota má geometrickou multiplicitu rovnající se její algebraické multiplicitě ). Postačující (ale není to nutná) podmínka, aby se to stalo, je to, že všechna vlastní čísla jsou různá (v tomto případě je geometrická a algebraická multiplicita rovna 1)
  • Komentář: Vždy lze normalizovat vlastní vektory tak, aby měly délku jedna (viz definice rovnice vlastních čísel)
  • Poznámka: Každý normální matice (tj matice, pro které , kde je konjugát transpozice ) může být eigendecomposed. Pro normální matici A (a pouze pro normální matici) mohou být vlastní vektory vytvořeny také jako orthonormal ( ) a vlastní složka bude číst jako . Zejména všechny unitární , hermitské nebo zkosené-hermitské (v reálném případě všechny ortogonální , symetrické nebo zkosené-symetrické matice) jsou normální, a proto mají tuto vlastnost.
  • Komentář: Pro jakoukoli skutečnou symetrickou matici A vlastní složka vždy existuje a lze ji zapsat jako , kde D i V mají skutečnou hodnotu.
  • Komentář: Vlastní složení je užitečné pro pochopení řešení soustavy lineárních obyčejných diferenciálních rovnic nebo lineárních diferenciálních rovnic. Například, rozdíl rovnice vychází z počátečního stavu je vyřešen , což je ekvivalentní , kde V a D jsou matrice vytvořené z charakteristických vektorů a vlastní čísla A . Vzhledem k tomu, že D je úhlopříčka, zvyšuje ji na sílu , pouze zahrnuje zvednutí každého prvku na úhlopříčce na sílu t . To je mnohem snazší udělat a pochopit, než zvýšit A na moc t , protože A obvykle není diagonální.

Jordanův rozklad

Jordan normální forma a rozklad Jordan-Chevalley

  • Platí pro: čtvercová matice A
  • Komentář: Normální forma Jordan zobecňuje vlastní složení na případy, kdy se opakují vlastní čísla a nelze je diagonalizovat, Jordan-Chevalleyův rozklad to dělá bez volby základu.

Schurův rozklad

Skutečný Schurův rozklad

  • Platí pro: čtvercová matice A
  • Rozklad: Toto je verze Schur rozkladu, kde a obsahovat pouze reálná čísla. Jeden může vždy na disk zapisovat , kde V je skutečný ortogonální matice , je přemístit z V a S je blok horní trojúhelníková matice s názvem skutečné Schur forma . Bloky na úhlopříčce S mají velikost 1 × 1 (v takovém případě představují skutečná vlastní čísla) nebo 2 × 2 (v takovém případě jsou odvozeny od komplexních párů vlastních čísel konjugátu ).

QZ rozklad

  • Také se nazývá: zobecněný Schurův rozklad
  • Platí pro: čtvercové matice A a B
  • Komentář: existují dvě verze tohoto rozkladu: komplexní a skutečná.
  • Dekompozice (komplexní verze): a kde Q a Z jsou jednotné matice , * horní index představuje transpozici konjugátu a S a T jsou horní trojúhelníkové matice.
  • Komentář: ve složitém QZ rozkladu jsou poměry diagonálních prvků S k odpovídajícím diagonálním prvkům T , zobecněná vlastní čísla, která řeší problém zobecněné vlastní hodnoty (kde je neznámý skalár a v je neznámý nenulový vektor).
  • Dekompozice (skutečná verze): a kde A , B , Q , Z , S a T jsou matice obsahující pouze reálná čísla. V tomto případě Q a Z jsou ortogonální matice , horní index T představuje transpozici a S a T jsou blokové horní trojúhelníkové matice. Bloky na úhlopříčce S a T mají velikost 1 × 1 nebo 2 × 2.

Takagiho faktorizace

  • Platí pro čtvercové, komplex, symetrické matice A .
  • Decomposition:, kde D je skutečná nezáporná diagonální matice a V je jednotné . označuje transpozice matice z V .
  • Komentář: Diagonální prvky D jsou nezáporné druhé odmocniny vlastních čísel z .
  • Komentář: V může být složité, i když A je skutečné.
  • Komentář: Nejedná se o speciální případ eigendecomposition (viz výše), který používá místo . Kromě toho, pokud A není reálné, není to Hermitian a použití formuláře také neplatí.

Rozklad singulární hodnoty

  • Platí pro m -by- n matice A .
  • Decomposition:, kde D je nezáporná diagonální matice a U a V splňují . Zde je konjugovat přemístit z V (nebo jednoduše přemístit , pokud V obsahuje pouze reálná čísla), a I označuje matice identity (nějakého rozměru).
  • Komentář: Diagonální prvky D se nazývají singulárních hodnot z A .
  • Komentář: Stejně jako výše uvedený rozklad eigendekompozice zahrnuje rozklad singulární hodnoty hledání základních směrů, podél kterých je násobení matice ekvivalentní skalárnímu násobení, ale má větší obecnost, protože uvažovaná matice nemusí být čtvercová.
  • Jedinečnost: singulární hodnoty jsou vždy jednoznačně určeny. a nemusí být obecně jedinečný.

Měřítko-invariantní rozklady

Odkazuje na varianty stávajících maticových rozkladů, jako je SVD, které jsou neměnné vzhledem k škálování úhlopříčky.

  • Platí pro m -by- n matice A .
  • Jednotka-rozměrově neměnného singulární rozklad: , kde S je unikátní nezáporná diagonální matice z rozměrově neměnného singulárních hodnot, U a V jsou unitární matice , je konjugovat přemístit z V , a pozitivní diagonální matice D a E .
  • Komentář: Je analogický s SVD, kromě toho, že diagonální prvky S jsou invariantní vzhledem k levé a / nebo pravé multiplikaci A libovolnými nesingulárními diagonálními maticemi, na rozdíl od standardního SVD, pro které jsou singulární hodnoty invariantní vzhledem k levé a / nebo pravé násobení A libovolnými unitárními maticemi.
  • Komentář: Je alternativou ke standardnímu SVD kdy neměnnost je nutný vzhledem k Úhlopříčka nikoliv unitární přeměnách A .
  • Jedinečnost: Jednotkové hodnoty invariantní vůči měřítku (dané diagonálními prvky S ) jsou vždy jednoznačně určeny. Diagonální matice D a E a unitární U a V nejsou obecně nutně jedinečné.
  • Komentář: Matice U a V nejsou stejné jako matice ze SVD.

Analogické škálově invariantní rozklady lze odvodit z jiných maticových rozkladů, např. Pro získání vlastních čísel škálovatelných.

Ostatní rozklady

Polární rozklad

  • Platí pro kterékoli pole komplexní matice A .
  • Rozklad: (pravý polární rozklad) nebo (levý polární rozklad), kde U je unitární matice a P a P ' jsou pozitivní semidefinitní hermitovské matice .
  • Jedinečnost: je vždy jedinečná a rovná se (což je vždy poustevník a pozitivní semidefinit). Pokud je invertibilní, pak je jedinečný.
  • Komentář: Jelikož každá hermitovská matice připouští spektrální rozklad s jednotnou maticí, lze ji zapsat jako . Protože je kladný semidefinit, všechny prvky v jsou nezáporné. Vzhledem k tomu, že produkt dvou unitárních matic je unitární, lze brát jeden, což je dekompozice singulární hodnoty. Existence polárního rozkladu je tedy ekvivalentní existenci rozkladu singulární hodnoty.

Algebraický polární rozklad

  • Platí pro čtvercové, komplexní, non-singulární matice A .
  • Decomposition:, kde Q je komplexní ortogonální matice a S je komplexní symetrická matice.
  • Jedinečnost: Pokud nemá žádné záporné reálné vlastní hodnoty, pak je rozklad jedinečný.
  • Komentář: Existence tohoto rozkladu je obdobou podobnosti .
  • Komentář: Varianta tohoto rozkladu je , kde R je skutečná matice a C je kruhová matice .

Mostowův rozklad

  • Platí pro čtvercové, komplexní, non-singulární matice A .
  • Dekompozice:, kde U je unitární, M je skutečné anti-symetrické a S je skutečné symetrické.
  • Komentář: Matici A lze také rozložit, protože kde U 2 je jednotný, M 2 je skutečný anti-symetrický a S 2 je skutečný symetrický.

Sinkhorn normální forma

  • Platí pro: čtvercová reálná matice A s přísně pozitivními prvky.
  • Decomposition:, kde S je dvojnásobně stochastické a D 1 a D 2 jsou skutečné diagonální matice s přísně pozitivními prvky.

Odvětvový rozklad

  • Platí pro: čtvercová, komplexní matice A s číselným rozsahem obsaženým v sektoru .
  • Decomposition:, kde C je invertibilní komplexní matice a se všemi .

Williamsonova normální forma

  • Použitelné pro: čtvercová, kladně určitá reálná matice A s řádem 2 n × 2 n .
  • Rozklad: , kde je symplectic matice a D je nezáporné n -by- n diagonální matice.

Druhá odmocnina matice

  • Rozklad:, není obecně jedinečný.
  • V případě pozitivního semidefinitu existuje jedinečný pozitivní semidefinit takový .

Zobecnění

Existují analogy SVD, QR, LU a Choleského faktorizace pro kvasimatrices a cmatrices nebo spojité matice . „Quasimatrix“ je, podobně jako matice, obdélníkové schéma, jehož prvky jsou indexovány, ale jeden diskrétní index je nahrazen spojitým indexem. Podobně „cmatrix“ je spojitá v obou indexech. Jako příklad cmatrix si můžeme představit jádro integrálního operátoru .

Tyto faktorizace vycházejí z rané práce Fredholma (1903) , Hilberta (1904) a Schmidta (1907) . Účet a překlad klíčových článků do angličtiny viz Stewart (2011) .

Viz také

Reference

Poznámky

Citace

Bibliografie

externí odkazy