slides5_04_cholesky

Prévia do material em texto

Decomposic¸a˜o de Cholesky
Eduardo Campos dos Santos
UFMG
3 de abril de 2018
Decomposic¸a˜o de Cholesky
Me´todos de soluc¸a˜o de sistemas lineares
Motivac¸a˜o
Em alguns problemas de engenharia e estat´ıstica, que resultam na
modelagem de um sistema de equac¸o˜es, a matriz dos coeficientes e´
sime´trica, isto e´, ela e´ igual a` sua transposta (A = AT ). Ale´m
disso, muitas das matrizes que surgem em engenharia, sa˜o de uma
classe denominada definida positiva (ou positiva definida). Para
esses casos, podemos usar uma versa˜o simplificada da
decomposic¸a˜o LU, que consiste em fatorar a matriz dos
coeficientes reescrevendo-a como o produto de uma matriz
triangular e sua transposta. O esforc¸o computacional cai por algo
pro´ximo da metade, ou ate´ mais, daquele necessa´rio para a
decomposic¸a˜o LU. Essa e´ a chamada decomposic¸a˜o de Cholesky,
representada por A = LLT , onde L e´ uma matriz triangular inferior.
Decomposic¸a˜o de Cholesky
Me´todos de soluc¸a˜o de sistemas lineares
Motivac¸a˜o
Func¸o˜es definidas positivas sa˜o caracterizadas por matrizes
definidas positivas e sa˜o muito comuns em problemas de
otimizac¸a˜o que lidam com a determinac¸a˜o de um ponto m´ınimo.
Decomposic¸a˜o de Cholesky
Me´todos de soluc¸a˜o de sistemas lineares
Atenc¸a˜o
A matriz L da decomposic¸a˜o de Cholesky nada tem a ver com a
matriz L da decomposic¸a˜o LU. No caso da decomposic¸a˜o de
Cholesky, os elementos da diagonal principal de L (e, portanto, de
LT ), na˜o sa˜o todos iguais a 1, como acontece na matriz L da
decomposic¸a˜o LU.
Na decomposic¸a˜o de Cholesky, os elementos de L sa˜o todos
calculados facilmente aplicando-se fo´rmulas iterativas, sem
necessidade de calcular e aplicar multiplicadores.
Decomposic¸a˜o de Cholesky
Me´todos de soluc¸a˜o de sistemas lineares
A ideia
Seja A = LLT

a11 a12 a13 . . . a1n
a21 a22 a23 . . . a2n
a31 a32 a33 . . . a2n
. . . . . . . . .
. . .
.
.
.
an1 an2 an3 . . . ann
 =

l11 0 0 ... 0
l21 l22 0 ... 0
l31 l32 l33 ... 0
. . . . . . . . .
. . . 0
ln1 ln2 ln3 ... lnn


l11 l21 l31 ... ln1
0 l22 l32 ... ln2
0 0 l33 ... ln3
0 0 0
. . .
.
.
.
0 0 0 ... lnn

Decomposic¸a˜o de Cholesky
Me´todos de soluc¸a˜o de sistemas lineares
A ideia
Seja A = LLT

a11 a12 a13 . . . a1n
a21 a22 a23 . . . a2n
a31 a32 a33 . . . a2n
. . . . . . . . .
. . .
.
.
.
an1 an2 an3 . . . ann
 =

l11 0 0 ... 0
l21 l22 0 ... 0
l31 l32 l33 ... 0
. . . . . . . . .
. . . 0
ln1 ln2 ln3 ... lnn


l11 l21 l31 ... ln1
0 l22 l32 ... ln2
0 0 l33 ... ln3
0 0 0
. . .
.
.
.
0 0 0 ... lnn

a11 = l211 ⇒ l11 =
√
a11
Decomposic¸a˜o de Cholesky
Me´todos de soluc¸a˜o de sistemas lineares
A ideia
Seja A = LLT

a11 a12 a13 . . . a1n
a21 a22 a23 . . . a2n
a31 a32 a33 . . . a2n
. . . . . . . . .
. . .
.
.
.
an1 an2 an3 . . . ann
 =

l11 0 0 ... 0
l21 l22 0 ... 0
l31 l32 l33 ... 0
. . . . . . . . .
. . . 0
ln1 ln2 ln3 ... lnn


l11 l21 l31 ... ln1
0 l22 l32 ... ln2
0 0 l33 ... ln3
0 0 0
. . .
.
.
.
0 0 0 ... lnn

a21 = l21 l11 ⇒ l21 = a21
l11
Decomposic¸a˜o de Cholesky
Me´todos de soluc¸a˜o de sistemas lineares
A ideia
Seja A = LLT

a11 a12 a13 . . . a1n
a21 a22 a23 . . . a2n
a31 a32 a33 . . . a2n
. . . . . . . . .
. . .
.
.
.
an1 an2 an3 . . . ann
 =

l11 0 0 ... 0
l21 l22 0 ... 0
l31 l32 l33 ... 0
. . . . . . . . .
. . . 0
ln1 ln2 ln3 ... lnn


l11 l21 l31 ... ln1
0 l22 l32 ... ln2
0 0 l33 ... ln3
0 0 0
. . .
.
.
.
0 0 0 ... lnn

a31 = l31 l11 ⇒ l31 = a31
l11
Decomposic¸a˜o de Cholesky
Me´todos de soluc¸a˜o de sistemas lineares
A ideia
Seja A = LLT

a11 a12 a13 . . . a1n
a21 a22 a23 . . . a2n
a31 a32 a33 . . . a2n
. . . . . . . . .
. . .
.
.
.
an1 an2 an3 . . . ann
 =

l11 0 0 ... 0
l21 l22 0 ... 0
l31 l32 l33 ... 0
. . . . . . . . .
. . . 0
ln1 ln2 ln3 ... lnn


l11 l21 l31 ... ln1
0 l22 l32 ... ln2
0 0 l33 ... ln3
0 0 0
. . .
.
.
.
0 0 0 ... lnn

a22 = l
2
21 + l
2
22 ⇒ l22 =
√
a22 − l221
Decomposic¸a˜o de Cholesky
Me´todos de soluc¸a˜o de sistemas lineares
A ideia
Seja A = LLT

a11 a12 a13 . . . a1n
a21 a22 a23 . . . a2n
a31 a32 a33 . . . a2n
. . . . . . . . .
. . .
.
.
.
an1 an2 an3 . . . ann
 =

l11 0 0 ... 0
l21 l22 0 ... 0
l31 l32 l33 ... 0
. . . . . . . . .
. . . 0
ln1 ln2 ln3 ... lnn


l11 l21 l31 ... ln1
0 l22 l32 ... ln2
0 0 l33 ... ln3
0 0 0
. . .
.
.
.
0 0 0 ... lnn

a32 = l31 l21 + l32 l22 ⇒ l32 = a32 − l31 l21
l22
Decomposic¸a˜o de Cholesky: Os fatores de L
A = LLT

a11 a12 a13 . . . a1n
a21 a22 a23 . . . a2n
a31 a32 a33 . . . a2n
. . . . . . . . .
. . .
.
.
.
an1 an2 an3 . . . ann
 =

l11 0 0 ... 0
l21 l22 0 ... 0
l31 l32 l33 ... 0
. . . . . . . . .
. . . 0
ln1 ln2 ln3 ... lnn


l11 l21 l31 ... ln1
0 l22 l32 ... ln2
0 0 l33 ... ln3
0 0 0
. . .
.
.
.
0 0 0 ... lnn

Logo,
l11 =
√
a11
li1 =
ai1
l11
, i = 2, 3, ..., n
lii =
√√√√(aii − i−1∑
k=1
l2ik) , i = 2, 3, ..., n
lij =
(aij −
∑j−1
k=1 lik ljk)
ljj
, 2 ≤ j < i .
Decomposic¸a˜o de Cholesky
Me´todos de soluc¸a˜o de sistemas lineares
Restric¸o˜es
Vemos, portanto, que os elementos de L sa˜o calculados mediante
um processo iterativo que envolve fo´rmulas com ca´lculos de ra´ızes
quadradas. Um erro ocorrera´ se uma dessas operac¸o˜es resultar no
ca´lculo da raiz de um nu´mero negativo. Ale´m disso, os elementos
da diagonal devem ser todos diferentes de zero, uma vez que
aparecem no denominador em algumas fo´rmulas. Essas restric¸o˜es
sera˜o satisfeitas se a matriz A original for definida positiva.
Decomposic¸a˜o de Cholesky: Os fatores de L
A = LLT

a11 a12 a13 . . . a1n
a21 a22 a23 . . . a2n
a31 a32 a33 . . . a3n
. . . . . . . . .
. . .
.
.
.
an1 an2 an3 . . . ann
 =

l11 0 0 ... 0
l21 l22 0 ... 0
l31 l32 l33 ... 0
. . . . . . . . .
. . . 0
ln1 ln2 ln3 ... lnn


l11 l21 l31 ... ln1
0 l22 l32 ... ln2
0 0 l33 ... ln3
0 0 0
. . .
.
.
.
0 0 0 ... lnn

Um algoritmo simples para determinar a fatorac¸a˜o de Cholesky:
1. calculamos l11
2. calculamos os outros elementos da primeira coluna l21, l31, ..., ln1
3. calculamos l22
4. calculamos os outros elementos da segunda coluna l32, l42, ..., ln2
5. calculamos l33
6. calculamos os outros elementos da segunda coluna l43, l53, ..., ln3
Tente propor outro algoritmo que realize algumas operac¸o˜es paralelas.
Obs.: o padra˜o para o ca´lculo dos elementos da diagonal de L

a11 a12 a13 . . . a1n
a21 a22 a23 . . . a2n
a31 a32 a33 . . . a2n
. . . . . . . . .
. . .
.
.
.
an1 an2 an3 . . . ann
 =

l11 0 0 ... 0
l21 l22 0 ... 0
l31 l32 l33 ... 0
. . . . . . . . .
. . . 0
ln1 ln2 ln3 ... lnn


l11 l21 l31 ... ln1
0 l22 l32 ... ln2
0 0 l33 ... ln3
0 0 0
. . .
.
.
.
0 0 0 ... lnn

No ca´lculo de cada elemento da diagonal principal de L aparece a subtrac¸a˜o do
quadrado de cada elemento da mesma linha e a` esquerda do que esta´ sendo calculado.
a11 = l211 ⇒ l11 =
√
a11
a22 = l221 + l
2
22 ⇒ l22 =
√
a22 − l221
a33 = l231 + l
2
32+ l
2
33 ⇒ l33 =
√
a33 − l231 − l232
a44 = l241 + l
2
42 + l
2
43 + l
2
44 ⇒ l44 =
√
a44 − l241 − l242 − l243
Decomposic¸a˜o de Cholesky
Me´todos de soluc¸a˜o de sistemas lineares
Sumarizando
Podemos usar uma versa˜o simplificada da decomposic¸a˜o LU
quando a matriz A for definida positiva.
Uma matriz sime´trica e´ dita definida positiva quando:
vTAv > 0 ∀ v 6= 0
Decomposic¸a˜o de Cholesky
Me´todos de soluc¸a˜o de sistemas lineares
Teorema de Cholesky
Se A for uma matriz sime´trica e definida positiva, enta˜o, existe
uma u´nica matriz triangular L com elementos da diagonal positivos
tal que A = LLT .
Observac¸a˜o: Se a decomposic¸a˜o de Cholesky for poss´ıvel para
uma determinada matriz A, enta˜o A e´, certamente, sime´trica e
definida positiva.
Um ponto atrativo
Devido a` estabilidade nume´rica da decomposic¸a˜o de uma matriz
sime´trica definida positiva, na˜o se faz necessa´rio o uso da
pivotac¸a˜o parcial na decomposic¸a˜o de Cholesky.
Frederico Campos [1]
Decomposic¸a˜o de Cholesky
Me´todos de soluc¸a˜o de sistemas lineares
Em s´ıntese
Se a matriz A for sime´trica e definida positiva, podemos resolver o
sistema linear com uma transformac¸a˜o similar a`quela usada na
decomposic¸a˜o LU e so´ precisamos basicamente calcular os
elementos de uma matriz triangular, uma vez que a outra e´ a
transposta da primeira.
Ax = b → LLT x = b → Ly = b, onde LT x = y
Mas como determinar se uma matriz sime´trica e´ definida positiva?
Decomposic¸a˜o de Cholesky
Me´todos de soluc¸a˜o de sistemas lineares
Crite´rios (na˜o suficientes) para determinar se uma matriz e´
definida positiva
Teorema: Se A e´ uma matriz definida positiva n x n, enta˜o:
I aii > 0, para cada i = 1, 2, 3, . . . , n;
I (aij)2 < aiiajj , para cada i 6= j .
Decomposic¸a˜o de Cholesky
Me´todos de soluc¸a˜o de sistemas lineares
Crite´rios (na˜o suficientes) para determinar se uma matriz e´
definida positiva
Teorema: Se A e´ uma matriz definida positiva n x n, enta˜o:
I aii > 0, para cada i = 1, 2, 3, . . . , n;
I (aij)2 < aiiajj , para cada i 6= j .

