Descomposició de matrius

De Viquipèdia
Dreceres ràpides: navegació, cerca

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 | modifica el codi]

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 forma 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 = QTb = 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 | modifica el codi]

Descomposició LU[modifica | modifica el codi]

Reducció LU[modifica | modifica el codi]

Descomposició LU per blocs[modifica | modifica el codi]

Factorització de rang[modifica | modifica el codi]

Factorització de Cholesky[modifica | modifica el codi]

  • Vàlida per: matriu A quadrada, simètrica i definida positiva
  • Descomposició: A=U^TU, 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 | modifica el codi]

  • 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^TQ=I, per tant Ax=b és equivalent a Rx=Q^Tb, que és més senzill de resoldre, ja que R és triangular.

Factorització RRQR[modifica | modifica el codi]

Descomposició en valors singulars[modifica | modifica el codi]

  • 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 | modifica el codi]

Descomposició en valors propis[modifica | modifica el codi]

  • 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^tc, que és equivalent a x_t = VD^tV^{-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 | modifica el codi]

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 | modifica el codi]

Descomposició QZ[modifica | modifica el codi]

Factorització de Takagi[modifica | modifica el codi]

  • 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 | modifica el codi]

Referències[modifica | modifica el codi]

  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. 

Enllaços externs[modifica | modifica el codi]