Maticový rozklad - Matrix decomposition

V matematický disciplína lineární algebra, a maticový rozklad nebo maticová faktorizace je faktorizace a matice do produktu matic. Existuje mnoho různých maticových rozkladů; každý najde uplatnění u určité třídy problémů.

Příklad

v numerická analýza, k implementaci efektivní matice se používají různé rozklady algoritmy.

Například při řešení a soustava lineárních rovnic ${ displaystyle Ax = b}$matice A lze rozložit pomocí LU rozklad. Rozklad LU faktorizuje matici na a dolní trojúhelníková matice L a horní trojúhelníková matice U. Systémy ${ displaystyle L (Ux) = b}$ a ${ displaystyle Ux = L ^ {- 1} b}$ vyžadují méně sčítání a násobení k vyřešení ve srovnání s původním systémem ${ displaystyle Ax = b}$, i když v nepřesné aritmetice může být vyžadováno podstatně více číslic, např plovoucí bod.

Podobně QR rozklad vyjadřuje A tak jako QR s Q an ortogonální matice a R horní trojúhelníková matice. Systém Q(Rx) = b řeší Rx = Q^Tb = Ca systém Rx = C řeší '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

• Použitelné pro: čtvercová matice A
• Rozklad: ${ displaystyle A = LU}$, kde L je spodní trojúhelníkový a U je horní trojúhelníkový
• Související: LDU rozklad je ${ displaystyle A = LDU}$, kde L je spodní trojúhelníkový s těmi na diagonále, U je horní trojúhelníkový s těmi na úhlopříčce a D je diagonální matice.
• Související: LUP rozklad je ${ displaystyle A = LUP}$, kde L je spodní trojúhelníkový, U je horní trojúhelníkový, a P je permutační matice.
• Existence: Existuje rozklad LUP pro jakoukoli čtvercovou matici A. Když P je matice identity, rozklad LUP se redukuje na rozklad LU. Pokud existuje rozklad LU, existuje rozklad LDU.^[1]
• Komentáře: Rozklady LUP a LU jsou užitečné při řešení n-podle-n soustava lineárních rovnic ${ displaystyle Ax = b}$. Tyto rozklady shrnují proces Gaussova eliminace v maticové formě. Matice P představuje jakoukoli záměnu řádků provedenou v procesu Gaussovy eliminace. Pokud Gaussova eliminace produkuje řádkový sled bez nutnosti jakýchkoli záměn řádků P = Já, takže existuje rozklad LU.

Snížení LU

Blokovat rozklad LU

Faktorizace pořadí

• Použitelné pro: m-podle-n matice A hodnosti r
• Rozklad: ${ displaystyle A = CF}$ kde C je m-podle-r úplná matice pořadí sloupců a F je r-podle-n matice hodnocení celé řady
• Komentář: Faktorizaci pořadí lze použít spočítat Moore-Penroseovu pseudoinverzi z A,^[2] na které se lze přihlásit získat všechna řešení lineárního systému ${ displaystyle Ax = b}$.

Choleský rozklad

• Použitelné pro: náměstí, poustevník, pozitivní určitý matice A
• Rozklad: ${ displaystyle A = U ^ {*} U}$, kde U je horní trojúhelníkový se skutečnými kladnými diagonálními položkami
• Komentář: pokud je matice A je Hermitian a pozitivní semi-definitivní, pak má rozklad formy ${ displaystyle A = U ^ {*} U}$ pokud jsou úhlopříčné položky ${ displaystyle U}$ mohou být 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 skutečné a symetrické, ${ displaystyle U}$ má všechny skutečné prvky
• Komentář: Alternativou je LDL rozklad, což může zabránit extrakci druhé odmocniny.

QR rozklad

