|
En [[Análise numérica|análise numérica]], algunhas descomposicións empréganse para desenvolver [[Algoritmo|algoritmos]] de matrices eficiente.
Por exemplo, ao solucionar un [[Sistema de ecuacións lineais|sistema de ecuacións lineais]] ''<math>Ax=b''</math>, a matriz ''<math>A''</math> pode ser descomposta por mediomediante da descomposición LU.<math>Ax=b</math> A descomposición LU factoriza unha matriz en unhanunha matriz triangular inferior ''<math>L''</math> e unha matriz triangular superior <math>U</math><ref>A notación de matrices <math>L</math> e <math>U</math> para falar de matrices triangulares inferiores e superiores provén dos termos ingleses ''U'''l'''ower'' e '''''u'''pper'', "inferior" e "superior" respectivamente, e que fan referencia á localización dos elementos da matriz que no son cero: por debaixo da diagonal principal no caso das inferiores, por riba no caso das superiores.</ref>. OsDeste xeito, de quixermos resolver os sistemas ''<math>L(Ux)=b''</math> e ''<math>Ux = L<sup>^{-1}b</supmath>b'', precisaremos precisanfacer menos sumas e multiplicacións paraque resolverse,ao comparadoresolver coo sistema orixinal ''<math>Ax=b''</math>, malia que pode precisar significativamente máis díxitoscifras significativas nunha aritmética inexacta, como a dode puntocoma flotante.
De xeito semellante, a descomposición QR expresa ''<math>A''</math> como ''o produto <math>QR''</math>, cononde ''<math>Q''</math> é unha matriz ortogonal e ''<math>R''</math> unha matriz triangular superior<ref>A notación de <math>R</math> provén do termos ingleses '''''r'''ight'', "dereita", e que fai referencia á localización dos elementos da matriz que no son cero: a dereita da diagonal principal.</ref>. O sistema ''<math>Q(Rx) ='' ''b''</math> é solucionado por ''<math>Rx = QTb ='' ''c''</math>, e o sistema ''<math>Rx = c''</math> é solucionado por ''substitución traseiracara atrás''. O número de adiciónssumas e multiplicacións que son requiridas é sobreao dúasredor vecesdo dobre que as de utilizar oa algoritmodescomposición LU, mais non precisa máis díxitoscifras sonsignificativas requiridosao en aritmética inexacta porqueser a descomposición QR é numericamente estable.
== Descomposicións relacionadas con solucionar sistemas de ecuacións lineais ==
=== Descomposición LU ===
* Aplicábel a: [[matriz cadrada]] ''<math>A''</math>.
* Descomposición: ''<math>A=LU''LDU</math>, onde ''<math>L''</math> é triangular inferior e ''<math>U''</math> é triangular superior.
* Relacionado: a descomposición LDU é ''<math>A=LDU''</math>, onde L é triangular inferior con uns na diagonal, U é triangular superior con uns na diagonal, e D é unha matriz diagonal.<math>A=LDU</math>
* Relacionado: a descomposición LUP é ''<math>A=LUP''</math>, onde L é triangular inferior e ''<math>U''</math> é triangular superior, e P é un matriz de permutación .<math>A=LUP</math>
* Existencia: unha descomposición ''<math>LUP''</math> existe para calquera matriz cadrada ''<math>A''</math>. Cando ''<math>P''</math> é unha matriz de identidade, a descomposición LUP redúcese a unha descomposición LU. Se existe a descomposición ''<math>LU''</math>, entón tamén existe a descomposición LDU.<ref>{{Cita Harvard sen parénteses|Simon|Blume|1994}} Chapter 7.</ref>
* Comentarios: as descomposicións LUP e LU son útiles para solucionar un sistema de ecuacións lineais ''<math>Ax=b''</math> n por n (con n ecuacións e n incógnitas).<math>Ax=b</math> Estas descomposicións son un resumo algoritmo de [[Eliminación de Gauss|eliminación de Gauss]] en forma matricial. A matriz ''<math>P''</math> representa calquera intercambio de fila levado a cabo no algoritmo. Se o algoritmo produce a forma de escada por filas sen precisar ningún intercambio de fila, entón ''<math>P'' = ''I''</math>, e logo existe a descomposición LU.
=== Rango factorización ===
* Aplicábel a: matriz ''<math>A''</math> ''m''x''n'' de rango ''r''
* Descomposi<math>A=CF</math>ón: ''<math>A=CF''</math>, onde ''<math>C''</math> é unha matriz ''m''x''n'' de rango de columna máximo e ''<math>F''</math> é unha matriz ''r''x''n'' de rango de fila máximo.
* Comentario: o rango factorización adótaise usar para computar a matriz pseudoinversa de Moore–Penrose de ''<math>A''</math>,<ref>{{Cita publicación periódica|volume=72|doi=10.2307/2690882|JSTOR=2690882}}</ref> que permite obter todas as solucións do sistema lineal ''<math>Ax=b''</math>.
=== Descomposición de Cholesky ===
* Aplicábel a: matrices cadradas, hermíticas, definidas positivas.
* Descomposición: ''<math>A=U<sup>*U</supmath>U'' onde ''<math>U''</math> é triangular superior coas entradas reais positivas na diagonal.
* Comentario: se a matriz ''<math>A''</math> é hermítica e semidefinida positiva, entón ten unha descomposición da forma ''<math>A=U<sup>*</sup>U''</math> se a diagonal de ''<math>U''</math> pode ter entradas nulas.
* Unicidade: para matrices definitivas positivas, a descomposición de Cholesky é única. Con todo, no caso de semidefinida positiva non é única.
* Comentario: se ''<math>A''</math> é unha matriz real e simétrica, ''<math>U''</math> té todos elementos reais.
* Comentario: Unha alternativa é a descomposición LDL, que pode evitar a obtención de raíces cadradas.
* Aplicábel a: matrices ''m''x''n''
* Descomposición: ''<math>A=QR''</math> onde ''<math>Q''</math> é unha matriz unitaria de orde ''m''x''m'', e ''<math>R''</math> é unha matriz triangular superior ''m''x''n''.
* Unicidade: En xeral non é única, mais se ''<math>A''</math> té rango máximo, entón existe unha única ''<math>R''</math> con todos os elementos da diagonal positivos. Se ''<math>A''</math> é cadrada, ''<math>Q''</math> tamén é única.
* Comentario: A descomposición de Q<math>Rx=Q^Tb</math> proporciona un xei<math>Q^TQ=I</math>o alternativo de solucionar o sistema de ecuacións ''<math>Ax=b''</math> sen inverter a matriz ''<math>A''</math>. O feito <math>Q^TQ=I</math>de que ''<math>Q''</math><math>Q^TQ=I</math> é ortogonal significa que ''<math>Q<sup>T</sup>Q = I''</math>, polo que ''<math>Ax=b''</math> é equivalente a ''<math>Rx = Q<sup>T</sup>b''</math>, que é o moito máis doado de resolver ao ser ''<math>R''</math> triangular.
== As descomposicións baseadas en autovalores e conceptos relacionados ==
* Tamén chamad''a descomposición'' espectral.
* Aplicábel a: matriz cadrada ''<math>A''</math> con autovalores linealmente independentes (non necesariamente distintos).
* Descomposición: ''<math>A=VDV-1''</math>, onde ''<math>D''</math> é unha matriz diagonal formada polos autovalores de ''<math>A</math>,'' e as columnas de V é son os correspondentes autovectores de ''<math>A''</math>.
* Existencia: Unha matriz ''<math>A''</math> de orde ''n''x''n'' sempre ten n autovalores (complexos), os calen poden ser ordeados (en máis dun xeito) para formar unha matriz ''<math>D''</math> diagonal ''n''x''n'' e a correspondente matriz de columnas non nulas que satisfai a ecuación dos autovalores ''<math>AV=VD''</math>. ''<math>V''</math> é invertible se e soamente se os autovalores son linealmente independientes (p.ex., cada autovalor ten a [[Valor propio, vector propio e espazo propio|multiplicidade xeométrica]] igual á súa multiplicidade alxebraica).<math>V</math> Unha suficiente (mais non necesaria) condición para suceder isto é que todos os autovalores sexan diferentes (neste caso as multiplicidades xeométricas e alxebraicas son iguais a 1)
* Comentario: ''<math>A''</math> sempre pode normalizar o autovectores para ter lonxitude 1 (ver a definición da ecuación do autovalor)
* Comentario: Cada matriz normal ''<math>A''</math> (p.ex., matriz para a cal ''<math>AA*=A*A''</math>, onde ''<math>A''</math> e unha matriz conxugada) pode ser descomposta en autovalores.<math>AA^*=A^*A</math><math>A^*</math> Para a matriz normal A (e só para unha matriz normal), os autovectores tamén pod<math>A=VDV^*</math>en ser feito ortonormais (''VV*=I'') e a descomposición en autovalores léese como ''<math>A=VDV*''</math>. En particular toda matriz unitaria, hermítica ou antihermítica (no caso real, toda ortogonal, simétrica ou antisimétrica, respectivamente) son normais e por tanto posúen esta propiedade.
* Comen<math>A=VDV^T</math>ario: Para calquera matriz real simétrica ''<math>A''</math>, descomposición en autovalores se pode escrita como ''<math>A=VDVT''</math>, onde ámbolos dous ''<math>D''</math> e ''<math>V''</math> son matrices reais.
* Comentario: O descomposición en autovaloesautovalores é útil para entender a solución dun sistema de ecuacións diferenciais normais lineais ou ecuacións de diferenza lineal. Por exemplo, a ecua<math>x_t = A^tc</math>ión diferencial x_{t+1}=Ax_t empezando no punto inicial x_0=c é resolvido por x_t=A^tc, o cal é equivalente a x_{t}=VD^{t}V^{-1}c}, onde V e D é as matrices formadas desde os autovalores e autovectores de ''<math>A</math>.'' Xa que D é diagonal, levantándoo a potencia D^t, só implica elevar cada elemento da diagonal ao poder t.<math>x_{t+1}=Ax_t</math><math>x_0=c</math><math>x_t = A^tc</math><math>x_t = VD^tV^{-1}c</math><math>D^t</math>Is''t''oIsto é moito máis fácil de facer e entender que elvevar ''<math>A''</math> a unha potencia t, xa que ''<math>A''</math> é normalmente non diagonal.
=== Descomposición de Jordan ===
A [[Forma canónica de Jordan|forma normal de Jordan]] e a descomposición Jordan–Chevalley
* Aplicábel a: matriz cadrada ''<math>A''</math>
* Comentario: a forma normal de Jordan xeneraliza o descomposición en autovalores nos caso onde hai autovalores repetido e non diagonaliza, descomposición Jordan–Chevalley faino sen sen escoller unha base.
=== Descomposición de Schur ===
* Aplicábel a: matriz cadrada ''<math>A''</math>
* Descomposición (versión complexa): ''<math>A=UTU*''</math></math>, onde ''<math>U''</math> é unha matriz unitaria, ''<math>U*''</math> a súa conxugada transposta e ''<math>T''</math> é unha matriz triangular superior chamada ''forma complexa de Schur'' que ten os autovalores de ''<math>A''</math> ao longo da diagonal.<math>A=UTU^*</math><math>U^*</math>
* Comentario: se ''<math>A''</math> é unha matriz normal, entón ''<math>T''</math> é diagonal e a descomposición de Schur coincide coa descomposición en autovalores.
=== Descomposición real de Schur ===
* Aplicábel a: matriz cadrada ''<math>A''</math>
* Descompo<math>S</math>ición: Isto é unha versión da descomposición de Schur onde ''<math>S''</math> só conté números reais.<math>V</math>''<math>A''</math><math>S</math> sempre se pode e<math>A=VSV^T</math>cribir ''<math>A=VSVT''</math> onde V é unha matriz real ortogonal, VT é a trasposta de V, e S é unha matriz triangular superior por bloques chamada forma Schur real.<math>A=VSV^T</math><math>V^T</math> O''s'' bloques na diagonal de S son de tamaño 1×1 (en que caso representan autovalores reais) ou 2×2 (en que caso que sexan son derivados desde pares de autovalores complexos conxugados).
=== Descomposición QZ ===
* Tamén chamou: ''descomposición de Schur xeneralizada''
* Aplicá''b''elAplicábel a: matrices cadradas <math>A</math> e <math>B''
* Comentario: hai dúas versións desta descomposición: complexa e real.
* Descompo<math>A=QSZ^*</math>ición (versión complexa): A=QSZ* e B=QTZ* onde Q e Z son matrices unitarias, o * superscripto representa conxugada transposta, e S e T é matriz triangular superior.<math>A=QSZ^*</math><math>B=QTZ^*</math>
* Comentario: na descompo''s''<math>\lambda_i = S_{ii}/T_{ii}</math>c<math>\lambda_i = S_{ii}/T_{ii}</math>ón de QZ complexa, as proporc<math>\lambda_i = S_{ii}/T_{ii}</math>óns dos elemen''t''os d<math>\lambda_i = S_{ii}/T_{ii}</math>agonais de S aos elementos diagonais correspondentes de T, \lam<math>Av=\lambda Bv</math>da _{i}=S_{ii}/T_{ii}, é son os autovalores xeneralizados que soluciona n o problema dos autovalores xeneralizacos Av=\lambda Bv (onde lamba é un escalar que chamaremos autovector xeneralizado e v será o autovector xeneralizado)
* Descomposición (versión real): A=QTZ^T e B=QTZ^T, onde A, B, Q, Z, S, e T son matrices que conteñen números reais só.Ne''s''te caso ''<math>Q''</math> e ''Z''<math>Q</math> é matrices ortogonais, o T superscripto representa transposición, e S e T é son matrices triangulares uperiroes de bloques. Os bloques na diagonal de S e T son de tamaño 1×1 ou 2×2.
=== Factorización de Takagi ===
* Aplicábel a: matriz cadrado, complexa, simétrica ''<math>A''</math>.
* Descomposición: A=VDVT, onde D é unha matriz real non negativa diagonal, e V é unitaria.<math>A=VDV^T</math> VT denota a matriz trasposta de V.<math>V^T</math>
* Comentario: Os elementos diagonais de D son as raíces non negativas dos autovalores de ''<math>AA*''</math>.<math>AA^*</math>
* Comentario: ''<math>V''</math> pode ser complexo incluso se A é real.
* Comen<math>V^T</math>ario: Isto non é un caso especial da descomposición en autovalores (ver arriba), o cal utiliza V^{-1} en vez de V^T
=== Descomposición de valores singulares ===
* Aplicábel a: m-por-n matriz ''Un''<math>A</math>.
* Descomposición: A=UDV*, onde D é un e matriz diagonal nonnegati<math>U^*U = I, V^*V = I</math>iva, e U e <math>A=UDV^*</math>V satisfan <math>U*</math>U =I, V*V?I. É o conxugar traspor de ''<math>V''</math> (ou sinxelamente o traspor, se <math>V^*</math> contén números reais só), e I denota a matriz de identidade (dalgunha dimensión).<math>V^*</math>
* Comentario: Os elementos ''d''iagonaisdiagonais de D é chamado os valores singulares de A.
* Comentario: Como o descomposición en autovalores, a descomposición de valor singular implica atopar bases de direccións ao longo das que a multiplicación de matriz é equivalentes a multiplicación escalar, mais ten máis xeneralidade grande desde a matriz baixo consideración non necesita ser cadrada.
* <math>A</math>Unicidade: os valores singulares de A son sempre uniquevicamente. U e V non ten que ser únicos en xeral.
=== Descomposición de Mostow ===
* Aplicábel a: matriz cadrada, complexa, non singular ''<math>A''</math>.<ref>{{Obra citada}}</ref><ref>{{Cita libro|ISBN=9783642302329|DOI=10.1007/978-3-642-30232-9}}</ref>
* Descompo<math>A=Ue^{iM}e^{S}</math>ción: A=Ue^{iM}e^{S}, onde U é unitaria, M é real antisimétrica e S é real simétrica.<math>A=Ue^{iM}e^{S}</math>
* Co<math>A=U_2e^{S_2}e^{iM_2}</math>mentar<math>A=U_2e^{S_2}e^{iM_2}</math>o: A matriz ''<math>A''</math> tamén pode se<math>A=U_2e^{S_2}e^{iM_2}</math>r descomposta como A=U_{2}e^{S_{2}e^{iM_2}, onde U2 é unitario, M2 é real antisimétrica e S2 é real simétrica.<math>A=U_2e^{S_2}e^{iM_2}</math><ref name=":0">{{Cita publicación periódica|url=http://www.sciencedirect.com/science/article/pii/S0024379513005612|volume=439|doi=10.1016/j.laa.2013.09.006}}</ref>
=== Forma normal de Sinkhorn ===
| 