Decomposição da matriz - Matrix decomposition

Na disciplina matemática de álgebra linear , uma decomposição de matriz ou fatoração de matriz é uma fatoração de uma matriz em um produto de matrizes. Existem muitas decomposições de matriz diferentes; cada um encontra uso em uma classe particular de problemas.

Exemplo

Na análise numérica , diferentes decomposições são usadas para implementar algoritmos de matriz eficientes .

Por exemplo, ao resolver um sistema de equações lineares , a matriz A pode ser decomposta por meio da decomposição LU . A decomposição LU fatoriza uma matriz em uma matriz triangular inferior L e uma matriz triangular superior L . Os sistemas e requerem menos adições e multiplicações de resolver, em comparação com o sistema original , embora se possa requerem significativamente mais dígitos em inexacta aritmética como ponto flutuante . ${\ displaystyle A \ mathbf {x} = \ mathbf {b}}$ ${\ displaystyle L (U \ mathbf {x}) = \ mathbf {b}}$${\ displaystyle U \ mathbf {x} = L ^ {- 1} \ mathbf {b}}$${\ displaystyle A \ mathbf {x} = \ mathbf {b}}$

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 ( R x ) = b é resolvido por R x = Q ^T b = c , e o sistema R x = c é resolvido por ' substituição reversa '. O número de adições e multiplicações necessárias é cerca de duas vezes maior do que usar o solucionador LU, mas não são necessários mais dígitos na aritmética inexata porque a decomposição QR é numericamente estável .

Decomposições relacionadas com a resolução de sistemas de equações lineares

Decomposição LU

• Tradicionalmente aplicável a: matriz quadrada A , embora matrizes retangulares possam ser aplicáveis.
• Decomposição:, onde L é triangular inferior e U é triangular superior${\ displaystyle A = LU}$
• Relacionado: a decomposição LDU é , onde L é triangular inferior com uns na diagonal, U é triangular superior com uns na diagonal e D é uma matriz diagonal . ${\ displaystyle A = LDU}$
• Relacionado: a decomposição de LUP é , onde L é triangular inferior , U é triangular superior e P é uma matriz de permutação . ${\ displaystyle A = LUP}$
• Existe uma LUP decomposição para qualquer matriz quadrada: existência Uma . 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 n -by- n 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 P  =  I , então existe uma decomposição LU. ${\ displaystyle A \ mathbf {x} = \ mathbf {b}}$

Redução LU

Bloco de decomposição LU

Fatoração de classificação

• Aplicável a: matriz A m -by- n de classificação r
• Decomposição: onde C é uma matriz de classificação de coluna completa m -by- r e F é uma matriz de classificação de linha completa r -by- n${\ displaystyle A = CF}$
• Comentário: A fatoração de classificação pode ser usada para calcular o pseudoinverso Moore-Penrose de A , que pode ser aplicado para obter todas as soluções do sistema linear . ${\ displaystyle A \ mathbf {x} = \ mathbf {b}}$

Decomposição de Cholesky

• Aplicável a: quadrado , hermitiano , matriz definida positiva A
• Decomposição: onde é triangular superior com entradas diagonais reais positivas ${\ displaystyle A = U ^ {*} U}$${\ displaystyle U}$
• Comentário: se a matriz é Hermitiana e semi-definida positiva, então ela tem uma decomposição da forma se as entradas diagonais de forem permitidas em zero ${\ displaystyle A}$${\ displaystyle A = U ^ {*} U}$${\ displaystyle U}$
• 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, tem todos os elementos reais ${\ displaystyle U}$
• Comentário: Uma alternativa é a decomposição do LDL , que pode evitar a extração de raízes quadradas.

Decomposição QR

