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
Sistemas Lineares - Métodos
Iterativos




É 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étodo mais apropriado para esse tipo de sistema 
métodos iterativo de Gauss-Seidel.
2
Métodos Iterativos

partem de um vertor de com uma solucão inicial


a cada iteracão:


obtem-se um outro vetor de solucões “melhoradas”, obtido por
substituicão no sistema de equacões (modificado para o método)
calcula-se o erro de todas as variáveis


i.e. valor inicial para todas as variáveis
até que todos os erros sejam menores que Epsilon
dependendo de “certas” condicões o método irá convergir para a solucão
do sistema de equacões
3
Métodos Iterativos
vetor
solucão
inicial X°
Mais um vetor
solucão X²
Novo vetor
solucão X¹
último
vetor
solucão
x 01
x 11
x 12
x1
x 02
x 12
x 22
x2
x 03
x 04
⋮
x 0n
x 13
x 14
⋮
x 1n
x 23
x 24
⋮
x n2
x3
x4
⋮
xn
4
Métodos Iterativos


Notacão:
k
 x
i
 valor da variável x na k-ézima iteracão
i
“erro” da variável xi na k-ézima iteracão:
k - x k-1 |
 | x
i
i

i.e. valor da variável na iteracão atual menos o seu
valor na iteracão anterior
5
Métodos Iterativos


Outra vantagem destes métodos  não são tão suscetíveis
ao acúmulo de erros de arredondamento como o método de
Eliminação de Gauss.
É importante lembrar que:

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 disso, também é preciso ter cuidado com a
convergência desses métodos.
6
Sistemas de Equações Lineares
Métodos Iterativos

Transforma o sistema linear Ax=b em x = Cx +g




A: matriz dos coeficientes, n x m
x: vetor das variáveis, n x 1;
b: vetor dos termos constantes, n x 1.
Métodos utilizados:
 Gauss-Jacobi
 Gauss-Seidel
 C: matriz n x n
 g: vetor n x 1
7
Sistemas de Equações Lineares
Método de Gauss-Jacobi

Conhecido
x(0)
(aproximação
inicial)
obtém-se
consecutivamente os vetores:
x 1 =Cx 0 +g,
x 2 =Cx 1 +g,
pr imeir a a pr oxima çã o
segunda a pr oxima çã o , etc .
 De um modo geral, a aproximação x(k+1) é calculada
pela fórmula
x(k+1) = C x(k)+g, k=0, 1, ...
8
Sistemas de Equações Lineares
Método de Gauss-Jacobi
 Da primeira equação do sistema
a11 x1 + a12 x2 + ... +a1n xn = b1
obtém-se
x1 = (1/a11) (b1
- a12 x2 - ... -a1n xn)
analogamente x2 = (1/a22) (b2 - a21 x1 -
.
.
.
.
... -a2n xn)
xn = (1/ann) (bn - an1 x1 - ... - an,n-1 xn-1
)
9
Sistemas de Equações Lineares
Método de Gauss-Jacobi
 Desta forma para
C=
g=
x= Cx+g
0
- a12 /a11 ...
- a1n /a11

...
- a2n /a22
 - a21 /a22 0
.
.
.


- an1 /ann - an2 /ann
0
(
b1 /a11
b2 /a22
. . . bn




/ann ) -1
10
Sistemas de Equações Lineares
Método de Gauss-Jacobi - Critério de parada
 Distância entre duas iterações
d(k) = max xi(k) - xi(k-1) 
 Critério de parada
dr(k) = d(k)/ (max xi(k) ) < 
11
Sistemas de Equações Lineares
Método de Gauss-Jacobi - EXEMPLO
 Seja o sistema
10 x1 + 2x2 + 3x3 = 7
x1 + 5x2 + x3 = -8
2x1 + 3x2 = 10x3 = 6
C=




0
- 2/10 - 1/10 
-1/5 0
- 1/5 

-1/5 – 3/10 0

g=
 -7/10

 -8/5
 -6/10




12
Sistemas de Equações Lineares
Método de Gauss-Jacobi - EXEMPLO
x0 =
Com
C=




 0,7 
 -1,6 


 0,6 
- 2/10 - 1/10 
-1/5 0
- 1/5 

-1/5 – 3/10 0

e  = 0,05
0
g=
 -7/10

 -8/5
 -6/10




13
Sistemas de Equações Lineares
Método de Gauss-Jacobi - EXEMPLO
obtemos
x(1) = Cx(0) + g
 = 0,05
 0,96 
 -1,86 
=

 0,94 