a11 a12 a13 ... a1n
a21 a22 a23 ... a2n
a31 a32 a33 ... a2n
. . . ... .
an1 an2 an3 ... ann

Decomposic¸a˜o de Cholesky
Me´todos de soluc¸a˜o de sistemas lineares
Crite´rios (na˜o suficientes) para determinar se uma matriz e´
definida positiva
Teorema: Se A e´ uma matriz definida positiva n x n, enta˜o:
I aii > 0, para cada i = 1, 2, 3, . . . , n;
I (aij)2 < aiiajj , para cada i 6= j .

a11 a12 a13 ... a1n
a21 a22 a23 ... a2n
a31 a32 a33 ... a2n
. . . ... .
an1 an2 an3 ... ann


a11 a12 a13 ... a1n
a21 a22 a23 ... a2n
a31 a32 a33 ... a2n
. . . ... .
an1 an2 an3 ... ann

Decomposic¸a˜o de Cholesky
Me´todos de soluc¸a˜o de sistemas lineares
Crite´rios suficientes para determinar se uma matriz e´ definida
positiva
Teorema: Uma matriz sime´trica Anxn e´ definida positiva, se, e
somente se:
I todos os seus menores principais l´ıderes sa˜o positivos
(crite´rio de Sylvester), ou seja, cada uma de suas submatrizes
principais tem determinante positivo;
I seus autovalores sa˜o todos reais e positivos;
I o processo de eliminac¸a˜o de Gauss pode ser realizado sem
permutac¸a˜o de linhas ou colunas com todos os elementos
pivoˆs positivos.
Basta verificar se a matriz A satisfaz a qualquer um desses crite´rios.
Crite´rios suficientes para determinar se uma matriz e´ definida
positiva
Menores principais l´ıderes positivos.
Seja:
A =

