aula11 sistemas

Prévia do material em texto

Ca´lculo Nume´rico
Resoluc¸a˜o de Sistemas de Equac¸o˜es Lineares
Heder S. Bernardino
Heder S. Bernardino Ca´lculo Nume´rico
Suma´rio
1 Aula Anterior
2 Decomposic¸a˜o LU com Pivotamento
3 Decomposic¸a˜o de Cholesky
4 Decomposic¸a˜o LDLT
5 Revisa˜o
Heder S. Bernardino Ca´lculo Nume´rico
Aula Anterior
Aula Anterior
Heder S. Bernardino Ca´lculo Nume´rico
Aula Anterior
Aula Anterior
◮ Eliminac¸a˜o de Gauss
◮ Transforma o sistema linear num sistema equivalente com matriz de
coeficientes triangular superior
◮ Resolve o sistema equivalente utilizando substituic¸o˜es retroativas
◮ Eliminac¸a˜o de Gauss com estrate´gias de pivotamento
◮ Evita que o pivoˆ seja nulo e evita efeitos nume´ricos
Heder S. Bernardino Ca´lculo Nume´rico
Aula Anterior
Aula Anterior
◮ Decomposic¸a˜o LU
◮ A matriz de coeficientes e´ decomposta em L e U
◮ L e´ uma matriz triangular inferior com elementos da diagonal principal
unita´rios
◮ U e´ uma matriz triangular superior
◮ Substituindo A por LU enta˜o a soluc¸a˜o pode ser obtida resolvendo
dois sistemas triangulares
◮ Ly = b
◮ Ux = y
◮ A decomposic¸a˜o na˜o envolve o vetor b
Heder S. Bernardino Ca´lculo Nume´rico
Decomposic¸a˜o LU com Pivotamento
Decomposic¸a˜o LU com Pivotamento
Heder S. Bernardino Ca´lculo Nume´rico
Decomposic¸a˜o LU com Pivotamento
Decomposic¸a˜o LU com Pivotamento
◮ Assim como na Eliminac¸a˜o de Gauss, alguns problemas podem ser
evitados ao utilizar estrate´gias de pivotamento na Decomposic¸a˜o LU
◮ A estrate´gia de pivotamento parcial sera´ vista aqui
◮ O vetor de constantes b na˜o participa do processo de decomposic¸a˜o
◮ As trocas das linhas devem ser aplicadas a ele quando o sistema
triangular estiver sendo resolvido
◮ Matriz de permutac¸a˜o
◮ Vetor de trocas – mais adequado computacionalmente
Heder S. Bernardino Ca´lculo Nume´rico
Decomposic¸a˜o LU com Pivotamento
Decomposic¸a˜o LU com Pivotamento
◮ Definic¸a˜o (Matriz de Permutac¸a˜o):
Uma matriz P quadrada de ordem n e´ uma matriz de permutac¸a˜o se
pode ser obtida permutando as colunas (ou linhas) da matriz
identidade I de ordem n.
◮ Seja P uma matriz de permutac¸a˜o e A uma matriz quadrada de
ordem n, enta˜o
◮ PA e´ a matriz A com as linhas permutadas
◮ AP e´ a matriz A com as colunas permutadas
Heder S. Bernardino Ca´lculo Nume´rico
Decomposic¸a˜o LU com Pivotamento
Decomposic¸a˜o LU com Pivotamento
◮ Por exemplo, sejam
P =

0 1 00 0 1
1 0 0

 → 1 na coluna 2→ 1 na coluna 3
→ 1 na coluna 1
e A =

3 1 41 5 9
2 6 5


◮ enta˜o
PA =

0 1 00 0 1
1 0 0



3 1 41 5 9
2 6 5

 =

1 5 92 6 5
3 1 4

 → linha 2 de A→ linha 3 de A
