LUP-hajoaminen

LUP-decomposition ( LUP -decomposition) - tietyn matriisin esitys tuotteena permutaatiomatriisi, joka saadaan identiteettimatriisista permutoimalla rivejä tai sarakkeita. Tällainen hajottaminen voidaan suorittaa mille tahansa ei- degeneroituneelle matriisille. LUP-hajottelua käytetään käänteismatriisin laskemiseen kompaktissa kaaviossa, lineaarisen yhtälöjärjestelmän ratkaisun laskemiseen. LU -hajotusalgoritmiin verrattuna LUP-hajotusalgoritmi pystyy käsittelemään mitä tahansa ei-singulaarisia matriiseja ja samalla sillä on korkeampi laskennallinen vakaus $A$ $PA = LU$ $L$ $U$ $P$ .

LUP-hajotusalgoritmi

Anna , , . Käytännössä permutaatiomatriisin P sijasta käytetään pääsääntöisesti permutaatiovektoria, joka saadaan vektorista permutoimalla matriisissa P permutoituja rivinumeroita vastaavat elementit. Jos esim. $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}}$

sitten , koska matriisi P saadaan vaihtamalla ensimmäinen ja toinen rivi. LUP-laajennuksen laskenta suoritetaan useissa vaiheissa. Olkoon matriisi C = A. Jokaisessa i:nnessä vaiheessa etsitään ensin viiteelementti (johtava) - elementti, jonka moduuli on suurin niistä i:nnen sarakkeen elementeistä, jotka eivät ole korkeampia kuin i. rivi , jonka jälkeen pivot-elementin rivi vaihdetaan i:nnen rivin kanssa. Samanaikaisesti sama vaihto suoritetaan matriisissa P. Tässä tapauksessa, jos matriisi on ei-singulaarinen, referenssielementti on taatusti erilainen kuin nolla. Sen jälkeen kaikki nykyisen i:nnen sarakkeen elementit i:nnen rivin alapuolella jaetaan pivotilla. Lisäksi kaikista elementeistä, jotka sijaitsevat i:nnen rivin ja i:nnen sarakkeen alapuolella (eli siten, että j>i ja k>i), tulo vähennetään . Tämän jälkeen laskuria i kasvatetaan yhdellä ja prosessia toistetaan kunnes i<n missä n on alkuperäisen matriisin dimensio. Kun kaikki vaiheet on suoritettu, matriisi C on seuraava summa: $p=(2,1,3)$ ${\displaystyle c_{jk))$ ${\displaystyle c_{ji}c_{ik))$

$C=L+UE$

missä E on identiteettimatriisi .

Algoritmi käyttää kolmea sisäkkäistä lineaarisilmukkaa, joten algoritmin kokonaismonimutkaisuus voidaan arvioida muodossa O( n ³).

Algoritmin toteutus C++:ssa

Alla on yllä olevan algoritmin ohjelmakoodi C++:ssa. Tässä Matrix on kontti, joka tukee indeksointitoimintoa. Huomaa, että lähtölaskenta on nollasta, ei yhdestä.

void LUP ( const Matrix & A , Matrix & C , Matrix & P ) { //n - alkuperäisen matriisin ulottuvuus const int n = A . Rivit (); C = A ; //lataa matriisiin P identiteettimatriisi P = IdentityMatrix (); for ( int i = 0 ; i < n ; i ++ ) { //hae pivot double pivotValue = 0 ; int pivot = -1 ; for ( int rivi = i ; rivi < n ; rivi ++ ) { if ( fabs ( C [ rivi ][ i ]) > pivotValue ) { pivotValue = fabs ( C [ rivi ][ i ]); pivot = rivi ; } } if ( pivotValue != 0 ) { //vaihtaa i:nnen rivin ja rivin viiteelementillä 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 ]; } } } } //nyt matriisi C = L + U - E

Kirjallisuus

Kormen, T. , Leizerson, C. , Rivest, R. , Stein, K. Algoritmit: rakentaminen ja analyysi = Introduction to Algorithms / Ed. I. V. Krasikova. - 2. painos - M .: Williams, 2005. - 1296 s. — ISBN 5-8459-0857-4 .

Vektorit ja matriisit

Vektorit

Peruskonseptit	Vektori geometriassa Perusta Ortogonaalinen perusta Vektorikoordinaatit Kollineaarisuus Ortogonaalisuus Lineaarinen riippuvuus Saraketila
Vektorityypit	Yksikkövektori Aksiaalinen vektori isotrooppinen vektori Normaali Kollineaarisuus Nolla vektori Sädevektori Omavektori
Operaatiot vektoreille	Skalaarituote vektorituote sekoitettu tuote Pseudoskalaarinen tuote Kaksinkertainen ristituote
Tilatyypit	vektoriavaruus affinista tilaa Euklidinen avaruus Pseudoeuklidinen avaruus Normaali tila Minkowskin tila

matriiseja

Peruskonseptit	Matriisin kertolasku Transponoitu matriisi Hermitian konjugaattimatriisi Symmetrinen matriisi käänteinen matriisi Ominaisarvo Matriisin karakteristinen polynomi
Erikoismatriisit	Identiteettimatriisi Nolla matriisi Diagonaalinen matriisi lambda matriisi
Matriisihajotukset	LU:n hajoaminen Cholesky-hajoaminen QR-hajotus LUP-hajoaminen singulaariarvon hajottelu Matriisin spektrihajotus

Muut