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=L{L}^{*}$

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=L{L}^{*}$ 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=L{L}^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=L{L}^{*},$ contudo, a decomposição não precisa ser única quando $A$ é positiva semidefinida.

O inverso é trivial: se $A$ pode ser escrita como $L{L}^{*}$ 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{=}𝐋𝐃𝐋}^{*}$

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 $L{L}^{*},$ como segue:

${𝐀\mathbf{=}𝐋𝐃𝐋}^{*}=𝐋{𝐃}^{\frac{1}{2}}{𝐃}^{\frac{1}{2}*}{𝐋}^{*}=𝐋{𝐃}^{\frac{1}{2}}(𝐋{𝐃}^{\frac{1}{2}}{)}^{*}$

Ou dada a decomposição de Cholesky clássica ${𝐋}^{Cholesky}$ a forma $𝐋𝐃{𝐋}^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 $𝐋𝐃{𝐋}^T$ são triangulos inferiores, Se $S$ é uma matriz diagonal que contém a diagonal principal de ${𝐋}^{Cholesky}$ então: $𝐃={𝐒}^2$

$𝐋={𝐋}^{Cholesky}{𝐒}^{-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=LD{L}^T$ e é geralmente referida como uma decomposição LDLT (ou decomposição $LD{L}^T$). É fortemente relacionado a decomposição em autovalores de matrizes simétricas, $A=Q\mathrm{\Lambda }{Q}^T.$

Exemplos

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

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

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

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

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:

${𝐀}^{(i)}=\left(\begin{array}{ccc}{𝐈}_{i-1}& 0& 0\\ 0& a_{i,i}& {𝐛}_i^{*}\\ 0& {𝐛}_i& {𝐁}^{(i)}\end{array}\right),$

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

Se nós definirmos agora a matriz $L_i$ por

${𝐋}_i:=\left(\begin{array}{ccc}{𝐈}_{i-1}& 0& 0\\ 0& \sqrt{a_{i,i}}& 0\\ 0& \frac{1}{\sqrt{a_{i,i}}}{𝐛}_i& {𝐈}_{n-i}\end{array}\right),$

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

${𝐀}^{(i)}={𝐋}_i{𝐀}^{(i+1)}{𝐋}_i^{*}$

onde

${𝐀}^{(i+1)}=\left(\begin{array}{ccc}{𝐈}_{i-1}& 0& 0\\ 0& 1& 0\\ 0& 0& {𝐁}^{(i)}-\frac{1}{a_{i,i}}{𝐛}_i{𝐛}_i^{*}\end{array}\right).$

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

$𝐋:={𝐋}_1{𝐋}_2\dots {𝐋}_n.$