LU bomlás

Az LU-dekompozíció ( LU-dekompozíció , LU-faktorizáció ) egy mátrix ábrázolása két mátrix szorzataként , ahol egy alsó háromszögmátrix és egy felső háromszögmátrix. $A$ $A=LU$ $L$ $U$

Az LU dekompozíciót lineáris egyenletrendszerek megoldására , mátrixok invertálására és a determináns kiszámítására használják . LU dekompozíció csak akkor létezik, ha a mátrix invertálható, és a mátrix összes vezető (sarok) fő minorja nem degenerált [1] . $A$ $A$

Ez a módszer a Gauss-módszer egyik változata .

Alkalmazások

Lineáris egyenletrendszerek megoldása

A mátrix (a rendszer együtthatóinak mátrixa) eredményül kapott LU-dekompozíciója felhasználható lineáris egyenletrendszerek családjának megoldására, ahol a jobb oldalon különböző vektorok találhatók [2] : $A$ $b$

ax=b

Ha a , , mátrix LU dekompozíciója ismert , akkor az eredeti rendszer így írható fel $A$ $A=LU$

LUx=b.

Ezt a rendszert két lépésben lehet megoldani. Az első lépés a rendszer megoldása

Ly=b.

Mivel ez egy alsó háromszögmátrix, ezt a rendszert közvetlenül direkt helyettesítéssel oldják meg . $L$

A második lépésben a rendszer megoldódik

x=y.

Mivel ez egy felső háromszög mátrix, ez a rendszer közvetlenül visszahelyettesítéssel oldható meg . $U$

Mátrix inverzió

A mátrixinverzió egyenértékű egy lineáris rendszer megoldásával $A$

AX=I

ahol egy ismeretlen mátrix, az azonosságmátrix. Ennek a rendszernek a megoldása egy inverz mátrix . $x$ $én$ $x$ $A^{{-1}}$

A rendszer a fent leírt LU dekompozíciós módszerrel oldható meg.

Mátrix determinánsának kiszámítása

Adott a mátrix LU dekompozíciója , $A$

A=LU

közvetlenül ki tudjuk számítani a determinánsát ,

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

ahol a mátrix mérete , és a mátrixok átlós elemei és . $n$ $A$ $L_{{ii}}$ $U_{{ii}}$ $L$ $U$

A képlet származtatása

Az alkalmazási kör alapján az LU-felbontás csak nem szinguláris mátrixra alkalmazható, ezért a következőkben feltételezzük, hogy a mátrix nem szinguláris. $A$

Mivel a mátrix első sorában és a mátrix első oszlopában is minden elem, kivéve esetleg az elsőt, egyenlő nullával, így $L$ $U$

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

Ha , akkor vagy . Az első esetben a mátrix első sora teljes egészében nullákból áll , a másodikban pedig a mátrix első oszlopa . Ezért a vagy degenerált, és ennélfogva degenerált , ami ellentmondáshoz vezet. Így ha , akkor a nem szinguláris mátrixnak nincs LU dekompozíciója. $a_{{11}}=0$ $l_{{11}}=0$ $u_{{11}}=0$ $L$ $U$ $L$ $U$ $A$ $a_{{11}}=0$ $A$

Hagyjuk , majd és . Mivel L és U úgy van definiálva, hogy U-t megszorozzuk egy konstanssal, és elosztjuk L-t ugyanazzal az állandóval, megkövetelhetjük, hogy . Ugyanakkor . $a_{{11}}\neq 0$ $l_{{11}}\neq 0$ $u_{{11}}\neq 0$ $l_{{11}}=1$ $u_{{11}}=a_{{11}}$

Ossza fel az A mátrixot cellákra:

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

ahol a méretek rendre , , . $v,w^{T},A'$ ${\megjelenítési stílus (N-1)\times 1}$ $1\times (N-1)$ ${\megjelenítési stílus (N-1)\times (N-1)}$