a11 a12 a13 ... a1n
a21 a22 a23 ... a2n
a31 a32 a33 ... a3n
. . . ... .
an1 an2 an3 ... ann

∣∣∣∣ a11 a12a21 a22
∣∣∣∣ > 0
∣∣∣∣∣∣
a11 a12 a13
a21 a22 a23
a31 a32 a33
∣∣∣∣∣∣ > 0
∣∣∣∣∣∣∣∣∣
a11 a12 a13 ... a1k
a21 a22 a23 ... a2k
a31 a32 a33 ... a3k
. . . ... .
ak1 ak2 ak3 ... akk
∣∣∣∣∣∣∣∣∣ > 0
ok, mas trabalhoso.
Crite´rios suficientes para determinar se uma matriz e´ definida
positiva
Todos os autovalores sa˜o reais e positivos.
Determinamos os autovalores calculando det[A− λI ] = 0∣∣∣∣∣∣∣∣∣∣
a11 − λ a12 a13 ... a1n
a21 a22 − λ a23 ... a2n
a31 a32 a33 − λ ... a3n
. . . ... .
an1 an2 an3 ... ann − λ
∣∣∣∣∣∣∣∣∣∣
= 0
ok, mas trabalhoso.
Crite´rios suficientes para determinar se uma matriz e´ definida
positiva
O paradigma do ovo e da galinha.
Devemos determinar se A e´ sime´trica e definida positiva para saber
se e´ poss´ıvel fatoriza´-la por Cholesky. Mas o usual e´: aplica-se o
algoritmo de decomposic¸a˜o de Cholesky – se ele funcionar, enta˜o a
matriz e´ sime´trica e definida positiva. Funcionar, nesse caso,
significa: obtermos uma matriz triangular inferior L com todos os
elementos reais, todos os elementos da diagonal principal positivos
e tal que A = LLT .
Exerc´ıcios
Usando os crite´rios apresentados, identifique as matrizes que
podem ser fatoradas pelo me´todo de Cholesky.
4 −4 2 8
−4 5 −7 −10
2 −7 42 18
8 −10 18 −46


