MN-10-resolucao-sistemas-metodos-iterativos-ppt

Prévia do material em texto

Métodos Numéricos 
Sistemas Lineares – Métodos Iterativos 
 
 
 Professor Volmir Eugênio Wilhelm 
Professora Mariana Kleina 
2 
Resolução de Sistemas Lineares 
• É bastante comum encontrar sistemas lineares que envolvem uma grande 
porcentagem de coeficientes nulos. Esses sistemas são chamados de sistemas 
esparsos. Para esses tipos de sistemas, o método de Eliminação de Gauss não é o 
mais apropriado, pois ele não preserva essa esparsidade, que pode ser útil por 
facilitar a resolução do sistema. 
• Métodos iterativos são mais econômicos no que tange a memória dos 
computadores 
• Podem ser usados para reduzir os erros de arredondamento na solução obtida 
por métodos exatos 
• Em alguns casos podem ser aplicados para resolver conjuntos de equações não 
lineares 
 
(Ruggiero, página 154) 
 
Métodos Iterativos – Introdução 
Professor Volmir Eugênio Wilhelm – Professora Mariana Kleina 
3 
Resolução de Sistemas Lineares 
• Um método é iterativo quando fornece uma sequência de aproximações da 
solução. 
• Cada uma das aproximações é obtida das anteriores pela repetição do mesmo 
processo. 
• Precisamos sempre saber se a sequência obtida está convergindo ou não para a 
solução desejada. 
• Dada uma sequência de vetores {x(k)}, dizemos que a sequência {x(k)} converge 
para x se ||x(k) – x||  0, quando k  . 
Métodos Iterativos – Introdução 
Professor Volmir Eugênio Wilhelm – Professora Mariana Kleina 
4 
Resolução de Sistemas Lineares 
• Portanto, como todo processo iterativo, estes métodos sempre apresentarão um 
resultado aproximado, que será tão próximo do resultado real conforme o 
número de iterações realizadas. 
• Para determinar a solução de um sistema linear por métodos iterativos, 
precisamos transformar o sistema dado em um outro sistema onde possa ser 
definido um processo iterativo. 
• A solução obtida para o sistema transformado deve ser também solução do 
sistema original (sistemas lineares devem ser equivalentes). 
Métodos Iterativos – Introdução 
Professor Volmir Eugênio Wilhelm – Professora Mariana Kleina 
5 
Resolução de Sistemas Lineares 
• Escrever o sistema Ax = b, de forma equivalente x = Fx + d (tal como f(x) = x – g(x) 
para iterações de ponto fixo). 
• Escolher uma aproximação inicial x(0). 
• Começando com x(0), gerar uma sequência de aproximações {xk} de forma 
iterativa através de 
x(k + 1) = Fx(k) + d 
 fazendo x(1) = Fx(0) + d, x(2) = Fx(1) + d e assim sucessivamente. 
 
Observação 
• A representação de F e d depende do tipo de método usado. 
• Assim, para métodos iterativos diferentes, F e d são obtidos a partir de A e b de 
formas diferentes. 
Métodos Iterativos – Algoritmo 
Professor Volmir Eugênio Wilhelm – Professora Mariana Kleina 
6 
Resolução de Sistemas Lineares 
• Como k→, a seqüência {x(k)} converge para o vetor solução sob algumas 
condições da matriz F. 
• Isto impõe condições diferentes na matriz A para diferentes métodos. 
• Para a mesma matriz A, um método pode convergir, enquanto outro pode 
divergir. 
• Portanto, para cada processo, a relação entre A e F deve ser encontrada para 
decidir sobre a convergência. 
Métodos Iterativos – Algoritmo 
Professor Volmir Eugênio Wilhelm – Professora Mariana Kleina 
7 
Resolução de Sistemas Lineares 
Métodos Iterativos – Algoritmo 
Quando Parar? 
• Se a sequência {x(k)} estiver suficientemente próximo de x(k-1) paramos o processo. 
• Dada um precisão ε, quando ||x(k) – x|| < ε então x(k) é a solução do sistema linear. 
• Computacionalmente, um número máximo de iterações também é critério de 
parada. 
Professor Volmir Eugênio Wilhelm – Professora Mariana Kleina 
8 
Resolução de Sistemas Lineares 
Método Iterativo Gauss-Jacobi 
Professor Volmir Eugênio Wilhelm – Professora Mariana Kleina 
9 
Resolução de Sistemas Lineares 
Professor Volmir Eugênio Wilhelm – Professora Mariana Kleina 
10 
Resolução de Sistemas Lineares 
Método Iterativo Gauss-Jacobi – Motivação 