→ linha 1 de A
Heder S. Bernardino Ca´lculo Nume´rico
Decomposic¸a˜o LU com Pivotamento
Decomposic¸a˜o LU com Pivotamento Parcial
◮ Seja
A′ = PA = LU
◮ enta˜o
LUx = PAx = Pb
◮ Logo, o sistema e´ resolvido definindo Ux = y e
◮ resolvendo Ly = Pb
◮ resolvendo Ux = y
◮ Nota-se que
det(A′) = det(LU) = det(U)
Heder S. Bernardino Ca´lculo Nume´rico
Decomposic¸a˜o LU com Pivotamento
Decomposic¸a˜o LU com Pivotamento Parcial
◮ Na pra´tica (implementac¸a˜o)
◮ a matriz de permutac¸a˜o P de ordem n e´ representada por um vetor p
de ordem n de valores inteiros
◮ p[k] representa o ı´ndice da coluna de P que tem o elemento da
k-e´sima linha igual a 1
◮ p representa as trocas de linhas da matriz A
◮ Por exemplo,
P =

0 1 00 0 1
1 0 0

 → 1 na coluna 2→ 1 na coluna 3
→ 1 na coluna 1
⇒ p =

23
1


Heder S. Bernardino Ca´lculo Nume´rico
Decomposic¸a˜o LU com Pivotamento
Exemplo
◮ Exemplo 1
Resolva o sistema linear que segue utilizando a Decomposic¸a˜o LU
com Pivotamento Parcial.
3 −4 11 2 2
4 0 −3



x1x2
x3

 =

 93
−2


◮ Soluc¸a˜o:
L =

 1 0 03/4 1 0
1/4 −1/2 1

 , U =

4 0 −30 −4 13/4
0 0 35/8

 e x =

 1−1
2


Heder S. Bernardino Ca´lculo Nume´rico
Decomposic¸a˜o de Cholesky
Decomposic¸a˜o de Cholesky
Heder S. Bernardino Ca´lculo Nume´rico
Decomposic¸a˜o de Cholesky
Decomposic¸a˜o de Cholesky
◮ As operac¸o˜es aritme´ticas da Decomposic¸a˜o LU podem ser
simplificadas ao explorar caracter´ısticas da matriz de coeficientes
◮ A Decomposic¸a˜o de Cholesky leva em conta que A e´
◮ sime´trica
◮ positiva definida
◮ A Decomposic¸a˜o de Cholesky e´ importante pois muitas matrizes com
essas caracter´ısticas surgem em aplicac¸o˜es de engenharias e cieˆncias
Heder S. Bernardino Ca´lculo Nume´rico
Decomposic¸a˜o de Cholesky
Decomposic¸a˜o de Cholesky
◮ Definic¸a˜o (Matriz Sime´trica):
Uma matriz real A quadrada de ordem n e´ sime´trica se
A = AT ,
ou seja, aij = aji, ∀i = 1, . . . , n e j = 1, . . . , n.
◮ Por exemplo,
A =

4 1 21 3 0
2 0 5

 = AT
◮ Definic¸a˜o (Matriz Positiva Definida):
Uma matriz real A quadrada de ordem n e´ positiva definida se
xTAx > 0, ∀x 6= 0
Heder S. Bernardino Ca´lculo Nume´rico
Decomposic¸a˜o de Cholesky
Decomposic¸a˜o de Cholesky
◮ Verificando se uma matriz e´ positiva definida
1. Crite´rio de Sylvester:
Uma matriz real e sime´trica A e´ positiva definida, se e somente se,
det(Ak) > 0, ∀k = 1, . . . , n,
onde Ak e´ o menor principal de ordem k da matriz A
2. Uma matriz real A e´ positiva definida, se e somente se, todos os pivoˆs
utilizados durante o processo de Eliminac¸a˜o de Gauss sem troca de
linha ou coluna forem positivos
Heder S. Bernardino Ca´lculo Nume´rico
Decomposic¸a˜o de Cholesky
Exemplo
◮ Exemplo 2
Verifique se a matriz que segue e´ sime´trica e positiva definida.

