Descomposició de matrius

En la disciplina matemàtica de l'àlgebra lineal, una descomposició de matrius o factorització de matrius és una factorització d'una matriu en producte de matrius. Hi ha molts tipus de descomposició de matrius; cada tipus té utilitat en una classe de problemes.

Exemple modifica

En anàlisi numèrica, s'usen diferents descomposicions per implementar de forma eficient diferents algorismes matricials.

Per exemple, quan es vol resoldre un sistema d'equacions lineals $Ax=b$ , la matriu A es pot descompondre mitjançant la descomposició LU. La descomposició LU factoritza una matriu en una matriu triangular inferior L (de l'anglès lower, inferior) i una matriu triangular superior U (de l'anglès upper, superior). Els sistemes $L(Ux)=b$ i $Ux=L^{-1}b$ requereixen moltes menys sumes i multiplicacions per ser resolts, en comparació amb el sistema original $Ax=b$ , encara que poden ser necessaris més dígits significatius en l'aritmètica inexacta com la coma flotant.

De manera similar, la descomposició QR expressa A com QR, on Q és una matriu unitària i R és una matriu triangular superior (la notació R ve de l'anglès right, dreta, perquè una matriu triangular superior té tots els seus elements a sobre i a la dreta de la diagonal principal --inclosa--). El sistema Q(Rx) = b es resol calculant Rx = Q^Tb = c, i el sistema Rx = c es resol per substitució enrere. El nombre de sumes i multiplicacions necessàries és prop del doble que per la descomposició LU, però no són necessaris més dígits significatius en els càlculs perquè la descomposició QR és numèricament estable.

Tipus de descomposició vinculats a la resolució de sistemes d'equacions lineals modifica

Descomposició LU modifica

Vàlida per: matriu quadrada A
Descomposició: $A=LU$ , on L és triangular inferior i U és triangular superior
Relacionada amb: la descomposició LDU és de la forma $A=LDU$ , on L és triangular inferior amb uns a la diagonal, U és triangular superior amb uns a la diagonal, i D és una matriu diagonal.
Relacionada amb: la descomposició LUP és de la forma $A=LUP$ , on L és triangular inferior, U és triangular superior, i P és una matriu permutació.
Existència: Sempre existeix una descomposició LUP per qualsevol matriu quadrada A. Quan P és una matriu identitat, la descomposició LUP es redueix a la descomposició LU. Si existeix una descomposició LU, llavors també existeix una descomposició LDU.^[1]
Comentaris: les descomposicions LUP i LU són útils per resoldre un sistema n × n d'equacions lineals $Ax=b$ . Aquestes descomposicions resumeixen el mètode de reducció de Gauss en forma matricial. La matriu P representa qualsevol intercanvi de files que s'hagi pogut fer en el transcurs de la reducció gaussiana. Si la reducció gaussiana ja produeix una matriu esglaonada sense que s'hagin fet intercanvis de files, llavors P=I, i aleshores existeix una descomposició LU.

Vàlida per: matriu A quadrada, simètrica i definida positiva
Descomposició: $A=U^{T}U$ , on U és triangular superior amb les entrades de la diagonal positives
Comentari: la factorització de Cholesky és un cas especial de la descomposició LU simètrica, amb $L=U^{T}$ .
Comentari: la factorització de Cholesky és única
Comentari: la factorització de Cholesky també es pot aplicar a matrius complexes hermítiques definides positives
Comentari: una alternativa és el mètode de Cholesky generalitzat, que pot estalviar el càlcul d'arrels quadrades.

Descomposició QR modifica

Vàlida per: matriu A de dimensió m × n
Descomposició: $A=QR$ on Q és una matriu ortogonal de dimensió m × m, i R és una matriu triangular superior de dimensió m × n
Comentari: La descomposició QR proporciona una forma alternativa de resoldre un sistema d'equacions lineals $Ax=b$ sense haver d'invertir la matriu A. El fet que Q sigui ortogonal significa que $Q^{T}Q=I$ , per tant $Ax=b$ és equivalent a $Rx=Q^{T}b$ , que és més senzill de resoldre, ja que R és triangular.

Factorització RRQR modifica

Descomposició en valors singulars modifica

Vàlida per: matriu A de dimensió m × n.
Descomposició: $A=UDV^{H}$ , on D és una matriu diagonal no-negativa, U i V són matrius unitàries, i $V^{H}$ denota la transposada conjugada de V (o simplement la matriu transposada, si V conté només nombres reals).
Comentari: Els elements de la diagonal de D s'anomenen valors singulars d'A.
Comentari: de forma semblant a la descomposició en valors propis que veurem més avall, la descomposició en valors singulars implica trobat direccions base al llarg de les quals la multiplicació matricial és equivalent a la multiplicació escalar, però és un resultat més general, ja que la matriu inicial A no té per què ser quadrada.

Descomposicions basades en valors propis i conceptes relacionats modifica

Descomposició en valors propis modifica

També anomenada descomposició espectral
Vàlida per: matriu quadrada A amb valors propis diferents.
Descomposició: $A=VDV^{-1}$ , on D és una matriu diagonal formada pels valors propis d'A, i les columnes de V són els corresponents vectors propis d'A.
Existència: Una matriu A de dimensió n × n sempre té n valors propis, que es poden ordenar (de més d'una forma) per configurar una matriu diagonal n × n D i la seva corresponent matriu de vectors no-nuls en columnes V que satisfan l'equació de valors propis $AV=VD$ . Si els n valors propis són diferents (és a dir, cap d'ells és igual als altres), llavors V és invertible, la qual cosa implica la descomposició $A=VDV^{-1}$ .^[2]
Comentari: La condició de tenir n valors propis diferents és suficient però no necessària. La condició necessària i suficient és que tot valor propi ha de tenir multiplicitat geomètrica igual a la seva multiplicitat algebraica.
Comentari: La descomposició en valors propis és útil per entendra la solució a un sistema lineal d'equacions diferencials ordinàries o per equacions lineals en diferències. Per exemple, l'equació en diferències $x_{t+1}=Ax_{t}$ amb condicions inicials $x_{0}=c$ es pot resoldre per $x_{t}=A^{t}c$ , que és equivalent a $x_{t}=VD^{t}V^{-1}c$ , on V i D són les matrius formades a partir dels vectors propis i valors propis d'A. Com que D és diagonal, per elevar-la a la potència $D^{t}$ només cal elevar cada element de la diagonal a la potència t. Això és molt més senzil de calcular que elevar A a la potència t, perquè normalment A no és diagonal.

Descomposició de Jordan modifica

Forma canònica de Jordan i Descomposició de Jordan–Chevalley

Vàlida per: matriu quadrada A
Comentari: la forma canònica de Jordan generalitza la descomposició en valors propis als casos en què hi ha valors propis repetits i la matriu A no es pot diagonalitzar. La descomposició de Jordan–Chevalley permet fer això sense haver d'escollir una base.

Descomposició de Schur modifica

Vàlida per: matriu quadrada A
Comentari: hi ha dues versions d'aquesta descomposició: la descomposició de Schur complexa i la descomposició de Schur real. Una matriu complexa sempre té una descomposició de Schur complexa. Una matriu real admet una descomposició de Schur real si i només si tots els seus valors propis són reals.
Descomposició (versió complexa): $A=UTU^{H}$ , on U és una matriu unitària, $U^{H}$ és la transposada conjugada d'U, i T és una matriu triangular superior anomenada forma de Schur complexa, que té a la diagonal els valors propis d'A.
Descomposició (versió real): $A=VSV^{T}$ , on A, V, S i $V^{T}$ són matrius a entrades reals. En aquest cas, V és una matriu ortogonal, $V^{T}$ és la transposada de V, i S és una matriu triangular superior per blocs anomenada la forma de Schur real. Els blocs de la diagonal de S són de dimensió 1×1 (en el cas que representin valors propis reals) o 2×2 (en el cas que estiguin derivats de parells de valors propis conjugats).

Descomposició QZ modifica

També anomenada: descomposició de Schur generalitzada
Vàlida per: matrius quadrades A i B
Comentari: hi ha dues versions d'aquesta descomposició: complexa i real.
Descomposició (versió complexa): $A=QSZ^{H}$ i $B=QTZ^{H}$ , on Q i Z són matrius unitàries, el superíndex H representa la transposada conjugada, i S i T són matrius triangulars superiors.
Comentari: en la descomposició QZ complexa, els quocients dels elements de la diagonal de S entre els corresponents elements de la diagonal de T, $\lambda _{i}=S_{ii}/T_{ii}$ , són els valors propis generalitzats que resolen el problema del valor propi generalitzat $Av=\lambda Bv$ (on $\lambda$ és un escalar desconegut i v és un vector no-nul desconegut).
Descomposició (versió real): $A=QSZ^{T}$ i $B=QTZ^{T}$ , on A, B, Q, Z, S, i T són matrius a entrades reals. En aquest cas, Q i Z són matrius ortogonals, el superíndex T representa la transposició, i S i T són matrius triangulars superiors per blocs. Els blocs de la diagonal de S i T són de dimensió 1×1 o 2×2.

Factorització de Takagi modifica

Vàlida per: matriu A quadrada, complexa i simètrica.
Descomposició: $A=VDV^{T}$ , on D és una matriu diagonal real no-negativa, i V és una matriu unitària. $V^{T}$ denota la matriu transposada de V.
Comentari: els elements de la diagonal de D són les arrels quadrades no-negatives dels valors propis de $AA^{H}$ .
Comentari: V pot ser complexa encara que A sigui real.

Altres descomposicions modifica

Referències modifica

↑ C. Simon i L.Blume. «7». A: Norton. Mathematics for Economists, 1994. ISBN 0-393-95733-0.
↑ Meyer, Carl D. Matrix Analysis and Applied Linear Algebra. Society for Industrial and Applied Mathematics, 2000, p. 514. ISBN 978-0-89871-454-8.

Enllaços externs modifica

[1] C. Simon i L.Blume. «7». A: Norton. Mathematics for Economists, 1994. ISBN 0-393-95733-0.

[2] Meyer, Carl D. Matrix Analysis and Applied Linear Algebra. Society for Industrial and Applied Mathematics, 2000, p. 514. ISBN 978-0-89871-454-8.

[1]

[2]