Unidade 3 - Sistemas de Equações Lineares

Prévia do material em texto

UNIDADE 3 – SOLUÇÃO NUMÉRICA DE SISTEMAS DE EQUAÇÕES LINEARES 
Introdução 
Vários problemas como o cálculo de estruturas de redes elétricas, cálculos genéticos, 
custos de produção e soluções de equações diferenciais recorrem a resolução numérica de um 
sistema linear. O objetivo desta unidade é a utilização de algoritmos computacionais para 
calcular a solução única de sistemas de equações lineares através de métodos diretos 
(decomposição e eliminação) e métodos iterativos. 
Sistemas de Equações Lineares 
Um sistema de equações lineares é uma equação do tipo: 
Ax b
 
Que pode ser representado nas formas: 
Algébrica: 
11 1 12 2 1 1
21 1 22 2 2 2
1 1 2 2
n n
n n
n n nn n n
a x a x a x b
a x a x a x b
a x a x a x b
   

   


    




 Matriz Completa: 
11 12 1 1
21 22 2 2
1 2
n
n
n n nn n
a a a b
a a a b
a a a b
 
 
 
 
 
 




 
 
Matricial: 
11 12 1 1 1
21 22 2 2 2
1 2
.
n
n
n nn n nn
a a a x b
a a a x b
x ba a a
     
     
     
     
     
    


 

 
Resolver um sistema consiste em determinar o vetor: 
1 2( , , , )
T
nx x x x 
 
que satisfaça todas as equações simultaneamente. 
 
Métodos Diretos 
São caracterizados por fornecer a solução exata para o sistema dado, não fossem os 
erros provenientes do processamento do algoritmo em um equipamento computacional. 
Sistema Triangular Inferior 
 Considere 
Lx b
 um sistema de equações lineares onde a matriz dos coeficientes é 
triangular inferior, isto é, os seus coeficientes 
0i jl 
 sempre que 
i j
 e com 
0iil 
, então: 
11 1 1
21 1 22 2 2
1 1 2 2n n nn n n
l x b
l x l x b
l x l x l x b


 


    


 
O vetor solução deste sistema pode ser obtido tomando-se: 
1
11 1 1 1
11
b
l x b x
l
  
 
 2 21 121 1 22 2 2 2 2 2 21 1
22 22 22
1b l x
l x l x b x x b l x
l l l
       
 
1 1 2 2 3 3 1 1
1 1 2 2 3 3 1 1 1
i i i i i i i
i i i i i i i i i i i
i i
b l x l x l x l x
l x l x l x l x l x b x
l
 
  
    
         


 
ou 
na forma compacta: 
( 1)
1
1 i
i i i j j
ji i
x b l x
l


 
  
 

 
Algoritmo 
 
1
1
11
b
x
l

 
 Para i = 2, ... , n faça 
 ( 1)
1
1 i
i i i j j
ji i
x b l x
l


 
  
 

 
Sistema Triangular Superior 
 Considere 
Ux b
 um sistema de equações lineares onde a matriz dos coeficientes é 
triangular superior, isto é, os seus coeficientes 
0iiu 
 sempre que 
i j
 e com 
0iiu 
, então: 
11 1 12 2 1 1
22 2 2 2
n n
n n
nn n n
u x u x u x b
u x u x b
u x b
   

  


 



 
O vetor solução para este sistema é obtido fazendo-se: 
n
nn n n n
nn
b
u x b x
l
  
 
1 1 2 2ii i ii i ii i in n iu x u x l x u x b       
 
Na forma compacta: 
( 1)
1 n
i i i j j
j ii i
x b u x
u  
 
  
 

 
Algoritmo 
 
n
n
nn
b
x
u

 
 Para 
( 1),( 2), ,1i n n   
 faça 
( 1)
1 n
i i i j j
j ii i
x b u x
u  
 
  
 

 
Método de Decomposição LU 
 Como observado, sistemas de equações lineares cuja matriz dos coeficientes possui a 
característica triangular superior ou inferior apresentam um esforço computacional menor para a 
obtenção de sua solução. Este fato nos motiva a buscar formas para que um sistema de equações 
lineares 
Ax b
 possa ser resolvido através da solução de sistemas com características 
triangulares permitindo, assim, a utilização dos algoritmos. 
 Para utilizarmos estes algoritmos devemos inicialmente verificar se a matriz não é 
singular, e para isto, definimos os “menores principais” da matriz dos coeficientes. 
Definição: denomina-se “menores principais” de ordem k de uma matriz 
( ) , 1,...,i jA a i j n 
 por: 
det( )k kA 
 