• Použitelné pro: m-podle-n matice A s lineárně nezávislými sloupy
• Rozklad: ${ displaystyle A = QR}$ kde Q je unitární matice velikosti m-podle-m, a R je horní trojúhelníkový matice velikosti m-podle-n
• Jedinečnost: Obecně to není jedinečné, ale pokud ${ displaystyle A}$ je plný hodnost, pak existuje jediný ${ displaystyle R}$ který má všechny kladné diagonální prvky. Li ${ displaystyle A}$ je také čtvercový ${ displaystyle Q}$ je jedinečný.
• Komentář: QR rozklad poskytuje alternativní způsob řešení soustavy rovnic ${ displaystyle Ax = b}$ bez převrácení matice A. Skutečnost, že Q je ortogonální znamená, že ${ displaystyle Q ^ {T} Q = I}$, aby ${ displaystyle Ax = b}$ je ekvivalentní k ${ displaystyle Rx = Q ^ {T} b}$, což je od té doby snadnější řešení R 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é zvaný spektrální rozklad.
• Použitelné pro: čtvercová matice A s lineárně nezávislými vlastními vektory (ne nutně odlišnými vlastními hodnotami).
• Rozklad: ${ displaystyle A = VDV ^ {- 1}}$, kde D je diagonální matice vytvořený z vlastní čísla z Aa sloupce PROTI jsou odpovídající vlastní vektory z A.
• Existence: An n-podle-n matice A vždycky n (komplexní) vlastní čísla, která lze objednat (více než jedním způsobem) za účelem vytvoření n-podle-n diagonální matice D a odpovídající matice nenulových sloupců PROTI který uspokojuje rovnice vlastního čísla ${ displaystyle AV = VD}$. ${ displaystyle V}$ je invertibilní právě tehdy, když n vlastní vektory jsou lineárně nezávislé (tj. každé vlastní číslo má geometrická multiplicita rovná se jeho algebraická multiplicita ). 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)
• Komentář: Každý normální matice A (tj. matice, pro kterou ${ displaystyle AA ^ {*} = A ^ {*} A}$, kde ${ displaystyle A ^ {*}}$ je konjugovat transponovat ) lze eigendecomposed. Pro normální matice A (a pouze pro normální matici) mohou být vlastní vektory také vytvořeny jako ortonormální (${ displaystyle VV ^ {*} = I}$) a vlastní složka zní jako ${ displaystyle A = VDV ^ {*}}$. Zejména všechny unitární, Hermitian nebo šikmo-poustevník (v případě skutečné hodnoty vše ortogonální, symetrický nebo šikmo symetrický matice jsou normální, a proto vlastní tuto vlastnost.
• Komentář: Pro všechny skutečné symetrická matice A, vlastní složka vždy existuje a lze ji zapsat jako ${ displaystyle A = VDV ^ {T}}$, kde oba D a PROTI 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 diferenciální rovnice ${ displaystyle x_ {t + 1} = Ax_ {t}}$ počínaje původním stavem ${ displaystyle x_ {0} = c}$ řeší ${ displaystyle x_ {t} = A ^ {t} c}$, což odpovídá ${ displaystyle x_ {t} = VD ^ {t} V ^ {- 1} c}$, kde PROTI a D jsou matice vytvořené z vlastních vektorů a vlastních hodnot z A. Od té doby D je úhlopříčka, což ji zvyšuje na sílu ${ displaystyle D ^ {t}}$, zahrnuje pouze zvednutí každého prvku na úhlopříčce na sílu t. To je mnohem snazší udělat a pochopit, než zvyšovat A k moci t, od té doby A obvykle není diagonální.

Jordanův rozklad

The Jordan normální forma a Jordan – Chevalleyův rozklad

• Použitelné 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ákladny.

Schurův rozklad

• Použitelné pro: čtvercová matice A
• Rozklad (složitá verze): ${ displaystyle A = UTU ^ {*}}$, kde U je unitární matice, ${ displaystyle U ^ {*}}$ je konjugovat transponovat z U, a T je horní trojúhelníkový matice zvaná komplex Schurova forma který má vlastní čísla z A podél jeho úhlopříčky.
• Komentář: pokud A je a normální matice, pak T je diagonální a Schurův rozklad se shoduje se spektrálním rozkladem.

Skutečný Schurův rozklad

• Použitelné pro: čtvercová matice A
• Dekompozice: Toto je verze Schurova rozkladu, kde ${ displaystyle V}$ a ${ displaystyle S}$ obsahují pouze reálná čísla. Vždy se dá psát ${ displaystyle A = VSV ^ {T}}$ kde PROTI je skutečný ortogonální matice, ${ displaystyle V ^ {T}}$ je přemístit z PROTI, a S je blok horní trojúhelníkový matice zvaná skutečná Schurova 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 tomto případě jsou odvozeny z komplexní konjugát páry vlastních čísel).