nnnn2n21n1
2n2n222121
1n1n212111
bxaxaxa
bxaxaxa
bxaxaxa




Seja um sistema com n variáveis e n equações 
 
 
 









1-n1-nn1n1nnnn
n2n1212222
n1n2121111
xaxabxa
xaxabxa
xaxabxa



...
  
  
  













1-n1-nn1n1n
nn
n
n2n1212
22
2
n1n2121
11
1
xaxab
a
x
xaxab
a
x
xaxab
a
x



1
...
1
1
Professor Volmir Eugênio Wilhelm – Professora Mariana Kleina 
11 
Resolução de Sistemas Lineares 
  
  
  













1-n1-nn1n1n
nn
n
n2n1212
22
2
n1n2121
11
1
xaxab
a
x
xaxab
a
x
xaxab
a
x



1
...
1
1
Método Iterativo Gauss-Jacobi 
Seja x(0) uma solução inicial para este sistema . Calculando o segundo valor, x(1), 
da sequência {x(k)} a partir de x(0) 
      
        
        














0
1n1nn
0
2n2
0
1n1n
nn
1
n
0
n2n
0
323
0
1212
22
1
2
0
n1n
0
2121
11
1
1
xaxaxab
a
1
x
xaxaxab
a
1
x
xaxab
a
1
x



...
 
 
 
 















1
n
1
2
1
1
1
x
x
x
x

 
 
 
 















0
n
0
2
0
1
0
x
x
x
x

Professor Volmir Eugênio Wilhelm – Professora Mariana Kleina 
12 
Resolução de Sistemas Lineares 
Método Iterativo Gauss-Jacobi 
Calculando o valor de ordem (k+1) da sequência {x(k)} a partir de x(k) 
 
 
 
 
 
 
 
 
 
Equação geral 
        
        
        

















k
1n1nn
k
2n2
k
1n1n
nn
1k
n
k
n2n
k
323
k
1212
22
1k
2
k
n1n
k
313
k
2121
11
1k
1
xaxaxab
a
1
x
xaxaxab
a
1
x
xaxaxab
a
1
x



...
     






  

 

1i
1j
n
1ij
k
jij
k
jiji
ii
1k
i xaxab
a
1
x
Professor Volmir Eugênio Wilhelm – Professora Mariana Kleina 
13 
Resolução de Sistemas Lineares 
Método Iterativo Gauss-Jacobi 
• Seja o sistema 
 
 
 
 
 
 
 
• Considerando que x(k+1) = Fx(k) + d, então temos 
 


















0......./aa/aa
.................................
/aa.......0/aa
/aa....../aa0
F
nnn2nnn1
222n2221
111n1112















nnn
222
111
/ab
.......
/ab
/ab
d
      
        
        

















k
1n1nn
k
2n2
k
1n1n
nn
1k
n
k
n2n
k
323
k
1212
22
1k
2
k
n1n
k
2121
11
1k
1
xaxaxab
a
1
x
xaxaxab
a
1
x
xaxab
a
1
x



...
Professor Volmir Eugênio Wilhelm – Professora Mariana Kleina 
14 
A iteração xk+1 = Fxk + d para o método Gauss-Jacobi 
A matriz A pode ser rescrita como A=L+D+U (não é decomposição) 
 
 
 
