Maticový rozklad

Rozklad matice je znázornění matice jako součinu matic, které mají některé specifické vlastnosti (například ortogonalita , symetrie , diagonalita ). Každá třída maticových rozkladů má svou vlastní oblast použití; zejména mnoho efektivních algoritmů výpočetní lineární algebry je založeno na konstrukci odpovídajících expanzí matic. $A$

Rozšíření pro řešení SLAE

Rozklad LU

Omezení: matice je čtvercová a nedegenerovaná a všechny její hlavní hlavní minority jsou nenulové [1] . $A$
Typ rozkladu: , kde je spodní trojúhelníková matice a je horní trojúhelníková matice . Pro jednoznačné expanze se obvykle navíc požaduje, aby matice byla unitriangular , tedy trojúhelníková matice s diagonálními vstupy rovnými jedné (někdy je na matici místo toho kladen požadavek unitrianity ) [2] . $A = LU$ $L$ $U$ $L$ $U$
Podobné rozklady: LDU - rozklad ve tvaru , kde je spodní jednotková trojúhelníková matice, je horní jednotková trojúhelníková matice a je diagonální $A=LDU$ $L$ $U$ $D$
Podobná rozšíření : LUP -rozklad ve tvaru _ _ _ Toto je zobecnění LU rozkladu na případ libovolných nedegenerovaných matic. $PA=LU$ $P$ $L$ $U$
Existence: LUP rozklad existuje pro jakoukoli čtvercovou matici . Když je matice redukována na matici identity , rozklad LUP se redukuje na rozklad LU . $A$ $P$
LUP a LU - rozklady se používají při řešení SLAE dimenze . Odpovídající metody jsou variantami maticového tvaru Gaussovy metody . Matice charakterizuje kumulativní účinek řádkových permutací v Gaussově metodě. $sekera=b$ $n\krát n$ $P$

Faktorizace pořadí

Omezení: libovolná matice velikosti a pořadí . $A$ $m\krát n$ $r$

Typ rozkladu: , kde je matice a je matice . $A=CF$ $C$ $m\times r$ $F$ $r\times n$
Faktorizace pořadí může být použita k výpočtu pseudoinverzní matice , která se používá při hledání obecného řešení SLAE . $sekera=b$

Choleský rozklad

Omezení: symetrická pozitivně definitní matice [3] . $A$
Typ rozkladu: (nebo ekvivalentně ), kde matice je horní trojúhelníková (respektive matice je dolní trojúhelníková ) [3] . $A=U^{T}U$ $A=LL^{T}$ $U$ $L$
Podobné rozklady: Alternativou je modifikovaný Choleského rozklad ( LDL -decomposition ), který se vyhýbá extrakci kořenů (ve kterém je matice nižší jednotka trojúhelníková a je diagonální ). $L$ $D$
Choleský rozklad je unikátní.
Choleského rozklad je také použitelný, pokud je matice hermitovská a pozitivně definitní . $A$
K vyřešení SLAE se použije Choleského rozklad, pokud má matrice vhodné vlastnosti. Tento způsob řešení je ve srovnání s metodou LU-dekompozice jistě numericky stabilní a vyžaduje o polovinu méně aritmetických operací [4] . $sekera=b$ $A$

QR rozklad

Omezení: libovolná matice velikosti . $A$ $m\krát n$
Typ rozkladu: , kde je ortogonální matice o velikosti a je horní trojúhelníková matice o velikosti . $A = QR$ $Q$ $m\times m$ $R$ $m\krát n$
Podobné rozklady: Existují analogické rozklady QL- , RQ- a LQ- .
Vzhledem k ortogonalitě matice (což znamená, že inverzní matice se shoduje s transponovanou maticí ), je systém ekvivalentní systému s trojúhelníkovou maticí, jejíž řešení není obtížné. $Q$ $Q^{-1}$ $Q^{T}$ $sekera=b$ $Rx=Q^{T}b$
Jedním ze způsobů, jak získat matici , je Gram-Schmidtův proces a poté . $Q$ $R=Q^{T}A$
Konstrukce QR rozkladu je základem QR algoritmu , který je jednou z metod hledání vlastních vektorů a maticových hodnot.
Algoritmy pro řešení SLAE založené na QR rozkladu fungují téměř stejně pro dobře podmíněné i singulární systémy [5] .

Interpolační expanze

Omezení: libovolná matice dimenze a hodnosti . $A$ $m\krát n$ $r$
Typ rozkladu: , kde je podmnožina indexů ; matice se skládá z odpovídajících sloupců původní matice; je matice, jejíž všechny prvky jsou modulo nejvýše 2 (navíc obsahuje jednotkovou podmatici dimenze ). Podobný rozklad lze získat v řadách. $A=A_{(:,J)}X$ $J$ $r$ $1,...,č$ ${\displaystyle A_{(:,J)))$ $X$ $r\times n$ $X$ $r\krát r$

Expanze vlastních nebo singulárních hodnot

Spektrální rozklad

