Matrix nedbrydning

Matrixnedbrydning er en repræsentation af en matrix som et produkt af matricer, der har nogle specifikke egenskaber (for eksempel ortogonalitet , symmetri , diagonalitet ). Hver klasse af matrixnedbrydninger har sit eget anvendelsesområde; især er mange effektive beregningsmæssige lineære algebraalgoritmer baseret på konstruktionen af de tilsvarende matrixudvidelser. $EN$

Udvidelser til løsning af SLAE

LU-nedbrydning

Begrænsninger: Matrixen er kvadratisk og ikke- degenereret , og alle dens førende hovedbiord er ikke-nul [1] . $EN$
Nedbrydningstype: , hvor er den nederste trekantede matrix , og er den øverste trekantede matrix . For entydige udvidelser kræves det normalt yderligere, at matricen var entriangulær , dvs. en trekantet matrix med diagonale indgange lig med én (nogle gange pålægges enhedskravet i stedet for matricen ) [2] . $A=LU$ $L$ $U$ $L$ $U$
Lignende nedbrydninger: LDU -nedbrydning i form , hvor er den nederste entriangulære matrix, er den øverste enhedstriangulære matrix og er diagonal $A=LDU$ $L$ $U$ $D$
Lignende udvidelser : LUP -nedbrydning i formen _ _ _ Dette er en generalisering af LU -dekomponeringen til tilfældet med vilkårlige ikke-degenererede matricer. $PA=LU$ $P$ $L$ $U$
Eksistens: En LUP -nedbrydning eksisterer for enhver kvadratisk matrix . Når matrixen er reduceret til identitetsmatrixen , reduceres LUP - nedbrydningen til LU - nedbrydningen. $EN$ $P$
LUP og LU -nedbrydninger bruges til at løse SLAE af dimension . De tilsvarende metoder er varianter af matrixformen af den Gaussiske metode . Matrixen karakteriserer den kumulative effekt af rækkepermutationer i Gauss-metoden. $akse=b$ $n\ gange n$ $P$

Rangfaktorisering

Begrænsninger: vilkårlig matrix af størrelse og rang . $EN$ $m\ gange n$ $r$

Nedbrydningstype: , hvor er matrixen og er matrixen . $A=CF$ $C$ $m\times r$ $F$ $r\times n$
Rangfaktorisering kan bruges til at beregne den pseudoinverse matrix , som bruges til at finde den generelle løsning af SLAE . $akse=b$

Kolesky nedbrydning

Begrænsninger: symmetrisk positiv bestemt matrix [3] . $EN$
Nedbrydningstype: (eller tilsvarende ), hvor matrixen er øvre trekantet (henholdsvis matrixen er nedre trekantet ) [3] . $A=U^{T}U$ $A=LL^{T}$ $U$ $L$
Lignende nedbrydninger: et alternativ er den modificerede Cholesky-nedbrydning ( LDL - nedbrydning ), som undgår udvinding af rødder (hvor matricen er lavere enhedstriangulær og diagonal ). $L$ $D$
Cholesky-nedbrydningen er unik.
Cholesky-nedbrydningen er også anvendelig, hvis matrixen er hermitisk og positiv bestemt . $EN$
Cholesky-nedbrydningen anvendes til at løse SLAE, hvis matrixen har de passende egenskaber. Denne løsningsmetode er i sammenligning med LU-nedbrydningsmetoden bestemt numerisk stabil og kræver halvt så mange aritmetiske operationer [4] . $akse=b$ $EN$

QR-nedbrydning

