Matriisin hajoaminen

Matriisihajotelma on esitys matriisista matriisien tulona , joilla on tiettyjä ominaisuuksia (esimerkiksi ortogonaalisuus , symmetria , diagonaalisuus ). Jokaisella matriisihajotusluokalla on oma sovellusalue; erityisesti monet tehokkaat laskennalliset lineaarialgebra -algoritmit perustuvat vastaavien matriisilaajennusten rakentamiseen. $A$

Laajennukset SLAE:n ratkaisemiseen

LU:n hajoaminen

Rajoitukset: matriisi on neliömäinen ja rappeutumaton , ja kaikki sen johtavat päämollarit ovat nollasta poikkeavia [1] . $A$
Hajotustyyppi: , jossa on alempi kolmiomatriisi ja ylempi kolmiomatriisi . Yksiselitteisiä laajennuksia varten vaaditaan yleensä lisäksi, että matriisi on yksikolmio , eli kolmiomatriisi, jonka diagonaaliset merkinnät ovat yhtä suuria (joskus matriisille asetetaan sen sijaan unitrianity-vaatimus ) [2] . $A = LU$ $L$ $U$ $L$ $U$
Samanlaisia hajotuksia: LDU -hajotelma muodossa , jossa on alempi kolmiomatriisi, on ylempi yksikolmiomatriisi ja on diagonaalinen $A=LDU$ $L$ $U$ $D$
Samanlaisia laajennuksia : LUP -hajotelma muodossa _ _ _ _ Tämä on yleistys LU -hajotelmasta mielivaltaisten ei-degeneroituneiden matriisien tapaukseen. $PA = LU$ $P$ $L$ $U$
Olemassaolo: LUP -hajotelma on olemassa mille tahansa neliömatriisille . Kun matriisi pelkistetään identiteettimatriisiin , LUP - hajotelma pelkistetään LU - hajotelmaksi. $A$ $P$
LUP- ja LU -hajotelmia käytetään mittasuhteiden SLAE :n ratkaisemisessa . Vastaavat menetelmät ovat muunnelmia Gaussin menetelmän matriisimuodosta . Matriisi kuvaa rivipermutaatioiden kumulatiivista vaikutusta Gaussin menetelmässä. $ax=b$ $n\ kertaa n$ $P$

Sijoitustekijät

Rajoitukset: mielivaltainen koon ja järjestyksen matriisi . $A$ $m\ kertaa n$ $r$

Hajotustyyppi: , missä on matriisi ja on matriisi . $A=CF$ $C$ $m\times r$ $F$ $r\times n$
Rank-faktorointia voidaan käyttää pseudoinversiomatriisin laskemiseen , jota käytetään SLAE : n yleisen ratkaisun löytämisessä . $ax=b$

Cholesky-hajoaminen

Rajoitukset: symmetrinen positiivinen määrätty matriisi [3] . $A$
Hajotustyyppi: (tai vastaavasti ), jossa matriisi on ylempi kolmiomainen ( vastaavasti matriisi on alakolmio ) [3] . $A=U^{T}U$ $A=LL^{T}$ $U$ $L$
Samankaltaiset hajotukset: vaihtoehtona on modifioitu Cholesky-hajoaminen ( LDL -hajoaminen ), joka välttää juurien irtoamisen ( jossa matriisi on alempi yksikolmiomainen ja diagonaalinen ). $L$ $D$
Cholesky-hajoaminen on ainutlaatuinen.
Cholesky-hajotelmaa voidaan soveltaa myös, jos matriisi on hermiittinen ja positiivinen definiitti . $A$
Cholesky-hajotelmaa käytetään ratkaisemaan SLAE , jos matriisilla on asianmukaiset ominaisuudet. Tämä ratkaisumenetelmä on LU-hajotusmenetelmään verrattuna varmasti numeerisesti vakaa ja vaatii puolet vähemmän aritmeettisia operaatioita [4] . $ax=b$ $A$

QR-hajotus