4 1 21 3 0
2 0 5


◮ Soluc¸a˜o:
Como aij = aji enta˜o A e´ sime´trica. Ale´m disso,
◮ det(A1) = 4 > 0
◮ det(A2) = 11 > 0
◮ det(A3) = 43 > 0
Logo, A e´ sime´trica e positiva definida (SPD)
Heder S. Bernardino Ca´lculo Nume´rico
Decomposic¸a˜o de Cholesky
Exemplo
◮ Exemplo 3
Verifique se a matriz que segue e´ sime´trica e positiva definida.

 2 −1 0−1 2 −1
0 −1 2


◮ Soluc¸a˜o:
Como aij = aji enta˜o A e´ sime´trica. Ale´m disso,
◮ det(A1) = 2 > 0
◮ det(A2) = 3 > 0
◮ det(A3) = 4 > 0
Logo, A e´ sime´trica e positiva definida (SPD)
Heder S. Bernardino Ca´lculo Nume´rico
Decomposic¸a˜o de Cholesky
Decomposic¸a˜o de Cholesky
◮ Teorema:
Se A e´ uma matriz real sime´trica e positiva definida (SPD), enta˜o
existe uma u´nica matriz triangular inferior G com elementos da
diagonal principal positivos, tal que
A = GGT
Heder S. Bernardino Ca´lculo Nume´rico
Decomposic¸a˜o de Cholesky
Decomposic¸a˜o de Cholesky
◮ Demonstrac¸a˜o:
◮ Se A e´ SPD, enta˜o pelo Crite´rio de Sylvester tem-se que
det(Ak) > 0, ∀k = 1, . . . , n
◮ Portanto, todos os menores principais de A sa˜o na˜o singulares e pelo
Teorema da Decomposic¸a˜o LU, tem-se que
A = LU
Heder S. Bernardino Ca´lculo Nume´rico
Decomposic¸a˜o de Cholesky
Decomposic¸a˜o de Cholesky
◮ Demonstrac¸a˜o:
◮ Sendo A sime´trica, enta˜o A = AT
◮ Assim,
LU = A = AT = (LU)
T
= UTLT
LU = UTLT
L−1LU = L−1UTLT
U
(
LT
)
−1
= L−1UTLT
(
LT
)
−1
U
(
LT
)
−1
= L−1UT
Heder S. Bernardino Ca´lculo Nume´rico
Decomposic¸a˜o de Cholesky
Decomposic¸a˜o de Cholesky
◮ Demonstrac¸a˜o:
◮ Nota-se que
◮ U
(
LT
)
−1
e´ uma triangular superior
◮ L−1UT e´ triangular inferior
◮ Logo, U
(
LT
)
−1
= L−1UT = D, onde D e´ uma matriz diagonal
◮ Assim,
D = U
(
LT
)
−1
DLT = U
(
LT
)
−1
LT
DLT = U
◮ Resultando em
A = LU = LDLT
Heder S. Bernardino Ca´lculo Nume´rico
Decomposic¸a˜o de Cholesky
Decomposic¸a˜o de Cholesky
◮ Demonstrac¸a˜o:
◮Como A e´ SPD e L e´ triangular com elementos da diagonal principal
unita´rios, enta˜o
dii > 0, ∀i = 1, . . . , n
◮ Portanto,
A = LDLT
= L (D)
1/2
︸ ︷︷ ︸
G
(D)
1/2
LT︸ ︷︷ ︸
GT
= GGT
Heder S. Bernardino Ca´lculo Nume´rico
Decomposic¸a˜o de Cholesky
Decomposic¸a˜o de Cholesky – Obtendo a Matriz G
◮ A matriz G pode ser obtida pela definic¸a˜o de produto e igualdade de
matrizes


a11 a12 a13 . . . a1n
a21 a22 a23 . . . a2n
a31 a32 a33 . . . a3n
...
...
...
. . .
...
an1 an2 an3 . . . ann


=


