Sistemas de
equações lineares
Métodos Directos
1
Análise Numérica - Resolução de Sistemas Métodos Directos
Sistemas triangulares
inferiores

Exemplo
2
 2 x1
 x1  2 2  1


 x2  (3  1) 2  2
 x1  2 x2  3
 11x1
 x   x
 21 1 22 2
  31x1   32x2   33x3



 k1x1   k 2 x2     kk xk



2
 b1 

 b2 
 b3  
 bk
x1  b1 11
x2  b2   21x1  22
x3  b3   31 x1   32 x2   33


k 1



 xk   bk    kj x j   kk



j

1


Análise Numérica - Resolução de Sistemas Métodos Directos

Sistemas triangulares
superiores

Exemplo
 3x1  x2  5
 x1  (5  1 2) 3  1


2 x2  4  x2  4 2  2





n



 u x u
x    ukn xn  bk
 xk   bk   ukj x j  ukk
 kk k k ,k 1 k 1
j  k 1








un1,n1xn1  un1,n xn  bn1  xn1  bn1  un1,n xn un1,n1



unnxn  bnn  x  b u
n
nn
 n

3
Análise Numérica - Resolução de Sistemas Métodos Directos

Método de Gauss


Pivot – elemento da diagonal akk
Para anular os elementos abaixo da
diagonal aik
 Multiplicar (mantêm a.s.) a linha pivot
pelo factor
aik

akk

4
Adicionar (mantêm c.d.) a linha obtida à
linha i
Análise Numérica - Resolução de Sistemas Métodos Directos
Decomposição LU

A=LU
L – matriz triangular inferior
U – matriz triangular superior
 Ly  b
U x  b  
Ax  b  L
Ux

y

y
Resolução de 1
sistema quadrado
5
Resolução de 2 sistemas
triangulares
Análise Numérica - Resolução de Sistemas Métodos Directos
Decomposição LU
 a11

a21
A 
 

an1
a12

a22



an 2

a1n   11
 
a2n   21

   
 
ann   n1
a11  11 u11
?



6
0

 22



 n2

0  u11
 
0  0
 
   
 
 nn   0
u12

u22



0

u1n 

u2n 

 

unn 
Problema indeterminado
?
Se uii=1 i  Decomposição de Crout
Se ℓii=1 i  Decomposição de Doolittle
Se ℓii=uii i  Decomposição de Choleski
 (A=LLT)(A simética e definida positiva)
 Se A só for simétrica A=LDLT
Análise Numérica - Resolução de Sistemas Métodos Directos
Decomposição de Doolittle

Para i de 1 até n
i 1
uij  aij    ik  ukj
j  i , , n
k 1
i 1
 ji 
7
a ji    jk  uki
k 1
uii
j  i  1,, n
Análise Numérica - Resolução de Sistemas Métodos Directos
Decomposição de Doolitle
Exemplo

Resolva o sistema
 3 x3  2
 4 x1

 3 x1  4 x2  x3  9
 x 2x 2x  3
2
3
 1
4
 4 0  3
 3  4 1   3
 4


1 4
1 2
2 
8
0
4
1
Análise Numérica - Resolução de Sistemas Métodos Directos
2
 3
13 
4
35 
8
Factorização LU

Resolva o sistema  x1  2 x2  5 x3  9

 x1  x2  3 x3  2
3 x  6 x  x  25
2
3
 1
a)
b)
c)
9
Método de Gauss
Usando o método de Gauss
Usando a decomposição LU de Doolitle
Compare os dois métodos
(solução exacta xT=(2,-3,-1))
Análise Numérica - Resolução de Sistemas Métodos Directos
Comparação entre o método de Gauss
e a decomposição LU (Doolitle).
Fazem as mesmas operações.
 A ordem pela qual as operações são
executadas é diferente.
 A matriz triangular superior do método
de Gauss é U.
 Em L estão armazenados os
simétricos dos factores usados para
eliminar o elemento correspondente.

10
Análise Numérica - Resolução de Sistemas Métodos Directos
Comparação entre o método de Gauss
e a decomposição LU (Doolitle).



11
O termo independente, do sistema
triangular superior obtido pelo método
de Gauss, é o vector y de
Ly=b
O método de Gauss só permite resolver
vários sistemas simultaneamente.
A decomposição LU permite resolver
vários sistemas sucessivamente.
Análise Numérica - Resolução de Sistemas Métodos Directos