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 ${\displaystyle 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 {\displaystyle L(U\mathbf {x} )=\mathbf {b} }}$ e ${\displaystyle {\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 {\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 ${\displaystyle Q(Rx)=b}$ é resolvido por ${\displaystyle Rx=Q^{T}b=c}$, e o sistema ${\displaystyle 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: ${\displaystyle A=LU}$, onde L é triangular inferior e U é triangular superior.
• Relacionado: a decomposição da LDU é ${\displaystyle 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 é ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle 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: ${\displaystyle A=CF}$, 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: ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle Ax=b}$. O fato de que Q é ortogonal significa que ${\displaystyle (Q^{T})*Q=I}$, para que ${\displaystyle Ax=b}$ é equivalente a ${\displaystyle 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.^[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