Métodos Iterativo em
Álgebra Linear
Prof. Jairo Ramalho
E-mail: [email protected]
Método de Jacobi
Dado um sistema linear, como por exemplo:
10x1 – x2 + 2x3
= 6
–x1 + 11x2 – x3 + 3x4 = 25
2x1 – x2 + 10x3 – x4 = -11
3x2 – x3 + 8x4 = 15
No método de Jacobi, isolamos a variável xk na k-ésima equação
(contanto que seu coeficiente seja diferente de zero):
x1 =
(1/10)x2 – (1/5)x3 +
3/5
x2 = (1/11)x1 +
(1/11)x3 – (3/11)x4 + 25/11
x3 = –(1/5)x1 +(1/10)x2
+ (1/10)x4 – 11/10
x4=
– (3/8)x2 + (1/8)x3 +
15/8
E obtemos o sistema iterativo:
0  x1k   3 / 5 
1 / 10  1 / 5
 x1k 1   0
 k 1  

 k  
1 / 11  3 / 11 x2   25 / 11 
0
 x2   1 / 11


 x k 1     1 / 5 1 / 10
k  


10
/
11

10
/
1
0
x
 3  

 3  


k  

 x k 1   0
8
/
15
0
8
/
1
8
/
3

x

 4  
 4  
Fazemos então um “chute” inicial para a solução, como, por exemplo,
x0 = (0,0,0,0)T, e calculamos o vetor solução x1 através de:
 x11   0
1 / 10  1 / 5
0  0   3 / 5 
 1 
  

0
1 / 11  3 / 11 0   25 / 11 
 x2   1 / 11

 x1     1 / 5 1 / 10



0
1 / 10 0
 11/ 10
3
  
  






 x1   0

3
/
8
1
/
8
0
0
15
/
8






 4
Obtido x1 = (0,6; 2,273; -1,1; 1,875)T, calculamos x2 via:
 x12   0
1 / 10  1 / 5
0  0,6   3 / 5 
 2 

 

0
1 / 11  3 / 11 2,273  25 / 11 
 x2   1 / 11

 2     1 / 5 1 / 10




0
1
/
10

1
,
1

11
/
10
x
 3 

 






 x2   0

3
/
8
1
/
8
0
1
,
875
15
/
8






 4
Continuando o procedimento, vamos obter:
x3 = (0,933; 2,053; -1,049; 1,131)T
...
x9 = (0,999; 2,000; -1,000; 1,000)T
x10 = (1,000; 2,000; -1,000; 1,000)T
E, em dez passos, o método converge para a solução exata.
Em termos matriciais, saímos do sistema Ax = b
10x1 – x2 + 2x3
= 6
–x1 + 11x2 – x3 + 3x4 = 25
2x1 – x2 + 10x3 – x4 = -11
3x2 – x3 + 8x4 = 15
 10  1 2 0  x1   6 

  

  1 11  1 3  x2   25 
 2  1 10  1 x     11

 3  

 0 3  1 8  x   15 

 4  

Para o sistema x = Tx + c
x1 =
(1/10)x2 – (1/5)x3 +
3/5
x2 = (1/11)x1 +
(1/11)x3 – (3/11)x4 + 25/11
x3 = –(1/5)x1 +(1/10)x2
+ (1/10)x4 – 11/10
x4=
– (3/8)x2 + (1/8)x3 +
15/8
1 / 10  1 / 5
0  x1   3 / 5 
 x1   0
  
  

0
1 / 11  3 / 11 x2   25 / 11 
 x2   1 / 11

 x     1 / 5 1 / 10



0
1 / 10 x3
 11/ 10
3
  
  



x   0


 3 / 8 1/ 8
0  x4   15 / 8 
 4 
Em termos matriciais, saímos do sistema Ax = b
10x1 – x2 + 2x3
= 6
–x1 + 11x2 – x3 + 3x4 = 25
2x1 – x2 + 10x3 – x4 = -11
3x2 – x3 + 8x4 = 15
 10  1 2 0  x1   6 

  

  1 11  1 3  x2   25 
 2  1 10  1 x     11

 3  

 0 3  1 8  x   15 

 4  

Para o sistema x = Tx + c
x1 =
(1/10)x2 – (1/5)x3 +
3/5
x2 = (1/11)x1 +
(1/11)x3 – (3/11)x4 + 25/11
x3 = –(1/5)x1 +(1/10)x2
+ (1/10)x4 – 11/10
x4=
– (3/8)x2 + (1/8)x3 +
15/8
Ou, em termos de fórmulas (para aii ≠ 0) :
n
aij x j
bi
xi   (
)  , i  1,2,...,n
aii
aii
j 1
j i
n: número de equações
Método de Jacobi
Mais ainda, colocando iterativamente:
n
bi   aij x kj
k 1
xi

