Fatoração de Cholesky

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.

Definição

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

$A=LL^{*}$

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

Se a matriz $A$ é hermitiana e positiva semi-definida, então ainda tem uma decomposição da forma $A=LL^{*}$ se as entradas diagonais de $L$ são permitidas serem nulas.

Quando $A$ tem entradas reais, $L$ também tem entradas reais e a fatorização pode ser escrita $A=LL^{T}$

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

O inverso é trivial: se $A$ pode ser escrita como $LL^{*}$ para alguma $L$ inversível, triangular inferior ou de outra forma, então $A$ é hermitiana e positiva definida.

Decomposição LDL

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

$\mathbf {A=LDL} ^{*}$

onde $L$ é uma matriz triangular unitária e $D$ é uma matriz diagonal.

Esta composição é relacionada a decomposição de Cholesky clássica, da forma $LL^{*},$ como segue:

$\mathbf {A=LDL} ^{*}=\mathbf {L} \mathbf {D} ^{\frac {1}{2}}\mathbf {D} ^{{\frac {1}{2}}{*}}\mathbf {L} ^{*}=\mathbf {L} \mathbf {D} ^{\frac {1}{2}}(\mathbf {L} \mathbf {D} ^{\frac {1}{2}})^{*}$

Ou dada a decomposição de Cholesky clássica $\mathbf {L} ^{Cholesky}$ a forma $\mathbf {L} \mathbf {D} \mathbf {L} ^{T}$ pode ser achada usando a propriedade de que a diagonal de $L$ deve ser 1 e de que ambas a decomposição de Cholesky e a forma $\mathbf {L} \mathbf {D} \mathbf {L} ^{T}$ são triangulos inferiores, Se $S$ é uma matriz diagonal que contém a diagonal principal de $\mathbf {L} ^{Cholesky}$ então: $\mathbf {D} =\mathbf {S} ^{2}$

$\mathbf {L} =\mathbf {L} ^{Cholesky}\mathbf {S} ^{-1}$

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

Exemplos

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

${\begin{aligned}\left({\begin{array}{*{3}{r}}4&12&-16\\12&37&-43\\-16&-43&98\\\end{array}}\right)=\left({\begin{array}{*{3}{r}}2&0&0\\6&1&0\\-8&5&3\\\end{array}}\right)\left({\begin{array}{*{3}{r}}2&6&-8\\0&1&5\\0&0&3\\\end{array}}\right)\end{aligned}}$

E sua decomposição $LDL^{T}:$

${\begin{aligned}\left({\begin{array}{*{3}{r}}4&12&-16\\12&37&-43\\-16&-43&98\\\end{array}}\right)&=\left({\begin{array}{*{3}{r}}1&0&0\\3&1&0\\-4&5&1\\\end{array}}\right)\left({\begin{array}{*{3}{r}}4&0&0\\0&1&0\\0&0&9\\\end{array}}\right)\left({\begin{array}{*{3}{r}}1&3&-4\\0&1&5\\0&0&1\\\end{array}}\right)\end{aligned}}$

Algoritmo computacional

Padrão de acesso (branco) e padrão de escrita (amarelo) para o algoritmo Cholesky — Banachiewicz em uma matriz 5 × 5

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

O algoritmo recursivo começa com $i:=1$ e

$A^{(1)}:=A$

No passo $i,$ a matriz $A^{(i)}$ tem a seguinte forma:

$\mathbf {A} ^{(i)}={\begin{pmatrix}\mathbf {I} _{i-1}&0&0\\0&a_{i,i}&\mathbf {b} _{i}^{*}\\0&\mathbf {b} _{i}&\mathbf {B} ^{(i)}\end{pmatrix}},$

onde $I_{i-1}$ denota a matriz identidade de dimensão $i-1.$

Se nós definirmos agora a matriz $L_{i}$ por

$\mathbf {L} _{i}:={\begin{pmatrix}\mathbf {I} _{i-1}&0&0\\0&{\sqrt {a_{i,i}}}&0\\0&{\frac {1}{\sqrt {a_{i,i}}}}\mathbf {b} _{i}&\mathbf {I} _{n-i}\end{pmatrix}},$

então nós podemos escrever $A^{(i)}$ como

$\mathbf {A} ^{(i)}=\mathbf {L} _{i}\mathbf {A} ^{(i+1)}\mathbf {L} _{i}^{*}$

onde

$\mathbf {A} ^{(i+1)}={\begin{pmatrix}\mathbf {I} _{i-1}&0&0\\0&1&0\\0&0&\mathbf {B} ^{(i)}-{\frac {1}{a_{i,i}}}\mathbf {b} _{i}\mathbf {b} _{i}^{*}\end{pmatrix}}.$

Note que $b_{i}b_{i}^{*}$ é um produto diádico, assim sendo este algoritmo é chamado de versão produto diádico em (Golub & Van Loan).

Repete-se isto para $i$ de $1$ a $n.$ Depois de $n$ passos, têm-se $A^{(n+1)}=I.$ Consequentemente, a matriz triangular inferior $L$ que estamos procurando é calculado como

$\mathbf {L} :=\mathbf {L} _{1}\mathbf {L} _{2}\dots \mathbf {L} _{n}.$