Ax = b  (L + D + U)x = b Dxk+1 = [b–(L+U)xk] xk+1 = (1/D)*[b–(L+U)xk] 
Dn×n é matriz diagonal formado pelos elementos da diagonal de A 
Un×n matriz triangular superior formada pelos elementos acima da diagonal de A 
Ln×n matriz triangular inferior formada pelos elementos abaixo da diagonal de A 
 
Fazendo Qn×n = (Un×n + Ln×n), e considerando Dn×n tal que A = (L + D + U) 
 



















































































3
2
1
23
1312
3
2
1
33
22
11
3
2
1
3231
21
3
2
1
333231
232221
131211
x
x
x
000
a00
aa0
x
x
x
a00
0a0
00a
x
x
x
0aa
00a
000
x
x
x
aaa
aaa
aaa
Resolução de Sistemas Lineares 
Método Iterativo Gauss-Jacobi 
   






 


n
1j
k
jiji
ii
1k
i xQb
D
1
x
Professor Volmir Eugênio Wilhelm – Professora Mariana Kleina 
15 
Resolução de Sistemas Lineares 
1. Sejam An×n e bn×1 
2. Construa as matrizes Q e D tal que Q = (U + L) e A = (L + D + U) 
3. Faça x(0) = 0; k = 0; Erro= Inf; Tolerancia = 10-5; 
4. while Erro > Tolerancia 
 
 
k = k + 1; 
Erro = ||b – Axk||; 
end 
 
Método Iterativo Gauss-Jacobi – Pseudo-Algoritmo 
   






 


n
j
k
jiji
ii
k
i xQb
D
x
1
1 1
Professor Volmir Eugênio Wilhelm – Professora Mariana Kleina 
16 








n
ji
j
ijii
n
ji
j ii
ij
a a 
n1,2,...,i para 
a
a
1
1
1
(matriz diagonalmente dominante) 
Se A é uma matriz diagonalmente dominante, então o método Jacobi converge 
para qualquer vetor inicial x(0). 
Resolução de Sistemas Lineares 
Método Iterativo Gauss-Jacobi – Critério de Convergência das linhas 
Critério das linhas. 
 
Dado o sistema Ax = b, seja 
 
Se , então o método de Gauss-Jacobi gera uma série convergente 
para a solução do sistema independentemente da escolha de x(0). 
|a|/|a|α kk
n
kj1,j
kjk 







 

1αmaxα k
nk1


Professor Volmir Eugênio Wilhelm – Professora Mariana Kleina 
 
 
 
 
 
 
Critério das linhas: 
 
 
 
 
Como logo, a sequência converge 
 
10,3
10
12
α1 













1032
151
1210
A








6x10x3x2
8xx5x1
7xx2x10
321
321
321
10,5
10
32
α3 

10,4
5
11
α2 


10,5αmaxα k
k1

 4
Método Iterativo Gauss-Jacobi – Critério das linhas – Exemplo 
Resolução de Sistemas Lineares 
17 Professor Volmir Eugênio Wilhelm – Professora Mariana Kleina 
18 


































15
21
7
x
x
x
512
184
114
3
2
1
 











0
0
0
x 0
 
   
 
   
 
   
5
x2x15
x
8
x4x21
x
4
xx7
x
0
2
0
11
3
0
3
0
11
2
0
3
0
21
1






3,0
5
15
2,625
8
21
1,75
4
7



  26,7395Axb 0 
  10,0452Axb 1 
Resolução de Sistemas Lineares 
Método Iterativo Gauss-Jacobi – Exemplo 1 
 











3,000
2,625
1,750
x 1
A matriz dos coeficientes é diagonalmente dominante 
Professor Volmir Eugênio Wilhelm – Professora Mariana Kleina 
19 
 
   
 
   
 
   
5
x2x15
x
8
x4x21
x
4
xx7
x
1
2
1
12
3
1
3
1
12
2
1
3
1
22
1






4,225
5
2,6251,75215
3,875
8
31,75421
1,65625
4
32,6257









  6,7413Axb 2 
 
 
  2,8875