4 −4 3 8
−4 5 −7 −10
2 −7 42 18
8 −10 18 46


4 −4 2 8
−4 5 7 −10
2 −7 42 −18
8 −10 18 46


4 −4 2 8
−4 5 −7 −10
2 −7 6 18
8 −10 18 46


4 −4 2 8
−4 5 7 −1
2 7 10 2
8 −1 2 6


4 −4 2 8
−4 5 −7 −10
2 −7 42 18
8 −10 18 46

Exerc´ıcios
Usando os crite´rios apresentados, identifique as matrizes que
podem ser fatoradas pelo me´todo de Cholesky.
4 −4 2 8
−4 5 −7 −10
2 −7 42 18
8 −10 18 −46


4 −4 3 8
−4 5 −7 −10
2 −7 42 18
8 −10 18 46


4 −4 2 8
−4 5 7 −10
2 −7 42 −18
8 −10 18 46


4 −4 2 8
−4 5 −7 −10
2 −7 6 18
8 −10 18 46


4 −4 2 8
−4 5 7 −1
2 7 10 2
8 −1 2 6


4 −4 2 8
−4 5 −7 −10
2 −7 42 18
8 −10 18 46

Exerc´ıcios
Usando os crite´rios apresentados, identifique as matrizes que
podem ser fatoradas pelo me´todo de Cholesky.