• Aplicável a: matriz A m -by- n com colunas linearmente independentes
• Decomposição: onde é uma matriz unitária de tamanho m -by- m , e é uma matriz triangular superior de tamanho m -by- n${\ displaystyle A = QR}$${\ displaystyle Q}$${\ displaystyle R}$
• Singularidade: em geral não é único, mas se for de nível total , então existe um único que tem todos os elementos diagonais positivos. Se é quadrado, também é único. ${\ displaystyle A}$${\ displaystyle R}$${\ displaystyle A}$${\ displaystyle Q}$
• Comentário: A decomposição QR fornece uma maneira eficaz de resolver o sistema de equações . O fato de ser ortogonal significa que , então isso é equivalente a , o que é muito fácil de resolver por ser triangular . ${\ displaystyle A \ mathbf {x} = \ mathbf {b}}$${\ displaystyle Q}$${\ displaystyle Q ^ {\ mathrm {T}} Q = I}$${\ displaystyle A \ mathbf {x} = \ mathbf {b}}$${\ displaystyle R \ mathbf {x} = Q ^ {\ mathsf {T}} \ mathbf {b}}$${\ displaystyle R}$

Fatoração RRQR

Decomposição interpolativa

Decomposições baseadas em autovalores e conceitos relacionados

Eigendecomposition

• Também chamada de decomposição espectral .
• Aplicável a: matriz quadrada A com autovetores linearmente independentes (não necessariamente autovalores distintos).
• Decomposição: , em que D é uma matriz diagonal formada a partir dos valores próprios de uma , e as colunas de V são os correspondentes vectores próprios de Uma . ${\ displaystyle A = VDV ^ {- 1}}$
• Existência: Um n -by- n matriz A tem sempre n (complexos) valores próprios, que podem ser ordenadas (em mais do que uma forma) para formar um N -by- n matriz diagonal D e uma matriz correspondente de colunas diferente de zero V que satisfaz a equação do valor próprio . é invertível se e somente se os n autovetores forem linearmente independentes (ou seja, cada autovalor tem multiplicidade geométrica igual à sua multiplicidade algébrica ). Uma condição suficiente (mas não necessária) para que isso aconteça é que todos os autovalores sejam diferentes (neste caso, a multiplicidade geométrica e algébrica são iguais a 1) ${\ displaystyle AV = VD}$${\ displaystyle V}$
• Comentário: Sempre é possível normalizar os autovetores para terem comprimento um (ver a definição da equação de autovalor)
• Comentário: Cada matriz normal A (ou seja, matriz para a qual , onde está uma transposta conjugada ) pode ser decomposta automaticamente. Para uma matriz normal A (e apenas para uma matriz normal), os autovetores também podem ser feitos ortonormais ( ) e a decomposição própria pode ser lida como . Em particular, todas as matrizes unitárias , hermitianas ou skew-hermitianas (no caso de valor real, todas ortogonais , simétricas ou assimétricas , respectivamente) são normais e, portanto, possuem essa propriedade. ${\ displaystyle AA ^ {*} = A ^ {*} A}$${\ displaystyle A ^ {*}}$ ${\ displaystyle VV ^ {*} = I}$${\ displaystyle A = VDV ^ {*}}$
• Comentário: Para qualquer matriz simétrica real A , a decomposição automática sempre existe e pode ser escrita como , onde D e V têm valores reais. ${\ displaystyle A = VDV ^ {\ mathsf {T}}}$
• Comentário: A decomposição automática é útil para compreender a solução de um sistema de equações diferenciais ordinárias lineares ou equações de diferenças lineares. Por exemplo, a equação de diferença a partir da condição inicial é resolvido por , o que é equivalente a , onde V e D são os formados a partir de matrizes de vectores prprios e os valores próprios de uma . Como D é diagonal, elevando-o à potência , envolve apenas elevar cada elemento na diagonal à potência t . Isso é muito mais fácil de fazer e entender do que elevar A à potência t , já que A geralmente não é diagonal. ${\ displaystyle x_ {t + 1} = Ax_ {t}}$${\ displaystyle x_ {0} = c}$${\ displaystyle x_ {t} = A ^ {t} c}$${\ displaystyle x_ {t} = VD ^ {t} V ^ {- 1} c}$${\ displaystyle D ^ {t}}$

Decomposição de Jordan

A forma normal de Jordan e a decomposição de Jordan-Chevalley

• Aplicável a: matriz quadrada A
• Comentário: a forma normal de Jordan generaliza a decomposição automática para casos onde há autovalores repetidos e não podem ser diagonalizados, a decomposição de Jordan-Chevalley faz isso sem escolher uma base.

Decomposição de Schur

