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 , 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 e requerem menos adições e multiplicações para resolver, em comparação com o sistema original , 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 é resolvido por , e o sistema é 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: , onde L é triangular inferior e U é triangular superior.
- Relacionado: a decomposição da 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 é , 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 . 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 , 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: , onde C é uma matriz de classificação de coluna completa F é uma matriz de classificação de linha completa r.
[1][2][3][4][5]
Decomposição de Cholesky
Artigo principal: decomposição de Cholesky
- Aplicável a: quadrado, hermitiano, matriz definida positiva A.
- Decomposição: , 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 , (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 . O fato de que Q é ortogonal significa que , para que é equivalente a , 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.[6][7][8]
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.[9][10]
.
- 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.