g11 0 0 . . . 0
g21 g22 0 . . . 0
g31 g32 g33 . . . 0
...
...
...
. . .
...
gn1 gn2 gn3 . . . gnn




g11 g21 g31 . . . gn1
0 g22 g32 . . . gn2
0 0 g33 . . . gn3
...
...
...
. . .
...
0 0 0 . . . gnn


◮ Os elementos de G podem enta˜o ser determinados a cada coluna j
como:
◮ Determina-se o elemento da diagonal gjj
◮ Obte´m-se os elementos abaixo de gjj
Heder S. Bernardino Ca´lculo Nume´rico
Decomposic¸a˜o de Cholesky
Decomposic¸a˜o de Cholesky – Obtendo a Matriz G
◮ Coluna 1
◮ Elemento da diagonal
a11 = g
2
11 ⇒ g11 =
√
a11
◮ Elementos abaixo da diagonal
a21 = g21g11 ⇒ g21 = a21
g11
a31 = g31g11 ⇒ g31 = a31
g11
...
an1 = gn1g11 ⇒ gn1 = an1
g11
Heder S. Bernardino Ca´lculo Nume´rico
Decomposic¸a˜o de Cholesky
Decomposic¸a˜o de Cholesky – Obtendo a Matriz G
◮ Coluna 2
◮ Elemento da diagonal
a22 = g
2
21 + g
2
22 ⇒ g22 =
√
a22 − g221
◮ Elementos abaixo da diagonal
a32 = g31g21 + g32g22 ⇒ g32 = a32 − g31g21
g22
a42 = g41g21 + g42g22 ⇒ g42 = a42 − g41g21
g22
...
an2 = gn1g21 + gn2g22 ⇒ gn2 = an2 − gn1g21
g22
Heder S. Bernardino Ca´lculo Nume´rico
Decomposic¸a˜o de Cholesky
Decomposic¸a˜o de Cholesky – Obtendo a Matriz G
◮ Generalizando para a coluna j
◮ Elemento da diagonal
ajj =
j∑
k=1
g2jk ⇒ ajj =
j−1∑
k=1
g2jk + g
2
jj ⇒ gjj =
√√√√ajj −
j−1∑
k=1
g2jk
◮ Elementos abaixo da diagonal (linhas i > j)
aij =
j∑
k=1
gikgjk ⇒ aij =
j−1∑
k=1
gikgjk + gijgjj
⇒ gij =
aij −
∑j−1
k=1 gikgjk
gjj
Heder S. Bernardino Ca´lculo Nume´rico
Decomposic¸a˜o de Cholesky
Decomposic¸a˜o de Cholesky – Algoritmo
Entrada: Matriz A, n
1 inicio
2 para j = 1, . . . , n fac¸a
3 gjj ←−
√
ajj −
∑j−1
k=1 g
2
jk ;
4 para i = j + 1, . . . , n fac¸a
5 gij ←− aij−
∑j−1
k=1
gikgjk
gjj
;
Algoritmo 1: Decomposic¸a˜o de Cholesky - Complexidade O(n3)
Heder S. Bernardino Ca´lculo Nume´rico
Decomposic¸a˜o de Cholesky
Decomposic¸a˜o de Cholesky
◮ Observa-se que
◮ A Decomposic¸a˜o de Cholesky realiza menos operac¸o˜es aritme´ticas do
que a Decomposic¸a˜o LU
◮ Apesar da mesma ordem de complexidade computacional O(n3)
◮ Como a matriz de coeficientes A e´ positiva definida, enta˜o os ca´lculos
de raiz quadrada podem ser realizados
◮ Ca´lculo do determinante de A
A = GGT ⇒ det(A) = det(GGT )
= det(G) det(GT )
= det(G)2
= (g11g22 . . . gnn)
2
Heder S. Bernardino Ca´lculo Nume´rico
Decomposic¸a˜o de Cholesky
Decomposic¸a˜o de Cholesky
◮ Para resolver o sistema Ax = b utilizando a Decomposic¸a˜o de
Cholesky
◮ Como Ax = b⇒ GGTx = b
◮ Faz-se GTx = y
◮ Resolve-se Gy = b
◮ Resolve-se GTx = y
Heder S. Bernardino Ca´lculo Nume´rico
Decomposic¸a˜o de Cholesky
Exemplo
◮ Exemplo 4
Dado o sistema de equac¸o˜es lineares que segue.
 4 −2 2−2 10 −7