Omezení: diagonalizovatelná čtvercová matice , tj. mající sadu různých vlastních vektorů ( vlastní hodnoty se nemusí lišit). $A$ $n$
Typ rozšíření: , kde je úhlopříčka vytvořená z vlastních čísel a sloupce jsou odpovídající vlastní vektory . $A=VDV^{-1}$ $D$ $A$ $PROTI$
Existence: Matice dimenzí má vždy vlastní čísla (početná násobnost), která lze seřadit (nikoli jedinečným způsobem), aby se vytvořila matice diagonálních rozměrů a odpovídající matice nenulových sloupců , které splňují rovnost . Pokud jsou vlastní vektory různé, pak má matice inverzní hodnotu, která poskytne požadované rozšíření [6] . $n\krát n$ $n$ $D$ $n\krát n$ $PROTI$ $AV=VD$ $n$ $PROTI$ $A=VDV^{-1}$
Vždy je možné normalizovat vlastní vektory tak, aby měly délku 1. Pokud jde o skutečnou symetrickou matici, pak je vždy invertibilní a normalizovatelná. V tomto případě se matice ukáže jako ortogonální, protože vlastní vektory jsou vůči sobě ortogonální . Požadované rozšíření (které v posuzovaném případě vždy existuje) lze tedy zapsat jako . $A$ $PROTI$ $PROTI$ $A=VDV^{T}$
Nezbytnou a postačující podmínkou diagonalizovatelnosti je shoda geometrické a algebraické násobnosti každého vlastního čísla. Zejména existence odlišných vlastních hodnot je postačující (ale ne nezbytnou) podmínkou. $n$
Spektrální rozklad je užitečný pro pochopení řešení systémů lineárních obyčejných diferenciálních rovnic nebo diferenčních rovnic . Například diferenční rovnice s počáteční podmínkou má řešení , které lze zapsat jinak jako (in case ). Zvednutí diagonální matice na mocninu se zredukuje na zvednutí každého prvku na diagonále na mocninu , což je nesrovnatelně jednodušší než (samozřejmě pokud ten druhý zpočátku nemá diagonální tvar). ${\displaystyle x_{t+1}=Ax_{t))$ $x_{0}=c$ $x_{t}=A^{t}c$ $x_{t}=VD^{t}V^{-1}c$ $A=VDV^{-1}$ $t$ $D$ $t$ $A$

Jordan normální tvar

Omezení: čtvercová matice . $A$
Typ expanze: , kde je Jordanova matice a je přechodová matice na nový základ. $A=CJC^{-1}$ $J$ $C$
Jordanova normální forma je zobecněním diagonální formy matice vlastních hodnot na případ, kdy geometrická násobnost jednoho nebo více vlastních hodnot je menší než algebraická násobnost . $A$

Schurův rozklad

Omezení: čtvercová matice . $A$
Existují dvě verze rozkladu: pro případ reálné matice a pro případ komplexní matice. Ta má vždy komplexní Schurovu expanzi.
Typ rozkladu (reálný případ): (všechny matice v obou částech rovnosti jsou složeny z přísně reálných hodnot). V tomto případě je ortogonální matice a je kvazitrojúhelníková matice . Ten se nazývá skutečná Schurova forma . Bloky na diagonále mají buď velikost (v tom případě se jedná o skutečná vlastní čísla) nebo (tvořené dvojicí komplexně sdružených vlastních čísel). $A=VSV^{T}$ $PROTI$ $S$ $S$ $1\krát 1$ $2\krát 2$
Typ rozkladu (složitý případ): , kde je unitární , je jeho hermitovský konjugát a je to horní trojúhelníková matice, nazývaná komplexní Schurova forma , která obsahuje vlastní čísla na diagonále. $A=UTU^{H}$ $U$ $U^{H}$ $T$ $A$

QZ-rozklad

Omezení: čtvercové matice a . $A$ $B$
Existují dvě verze rozkladu: komplexní a skutečný.
Typ expanze (složitý případ): , kde a jsou unitární matice , je hermitovský konjugovaný k , a jsou horní trojúhelníkové matice . $A=QSZ^{H},B=QTZ^{H}$ $Q$ $Z$ $Z^{H}$ $Z$ $S$ $T$
V zadaném rozkladu jsou poměrem diagonálních prvků v a odpovídajících zobecněná vlastní čísla, která jsou řešením zobecněného problému hledání vlastních čísel (kde je neznámý skalár a je neznámý nenulový vektor). $S$ $T$ ${\displaystyle \lambda _{i}=S_{ii}/T_{ii))$ $Av=\lambda Bv$ $\lambda$ $proti$
Typ rozkladu (reálný případ): , kde všechny matice sestávají výhradně z reálných hodnot. jsou ortogonální matice a jsou kvazitrojúhelníkové matice , sestávající z bloků nebo (podobně jako odpovídající bloky v Schurově expanzi). $A=QSZ^{T},B=QTZ^{T}$ $Q,Z$ $SVATÝ$ $1\krát 1$ $2\krát 2$

Dekompozice singulární hodnoty