Begrænsninger: vilkårlig matrix af størrelse . $EN$ $m\ gange n$
Nedbrydningstype: , hvor er en ortogonal matrix af størrelse , og er en øvre trekantet matrix af størrelse . $A = QR$ $Q$ $m\times m$ $R$ $m\ gange n$
Lignende nedbrydninger: Der er analoge QL -, RQ - og LQ -nedbrydninger.
På grund af matrixens ortogonalitet (hvilket betyder, at den inverse matrix falder sammen med den transponerede matrix ), svarer systemet til et system med en trekantet matrix, hvis løsning ikke er svær. $Q$ $Q^{-1}$ $Q^{T}$ $akse=b$ $Rx=Q^{T}b$
En af måderne at opnå en matrix på er Gram-Schmidt-processen og derefter . $Q$ $R=Q^{T}A$
Konstruktionen af en QR - nedbrydning er grundlaget for QR-algoritmen , som er en af metoderne til at søge efter egenvektorer og matrixværdier.
Algoritmer til løsning af SLAE baseret på QR - nedbrydningen virker næsten ligeligt for både velkonditionerede og singulære systemer [5] .

Interpolationsudvidelse

Begrænsninger: vilkårlig matrix af dimension og rang . $EN$ $m\ gange n$ $r$
Type af nedbrydning: , hvor er en delmængde af indekser ; matrixen består af de tilsvarende kolonner i den oprindelige matrix; er en matrix, hvis alle elementer er modulo ikke mere end 2 (derudover indeholder den en enhedsundermatrix af dimension ). En lignende nedbrydning kan opnås i rækker. $A=A_{(:,J)}X$ $J$ $r$ $1,...,n$ ${\displaystyle A_{(:,J)))$ $x$ $r\times n$ $x$ $r\ gange r$

Egenværdi- eller entalsværdiudvidelser

Spektral nedbrydning