5
3,8751,65625215
x
3,98125
8
4,2251,65625421
x
1,6625
4
4,2253,8757
x
3
3
3
2
3
1









  1,9534Axb 3 
Resolução de Sistemas Lineares 
Método Iterativo Gauss-Jacobi – Exemplo 1 
 











4,2250
3,8750
1,6562
x 2
 











2,88750
3,98125
1,66250
x 3
A matriz é uma diagonalmente dominante, então o método Jacobi converge. 
Professor Volmir Eugênio Wilhelm – Professora Mariana Kleina 

































1
1
1
xbAx
7
7
7
b
511
151
115
A




































1,4000
1,4000
1,4000
7/5
7/5
7/5
b/Dd
0,00000,20000,2000
0,20000,00000,2000
0,20000,20000,0000
F











0,0000
0,0000
0,0000
x(0)
20 
Resolução de Sistemas Lineares 
Método Iterativo Gauss-Jacobi – Exemplo 2 
   
    

























 
k
i
1k
n
1j
k
ji ji
i i
1k
i
xFdx
xqb
d
1
x
Solução exata 
  12,124Axb 0 Erro: 
Professor Volmir Eugênio Wilhelm – Professora Mariana Kleina 
   
   
    0,04971Axb0,12367Axb
0,9959
0,9959
0,9959
dFxx
1,0102
1,0102
1,0102
dFxx
0,31038Axb0,77596Axb
0,9744
0,9744
0,9744
dFxx
1,0640
1,0640
1,0640
dFxx
1,9399Axb4,8497Axb
0,8400
0,8400
0,8400
dFxx
1,4000
1,4000
1,4000
dFxx
65
(5)(6)(4)(5)
43
(3)(4)(2)(3)
21
(1)(2)(0)(1)





































































21 
Resolução de Sistemas Lineares 
Método Iterativo Gauss-Jacobi – Exemplo 2 
Professor Volmir Eugênio Wilhelm – Professora Mariana Kleina 
22 
Resolução de Sistemas Lineares 
Método Iterativo Gauss-Seidel 
Professor Volmir Eugênio Wilhelm – Professora Mariana Kleina 
23 
Resolução de Sistemas Lineares 
Calculando o valor x(k+1) da sequência {x(k)} a partir de x(k) 
 
 
 
 Gauss-Jacobi 
 
 
 
 
 
 
 
 
Gauss-Seidel 
 
 
        
        
        

















k
1n1nn
k
2n2
k
1n1n
nn
1k
n
k
n2n
k
323
k
1212
22
1k
2
k
n1n
k
313
k
2121
11
1k
1
xaxaxab
a
1
x
xaxaxab
a
1
x
xaxaxab
a
1
x



...
        
        
        


















1k
1n1nn
1k
2n2
1k
1n1n
nn
1k
n
k
n2n
k
323
1k
1212
22
1k
2
k
n1n
k
313
k
2121
11
1k
1
xaxaxab
a
1
x
xaxaxab
a
1
x
xaxaxab
a
1
x



...
Professor Volmir Eugênio Wilhelm – Professora Mariana Kleina 
24 
        
        
        


















1k
1n1nn
k
2n2
k
1n1n
nn
1k
n
k
n2n
k
323
1k
1212
22
1k
2
k
n1n
k
313
k
2121
11
1k
1
xaxaxab
a
1
x
...
xaxaxab
a
1
x
xaxaxab
a
1
x



11
Resolução de Sistemas Lineares 
Método Iterativo Gauss-Seidel 
     






  

 

1i
1j
n
1ij
k
jij
1k
jiji
ii
1k
i xaxab
a
1
x
Professor Volmir Eugênio Wilhelm – Professora Mariana Kleina 
25 
Resolução de Sistemas Lineares 
Método Iterativo Gauss-Seidel 






  

 

1i
1j
n
1ij
k
jij
1k
jiji
ii
1k
i xaxab
a
1
x
Ax = b  (L + D + U)x = b 
 
