Aula 09 e 10 Decomposicao Cholesky

Prévia do material em texto

5 Nov 2008 . 10:58 
Decomposição de Cholesky 
• Idéia: 
 
 Podemos simplificar o método de decomposição LU, quando a 
matriz é simétrica, positiva definida. 
 
 
5 Nov 2008 . 10:58 
Definições 
• Matrizes simétricas: 
 aij = aji 
 
• Matrizes positivas definidas: 
 
 xtAx > 0, qualquer que seja x. 
 
 Critério de Sylvestre: a matriz é positiva definida se e 
somente se todos os menores principais tem 
determinante positivo: 
 
 
 
•Teorema 
Uma matriz simétrica A é positiva definida se, e somente se, o 
determinante de cada submatriz principal é positivo 
1
943
421
312
,3
21
12
,22 







 
Exemplo: 
 
 A matriz 














943
421
312
A
 é positiva pois 
 todos os quais são positivos. Assim, sabe-se que todos os autovalores 
 de A são positivos e que 
0x
0xx AT
 para qualquer 
Outras definições: 
• Uma matriz simétrica A e a forma quadrática 
xxx qualquerparaAse T 0 
xx AT
 são chamadas 
 não-negativa 
0xxx  qualquerparaAse T 0
xxx qualquerparaAse T 0
negativose
positivosvaloresosambostomaAse T xx
negativa 
não-positiva 
indefinida 
Como construir de forma simples matrizes positivas 
definidas ? 
Teorema: Uma matriz simétrica A é positiva definida se, e somente se, 
todos os autovalores de A são positivos 
Teorema: Uma matriz simétrica A é negativa definida se, e somente se, 
todos os autovalores de A são negativos 
Teorema: Uma matriz simétrica A é negativa semi-definida se, e somente 
se, todos os autovalores de A são negativos e existir algum nulo 
Teorema: Uma matriz simétrica A é positiva semi-definida se, e 
somente se, todos os autovalores de A são positivos 
FATORAÇÃO DE CHOLESKY 
 
Definição: Uma matriz quadrada de ordem n é 
definida positiva se . 
 
Definição: A fatoração de Cholesky de uma matriz , 
simétrica positiva, é dada por 
 
 
com uma matriz triangular inferior com elementos da 
diagonal estritamente positivos. 
 
 
A
nT xxAx  0
A
,:onde nnGGGA T 
G
FATORAÇÃO DE CHOLESKY 
 
Do teorema LU, temos , onde é uma 
matriz diagonal de ordem n. Ainda, se for simétrica, 
então e a fatoração escreve-se como: 
 
 
 
Portanto, 
 
A
D
UDLA 
TLU 
ii
TT dLDDLLDLA  iidonde
DLG 
FATORAÇÃO DE CHOLESKY 
 
 
Considere a matriz 
 
 
Calculando os fatores L U 
 



















83214
214112
1124
412416
A













 






































81000
1100
0210
412416
1104/1
0124/3
0014/1
0001
83214
214112
1124
412416
A
FATORAÇÃO DE CHOLESKY 
 
Calculando os fatores 
 
ULA 













 






































81000
1100
0210
412416
1104/1
0124/3
0014/1
0001
83214
214112
1124
412416
UDLDL e
TLDLA 













 


































1000
1100
0210
4/14/34/11
81000
0100
0010
00016
1104/1
0124/3
0014/1
0001
FATORAÇÃO DE CHOLESKY 
 
Enfim, 
 
 
 
 
 
Ou ainda, 
TLDDLA 













 

















































1000
1100
0210
4/14/34/11
9000
0100
0010
0004
9000
0100
0010
0004
1104/1
0124/3
0014/1
0001
TGGA 













 


















9000
1100
0210
1314
9101
0123
0011
0004
FATORAÇÃO DE CHOLESKY 
 
Resolução de sistemas lineares é semelhante 
ao método LU. Seja , então resolver 
 é equivalente a resolver e 
depois . 
 
TGGA 
bxA  byG 
yxGT 
Neste caso não há necessidade de aplicar permutações. 
 
 
 
Substituições direta 
 
Substituições Inversa 
T
T
GG
GG x b
 