• Aplicável a: matriz quadrada A
• Decomposição (versão complexa) :, onde U é uma matriz unitária , é a transposta conjugada de U , e T é uma matriz triangular superior chamada forma de Schur complexa que tem os autovalores de A ao longo de sua diagonal. ${\ displaystyle A = UTU ^ {*}}$${\ displaystyle U ^ {*}}$
• Comentário: se A é uma matriz normal , então T é diagonal e a decomposição de Schur coincide com a decomposição espectral.

Decomposição de Schur real

• Aplicável a: matriz quadrada A
• Decomposição: Esta é uma versão da decomposição de Schur onde e contém apenas números reais. Sempre se pode escrever onde V é uma matriz ortogonal real , é a transposta de V e S é uma matriz triangular superior de bloco chamada forma de Schur real . Os blocos na diagonal de S são de tamanho 1 × 1 (caso em que representam autovalores reais) ou 2 × 2 (caso em que são derivados de pares de autovalores conjugados complexos ). ${\ displaystyle V}$${\ displaystyle S}$${\ displaystyle A = VSV ^ {\ mathsf {T}}}$${\ displaystyle V ^ {\ mathsf {T}}}$

Decomposição QZ

• Também chamado de decomposição de Schur generalizada
• Aplicável a: matrizes quadradas A e B
• Comentário: existem duas versões desta decomposição: complexa e real.
• Decomposição (versão complexa): e onde Q e Z são matrizes unitárias , o * sobrescrito representa a transposta conjugada e S e T são matrizes triangulares superiores . ${\ displaystyle A = QSZ ^ {*}}$${\ displaystyle B = QTZ ^ {*}}$
• Comentário: na decomposição QZ complexo, as proporções dos elementos diagonais de S para os elementos diagonais correspondentes de T , , são os generalizadas valores próprios que resolvem o problema de valores próprios generalizada (onde é um escalar desconhecido e v é um vector diferente de zero desconhecido). ${\ displaystyle \ lambda _ {i} = S_ {ii} / T_ {ii}}$ ${\ displaystyle A \ mathbf {v} = \ lambda B \ mathbf {v}}$${\ displaystyle \ lambda}$
• Decomposição (versão real): e onde A , B , Q , Z , S e T são matrizes contendo apenas números reais. Neste caso, Q e Z são matrizes ortogonais , o T sobrescrito representa a transposição e S e T são matrizes triangulares superiores em bloco . Os blocos na diagonal de S e T são de tamanho 1 × 1 ou 2 × 2. ${\ displaystyle A = QSZ ^ {\ mathsf {T}}}$${\ displaystyle B = QTZ ^ {\ mathsf {T}}}$

Fatoração de Takagi

• Aplicável a: praça, complexo, simétrica matriz A .
• Decomposição:, onde D é uma matriz diagonal não negativa real e V é unitária . indica a transposta da matriz de V . ${\ displaystyle A = VDV ^ {\ mathsf {T}}}$${\ displaystyle V ^ {\ mathsf {T}}}$
• Comentário: Os elementos diagonais de D são as raízes quadradas não negativas dos autovalores de . ${\ displaystyle AA ^ {*}}$
• Comentário: V pode ser complexo mesmo se A for real.
• Comentário: Este não é um caso especial de eigendecomposition (veja acima), que usa em vez de . Além disso, se A não for real, não é hermitiano e a forma usando também não se aplica. ${\ displaystyle V ^ {- 1}}$${\ displaystyle V ^ {\ mathsf {T}}}$${\ displaystyle V ^ {*}}$

Decomposição de valor singular

• Aplicável a: matriz A m -by- n .
• Decomposição:, onde D é uma matriz diagonal não negativa e U e V satisfazem . Aqui está a transposta conjugada de V (ou simplesmente a transposta , se V contiver apenas números reais), e I denota a matriz de identidade (de alguma dimensão). ${\ displaystyle A = UDV ^ {*}}$${\ displaystyle U ^ {*} U = I, V ^ {*} V = I}$${\ displaystyle V ^ {*}}$
• Comentário: Os elementos da diagonal de D são chamados os valores singulares de A .
• Comentário: Como a decomposição automática acima, a decomposição de valor singular envolve encontrar direções básicas ao longo das quais a multiplicação da matriz é equivalente à multiplicação escalar, mas tem maior generalidade, uma vez que a matriz em consideração não precisa ser quadrada.
• Singularidade: os valores singulares de são sempre determinados de forma única. e não precisa ser único em geral. ${\ displaystyle A}$${\ displaystyle U}$${\ displaystyle V}$

