Descompunerea LUP

LUP-descomposition ( LUP -descomposition) - reprezentarea unei matrice date ca produs o matrice de permutare obținută din matricea de identitate prin permutarea rândurilor sau coloanelor. O astfel de descompunere poate fi efectuată pentru orice matrice nedegenerată . Descompunerea LUP este utilizată pentru a calcula matricea inversă într-o schemă compactă, pentru a calcula soluția unui sistem de ecuații liniare. În comparație cu algoritmul de descompunere LU , algoritmul de descompunere LUP poate gestiona orice matrice nedegenerată și, în același timp, are o stabilitate de calcul mai mare . $A$ $PA=LU$ $L$ $U$ $P$

Algoritmul de descompunere LUP

Să , , . În practică, de regulă, în locul matricei de permutare P se folosește un vector de permutare, obținut din vector prin permutarea elementelor corespunzătoare numerelor de rând permutate în matricea P. De exemplu, dacă $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}}$

atunci , deoarece matricea P se obține prin interschimbarea primului și al doilea rând. Calculul expansiunii LUP se realizează în mai mulți pași. Fie matricea C = A. La fiecare pas i-a, mai întâi, se caută un element de referință (conducător) — elementul cu modulul maxim dintre elementele coloanei i-a care nu sunt mai mari decât rândul i-a , după care rândul cu elementul pivot este schimbat cu linia i-a. În același timp, se efectuează același schimb în matricea P. În acest caz, dacă matricea este nesingulară, atunci elementul de referință este garantat a fi diferit de zero. După aceea, toate elementele coloanei i-a actuale de sub rândul i-a sunt împărțite la pivot. În plus, din toate elementele situate sub i-lea rând și i-a coloană (adică, astfel încât j>i și k>i), produsul este scăzut . După aceea, contorul i este incrementat cu unu și procesul se repetă până când i<n unde n este dimensiunea matricei originale. După ce toți pașii sunt finalizați, matricea C va fi următoarea sumă: $p=(2,1,3)$ $c_{jk)$ $c_{ji}c_{ik)$

$C=L+UE$

unde E este matricea de identitate .

Algoritmul folosește trei bucle liniare imbricate, astfel încât complexitatea generală a algoritmului poate fi estimată ca O( n ³).

Implementarea algoritmului în C++

Mai jos este codul de program al algoritmului de mai sus în C++. Aici Matrix este un container care acceptă operația de indexare. Vă rugăm să rețineți că numărătoarea inversă este de la zero, nu de la unu.

void LUP ( const Matrix & A , Matrix & C , Matrix & P ) { //n - dimensiunea matricei originale const int n = A . Rânduri (); C = A ; //încărcați în matricea P matricea de identitate P = IdentityMatrix (); pentru ( int i = 0 ; i < n ; i ++ ) { //căutați un pivot dublu pivotValue = 0 ; int pivot = -1 ; pentru ( int rând = i ; rând < n ; rând ++ ) { if ( fabs ( C [ rând ][ i ]) > pivotValue ) { pivotValue = fabs ( C [ rând ][ i ]); pivot = rând ; } } if ( pivotValue != 0 ) { //schimba linia i-a și linia cu elementul de referință P . SwapRows ( pivot , i ); C. _ SwapRows ( pivot , i ); pentru ( int j = i + 1 ; j < n ; j ++ ) { C [ j ][ i ] /= C [ i ][ i ]; pentru ( int k = i + 1 ; k < n ; k ++ ) C [ j ][ k ] -= C [ j ][ i ] * C [ i ][ k ]; } } } } //acum matricea C = L + U - E

Literatură

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

Vectori și matrici

Vectori

Noțiuni de bază	Vector în geometrie Bază Baza ortogonala Coordonatele vectoriale Coliniaritate Ortogonalitatea Dependență liniară Spațiu coloane
Tipuri de vectori	Vector unitar Vector axial vector izotrop Normal Coliniaritate Vector zero Vector rază Vector propriu
Operații pe vectori	Produs scalar produs vectorial produs mixt Produs pseudoscalar Produs dublu cruce
Tipuri de spațiu	spațiu vectorial spatiu afin Spațiul euclidian Spațiul pseudo-euclidian Spațiu normat Spațiul Minkowski

matrici

Noțiuni de bază	Înmulțirea matricei Matrice transpusă Matricea conjugată hermitiană Matricea simetrică matrice inversă Valoare proprie Polinom caracteristic al unei matrice
Matrici speciale	Matrice de identitate Matrice zero Matricea diagonală matricea lambda
Descompuneri de matrice	descompunerea LU Descompunerea Cholesky Descompunerea QR Descompunerea LUP descompunerea unei valori singulare Descompunerea spectrală a unei matrice

Alte