Cálculo Numérico
Módulo III
Sistemas de Equações
Lineares (SEL ) – Parte II
Profs.: Bruno Correia da Nóbrega Queiroz
José Eustáquio Rangel de Queiroz
Marcelo Alves de Barros
Métodos Iterativos

Motivação I

Ocorrência em larga escala de sistemas lineares
em cálculos de Engenharia e modelagem científica

Exemplos:

Simulações de processos químicos

Simulações de dispositivos e circuitos

Modelagem
de
geoambientais
processos

Análise estrutural

Biologia estrutural

Modelagem de processos físicos
geocientíficos
e
2
Métodos Iterativos

Motivação II


Tendência à existência de matrizes de coeficientes à
grandes e esparsas

Grandes  Comum para n > 100.000

Esparsas  Maioria dos coeficientes nulos
Resolução
diretos

de
sistemas
esparsos
por
métodos
Processos de triangularização e fatoração  Onerosos,
por não preservarem a esparsidade original, que pode
ser útil por facilitar a resolução do sistema.
3
Métodos Iterativos

Motivação III

Métodos mais apropriados para a resolução de
sistemas de natureza esparsa  Métodos iterativos

Gauss-Jacobi

Gauss-Seidel
4
Métodos Iterativos

Sistemas Esparsos no MATLAB

>>help issparse
 Teste de esparsidade

>>help sparse
 Conversão de matriz cheia

>>help full
 Conversão de matriz esparsa

Geração de Matrizes Esparsas:
em matriz esparsa
em matriz cheia

>>help sprand

>>help sparndsym  Geração de matriz esparsa
aleatória

Geração
de
matriz
esparsa
simétrica aleatória
5
Métodos Iterativos

Métodos para Sistemas Esparsos no MATLAB

>> help pcg

Gradiente Conjugado

>> help cgs

Gradiente

>> help bicg

Gradiente BiConjugado (BiCG)

Quadrático (CGS)
>>help bicgstab  Gradiente
Estabilizdo (BiCGSTAB)
Conjugado
BiConjugado

>>help gmres

Resíduo Mínimo Generalizado

>>help qmr

Resíduo Quase Mínimo (QMR)
(GMRES)
6
Métodos Iterativos

A partir de uma estimativa inicial xi0, consistem em
encontrar uma seqüência de estimativas xik que
convirja para uma solução do SEL após um número
suficientemente grande de iterações.
 x1(0) 


 x (0 ) 
 2 
 (0 ) 
x3 


  


 x (n0) 
 x1(1) 


 x (1) 
 2 
 (1) 
x3 


  


 x (n1) 
 x1(2) 


 x (2) 
 2 
 (2) 
x3 


  


 x (n2) 

 x1(k ) 


 x (k ) 
 2 
 (k ) 
x3 


  


 x (nk ) 
7
Métodos Iterativos


Vantagem  Menos suscetíveis ao acúmulo de
erros de arredondamento do que o método de
Eliminação de Gauss.
Lembretes importantes:


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.
Além disto, também é preciso ter cuidado com a
convergência destes métodos.
8
Sistemas de Equações Lineares
Métodos Iterativos


Transformação
x = Cx +g
do
sistema
linear

A: matriz dos coeficientes, n x m

x: vetor das variáveis, n x 1;

b: vetor dos termos constantes, n x 1;

C: matriz, n x n; e

g: vetor, n x 1.
Ax=b
em
Métodos a estudar

Gauss-Jacobi

Gauss-Seidel
9
Método de Gauss-Jacobi
Método de Gauss-Jacobi

Conhecida a estimativa inicial,
consecutivamente os vetores:
x(0),
obtém-se
x(1)  Cx(0)  g,
(primeiraaproximaçã
o)
x(2)  Cx(1)  g,
(segundaaproximaçã
o)

x(k)  Cx(k 1)  g, (k - ésimaaproximaçã
o)
 De um modo geral, a aproximação x(k+1) é calculada
pela fórmula:
x(k+1) = C x(k)+g, k=0, 1, ...
10
Método de Gauss-Jacobi
 Método de Gauss-Jacobi
 Da primeira equação do sistema:
a11 x1 + a12 x2 + ... +a1n x2 = b1
obtém-se: x1 = (1/a11) (b1 - a12 x2 - ... -a1n x2)
e, analogamente,
x2 = (1/a22) (b2 - a21 x1 - ... -a2n xn)

