Métodos Iterativos
Motivação




Em certos casos, métodos diretos não são
eficientes, por exemplo, quando a matriz dos
coeficientes é uma matriz esparsa (muitos
elementos iguais a zero)
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
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
 Precisam sempre saber se a sequência
obtida está convergindo ou não para a
solução desejada.

Convergência

Dados uma sequência de vetores x(k)  E

Uma norma sobre E, onde E é um espaço
vetorial

Dizemos que a sequência {x(k)} converge para x
 E se ||x(k) – x||  0, quando k  .
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)

Assim um sistema do tipo Ax=b é
transformado em xk =Fx(k-1)+d
 Escolhemos uma aproximação inicial x0
 Assim, x1 =Fx0 +d
 x2 = Fx1+d
 E assim sucessivamente

Método de Jacobi

Iterativamente, reescreve-se o sistema
x1


( k 1)

1
(k )
(k )
(k )
b1  a12 x 2  a13 x3  ...... a1n x n
a11
( k 1)

1
(k )
(k )
(k )
b2  a 21 x1  a 23 x3  ...... a 2 n x n
a 22
x2


..........
..........
..........
..........
..........
.......
1
( k 1)
(k )
(k )
(k )
xn

bn  a n1 x1  a n 2 x 2  ...... a n , n 1 x n 1
a nn


Método de Jacobi

Desta forma
0


  a21 / a22
F 
........

 a / a
n1
nn

 a12 / a11
0
.........
 an 2 / ann
 a1n / a11 

.......  a2 n / a22 
.......
......... 


.......
0

......
 b1 / a11 


 b2 / a22 
d 
....... 


b / a 
 n nn 
Quando Parar?
Se a sequência xk estiver suficientemente
próximo de x(k-1) paramos o processo
 Dada um precisão ε, quando
||x(k) – x|| < ε
Então xk é a solução do sistema linear

Computacionalmente, um número máximo
de iterações também é critério de parada

Exemplo:
x (0)

Seja
 0 .7 


   1.6 
 0 .6 


10 x1  2 x 2  x3  7
1 x1  5 x 2  x3  8
2 x1  3 x 2  10 x3  6
com
 2 / 10  1 / 10
 0


F   1/ 5
0
1/ 5 
  1 / 5  3 / 10
0 

ε = 0.05. Portanto,
 7 / 10   0.7 

 

d    8 / 5     1.6 
 6 / 10   0.6 

 


Substituindo
(1)
 0.2 x 2
( 0)
 0.1 x3
x2
(1)
 0.2 x1
( 0)
 0.2 x3
( 0)
 1.6  0.2 (0.7)  0.2 (0.6)  1.6  1.86
x3
(1)
 0.2 x1
(0)
 0.3 x 2
( 0)
 0.6  0.2 (0.7)  0.3 (1.6)  0.6  0.94
x1

Segue
x (1)
 0.96 


   1.86 
 0.94 


( 0)
 0.7  0.2 (1.6)  0.1 (0.6)  0.7  0.96
d1(1)  x1(1)  x1( 0)  0.26  0.05
d 2(1)  x 2(1)  x 2( 0)  0.26  0.05
d 3(1)  x3(1)  x3( 0)  0.34  0.05

( 2)
x
Continuando
 0.978 


   1.98  com
 0.966 


d ( 2)  MAX xi2   xi1  0.12  
1i  n


 0.999 
Segue


( 3)
x    1.999 
 0.998 


é a solução, pois
d (3)  MAX xi(3)  xi( 2)  0.032  
1i  n
critério de parada
Sistemas de Equações Lineares
Método de Gauss-Seidel

Conhecido x(0) (aproximação inicial) obtém-se x1, x2,
...xk.

Ao se calcular
k 1
k 1
x1 ,...,x j 1
k
k
x j 1 ,...,xn
x kj 1 usa-se todos os valores
que já foram calculados e os valores
restantes.
Métodos Iterativos – Gauss-Seidel
Descrição do Método

Seja o seguinte sistema de equações:
a11.x1  a12 .x 2  a13 .x 3  ...  a1n 1.x n 1  a1n 1.x n  b1
a 21.x1  a 22 .x 2  a 23 .x 3  ...  a 2n 1.x n 1  a 2n 1.x n  b 2
a 31.x1  a 32 .x 2  a 33 .x 3  ...  a 3n 1.x n 1  a 3n 1.x n  b 3

a n1 .x1  a n 2 .x 2  a n 3 .x 3  ...  a n1n 1.x n 1  a nn .x n  b n
Métodos Iterativos – Gauss-Seidel

Isolando xi a partir da linha i, temse:
x1 
1
b1  a12 .x2  a13 .x3  a1n 1.xn 1  a1n .xn 
a11
x2 
1
b 2  a 21.x1  a 23 .x 3  a 2n 1.x n 1  a 2n .x n 
a 22
x3 
1
b 3  a 31.x 2  a 32 .x 2  a 3n 1.x n 1  a 3n .x n 
a 33

xn 
1
b n  a n1.x1  a n2 .x 2  ...  a nn 1.x n 1 
a nn
Métodos Iterativos – Gauss-Seidel

O processo iterativo é obtido a partir das equações, fazendo:


k 1
1
1

b1  a12 .x 2k  a13 .x3k  ...  a1,n 1 .x nk1  a1n .x nk
a11
k 1
2
1

b2  a 21 .x1k 1  a 23 .x3k  ...  a 2,n 1 .x nk1  a 2 n .x nk
a 22
x
x