2 −7 30



x1x2
x3

 =

 811
−31


◮ Verifique se a matriz de coeficientes pode ser decomposta usando a
Decomposic¸a˜o de Cholesky
◮ Decomponha A em GGT
◮ Calcule o determinante de A utilizando o resultado da decomposic¸a˜o
◮ Resolva o sistema linear
Heder S. Bernardino Ca´lculo Nume´rico
Decomposic¸a˜o de Cholesky
Exemplo
◮ Exemplo 4 – Soluc¸a˜o:
◮ Como A = AT enta˜o a matriz e´ sime´trica e sendo det(A1) = 4 > 0,
det(A2) = 36 > 0 e det(A3) = 900 > 0, enta˜o a matriz de
coeficientes e´ SPD e a Decomposic¸a˜o de Cholesky pode ser utilizada
◮ A decomposic¸a˜o fica como
A =

 2 0 0−1 3 0
1 −2 5



2 −1 10 3 −2
0 0 5


◮ det(G)2 = 900
◮ Soluc¸a˜o do sistema
x =

 31
−1


Heder S. Bernardino Ca´lculo Nume´rico
Decomposic¸a˜o de Cholesky
Decomposic¸a˜o de Cholesky – Exemplo em Python
1 from pylab import *
2
3 def cholesky(A):
4 n = A.shape[ 0 ]
5 for j in range(0,n):
6 soma = 0
7 for k in range(0,j):
8 soma += A[ j, k ]*A[ j, k ]
9 A[ j, j ] = sqrt( A[ j, j] - soma )
10 for i in range(j+1,n):
11 soma = 0
12 for k in range(0,j):
13 soma += A[ i, k ]*A[ j, k ]
14 A[i,j] = ( A[i, j] - soma ) / A[ j, j ]
Heder S. Bernardino Ca´lculo Nume´rico
Decomposic¸a˜o de Cholesky
Decomp. de Cholesky – Exemplo em Python – cont.
1 # inicializa a matriz A
2 A = np.matrix([[ 4, -2, 2 ],
3 [ -2, 10, -7 ],
4 [ 2, -7, 30 ]])
5
6 # inicializa o vetor b
7 b = np.matrix( [ [8.0], [11.0], [-31.0] ] )
8
9 #Decomposicao de Cholesky
10 cholesky( A )
11
12 #Resolve o sistema Gy=b
13 y = substituicoesSucessivas( A, b )
14
15 #Resolve o sistema G^Tx=y
16 x = substituicoesRetroativas( A.transpose(), y )
17 print( x )
Heder S. Bernardino Ca´lculo Nume´rico
Decomposic¸a˜o de Cholesky
Decomposic¸a˜o de Cholesky via Decomposic¸a˜o LU
◮ A Decomposic¸a˜o de Cholesky tambe´m pode ser realizada fazendo
◮ Decomponha A em LU
◮ Pode-se utilizar a Eliminac¸a˜o de Gauss
◮ Sendo U = DLT , enta˜o D e´ formada pela diagonal principal de U
◮ Finalmente, G = LD1/2
Heder S. Bernardino Ca´lculo Nume´rico
Decomposic¸a˜o de Cholesky
Exemplo
◮ Exemplo 5
Determine a matriz G da Decomposic¸a˜o de Cholesky sabendo que
A =

 4 −2 2−2 10 −7
2 −7 30

 =

 1 0 0−1/2 1 0
1/2 −2/3 1



4 −2 20 9 −6
0 0 25