G y b
TG x y
5 Nov 2008 . 10:58 
Decompsição de Cholesky 
• Se a matriz A é definida positiva, podemos decompô-la 
unicamente no produto GGt, onde G é uma matriz 
triangular inferior com elementos positivos na diagonal. 
Multiplicando as linhas i pelas colunas i, temos os elementos 
da diagonal da matriz A: 
5 Nov 
Decomposição de Cholesky (diagonal) 
No caso geral: 
... 
i=2,3,... 
Importante! (1) 
5 Nov 2008 . 10:58 
Método de Cholesky (2a coluna) 
multiplicamos as linhas de G (abaixo da diagonal) pela 2a coluna de Gt 
5 Nov 2008 . 10:58 
Método de Cholesky (na coluna) 
multiplicamos as linhas de G (abaixo da diagonal) pela na coluna de Gt 
5 Nov 2008 . 10:58 
Expressão Genérico 
Importante 2! 
Importante! 
Relembrando a fórmula para a diagonal: 
Que devem ser usadas de forma conveniente... 
5 Nov 2008 . 10:58 
"Forma coveniente" 
Expressão (2) 
Expressão (1) 
1) Aplicamos (1) para calcular g11 
2) Aplicamos (2) para calcular g21, g31, ..., gn1 
 
3) Aplicamos (1) para calcular g22 
4) Aplicamos (2) para calcular g32, g42, ..., gn2 
 
... 
5 Nov 2008 . 10:58 
Exemplo 
5 Nov 2008 . 10:58 
Exemplo - resolução 
a) Condições para o método de Cholesky: 
1) A é simétrica: 
 aij = aji OK! 
 
2) A matriz é definida positiva. (Vamos usar a condição de Sylvester: 
todos os menores principais têm determinantes 
positivos): 
 det(A1) = 4>0; det(A2) = 36>0; det(A3) = 36>0 OK! 
 
5 Nov 2008 . 10:58 
Exemplo - resolução 
b) 
 
Aplicamos uma sequência "conveniente": 
 
calculamos: 
1) g11 (1) 
2) g21, g31 (2) 
3) g22 (1) 
4) g32 (2) 
5) g33 (1) 
 
 
 
 
5 Nov 2008 . 10:58 
Exemplo - resolução 
b) 
 
 
 
calculamos: 
1) g11 (1) 
2) g21, g31 (2) 
3) g22 (1) 
4) g32 (2) 
5) g33 (1) 
 
 
 
 
5 Nov 2008 . 10:58 
Observações 
• O método de Cholesky é menos custoso 
computacionalmente que o método de decomposição 
LU 
 
• Precisamos de A definida positiva para garantir que as 
raízes quadradas serão sempre efetuadas sobre 
números positivos (poderíamos também trabalhar com 
aritmética complexa) 
 
• Como vimos no exemplo: det(A) = (g11 .g22 ... gnn )
2 
 
Cholesky: 
Para A positiva, definida e simétrica: 
 A = AT 
 x T A x > 0 para todo x  0, 
podemos escolher 
 
U= LT 
 (ljk = ukj). 
 
A = L LT 
2;,,1
1
,,2
,,2
1
1
11
1
1
1
1
2
1111

















knkj
a
nj
a
nka
a
k
i
kijijk
kk
jk
j
j
j
i
jijjjj
ll
l
l

l
l
ll
l
Decomposição de Cholesky 
 
– Consideremos as diversas partes da matriz 
• 
 
 
 
– Sem pivoteamento e muito estavel numericamente 
 
  N,,1ijLLa
L
1
L
LaL
1i
1k jkikij
ii
ij
211i
1k
2
ikiiii








ALLT 
COMPARAÇÃO DOS MÉTODOS 
 
Fatoração de Cholesky: Primeiro verificar se uma 
matriz simétrica é definida positiva. Em caso positivo, 
continuar com o método de Cholesky; 
 
A decomposição de Cholesky requer multiplicações, isto é, a 
metade das exigidas pela redução de Crout/Doolittle. Os produtos 
internos devem ser acumulados em precisão dupla, para se obter 
exatidão adicional. 
Complexidade da Decomposição de Cholesky 
6
3n
Decomposição de Cholesky 
Definição: Seja A uma matriz de ordem n real e simétrica tal que xTAx>0, 
xRn - {0}, então diz-se que A é positiva definida. 
Teorema: Se A é positiva definida, então A é não singular. 
Corolário: Se A é positiva definida e bRn, então o sistema linear Ax = b 
possui exatamente uma solução. 
Observação: O algoritmo da decomposição de Cholesky é 
incondicionalmente estável pois como A é positiva definida, não há 
necessidade de pivoteamento, pois neste caso ela sempre é 
diagonalmente dominante. 
Como construir de forma simples matrizes positivas 
definidas ? 
Teorema: Seja Mnn uma matriz real e não singular tal que A = M M
T. 
Então A é positiva definida. 
Teorema da Decomposição de Cholesky: Seja A uma matriz positiva 
definida. Então A pode ser decomposta, de modo único, na forma A = 
G GT, onde G é uma matriz triangular inferior com coeficientes 
positivos ao longo da diagonal principal. Esta decomposição é 
denominada decomposição de Cholesky e nos referimos a G como o 
fator Cholesky de A. 
Corolário: A é uma matriz positiva definida se e somente se existe uma 
matriz triangular inferior G com coeficientes positivos na diagonal 
principal tal que A = G GT. 
• Definição 
• Se A é uma matriz n x n, então um vetor não-nulo x em Rn é chamado 
um autovetor de A se A x é um múltiplo escalar de x, ou seja, 
 A x = l x 
 para algum escalar l . O escalar l é chamado um autovalor de A e 