Onde 
( ) , 1,...,k iiA a i j k 
, k é formado pelas primeiras linhas e k primeiras colunas da 
matriz A. 
Processo de decomposição 
Teorema: seja A uma matriz quadrada de ordem n, se os menores principais de A, 
0 1,2,..., 1i i n   
, então A se decompõe, de maneira única no produto de uma matriz 
triangular inferior 
( ) , 1,...,i jL l i j n 
, com 
1iil 
, por uma matriz triangular superior 
( ) , 1,...,i jU u i j n 
. Além disso, 
det( ) det( )A U
. 
Considerando o enunciado do teorema podemos montar a relação: 
11 12 13 1 11 12 1
22 23 2 21 22 221
31 32 33 3 31 32 3
1 2 3 1 2
1
1
1 .
1
n n
n n
n n
n n n nn n n nn
u u u u a a a
u u u a a al
l l u u a a a
l l l u a a a
    
    
    
    
    
    
    
     
 
 
 
  
 
 
 
Para construção do algoritmo, construímos a matriz U por linhas e a matriz L por colunas, isto é: 
Cálculo da primeira linha de U: Cálculo da primeira coluna de L: 
11 11 11 111u a u a  
 
21
21 11 21 21
11
a
l u a l
u
  
 
12 12 12 121u a u a  
 
31
31 11 31 31
11
a
l u a l
u
  
 
 

 

 
1 1 1 11 n n n nu a u a  
 
1
1 1 1 1
11
n
n n n n
a
l u a l
u
  
 
Se continuarmos os cálculos para as colunas e linhas, obteremos as seguintes fórmulas gerais 
para os elementos das matrizes L e U: 
Matriz U 
1
1
i
i j i j i k k j
k
u a l u


 
 para 
, 1,..., ,i j n i j 
 
Matriz L 
1
1
1 j
i j i j i k k j
kj j
l a l u
u


 
  
 

 para 
, 1,..., ,i j n i j 
 
Algoritmo 
 Para 
1,..., 1,m n 
 faça 
 Para 
, 1,..., ,j m m n 
 faça 
 1
1
m
m j m j mk k j
k
u a l u


 
 
 Para 
1,..., ,i m n 
 
 1
1
1 m
i m im ik k m
km m
l a l u
u


 
  
 

 
 
1mml 
 
 Para 
m n
 faça 
 1
1
n
mm nn nk k n
k
u a l u


 
 
 
1nnl 
 
------------------------------------------------------------------------------------------------------------------- 
Considerando um sistema de equações lineares 
Ax b
, cuja matriz dos coeficientes A 
satisfaz a condição 
A LU
, podemos escrever o sistema de equações como: 
 LU x b
 
Se denominarmos 
Ux y
, teremos substituído o cálculo da solução do sistema 
Ax b
, pela 
solução de dois sistemas triangulares: um inferior 
Ly b
 e outro superior 
Ux y
. 
Resumo do método 
1º - Verifica-se o teorema dos menores principais; 
2º - Decompõe-se a matriz utilizando o algoritmo de decomposição LU; 
3º - Resolve-se o sistema 
Ly b
, aplicando-se o algoritmo de resolução de sistema triangular 
inferior na matriz L, obtendo o vetor solução y; 
4º - Resolve-se o sistema 
Ux y
, aplicando-se o algoritmo de resolução de sistema triangular 
superior na matriz U, obtendo o vetor solução x; 
Exemplo 
Usando o método de decomposição LU, resolva o seguinte sistema de equações lineares. 
1
2
3
3 2 4 1
1 1 2 . 2
4 3 2 3
x
x
x
     
     
     
          
 
Solução 
1º) Para resolvermos este problema, devemos calcular os menores principais, 
det( )k kA 
, da 
matriz dos coeficientes.Então, 
 Tomando-se 
1k 
, temos: 
1 3 0  
 
 Tomando-se 
2k 
, temos: 
2
3 2
3 2 1 0
1 1
     
. 
Como os menores principais são diferentes de zero, podemos aplicar o teorema e transformar a 
matriz A em um produto LU. 
2º) Devemos construir as matrizes L e U utilizando o algoritmo de decomposição. 
Temos que 
1,2,3m 
; 
1,2,3j 
 e 
2,3i 
. 
Inicio 
 Quando 
1m 
 
 
1j 
 
 
11 11 11 11 110 3u a u a u     
 
 
2j 
 
 
12 12 12 12 120 2u a u a u     
 
 
3j 
 
 
13 13 13 13 130 4u a u a u     
 
 
2i 
 
 
21 21
21 21 21
11 11
0 1
3
a a
l l l
u u

    
 
 
3i 
 
 
31 31
31 31 31
11 11
0 4
3
a a
l l l
u u

    
 
 
11 1l 
 
 Quando 
2m 
 
 
2j 
 
 
22 22 21 12 22 22
1 1
1 (2)
3 3
u a l u u u      
 
 
3j 
 
 
23 23 21 13 23 23
1 2
2 (4)
3 3
u a l u u u      
 
 
3i 
 
 32 31 12
32 32 32
22
4
3 (2)
3 1
1
3
a l u
l l l
u


     
 
22 1l 
 
 Quando 
3m n 
 
 
33 33 31 13 32 23 33 33
4 2
2 (4) 1 8
3 3
u a l u l u u u
 
           
 
 
 
33 1l 
 
