Fatoração de Cholesky

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

Em álgebra linear, a decomposição de Cholesky ou fatoração de Cholesky é uma decomposição de uma matriz hermitiana e positiva definida no produto de uma matriz triangular inferior e sua matriz adjunta, o que é útil por exemplo para soluções numéricas eficientes e simulações de Monte Carlo. Foi descoberta por André-Louis Cholesky para matrizes reais. Quando é aplicável, a decomposição de Cholesky é aproximadamente duas vezes mais eficiente que a decomposição LU para resolver sistemas de equações lineares.[1]

Definição[editar | editar código-fonte]

A decomposição de Cholesky de uma matriz Hermitiana positiva definida "A" se dá da forma:

onde é uma matriz triangular inferior com entradas diagonais positivas e reais, e denota a matriz conjugada transposta de . Toda matriz hermitiana positiva-definida (e portanto também toda matriz real simétrica e positiva-definida) tem uma única decomposição de Cholesky.[2]

Se a matriz é hermitiana e positiva semi-definida, então ainda tem uma decomposição da forma se as entradas diagonais de são permitidas serem nulas.[3]

Quando tem entradas reais, também tem entradas reais e a fatorização pode ser escrita [4]

A decomposição de Cholesky é única quando é positiva definida; existe apenas uma matriz triangular inferior com entradas diagonais estritamente positivas tais que , contudo, a decomposição não precisa ser única quando é positiva semidefinida.

The converse holds trivially: if A can be written as LL* for some invertible L, lower triangular or otherwise, then A is Hermitian and positive definite.

O inverso é trivial: se pode ser escrita como para alguma inversível, triangular inferior ou de outra forma, então é hermitiana e positiva definida.

Decomposição LDL[editar | editar código-fonte]

Uma variante fortemente relacionada da decomposição de Cholesky clássica é a decomposição LDL,

onde é uma matriz triangular unitária e é uma matriz diagonal.

Esta composição é relacionada a decomposição de Cholesky clássica, da forma , como segue:

Ou dada a decomposição de Cholesky clássica a forma pode ser achada usando a propriedade de que a diagonal de deve ser 1 e de que ambas a decomposição de Cholesky e a forma são triangulos inferiores,[5] Se é uma matriz diagonal que contém a diagonal principal de então:

A variante , se eficientemente implementada, requer o mesmo espaço e complexidade computacional para construir e usar, mas evita extrair raízes quadradas.[6] Para matrizes indefinidas para as quais não existe a decomposição de Cholesky têm uma decomposição com entradas negativas em . Para esses casos, a decomposição LDL pode ser preferível. Para matrizes reais, a fatorização tem a forma e é geralmente referida como uma decomposição LDLT (ou decomposição ). É fortemente relacionado a decomposição em autovalores de matrizes simétricas, .

Exemplos[editar | editar código-fonte]

Eis uma decomposição de Cholesky de uma matriz simétrica real:

E sua decomposição :

Algoritmo computacional[editar | editar código-fonte]

O algoritmo de Cholesky, usado para calcular a matriz de decomposição , é uma versão modificada da Eliminação gaussiana.

O algoritmo recursivo começa com e

No passo , a matriz tem a seguinte forma:

onde denota a matriz identidade de dimensão .

Se nós definirmos agora a matriz por

então nós podemos escrever como

onde

Note que é um produto diádico, assim sendo este algoritmo é chamado de versão produto diádico em (Golub & Van Loan).

Repete-se isto para de a . Depois de passos, têm-se . Consequentemente, a matriz triangular inferior que estamos procurando é calculado como

Referências

  1. Press, William H.; Teukolsky, Saul A.; Vetterling, William T.; Flannery, Brian P. (1992). Numerical Recipes in C: The Art of Scientific Computing (second edition). [S.l.]: Cambridge University England EPress. p. 994. ISBN 0-521-43108-5 
  2. Golub & Van Loan (1996, p. 143), Horn & Johnson (1985, p. 407), Trefethen & Bau (1997, p. 174)
  3. Golub & Van Loan (1996, p. 147)
  4. Horn & Johnson (1985, p. 407)
  5. variance – LDLT decomposition from Cholesky decomposition – Cross Validated. Stats.stackexchange.com (2016-04-21). Retrieved on 2016-11-02.
  6. Krishnamoorthy, Aravindh; Menon, Deepak (2011). «Matrix Inversion Using Cholesky Decomposition». 1111: 4144. Bibcode:2011arXiv1111.4144K. arXiv:1111.4144Acessível livremente 

Wiki letter w.svgEste artigo sobre matemática é mínimo. Você pode ajudar a Wikipédia expandindo-o.