dizemos que x é um autovetor associado a l . 
10  l
l x 
x 
x 
l x 
1l
x 
xl
01  l
xl
x
1l
Exemplo: 
• O vetor é um autovetor de 
 
 correspondendo ao autovalor 
 
 pois 
xx 3
2
1
3
6
3
2
1
18
03

























A








18
03
A







2
1
x
3l
•Autovalor (eigenvalue, valor característico): 
é um número (real ou complexo) l tal que a equação 
 A x = l x 
tem solução não trivial x  0 
 x é um autovetor (eigenvector). 
•O conjunto de autovalores de A é chamado de o espectro de A. 
 (A - l I)x= 0 
•Só existe solução não trivial se det | A - l I| = 0. 
 
•Matrizes similares têm os mesmos autovalores. 
 
D é similar a A 
se existe uma 
matriz T tal que 
D = T-1 A T 
Como construir de forma simples matrizes positivas 
definidas ? 
•Desvio espectral: se A tem o conjunto de 
autovalores l1 , l2 , l3 ..... , então A - k I terá 
como autovalores l1 - k , l2 - k , l3 - k ..... 
 
•O maior valor absoluto do conjunto {l} é chamado 
de raio espectral de A. 
 
•Os autovalores são as raízes da equação característica 
 det | A - l I| = 0 
•A soma dos autovalores é chamado de traço de A. 
 
 traço A 

l
n
j
j
n
j
jja
11
• Pode ser mostrado que se A é uma matriz n x n, então o polinômio 
característico de A tem grau n e o coeficiente de é 1, ou seja, 
o polinômio característico p(x) de uma matriz n x n é da forma 
 
 
• Pelo teorema fundamental da Álgebra segue que a equação 
característica 
 
 tem, no máximo, n soluções distintas, de modo que uma matriz n x n 
tem, no máximo, n autovalores distintos. 
 
 
n
nn ccAIp   ...)(det)( 11llll
nl
0...11 

n
nn cc ll
Exemplo: autovalores de uma matriz 3 x 3 
• Encontrar os autovalores de 
 
• Solução: 
• O polinômio característico de A é 
 
 
 
 
• Os autovalores de A, satisfazem a equação 
 
 
4178
8174
10
01
det)det( 23 













 lll
l
l
l
l AI












8174
100
010
A
04178 23  lll
• Para resolver a equação 
 
• Começa-se procurando soluções inteiras. Essa tarefa pode ser 
simplificada se lembrarmos que todas as soluções inteiras (se houverem) 
de uma equação polinomial 
 
 com coeficientes inteiros são divisores do termo constante . 
• Assim, as únicas possíveis soluções inteiras são os divisores de -4, ou 
seja, 
• Substituindo sucessivamente cada um destes valores mostra que 
 é uma solução inteira. Consequentemente, pode se escrever 
 
 e as demais soluções satisfazem a equação quadrática 
 Assim, os autovalores de A são 
4l
4,3,2,1 
04178 23  lll
0...11 

n
nn cc ll
nc
  0)14(4 2  lll
0142  ll
32,32,4  lll
Exemplo: Autovalores de uma matriz triangular superior 
• Encontrar os autovalores da matriz triangular superior 
 
 
• Solução: 
• Lembrando que o determinante de uma matriz triangular superior é o 
produto das entradas na diagonal principal obtemos 
 
 
 
 
 
 
• Assim a equação característica é 
 
• E os autovalores 
)()()()(
000
00
0
det)det(
44332211
44
3433
242322
14131211
aaaa
a
aa
aaa
aaaa
AI


















llll
l
l
l
l
l
44332211 ,,, aaaa  llll













44
3433
242322
14131211
000
00
0
a
aa
aaa
aaaa
A
0)()()()( 44332211  aaaa llll
• Teorema 7.1.1 
• Se A é uma matriz n x n triangular (superior, inferior ou diagonal), então 
os autovalores de A são as entradas na diagonal principal de A 
 
• Exemplo: Autovalores de uma matriz triangular inferior 
 
• Por inspeção, os autovalores da matriz triangular inferior 
 
 
 
 são 
4/13/2,2/1  lll e












4185
0321
0021
A
Observação: muitas vezes, em problemas aplicados, a matriz A é tão grande 
que não é prático calcular a equação característica. Nesse caso, existem 
Métodos de aproximação que podem ser usados para a obtenção dos 
autovalores.