LUP bomlás

LUP-dekompozíció ( LUP -decomposition) - egy adott mátrix szorzatként való megjelenítése az identitásmátrixból sorok vagy oszlopok permutálásával nyert permutációs mátrix. Az ilyen bontás bármely nem degenerált mátrixra elvégezhető . A LUP-dekompozíció az inverz mátrix kiszámítására szolgál egy kompakt sémában, egy lineáris egyenletrendszer megoldásának kiszámításához. Az LU dekompozíciós algoritmushoz képest a LUP felbontó algoritmus bármilyen nem szinguláris mátrixot képes kezelni, ugyanakkor nagyobb számítási stabilitással rendelkezik. $A$ $PA=LU$ $L$ $U$ $P$ .

LUP dekompozíciós algoritmus

Legyen , , . A gyakorlatban általában a P permutációs mátrix helyett egy permutációs vektort használnak, amelyet a vektorból a P mátrixban permutált sorszámoknak megfelelő elemek permutálásával kapunk. Például, ha $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}}$

akkor , mivel a P mátrixot az első és a második sor felcserélésével kapjuk. A LUP kiterjesztésének kiszámítása több lépésben történik. Legyen a mátrix C = A. Minden i-edik lépésben először egy referencia (vezető) elemet keresünk – az i-edik oszlop azon elemei közül a legnagyobb modulusú elemet, amely nem magasabb az i-edik sornál , ami után a pivot elemet tartalmazó sor felcserélődik az i -edik sorra. Ugyanakkor ugyanazt a cserét hajtják végre a P mátrixban. Ebben az esetben, ha a mátrix nem szinguláris, akkor a referenciaelem garantáltan különbözik a nullától. Ezt követően az aktuális i-edik oszlop minden elemét az i-edik sor alatt osztja el a pivot. Továbbá az i-edik sor és az i-edik oszlop alatt található összes elemből (vagyis olyanból, hogy j>i és k>i) a szorzat kivonásra kerül . Ezt követően az i számlálót eggyel növeljük, és a folyamatot addig ismételjük, amíg i<n, ahol n az eredeti mátrix dimenziója. Az összes lépés befejezése után a C mátrix a következő összeg lesz: $p=(2,1,3)$ ${\displaystyle c_{jk))$ ${\displaystyle c_{ji}c_{ik))$

$C=L+UE$

ahol E az azonosságmátrix .

Az algoritmus három egymásba ágyazott lineáris hurkot használ, így az algoritmus teljes összetettsége O( n ³) becsülhető .

Az algoritmus implementációja C++ nyelven

Alább látható a fenti algoritmus programkódja C++ nyelven. Itt a Matrix egy olyan konténer, amely támogatja az indexelési műveletet. Kérjük, vegye figyelembe, hogy a visszaszámlálás nullától kezdődik, nem egytől.

void LUP ( const Matrix & A , Matrix & C , Matrix & P ) { //n - az eredeti mátrix dimenziója const int n = A . Sorok (); C = A ; //betöltjük a P mátrixba a P identitásmátrixot = IdentityMatrix ( ); for ( int i = 0 ; i < n ; i ++ ) { // pivot double pivotValue = 0 keresése ; int pivot = -1 ; for ( int sor = i ; sor < n ; sor ++ ) { if ( fabs ( C [ sor ][ i ]) > pivotValue ) { pivotValue = fabs ( C [ sor ][ i ]); pivot = sor ; } } if ( pivotValue != 0 ) { //az i-edik sort és a sort felcseréljük a P hivatkozási elemmel . 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 ]; } } } } //most C mátrix = L + U - E

Irodalom

Kormen, T. , Leizerson, C. , Rivest, R. , Stein, K. Algorithms: construction and analysis = Introduction to Algorithms / Szerk. I. V. Krasikova. - 2. kiadás - M. : Williams, 2005. - 1296 p. — ISBN 5-8459-0857-4 .

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