# Decomposição matricial
## Exemplo

Na análise numérica, diferentes decomposições são usadas para implementar algoritmos matriciais eficientes.
Por exemplo, ao resolver um sistema de equações lineares $Ax=b$, a matriz A pode ser decomposta através da decomposição lu. A decomposição LU fatora uma matriz em uma matriz triangular inferior L e uma matriz triangular superior U. Os sistemas ${\displaystyle L(U\mathbf {x} )=\mathbf {b} }$ e ${\displaystyle U\mathbf {x} =L^{-1}\mathbf {b} }$ requerem menos adições e multiplicações para resolver, em comparação com o sistema original ${\displaystyle A\mathbf {x} =\mathbf {b} }$, embora possa-se exigir significativamente mais dígitos na aritmética inexata, como ponto flutuante.
Da mesma forma, a decomposição QR expressa A como QR com Q uma matriz ortogonal e R uma matriz triangular superior. O sistema $Q(Rx)=b$ é resolvido por $Rx=Q^{T}b=c$, e o sistema $Rx=c$ é resolvido por 'substituição traseira'. O número de adições e multiplicações necessárias é cerca de duas vezes maior do que o uso do solucionador de LU, mas não são necessários mais dígitos na aritmética inexata porque a decomposição do QR é numericamente estável.

## Decomposições relacionadas à solução de sistemas de equações lineares
### Decomposição LU

Artigo principal: decomposição LU
* Aplicável a: matriz quadrada A.
* Decomposição: $A=LU$, onde L é triangular inferior e U é triangular superior.
* Relacionado: a decomposição da LDU é $A=LDU$, onde L é triangular inferior com uns na diagonal, U é triangular superior com uns na diagonal e D é uma matriz diagonal.
* Relacionado: a decomposição do LUP é $A=LUP$, onde L é triangular inferior, U é triangular superior e P é uma matriz de permutação.
* Existe uma LUP decomposição para qualquer matriz quadrada: Quando P é uma matriz identidade, a decomposição LUP se reduz à decomposição LU.
* Se a decomposição LU existe, então existe a decomposição LDU.
* Comentários: O LUP e decomposições LU são úteis na solução de um sistema de equações lineares $Ax=b$. Essas decomposições resumem o processo de eliminação gaussiana em forma de matriz.
* A matriz P representa quaisquer trocas de linhas realizadas no processo de eliminação gaussiana. Se a eliminação gaussiana produz a forma escalonada de linha sem exigir nenhuma troca de linha, então $P=I$, então existe uma decomposição LU.

### Redução LU

A redução de LU é um algoritmo relacionado à decomposição de LU. Este termo é geralmente usado no contexto de supercomputação e computação altamente paralela. Neste contexto, é usado como um algoritmo de benchmarking, ou seja, para fornecer uma medida comparativa de velocidade para diferentes computadores.
A redução de LU é uma versão especial paralelizada de um algoritmo de decomposição de LU.. A versão paralelizada geralmente distribui o trabalho de uma linha de matriz para um único processador e sincroniza o resultado com toda a matriz.

### Decomposição do bloco LU

Em álgebra linear, uma decomposição do bloco LU é uma decomposição da matriz de uma matriz de bloco em bloco uma matriz triangular inferior L e um bloco superior triangular matriz L.
Esta decomposição é usada na análise numérica para reduzir a complexidade da fórmula da matriz de bloco.

### Fatoração de classificação

* Aplicável a: matriz A de classificação r
* Decomposição: $A=CF$, onde C é uma matriz de classificação de coluna completa F é uma matriz de classificação de linha completa r.

### Decomposição de Cholesky

Artigo principal: decomposição de Cholesky
* Aplicável a: quadrado, hermitiano, matriz definida positiva A.
* Decomposição: $A=U*U$, onde U é triangular superior com entradas diagonais positivas reais.
* Se a matriz A é uma matriz hermitiana e (semi)definida positiva, então tem uma decomposição da forma $A=U*U$, (as entradas diagonais U podem ser zero),
* Singularidade: para matrizes definidas positivas, a decomposição de Cholesky é única. No entanto, não é único no caso (semi)definido positivo.
* Comentário: se A é real e simétrico, U tem todos os elementos reais
* Comentário: Uma alternativa é a decomposição do LDL , que pode evitar a extração de raízes quadradas.

### Decomposição QR

Artigo principal: decomposição QR
* Aplicável a: matriz A com colunas linearmente independentes
* Decomposição: A = QR, onde Q é uma matriz unitária de tamanho n, e R é uma matriz triangular superior de tamanho m.
* Singularidade: em geral, não é único, mas se A é de classificação completa, então existe um único R, que tem todos os elementos diagonais positivos. Se A é quadrado também Q é único.
* Comentário: A decomposição QR fornece uma maneira eficaz de resolver o sistema de equações $Ax=b$. O fato de que Q é ortogonal significa que $(Q^{T})*Q=I$, para que $Ax=b$ é equivalente a $Rx=(Q^{T})*b$, o que é muito fácil de resolver, pois R é triangular.