xn = (1/ann) (bn - an1 x1 - ... - ann-1 xn-1)
11
Método de Gauss-Jacobi
 Método de Gauss-Jacobi
 Desta forma, para x = C x + g, obtém-se:

a12 a11 a13 a11
0

  a21 a22
 a23 a22
0

C    a31 a33  a32 a33
0





 a a
 n1 nn  an2 ann  an3 ann
 a1n a11 

  a2n a22 



a
a
3
n
33


 




0

 b1 


a
 11 


b
 2 
 a22 


e g   b3 


 a33 


  


 bn 
a 
 nn 
12
Método de Gauss-Jacobi
 Método de Gauss-Jacobi
 Distância entre duas iterações
(k-1)
d(k)  max x(k)
x
i
i
 Critério de Parada
d(k)

r
d(k)
max x
(k )
i


13
Método de Gauss-Jacobi
 Método de Gauss-Jacobi – Exemplo 13
 Seja o sistema:
10 x1  2x2  3x3  7
x1  5x2 
x3  8
2x1  3x2  10x3  6
 Determinação de C e g
 0
C  -1/5
-1/5
- 2/10 - 3/10
0
-1/5
– 3/10
0 

 7 
 
 10 
 
8
g  
 5 
 
 6 
 
 10 
14
Método de Gauss-Jacobi
 Método de Gauss-Jacobi – Exemplo 13
 Assim, considerando como estimativa inicial:
 0,7 
x 0  - 1,6
 0,6 


e  = 0,05, obtém-se:
0,84
x(1)  Cx(0)  g  1,34
0,94


|x1(1) – x1(0)| = 0,14
e
|x2(1) – x2(0)| = 2,94
|x3(1) – x3(0)| = 0,34
15
Método de Gauss-Jacobi
 Método de Gauss-Jacobi – Exemplo 13
 Assim:
0,150
0,91
(2)
(2)
(1)


 0,7315  
x  Cx  g  1,244  dr 
0,030
1,244


e, analogamente:
0,4422
0,32
(3)
(3)
(2)


x  Cx  g  1,5640  dr 
 0,2046  
0,1968
1,5640


16
Método de Gauss-Jacobi
 Método de Gauss-Jacobi – Exemplo 13
 Igualmente:
0,3282
0,1544
(4)
(4)
(3)


 0,1049  
x  Cx  g  1,4722  dr 
0,0424
1,4722


e, finalmente:
0,3929
0,0647
(5)
(5)
(4)


 0,0424  
x  Cx  g  1,5259  dr 
1,5259
0,0927


17
Método de Gauss-Seidel
Método de Gauss-Seidel

Similarmente ao método de Gauss-Jacobi, conhecida a
estimativa inicial, x(0), obtém-se consecutivamente os
vetores x(1), x(2), ..., x(k)
 Todavia, ao se calcular xj(k+1), usa-se todos os valores
x1(k+1), x2(k+1), ..., xj-1(k+1) que já foram calculados e os
valores xj+1(k), xj+2(k), ..., xn(k) restantes.
18
Método de Gauss-Seidel
Método de Gauss-Seidel

Descrição I

Seja o seguinte sistema de equações:
a11.x1  a12.x2  a13.x 3    a1n 1.xn 1  a1n.xn  b1
a21.x1  a22.x2  a23.x 3    a2n 1.xn 1  a2n.x n  b2
a31.x1  a32.x2  a33.x 3    a3n 1.xn 1  a3n.xn  b3



an1.x1  an2 .x2  an3 .x 3    ann1.xn 1  ann.x n  bn
19
Método de Gauss-Seidel
Método de Gauss-Seidel

Descrição II

Isolando xi a partir da linha i, tem-se:
x1 
1
b1  a12.x2  a13.x 3    a1n 1.x n 1  a1n.x n 
a11
x2 
1
b2  a21.x1  a23.x 3    a2n 1.x n 1  a2n.x n 
a22
x3 
1
b3  a31.x2  a32.x2    a3n 1.x n 1  a3n.x n 
a33

xn 
1
bn  an1.x1  an2 .x2    ann1.xn 1 
ann
20
Método de Gauss-Seidel
Método de Gauss-Seidel

Descrição III

O processo iterativo se dá a partir das equações:
x1k 1 
x
k 1
2

