Pergunta que precisamos responder: encontrar o vetor x que satisfaz A x = b, utilizando a decomposição de Cholesky.]
Passo 2
O que é a decomposição de Cholesky e quando dá para usar? Vou explicar devagarinho.
A decomposição de Cholesky procura uma matriz triangular inferior L tal que
A = L\,L^{T},
onde L^{T} é a transposta de L. Essa decomposição só existe (e é única) quando A é simétrica e definida positiva (ou, em termos práticos, quando os menores principais são positivos). No nosso caso a matriz A é simétrica (os elementos fora da diagonal espelham-se), então faz sentido tentar Cholesky.
Se conseguimos A = L L^{T}, para resolver A x = b fazemos dois passos:
Resolver o sistema triangular inferior L y = b por substituição direta (forward substitution).
Resolver o sistema triangular superior L^{T} x = y por substituição retroativa (back substitution).
Agora as fórmulas para construir L. Se L tem entradas l_{ij} (com l_{ij}=0 para j>i), então, para i=1,\dots,n:
Aqui a_{ij} são os elementos da matriz A. Essas fórmulas vêm de igualar A com L L^{T} e identificar entradas correspondentes. Vou aplicar isso passo a passo com números.
Você pode checar multiplicando L L^{T} e verificar que volta a dar A; é uma boa checagem mental (não vou repetir a multiplicação inteira aqui para não alongar demais).]
Passo 9
Agora vamos resolver L y = b (forward substitution). Escrevendo as equações linha a linha: