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.^[1]

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

${\displaystyle A=LL^{*}}$

onde ${\displaystyle L}$ é uma matriz triangular inferior com entradas diagonais positivas e reais, e ${\displaystyle L^{*}}$ denota a matriz conjugada transposta de ${\displaystyle 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.^[2]

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

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

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

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

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

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

onde ${\displaystyle L}$ é uma matriz triangular unitária e ${\displaystyle D}$ é uma matriz diagonal.

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

${\displaystyle \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 ${\displaystyle \mathbf {L} ^{Cholesky}}$ a forma ${\displaystyle \mathbf {L} \mathbf {D} \mathbf {L} ^{T}}$ pode ser achada usando a propriedade de que a diagonal de ${\displaystyle L}$ deve ser 1 e de que ambas a decomposição de Cholesky e a forma ${\displaystyle \mathbf {L} \mathbf {D} \mathbf {L} ^{T}}$ são triangulos inferiores,^[5] Se ${\displaystyle S}$ é uma matriz diagonal que contém a diagonal principal de ${\displaystyle \mathbf {L} ^{Cholesky}}$ então: ${\displaystyle \mathbf {D} =\mathbf {S} ^{2}}$

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

A variante ${\displaystyle LDL,}$ 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 ${\displaystyle LDL}$ com entradas negativas em ${\displaystyle D.}$ Para esses casos, a decomposição LDL pode ser preferível. Para matrizes reais, a fatorização tem a forma ${\displaystyle A=LDL^{T}}$ e é geralmente referida como uma decomposição LDLT (ou decomposição ${\displaystyle LDL^{T}}$). É fortemente relacionado a decomposição em autovalores de matrizes simétricas, ${\displaystyle A=Q\Lambda Q^{T}.}$

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

${\displaystyle {\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 ${\displaystyle LDL^{T}:}$

${\displaystyle {\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}}}$

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

O algoritmo recursivo começa com ${\displaystyle i:=1}$ e

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

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

${\displaystyle \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 ${\displaystyle I_{i-1}}$ denota a matriz identidade de dimensão ${\displaystyle i-1.}$

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

${\displaystyle \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 ${\displaystyle A^{(i)}}$ como

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

onde

${\displaystyle \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 ${\displaystyle 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 ${\displaystyle i}$ de ${\displaystyle 1}$ a ${\displaystyle n.}$ Depois de ${\displaystyle n}$ passos, têm-se ${\displaystyle A^{(n+1)}=I.}$ Consequentemente, a matriz triangular inferior ${\displaystyle L}$ que estamos procurando é calculado como

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

Referências

Este artigo sobre matemática é um esboço. Você pode ajudar a Wikipédia expandindo-o.