1
b1  a12.x2k  a13.x k3  ...  a1,n 1.x kn 1  a1n .x kn
a11


1

b2  a21.x1k 1  a23.x k3  ...  a2 ,n 1.x kn 1  a2n .x kn
a22


x k3 1 
1
b3  a31.x1k 1  a32 .x2k 1  ...  a3 ,n 1.x kn 1  a3n.x kn
a33
x kn 1 
1
bn  an1.x1k 1  an2 .x2k 1  ...  an,n 1.x kn 11
ann



21
Método de Gauss-Seidel
Método de Gauss-Seidel

Critério de Parada I

Diferença relativa entre duas iterações consecutivas,
dada por:
k 1
R
M

 Máx.
1in

 0



1


x ki 1  x ki
k 1
,
se
x
 0
i
k 1
xi
, se x ki 1

xki  0
 x ki 1  0

, se 
 x ki
 0
22
Método de Gauss-Seidel
Método de Gauss-Seidel

Critério de Parada II

Fim do processo iterativo  Valor de MRk+1
suficientemente pequeno para a precisão desejada
23
Método de Gauss-Seidel
 Método de Gauss-Seidel – Exemplo 14
 Resolver:
5x  y  z  5
3x  4y  z  6
3x  3y  6z  0,
com
MRk  5.102.
 Solução:
1
5  y  z
5
1
6  3x  z
y
4
1
 3x  3y   z   1 x  y 
z
6
2
x
24
Método de Gauss-Seidel
 Método de Gauss-Seidel – Exemplo 14
 Quadro de resultados do processo iterativo
M yk
zk
M zk
M Rk
0
-
1
-
-
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
xk
M xk
-1
-
0,8
x = 1,002
yk
y = 0,998
z = -1
25
Método de Gauss-Seidel
 Método de Gauss-Seidel – Exemplo 14
 Verificação (substituição no sistema)
x = 1,002
y = 0,998
z = -1
5.(1,002) + 1.(0,998) + 1.(-1) = 5,008  5 OK
3.(1,002) + 4.(0,998) + 1.(-1) = 5,998  6 OK
3.(1,002) + 3.(0,998) + 6.(-1) = 0
OK
26
Método de Gauss-Seidel
 Critérios de Convergência
 Processo iterativo  Convergência para a solução
exata não garantida para qualquer sistema.
 Necessidade de determinação de certas condições
que devem ser satisfeitas por um SEL para a garantia
da convergência do método.
 Critérios de
convergência
determinação
das
condições
de
 Critério de Sassenfeld
 Critério das Linhas
27
Método de Gauss-Seidel
 Critério de Sassenfeld I
 Sejam as quantidades i dadas por:
1
1 

a11
n

j 2
a1 j
e

1 
i 

aii 

para i = 2, 3, ..., n
i 1

j 1
n
aij   j 

j  i 1

aij 


n - ordem do sistema linear que se deseja resolver
aij - coeficientes das equações do sistema
28
Método de Gauss-Seidel
 Critério de Sassenfeld II
 Este critério garante que o método de Gauss-Seidel
convergirá para um dado SEL se a quantidade M,
definida por:
M  max 
1in
i
for menor que 1 (M<1).
29
Método de Gauss-Seidel
 Critério de Sassenfeld III
 Exemplo 15: Seja A a matriz dos coeficientes e b o
vetor dos termos constantes, dados por:
a11
1 
1
 a12  a13  a14 
a11
2 
1
 a21 1  a23  a24
a22
3 
1
 a31 1  a32 2  a34
a33
4 
1
 a41 1  a42 2  a43  3
a44
for menor que 1 (M<1).
a12 a13 a14 b1
a21 a22 a23 a24 b2
a31 a32 a33 a34 b3
a41 a42 a43 a44 b4






30
Método de Gauss-Seidel
 Critério de Sassenfeld IV
 Exemplo 15: Seja A a matriz dos coeficientes e b o
vetor dos termos constantes, dados por:
a11 a12 a13 a14
b1
a21 a22 a23 a24 b2
a31 a32 a33 a34 b3
a41 a42 a43 a44 b4
1 
1
 a12  a13  a14 
a11
2 
1
 a21 1  a23  a24
a22
3 
1
 a31 1  a32 2  a34
a33
4 
1
 a41 1  a42 2  a43  3
a44