j 1
j i
aii
, i  1,2,...,n
Onde xi0 é uma aproximação inicial dada.
Algoritmo: Método de Jacobi
Dados de Entrada. Matriz: A, vetores: b, x0, número de equações: n,
tolerância: tol, número máximo de iterações: Nmax.
cont = 1
Enquanto cont ≤ Nmax Faça
Para i = 1 até n, passo 1, Faça
soma = 0
Para j=1 até i-1, passo 1, Faça
soma = soma + A( i, j )*x0( j )
Para j=i+1 até n, passo 1, Faça
soma = soma + A( i, j )*x0( j )
x( i ) = [ b( i ) – soma ] / A( i, i )
Se || x – x0 || < tol
Retornar x
Sair
Senão
x0 = x
cont = cont + 1
Algoritmo: Método de Jacobi
Observações.
1) Antes de começar o algoritmo, é preciso checar se os aii (elementos da
diagonal) são diferentes de zero. Se isso ocorrer e a matriz A for nãosingular, basta fazer troca de linhas.
2) Se possível, o ideal é fazer troca de linhas de modo a colocar nas
diagonais os maiores valores possíveis (reduzindo erros de
arredondamento).
Método de Gauss-Seidel
Observando o método de Jacobi
x1k+1 =
(1/10)x2k – (1/5)x3k +
3/5
x2k+1 = (1/11)x1k +
(1/11)x3k – (3/11)x4k + 25/11
x3k+1 = –(1/5)x1k +(1/10)x2k
+ (1/10)x4k – 11/10
x4k+1=
– (3/8)x2k + (1/8)x3k +
15/8
Se este é convergente, então, uma possível melhoria na sua eficiência
computacional pode ser obtida notando-se que as componentes de
xk+1 que já foram calculadas podem ser aproximações melhores do
que seus valores no passo k.
Essa é a idéia do Método de Gauss-Seidel. Isto é: acelerar a
convergência calculando xik+1 usando os valores x1k+1, x2k+1,..., xi-1k+1
que já foram calculados, ao invés de seus valores no passo anterior.
Método de Gauss-Seidel
Exemplo:
Contrastando os dois métodos, no método de Jacobi fazemos:
x1k+1 =
(1/10)x2k – (1/5)x3k +
3/5
x2k+1 = (1/11)x1k +
(1/11)x3k – (3/11)x4k + 25/11
x3k+1 = –(1/5)x1k +(1/10)x2k
+ (1/10)x4k – 11/10
x4k+1=
– (3/8)x2k + (1/8)x3k +
15/8
Enquanto no método de Gauss-Seidel, fazemos
x1k+1 =
(1/10)x2k – (1/5)x3k +
3/5
x2k+1 = (1/11)x1k+1 +
(1/11)x3k – (3/11)x4k + 25/11
x3k+1 = –(1/5)x1k+1 +(1/10)x2k+1
+ (1/10)x4k – 11/10
x4k+1=
– (3/8)x2k+1 + (1/8)x3k+1 +
15/8
x1k+1 =
(1/10)x2k – (1/5)x3k +
3/5
x2k+1 = (1/11)x1k+1 +
(1/11)x3k – (3/11)x4k + 25/11
x3k+1 = –(1/5)x1k+1 +(1/10)x2k+1
+ (1/10)x4k – 11/10
x4k+1=
– (3/8)x2k+1 + (1/8)x3k+1 +
15/8
Considerando novamente o “chute inicial” x0 = (0,0,0,0)T, obtemos
os seguintes resultados:
x11 = (1/10)*0 – (1/5)*0 + 3/5 = 0,6
x21 = (1/11)*0,6 + (1/11)*0 – (3/11)*0 + 25/11 = 2,327
x31 = –(1/5)*0,6 +(1/10)*2,327 + (1/10)*0 – 11/10 = -0,987
x41 = – (3/8)*2,327 + (1/8)*(-0,987) + 15/8 = 0,8789
Continuando o mesmo procedimento, vamos obter:
x2 = (1,030; 2,037; -1,014; 0,984)T
....
x5 = (1,000; 2,000; -1,000; 1,000)T
Observe que, como visto na aula anterior, nesse exemplo, o método
de Jacobi precisou de praticamente o dobro de iterações para chegar
no mesmo resultado.
Método de Gauss-Seidel
Assim como fizemos para o método de Jacobi, em termos de
fórmulas, podemos escrever o método de Gauss-Seidel da seguinte
forma:
i 1
k 1
xi

bi   aij x kj 1 
j 1
aii
n
k
a
x
 ij j
j i 1
, i  1,2,...,n
Onde xi0 é uma aproximação inicial dada.
Algoritmo: Método de Gauss-Seidel
Dados de Entrada. Matriz: A, vetores: b, x0, número de equações: n,
tolerância: tol, número máximo de iterações: Nmax.
cont = 1;
Enquanto cont ≤ Nmax Faça
Para i = 1 até n, passo 1, Faça
soma = 0
Para j=1 até i-1, passo 1, Faça
soma = soma + A( i, j )*x( j )
Para j=i+1 até n, passo 1, Faça
soma = soma + A( i, j )*x0( j )
x( i ) = [ b( i ) – soma ] / A( i, i )
Se || x – x0 || < tol
Retornar x
Sair
Senão
Obs.: Algoritmo idêntico ao de
x0 = x
Jacobi, exceto nos trechos marcados
em verde.
cont = cont + 1
x = x0;
Métodos de Relaxação
Uma terceira classe de métodos são os chamados métodos de
relaxação, descritos pela fórmula:
i 1
k 1
xi
 (1  w) x i  w