|x1(1) – x1(0)| = 0,26
|x2
(1)
– x2
(0)|
= 0,26
dr(1) = 0,34/ (max xi(1) )
= 0,1828 > 
|x3(1) – x3(0)| = 0,34
14
Sistemas de Equações Lineares
Método de Gauss-Jacobi - EXEMPLO
 0,978 
x(2) =  -1,98 


 0,966 
 0,9997 
x(3) =  -1,9888 


 0,984
 = 0,05
dr(1) = 0,12/ 1,98 = 0,0606 > 
dr(1) = 0,0324/ 1,9888 = 0,0163 < 
15
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
+1
x 1k +1 , .. . ,x kj−1
x kj+ 1 , .. . ,x kn
x kj +1
usa-se todos os valores
que já foram calculados e os valores
restantes.
16
Métodos Iterativos –
Gauss Seidel
Descrição do Método

Seja o seguinte sistema de equações:
a 11 . x 1
a 12 . x 2
a 13 . x 3
. ..
a 1n− 1 . x n− 1
a 1n− 1 . x n = b 1
a 21 . x 1
a 22 . x 2
a 23 . x 3
. ..
a 2n− 1 . x n− 1
a 2n− 1 . x n = b 2
a 31 . x 1
a 32 . x 2
a 33 . x 3
. ..
a 3n− 1 . x n− 1
a 3n− 1 . x n = b 3
.. .
a n n− 1 . x n− 1
a nn . x n = b n
⋮
an . x 1
1
an . x 2
2
an . x3
3
1
17
Métodos Iterativos –
Gauss Seidel

Isolando xi a partir da linha i, tem-se:
x1=
1
b 1 − a 1 2 . x 2 − a 1 3 . x 3 − a 1, n − 1 . x n − 1 − a 1 n . x n
a 11
x2=
1
b 2 − a 2 1 . x 1 − a 2 3 . x 3 − a 2, n − 1 . x n − 1 − a 2 n . x n
a 22
x3=
1
b 3 − a 3 1 . x 2 − a 3 2 . x 2 − a 3, n − 1 . x n − 1 − a 3 n . x n
a 33
⋮
xn=
1
b n − a n . x 1 − a n . x 2 − . . . − a n , n− 1 . x n − 1
a nn
2
1
18
Métodos Iterativos –
Gauss Seidel

O processo iterativo é obtido a partir das equações, fazendo:
k +1 1
x1 =
a 11
b 1 − a 12 . x 2k − a 13 . x k3 − . . .− a 1, n − 1 . x kn− 1 − a 1n . x nk
x 2k + 1 =
1
b 2 − a 21 . x 1k + 1 − a 23 . x 3k − .. .− a 2, n − 1 . x kn− 1 − a 2n . x kn
a 22
x 3k + 1 =
1
b 3 − a 31 . x 1k + 1 − a 32 . x 2k + 1 − . ..− a 3, n − 1 . x kn− 1 − a 3n . x nk
a 33
k +1 1
xn =
a nn
b n − a n1 . x k1 + 1 − a n2 . x k2 + 1 − . ..− a n,n− 1 . x kn−+11
19
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
k
1 
M

R 



1



k
1
k
x

x
i
i
k
1
x
i
se
k
1
se x
0
i
k
1
k
x

x
0
i
i 
k
1

0
x
i
se 
k

x
 i 0
Fim do processo iterativo - valor de MRk+1 pequeno o bastante
para a precisão desejada.
20
Métodos Iterativos –
Gauss Seidel
Exemplo: Resolva:
Solução:
21
Métodos Iterativos –
Gauss Seidel
xk
M xk
M yk
yk
zk
M 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
22
Método de Gauss-Seidel Convergência


Processo iterativo  a convergência para a solução exata não é
garantida para qualquer sistema.
No sistema de equações lineares existem certas condições que,
se forem satisfeitas irão garantir a convergência do método.

essas condições são SUFICIENTES para convergencia,

mas NÃO são condições necessárias,


Critérios de
significa que seria possível a convergência do método para um certo
sistema, mesmo não que este não obedeça às condições abaixo:
As condições de convergência são os critérios:
 Critério de Sassenfeld
 Critério das Linhas.
23
Método de Gauss-Seidel Convergência

Critérios de
OBS:
 Se um sistema linear obedece aos critérios de Sassenfeld
então também obedece aos critérios de linha (diagonal
dominate).
24
Critério de Sassenfeld