Mostrar que a solução do SEL a seguir convergirá
pelo método de Gauss-Seidel.
31
Método de Gauss-Seidel
 Critério de Sassenfeld V
 Exemplo 15:
2,0  x1 
0,6  x1 
x2  0,2  x 3  0,2  x 4 
3  x2  0,6  x 3  0,3  x 4  7,8
 0,1  x1  0,2  x2 
0,4  x1 
0,4
x 3  0,2  x 4 
1,0
1,2  x2  0,8  x 3  4,0  x 4  10,0
32
Método de Gauss-Seidel
A
b
 Critério de Sassenfeld VI
 Exemplo 15: Solução
2.0
1.0 - 0.2
0.2
0.6
3.0 - 0.6 - 0.3
1
 1  0,2  0,2  0,7
- 0.1 - 0.2
2
1
0.4
1.2
2   0,6  0,7  0,6  0,3  0,44
3
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
1 
M  max i  0,7
1in
1.0
0.8
0.4
- 7.8
0.2
1.0
4.0 - 10.0
M < 1  Convergência da
solução do sistema a partir do
método de Gauss-Seidel
33
Método de Gauss-Seidel
 Critério das Linhas
 Segundo este critério, um determinado sistema irá
convergir pelo método de Gauss-Seidel, se:
n
a
ij
 aii , para i  1, 2, 3, ..., n.
j 1
ji
34
Método de Gauss-Seidel
 Critério das Linhas
 Exemplo 16: O SEL do Exemplo 14 satisfaz o Critério
das Linhas, sendo a verificação quase imediata, se for
observado que:
a11  2  a12  a13  a14  1  0,2  0,2  1,4
a22  3  a21  a23  a24  0,6  0,6  0,3  1,5
a33  1  a31  a32  a34  0,1  0,2  0,2  0,5
a44  4  a41  a42  a43  0,4  1,2  0,8  2,4
n
a
ij
 aii para i  1, 2, 3, 4.
j 1
ji
35
Considerações Finais

Tanto o Critério de Sassenfeld quanto o Critério
das Linhas são condições suficientes, porém não
necessárias, para a convergência do método de
Gauss-Seidel para um dado SEL


Um dado SEL pode não satisfazer estes critérios e
ainda convergir
Um sistema pode não satisfazer o Critério das
Linhas, porém sua convergência será garantida se
satisfizer o Critério de Sassenfeld
36
Método de Gauss-Seidel
 Critério das Linhas x Critério de Sassenfeld
 Exemplo 17: Seja o seguinte SEL:
10  x1 
x2  23
6  x1  2  x2  18
 O Critério das Linhas não é satisfeito, visto que:
a22  2  a21  6
 Todavia, o Critério de Sassenfeld é satisfeito, uma
vez que:
1 
1
 1  0,1
10
e
2 
1
 6  0,1  0,3
2
37
Método de Gauss-Seidel
 Critério das Linhas x Critério de Sassenfeld
 Exemplo 17: Assim sendo, a convergência do SEL é
garantida.
38
Considerações Finais

Embora não altere a solução do SEL, a ordem de
aparecimento das equações pode alterar sua
convergência pelo método da Gauss-Seidel.

Exemplo 18: Seja o SEL:
4  x1  10  x2  19
5  x1  3  x2  15


Observa-se que na ordem atual de aparecimento das
equações, o SEL não satisfaz o Critério das Linhas
(verificar!!!); logo, sua convergência não é garantida.
A inversão da ordem das duas equações do SEL fará com
que o Critério das Linhas seja satisfeito e sua
convergência pelo método de Gauss-Seidel garantida
(verificar também!!! ).
39
Bibliografia
 Ruggiero, M. A. Gomes & Lopes, V. L. da R. Cálculo
Numérico: Aspectos teóricos e computacionais.
MAKRON Books, 1996, 2ª ed.
 Asano, C. H. & Colli, E. Cálculo Numérico:
Fundamentos e Aplicações. Departamento de
Matemática Aplicada – IME/USP, 2007.
 Sanches, I. J. & Furlan, D. C. Métodos Numéricos.
DI/UFPR, 2006.
 Paulino, C. D. & Soares, C. Erros e Propagação de
Erros, Notas de aula, SE/ DM/ IST [Online]
http://www.math.ist.utl.pt/stat/pe/qeb/semestr
e_1_2004-2005/PE_erros.pdf [Último acesso 07
de Junho de 2007].
40