Rozklad LUP

LUP-decomposition ( LUP -decomposition) - reprezentace dané matice jako produktu permutační matice získaná z matice identity permutací řádků nebo sloupců. Takový rozklad lze provést pro jakoukoli nedegenerovanou matrici. LUP-dekompozice se používá k výpočtu inverzní matice v kompaktním schématu, k výpočtu řešení soustavy lineárních rovnic. Ve srovnání s LU dekompozičním algoritmem si LUP dekompoziční algoritmus poradí s jakýmikoli nedegenerovanými maticemi a zároveň má vyšší výpočetní stabilitu . $A$ $PA=LU$ $L$ $U$ $P$

Algoritmus rozkladu LUP

Nech , , . V praxi se zpravidla místo permutační matice P používá permutační vektor získaný z vektoru permutací prvků odpovídajících číslům řádků permutovaných v matici P. Např. $A=(a_{{ij}})$ $L=(l_{{ij}})$ $U=(u_{{ij}})$ $p_{i}=(1,2,...,n)$

$P={\begin{pmatrix}0&1&0\\1&0&0\\0&0&1\\\end{pmatrix}}$

potom , protože matice P se získá záměnou prvního a druhého řádku. Výpočet rozšíření LUP se provádí v několika krocích. Nechť matici C = A. V každém i-tém kroku se nejprve hledá referenční (vedoucí) prvek — prvek s maximálním modulem mezi prvky i-tého sloupce, které nejsou vyšší než i-tý řádek , načež se řada s otočným prvkem prohodí s i -tou čárou. Současně se stejná výměna provádí v matici P. V tomto případě, pokud je matice nesingulární, je zaručeno, že referenční prvek bude odlišný od nuly. Poté jsou všechny prvky aktuálního i-tého sloupce pod i-tým řádkem rozděleny pivotem. Dále od všech prvků umístěných pod i-tým řádkem a i-tým sloupcem (tj. takových, že j>i a k>i) se odečte součin . Poté se čítač i zvýší o jedničku a proces se opakuje, dokud i<n, kde n je rozměr původní matice. Po dokončení všech kroků bude matice C následující součet: $p=(2,1,3)$ ${\displaystyle c_{jk))$ ${\displaystyle c_{ji}c_{ik))$

$C=L+UE$

kde E je matice identity .

Algoritmus používá tři vnořené lineární smyčky, takže celkovou složitost algoritmu lze odhadnout jako O( n ³).

Implementace algoritmu v C++

Níže je uveden programový kód výše uvedeného algoritmu v C++. Zde Matrix je nějaký kontejner, který podporuje operaci indexování. Upozorňujeme, že odpočítávání je od nuly, nikoli od jedné.

void LUP ( const Matrix & A , Matrix & C , Matrix & P ) { //n - rozměr původní matice const int n = A . Řádky (); C = A ; //nahrání do matice P matici identity P = IdentityMatrix (); for ( int i = 0 ; i < n ; i ++ ) { //hledání pivotu double pivotValue = 0 ; int pivot = -1 ; for ( int řádek = i ; řádek < n ; řádek ++ ) { if ( fabs ( C [ řádek ][ i ]) > pivotValue ) { pivotValue = fabs ( C [ řádek ][ i ]); pivot = řada ; } } if ( pivotValue != 0 ) { //prohoď i-tý řádek a řádek s referenčním prvkem P . SwapRows ( pivot , i ); C. _ SwapRows ( pivot , i ); for ( int j = i + 1 ; j < n ; j ++ ) { C [ j ][ i ] /= C [ i ][ i ]; for ( int k = i + 1 ; k < n ; k ++ ) C [ j ][ k ] -= C [ j ][ i ] * C [ i ][ k ]; } } } } //nyní matice C = L + U - E

Literatura

Kormen, T. , Leizerson, C. , Rivest, R. , Stein, K. Algoritmy: konstrukce a analýza = Introduction to Algorithms / Ed. I. V. Krasíková. - 2. vyd. - M. : Williams, 2005. - 1296 s. — ISBN 5-8459-0857-4 .

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ý