Hasonlóképpen osztjuk a mátrix sejtjeire, és : $L$ $U$

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

Az egyenlet felveszi a formát $A=LU$

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

v=a_{11}v_{l},

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

Megoldva a , , , egyenletrendszert , megkapjuk: ${\displaystyle v_{l))$ ${\displaystyle w_{u))$ $L'$ $U'$

w_{u}=w,

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

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

Végül nálunk van:

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}.

Tehát a méretmátrix LU dekompozícióját a méretmátrix LU dekompozíciójára redukáltuk . $N\times N$ ${\megjelenítési stílus (N-1)\times (N-1)}$

A kifejezést az A mátrixban szereplő elem Schur-komplementerének nevezzük [1] . $A'-vw^{T}/a_{{11}}$ $a_{11}$

Algoritmus

Az alábbiakban bemutatjuk az LU-felbontás kiszámításának egyik algoritmusát. [3]

A mátrixelemekhez a következő jelölést fogjuk használni: , , , ; és a mátrix átlós elemei : , . $A=(a_{{ij}})$ $L=(l_{{ij}})$ $U=(u_{{ij}})$ $i,j=1\pont n$ $L$ $l_{{ii}}=1$ $i=1\pont n$

A mátrixokat és a következőképpen találhatja meg (a lépéseket szigorúan sorrendben kell végrehajtani, mivel a következő elemek találhatók az előzőek használatával): $L$ $U$

i hurok 1-től n-ig
1. j hurok 1-től n-ig
  1. uij = 0, lij = 0
  2. l ii =1
i hurok 1-től n-ig
1. j hurok 1-től n-ig
  1. Ha i<=j: ${\displaystyle u_{ij}=a_{ij}-\sum _{k=1}^{i-1}l_{ik}*u_{kj))$
  2. Ha i>j: ${\displaystyle l_{ij}=(a_{ij}-\sum _{k=1}^{j-1}l_{ik}*u_{kj})/u_{jj))$

Ennek eredményeként mátrixokat kapunk - és . $L$ $U$

Lásd még

Jegyzetek

↑ 1 2 E. E. Tirtysnyikov. Mátrixanalízis és lineáris algebra. — 2004-2005.
↑ Levitin, 2006 .
↑ Verzsbitszkij V.M. A numerikus módszerek alapjai. Tankönyv középiskoláknak. - Felsőiskola, 2002. - S. 63-64. — ISBN 5-06-004020-8 .

Irodalom

Ortega J. Bevezetés a lineáris rendszerek megoldásának párhuzamos és vektoros módszereibe. — M .: Mir, 1991. — 376 p. — ISBN 5-03-001941-3 .
Levitin A. V. Algoritmusok. Bevezetés a fejlesztésbe és elemzésbe - M .: Williams , 2006. - 576 p. — ISBN 978-5-8459-0987-9

Vektorok és mátrixok

Vektorok

Alapfogalmak	Vektor a geometriában Alap Ortogonális alap Vektor koordináták Kollinearitás Ortogonalitás Lineáris függőség Oszlopköz
A vektorok fajtái	Egységvektor Axiális vektor izotróp vektor Normál Kollinearitás Nulla vektor Sugár vektor Sajátvektor
Műveletek vektorokon	Skaláris szorzat vektor termék vegyes termék Pszeudoszkaláris termék Kettős kereszttermék
Tértípusok	vektor tér affin tér Euklideszi tér Pszeudoeuklideszi tér Normált tér Minkowski tér

mátrixok

Alapfogalmak	Mátrixszorzás Transzponált mátrix Hermitikus konjugált mátrix Szimmetrikus mátrix inverz mátrix Sajátérték Mátrix karakterisztikus polinomja
Speciális mátrixok	Identitásmátrix Nulla mátrix Átlós mátrix lambda mátrix
Mátrix dekompozíciók	LU bomlás Cholesky-bomlás QR-bontás LUP bomlás szinguláris érték felbontás Mátrix spektrális lebontása

Egyéb