Sejam as quantidades i dadas por:
n
1
β 1 =∣ ∣⋅ ∑ ∣a 1 j∣
a 1 1 j= 2
e
β i =∣
1
∣⋅
a ii
[
i− 1
n
∑ ∣a ij∣⋅ β j ∑
j= 1
j= i+ 1
∣a ij∣
]
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:
β
i
for menor que 1 (M<1).
25
Critério de Sassenfeld

Exemplo: Seja A, a matriz dos coeficientes e b o vetor dos
termos constantes dados por:
a 11 a 12 a 13 a 14
a 21 a 22 a 23 a 24
a 31 a 32 a 33 a 34
a 4 1 a4 2 a 4 3 a 4 4
b1
b2
b3
b4
1
β 1 =∣ ∣⋅ a 1 2 + a 1 3 + a 1 4
a 11
1
β 2 =∣ ∣⋅ ∣a 2 1∣ β 1 ∣a 2 3∣ ∣a 2 4∣
a 22
1
β 3 =∣ ∣⋅ ∣a 3 1∣ β 1 ∣a 3 2∣ β 2 ∣a 3 4∣
a 33
1
β 4 = ∣ ∣⋅ ∣a 4 1∣ β 1 ∣a 4 2∣ β 2 ∣a 4 3∣ β 3
a 44
26
Critério de Sassenfeld
Exemplo: Mostre que a solução do sistema linear dado
pelas equações:
convergirá pelo método de Gauss-Seidel.
27
Critério de Sassenfeld

Solução: critério de Sassenfeld
 calcular os valores das quantidades  .
i
A
B
1
β 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
desse sistema irá convergir usando
i
o método de Gauss-Seidel.
β = 0 .7
28
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.
29
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⋅ x 1 + x 2 − 0 . 2⋅ x 3 0 . 2⋅ x 4 = 0 . 4
0 . 6⋅ x 1 3⋅ x 2 − 0 .6⋅ x 3 − 0 .3⋅ x 4 = − 7 .8
− 0 . 1⋅ x 1 − 0 . 2⋅ x 2 + x 3 0 . 2⋅ x 4 = 1 . 0
0 . 4⋅ x 1 1 .2⋅ x 2 0 .8⋅ x 3 4⋅ x 4 = − 10 .0
∣a 1 1∣= 2
∣a 2 2∣= 3
∣a 3 3∣= 1
∣a 4 4∣= 4
∣a 1 2∣
∣a 2 1∣
∣a 3 1∣
∣a 4 1∣
∣a 1 3∣
∣a 2 3∣
∣a 3 2∣
∣a 4 2∣
∣a 1 4∣= 1 0 . 2 0 .2 = 1 . 4
∣a 2 4∣= 0 . 6 0 . 6 0 . 3 = 1 . 5
∣a 3 4∣= 0 . 1 0 . 2 0 . 2 = 0 . 5
∣a 4 3∣= 0 . 4 1 . 2 0 .8 = 2 . 4
n
a
j1
ji
ij
 aii
para i=1, 2, 3, 4.
30
Considerações Finais
É importante saber que:

Os Critérios são condições suficientes, porém não
necessárias, para a convergência do método de GaussSeidel para um dado sistema linear  Isso significa que um
sistema pode não satisfazer esses critérios e ainda
convergir.

Um sistema pode não satisfazer o critério das linhas e
satisfazer o critério de Sassenfeld, o que garantirá sua
convergência.
31
Considerações Finais
Exemplo:
Seja o sistema:
1 0⋅ x 1 + x 2 = 2 3
6⋅ x 1 2⋅ x 2 = 1 8
Note que esse sistema não satisfaz o critério das linhas, pois:
∣a 22∣= 2 ∣a 21∣= 6
porém, ele satisfaz o critério de Sassenfeld:
1
∣⋅ 1 = 0 .1
10
1
β 2 =∣ ∣⋅ 6⋅ 0 .1 = 0 . 3
2
β 1 =∣
β i= 0 . 3
1
 Convergência garantida.
32
Considerações Finais
Outra observação importante

A ordem com que as equações aparecem no sistema.

Apesar da ordem das equações não alterar a solução do
sistema, ela pode alterar a convergência do mesmo pelo
método da Gauss-Seidel.
33
Considerações Finais
Exemplo:
Seja o sistema:
− 4⋅ x 1 1 0⋅ x 2 = 1 9
5⋅ x 1 3⋅ x 2 = 1 5
 Na forma como o sistema está representado, ele não
satisfaz o critério das linhas (verifique isso), portanto sua
convergência não é garantida.
 Porém, trocando-se a ordem das duas equações, o
sistema satisfaz esse critério, e sua convergência pelo
método de Gauss-Seidel é garantida (verifique isso
também).
34