Sistemas Lineares
Parte 2
Métodos Iterativos
Introdução


Métodos diretos: eliminação por Gauss,
fatoração LU, fatoração de Cholesky, ...
Fornecem solução de qualquer sistema.
Para minimizar problemas de
arredondamento, adota-se o pivoteamento.
Métodos iterativos: podem ser mais rápidos e
necessitar de menos memória do
computador. Fornecem seqüências que
convergem para a solução sob certas
condições.
Introdução


n
Seja A x  b um sistema linear de ordem
.
A idéia é generalizar o método do ponto fixo,
escrevendo o sistema linear na forma
xC x g
onde C é uma matriz de ordem n e g é um
vetor coluna n  1 .
(0)
x
Dado um vetor aproximação inicial
, construímos iterativamente:
x (1)  C x (0)  g
x ( 2)  C x (1)  g
Introdução
Se a seqüência x
(0)
, x
(1)
, ....., x
(k )
convergir
Lim x ( k )  C x ( k 1)  g  
k grande
Então  é a solução do sistema linear
A x  b com
x
Teste de Parada
(k )
Se a seqüência x estiver suficientemente
( k 1)
próximo de x
paramos o processo.
 Dada um precisão  , quando
d
(k )
 MAX
1i  n
k
xi

k 1
xi

(k )
x
então
é a solução do sistema linear.
 Computacionalmente, um número máximo de
iterações também é critério de parada.
MÉTODOS ITERATIVOS
MÉTODO DE GAUSS-JACOBI
Seja o sistema linear
a11 x1  a12 x 2  a13 x3  ...... a1n x n  b1
a 21 x1  a 22 x 2  a 23 x3  ...... a 2 n x n  b2
..........
..........
..........
..........
..........
.......
a n1 x1  a n 2 x 2  a n3 x3  ...... a nn x n  bn
Se aii  0 para i  1...n podemos isolar
x  C x  g por separação da diagonal.
MÉTODOS ITERATIVOS
MÉTODO DE GAUSS-JACOBI
Iterativamente, o sistema reescreve-se como:
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ÉTODOS ITERATIVOS
MÉTODO DE GAUSS-JACOBI
Desta forma temos x  C x  g , onde
0


 a / a
C   21 22
........

 a / a
 n1 nn
 a12 / a11
0
.........
 a n 2 / a nn
......  a1n / a11 

.......  a 2 n / a 22 
....... ......... 


.......
0

e
 b1 / a11 


 b2 / a 22 
g 
....... 


b / a 
 n nn 
(0)
Do método de Gauss-Jacobi, dado x ,
(1)
Obtemos x , ....., x ( k 1) através da relação
recursiva
( k 1)
(k )
x
C x  g
MÉTODOS ITERATIVOS
MÉTODO DE GAUSS-JACOBI
Exemplo:Seja o sistema linear
10 x1  2 x 2  x3  7
1 x1  5 x 2  x3  8
2 x1  3 x 2  10 x3  6
Seja
x (0)
 0 .7 


   1.6 
 0 .6 


com   0.05 . Portanto,
 2 / 10  1 / 10 
 0


C    1/ 5
0
 1/ 5 
  1 / 5  3 / 10
0 

 7 / 10   0.7 

 

g    8 / 5     1.6 
 6 / 10   0.6 

 

MÉTODOS ITERATIVOS
MÉTODO DE GAUSS-JACOBI
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
( 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
Segue x (1)
 0.96 


   1.86  . Calculando d (1)  x (1)  x ( 0)  0.26  0.05
2
2
2
 0.94 


d 3(1)  x3(1)  x3( 0)  0.34  0.05
MÉTODOS ITERATIVOS
MÉTODO DE GAUSS-JACOBI
Continuando x ( 2)
 0.978 


   1.98  com
 0.966 


d ( 2)  MAX xi2   xi1  0.12  
1i  n
( 3)
Segue x
 0.999 


   1.999 
 0.998 


é a solução, pois
d (3)  MAX xi(3)  xi( 2)  0.032  
1i  n
critério de parada
Critérios de Convergência

Nos métodos iterativos são necessários
critérios que garantam a convergência.

Um critério para a convergência do Método
de Gauss-Jacobi é dado pelo:
1) Critério das linhas.
Método de Gauss-Jacobi
Convergência: Critério das linhas