k
bi   aij x j 
k 1
j 1
aii
n
a x
j i 1
ij
k
j
, i  1,2,...,n
Observe que se w = 1, temos o método de Gauss-Seidel. Assim, o
parâmetro w funciona como uma ponderação que pode auxiliar a
acelerar a convergência. Estes métodos utilizam 0 < w < 2.
Matrizes Esparsas
Métodos iterativos são convenientes para resolver sistemas envolvendo
matrizes grandes e esparsas. O motivo disso é que as várias
multiplicações envolvidas em métodos como o de Jacobi e GaussSeidel não precisam ser feitas pois são multiplicações por zero.
Veja o caso, por exemplo, do sistema Ax=b abaixo. Dos 25 elementos
da matriz A, apenas 12 são diferentes de zero.
 2  1 0 0 0  x1   1 

   
 1 3  1 0 0  x2   2 
 0 0 5  1 0  x    3 

 3   
 0 0 2 8  1 x4   4 
 0 0 0 1 9  x   5 

 5   
Além disso, podemos economizar memória do computador se
deixarmos de armazenar os zeros da matriz.
Isto pode ser feito usando uma matriz auxiliar que armazene
apenas os valores não nulos e suas respectivas posições. Isto é,
podemos substituir a matriz A abaixo pela matriz M.
 2 1 0 0 0 


 1 3 1 0 0 
A   0 0 5 1 0 


 0 0 2 8  1
0 0 0 1 9 


Onde M é 12x3, sendo 12 o número de
elementos não nulos (NENN) de A.
Repare que dada uma linha k de M, isto é (mk1,
mk2, mk3), temos que mk3 é o elemento
amk1,mk2. Por exemplo, na linha
4 de M, (2,2,3), o elemento 3 é o elemento a2,2.
1

1
2

2
2

3
M 
3
4

4
4

5
5

1
2
1
2
3
3
4
3
4
5
4
5
2

 1
1

3
 1
5

 1
2

8
 1

1
9 
 2 1 0 0 0 


 1 3 1 0 0 
A   0 0 5 1 0 


 0 0 2 8  1
0 0 0 1 9 


Observe que, nesse caso, a matriz M tem mais
elementos que a matriz A porque esta é uma
matriz “pequena”.
Imagine, por exemplo, uma matriz A100x100,
esparsa, com apenas 30 elementos não nulos.
Nesse caso, a matriz M teria apenas 90 elementos,
enquanto a matriz A teria 10.000.
1

1
2

2
2

3
M 
3
4

4
4

5
5

1
2
1
2
3
3
4
3
4
5
4
5
2

 1
1

3
 1
5

 1
2

8
 1

1
9 
Algoritmo do Método de Gauss-Seidel
para Matrizes Esparsas
Supondo que a matriz A seja substituída pela matriz M, o algoritmo
do método de Gauss-Seidel muda para o seguinte.
Dados de Entrada. Número de Equações: n, número máximo de
iterações: Nmax, número de elementos não-nulos: NENN,
tolerância: tol, Matriz: A na forma M, vetores: b e x0.
...
continua
...
i 1
n
x = x0;
k 1
k
b

a
x

a
x


i
ij
ij
Para cont = 1 até Nmax, Passo 1, Faça
j 1
j i 1
k 1
x

k=1
aii
Para i = 1 até n, passo 1, Faça
soma = 0
Enquanto M(k,1)=i e M(k,2)≤ i-1 Faça
soma = soma + M(k,3)*x( M(k,2) )
k=k+1
aii=M(k,3)
k=k+1
Enquanto k<NENN e M(k,1)=i e M(k,2) ≤ n Faça
soma = soma + M( k, 3 )*x0( M(k,2) )
k=k+1
x( i ) = [ b( i ) – soma ] / aii
Se || x – x0 || < tol
Retornar x e Sair
Senão
x0 = x
j
i
j
Projeto 2.
Prezados alunos.
Como combinado em sala de aula, o objetivo desse segundo projeto
é resolver os sistemas lineares do projeto 1 (com n=100 e n=1000)
utilizando métodos iterativos para comparar com a solução por
eliminação de Gauss.
Assim, adaptem os métodos de Jacobi, Gauss-Seidel e Relaxação
(com w variando entre 1.8, 1.9 e 1.95) ao algoritmo para matrizes
esparsas e verifiquem os tempos que estes métodos levam para
solucionar os sistemas lineares (comparar com o tempo do método
da eliminação de Gauss). Adotem nos métodos uma tolerância
(precisão) de 10-5.