Métodos Iterativos para Resolução de Sistemas Lineares

Prévia do material em texto

GEX114 - Ca´lculo Nume´rico
Profa.Dra. Amanda Castro Oliveira
Departamento de Cieˆncias Exatas - DEX/UFLA
amanda@dex.ufla.br
Cap.3 Resoluc¸o˜es de Sistemas Lineares
Seja o Sistema Linear Ax = b , onde A = (aij) i , j = 1, 2, ..., n
A = matriz nxn, matriz dos coeficientes,
x = (xj)
t , j = 1, ..., n
vetor da inco´gnitas,
b = (bi )
t , i = 1, ..., n
vetor dos coeficientes independentes,
det(A) 6= 0
Garantia de soluc¸a˜o u´nica.
3.4 Me´todos Iterativos
Ja´ vimos alguns me´todos que, a menos de erros de arredondamento
fornecem a soluc¸a˜o do sistema apo´s um nu´mero finito de passos:
me´todos diretos.
Agora veremos me´todos que partindo de uma aproximac¸a˜o inicial,
atrave´s de iterac¸o˜es sucessivas, fornecem novas aproximac¸o˜es num
processo de convergeˆncia, sob determinadas condic¸o˜es sobre a matriz
A, para a soluc¸a˜o do sistema.
Os me´todos iterativos sa˜o convenientes para sistemas grandes e
esparsos que aparecem frequentemente na discretizac¸a˜o de equac¸o˜es
diferenciais.
3.4 Me´todos Iterativos
Ja´ vimos alguns me´todos que, a menos de erros de arredondamento
fornecem a soluc¸a˜o do sistema apo´s um nu´mero finito de passos:
me´todos diretos.
Agora veremos me´todos que partindo de uma aproximac¸a˜o inicial,
atrave´s de iterac¸o˜es sucessivas, fornecem novas aproximac¸o˜es num
processo de convergeˆncia, sob determinadas condic¸o˜es sobre a matriz
A, para a soluc¸a˜o do sistema.
Os me´todos iterativos sa˜o convenientes para sistemas grandes e
esparsos que aparecem frequentemente na discretizac¸a˜o de equac¸o˜es
diferenciais.
3.4 Me´todos Iterativos
Ja´ vimos alguns me´todos que, a menos de erros de arredondamento
fornecem a soluc¸a˜o do sistema apo´s um nu´mero finito de passos:
me´todos diretos.
Agora veremos me´todos que partindo de uma aproximac¸a˜o inicial,
atrave´s de iterac¸o˜es sucessivas, fornecem novas aproximac¸o˜es num
processo de convergeˆncia, sob determinadas condic¸o˜es sobre a matriz
A, para a soluc¸a˜o do sistema.
Os me´todos iterativos sa˜o convenientes para sistemas grandes e
esparsos que aparecem frequentemente na discretizac¸a˜o de equac¸o˜es
diferenciais.
3.4 Me´todos Iterativos
Ideia central: generalizar o me´todo do ponto fixo.
Seja o sistema linear Ax = b, onde:
A :matriz dos coeficientes nXn;
x :vetor das varia´veis nX1;
b :vetor dos termos constantes nX1.
Convertemos este sistema Ax = b num sistema do tipo:
x = Cx + g ,
C e´ uma matriz nXn e g e´ um vetor nX1.
φ(x) = Cx + g e´ uma func¸a˜o de iterac¸a˜o matricial.
3.4 Me´todos Iterativos
Ideia central: generalizar o me´todo do ponto fixo.
Seja o sistema linear Ax = b, onde:
A :matriz dos coeficientes nXn;
x :vetor das varia´veis nX1;
b :vetor dos termos constantes nX1.
Convertemos este sistema Ax = b num sistema do tipo:
x = Cx + g ,
C e´ uma matriz nXn e g e´ um vetor nX1.
φ(x) = Cx + g e´ uma func¸a˜o de iterac¸a˜o matricial.
3.4 Me´todos Iterativos
Partimos de um vetor aproximac¸a˜o inicial x (0) e constru´ımos
iterativamente os vetores:
x (1) = φ(x (0)) = Cx (0) + g
x (2) = φ(x (1)) = Cx (1) + g
...
x (k) = φ(x (k−1)) = Cx (k−1) + g
Se a sequeˆncia de aproximac¸o˜es x (0), x (1), · · · , x (k) e´ tal que
lim
k→∞
x (k) = α,
enta˜o α = Cα + g , isto e´, α e´ a soluc¸a˜o do sistema linear Ax = b.
3.4 Me´todos Iterativos
Partimos de um vetor aproximac¸a˜o inicial x (0) e constru´ımos
iterativamente os vetores:
x (1) = φ(x (0)) = Cx (0) + g
x (2) = φ(x (1)) = Cx (1) + g
...
x (k) = φ(x (k−1)) = Cx (k−1) + g
Se a sequeˆncia de aproximac¸o˜es x (0), x (1), · · · , x (k) e´ tal que
lim
k→∞
x (k) = α,
enta˜o α = Cα + g , isto e´, α e´ a soluc¸a˜o do sistema linear Ax = b.
3.4.2 Crite´rios de Parada
O processo iterativo deve ser repetido ate´ que o vetor x (k) esteja
suficientemente pro´ximo do vetor x (k−1)
Seja a distaˆncia entre x (k) e x (k−1) dada por:
d (k) = max
1≤i≤n
|x (k)i −(k−1)i |
ex.x (k) = (3, 4, 5) e x (k−1) = (3, 5, 8)
d (k) = max
1≤i≤n
|x (k)i −(k−1)i |
max{|3− 3|, |4− 5|, |5− 8|} = max{0, 1, 3} = 3
Assim, dada uma precisa˜o �, o vetor x (k) sera´ escolhido como x¯ ,
soluc¸a˜o aproximada do sistema linear Ax = b se d (k) < �.
3.4.2 Crite´rios de Parada
O processo iterativo deve ser repetido ate´ que o vetor x (k) esteja
suficientemente pro´ximo do vetor x (k−1)
Seja a distaˆncia entre x (k) e x (k−1) dada por:
d (k) = max
1≤i≤n
|x (k)i −(k−1)i |
ex.x (k) = (3, 4, 5) e x (k−1) = (3, 5, 8)
d (k) = max
1≤i≤n
|x (k)i −(k−1)i |
max{|3− 3|, |4− 5|, |5− 8|} = max{0, 1, 3} = 3
Assim, dada uma precisa˜o �, o vetor x (k) sera´ escolhido como x¯ ,
soluc¸a˜o aproximada do sistema linear Ax = b se d (k) < �.
3.4.2 Crite´rios de Parada
O processo iterativo deve ser repetido ate´ que o vetor x (k) esteja
suficientemente pro´ximo do vetor x (k−1)
Seja a distaˆncia entre x (k) e x (k−1) dada por:
d (k) = max
1≤i≤n
|x (k)i −(k−1)i |
ex.x (k) = (3, 4, 5) e x (k−1) = (3, 5, 8)
d (k) = max
1≤i≤n
|x (k)i −(k−1)i |
max{|3− 3|, |4− 5|, |5− 8|} = max{0, 1, 3} = 3
Assim, dada uma precisa˜o �, o vetor x (k) sera´ escolhido como x¯ ,
soluc¸a˜o aproximada do sistema linear Ax = b se d (k) < �.
3.4.2 Crite´rios de Parada
O processo iterativo deve ser repetido ate´ que o vetor x (k) esteja
suficientemente pro´ximo do vetor x (k−1)
Seja a distaˆncia entre x (k) e x (k−1) dada por:
d (k) = max
1≤i≤n
|x (k)i −(k−1)i |
ex.x (k) = (3, 4, 5) e x (k−1) = (3, 5, 8)
d (k) = max
1≤i≤n
|x (k)i −(k−1)i |
max{|3− 3|, |4− 5|, |5− 8|} = max{0, 1, 3} = 3
Assim, dada uma precisa˜o �, o vetor x (k) sera´ escolhido como x¯ ,
soluc¸a˜o aproximada do sistema linear Ax = b se d (k) < �.
3.4.2 Crite´rios de Parada
O processo iterativo deve ser repetido ate´ que o vetor x (k) esteja
suficientemente pro´ximo do vetor x (k−1)
Seja a distaˆncia entre x (k) e x (k−1) dada por:
d (k) = max
1≤i≤n
|x (k)i −(k−1)i |
ex.x (k) = (3, 4, 5) e x (k−1) = (3, 5, 8)
d (k) = max
1≤i≤n
|x (k)i −(k−1)i |
max{|3− 3|, |4− 5|, |5− 8|} = max{0, 1, 3} = 3
Assim, dada uma precisa˜o �, o vetor x (k) sera´ escolhido como x¯ ,
soluc¸a˜o aproximada do sistema linear Ax = b se d (k) < �.
3.4.2 Crite´rios de Parada
Para o teste do erro relativo calculamos a distaˆncia relativa dada por:
d
(k)
r =
d (k)
max
1≤i≤n
|x (k)i |
ex.x (k) = (3, 4, 5) e x (k−1) = (3, 5, 8)
d
(k)
r =
d (k)
max
1≤i≤n
|x (k)i |
=
3
max{3, 4, 5} =
3
5
3.4.2 Crite´rios de Parada
Para o teste do erro relativo calculamos a distaˆncia relativa dada por:
d
(k)
r =
d (k)
max
1≤i≤n
|x (k)i |
ex.x (k) = (3, 4, 5) e x (k−1) = (3, 5, 8)
d
(k)
r =
d (k)
max
1≤i≤n
|x (k)i |
=
3
max{3, 4, 5} =
3
5
3.4.3 Me´todo Iterativo de Gauss - Jacobi
Queremos transformar o sistema Ax = b em x = Cx + g .
Assumindo que aii 6= 0 ∀i temos:
a11x1+ a12x2+ · · · +a1nxn =
a21x1+ a22x2+ · · · +a2nxn =
...
an1x1+ an2x2+ · · · +annxn =
b1
b2
...
bn
Isolamos o vetor x da seguinte forma:
x
(k+1)
1 =
1
a11
(b1 − a12x (k)2 − a13x (k)3 − · · · − a1nx (k)n )
x
(k+1)
2 =
1
a22
(b2 − a21x (k)1 − a23x (k)3 − · · · − a2nx (k)n )
...
x
(k+1)
n =
1
ann
(bn − an1x (k)1 − an2x (k)2 − · · · − ann−x (k)n−1)
3.4.3 Me´todo Iterativo de Gauss - Jacobi
Queremos transformar o sistema Ax = b em x = Cx + g .
Assumindo que aii 6= 0 ∀i temos:
a11x1+ a12x2+ · · · +a1nxn =
a21x1+ a22x2+ · · · +a2nxn =
...
an1x1+ an2x2+ · · · +annxn =
b1
b2
...
bn
Isolamos o vetor x da seguinte forma:
x
(k+1)
1 =
1
a11
(b1 − a12x (k)2 − a13x (k)3 − · · · − a1nx (k)n )
x
(k+1)
2 =
1
a22
(b2 − a21x (k)1 − a23x (k)3 − · · · − a2nx(k)n )
...
x
(k+1)
n =
1
ann
(bn − an1x (k)1 − an2x (k)2 − · · · − ann−x (k)n−1)
3.4.3 Me´todo Iterativo de Gauss - Jacobi
De tal forma que
x
(k+1)
i =
1
aii
(bi −
n∑
j=1
j 6=i
aijx
(k)
j )
Como vetor aproximac¸a˜o inicial, x (0), podemos escolher qualquer
vetor,pois se o sistema convergir a escolha inicial na˜o sera´ relevante.
Resolva numericamente o sistema abaixo usando o me´todo de
Gauss-Jacobi. 
10x1 + 3x2 + x3 =
2x1 − 10x2 + 3x3 =
x1 + 3x2 + 10x3 =
14
−5
14
Para facilitar as contas tome x (0) = (0, 0, 0)t
3.4.3 Me´todo Iterativo de Gauss - Jacobi
De tal forma que
x
(k+1)
i =
1
aii
(bi −
n∑
j=1
j 6=i
aijx
(k)
j )
Como vetor aproximac¸a˜o inicial, x (0), podemos escolher qualquer
vetor,pois se o sistema convergir a escolha inicial na˜o sera´ relevante.
Resolva numericamente o sistema abaixo usando o me´todo de
Gauss-Jacobi. 
10x1 + 3x2 + x3 =
2x1 − 10x2 + 3x3 =
x1 + 3x2 + 10x3 =
14
−5
14
Para facilitar as contas tome x (0) = (0, 0, 0)t
3.4.3 Me´todo Iterativo de Gauss - Jacobi
Sistema de iterac¸a˜o
xk+11 =
1
10
(14− 3xk2 − xk3 )
xk+12 =
1
−10(−5− 2x
k
1 − 3xk3 )
xk+13 =
1
10
(14− xk1 − 3xk2 )
k = 0
x11 =
1
10
(14− 3(0)− (0)) = 1.4
x12 =
1
−10(−5− 2(0)− 3(0)) = 0.5
x13 =
1
10
(14− (0)− 3(0)) = 1.4
x (1) = (1.4, 0.5, 1.4)t
3.4.3 Me´todo Iterativo de Gauss - Jacobi
d
(k)
r =
d (k)
max
1≤i≤n
|x (k)i |
=
1.4
max{1.4, 0.5, 1.4} = 1
k = 1
x21 =
1
10
(14− 3(0.5)− (1.4)) = 1.11
x22 =
1
−10(−5− 2(1.4)− 3(1.4)) = 1.20
x23 =
1
10
(14− (1.4)− 3(0.5)) = 1.11
x (1) = (1.11, 1.20, 1.11)t
d
(k)
r =
d (k)
max
1≤i≤n
|x (k)i |
=
0.70
max{1.11, 1.20, 1.11} =
0.70
1.20
= 0.583
3.4.3 Me´todo Iterativo de Gauss - Jacobi
d
(k)
r =
d (k)
max
1≤i≤n
|x (k)i |
=
1.4
max{1.4, 0.5, 1.4} = 1
k = 1
x21 =
1
10
(14− 3(0.5)− (1.4)) = 1.11
x22 =
1
−10(−5− 2(1.4)− 3(1.4)) = 1.20
x23 =
1
10
(14− (1.4)− 3(0.5)) = 1.11
x (1) = (1.11, 1.20, 1.11)t
d
(k)
r =
d (k)
max
1≤i≤n
|x (k)i |
=
0.70
max{1.11, 1.20, 1.11} =
0.70
1.20
= 0.583
3.4.3 Me´todo Iterativo de Gauss - Jacobi
d
(k)
r =
d (k)
max
1≤i≤n
|x (k)i |
=
1.4
max{1.4, 0.5, 1.4} = 1
k = 1
x21 =
1
10
(14− 3(0.5)− (1.4)) = 1.11
x22 =
1
−10(−5− 2(1.4)− 3(1.4)) = 1.20
x23 =
1
10
(14− (1.4)− 3(0.5)) = 1.11
x (1) = (1.11, 1.20, 1.11)t
d
(k)
r =
d (k)
max
1≤i≤n
|x (k)i |
=
0.70
max{1.11, 1.20, 1.11} =
0.70
1.20
= 0.583
3.4.3 Me´todo Iterativo de Gauss - Jacobi
Apo´s mais algumas iterac¸o˜es podemos observar que o algoritmo
converge para a soluc¸a˜o x = (1, 1, 1)t
Crite´rio de Convergeˆncia
Teorema 3.3 - Crite´rio das Linhas
Seja o sistema linear Ax = b e seja αk =
n∑
j=1
j 6=k
|akj |
|akk | . Se α = max1≤k≤n
αk < 1
enta˜o o me´todo de Gauss-Jacobi gera uma sequeˆncia {xk} convergente
para a soluc¸a˜o do sistema dado, independentemente da escolha da
aproximac¸a˜o inicial x (0). Neste caso a matriz A e´ dita diagonalmente
dominante.
3.4.3 Me´todo Iterativo de Gauss - Jacobi
Apo´s mais algumas iterac¸o˜es podemos observar que o algoritmo
converge para a soluc¸a˜o x = (1, 1, 1)t
Crite´rio de Convergeˆncia
Teorema 3.3 - Crite´rio das Linhas
Seja o sistema linear Ax = b e seja αk =
n∑
j=1
j 6=k
|akj |
|akk | . Se α = max1≤k≤n
αk < 1
enta˜o o me´todo de Gauss-Jacobi gera uma sequeˆncia {xk} convergente
para a soluc¸a˜o do sistema dado, independentemente da escolha da
aproximac¸a˜o inicial x (0). Neste caso a matriz A e´ dita diagonalmente
dominante.
3.4.3 Me´todo Iterativo de Gauss - Jacobi
Seja a matriz dos coeficientes do exemplo anterior
A =
 10 3 12 −10 3