### Fatoração RRQR

Uma fatoração RRQR ou fatoração QR reveladora de classificação é um algoritmo de decomposição de matriz com base na fatoração QR que pode ser usado para determinar a classificação de uma matriz. A decomposição de valor singular pode ser usada para gerar um RRQR, mas não é um método eficiente para fazê-lo. Uma implementação RRQR está disponível no MATLAB.

### Decomposição interpolativa

Na análise numérica, a decomposição interpolativa (ID) fatora uma matriz como o produto de duas matrizes, uma das quais contém colunas selecionadas da matriz original e a outra possui um subconjunto de colunas que consiste na matriz identidade e todos os seus valores são não maior que 2 em valor absoluto.
* Choudhury, Dipa; Horn, Roger A. (abril de 1987). «A Complex Orthogonal-Symmetric Analog of the Polar Decomposition». SIAM Journal on Algebraic and Discrete Methods. 8: 219–225. doi:10.1137/0608019
* Fredholm, I. (1903), «Sur une classe d'´equations fonctionnelles», Acta Mathematica (em francês), 27: 365–390, doi:10.1007/bf02421317
* Hilbert, D. (1904), «Grundzüge einer allgemeinen Theorie der linearen Integralgleichungen», Nachr. Königl. Ges. Gött (em alemão), 1904: 49–91
* Horn, Roger A.; Merino, Dennis I. (janeiro de 1995). «Contragredient equivalence: A canonical form and some applications». Linear Algebra and Its Applications. 214: 43–92. doi:10.1016/0024-3795(93)00056-6
* Meyer, C. D. (2000), Matrix Analysis and Applied Linear Algebra, ISBN 978-0-89871-454-8, SIAM
* Schmidt, E. (1907), «Zur Theorie der linearen und nichtlinearen Integralgleichungen. I Teil. Entwicklung willkürlichen Funktionen nach System vorgeschriebener», Mathematische Annalen (em alemão), 63 (4): 433–476, doi:10.1007/bf01449770
* Simon, C.; Blume, L. (1994). Mathematics for Economists. [S.l.]: Norton. ISBN 978-0-393-95733-4
* Stewart, G. W. (2011), Fredholm, Hilbert, Schmidt: three fundamental papers on integral equations (PDF), consultado em 6 de janeiro de 2015
* Townsend, A.; Trefethen, L. N. (2015), «Continuous analogues of matrix factorizations», Proc. R. Soc. A, 471 (2173), Bibcode:2014RSPSA.47140585T, PMC 4277194, PMID 25568618, doi:10.1098/rspa.2014.0585
* ↑ Banerjee, Sudipto (2014). Linear algebra and matrix analysis for statistics. Anindya Roy. Boca Raton: [s.n.] OCLC 875055780
* ↑ Lay, David C. (2003). Linear algebra and its applications 3rd ed ed. Boston: Addison Wesley. OCLC 50583747 !CS1 manut: Texto extra (link)
* ↑ Golub, Gene H. (1996). Matrix computations. Charles F. Van Loan 3rd ed ed. Baltimore: Johns Hopkins University Press. OCLC 34515797 !CS1 manut: Texto extra (link)
* ↑ Stewart, G. W. Matrix algorithms. ©1998-<2001>. Philadelphia: Society for Industrial and Applied Mathematics. OCLC 39052423
* ↑ Piziak, R.; Odell, P. L. (junho de 1999). «Full Rank Factorization of Matrices». Mathematics Magazine (em inglês) (3): 193–201. ISSN 0025-570X. doi:10.1080/0025570X.1999.11996730. Consultado em 8 de abril de 2021
* ↑ Gu, Ming; Eisenstat, Stanley C. (julho de 1996). «Efficient Algorithms for Computing a Strong Rank-Revealing QR Factorization». SIAM Journal on Scientific Computing (em inglês) (4): 848–869. ISSN 1064-8275. doi:10.1137/0917055. Consultado em 8 de abril de 2021
* ↑ Hong, Y. P.; Pan, C.-T. (janeiro de 1992). «Rank-Revealing QR Factorizations and the Singular Value Decomposition». Mathematics of Computation (197). 213 páginas. doi:10.2307/2153029. Consultado em 8 de abril de 2021
* ↑ "RRQR Factorization" (PDF). 29 March 2007. Retrieved 2 April 2011.
* ↑ Cheng, Hongwei, Zydrunas Gimbutas, Per-Gunnar Martinsson, and Vladimir Rokhlin. "On the compression of low rank matrices." SIAM Journal on Scientific Computing 26, no. 4 (2005): 1389–1404.
* ↑ Liberty, E., Woolfe, F., Martinsson, P. G., Rokhlin, V., & Tygert, M. (2007). Randomized algorithms for the low-rank approximation of matrices Proceedings of the National Academy of Sciences, 104(51), 20167–20172.