◮ Soluc¸a˜o:
Sendo
U =

4 −2 20 9 −6
0 0 25

⇒ D =

4 0 00 9 0
0 0 25

⇒ D1/2 =

2 0 00 3 0
0 0 5


Logo,
G = LD1/2 =

 1 0 0−1/2 1 0
1/2 −2/3 1



2 0 00 3 0
0 0 5

 =

 2 0 0−1 3 0
1 −2 5


Heder S. Bernardino Ca´lculo Nume´rico
Decomposic¸a˜o LDLT
Decomposic¸a˜o LDLT
Heder S. Bernardino Ca´lculo Nume´rico
Decomposic¸a˜o LDLT
Decomposic¸a˜o LDLT
◮ Verificou-se que A pode tambe´m ser decomposta em LDLT
◮ L e´ uma matriz triangular inferior com elementos da diagonal principal
unita´rios
◮ D e´ uma matriz diagonal
Heder S. Bernardino Ca´lculo Nume´rico
Decomposic¸a˜o LDLT
Decomposic¸a˜o LDLT
◮ Neste caso,
Ax = b⇒ LDDTx︸ ︷︷ ︸
y
= b
⇒ L Dy︸︷︷︸
w
= b
⇒ Lw = b
e o sistema linear pode ser resolvido seguindo os seguintes passos:
◮ Resolve-se Lw = b
◮ Resolve-se Dy = w
◮ Resolve-se LTx = y
◮ Ale´m disso, tem-se que
det(A) = det(LDLT ) = det(D) = d11d22 . . . dnn
Heder S. Bernardino Ca´lculo Nume´rico
Decomposic¸a˜o LDLT
Decomposic¸a˜o LDLT
◮ Pelo produto e igualdade de matrizes, determina-se que
djj = ajj −
j−1∑
k=1
l2jkdkk, j = 1, . . . , n
lij =
aij −
∑j−1
k=1 likdkkljk
djj
, j = 1, . . . , n− 1 e i = j + 1, . . . , n
◮ Essa te´cnica na˜o requer o ca´lculo de raiz quadrada na decomposic¸a˜o
◮ Entretanto, requer a resoluc¸a˜o de um sistema de equac¸o˜es lineares
adicional para obter a soluc¸a˜o do sistema original
Heder S. Bernardino Ca´lculo Nume´rico
Decomposic¸a˜o LDLT
Decomposic¸a˜o LDLT
Entrada: Matriz A, n
1 inicio
2 para j = 1, . . . , n fac¸a
3 djj ←− ajj −
∑j−1
k=1 l
2
jkdkk ;
4 para i = j + 1, . . . , n fac¸a
5 lij ←− aij−
∑j−1
k=1
likdkkljk
djj
;
Algoritmo 2: Decomposic¸a˜o LDLT - Complexidade O(n3)
Heder S. Bernardino Ca´lculo Nume´ricoRevisa˜o
Revisa˜o
Heder S. Bernardino Ca´lculo Nume´rico
Revisa˜o
Revisa˜o
◮ Decomposic¸a˜o LU com Pivotamento Parcial
◮ Vetor com as permutac¸o˜es das linhas
◮ Decomposic¸a˜o de Cholesky
◮ Sistemas em que a matriz de coeficientes e´ sime´trica e positiva definida
◮ Requer menos operac¸o˜es aritme´ticas do que a decomposic¸a˜o LU
◮ Decomposic¸a˜o LDLT
◮ Na˜o necessita de ca´lculos de raiz quadrada
◮ Requer a resoluc¸a˜o de um sistema linear com uma matriz de
coeficientes diagonal, ale´m de dois sistemas triangulares
Heder S. Bernardino Ca´lculo Nume´rico
Revisa˜o
Du´vidas?
Heder S. Bernardino Ca´lculo Nume´rico
	Aula Anterior
	Decomposição LU com Pivotamento
	Decomposição de Cholesky
	Decomposição LDLT
	Revisão