Teorema – Critério das linhas
n
Dado o sistema A x  b, seja  k  ( | a kj |) / | a kk |
j 1
j k
Se   max  k  1 , então o método de Gauss1 k  n
Jacobi gera uma série convergente para a
solução do sistema independentemente da
(0)
x
escolha de
.
Método de Gauss-Jacobi
Convergência: Critério das linhas

Exemplo:Considere o sistema já estudado
10 x1  2 x 2  x3  7
1 x1  5 x 2  x3  8
2 x1  3 x 2  10 x3  6
10 2 1 


A 1 5 1 
 2 3 10 


Critério das linhas:
2 1
1 
 0.3  1
10
 k  0.5  1
Logo,   1max
k n
11
2 
 0.4  1
5
3 
23
 0.5  1
10
convergência OK!
Método de Gauss-Jacobi
Convergência: Critério das linhas

Obs1: O sistema
x1  x 2  3
x1  3 x 2  3
converge pelo método de Gauss-
Jacobi. No entanto,   max  k  1 . Isto mostra que o Teorema das
1 k  n
linhas é apenas suficiente para convergência.

Obs2: O sistema
1 x1  3 x 2  x3  2
5 x1  2 x 2  2 x3  3
0 x1  6 x 2  8 x3  6
Contudo, o sistema 5 x1  2 x 2  2 x3  3
Equivalente converge 1 x1  3 x 2  x3  2
pelo critério das linhas 0 x1  6 x 2  8 x3  6
  max  k  4
1k  n

  max  k  0.8  1
1 k  n
MÉTODOS ITERATIVOS
MÉTODO DE GAUSS-SEIDEL
Seja o sistema linear
a11 x1  a12 x 2  a13 x3  ...... a1n x n  b1
a 21 x1  a 22 x 2  a 23 x3  ...... a 2 n x n  b2
..........
..........
..........
..........
..........
.......
a n1 x1  a n 2 x 2  a n3 x3  ...... a nn x n  bn
Se aii  0 para i  1...n podemos isolar
x  C x  g por separação da diagonal.
MÉTODOS ITERATIVOS
MÉTODO DE GAUSS-SEIDEL
Iterativamente, o sistema reescreve-se como:
x1


( k 1)
1
(k )
(k )
(k )

b1  a12 x 2  a13 x3  ...... a1n x n
a11
( k 1)
1
( k 1)
(k )
(k )

b2  a 21 x1
 a 23 x3  ...... a 2 n x n
a 22
x2


..........
..........
..........
..........
..........
.......
1
( k 1)
( k 1)
( k 1)
( k 1)
xn

bn  a n1 x1
 an2 x2
 ...... a n,n 1 x n 1
a nn


MÉTODOS ITERATIVOS
MÉTODO DE GAUSS-SEIDEL
Comentário: Gauss-Jacobi X Gauss-Seidel
 O Método de Gauss-Seidel é uma variação
do Método de Gauss-Jacobi, pois para
( k 1)
x
calcular j
utilizamos os valores
x1
( k 1)
, x2
( k 1)
, x3
( k 1)
, ....., x j 1
( k 1)
já calculados e os valores restantes
x j 1
( k 1)
, x j 2
( k 1)
, ....., xn
( k 1)
MÉTODOS ITERATIVOS
MÉTODO DE GAUSS-SEIDEL
5 x1  1 x 2  1 x3  5
Exemplo:Seja o sistema linear
Seja
x ( 0)
 0
 
  0
 0
 
x1
( k 1)
x2
x3
( k 1)
3 x1  3 x 2  6 x3  0
com   0.05 . Portanto,

 0.2 x 
  1.5  0.75 x
 0.25 x 

  0  0.5 x
 0.5 x
 1  0.2 x 2
(k )
(k )
3
( k 1)
(k )
1
( k 1)
3 x1  4 x 2  1 x3  6
3
( k 1)
1
( k 1)
2
MÉTODOS ITERATIVOS
MÉTODO DE GAUSS-SEIDEL
Logo, a primeira iteração fornece
x1
(1)
x2
(1)
x3
(1)

 0.2 x   1  0  0  1
  1.5  0.75 x  0.25 x   1.5  0.75  1  0.25  0  0.75
  0  0.5 x  0.5 x   0.5  1  0.5  0.75  0.88
 1  0.2 x 2
