LU nedbrydning

LU-nedbrydning ( LU-dekomponering , LU-faktorisering ) er en repræsentation af en matrix som et produkt af to matricer , hvor er en nedre trekantet matrix og er en øvre trekantet matrix. $EN$ $A=LU$ $L$ $U$

LU-dekomponeringen bruges til at løse systemer af lineære ligninger , invertere matricer og beregne determinanten . En LU-nedbrydning eksisterer kun, hvis matrixen er inverterbar, og alle førende (hjørne) hoved - minorer af matrixen er ikke- degenererede [1] . $EN$ $EN$

Denne metode er en af varianterne af Gauss-metoden .

Ansøgninger

Løsning af systemer af lineære ligninger

Den resulterende LU-nedbrydning af matricen (matrix af koefficienter for systemet) kan bruges til at løse en familie af systemer af lineære ligninger med forskellige vektorer på højre side [2] : $EN$ $b$

akse=b

Hvis LU-nedbrydningen af matrixen , , er kendt , kan det oprindelige system skrives som $EN$ $A=LU$

LUx=b.

Dette system kan løses i to trin. Det første skridt er at løse systemet

Ly=b.

Da det er en lavere trekantet matrix, løses dette system direkte ved direkte substitution . $L$

På andet trin er systemet løst

x=y.

Da det er en øvre trekantet matrix, løses dette system direkte ved tilbagesubstitution . $U$

Matrix inversion

Matrixinversion svarer til at løse et lineært system $EN$

AX=I

hvor er en ukendt matrix, er identitetsmatrixen. Løsningen på dette system er en omvendt matrix . $x$ $jeg$ $x$ $A^{{-1}}$

Systemet kan løses ved LU-nedbrydningsmetoden beskrevet ovenfor.

Beregning af determinanten for en matrix

I betragtning af LU-nedbrydningen af matrixen , $EN$

A=LU

vi kan direkte beregne dens determinant ,

\det(A)=\det(LU)=\det(L)\det(U)=\left(\prod _{{i=1}}^{n}L_{{ii}}\right)\ venstre(\prod _{{i=1}}^{n}U_{{ii}}\right)

hvor er størrelsen af matricen , og er de diagonale elementer i matricerne og . $n$ $EN$ $L_{{ii}}$ $U_{{ii}}$ $L$ $U$

Afledning af formlen

Baseret på anvendelsesomfanget kan LU-dekomponeringen kun anvendes på en ikke-singular matrix, derfor vil vi i det følgende antage, at matrixen er ikke- singular. $EN$

Da både i den første række af matricen og i den første kolonne af matrixen , alle elementer, undtagen muligvis det første, er lig nul, har vi $L$ $U$

a_{{11}}=l_{{11}}u_{{11}}

Hvis , så eller . I det første tilfælde består den første række af matrixen udelukkende af nuller , i den anden, den første kolonne af matrixen . Derfor, eller er degenereret, og dermed er degenereret , hvilket fører til en modsigelse. Således, hvis , så har den ikke-singulære matrix ikke en LU-nedbrydning. $a_{{11}}=0$ $l_{{11}}=0$ $u_{{11}}=0$ $L$ $U$ $L$ $U$ $EN$ $a_{{11}}=0$ $EN$

Lad , så og . Da L og U er defineret op til at gange U med en konstant og dividere L med den samme konstant, kan vi kræve, at . På samme tid . $a_{{11}}\neq 0$ $l_{{11}}\neq 0$ $u_{{11}}\neq 0$ $l_{{11}}=1$ $u_{{11}}=a_{{11}}$

Opdel matrix A i celler:

A={\begin{pmatrix}a_{{11}}&w^{T}\\v&A'\\\end{pmatrix}}

hvor har dimensioner henholdsvis , . $v,w^{T},A'$ $(N-1)\ gange 1$ $1\gange (N-1)$ $(N-1)\ gange (N-1)$

På samme måde deler vi os i celler i matrixen og : $L$ $U$

L={\begin{pmatrix}1&0\\v_{l}&L'\\\end{pmatrix)),\ U={\begin{pmatrix}a_{11}&w_{u}^{T} \\0&U'\\\end{pmatrix}}.

Ligningen tager formen $A=LU$

w^{T}=w_{u}^{T},

v=a_{11}v_{l},

A'=v_{l}w_{u}^{T}+L'U'.

Ved at løse ligningssystemet for , , , , får vi: $v_{l}$ ${\displaystyle w_{u))$ $L'$ $U'$

w_{u}=w,

v_{l}=v/a_{11},

L'U'=A'-vw^{T}/a_{11}.

Endelig har vi:

L={\begin{pmatrix}1&0\\v/a_{11}&L'\\\end{pmatrix)),

U={\begin{pmatrix}a_{11}&w^{T}\\0&U'\\\end{pmatrix)),

L'U'=A'-vw^{T}/a_{11}.

Så vi har reduceret LU-nedbrydningen af størrelsesmatrixen til LU-nedbrydningen af størrelsesmatrixen . $N\ gange N$ $(N-1)\ gange (N-1)$

Udtrykket kaldes Schur-komplementet af grundstoffet i matricen A [1] . $A'-vw^{T}/a_{{11}}$ $a_{11}$

Algoritme

En af algoritmerne til beregning af LU-nedbrydningen er angivet nedenfor. [3]

Vi vil bruge følgende notation til matrixelementer: , , , ; og de diagonale elementer i matrixen : , . $A=(a_{{ij}})$ $L=(l_{{ij}})$ $U=(u_{{ij}})$ $i,j=1\prikker n$ $L$ $l_{{ii}}=1$ $i=1\prikker n$

Du kan finde matricerne og som følger (trinene skal udføres strengt i rækkefølge, da følgende elementer findes ved hjælp af de foregående): $L$ $U$

Loop i fra 1 til n
1. Loop j fra 1 til n
  1. uij = 0, lij = 0
  2. l ii = 1
Loop i fra 1 til n
1. Loop j fra 1 til n
  1. Hvis jeg<=j: ${\displaystyle u_{ij}=a_{ij}-\sum _{k=1}^{i-1}l_{ik}*u_{kj))$
  2. Hvis i>j: ${\displaystyle l_{ij}=(a_{ij}-\sum _{k=1}^{j-1}l_{ik}*u_{kj})/u_{jj))$

Som følge heraf får vi matricer - og . $L$ $U$

Se også

Noter

↑ 1 2 E. E. Tyrtyshnikov. Matrixanalyse og lineær algebra. — 2004-2005.
↑ Levitin, 2006 .
↑ Verzhbitsky V.M. Grundlæggende om numeriske metoder. Lærebog for gymnasier. - Videregående skole, 2002. - S. 63-64. — ISBN 5-06-004020-8 .

Litteratur

Ortega J. Introduktion til parallelle og vektormetoder til løsning af lineære systemer. — M .: Mir, 1991. — 376 s. — ISBN 5-03-001941-3 .
Levitin A. V. Algoritmer. Introduktion til udvikling og analyse - M. : Williams , 2006. - 576 s. — ISBN 978-5-8459-0987-9

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