Decomposições invariantes de escala

Refere-se a variantes de decomposições de matriz existentes, como o SVD, que são invariantes em relação à escala diagonal.

• Aplicável a: matriz A m -by- n .
• Unidade-Scale-Invariant Singular Value Decomposition-: , onde S é um não-negativo única matriz diagonal de valores singulares de escala-invariante, U e V são matrizes unitárias , é a transposta conjugada de V , e matrizes diagonais positivos D e E . ${\ displaystyle A = DUSV ^ {*} E}$${\ displaystyle V ^ {*}}$
• Comentário: É análogo ao SVD, exceto que os elementos diagonais de S são invariantes em relação à multiplicação esquerda e / ou direita de A por matrizes diagonais não singulares arbitrárias, em oposição ao SVD padrão para o qual os valores singulares são invariantes em relação à esquerda e / ou multiplicação correta de A por matrizes unitárias arbitrárias.
• Comentário: É uma alternativa para o SVD padrão quando invariância é necessário em relação à diagonal em vez de transformações unitárias de Uma .
• Singularidade: os valores singulares de escala invariante de (dados pelos elementos diagonais de S ) são sempre determinados de forma única. As matrizes diagonais D e E , e U e V unitárias , não são necessariamente únicas em geral. ${\ displaystyle A}$
• Comentário: as matrizes U e V não são iguais às do SVD.

Decomposições invariantes de escala análogas podem ser derivadas de outras decomposições de matriz, por exemplo, para obter autovalores invariantes de escala.

Outras decomposições

Decomposição polar

• Aplicável a: qualquer quadrado complexa matriz A .
• Decomposição: (decomposição polar direita) ou (decomposição polar esquerda), onde U é uma matriz unitária e P e P ' são matrizes Hermitianas semidefinidas positivas . ${\ displaystyle A = UP}$${\ displaystyle A = P'U}$
• Singularidade: é sempre única e igual a (que é sempre hermitiana e semidefinida positiva). Se for invertível, será único. ${\ displaystyle P}$${\ displaystyle {\ sqrt {A ^ {*} A}}}$${\ displaystyle A}$${\ displaystyle U}$
• Comentário: Uma vez que qualquer matriz Hermitiana admite uma decomposição espectral com uma matriz unitária, pode ser escrita como . Como é semidefinido positivo, todos os elementos em são não negativos. Como o produto de duas matrizes unitárias é unitário, tomando- se pode escrever qual é a decomposição de valor singular. Portanto, a existência da decomposição polar é equivalente à existência da decomposição em valor singular. ${\ displaystyle P}$${\ displaystyle P = VDV ^ {*}}$${\ displaystyle P}$${\ displaystyle D}$${\ displaystyle W = UV}$${\ displaystyle A = U (VDV ^ {*}) = WDV ^ {*}}$

Decomposição polar algébrica

• Aplicável a: matriz A quadrada, complexa e não singular .
• Decomposição:, onde Q é uma matriz ortogonal complexa e S é uma matriz simétrica complexa. ${\ displaystyle A = QS}$
• Unicidade: Se não houver autovalores reais negativos, a decomposição é única. ${\ displaystyle A ^ {\ mathsf {T}} A}$
• Comentário: A existência desta decomposição é equivalente a ser semelhante a . ${\ displaystyle AA ^ {\ mathsf {T}}}$${\ displaystyle A ^ {\ mathsf {T}} A}$
• Comentário: Uma variante dessa decomposição é , onde R é uma matriz real e C é uma matriz circular . ${\ displaystyle A = RC}$

Decomposição de Mostow

• Aplicável a: matriz A quadrada, complexa e não singular .
• Decomposição: onde U é unitário, M é anti-simétrico real e S é simétrico real. ${\ displaystyle A = Ue ^ {iM} e ^ {S}}$
• Comentário: A matriz A também pode ser decomposta como , onde U ₂ é unitário, M ₂ é anti-simétrico real e S ₂ é simétrico real. ${\ displaystyle A = U_ {2} e ^ {S_ {2}} e ^ {iM_ {2}}}$