(0)
( 0)
3
(1)
(0)
1
x (1)
3
(1)
1
 1 


  0.75 
  0.88 


(1)
2
(1)
 x1
x2
(1)
 x2
( 0)
 0.75  0  0.75  
x3
(1)
 x3
( 0)
  0.88  0  0.88  
x1
( 0)
 1 0 1 
MÉTODOS ITERATIVOS
MÉTODO DE GAUSS-SEIDEL
Logo, a segunda iteração fornece
x1
x ( 2)
( 2)
x2
( 2)
x3
( 2)

 0.2 x   1.03
 1.5  0.75 x
 0.25 x   0.95
 0  0.5 x
 0.5 x   0.99
 1  0.2 x 2
(1)
(1)
3
( 2)
(1)
1
 1.03 


  0.95 
  0.99 


3
( 2)
( 2)
1
2
( 2)
 x1
x2
( 2)
 x2
(1)
 0.2  
x3
( 2)
 x3
(1)
 0.11  
x1
(1)
 0.03  
MÉTODOS ITERATIVOS
MÉTODO DE GAUSS-SEIDEL
Logo, a terceira iteração fornece
x1
x ( 3)
( 3)
x2
( 3)
x3
( 3)

 0.2 x   1.01
 1.5  0.75 x  0.25 x   0.99
 0  0.5 x  0.5 x   1.00
 1  0.2 x 2
( 2)
( 2)
3
( 3)
( 2)
1
 1.01 


  0.99 
  1.00 


3
( 3)
( 3)
1
2
( 3)
 x1
x2
( 3)
 x2
( 2)
 0.04  
x3
( 3)
 x3
( 2)
 0.01  
x1
( 2)
 0.02  
MÉTODOS ITERATIVOS
MÉTODO DE GAUSS-SEIDEL
Logo, após a terceira iteração
x  x ( 3)
 1.01 


  0.99 
  1.00 


é solução do sistema considerado com erro
menor do que   0.05 .
Critérios de Convergência

Nos métodos iterativos são necessários
critérios que garantam a convergência.

Convergência para o Método de Gauss-Seidel:
1) Critério das linhas (já visto)
2) Critério de Sassenfeld

Os critérios acima estabelecem condições
suficientes para a convergência.
Método de Gauss-Seidel
Convergência - Critério de Sassenfeld

Sejam
| a12 |  | a13 |    | a1n |
1 

| a11 |
n
| a1 j |
|a
j 2
11
|
e
| ai1 | 1  | ai 2 |  2    | aii1 |  i 1  | aii1 |   | ain |
i 
| aii |
[
i 1
| a
j 1
ij
| j 
n
| a
j i 1
ij
| ]/ | aii | i  2,3,  n
Critério de Sassenfeld

Seja
  max{ i }
1i  n
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.
Exemplos
 x1  0.5 x 2  0.1x3  0.1x 4  0.2

0.2 x1  x 2  0.2 x3  0.1x 4  2.6

 0.1x1  0.2 x 2  x3  0.2 x 4  1.0

0.1x1  0.3x 2  0.2 x3  x 4  2.5
Seja o sistema:
1  [
4
| a
1j
|] / | a11 | [| a12 |  | a13 |  | a14 | ]/ | a11 | [0.5  0.1  0.1] / 1  0.7
j 2
2  [
2 1
| a
2j
| j 
j 1
4
| a
2j
| ]/ | a 22 | [| a 21 | 1  | a 23 |  | a 24 | ]/ | a 22 |
j  2 1
 [0.2  0.7  0.2  0.1] / 1  0.44
3  [
31
| a
3j
| j 
j 1
4
| a
3j
| ]/ | a 33 | [| a 31 | 1  | a 32 |  2  | a 34 | ]/ | a 33 |
j 31
 [0.1  0.7  0.2  0.44  0.2] / 1  0.358
4  [
4 1
| a
j 1
4j
| j 
4
| a
4j
| ]/ | a 44 | [| a 41 | 1  | a 42 |  2  | a 43 |  3 ] / | a 44 |
j  4 1
 [0.1  0.7  0.2  0.44  0.2  0.358] / 1  0.274
Exemplos

Então,
  max{ i }  0.7  1
1i  n
de modo que o método de Gauss-Seidel
converge.
Exemplos
2. Seja o sistema:
2 x1  x 2  3x3  9

  x 2  x3  1