4 −4 2 8
−4 5 −7 −10
2 −7 42 18
8 −10 18 46

Com uma breve inspec¸a˜o
visual, notamos que:
I aii > 0, para cada
i = 1, 2, 3, . . . , n;
I (aij)2 < aiiajj , para
cada i 6= j .
Exerc´ıcios
Usando os crite´rios apresentados, identifique as matrizes que
podem ser fatoradas pelo me´todo de Cholesky.
Verificando se os determinantes das submatrizes sa˜o todos positivos:∣∣∣∣ 4 −4−4 5
∣∣∣∣ = (4× 5)− (4× 4) = 4 > 0∣∣∣∣∣∣
4 −4 2
−4 5 −7
2 −7 42
∣∣∣∣∣∣
= [4×5×42]+2×[(−4)×(−7)×2]−[2×5×2]−[(−4)×(−4)×42]−[(−7)×(−7)×4]
= 64 > 0 ∣∣∣∣∣∣∣∣
4 −4 2 8
−4 5 −7 −10
2 −7 42 18
8 −10 18 46
∣∣∣∣∣∣∣∣ = 1600 > 0
Observac¸o˜es
I O me´todo de Cholesky e´ menos custoso computacionalmente
que o me´todo de decomposic¸a˜o LU
I A matriz A deve ser definida positiva para garantir que as
ra´ızes quadradas sera˜o sempre efetuadas sobre nu´meros
positivos
I Como A = LLT , temos: det(A) = det(L)× det(LT )
Assim: det(A) = (
∏
lii )
2
Exerc´ıcio proposto 1
Desenvolvimento das fo´rmulas
Considere uma matriz A4x4 sime´trica e definida positiva e a
decomposic¸a˜o de Cholesky para essa matriz conforme representada
abaixo. Demostre a relac¸a˜o entre os elementos de A e de L
simplesmente aplicando as multiplicac¸o˜es entre as respectivas
linhas e colunas. Depois, reescreva as expresso˜es de modo a
demonstrar como os elementos de L podem ser obtidos
iterativamente.
A = LLT