QZ rozklad

• Také zvaný: zobecněný Schurův rozklad
• Použitelné pro: čtvercové matice A a B
• Komentář: Existují dvě verze tohoto rozkladu: komplexní a skutečná.
• Rozklad (složitá verze): ${ displaystyle A = QSZ ^ {*}}$ a ${ displaystyle B = QTZ ^ {*}}$ kde Q a Z jsou unitární matice, představuje * horní index konjugovat transponovat, a S a T jsou horní trojúhelníkový matice.
• Komentář: ve složitém QZ rozkladu, poměry diagonálních prvků S na odpovídající diagonální prvky T, ${ displaystyle lambda _ {i} = S_ {ii} / T_ {ii}}$, jsou zobecněné vlastní čísla které řeší zobecněný problém vlastních čísel ${ displaystyle Av = lambda Bv}$ (kde ${ displaystyle lambda}$ je neznámý skalární a proti je neznámý nenulový vektor).
• Rozklad (skutečná verze): ${ displaystyle A = QSZ ^ {T}}$ a ${ displaystyle B = QTZ ^ {T}}$ 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, T horní index představuje transpozice, a S a T jsou blok horní trojúhelníkový matice. Bloky na úhlopříčce S a T mají velikost 1 × 1 nebo 2 × 2.

Takagiho faktorizace

• Použitelné pro: čtvercová, komplexní, symetrická matice A.
• Rozklad: ${ displaystyle A = VDV ^ {T}}$, kde D je skutečně nezáporný diagonální matice, a PROTI je unitární. ${ displaystyle V ^ {T}}$ označuje maticová transpozice z PROTI.
• Komentář: Diagonální prvky D jsou nezáporné druhé odmocniny vlastních čísel z ${ displaystyle AA ^ {*}}$.
• Komentář: PROTI 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á ${ displaystyle V ^ {- 1}}$ namísto ${ displaystyle V ^ {T}}$.

Rozklad singulární hodnoty

• Použitelné pro: m-podle-n matice A.
• Rozklad: ${ displaystyle A = UDV ^ {*}}$, kde D není negativní diagonální matice, a U a PROTI uspokojit ${ displaystyle U ^ {*} U = I, V ^ {*} V = I}$. Tady ${ displaystyle V ^ {*}}$ je konjugovat transponovat z PROTI (nebo jednoduše přemístit, pokud PROTI obsahuje pouze reálná čísla) a Já označuje matici identity (nějaké dimenze).
• Komentář: Diagonální prvky D se nazývají singulární hodnoty 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 ${ displaystyle A}$ jsou vždy jednoznačně určeny. ${ displaystyle U}$ a ${ displaystyle V}$ 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.