x3k 1 
1
b3  a31 .x1k 1  a32 .x 2k 1  ...  a3,n 1 .x nk1  a3n .x nk
a33
x nk 1 
1
bn  a n1 .x1k 1  a n 2 .x 2k 1  ...  a n ,n 1 .x nk11
a nn



Métodos Iterativos – Gauss-Seidel
Critério de Parada
 Diferença
relativa entre duas iterações consecutivas.
 Define-se por diferença relativa a expressão:


Máx.
 1
 in
0

M Rk 1  



1


xik 1  xik
xik 1
se
se
xik 1  0
se
xik 1

 xik 1  0
 k
 xi  0
xik  0
Métodos Iterativos – Gauss-Seidel
Exemplo: Resolva:
5x  y  z  5
3x  4 y  z  6
3x  3 y  6 z  0
Solução:
com
1
5  y  z 
5
1
y  6  3 x  z 
4
1
1
z   3 x  3 y   z   x  y 
6
2
x
M Rk  5.10 2.
Métodos Iterativos – Gauss-Seidel
M xk
xk
yk
M yk
M zk
zk
M Rk
-1
-
0
-
1
-
-
0,8
2,25
0,65
1
-0,725
2,379
2,379
1,015
0,212
0,92
0,293
-0,967
0,250
0,293
1,009
0,006
0,985
0,066
-0,997
0,030
0,066
1,002
0,007
0,998
0,0013
-1
0,003
0,0013
x = 1,002
y = 0,998
z = -1
Verificação (substituição no sistema):
5.(1,002) + (0,998) + (-1) = 5,008  5
3.(1,002) + 4.(0,998) + (-1) = 5,998  6
3.(1,002) + 3.(0,998) + 6.(-1) = 0
ok
ok
ok
Método de Gauss-Seidel Critérios de Convergência

Processo iterativo  a convergência para a solução
exata não é garantida para qualquer sistema.

Existem certas condições que devem ser satisfeitas
por um sistema de equações lineares para se
garantir a convergência do método.

As condições podem ser determinadas por dois
critérios:
 Critério
de Sassenfeld
 Critério das Linhas.
Método de Gauss-Seidel Critério de Sassenfeld

Sejam as quantidades i dadas por:
1 n
1 
  a1 j
a11 j  2
e
1
i 
aii
 i 1
  ( aij   j ) 
 j 1



aij 

j i 1 
n

para i = 2, 3, ..., n.
n - ordem do sistema linear que se deseja resolver
aij - são os coeficientes das equações que compõem o sistema.

Este critério garante que o método de Gauss-Seidel convergirá
para um dado sistema linear se a quantidade M, definida por:
M  max  i
1i  n
for menor que 1 (M<1).
Método de Gauss-Seidel Critério de Sassenfeld

Exemplo: Seja A, a matriz dos coeficientes e b o
vetor dos termos constantes dados por:
1
1 
 | a12  | a13 |  | a14 
a11
a11 a12 a13 a14 b1
1
2 
  a21 1  a23  a24 
a21 a22 a23 a24 b2
a22
a31 a32 a33 a34 b3
1
a41 a42 a43 a44 b4
3 
  a31 1  a32  2  a34 
a33
1
4 
  a41 1  a42  2  a43  3 
a44
Método de Gauss-Seidel Critério de Sassenfeld
Exemplo: Mostre que a solução do sistema
linear dado pelas equações:
2  x1  x2  0.2  x3  0.2  x4  0.4
0.6  x1  3  x2  0.6  x3  0.3  x4  7.8
 0.1  x1  0.2  x2  x3  0.2  x4  1.0
0.4  x1  1.2  x2  0.8  x3  4  x4  10.0
convergirá pelo método de Gauss-Seidel.

Método de Gauss-Seidel Critério de Sassenfeld
Solução: critério de Sassenfeld
 calcular
os valores das quantidades i.
A
B
1
 1  0.2  0.2  0.7
2.0 1.0 - 0.2 0.2
0.4
2
0.6 3.0 - 0.6 - 0.3 - 7.8
1
 2   0.6  0.7  0.6  0.3  0.44
- 0.1 - 0.2 1.0 0.2
1.0
3
0.4 1.2 0.8 4.0 - 10.0
1
 3   0.1  0.7  0.2  0.44  0.2  0.358
1
1
 4   0.4  0.7  1.2  0.44  0.8  0.358  0.2736
4
M é menor que 1  a solução
M
 i  0.7
desse sistema irá convergir usando
1i  4
o método de Gauss-Seidel.
1 
max
Método de Gauss-Seidel Critério das Linhas

Segundo esse critério, um determinado sistema irá
convergir pelo método de Gauss-Seidel, se:
n
a
j 1
j i
ij
 aii
,
para i=1, 2, 3, ..., n.
Método de Gauss-Seidel Critério das Linhas
Exemplo: O sistema do exemplo anterior satisfaz o
critério das linhas e essa verificação pode ser feita
de maneira quase imediata, observando-se que:
2  x1  x2  0.2  x3  0.2  x4  0.4
0.6  x1  3  x2  0.6  x3  0.3  x4  7.8
 0.1  x1  0.2  x2  x3  0.2  x4  1.0
0.4  x1  1.2  x2  0.8  x3  4  x4  10.0
a11  2  a12  a13  a14  1  0.2  0.2  1.4
a 22  3  a 21  a 23  a 24  0.6  0.6  0.3  1.5
a33  1  a31  a32  a34  0.1  0.2  0.2  0.5
a 44  4  a 41  a 42  a 43  0.4  1.2  0.8  2.4
n
a
j 1
j i
ij
 aii
para i=1, 2, 3, 4.