a11 a21 a31 a41
a21 a22 a32 a42
a31 a32 a33 a43
a41 a42 a43 a44
 =

l11 0 0 0
l21 l22 0 0
l31 l32 l33 0
l41 l42 l43 l44


l11 l21 l31 l41
0 l22 l32 l42
0 0 l33 l43
0 0 0 l44

Exerc´ıcio resolvido (baseado nos slides dos professores Mana´ıra e Lo¨ıc [2])
Sugesta˜o: Identifique os termos da fo´rmula no dispositivo pra´tico para compreender como
eles aparecem em cada caso
Obtenha a decomposic¸a˜o de Cholesky para a matriz A abaixoe
determine seu determinante a partir dos elementos da diagonal de
L.
A =

4 −4 2 8
−4 5 −7 −10
2 −7 42 18
8 −10 18 46

Exerc´ıcio resolvido
Sugesta˜o: Identifique os termos da fo´rmula no dispositivo pra´tico para compreender como
eles aparecem em cada caso
i/j 1 2 3 4 i/j 1 2 3 4
1 4 1
2 -4 5 2
3 2 -7 42 3
4 8 -10 18 46 4
Exerc´ıcio resolvido
Sugesta˜o: Identifique os termos da fo´rmula no dispositivo pra´tico para compreender como
eles aparecem em cada caso
i/j 1 2 3 4 i/j 1 2 3 4
1 4 1
√
4
2 -4 5 2
3 2 -7 42 3
4 8 -10 18 46 4
l11 =
√
a11
Exerc´ıcio resolvido
Sugesta˜o: Identifique os termos da fo´rmula no dispositivo pra´tico para compreender como
eles aparecem em cada caso
i/j 1 2 3 4 i/j 1 2 3 4
1 4 1 2
2 -4 5 2
3 2 -7 42 3
4 8 -10 18 46 4
Exerc´ıcios
Sugesta˜o: Identifique os termos da fo´rmula no dispositivo pra´tico para compreender como
eles aparecem em cada caso
i/j 1 2 3 4 i/j 1 2 3 4
1 4 1 2
2 -4 5 2 −42
3 2 -7 42 3
4 8 -10 18 46 4
l21 =
a21
l11
Exerc´ıcio resolvido
Sugesta˜o: Identifique os termos da fo´rmula no dispositivo pra´tico para compreender como
eles aparecem em cada caso
i/j 1 2 3 4 i/j 1 2 3 4
1 4 1 2
2 -4 5 2 -2
3 2 -7 42 3
4 8 -10 18 46 4
Exerc´ıcio resolvido
Sugesta˜o: Identifique os termos da fo´rmula no dispositivo pra´tico para compreender como
eles aparecem em cada caso
i/j 1 2 3 4 i/j 1 2 3 4
1 4 1 2
2 -4 5 2 -2
3 2 -7 42 3 22
4 8 -10 18 46 4
l31 =
a31
l11
Exerc´ıcio resolvido
Sugesta˜o: Identifique os termos da fo´rmula no dispositivo pra´tico para compreender como
eles aparecem em cada caso
i/j 1 2 3 4 i/j 1 2 3 4
1 4 1 2
2 -4 5 2 -2
3 2 -7 42 3 1
4 8 -10 18 46 4
Exerc´ıcio resolvido
Sugesta˜o: Identifique os termos da fo´rmula no dispositivo pra´tico para compreender como
eles aparecem em cada caso
i/j 1 2 3 4 i/j 1 2 3 4
1 4 1 2
2 -4 5 2 -2
3 2 -7 42 3 1
4 8 -10 18 46 4 82
l41 =
a41
l11
Exerc´ıcio resolvido
Sugesta˜o: Identifique os termos da fo´rmula no dispositivo pra´tico para compreender como
eles aparecem em cada caso
i/j 1 2 3 4 i/j 1 2 3 4
1 4 1 2
2 -4 5 2 -2
3 2 -7 42 3 1
4 8 -10 18 46 4 4
Exerc´ıcio resolvido
Sugesta˜o: Identifique os termos da fo´rmula no dispositivo pra´tico para compreender como
eles aparecem em cada caso
i/j 1 2 3 4 i/j 1 2 3 4
1 4 1 2
2 -4 5 2 -2
√
5− (−2)2
3 2 -7 42 3 1
4 8 -10 18 46 4 4
l22 =
√
(a22 −
∑2−1
k=1 l
2
2k)
l22 =
√
(a22 − l221)
Exerc´ıcio resolvido
Sugesta˜o: Identifique os termos da fo´rmula no dispositivo pra´tico para compreender como
eles aparecem em cada caso
i/j 1 2 3 4 i/j 1 2 3 4
1 4 1 2
2 -4 5 2 -2 1
3 2 -7 42 3 1
4 8 -10 18 46 4 4
Exerc´ıcio resolvido
Sugesta˜o: Identifique os termos da fo´rmula no dispositivo pra´tico para compreender como
eles aparecem em cada caso
i/j 1 2 3 4 i/j 1 2 3 4
1 4 1 2
2 -4 5 2 -2 1
3 2 -7 42 3 1 −7−(1)(−2)1
4 8 -10 18 46 4 4
l32 =
(a32 −
∑2−1
k=1 l3k l2k)
l22
l32 =
(a32 − l31l21)
l22
Exerc´ıcio resolvido
Sugesta˜o: Identifique os termos da fo´rmula no dispositivo pra´tico para compreender como
eles aparecem em cada caso
i/j 1 2 3 4 i/j 1 2 3 4
1 4 1 2
2 -4 5 2 -2 1
3 2 -7 42 3 1 -5
4 8 -10 18 46 4 4
Exerc´ıcio resolvido
Sugesta˜o: Identifique os termos da fo´rmula no dispositivo pra´tico para compreender como
eles aparecem em cada caso
i/j 1 2 3 4 i/j 1 2 3 4
1 4 1 2
2 -4 5 2 -2 1
3 2 -7 42 3 1 -5
4 8 -10 18 46 4 4 −10−(4)(−2)1
l42 =
(a42 −
∑2−1
k=1 l4k l2k)
l22
l42 =
(a42 − l41l21)
l22
Exerc´ıcio resolvido
Sugesta˜o: Identifique os termos da fo´rmula no dispositivo pra´tico para compreender como
eles aparecem em cada caso
i/j 1 2 3 4 i/j 1 2 3 4
1 4 1 2
2 -4 5 2 -2 1
3 2 -7 42 3 1 -5
4 8 -10 18 46 4 4 -2
Exerc´ıcio resolvido
Sugesta˜o: Identifique os termos da fo´rmula no dispositivo pra´tico para compreender como
eles aparecem em cada caso
i/j 1 2 3 4 i/j 1 2 3 4
1 4 1 2
2 -4 5 2 -2 1
3 2 -7 42 3 1 -5
√
42− 12 − (−5)2
4 8 -10 18 46 4 4 -2
l33 =
√
(a33 −
∑3−1
k=1 l
2
3k)
l33 =
√
(a33 − l231 − l232)
Exerc´ıcio resolvido
Sugesta˜o: Identifique os termos da fo´rmula no dispositivo pra´tico para compreender como
eles aparecem em cada caso
i/j 1 2 3 4 i/j 1 2 3 4
1 4 1 2
2 -4 5 2 -2 1
3 2 -7 42 3 1 -5 4
4 8 -10 18 46 4 4 -2
Exerc´ıcio resolvido
Sugesta˜o: Identifique os termos da fo´rmula no dispositivo pra´tico para compreender como
eles aparecem em cada caso
i/j 1 2 3 4 i/j 1 2 3 4
1 4 1 2
2 -4 5 2 -2 1
3 2 -7 42 3 1 -5 4
4 8 -10 18 46 4 4 -2 18−(4)(1)−(−2)(−5)4
l43 =
(a43 −
∑3−1
k=1 l4k l3k)
l33
l43 =
(a43 − l41l31 − l42l32)
l33
Exerc´ıcio resolvido
Sugesta˜o: Identifique os termos da fo´rmula no dispositivo pra´tico para compreender como
eles aparecem em cada caso
i/j 1 2 3 4 i/j 1 2 3 4
1 4 1 2
2 -4 5 2 -2 1
3 2 -7 42 3 1 -5 4
4 8 -10 18 46 4 4 -2 1
Exerc´ıcio resolvido
Sugesta˜o: Identifique os termos da fo´rmula no dispositivo pra´tico para compreender como
eles aparecem em cada caso
i/j 1 2 3 4 i/j 1 2 3 4
1 4 1 2
2 -4 5 2 -2 1
3 2 -7 42 3 1 -5 4
4 8 -10 18 46 4 4 -2 1
√
46− 42 − (−2)2 − 12
l44 =
√
(a44 −
∑4−1
k=1 l
2
4k)
l44 =
√
(a44 − l241 − l242 − l243)
Exerc´ıcio resolvido
Sugesta˜o: Identifique os termos da fo´rmula no dispositivo pra´tico para compreender como
eles aparecem em cada caso
i/j 1 2 3 4 i/j 1 2 3 4
1 4 1 2
2 -4 5 2 -2 1
3 2 -7 42 3 1 -5 4
4 8 -10 18 46 4 4 -2 1 5
Exerc´ıcio resolvido
Sugesta˜o: Identifique os termos da fo´rmula no dispositivo pra´tico para compreender como
eles aparecem em cada caso
i/j 1 2 3 4 i/j 1 2 3 4
1 4 1 2
2 -4 5 2 -2 1
3 2 -7 42 3 1 -5 4
4 8 -10 18 46 4 4 -2 1 5
L =