• Použitelné pro: m-podle-n matice A.
• Unit-Scale-Invariant Singular-Value Decomposition: ${ displaystyle A = DUSV ^ {*} E}$, kde S je jedinečný nezáporný diagonální matice singulárních hodnot neměnných v měřítku, U a PROTI jsou unitární matice, ${ displaystyle V ^ {*}}$ je konjugovat transponovat z PROTIa pozitivní diagonální matice D a E.
• Komentář: Je obdobou SVD, kromě toho, že diagonální prvky S jsou neměnné s ohledem na levé a / nebo pravé násobení A libovolnými nonsingulárními diagonálními maticemi, na rozdíl od standardního SVD, pro které jsou singulární hodnoty neměnné vzhledem k levému a / nebo pravému násobení A libovolnými jednotnými maticemi.
• Komentář: Je alternativou ke standardnímu SVD, když je vyžadována invariance s ohledem na diagonální, nikoli jednotkové transformace A.
• Jedinečnost: Jednotkové hodnoty neměnného rozsahu ${ displaystyle A}$ (dáno úhlopříčnými prvky S) jsou vždy jednoznačně určeny. Diagonální matice D a Ea unitární U a PROTI, nemusí být nutně jedinečné obecně.
• Komentář: U a PROTI matice 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.^[3][4]

Jiné rozklady

Polární rozklad