1 3 10

α1 =
3+1
10 = 0.4
α2 =
3+2
10 = 0.5
α3 =
3+1
10 = 0.4
α = max
1≤k≤3
αk = max{0.4, 0.5} = 0.5
Como α = 0.5 < 1 assim, pelo crite´rio de linhas, temos assegurada a
convergeˆncia do processo iterativo para a soluc¸a˜o do problema.
3.4.3 Me´todo Iterativo de Gauss - Jacobi
Considere o sistema linear{
x1 + x2 = 3
x1 − 3x2 = −3 ,
o me´todo iterativo de Gauss-Jacobi gera uma sequeˆncia convergente
para a soluc¸a˜o exata x = (1.5, 1.5)t . Pore´m, o crite´rio das linhas na˜o
e´ satisfeito, uma vez que, α1 = 1.
Este fato ocorre visto que a condic¸a˜o do teorema 3.3 e´ uma condic¸a˜o
apenas suficiente.
Se a matriz inicial na˜o for diagonalmente dominante, podemos tentar
uma reorganizac¸a˜o das suas linhas antes de aplicarmos o me´todo
iterativo.
3.4.3 Me´todo Iterativo de Gauss - Jacobi
Tome o seguinte sistema linear:
x1 + 3x2 + x3 =
5x1 + 2x2 + 2x3 =
6x2 + 8x3 =
−2
3
−6
temos que
α1 =
3+1
1 = 4
α2 =
5+2
2 = 3.5
α3 =
6
8 = 0.75
α = 4 > 1, na˜o satisfaz ao crite´rio de linhas.
3.4.3 Me´todo Iterativo de Gauss - Jacobi
Tome o seguinte sistema linear:
x1 + 3x2 + x3 =
5x1 + 2x2 + 2x3 =
6x2 + 8x3 =
−2
3
−6
temos que
α1 =
3+1
1 = 4
α2 =
5+2
2 = 3.5
α3 =
6
8 = 0.75
α = 4 > 1, na˜o satisfaz ao crite´rio de linhas.
3.4.3 Me´todo Iterativo de Gauss - Jacobi
Tome o seguinte sistema linear:
x1 + 3x2 + x3 =
5x1 + 2x2 + 2x3 =
6x2 + 8x3 =
−2
3
−6
temos que
α1 =
3+1
1 = 4
α2 =
5+2
2 = 3.5
α3 =
6
8 = 0.75
α = 4 > 1, na˜o satisfaz ao crite´rio de linhas.
3.4.3 Me´todo Iterativo de Gauss - Jacobi
Se permutarmos as linhas 1 e 2 teremos:
5x1 + 2x2 + 2x3 =
x1 + 3x2 + x3 =
6x2 + 8x3 =
−2
3
−6
temos que:
α1 =
2+2
5 = 0.8
α2 =
1+1
3 = 0.667
α3 =
6
8 = 0.75
α = 0.8 < 1
O novo sistema e´ equivalente ao sistema original e sua matriz dos
coeficientes e´ diagonalmente dominante uma vez que satisfaz ao
crite´rio das linhas.
Agora podemos aplicar o me´todo de Gauss-Jacobi a esta nova
disposic¸a˜o do sistema, uma vez que a convergeˆncia esta´ assegurada
pelo crite´rio das linhas.
3.4.3 Me´todo Iterativo de Gauss - Jacobi
Se permutarmos as linhas 1 e 2 teremos:
5x1 + 2x2 + 2x3 =
x1 + 3x2 + x3 =
6x2 + 8x3 =
−2
3
−6
temos que:
α1 =
2+2
5 = 0.8
α2 =
1+1
3 = 0.667
α3 =
6
8 = 0.75
α = 0.8 < 1
O novo sistema e´ equivalente ao sistema original e sua matriz dos
coeficientes e´ diagonalmente dominante uma vez que satisfaz ao
crite´rio das linhas.
Agora podemos aplicar o me´todo de Gauss-Jacobi a esta nova
disposic¸a˜o do sistema, uma vez que a convergeˆncia esta´ assegurada
pelo crite´rio das linhas.
3.4.3 Me´todo Iterativo de Gauss - Jacobi
Sempre que o crite´rio de linhas na˜o for satisfeito devemos tentar
permutac¸o˜es de linhas ou colunas de forma a obtermos uma
disposic¸a˜o para a qual a matriz dos coeficientes satifac¸a o crite´rio das
linhas.
No entanto, nem sempre e´ poss´ıvel obter tal disposic¸a˜o e ainda assim,
e´ poss´ıvel encontrar sequeˆncias do MGJ que sejam convergentes.
3.4.4 Me´todo Iterativo de Gauss - Seidel
Podemos modificar o me´todo de Gauss-Jacobi de tal forma que cada
iterac¸a˜o e´ calculada atualizando os valores das componentes do vetor
x a` medida que as mesmas va˜o sendo calculadas.
Seja o sistema linear Ax = b, no me´todo de Gauss-Seidel
reescrevemos este sistema por separac¸a˜o diagonal, na forma
equivalente x = Cx + g
O processo iterativo consiste em, sendo x (0) uma aproximac¸a˜o inicial,
calcular x (1), x (2), · · · , x (k) da seguinte forma:
x
(k+1)
1 =
1
a11
(b1 − a12x (k)2 − a13x (k)3 − · · · − a1nx (k)n )
x
(k+1)
2 =
1
a22
(b2 − a21x (k+1)1 − a23x (k)3 − · · · − a2nx (k)n )
...
x
(k+1)
n =
1
ann
(bn − an1x (k+1)1 − an2x (k+1)2 − · · · − ann−x (k)n−1)
3.4.4 Me´todo Iterativo de Gauss - Seidel
Logo, no processo iterativo de Gauss-Seidel, nomomento de se
calcular x
(k+1)
j usamos todos os valores x
(k+1)
1 , x
(k+1)
2 , · · · , x (k+1)j−1 que
ja´ foram calculados e os x
(k)
j+1, x
(k)
j+2, · · · , x (k)n restantes.
Resolva numericamente o sistema abaixo usando o me´todo de
Gauss-Seidel. 
10x1 + 3x2 + x3 =
2x1 − 10x2 + 3x3 =
x1 + 3x2 + 10x3 =
14
−5
14
Tome x (0) = (0, 0, 0)t
3.4.4 Me´todo Iterativo de Gauss - Seidel
Logo, no processo iterativo de Gauss-Seidel, no momento de se
calcular x
(k+1)
j usamos todos os valores x
(k+1)
1 , x
(k+1)
2 , · · · , x (k+1)j−1 que
ja´ foram calculados e os x
(k)
j+1, x
(k)
j+2, · · · , x (k)n restantes.
Resolva numericamente o sistema abaixo usando o me´todo de
Gauss-Seidel. 
10x1 + 3x2 + x3 =
2x1 − 10x2 + 3x3 =
x1 + 3x2 + 10x3 =
14
−5
14
Tome x (0) = (0, 0, 0)t
3.4.4 Me´todo Iterativo de Gauss - Seidel
Sistema de iterac¸a˜o
xk+11 =
1
10
(14− 3xk2 − xk3 )
xk+12 =
1
−10(−5− 2x
k+1
1 − 3xk3 )
xk+13 =
1
10
(14− xk+11 − 3xk+12 )
k = 0
x11 =
1
10
(14− 3(0)− (0)) = 1.4
x12 =
1
−10(−5− 2(1.4)− 3(0)) = 0.78
x13 =
1
10
(14− (1.4)− 3(0.78)) = 1.026
x (1) = (1.4, 0.78, 1.026)t
3.4.4 Me´todo Iterativo de Gauss - Seidel
Sistema de iterac¸a˜o
xk+11 =
1
10
(14− 3xk2 − xk3 )
xk+12 =
1
−10(−5− 2x
k+1
1 − 3xk3 )
xk+13 =
1
10
(14− xk+11 − 3xk+12 )
k = 0
x11 =
1
10
(14− 3(0)− (0)) = 1.4
x12 =
1
−10(−5− 2(1.4)− 3(0)) = 0.78
x13 =
1
10
(14− (1.4)− 3(0.78)) = 1.026
x (1) = (1.4, 0.78, 1.026)t
3.4.4 Me´todo Iterativo de Gauss - Seidel
Sistema de iterac¸a˜o
xk+11 =
1
10
(14− 3xk2 − xk3 )
xk+12 =
1
−10(−5− 2x
k+1
1 − 3xk3 )
xk+13 =
1
10
(14− xk+11 − 3xk+12 )
k = 0
x11 =
1
10
(14− 3(0)− (0)) = 1.4
x12 =
1
−10(−5− 2(1.4)− 3(0)) = 0.78
x13 =
1
10
(14− (1.4)− 3(0.78)) = 1.026
x (1) = (1.4, 0.78, 1.026)t
3.4.4 Me´todo Iterativo de Gauss - Seidel
k = 1
x11 =
1
10
(14− 3(0.78)− (1.026)) = 1.0634
x12 =
1
−10(−5− 2(1.0634)− 3(1.026)) = 1.02048
x13 =
1
10
(14− (1.0634)− 3(1.02048)) = 0.98752
x (1) = (1.0634, 1.02048, 0.98752)t
Que esta´ convergindo para a soluc¸a˜o exata. Avance nos ca´lculos e
verifique a convergeˆncia!!
3.4.4 Me´todo Iterativo de Gauss - Seidel
k = 1
x11 =
1
10
(14− 3(0.78)− (1.026)) = 1.0634
x12 =
1
−10(−5− 2(1.0634)− 3(1.026)) = 1.02048
x13 =
1
10
(14− (1.0634)− 3(1.02048)) = 0.98752
x (1) = (1.0634, 1.02048, 0.98752)t
Que esta´ convergindo para a soluc¸a˜o exata. Avance nos ca´lculos e
verifique a convergeˆncia!!
3.4.4 Me´todo Iterativo de Gauss - Seidel
k = 1
x11 =
1
10
(14− 3(0.78)− (1.026)) = 1.0634
x12 =
1
−10(−5− 2(1.0634)− 3(1.026)) = 1.02048
x13 =
1
10
(14− (1.0634)− 3(1.02048)) = 0.98752
x (1) = (1.0634, 1.02048, 0.98752)t
Que esta´ convergindo para a soluc¸a˜o exata. Avance nos ca´lculos e
verifique a convergeˆncia!!
3.4.4 Me´todo Iterativo de Gauss - Seidel
Crite´rio de Convergeˆncia
Crite´rio de Sassenfeld
Sejam
β1 =
|a12|+ |a13|+ · · ·+ |a1n|
|a11|
e
βj =
|aj1|β1 + |aj2|β2 + · · ·+ |ajj−1|βj−1 + |ajj+1|+ · · ·+ |ajn|
|ajj |
Seja β = max
1≤j≤n
βj . Se β < 1, enta˜o o me´todo de Gauss-Seidel gera uma
sequeˆncia convergente qualquer que seja x (0). Ale´m disto, quanto menor
for β mais ra´pida sera´ a convergeˆncia do me´todo.
3.4.4 Me´todo Iterativo de Gauss - Seidel
Seja a matriz dos coeficientes abaixo, verifique se ela atende ao
crite´rio de Sassenfeld
A =

1.0 0.5 −0.1 0.1
0.2 1.0 −0.2 −0.1
−0.1 −0.2 1.0 0.2
0.1 0.3 0.2 1.0

β1 =
0.5+0.1+0.1
1.0 = 0.7
β2 =
0.2∗0.7+0.2+0.1
1.0 = 0.44
β3 =
0.1∗0.7+0.2∗0.44+0.2
1.0 = 0.358
β4 =
0.1∗0.7+0.2∗0.44+0.2∗0.358
1.0 = 0.2736
β = max
1≤j≤n
βj = max{0.7, 0.44, 0.358, 0.2736} = 0.7
Como β = 0.7 < 1 o me´todo de Gauss-Seidel para esta matriz A ira´
convergir.
3.4.4 Me´todo Iterativo de Gauss - Seidel
Seja a matriz dos coeficientes abaixo, verifique se ela atende ao
crite´rio de Sassenfeld
A =

1.0 0.5 −0.1 0.1
0.2 1.0 −0.2 −0.1
−0.1 −0.2 1.0 0.2
0.1 0.3 0.2 1.0

β1 =
0.5+0.1+0.1
1.0 = 0.7
β2 =
0.2∗0.7+0.2+0.1
1.0 = 0.44
β3 =
0.1∗0.7+0.2∗0.44+0.2
1.0 = 0.358
β4 =
0.1∗0.7+0.2∗0.44+0.2∗0.358
1.0 = 0.2736
β = max
1≤j≤n
βj = max{0.7, 0.44, 0.358, 0.2736} = 0.7
Como β = 0.7 < 1 o me´todo de Gauss-Seidel para esta matriz A ira´
convergir.
3.4.4 Me´todo Iterativo de Gauss - Seidel
Seja a matriz dos coeficientes abaixo, verifique se ela atende ao
crite´rio de Sassenfeld
A =

1.0 0.5 −0.1 0.1
0.2 1.0 −0.2 −0.1
−0.1 −0.2 1.0 0.2
0.1 0.3 0.2 1.0

β1 =
0.5+0.1+0.1
1.0 = 0.7
β2 =
0.2∗0.7+0.2+0.1
1.0 = 0.44
β3 =
0.1∗0.7+0.2∗0.44+0.2
1.0 = 0.358
β4 =
0.1∗0.7+0.2∗0.44+0.2∗0.358
1.0 = 0.2736
β = max
1≤j≤n
βj = max{0.7, 0.44, 0.358, 0.2736} = 0.7
Como β = 0.7 < 1 o me´todo de Gauss-Seidel para esta matriz A ira´
convergir.
3.4.4 Me´todo Iterativo de Gauss - Seidel
Seja a matriz dos coeficientes abaixo, verifique se ela atende ao
crite´rio de Sassenfeld
A =

1.0 0.5 −0.1 0.1
0.2 1.0 −0.2 −0.1
−0.1 −0.2 1.0 0.2
0.1 0.3 0.2 1.0

β1 =
0.5+0.1+0.1
1.0 = 0.7
β2 =
0.2∗0.7+0.2+0.1
1.0 = 0.44
β3 =
0.1∗0.7+0.2∗0.44+0.2
1.0 = 0.358
β4 =
0.1∗0.7+0.2∗0.44+0.2∗0.358
1.0 = 0.2736
β = max
1≤j≤n
βj = max{0.7, 0.44, 0.358, 0.2736} = 0.7
Como β = 0.7 < 1 o me´todo de Gauss-Seidel para esta matriz A ira´
convergir.
3.4.4 Me´todo Iterativo de Gauss - Seidel
Seja a matriz dos coeficientes abaixo, verifique se ela atende ao
crite´rio de Sassenfeld
A =

1.0 0.5 −0.1 0.1
0.2 1.0 −0.2 −0.1
−0.1 −0.2 1.0 0.2
0.1 0.3 0.2 1.0

β1 =
0.5+0.1+0.1
1.0 = 0.7
β2 =
0.2∗0.7+0.2+0.1
1.0 = 0.44
β3 =
0.1∗0.7+0.2∗0.44+0.2
1.0 = 0.358
β4 =
0.1∗0.7+0.2∗0.44+0.2∗0.358
1.0 = 0.2736
β = max
1≤j≤n
βj = max{0.7, 0.44, 0.358, 0.2736} = 0.7
Como β = 0.7 < 1 o me´todo de Gauss-Seidel para esta matriz A ira´
convergir.
3.4.4 Me´todo Iterativo de Gauss - Seidel
Seja a matriz dos coeficientes abaixo, verifique se ela atende ao
crite´rio de Sassenfeld
A =

1.0 0.5 −0.1 0.1
0.2 1.0 −0.2 −0.1
−0.1 −0.2 1.0 0.2
0.1 0.3 0.2 1.0

β1 =
0.5+0.1+0.1
1.0 = 0.7
β2 =
0.2∗0.7+0.2+0.1
1.0 = 0.44
β3 =
0.1∗0.7+0.2∗0.44+0.2
1.0 = 0.358
β4 =
0.1∗0.7+0.2∗0.44+0.2∗0.358
1.0 = 0.2736
β = max
1≤j≤n
βj = max{0.7, 0.44, 0.358, 0.2736} = 0.7
Como β = 0.7 < 1 o me´todo de Gauss-Seidel para esta matriz A ira´
convergir.
3.4.4 Me´todo Iterativo de Gauss - Seidel
O crite´rio de Sassenfeld e´ apenas suficiente. Ele pode na˜o ser
satisfeito e mesmo assim o me´todo gerar uma sequeˆncia convergente.
Sempre e´ poss´ıvel trocar linhas ou colunas para tentar atender a este
crite´rio.
Crite´rio das Linhas: seja αk =
n∑
j=1
j 6=k
|akj |
|akk | . Se α = max1≤k≤n
αk < 1 enta˜o
o me´todo de Gauss-Seidel gera uma sequeˆncia {xk} convergente para
a soluc¸a˜o do sistema dado.
Se o crite´rio de linhas e´ satisfeito para uma dada matriz A, enta˜o,
automaticamente o crite´rio de Sassenfeld e´ satisfeito.
Entretanto, o crite´rio de Sassenfeld pode ser satisfeito mesmo que o
crite´rio de linhas na˜o o seja.
3.4.4 Me´todo Iterativo de Gauss - Seidel
Seja o sistema linear Ax = b tal que
A =
 3 0 11 −1 0
3 1 2

α1 = β1 =
1
3
α2 = 1→ fura o crite´rio de linhas!!
β2 =
1∗1/3
1 =
1
3
α3 =
3+1
2 = 2
β3 =
1∗1/3+1∗1/3
2 =
4
6 < 1!!
3.4.4 Me´todo Iterativo de Gauss - Seidel
Seja o sistema linear Ax = b tal que
A =
 3 0 11 −1 0
3 1 2

α1 = β1 =
1
3
α2 = 1→ fura o crite´rio de linhas!!
β2 =
1∗1/3
1 =
1
3
α3 =
3+1
2 = 2β3 =
1∗1/3+1∗1/3
2 =
4
6 < 1!!
3.4.4 Me´todo Iterativo de Gauss - Seidel
Seja o sistema linear Ax = b tal que
A =
 3 0 11 −1 0
3 1 2

α1 = β1 =
1
3
α2 = 1→ fura o crite´rio de linhas!!
β2 =
1∗1/3
1 =
1
3
α3 =
3+1
2 = 2
β3 =
1∗1/3+1∗1/3
2 =
4
6 < 1!!
3.4.4 Me´todo Iterativo de Gauss - Seidel
Seja o sistema linear Ax = b tal que
A =
 3 0 11 −1 0
3 1 2

α1 = β1 =
1
3
α2 = 1→ fura o crite´rio de linhas!!
β2 =
1∗1/3
1 =
1
3
α3 =
3+1
2 = 2
β3 =
1∗1/3+1∗1/3
2 =
4
6 < 1!!
3.4.4 Me´todo Iterativo de Gauss - Seidel
Seja o sistema linear Ax = b tal que
A =
 3 0 11 −1 0
3 1 2

α1 = β1 =
1
3
α2 = 1→ fura o crite´rio de linhas!!
β2 =
1∗1/3
1 =
1
3
α3 =
3+1
2 = 2
β3 =
1∗1/3+1∗1/3
2 =
4
6 < 1!!
U´ltimas considerac¸o˜es
Em relac¸a˜o a` convergeˆncia, os me´todos diretos sa˜o processos finitos e
portanto teoricamente sempre chegara˜o a` soluc¸a˜o do sistema,
enquanto que os me´todos iterativos so´ tera˜o assegurada a`
convergeˆncia sob certas condic¸o˜es.
Sistemas lineares esparsos, que sa˜o bem frequentes em problemas de
engenharia, sa˜o mais facilmente resolvidos pelos me´todos iterativos.
Os me´todos iterativos sa˜o mais robustos em relac¸a˜o aos erros de
arredondamento.
Lista 3: 1,2,5,6,9(a,b,f),10,17,18,22,23,24 e 31
Pro´xima aula
Por hoje e´ so´ pessoal!!
Este material e´ inteiramente baseado na bibliografia do curso,
principalmente no livro texto :RUGIERO, M. A.G; LOPES,V Ca´lculo
Nume´rico: Aspectos teo´ricos e computacionais, Editora McGraw-Hill.1997.
Sites consultados acessados em 24/03/2011: CASTILHO, J. E., Apostila
de Ca´lculo Nume´rico, http://www.castilho.prof.ufu.br, UFU, 2002
http://www.alunos.eel.usp.br/numerico/notas.html
Colli, E., Asano, H. C,Ca´lculo Nume´rico — Fundamentos e
Aplicac¸o˜es-Departamento de Matema´tica Aplicada – IME-USP, 2009
Este material na˜o substitui a bibliografia.