LUP nedbrydning

LUP-dekomponering ( LUP -dekomponering) - repræsentation af en given matrix som et produkt en permutationsmatrix opnået fra identitetsmatrixen ved at permutere rækker eller kolonner. En sådan nedbrydning kan udføres for enhver ikke- degenereret matrix. LUP-dekomponering bruges til at beregne den inverse matrix i et kompakt skema, til at beregne løsningen af et system af lineære ligninger. Sammenlignet med LU-dekomponeringsalgoritmen kan LUP-dekomponeringsalgoritmen håndtere alle ikke-singulære matricer og har på samme tid højere beregningsstabilitet $EN$ $PA=LU$ $L$ $U$ $P$ .

LUP-nedbrydningsalgoritme

Lad , , . I praksis anvendes som regel i stedet for permutationsmatricen P en permutationsvektor, der opnås fra vektoren ved at permutere de elementer, der svarer til rækkenumrene permuteret i matricen P. Hvis f.eks. $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}}$

da , da matrixen P opnås ved at ombytte den første og anden række. Beregningen af LUP-udvidelsen udføres i flere trin. Lad matrixen C = A. Ved hvert i-te trin søges først efter et referenceelement (førende) - elementet med det maksimale modul blandt elementerne i den i-te kolonne, der ikke er højere end den i-te række , hvorefter rækken med pivotelementet ombyttes med i-te linje. Samtidig udføres den samme udveksling i matricen P. I dette tilfælde, hvis matrixen er ikke-singular, er referenceelementet garanteret at være forskelligt fra nul. Derefter bliver alle elementer i den aktuelle i-te kolonne under den i-te række divideret med pivoten. Yderligere, fra alle elementer placeret under den i-te række og i-te kolonne (det vil sige sådan, at j>i og k>i), trækkes produktet fra . Derefter øges tælleren i med én, og processen gentages indtil i<n hvor n er dimensionen af den oprindelige matrix. Når alle trin er gennemført, vil matrix C være følgende sum: $p=(2,1,3)$ ${\displaystyle c_{jk))$ ${\displaystyle c_{ji}c_{ik))$

$C=L+UE$

hvor E er identitetsmatrixen .

Algoritmen bruger tre indlejrede lineære sløjfer, så den samlede kompleksitet af algoritmen kan estimeres som O( n ³).

Implementering af algoritmen i C++

Nedenfor er programkoden for ovenstående algoritme i C++. Her er Matrix en container, der understøtter indekseringsoperationen. Bemærk venligst, at nedtællingen er fra nul, ikke fra én.

void LUP ( const Matrix & A , Matrix & C , Matrix & P ) { //n - dimension af den oprindelige matrix const int n = A . Rækker (); C = A ; //indlæs i matrix P identitetsmatrixen P = IdentityMatrix (); for ( int i = 0 ; i < n ; i ++ ) { //søg efter en pivot double pivotValue = 0 ; int pivot = -1 ; for ( int række = i ; række < n ; række ++ ) { if ( fabs ( C [ row ][ i ]) > pivotValue ) { pivotValue = fabs ( C [ række ][ i ]); pivot = række ; } } if ( pivotValue != 0 ) { //byt den i-te linje og linjen med referenceelementet 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 ]; } } } } //nu matrix C = L + U - E

Litteratur

Kormen, T. , Leizerson, C. , Rivest, R. , Stein, K. Algoritmer: konstruktion og analyse = Introduktion til algoritmer / Ed. I. V. Krasikova. - 2. udg. - M. : Williams, 2005. - 1296 s. — ISBN 5-8459-0857-4 .

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