Rajoitukset: mielivaltainen koon matriisi . $A$ $m\ kertaa n$
Hajotustyyppi: , jossa on ortogonaalinen matriisi , jonka koko on , ja on ylempi kolmiomatriisi , jonka koko on . $A = QR$ $K$ $m\times m$ $R$ $m\ kertaa n$
Samanlaisia hajotuksia: On olemassa analogisia QL -, RQ - ja LQ -hajoja.
Matriisin ortogonaalisuudesta johtuen (mikä tarkoittaa, että käänteismatriisi osuu yhteen transponoidun matriisin kanssa ) järjestelmä vastaa järjestelmää , jossa on kolmiomatriisi, jonka ratkaiseminen ei ole vaikeaa. $K$ $Q^{-1}$ $Q^{T}$ $ax=b$ $Rx=Q^{T}b$
Yksi tavoista saada matriisi on Gram–Schmidt-prosessi ja sitten . $K$ $R=Q^{T}A$
QR -hajotelman rakentaminen on perusta QR-algoritmille , joka on yksi menetelmistä ominaisvektoreiden ja matriisiarvojen etsimiseen .
QR -hajoamiseen perustuvat SLAE-ratkaisun algoritmit toimivat lähes yhtä hyvin sekä hyvin ehdollisissa että yksittäisissä järjestelmissä [5] .

Interpoloinnin laajennus

Rajoitukset: mielivaltainen ulottuvuuden ja arvon matriisi . $A$ $m\ kertaa n$ $r$
Hajotustyyppi: , jossa on indeksien osajoukko ; matriisi koostuu alkuperäisen matriisin vastaavista sarakkeista; on matriisi, jonka kaikki elementit ovat modulo enintään 2 (lisäksi se sisältää yksikköalimatriisin dimensiolla ). Samanlainen jaottelu voidaan saada riveissä. $A=A_{(:,J)}X$ $J$ $r$ $1,...,n$ ${\näyttötyyli A_{(:,J)))$ $X$ $r\times n$ $X$ $r\ kertaa r$

Ominaisarvon tai yksittäisarvon laajennukset

Spektrihajoaminen

