07 Cholesky
07 Cholesky
07 Cholesky
Definição: Se 𝐴𝑛×𝑛 é uma matriz quadrada e 𝑣𝑛×1 é um vetor coluna não nulo, dizemos
que 𝐴 é uma matriz definida positiva se satisfaz ambas as condições abaixo:
(i) A é simétrica
(ii) 𝑣 𝑇 𝐴𝑣 > 0, ∀𝑣 não nulo
2 1
𝐴=[ ]
1 2
2 1
𝐴𝑇 = [ ]=𝐴
1 2
𝑥 2𝑥 + 𝑦
[𝑥 𝑦] ∙ [2 1] ∙ [ ] = [𝑥 𝑦] ∙ [ ]
1 2 𝑦 𝑥 + 2𝑦
= 2𝑥 2 + 𝑥𝑦 + 𝑦𝑥 + 2𝑦 2
1 2
𝑀=[ ]
2 5
2 1 1
𝐴 = [1 2 1]
1 1 1
2 1 1 𝑥 2𝑥 + 𝑦 + 𝑧
[𝑥 𝑦 𝑧 ] ∙ [1 2 1] ∙ [𝑦] = [𝑥 𝑦 𝑧] ∙ [𝑥 + 2𝑦 + 𝑧]
1 1 1 𝑧 𝑥+𝑦+𝑧
Obs.
(𝑥 + 𝑦 + 𝑧)2 = 𝑥 2 + 𝑦 2 + 𝑧 2 + 2(𝑥𝑦 + 𝑥𝑧 + 𝑦𝑧)
Logo:
2 1 1 𝑥
[𝑥 𝑦 𝑧 ] ∙ [1 2 1] ∙ [𝑦] = (𝑥 + 𝑦 + 𝑧)2 + 𝑥 2 + 𝑦 2 > 0
1 1 1 𝑧
2 −1 0
𝐴 = [−1 2 −1]
0 −1 2
2 −1 0
𝑇
𝐴 = [−1 2 −1] = 𝐴
0 −1 2
𝑑𝑒𝑡(𝐴1×1 ) = 2 > 0
2 −1
𝑑𝑒𝑡(𝐴2×2 ) = | |= 4−1= 3> 0
−1 2
2 −1 0
𝑑𝑒𝑡(𝐴3×3 ) = |−1 2 −1| = 8 − 2 − 2 = 4 > 0
0 −1 2
−2 −1 0
𝐴 = [−1 2 −1]
0 −1 2
Matlab
clear
clc
[i,j]=size(A);
tic
for n=1:i
if det(A(1:n,1:n))>0
if n==i
disp('MATRIZ DEFINIDA POSITIVA')
end
else
disp('NÃO É DEFINIDA POSITIVA')
break
end
end
toc
• Decomposição de Cholesky
Cholesky
Se 𝐴 é uma matriz definida positiva, então ela pode ser fatorada por:
𝐴 = 𝐿𝐿𝑇 𝑜𝑢 𝑈 𝑇 𝑈
Obs. Para os exemplos ilustrativos utilizaremos sempre a decomposição pela matriz
triangular superior (𝐴 = 𝑈 𝑇 𝑈) para fins de conferência com o Matlab.
9 6
𝐴=[ ]
6 5
Primeiro, verificamos que 𝐴 é definida positiva, pois a matriz é simétrica, e 𝐴1×1 = 9 >
0 e 𝑑𝑒𝑡(𝐴) = 45 − 36 = 9 > 0
Matriz 𝑈 genérica:
𝑎 𝑏
𝑈=[ ]
0 𝑐
Aplicando o método:
𝑎 0 𝑎 2
𝑈𝑇 𝑈 = [ ][
𝑏
] = [𝑎 𝑎𝑏 ] = [9 6] = 𝐴
𝑏 𝑐 0 𝑐 𝑎𝑏 𝑏 + 𝑐2
2 6 5
𝑎2 = 9 ⇒ 𝑎 = 3
𝑎𝑏 = 6 ⇒ 𝑏 = 2
𝑏2 + 𝑐 2 = 5 ⇒ 𝑐 = 1
3 2
𝑈=[ ]
0 1
Checando:
3 0 3 2 9 6
𝑈𝑇 𝑈 = [ ][ ]=[ ]=𝐴
2 1 0 1 6 5
Matlab:
𝐴𝑥 = 𝑏 𝑇 𝑈𝑇 𝑦 = 𝑏
{ ⇒ 𝑈 𝑈𝑥 = 𝑏 ⇒ {
𝐴 = 𝑈𝑇 𝑈 𝑦 = 𝑈𝑥
Note que criamos o vetor auxiliar 𝑦. Vai ser necessário resolver 2 sistemas, mas como
eles são triangulares, são rápidos de resolver (igual à Fatoração LU). Devemos seguir os
seguintes passos:
1º passo: Obter a matriz 𝑈
25 15 −5 70
𝐴 = [ 15 18 0 ]; 𝑏 = [ 48 ]
−5 0 11 −21
1º passo: Calcular 𝑈
𝑎 0 0 𝑎 𝑏 𝑐 𝑎2 𝑎𝑏 𝑎𝑐 25 15 −5
𝑇
𝑈 𝑈 = [𝑏 𝑑 0 ] [0 𝑑 𝑒 ] = [𝑎𝑏 𝑏2 + 𝑑2 𝑏𝑐 + 𝑑𝑒 ] = [ 15 18 0 ] = 𝐴
𝑐 𝑒 𝑓 0 0 𝑓 𝑎𝑐 𝑏𝑐 + 𝑑𝑒 𝑐2 + 𝑒2 + 𝑓2 −5 0 11
𝑎 = 5; 𝑏 = 3; 𝑐 = −1; 𝑑 = 3; 𝑒 = 1; 𝑓 = 3
5 3 −1
𝑈 = [0 3 1]
0 0 3
2º passo: 𝑈 𝑇 𝑦 = 𝑏
5 0 0 𝑦1 70 𝑦1 = 14
[ 3 3 0] [𝑦2 ] = [ 48 ] ⇒ 𝑦2 = 2
−1 1 3 𝑦3 −21 𝑦3 = −3
3º passo: 𝑦 = 𝑈𝑥
5 3 −1 𝑥1 14 𝑥1 = 2
[0 3 1 ] [𝑥2 ] = [ 2 ] ⇒ 𝑥2 = 1
0 0 3 𝑥3 −3 𝑥3 = −1
U = chol(A); % 1o Passo
y = U'\b; % 2o Passo
sol = U\y % 3o Passo
Exercício: Mostre que o sistema pode ser resolvido pelo método de Cholesky e resolva-
o usando Cholesky.