k1k UxLx 
Dxk+1 
        
        
        


















1k
1n1nn
k
2n2
k
1n1n
nn
1k
n
k
n2n
k
323
1k
1212
22
1k
2
k
n1n
k
313
k
2121
11
1k
1
xaxaxab
a
1
x
...
xaxaxab
a
1
x
xaxaxab
a
1
x



11
Professor Volmir Eugênio Wilhelm – Professora Mariana Kleina 
26 
Resolução de Sistemas Lineares 
1. Sejam An×n e bn×1 
2. Construa as matrizes D, L e U tal que A = (L + D + D) 
3. Faça x(0) = 0; k = 0; Erro = Inf; Tolerancia = 10-5; 
4. while Erro > Tolerancia 
 
 
K = k + 1; 
Erro = ||b – Axk||; 
end 
 
Método Iterativo Gauss-Seidel – Pseudo-Algoritmo 
     






 





nj
ij
k
jij
ij
j
k
jiji
ii
k
i xUxLb
D
x
1
1
1
11 1
Professor Volmir Eugênio Wilhelm – Professora Mariana Kleina 
27 
• Gauss-Jacobi converge para qualquer vetor inicial, se a matriz A é uma matriz 
diagonal dominante. 
• Gauss-Seidel converge para qualquer vetor inicial se A é uma matriz definida 
positiva. 
• A Matrix é definida positiva se xTAx > 0 para todo x diferente do vetor nulo. 
• A matriz é definida positiva, se todos os autovalores são positivos. 
• Mas o critério a ser adotado para convergência do método Gauss-Seidel será o de 
SASSENFELD. 
Resolução de Sistemas Lineares 
Método Iterativo Gauss-Seidel – Critério de Convergência 
Professor Volmir Eugênio Wilhelm – Professora Mariana Kleina 
28 
Resolução de Sistemas Lineares 
Método Iterativo Gauss-Seidel – Critério de Convergência 
Critérios de Convergência; 
 
 1) Critério das linhas –para o método GAUSS-JACOBI; 
 
 2) Critério de Sassenfeld – para o método GAUSS-SEIDEL. 
 
Os critérios acima estabelecem condições suficientes para a convergência. 
 
Critério de Sassenfeld 
 
Sejam as quantidades i dadas por: 
 
 
 
 
Se o método de Gauss-Seidel convergirá. Quanto menor , mais 
rápida é a convergência. 