Forma normal de Sinkhorn

• Aplicável a: matriz real quadrada A com elementos estritamente positivos.
• Decomposição:, onde S é duplamente estocástico e D ₁ e D ₂ são matrizes diagonais reais com elementos estritamente positivos. ${\ displaystyle A = D_ {1} SD_ {2}}$

Decomposição setorial

• Aplicável a: quadrada, matriz complexa A com intervalo numérico contido no setor . ${\ displaystyle S _ {\ alpha} = \ left \ {re ^ {i \ theta} \ in \ mathbb {C} \ mid r> 0, | \ theta | \ leq \ alpha <{\ frac {\ pi} { 2}} \ certo \}}$
• Decomposição:, onde C é uma matriz complexa invertível e com todos . ${\ displaystyle A = CZC ^ {*}}$${\ displaystyle Z = \ operatorname {diag} \ left (e ^ {i \ theta _ {1}}, \ ldots, e ^ {i \ theta _ {n}} \ right)}$${\ displaystyle \ left | \ theta _ {j} \ right | \ leq \ alpha}$

Forma normal de Williamson

• Aplicável a: quadrada, matriz real definida positiva A com ordem 2 n × 2 n .
• Decomposição :, onde é uma matriz simplética e D é uma matriz diagonal n-por- n não negativa . ${\ displaystyle A = S ^ {\ mathsf {T}} \ operatorname {diag} (D, D) S}$${\ displaystyle S \ in {\ text {Sp}} (2n)}$

Raiz quadrada da matriz

• Decomposição:, não único em geral. ${\ displaystyle A = BB}$
• No caso do semidefinido positivo , existe um semidefinido positivo único tal que . ${\ displaystyle A}$${\ displaystyle B}$${\ displaystyle A = B ^ {*} B = BB}$

Generalizações

Existem análogos das fatorações SVD, QR, LU e Cholesky para quasimatrizes e cmatrizes ou matrizes contínuas . Uma 'quasimatriz' é, como uma matriz, um esquema retangular cujos elementos são indexados, mas um índice discreto é substituído por um índice contínuo. Da mesma forma, uma 'cmatriz' é contínua em ambos os índices. Como exemplo de cmatrix, pode-se pensar no kernel de um operador integral .

Essas fatorações são baseadas nos primeiros trabalhos de Fredholm (1903) , Hilbert (1904) e Schmidt (1907) . Para um relato e uma tradução para o inglês dos artigos seminais, consulte Stewart (2011) .

Veja também

• Divisão de matriz
• Fatoração de matriz não negativa
• Análise do componente principal

Referências

Notas

Citações

Bibliografia

• 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 (2): 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). "Equivalência contragrediente: uma forma canônica e algumas aplicações" . Álgebra Linear e suas aplicações . 214 : 43–92. doi : 10.1016 / 0024-3795 (93) 00056-6 .
• Meyer, CD (2000), Matrix Analysis and Applied Linear Algebra , SIAM , ISBN   978-0-89871-454-8
• 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-4767, doi : 10.1007 / b.
• Simon, C .; Blume, L. (1994). Matemática para Economistas . Norton. ISBN   978-0-393-95733-4 .
• Stewart, GW (2011), Fredholm, Hilbert, Schmidt: três artigos fundamentais sobre equações integrais (PDF) , recuperado em 06-01-2015
• Townsend, A .; Trefethen, LN (2015), "Continuous analogues of matrix factorizations", Proc. R. Soc. A , 471 (2173): 20140585, Bibcode : 2014RSPSA.47140585T , doi : 10.1098 / rspa.2014.0585 , PMC   4277194 , PMID   25568618

links externos

• Calculadora Matrix Online
• Wolfram Alpha Matrix Decomposition Computation »LU e QR Decomposition
• Springer Encyclopaedia of Mathematics »Fatoração de matrizes
• GraphLab Biblioteca de filtragem colaborativa GraphLab , implementação paralela em larga escala de métodos de decomposição de matriz (em C ++) para multicore.