Omezení: matice libovolné velikosti [7] . $A$ $m\krát n$
Typ rozkladu: , kde je nezáporná diagonální matice , jsou unitární matice a je Hermitova konjugovaná . V reálném případě , a , stejně jako dříve, nezáporná diagonální matice , jsou ortogonální [7] [8] . $A=U\Sigma V^{H}$ $\Sigma$ $U,V$ $V^{H}$ $A=U\Sigma V^{T}$ $\Sigma$ $U,V$
Prvky na diagonále matice se nazývají singulární hodnoty matice a označují se Počet nenulových singulárních hodnot matice se rovná hodnosti této matice [9] . $\Sigma$ $A$ $\sigma _{j}.$ $A$
Singulární rozklad, stejně jako spektrální rozklad, zahrnuje nalezení základu podprostorů, akci operátora, na jehož elementech je ekvivalentní násobení skalárem (tj. ), ale singulární rozklad je obecnější metodou, protože matice nemá být hranatý. $\mathcal{A}$ $Av=\sigma _{j}v$ $A$

Další rozšíření

Polární expanze

Omezení: čtvercová komplexní matice [10] . $A$
Typ expanze (složitý případ): , kde je hermitovská matice s nezápornými vedoucími minoritami a je unitární matice [10] [11] . $A = NE$ $S$ $U$
Typ expanze (reálný případ): , kde je symetrická matice s nezápornými úvodními minoritami a je ortogonální matice [12] [13] . $A=SQ$ $S$ $Q$
Pro nedegenerovanou matrici je polární rozklad jedinečný a pro degenerovanou matrici je jednoznačně definován pouze faktor [10] . $S$
Polární rozklad matice v komplexním případě je analogický k reprezentaci libovolného komplexního čísla ve tvaru [14] . $z$ ${\displaystyle z=|z|e^{i\varphi ))$

Frobenius normální forma

Omezení: čtvercová matice . $A$
Typ rozkladu: , kde je blokově-diagonální matice skládající se z doprovodných matic pro unitární polynomy , které jsou násobkem . je přechodová matice. $A=PCP^{-1}$ $C$ $f_{i}$ $f_{{i+1}}$ $f_{i}$ $P$

Poznámky

↑ Ikramov, 1991 , s. dvacet.
↑ Voevodin a Kuzněcov, 1984 , s. 75-76.
↑ 1 2 Voevodin a Kuzněcov, 1984 , s. 176.
↑ William H. Press, Saul A. Teukolsky, William T. Vetterling, Brian P. Flannery. . 2.9 Cholesky Decomposition // Numerical Recipes in C. 2nd edition. — Cambridge: Cambridge University Press. - ISBN 0-521-43108-5 .
↑ QR a SVD rozklady: "špatné" SLAE . Získáno 17. listopadu 2016. Archivováno z originálu 22. června 2017. (neurčitý)
↑ Meyer, 2000 , str. 514.
↑ 1 2 Ikramov, 1991 , str. 21.
↑ Voevodin a Kuzněcov, 1984 , s. 80.
↑ Forsyth J., Malcolm M., Moler K. . Strojové metody matematických výpočtů. — M .: Mir , 1980. — 280 s. — S. 214, 225.
↑ 1 2 3 Voevodin a Kuzněcov, 1984 , s. 78.
↑ Gantmakher, 1988 , str. 234-236.
↑ Voevodin a Kuzněcov, 1984 , s. 79.
↑ Gantmakher, 1988 , str. 244.
↑ Gantmakher, 1988 , str. 236.

Literatura

Voevodin V.V. , Kuzněcov Yu.A. Matice a výpočty. — M .: Nauka , 1984. — 320 s.
Gantmakher F. R. Teorie matic. 4. vyd. — M .: Nauka , 1988. — 552 s. — ISBN 5-02-013722-7 .
Ikramov H. D. . Asymetrický problém vlastních čísel. Numerické metody. — M .: Nauka , 1991. — 240 s. — ISBN 5-02-014462-2 .
Meyer, Carl D. Maticová analýza a aplikovaná lineární algebra . - Philadelphia: SIAM , 2000. - xii + 718 s. — ISBN 0-89871-454-0 .

Vektory a matice

vektory

Základní pojmy	Vektor v geometrii Základ Ortogonální základ Vektorové souřadnice Kolinearita Ortogonalita Lineární závislost Prostor sloupců
Druhy vektorů	Jednotkový vektor Axiální vektor izotropní vektor Normální Kolinearita Nulový vektor Vektor poloměru Vlastní vektor
Operace s vektory	Skalární součin vektorový produkt smíšený produkt Pseudoskalární produkt Dvojitý křížový produkt
Typy prostoru	vektorový prostor afinní prostor Euklidovský prostor Pseudoeuklidovský prostor Normovaný prostor Minkowského prostor

matrice

Základní pojmy	Maticové násobení Transponovaná matice Hermitovská konjugovaná matice Symetrická matice inverzní matice Vlastní hodnota Charakteristický polynom matice
Speciální matrice	Matice identity Nulová matice Diagonální matice lambda matrice
Maticové rozklady	LU rozklad Choleský rozklad QR rozklad rozklad LUP singulární rozklad hodnoty Spektrální rozklad matice

jiný