Cholesky

1.5- O Método de Cholesky
1.5.1- O Processo de Decomposição de Cholesky
O Processo de Cholesky é definido para a resolução de sistemas lineares (n x n) cuja matriz do Sistema é Simétrica e Definida Positiva (ver livro de Ruggiero, M.A.G.) A decomposição feita a seguir considera estas hipóteses.
Seja:

a 12 ..... a1n   g11
0  g11
 a 11

 

a 22 ..... a 2 n   g 21 g 22
 a 21

 ..........
 = .........


 

 a
 

 n1 a n 2 ..... a nn   g n1 g n 2 ... g nn  0
Aplicando a definição de produtos de matrizes obtemos:
a) Elementos diagonais.
2
a 11 = g 11

a 22 = g 2 + g 2
21
22
M
a nn = g 21 + g 2 2 + L + g 2 nn n n Assim:

g11 = a 11


1/ 2 i −1
(I )
, i = 2,3, L , n

2 
g ii =  a ii − ∑ g ik 



 k =1



b) Elementos não diagonais.
b.1) 1ª coluna a 21 = g 21 g11 a 31 = g 31 g11
M
a n1 = g n1 g11
20

g 21 ..... g n1 

g 22 ..... g n 2 

...........

g nn 


b.2) 2ª coluna a 32 = g 31 g 21 + g 32 g 22 a 42 = g 41 g 21 + g 42 g 22
K
a n 2 = g n1 g 21 + g n 2 g 22
b.3) Para a j-ésima coluna , teríamos:

a j+1, j = g j+1,1 g j1 + g j+1, 2 g j2 + K+ g j+1, jg jj a j+2 , j = g j+2 ,1 g j1 + g j+ 2, 2 g j2 + K + g j+ 2, jg jj
L
a nj = g n1 g j1 + g n 2 g j2 + L + g njg jj
Assim
a

g i1 = i1 , i = 2,3, K , n

g11
(II )

j −1


g ij =  a ij − ∑ g ik g jk  g jj ,2〈 j〈i



k =1




Utilizadas numa ordem conveniente as fórmulas (I) e (II) determinam os gij.
Uma ordem conveniente pode ser: g11 , g21, g31 , ..., gn1 ; g22 , g32, ..., gn2 ; ..., gnn
Observação:
1.) Vimos no caso da decomposição LU, que det(A) = u .u22 ...unn , uma
11
vez que os elementos diagonais de L eram unitários.
No caso do método de Cholesky temos:
A = G.Gt
∴ det (A) = (det G)2 = (g11 g22 ......gnn)2
2.) Uma vez calculado G, a solução de Ax = b fica reduzida à solução do par de sistemas triangulares:
Gy = b
Gtx = y

21