2 0 0 0
−2 1 0 0
1 −5 4 0
4 −2 1 5

Exerc´ıcio resolvido
Sugesta˜o: Identifique os termos da fo´rmula no dispositivo pra´tico para compreender como
eles aparecem em cada caso
i/j 1 2 3 4 i/j 1 2 3 4
1 4 1 2
2 -4 5 2 -2 1
3 2 -7 42 3 1 -5 4
4 8 -10 18 46 4 4 -2 1 5
L =

2 0 0 0
−2 1 0 0
1 −5 4 0
4 −2 1 5

A = LLT , temos: det(A) = det(L)× det(LT )
Assim: det(A) = (
∏
lii )
2 =⇒ (2× 1× 4× 5)2 = 1600
Exerc´ıcio proposto 2 (baseado nos slides dos professores Mana´ıra e Lo¨ıc [2])
Decomposic¸a˜o de Cholesky
Obtenha a decomposic¸a˜o de Cholesky para a matriz A abaixo e
determine seu determinante a partir dos elementos da diagonal de
L. Use treˆs casas decimais.
A =

4 2 1 1
2 9 12 −16
1 12 37 −43
1 −16 −43 98

Exerc´ıcio proposto 3 (baseado nos slides dos professores Mana´ıra e Lo¨ıc [2])
Ca´lculo de inversa de uma matriz
Utilizando a decomposic¸a˜o de Cholesky para a matriz A do
exemplo anterior, determine a inversa dessa matriz. Use treˆs casas
decimais.
Refereˆncias bibliogra´ficas
[1] Frederico Campos. Algoritmos Nume´ricos. LTC
[2] Mana´ıra Lima e Lo¨ıc Cerf Dispon´ıvel em:
http://homepages.dcc.ufmg.br/ lcerf/slides/cn112ae4.pdf. Acessado em: 07 de
setembro de 2013.