n
2j
1j
11
1 a
a
1
β n2,3,...,i,aaβ
a
1β
n
1ij
ij
1i
1j
ijj
ii
i 





 



}{βmaxβ i
ni1 

Professor Volmir Eugênio Wilhelm – Professora Mariana Kleina 
Sejam 
 
 
e 
 
 
 
 
 
Seja . Se  < 1, o método de Gauss-Seidel gera uma sequência 
convergente para qualquer x(0). Quanto menor , mais rápida a convergência.
Método Iterativo Gauss-Seidel – Critério de Sassenfeld 
Resolução de Sistemas Lineares 





n
2j 11
1j
11
1n1312
1
|a|
|a|
|a|
|a||a||a|
β

n2,3,i|a||]/a|β|a|[ 
|a|
|a||a|β|a|β|a|β|a|
β
ii
n
1ij
ijj
1i
1j
ij
ii
in1ii1i1ii2i21i1
i










}{βmaxβ i
ni1 

29 Professor Volmir Eugênio Wilhelm – Professora Mariana Kleina 
30 
Resolução de Sistemas Lineares 
Método Iterativo Gauss-Seidel – Critério de Convergência de Sassenfeld – Exemplo 
 













44434241
34333231
24232221
14131211
a a a a
a a a a
a a a a
a a a a
A
 
 
 
 343242141
44
4
34232131
33
3
2423121
22
2
141312
11
1
βaβaβa
a
1
β
aβaβa
a
1
β
aaβa
a
1
β
a||a|a|
a
1
β




 i
4i1
βmaxβ

Seja . Se  é menor que 1 então o método iterativo Gauss-Seidel irá 
convergir para a solução do sistema. 













4
3
2
1
b
b
b
b
b
Professor Volmir Eugênio Wilhelm – Professora Mariana Kleina 
Resolução de Sistemas Lineares 
31 











104x0,8x1,2x0,4x
10,2xx0,2x0,1x
7,80,3x0,6x3x0,6x
0,40,2x0,2xx2x
4321
4321
4321
4321
 
 
 
 














0,27360,3580,80,441,20,70,4
4
1
β
0,3580,20,440,20,70,1
1
1
β
0,440,30,60,70,6
3
1
β
0,70,20,21
2
1
β
4
3
2
1
Como  < 1, a sequência gerada pelo método de Gauss-Seidel converge para a 
solução do sistema Ax = b. 
Método Iterativo Gauss-Seidel – Critério de Sassenfeld – Exemplo 
 
    0,70,27360,358,0,44,0,7,maxβmaxβ i
4i1


















40,81,20,4
0,210,20,1
0,30,630,6
0,20,212
A
Professor Volmir Eugênio Wilhelm – Professora Mariana Kleina 
32 


































15
21
7
x
x
x
512
184
114
3
2
1
 











0
0
0
x 0   26,7395Axb 0 
  10,0452AxbGJ 1 :
Resolução de Sistemas Lineares 
Método Iterativo Gauss-Seidel – Exemplo 1 
 











3,000
3,500
1,750
x 1
A matriz dos coeficientes é diagonalmente dominante 
 
   
 
   
 
   
5
x2x15
x
8
x4x21
x
4
xx7
x
1
2
1
11
3
0
3
1
11
2
0
3
0
21
1






3,0
5
3,51,75215
3,5
8
1,75421
1,75
4
7







  3,0414Axb 1 
Professor Volmir Eugênio Wilhelm – Professora Mariana Kleina 
33 
  6,7413AxbGJ 2 :
 
 
  2,9991
5
3,99221,9937215
x
3,9921
8
2,96251,9937421
x
1,9937
4
2,96253,93757
x
3
3
3
2
3
1









  1,9534AxbGJ 3 :
Resolução de Sistemas Lineares 
Método Iterativo Gauss-Seidel – Exemplo 1 
 











2,9625
3,9375
1,8750
x 2
 











2,9991
3,9921
1,9937
x 3
 
   
 
   
 
   
5
x2x15
x
8
x4x21
x
4
xx7
x
2
2
2
12
3
1
3
2
12
2
1
3
1
22
1






2,9625
5
3,93751,875215
3,9375
8
31,875421
1,875
4
33,57









  0,4765Axb 2 
  0,0408Axb 3 
Quando ambos Jacobi e Gauss-Seidel convergem, Gauss-Seidel converge mais rápido. 
Professor Volmir Eugênio Wilhelm – Professora Mariana Kleina 























































1,0000
1,0000
1,0000
dFxx
1,0001
1,0000
0,9996
dFxx
1,0004
1,0014
0,9964
dFxx
0,9964
1,0214
0,9968
dFxx
0,8960
1,1200
1,4000
dFxx
(4)(5)
(3)(4)(2)(3)
(1)(2)(0)(1)
34 
Resolução de Sistemas Lineares 
Método Iterativo Gauss-Seidel – Exemplo 2 
Professor Volmir Eugênio Wilhelm – Professora Mariana Kleina 
Implementação paralela: Gauss-Jacobi 
Resolução de Sistemas Lineares 
Métodos Iterativos Gauss-Jacobi e Gauss-Seidel – Comparação 
     






 





nj
ij
k
jij
ij
j
k
jiji
ii
k
i xUxLb
D
xSeidelGauss
1
1
1
11 1:
     






 





nj
ij
k
jij
ij
j
k
jiji
ii
k
i xUxLb
D
xJordanGauss
1
1
1
1 1:
35 Professor Volmir Eugênio Wilhelm – Professora Mariana Kleina