LU rozklad

LU-dekompozice ( LU-decomposition , LU-factorization ) je zobrazení matice jako součinu dvou matic, , kde je spodní trojúhelníková matice a je horní trojúhelníková matice. $A$ $A = LU$ $L$ $U$

Rozklad LU se používá k řešení soustav lineárních rovnic , invertování matic a výpočtu determinantu . Rozklad LU existuje pouze v případě, že matice je invertibilní a všechny úvodní (rohové) hlavní minority matice jsou nedegenerované [1] . $A$ $A$

Tato metoda je jednou z odrůd Gaussovy metody .

Aplikace

Řešení soustav lineárních rovnic

Výsledný LU-rozklad matice (matice koeficientů systému) lze použít k řešení řady soustav lineárních rovnic s různými vektory na pravé straně [2] : $A$ $b$

sekera=b

Pokud je znám rozklad LU matice , , lze původní systém zapsat jako $A$ $A = LU$

LUx=b.

Tento systém lze vyřešit ve dvou krocích. Prvním krokem je vyřešení systému

Ly=b.

Protože se jedná o nižší trojúhelníkovou matici, je tento systém řešen přímo přímou substitucí . $L$

Ve druhém kroku je systém vyřešen

x=y.

Protože se jedná o horní trojúhelníkovou matici, je tento systém řešen přímo zpětnou substitucí . $U$

Inverze matice

Maticová inverze je ekvivalentní řešení lineárního systému $A$

AX=I

kde je neznámá matice, je matice identity. Řešením tohoto systému je inverzní matice . $X$ $já$ $X$ $A^{{-1}}$

Systém lze řešit výše popsanou metodou rozkladu LU.

Výpočet determinantu matice

Vzhledem k LU rozkladu matice , $A$

A = LU

můžeme přímo vypočítat jeho determinant ,

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

kde je velikost matice a jsou diagonální prvky matic a . $n$ $A$ $L_{{ii}}$ $U_{{ii}}$ $L$ $U$

Odvození vzorce

Na základě rozsahu aplikace lze LU rozklad aplikovat pouze na nesingulární matici, proto v následujícím budeme předpokládat, že matice je nesingulární. $A$

Protože jak v prvním řádku matice, tak v prvním sloupci matice jsou všechny prvky, možná kromě prvního, rovny nule, máme $L$ $U$

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

Pokud , tak nebo . V prvním případě se první řádek matice skládá výhradně z nul , ve druhém z prvního sloupce matice . Proto, nebo je degenerované, a tudíž je degenerované , což vede k rozporu. Pokud tedy , pak nesingulární matice nemá rozklad LU. $a_{{11}}=0$ $l_{{11}}=0$ $u_{{11}}=0$ $L$ $U$ $L$ $U$ $A$ $a_{{11}}=0$ $A$

Nechte , pak a . Protože L a U jsou definovány až po násobení U konstantou a dělení L stejnou konstantou, můžeme požadovat, aby . Ve stejnou dobu . $a_{{11}}\neq 0$ $l_{{11}}\neq 0$ $u_{{11}}\neq 0$ $l_{{11}}=1$ $u_{{11}}=a_{{11}}$

Rozdělte matici A na buňky:

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

kde mít rozměry , , . $v,w^{T},A'$ $(N-1)\times 1$ $1\times (N-1)$ $(N-1)\times (N-1)$

Podobně dělíme na buňky matice a : $L$ $U$

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

Rovnice má tvar $A = LU$

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

v=a_{11}v_{l},

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

Řešením soustavy rovnic pro , , , , dostaneme: ${\displaystyle v_{l))$ ${\displaystyle w_{u))$ $L'$ $U'$

w_{u}=w,

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

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

Nakonec máme:

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

Takže jsme redukovali LU rozklad matice velikostí na LU rozklad matice velikostí . $N\times N$ $(N-1)\times (N-1)$

Výraz se nazývá Schurův doplněk prvku v matici A [1] . $A'-vw^{T}/a_{{11}}$ $a_{11}$

Algoritmus

Jeden z algoritmů pro výpočet rozkladu LU je uveden níže. [3]

Pro prvky matice použijeme následující zápis: , , , ; a diagonální prvky matice : , . $A=(a_{{ij}})$ $L=(l_{{ij}})$ $U=(u_{{ij}})$ $i,j=1\tečky n$ $L$ $l_{{ii}}=1$ $i=1\tečky n$

Můžete najít matice a následovně (kroky by měly být prováděny přesně v pořadí, protože následující prvky se nacházejí pomocí předchozích): $L$ $U$

Smyčka i od 1 do n
1. Smyčka j od 1 do n
  1. uij = 0, lij = 0
  2. l ii = 1
Smyčka i od 1 do n
1. Smyčka j od 1 do n
  1. Pokud i<=j: ${\displaystyle u_{ij}=a_{ij}-\sum _{k=1}^{i-1}l_{ik}*u_{kj))$
  2. Pokud i>j: ${\displaystyle l_{ij}=(a_{ij}-\sum _{k=1}^{j-1}l_{ik}*u_{kj})/u_{jj))$

V důsledku toho dostaneme matice - a . $L$ $U$

Viz také

Poznámky

↑ 1 2 E. E. Tyrtyšnikov. Maticová analýza a lineární algebra. — 2004-2005.
↑ Levitin, 2006 .
↑ Verzhbitsky V.M. Základy numerických metod. Učebnice pro střední školy. - Vyšší škola, 2002. - S. 63-64. — ISBN 5-06-004020-8 .

Literatura

Ortega J. Úvod do paralelních a vektorových metod řešení lineárních systémů. — M .: Mir, 1991. — 376 s. — ISBN 5-03-001941-3 .
Levitin A. V. Algorithms. Úvod do vývoje a analýzy - M .: Williams , 2006. - 576 s. — ISBN 978-5-8459-0987-9

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ý