LUP-nedbrytning

LUP-nedbrytning ( LUP -dekomponering) - representation av en given matris som en produkt en permutationsmatris erhållen från identitetsmatrisen genom att permutera rader eller kolumner. En sådan sönderdelning kan utföras för vilken icke degenererad matris som helst. LUP-nedbrytning används för att beräkna den inversa matrisen i ett kompakt schema, för att beräkna lösningen av ett system av linjära ekvationer. Jämfört med LU-sönderdelningsalgoritmen kan LUP-sönderdelningsalgoritmen hantera alla icke-degenererade matriser och har samtidigt högre beräkningsstabilitet .

LUP-sönderdelningsalgoritm

Låt , , . I praktiken används som regel istället för permutationsmatrisen P en permutationsvektor, erhållen från vektorn genom att permutera de element som motsvarar radnumren permuterade i matrisen P. Om t.ex.

sedan , eftersom matrisen P erhålls genom att växla de första och andra raden. Beräkningen av LUP-expansionen utförs i flera steg. Låt matrisen C = A. Vid varje i:te steget söks först efter ett referenselement (ledande) — elementet med den maximala modulen bland elementen i den i:te kolumnen som inte är högre än den i:te raden , varefter raden med pivotelementet byts ut med i-te raden. Samtidigt utförs samma utbyte i matrisen P. I det här fallet, om matrisen är icke-singular, är referenselementet garanterat annorlunda än noll. Därefter delas alla element i den aktuella i:te kolumnen under den i:te raden med pivoten. Vidare, från alla element som finns under den i:te raden och i:te kolumnen (det vill säga så att j>i och k>i), subtraheras produkten . Därefter inkrementeras räknaren i med ett och processen upprepas tills i<n där n är dimensionen för den ursprungliga matrisen. När alla steg är slutförda kommer matrisen C att vara följande summa:

där E är identitetsmatrisen .

Algoritmen använder tre kapslade linjära slingor, så den övergripande komplexiteten för algoritmen kan uppskattas som O( n ³).

Implementering av algoritmen i C++

Nedan finns programkoden för ovanstående algoritm i C++. Här är Matrix någon behållare som stöder indexeringsoperationen. Observera att nedräkningen är från noll, inte från ett.

void LUP ( const Matrix & A , Matrix & C , Matrix & P ) { //n - dimension av den ursprungliga matrisen const int n = A . Rader (); C = A ; //ladda in i matris P identitetsmatrisen P = IdentityMatrix (); for ( int i = 0 ; i < n ; i ++ ) { //sök efter ett pivot dubbelt pivotValue = 0 ; int pivot = -1 ; för ( int rad = i ; rad < n ; rad ++ ) { if ( fabs ( C [ rad ][ i ]) > pivotValue ) { pivotValue = fabs ( C [ rad ][ i ]); pivot = rad ; } } if ( pivotValue != 0 ) { //byt den i:te raden och raden med referenselementet P . SwapRows ( pivot , i ); C. _ SwapRows ( pivot , i ); för ( int j = i + 1 ; j < n ; j ++ ) { C [ j ][ i ] /= C [ i ][ i ]; för ( int k = i + 1 ; k < n ; k ++ ) C [ j ][ k ] -= C [ j ][ i ] * C [ i ][ k ]; } } } } //nu matris C = L + U - E

Litteratur

  • Kormen, T. , Leizerson, C. , Rivest, R. , Stein, K. Algoritmer: konstruktion och analys = Introduktion till algoritmer / Ed. I. V. Krasikova. - 2:a uppl. - M. : Williams, 2005. - 1296 sid. — ISBN 5-8459-0857-4 .