Fim 
Feita a decomposição utilizando o algoritmo, temos as seguintes matrizes: 
1 0 0
1
1 0
3
4
1 1
3
L
 
 
 
 
 
 
 
 
 
3 2 4
1 2
0
3 3
0 0 8
U
 
 
 
 
  
 
3º) Devemos resolver o sistema triangular inferior do tipo, 
Ly b
: 
1
2
3
1 0 0
1
1
1 0 2
3
3
4
1 1
3
y
Ly b y
y
 
 
    
      
    
        
 
 
. Utilizando o algoritmo para sistemas triangulares 
inferiores, temos: 
Inicio 
Quando 
1i 
 
 
1
1 1
11
1
b
y y
l
  
 
Quando 
2i 
 
 2 21 1
2 2 2
22
1
2 (1)
53
1 3
b l y
y y y
l


    
 
Quando 
3i 
 
3 31 1 32 2
3 3 3
33
4 5
3 (1) (1)
3 3 0
1
b l y l y
y y y
l
 
 
    
 
Fim 
Temos, portanto que o vetor solução y é dado por: 
1
2
3
1
5
3
0
y
y
y
 
   
   
   
    
 
 
4º) Resolve-se o sistema 
Ux y
, aplicando-se o algoritmo de resolução de sistema triangular 
superior na matriz U, obtendo o vetor solução x; 
1
2
3
3 2 4 1
1 2 5
0
3 3 3
0 0 8 0
x
Ux y x
x
   
    
      
    
        
 
Utilizando o algoritmo: 
Inicio 
 Quando 
3i 
 
 
3
3 3
33
0
y
x x
u
  
 
 Quando 
2i 
 
 2 23 3
2 2 2
22
5
0
3 5
1
3
y u x
x x x
u


     
 Quando 
1i 
 
 
1 12 2 13 3
1 1 1
11
1 2(5) 0
3
3
y u x u x
x x x
u
   
     
 
Como a solução é fornecida pelo vetor x, temos que: 
( 3,5,0)Tx   
 
 
 
Método de Cholesky 
 O método consiste em transformar a matriz dos coeficientes A, no produto TA R R , 
onde 
R
 é uma matriz triangular superior, com diagonal positiva e TR sua transposta. 
Processe de decomposição 
 Considere uma matriz A, devemos construir os elementos da matriz triangular superior 
R
escrevendo o produto, TR R A , então: 
11 12 13 1 11 12 111
22 23 2 21 22 221 22
31 32 33 33 3 31 32 3
1 2 3 1 2
.
n n
n n
n n
n n n nn nn n n nn
r r r r a a ar
r r r a a ar r
r r r r r a a a
r r r r r a a a
    
    
    
    
    
    
    
     
 
 
 
  
 
 
A construção dos elementos da diagonal de R é dada por: 
2
11 11 11 11 11 11 11r r a r a r a    
 
2 2 2 2 2
12 12 22 22 22 12 22 22 22 22 12 22 22 12r r r r a r r a r a r r a r          
 
Generalizando, temos: 
1/ 2
1
2
1
i
i i i i k i
k
r a r


 
  
 

, 
1,2,...,i n
 
Os elementos não pertencentes à diagonal de R podem ser construídos fazendo-se: 
Cálculo da primeira linha de R: Cálculo da primeira coluna de L: 
12
11 12 12 12
11
a
r r a r
r
  
 
23 12 13
12 13 22 23 23 23
22
a r r
r r r r a r
r

   
13
11 13 13 13
11
a
r r a r
r
  
 
24 12 14
12 14 22 24 24 24
22
a r r
r r r r a r
r

   
1
11 1 1 1
11
n
n n n
a
r r a r
r
  
 
2 12 1
12 1 22 2 2 2
22
n n
n n n n
a r r
r r r r a r
r

   
 
De forma geral, 
1
1
1 i
i j i j k i k j
ki i
r a r r
r


 
  
 

, 
1,2,...,i n
 e 
1,...,j i n 
 
Algoritmo 
Para 
1,...,i n
 faça 
1/ 2
1
2
1
i
i i i i k i
k
r a r


 
  
 

 
Para 
1,...,j i n 
 faça 
1
1
1 i
i j i j k i k j
ki i
r a r r
r


 
  
 

 
Se a matriz A satisfaz ás condições TR R A , e se tomarmos o sistema Ax b pode-
se escrever: 
( )TR R x b
 
Se denominarmos 
Rx y
, teremos substituído o cálculo da solução do sistema 
Ax b
, pela 
solução de dois sistemas triangulares 
TR y b
 e 
Rx y
. 
Resumo do método 
1º - Verifica-se o teorema dos menores principais; 
2º - Decompõe-se a matriz utilizando o algoritmo de decomposição de Cholesky; 
3º - Resolve-se o sistema 
TR y b
, aplicando-se o algoritmo de resolução de sistema triangular 
inferior na matriz TR , obtendo o vetor solução y; 
4º - Resolve-se o sistema 
Rx y
, aplicando-se o algoritmo de resolução de sistema triangular 
superior na matriz R, obtendo o vetor solução x;