x
 3x3  3
 1
Neste caso, 1  [1  3] / 2  2  1
Trocando a 1ª equação pela terceira,
 3x3  3
 x1

  x 2  x3  1
2 x  x  3x  9
2
3
 1
Nesta disposição: 1  [0  3] / 1  3  1
Exemplos
2. Agora se trocarmos a 1ª coluna pela
terceira,
 x1  3
3x3

1
 x3  x 2 
3x  x  2 x  9
2
1
 3
Nesta disposição:
1  [1  1] / 3  1 / 3
 2  [1  (1 / 3)  0] / 1  1 / 3
 3  [3  (1 / 3)  1  (1 / 3) // 2  2 / 3
  max{ i }  2 / 3  1
1i  n
Garantia de
convergência
Exemplos
3.


 x1  x 2  3
Seja o sistema: 
 x1  3x 2  3
O método de Gauss-Seidel gera uma seqüência
convergente, apesar do crit´rio das linhas não ser
satisfeito.
Pelo critério de Sassenfeld
1  1 / 1  1
2  11/ 3  1/ 3
O critério de Sassenfeld
não é satisfeito.
O critério de Sassenfeld também é
suficiente, mas não necessário.
Metodos Iterativos - Comparação
 x1  x 2  3
Seja o sistema:  x  3x  3
2
 1
x1( k 1)  3  x 2( k )
Método de Gauss-Jacobi:
x 2( k 1)

1
 3  x1( k )
3

Temos a seqüência:
x
( 0)
 0
 3
 2
 1 
 4 / 3
(1)
( 2)
(3)
( 4)
 , x  

   , x    , x    , x  
 0
 1
 2
 5 / 3
 4 / 3
Metodos Iterativos - Comparação
 x1  x 2  3
Seja o sistema: 
 x1  3x 2  3
x1( k 1)  3  x 2( k )
Método de Gauss-Seidel:
x 2( k 1)

1
 3  x1( k 1)
3

Temos a seqüência:
x
( 0)
 0
 3
 1 
 5/3 
(1)
( 2)
( 3)
 , x  

   , x    , x  
 0
 2
 4 / 3
14 / 9 
Metodos Iterativos - Comparação

Comentário1: As duas seqüências convergem para a
solução exata do sistema x  1.5 1.5 . Vejamos,
( 4)
x
a) Gauss-Jacobi : GJ  1.33 1.33
b) Gauss-Seidel: xGS (3)  1.67 1.56
 Comentário 2: A convergência do Método de GaussSeidel é mais rápida, por construção do método.
 Comentário 3: Embora a ordem das equações num
sistema linear não mude a solução exata, as seqüências
geradas pelos Métodos de Gauss-Jacobi e Gauss-Seidel
dependem fundamentalmente da disposição das equações
Métodos Direto e Iterativos
Comparação
1) Convergência:

Os Métodos Diretos são processos finitos
portanto fornecem solução para qualquer
sistema linear não-singular.

Os Métodos Iterativos têm convergência
assegurada sob certas condições.
Métodos Direto e Iterativos
Comparação
2) Esparsidade da Matriz A :
Em problemas reais, como a discretização de EDO’s pelo
Método de Elementos Finitos ou Diferenças Finitas, as
matrizes dos coeficientes tornam-se esparsas. A forma de
armazenamento destes dados tira proveito da esparsidade.

Métodos diretos em sistemas esparsos provocam o
preenchimento da matriz e no processo de Eliminação
(escalonamento) geram elementos não-nulos, onde originalmente
tínhamos elementos nulos. Técnicas especiais de pivoteamento
reduzem este preenchimento. Fatoramento LU dão bons
resultados. Algumas situações estes métodos não são possíveis.

Métodos iterativos não alteram a estrutura da matriz dos
coeficientes. Vantagem.
Métodos Direto e Iterativos
Comparação
A
3) Erros de Arredondamento

Métodos Diretos têm problemas de
arredondamento. Técnicas de Pivoteamento
amenizam tais erros.
 Métodos iterativos têm menos erros de
arredondamento, quando a convergência
estiver assegurada.
Lista de Métodos para
Sistemas Lineares
 Fazer exercícios 3, 5, 9,14, 22, 29 do
livro texto.