Rajoitukset: diagonalisoitava neliömatriisi , eli jossa on joukko erilaisia ominaisvektoreita ( ominaisarvojen ei tarvitse olla erilaisia). $A$ $n$
Laajennustyyppi: , missä on ominaisarvoista muodostettu diagonaali ja sarakkeet vastaavat ominaisvektorit . $A=VDV^{-1}$ $D$ $A$ $V$
Olemassaolo: Dimensiomatriisilla on aina ominaisarvot (laskentakerroin), jotka voidaan järjestää (ei ainutlaatuisella tavalla) diagonaalisen mittamatriisin ja vastaavan nollasta poikkeavien sarakkeiden matriisin muodostamiseksi, jotka täyttävät yhtälön . Jos ominaisvektorit ovat erilaisia, niin matriisissa on käänteisarvo, joka antaa halutun laajennuksen [6] . $n\ kertaa n$ $n$ $D$ $n\ kertaa n$ $V$ $AV=VD$ $n$ $V$ $A=VDV^{-1}$
Aina on mahdollista normalisoida ominaisvektorit niin, että niiden pituus on 1. Jos todellinen symmetrinen matriisi, niin se on aina käännettävä ja normalisoitavissa. Tässä tapauksessa matriisi osoittautuu ortogonaaliseksi, koska ominaisvektorit ovat ortogonaalisia toisiinsa nähden. Siten haluttu laajennus (joka on aina olemassa tarkasteltavassa tapauksessa) voidaan kirjoittaa muodossa . $A$ $V$ $V$ $A=VDV^{T}$
Diagonalisoitavuuden välttämätön ja riittävä ehto on kunkin ominaisarvon geometrisen ja algebrallisen monikertaisyyden yhtäläisyys. Erityisesti erillisten ominaisarvojen olemassaolo on riittävä (mutta ei välttämätön) ehto. $n$
Spektrihajotus on hyödyllinen ratkaisujen ymmärtämiseen lineaaristen tavallisten differentiaaliyhtälöiden tai differentiaaliyhtälöiden järjestelmiin . Esimerkiksi eroyhtälöllä, jolla on alkuehto, on ratkaisu , joka voidaan kirjoittaa eri tavalla muodossa (tapauksessa ). Diagonaalimatriisin nostaminen potenssiin pelkistää diagonaalin jokaisen elementin nostamisen potenssiin , joka on verrattoman yksinkertaisempi kuin (ellei jälkimmäisellä tietysti alun perin ole diagonaalinen muoto). ${\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 normaalimuoto

Rajoitukset: neliömatriisi . $A$
Laajennustyyppi: , missä on Jordan-matriisi ja siirtymämatriisi uudelle perustalle. $A=CJC^{-1}$ $J$ $C$
Jordanin normaalimuoto on ominaisarvomatriisin diagonaalimuodon yleistys tapaukseen, jossa yhden tai useamman ominaisarvon geometrinen monikertaisuus on pienempi kuin algebrallinen monikerta . $A$

Schur decomposition

Rajoitukset: neliömatriisi . $A$
Hajotuksesta on kaksi versiota: todellisen matriisin tapauksessa ja kompleksisen matriisin tapauksessa. Jälkimmäisellä on aina monimutkainen Schur-hajoaminen.
Hajotustyyppi (reaalitapaus): (kaikki matriisit yhtälön molemmissa osissa koostuvat tiukasti reaaliarvoista). Tässä tapauksessa on ortogonaalinen matriisi ja kvasi - kolmiomatriisi . Jälkimmäistä kutsutaan oikeaksi Schur-muodoksi . Diagonaalin lohkot ovat joko kooltaan (jolloin ne ovat todellisia ominaisarvoja) tai (muodostuvat kompleksisten konjugoitujen ominaisarvojen parista). $A=VSV^{T}$ $V$ $S$ $S$ $1\kertaa 1$ $2\ kertaa 2$
Hajotustyyppi (monimutkainen tapaus): , jossa on unitaarinen , on sen hermiittinen konjugaatti ja on ylempi kolmiomatriisi, jota kutsutaan kompleksiseksi Schur-muodoksi ja joka sisältää ominaisarvoja diagonaalissa. $A=UTU^{H}$ $U$ $U^{H}$ $T$ $A$

QZ-hajoaminen

Rajoitukset: neliömatriisit ja . $A$ $B$
Hajoamisesta on kaksi versiota: monimutkainen ja todellinen.
Laajennustyyppi (monimutkainen tapaus): , jossa ja ovat unitaarisia matriiseja , on hermiittinen konjugaatti , ja ovat ylempiä kolmiomatriiseja . $A=QSZ^{H},B=QTZ^{H}$ $K$ $Z$ $Z^{H}$ $Z$ $S$ $T$
Määritetyssä jaottelussa diagonaalielementtien suhde ja sitä vastaavat ovat yleistettyjä ominaisarvoja, jotka ovat ratkaisu ominaisarvojen löytämisen yleiseen ongelmaan (jossa on tuntematon skalaari ja tuntematon nollasta poikkeava vektori). $S$ $T$ ${\displaystyle \lambda _{i}=S_{ii}/T_{ii))$ $Av=\lambda Bv$ $\lambda$ $v$
Hajotustyyppi (todellinen tapaus): , jossa kaikki matriisit koostuvat tiukasti reaaliarvoista. ovat ortogonaalisia matriiseja ja ovat kvasi -kolmiomatriiseja , jotka koostuvat lohkoista tai (samanlainen kuin vastaavat lohkot Schur-laajennuksessa). $A=QSZ^{T},B=QTZ^{T}$ $Q,Z$ $S,T$ $1\kertaa 1$ $2\ kertaa 2$

Yksittäisen arvon hajottelu

Rajoitukset: mielivaltainen kokomatriisi [7] . $A$ $m\ kertaa n$
Hajotustyyppi: , jossa on ei-negatiivinen diagonaalinen matriisi , ovat unitaarisia matriiseja ja on hermiittinen konjugaatti . Todellisessa tapauksessa , ja , kuten aiemmin, ei-negatiivinen diagonaalimatriisi , ovat ortogonaalisia [7] [8] . $A=U\Sigma V^{H}$ $\Sigma$ $U,V$ $V^{H}$ $A=U\Sigma V^{T}$ $\Sigma$ $U,V$
Matriisin diagonaalissa olevia elementtejä kutsutaan matriisin singulaariarvoiksi ja niitä merkitään . Matriisin nollasta poikkeavien singulaariarvojen lukumäärä on yhtä suuri kuin tämän matriisin arvo [9] . $\Sigma$ $A$ $\sigma _{j}.$ $A$
Singulaarihajotus sisältää spektrihajottamisen tapaan aliavaruuksien perustan löytämisen, operaattorin toiminta, jonka alkioissa vastaa skalaarilla kertomista (eli ), mutta singulaariarvon hajottaminen on yleisempi menetelmä, koska matriisissa ei ole olla neliö. $\mathcal{A}$ $Av=\sigma _{j}v$ $A$

Muut laajennukset

Napalaajennus

Rajoitukset: neliökompleksimatriisi [10] . $A$
Laajennustyyppi (monimutkainen tapaus): , jossa on hermiittinen matriisi , jossa on ei-negatiivisia alamoreita, ja on unitaarinen matriisi [10] [11] . $A = SU$ $S$ $U$
Laajennustyyppi (todellinen tapaus): , jossa on symmetrinen matriisi , jossa on ei-negatiiviset alamerkit, ja on ortogonaalinen matriisi [12] [13] . $A=SQ$ $S$ $K$
Ei-degeneroituneelle matriisille polaarinen hajoaminen on ainutlaatuinen, ja degeneroituneelle matriisille vain tekijä on yksiselitteisesti määritelty [10] . $S$
Matriisin polaarinen hajotelma kompleksitapauksessa on analoginen mielivaltaisen kompleksiluvun esittämisen kanssa muodossa [14] . $z$ $z=|z|e^{i\varphi }$

Frobenius normaalimuoto

Rajoitukset: neliömatriisi . $A$
Hajotustyyppi: , jossa on lohko-diagonaalinen matriisi , joka koostuu mukana olevista unitaaristen polynomien matriiseista , jolloin se on :n kerrannainen . on siirtymämatriisi. $A=PCP^{-1}$ $C$ $f_{i}$ $f_{{i+1}}$ $f_{i}$ $P$

Muistiinpanot

↑ Ikramov, 1991 , s. kaksikymmentä.
↑ Voevodin ja Kuznetsov, 1984 , s. 75-76.
↑ 1 2 Voevodin ja Kuznetsov, 1984 , s. 176.
↑ William H. Press, Saul A. Teukolsky, William T. Vetterling, Brian P. Flannery. . 2.9 Cholesky Decomposition // Numeeriset reseptit C. 2. painos. — Cambridge: Cambridge University Press. - ISBN 0-521-43108-5 .
↑ QR- ja SVD-hajotelmat: "huono" SLAE . Haettu 17. marraskuuta 2016. Arkistoitu alkuperäisestä 22. kesäkuuta 2017. (määrätön)
↑ Meyer, 2000 , s. 514.
↑ 1 2 Ikramov, 1991 , s. 21.
↑ Voevodin ja Kuznetsov, 1984 , s. 80.
↑ Forsyth J., Malcolm M., Moler K. . Matemaattisten laskelmien konemenetelmät. — M .: Mir , 1980. — 280 s. — S. 214, 225.
↑ 1 2 3 Voevodin ja Kuznetsov, 1984 , s. 78.
↑ Gantmakher, 1988 , s. 234-236.
↑ Voevodin ja Kuznetsov, 1984 , s. 79.
↑ Gantmakher, 1988 , s. 244.
↑ Gantmakher, 1988 , s. 236.

Kirjallisuus

Voevodin V.V. , Kuznetsov Yu.A. Matriisit ja laskelmat. — M .: Nauka , 1984. — 320 s.
Gantmakher F. R. . Matriisi teoria. 4. painos — M .: Nauka , 1988. — 552 s. — ISBN 5-02-013722-7 .
Ikramov H.D. Epäsymmetrinen ominaisarvoongelma. Numeeriset menetelmät. — M .: Nauka , 1991. — 240 s. — ISBN 5-02-014462-2 .
Meyer, Carl D. . Matriisianalyysi ja sovellettu lineaarinen algebra . - Philadelphia: SIAM , 2000. - xii + 718 s. — ISBN 0-89871-454-0 .

Vektorit ja matriisit

Vektorit

Peruskonseptit	Vektori geometriassa Perusta Ortogonaalinen perusta Vektorikoordinaatit Kollineaarisuus Ortogonaalisuus Lineaarinen riippuvuus Saraketila
Vektorityypit	Yksikkövektori Aksiaalinen vektori isotrooppinen vektori Normaali Kollineaarisuus Nolla vektori Sädevektori Omavektori
Operaatiot vektoreille	Skalaarituote vektorituote sekoitettu tuote Pseudoskalaarinen tuote Kaksinkertainen ristituote
Tilatyypit	vektoriavaruus affinista tilaa Euklidinen avaruus Pseudoeuklidinen avaruus Normaali tila Minkowskin tila

matriiseja

Peruskonseptit	Matriisin kertolasku Transponoitu matriisi Hermitian konjugaattimatriisi Symmetrinen matriisi käänteinen matriisi Ominaisarvo Matriisin karakteristinen polynomi
Erikoismatriisit	Identiteettimatriisi Nolla matriisi Diagonaalinen matriisi lambda matriisi
Matriisihajotukset	LU:n hajoaminen Cholesky-hajoaminen QR-hajotus LUP-hajoaminen singulaariarvon hajottelu Matriisin spektrihajotus

Muut