• Platí pro: libovolná čtvercová komplexní matice A.
• Rozklad: ${ displaystyle A = NAHORU}$ (pravý polární rozklad) nebo ${ displaystyle A = P'U}$ (levý polární rozklad), kde U je unitární matice a P a P ' jsou pozitivní semidefinit Hermitovské matice.
• Jedinečnost: ${ displaystyle P}$ je vždy jedinečný a stejný ${ displaystyle { sqrt {A ^ {*} A}}}$ (což je vždy poustevník a pozitivní semidefinit). Li ${ displaystyle A}$ je tedy invertibilní ${ displaystyle U}$ je jedinečný.
• Komentář: Jelikož každá hermitovská matice připouští spektrální rozklad s jednotnou maticí, ${ displaystyle P}$ lze psát jako ${ displaystyle P = VDV ^ {*}}$. Od té doby ${ displaystyle P}$ je kladný semidefinit, všechny prvky v ${ displaystyle D}$ jsou nezáporné. Vzhledem k tomu, že produkt dvou jednotných matic je jednotný, přičemž ${ displaystyle W = UV}$dá se psát ${ displaystyle A = U (VDV ^ {*}) = WDV ^ {*}}$ což je rozklad singulární hodnoty. Existence polárního rozkladu je tedy ekvivalentní existenci rozkladu singulární hodnoty.

Algebraický polární rozklad

• Použitelné pro: čtvercová, složitá, nesingulární matice A.^[5]
• Rozklad: ${ displaystyle A = QS}$, kde Q je komplexní ortogonální matice a S je komplexní symetrická matice.
• Jedinečnost: Pokud ${ displaystyle A ^ {T} A}$ nemá žádná záporná skutečná vlastní čísla, pak je rozklad jedinečný.^[6]
• Komentář: Existence tohoto rozkladu je ekvivalentní ${ displaystyle AA ^ {T}}$ být podobný ${ displaystyle A ^ {T} A}$.^[7]
• Komentář: Varianta tohoto rozkladu je ${ displaystyle A = RC}$, kde R je skutečná matice a C je kruhová matice.^[6]

Mostowův rozklad

• Použitelné pro: čtvercová, složitá, nesingulární matice A.^[8][9]
• Rozklad: ${ displaystyle A = Ue ^ {iM} e ^ {S}}$, kde U je unitární, M je skutečný anti-symetrický a S je skutečně symetrický.
• Komentář: Matice A lze také rozložit jako ${ displaystyle A = U_ {2} e ^ {S_ {2}} e ^ {iM_ {2}}}$, kde U₂ je unitární, M₂ je skutečný anti-symetrický a S₂ je skutečně symetrický.^[6]

Sinkhorn normální forma

• Platí pro: čtvercová reálná matice A s přísně pozitivními prvky.
• Rozklad: ${ displaystyle A = D_ {1} SD_ {2}}$, kde S je dvojnásobně stochastický a D₁ a D₂ jsou skutečné diagonální matice s přísně pozitivními prvky.

Odvětvový rozklad

• Použitelné pro: čtvercová, komplexní matice A s číselný rozsah obsažené v sektoru ${ displaystyle S _ { alpha} = left {re ^ {i theta} in mathbb {C} mid r> 0, | theta | leq alpha <{ frac { pi} { 2}} doprava }}$.
• Rozklad: ${ displaystyle A = CZC ^ {*}}$, kde C je invertibilní komplexní matice a ${ displaystyle Z = operatorname {diag} left (e ^ {i theta _ {1}}, ldots, e ^ {i theta _ {n}} right)}$ se vším ${ displaystyle left | theta _ {j} right | leq alpha}$.^[10][11]

Williamsonova normální forma

• Platí pro: čtverec, pozitivní-definitivní skutečná matice A s objednávkou 2n-by-2n.
• Rozklad: ${ displaystyle A = S ^ {T} { textrm {diag}} (D, D) S}$, kde ${ displaystyle S in { text {Sp}} (2n)}$ je symplektická matice a D není negativní n-podle-n diagonální matice.^[12]

Zobecnění

Tato sekce potřebuje expanzi s: příklady a další citace. Můžete pomoci přidávat k tomu. (Prosince 2014)

Existují analogy faktorizace SVD, QR, LU a Cholesky pro quasimatrices a cmatrices nebo spojité matice.^[13] „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í operátor.

Tyto faktorizace jsou založeny na rané práci od Fredholm (1903), Hilbert (1904) a Schmidt (1907). Účet a překlad seminárních prací do angličtiny viz Stewart (2011).

Viz také

• Rozdělení matice
• Nezáporná maticová faktorizace
• Analýza hlavních komponent

Poznámky

Reference

• Choudhury, Dipa; Horn, Roger A. (duben 1987). „Komplexní ortogonálně symetrický analog polárního rozkladu“. SIAM Journal o algebraických a diskrétních metodách. 8 (2): 219–225. doi:10.1137/0608019.
• Fredholm, I. (1903), „Sur une classe d'´equations fonctionnelles“, Acta Mathematica (francouzsky), 27: 365–390, doi:10.1007 / bf02421317
• Hilbert, D. (1904), „Grundzüge einer allgemeinen Theorie der linearen Integralgleichungen“, Nachr. Königl. Ges. Gött (v němčině), 1904: 49–91
• Horn, Roger A .; Merino, Dennis I. (leden 1995). „Ekvivalence přísad: kanonická forma a některé aplikace“. Lineární algebra a její aplikace. 214: 43–92. doi:10.1016/0024-3795(93)00056-6.
• Meyer, C. D. (2000), Maticová analýza a aplikovaná lineární algebra, SIAM, ISBN  978-0-89871-454-8
• Schmidt, E. (1907), "Zur Theorie der linearen und nichtlinearen Integralgleichungen. Teil. Entwicklung willkürlichen Funktionen nach System vorgeschriebener", Mathematische Annalen (v němčině), 63 (4): 433–476, doi:10.1007 / bf01449770
• Simon, C .; Blume, L. (1994). Matematika pro ekonomy. Norton. ISBN  978-0-393-95733-4.CS1 maint: ref = harv (odkaz)
• Stewart, G. W. (2011), Fredholm, Hilbert, Schmidt: tři základní práce o integrálních rovnicích (PDF), vyvoláno 2015-01-06
• Townsend, A .; Trefethen, L. N. (2015), "Kontinuální analogie maticových faktorizací", Proc. R. Soc. A, 471 (2173): 20140585, Bibcode:2014RSPSA.47140585T, doi:10.1098 / rspa.2014.0585, PMC  4277194, PMID  25568618

externí odkazy

• Online maticová kalkulačka
• Výpočet rozkladu matice Wolfram Alpha »Rozklad LU a QR
• Springerova encyklopedie matematiky »Maticová faktorizace
• GraphLab GraphLab kolaborativní filtrační knihovna, rozsáhlá paralelní implementace metod rozkladu matic (v C ++) pro vícejádrové.