Begrænsninger: en diagonaliserbar kvadratisk matrix , dvs. har et sæt af forskellige egenvektorer ( egenværdierne behøver ikke være forskellige). $EN$ $n$
Udvidelsestype: , hvor er diagonalen dannet ud fra egenværdierne , og søjlerne er de tilsvarende egenvektorer . $A=VDV^{-1}$ $D$ $EN$ $V$
Eksistens: En dimensionsmatrix har altid egenværdier (tællende multiplicitet), der kan bestilles (ikke på en unik måde) til at konstruere en diagonal dimensionsmatrix og en tilsvarende matrix af ikke-nul kolonner , der opfylder ligheden . Hvis egenvektorerne er forskellige, så har matrixen en invers, som vil give den ønskede ekspansion [6] . $n\ gange n$ $n$ $D$ $n\ gange n$ $V$ $AV=VD$ $n$ $V$ $A=VDV^{-1}$
Det er altid muligt at normalisere egenvektorer, så de har længde 1. Hvis en reel symmetrisk matrix, så er den altid inverterbar og normaliserbar. I dette tilfælde viser matricen sig at være ortogonal, da egenvektorerne er ortogonale i forhold til hinanden. Den ønskede udvidelse (som altid eksisterer i det pågældende tilfælde) kan således skrives som . $EN$ $V$ $V$ $A=VDV^{T}$
En nødvendig og tilstrækkelig betingelse for diagonaliserbarhed er sammenfaldet af den geometriske og algebraiske multiplicitet af hver egenværdi. Især er eksistensen af distinkte egenværdier en tilstrækkelig (men ikke nødvendig) betingelse. $n$
Den spektrale nedbrydning er nyttig til at forstå løsninger til systemer med lineære ordinære differentialligninger eller differensligninger . For eksempel har en differensligning med en startbetingelse en løsning , som kan skrives anderledes som (i tilfælde ). At hæve en diagonal matrix til en potens vil reducere til at hæve hvert element på diagonalen til en potens , hvilket er uforlignelig enklere end (medmindre, selvfølgelig, sidstnævnte oprindeligt har en diagonal form). ${\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$ $EN$

Jordan normal form

Begrænsninger: kvadratisk matrix . $EN$
Udvidelsestype: , hvor er Jordan-matricen, og er overgangsmatrixen til et nyt grundlag. $A=CJC^{-1}$ $J$ $C$
Jordan normalformen er en generalisering af egenværdimatricens diagonale form til det tilfælde, hvor den geometriske multiplicitet af en eller flere egenværdier er mindre end den algebraiske multiplicitet . $EN$

Schur nedbrydning

Begrænsninger: kvadratisk matrix . $EN$
Der er to versioner af dekomponering: for tilfældet med en reel matrix og for tilfældet med en kompleks matrix. Sidstnævnte har altid en kompleks Schur-nedbrydning.
Type af nedbrydning (reelle tilfælde): (alle matricer i begge dele af ligheden er sammensat af strengt reelle værdier). I dette tilfælde er en ortogonal matrix , og er en kvasi -trekant matrix . Sidstnævnte kaldes den rigtige Schur-form . Blokkene på diagonalen er enten af størrelse (i hvilket tilfælde de er reelle egenværdier) eller (dannet af et par komplekse konjugerede egenværdier). $A=VSV^{T}$ $V$ $S$ $S$ $1 gange 1$ $2 gange 2$
Nedbrydningstype (komplekst tilfælde): , hvor er ensartet , er dets hermitiske konjugat , og er en øvre trekantet matrix, kaldet den komplekse Schur-form , som indeholder egenværdier på diagonalen. $A=UTU^{H}$ $U$ $U^{H}$ $T$ $EN$

QZ-nedbrydning

Begrænsninger: kvadratiske matricer og . $EN$ $B$
Der er to versioner af nedbrydning: kompleks og reel.
Ekspansionstype (komplekst tilfælde): , hvor og er enhedsmatricer , er hermitisk konjugat til , og er øvre trekantede matricer . $A=QSZ^{H},B=QTZ^{H}$ $Q$ $Z$ $Z^{H}$ $Z$ $S$ $T$
I den specificerede dekomponering er forholdet mellem diagonale elementer i og svarende til , generaliserede egenværdier, som er løsningen på det generaliserede problem med at finde egenværdier (hvor er en ukendt skalar og er en ukendt ikke-nul vektor). $S$ $T$ ${\displaystyle \lambda _{i}=S_{ii}/T_{ii))$ $Av=\lambda Bv$ $\lambda$ $v$
Dekomponeringstype (reelt tilfælde): , hvor alle matricer udelukkende består af reelle værdier. er ortogonale matricer, og er kvasi -triangulære matricer , bestående af blokke eller (svarende til de tilsvarende blokke i Schur-udvidelsen). $A=QSZ^{T},B=QTZ^{T}$ $Q,Z$ $S,T$ $1 gange 1$ $2 gange 2$

Singular værdi nedbrydning

Begrænsninger: vilkårlig størrelse matrix [7] . $EN$ $m\ gange n$
Type af nedbrydning: , hvor er en ikke-negativ diagonal matrix , er enhedsmatricer , og er hermitisk konjugat . I det virkelige tilfælde , og som før , er den ikke-negative diagonale matrix ortogonale [7] [8] . $A=U\Sigma V^{H}$ $\Sigma$ $U,V$ $V^{H}$ $A=U\Sigma V^{T}$ $\Sigma$ $U,V$
Elementer på diagonalen af en matrix kaldes singulære værdier af en matrix og betegnes Antallet af singulære værdier, der ikke er nul, er lig med rangeringen af denne matrix [9] . $\Sigma$ $EN$ $\sigma _{j}.$ $EN$
Singular nedbrydning, ligesom spektral nedbrydning, omfatter at finde grundlaget for underrum, handlingen af operatoren på hvis elementer er ækvivalent med multiplikation med en skalar (dvs. ), men singular værdi dekomponering er en mere generel metode, da matricen ikke har at være firkantet. $\mathcal{A}$ $Av=\sigma _{j}v$ $EN$

Andre udvidelser

Polær ekspansion

Begrænsninger: kvadratisk kompleks matrix [10] . $EN$
Ekspansionstype (komplekst kasus): , hvor er en hermitisk matrix med ikke-negative ledende mindreårige og er en enhedsmatrix [10] [11] . $A=SU$ $S$ $U$
Ekspansionstype (reelle tilfælde): , hvor er en symmetrisk matrix med ikke-negative ledende mol, og er en ortogonal matrix [12] [13] . $A=SQ$ $S$ $Q$
For en ikke-degenereret matrix er den polære nedbrydning unik, og for en degenereret matrix er kun faktoren entydigt defineret [10] . $S$
Den polære nedbrydning af en matrix i det komplekse tilfælde er analog med repræsentationen af et vilkårligt komplekst tal i formen [14] . $z$ ${\displaystyle z=|z|e^{i\varphi ))$

Frobenius normalform

Begrænsninger: kvadratisk matrix . $EN$
Nedbrydningstype: , hvor er en blok-diagonal matrix bestående af ledsagende matricer for unitære polynomier , sådan som er et multiplum af . er en overgangsmatrix. $A=PCP^{-1}$ $C$ $f_{i}$ $f_{{i+1}}$ $f_{i}$ $P$

Noter

↑ Ikramov, 1991 , s. tyve.
↑ Voevodin og Kuznetsov, 1984 , s. 75-76.
↑ 1 2 Voevodin og Kuznetsov, 1984 , s. 176.
↑ William H. Press, Saul A. Teukolsky, William T. Vetterling, Brian P. Flannery. . 2.9 Cholesky Decomposition // Numeriske opskrifter i C. 2. udgave. — Cambridge: Cambridge University Press. - ISBN 0-521-43108-5 .
↑ QR- og SVD-nedbrydninger: "dårlige" SLAE'er . Hentet 17. november 2016. Arkiveret fra originalen 22. juni 2017. (ubestemt)
↑ Meyer, 2000 , s. 514.
↑ 1 2 Ikramov, 1991 , s. 21.
↑ Voevodin og Kuznetsov, 1984 , s. 80.
↑ Forsyth J., Malcolm M., Moler K. . Maskinelle metoder til matematiske beregninger. — M .: Mir , 1980. — 280 s. — S. 214, 225.
↑ 1 2 3 Voevodin og Kuznetsov, 1984 , s. 78.
↑ Gantmakher, 1988 , s. 234-236.
↑ Voevodin og Kuznetsov, 1984 , s. 79.
↑ Gantmakher, 1988 , s. 244.
↑ Gantmakher, 1988 , s. 236.

Litteratur

Voevodin V.V. , Kuznetsov Yu.A. Matricer og beregninger. — M .: Nauka , 1984. — 320 s.
Gantmakher F. R. . Matrix teori. 4. udg. — M .: Nauka , 1988. — 552 s. — ISBN 5-02-013722-7 .
Ikramov H. D. . Asymmetrisk egenværdi problem. Numeriske metoder. — M .: Nauka , 1991. — 240 s. — ISBN 5-02-014462-2 .
Meyer, Carl D. . Matrixanalyse og anvendt lineær algebra . - Philadelphia: SIAM , 2000. - xii + 718 s. — ISBN 0-89871-454-0 .

Vektorer og matricer

Vektorer

Basale koncepter	Vektor i geometri Basis Ortogonalt grundlag Vektorkoordinater Kolinearitet Ortogonalitet Lineær afhængighed Søjleplads
Slags vektorer	Enhedsvektor Aksial vektor isotrop vektor Normal Kolinearitet Nul vektor Radius vektor Egenvektor
Operationer på vektorer	Skalært produkt vektor produkt blandet produkt Pseudoskalært produkt Dobbelt kryds produkt
Rumtyper	vektor rum affint rum Euklidisk rum Pseudo-euklidisk rum Normeret rum Minkowski plads

matricer

Basale koncepter	Matrix multiplikation Transponeret matrix Hermitisk konjugeret matrix Symmetrisk matrix omvendt matrix Egenværdi Karakteristisk polynomium af en matrix
Særlige matricer	Identitetsmatrix Nul matrix Diagonal matrix lambda matrix
Matrix nedbrydninger	LU nedbrydning Kolesky nedbrydning QR-nedbrydning LUP nedbrydning singular værdi nedbrydning Spektral nedbrydning af en matrix

Andet