Sumário 1. Introdução 2. Método iterativo de Gauss

Universidade Estadual de Maringá - Departamento de Matemática
Cálculo Diferencial e Integral: um KIT de Sobrevivência
c Publicação eletrônica do KIT
°
http://www.dma.uem.br/kit
Sobre o Critério de Sassenfeld
Resumo: Neste trabalho demonstraremos o Critério de Sassenfeld que é um
importante resultado sobre a convergência do método de Gauss-Seidel. Também
daremos uma aplicação usando este resultado.
Sumário
1. Introdução
1
2. Método iterativo de Gauss-Seidel
1
3. Critérios de Parada
2
4. Resultado principal
2
1.
Introdução
Em Análise Numérica usamos os métodos iterativos para resolver sistemas
de equações lineares de grande porte. Um desses métodos é o método de
Gauss-Seidel. Nesse trabalho demonstraremos o Critério de Sassenfeld, que
nos dá condições suficientes para a convergência desse método, independente
da aproximação inicial x(0) atribuída.
2.
Método iterativo de Gauss-Seidel
No método de Gauss-Seidel, um sistema de equações lineares Ax = b é escrito
de forma equivalente x = Cx + g por separação da diagonal. Seja x(0) uma
aproximação inicial, pelo processo iterativo queremos calcular x(1) , x(2) , . . . , x(k) , . . . ,
por:
2
João M. S. Pitot

1
(k)
(k)
(k)
(k+1)


(b1 − a12 x2 − a13 x3 − · · · − a1n xn )
x1
=


a

11


1
(k)
(k)
(k+1)
(k+1)


x2
=
(b2 − a21 x1
− a23 x3 − · · · − a2n xn )


a22

1
(k+1)
(k+1)
(k+1)
(k)
(k)
=
x3
(b3 − a31 x1
− a32 x2
− a34 x4 − · · · − a3n xn )

a33



.

.

.




1
(k+1)
(k+1)
(k+1)

 x(k+1)
(bn − an1 x1
− an2 x2
− · · · − an,n−1 xn−1 ).
=
n
ann
(k+1)
Portanto, no método de Gauss-Seidel, quando calcularmos xj
usamos
(k+1)
(k+1)
todos os valores de x1
, . . . , xj−1 que já foram calculados e os valores
(k)
(k)
xj+1 , . . . , xn restantes.
3.
Critérios de Parada
O processo iterativo Gauss-Seidel é repetido várias vezes até que o vetor x(k)
esteja muito próximo do vetor x(k−1) . Considerando a norma de vetores, e
dada uma precisão ², o vetor x(k) será escolhido como uma solução aproximada da solução exata se:
(i) kx(k) − x(k−1) k < ² (erro absoluto),
(ii)
kx(k) − x(k−1) k
< ² (erro relativo).
kx(k) k
Os critérios de parada acima são os mais utilizados.
4.
Resultado principal
Teorema 4..1 (Critério de Sassenfeld) Seja A = (aij ) uma matriz quadrada
de ordem n. Sejam βi , i = 1, 2, ..., n dados por:
β1 =
n
X
|a1j |
j=2
βi =
,
n
X
|aij |
+
.
|aii |
|aii |
j=i+1
i−1
X
|aij |βj
j=1
|a11 |
c KIT - Cálculo Diferencial e Integral
°
3
Se β = max {βi } < 1, então o método de Gauss-Seidel gera uma se1≤i≤n
qüência de vetores (x(k) ) convergente qualquer que seja a aproximação inicial
x(0) .
Além disso, quanto menor for β mais rápida será a convergência.
Demonstração:


x1
 x2 


Seja x =  ..  a solução exata do sistema de equações lineares Ax = b
 . 
xn
 (k) 
x1
 x(k) 


e seja x(k) =  2.  a k-ésima aproximação de x obtida pelo método de
.
 . 
(k)
xn
Gauss-Seidel.
Queremos uma condição que nos garanta que x(k) −→ x quando k −→ ∞.
Ou seja, que
(k)
lim ei
k→∞
(k)
= 0, para i = 1, . . . , n, onde ei
(k)
= xi − xi .
Agora, aplicando Gauss-Seidel temos

1
(k+1)
(k)
(k)
(k)

= − (a12 e2 + a13 e3 + · · · + a1n en )
e1



a11



 e(k+1) = − 1 (a21 e(k+1) + a23 e(k) + · · · + a2n e(k)
n )
2
1
3
a22
..



.



1

(k+1)
(k)
(k+1)
 e(k+1)
=−
(an1 e1
+ an2 e2 + · · · + ann−1 en−1 ).
n
ann
(k)
Denotaremos de E (k) = max |ei |, e sejam
1≤i≤n
β1 =
n
X
|a1j |
j=2
βi =
|a11 |
,
n
X
|aij |
+
, para i = 2, 3, . . . , n.
|aii |
|aii |
j=i+1
i−1
X
|aij |βj
j=1
Mostraremos por indução que E (k+1) ≤ βE (k) onde β = max1≤i≤n {βi }.
4
João M. S. Pitot
Para i = 1, temos
(k+1)
|e1
|≤
≤
1
(k)
(|a12 ||ek2 | + |a13 ||e3 | + · · · + |a1n ||e(k)
n |)
|a11 |
1
(|a12 | + |a13 | + · · · + |a1n |) E (k) .
|a |
{z
}
| 11
(k+1)
|
|e1
(k)
≤ β1 E ≤ βE
Então,
Suponhamos por indução que
=β1
(k)
.
(k+1)
| ≤ β2 E (k)
(k+1)
| ≤ β3 E (k)
|e2
|e3
..
.
(k+1)
|ei−1 | ≤ βi−1 E (k) , tal que i ≤ n
(k+1)
e mostraremos que |ei
De fato, temos que
(k)
| ≤ βi max1≤j≤n |ej |
(k+1)
|≤
1
1
(k+1)
(k+1)
(k)
(|ai1 ||e1
|+· · ·+|ai,i−1 ||ei−1 |)+
(|ai,i+1 ||ei+1 |+· · ·+|ain ||e(k)
n |)
|aii |
|aii |
(k+1)
|≤
1
(|ai1 |β1 + |ai2 |β2 + . . . |ai,i−1 |βi−1 + |ai,i+1 | + · · · + |ain |) E (k) ,
|a |
| ii
{z
}
|ei
|ei
βi
ou seja,
(k+1)
|ei
| ≤ βi E (k) ≤ βE (k) ,
∀i, 1 ≤ i ≤ n.
Portanto,
(k+1)
E (k+1) = max |ei
1≤i≤n
(k)
| ≤ β max |ej | = βE (k) .
1≤j≤n
(4.1)
Assim, basta que β < 1 para que tenhamos E (k+1) < E (k) . Aplicando (1)
seguidas vezes, obtemos
E (k) ≤ βE (k−1) ≤ β(βE (k−2) ) ≤ · · · ≤ β k E (0) ,
c KIT - Cálculo Diferencial e Integral
°
5
ou seja,
E (k) ≤ β k E (0) .
Logo,
lim β k E (0) = 0.
k→∞
Portanto, se β < 1 então x(k) −→ x, independendo da aproximação inicial
escolhida.
¤
• Exemplo 4..2 Seja o sistema linear

 2x1 + x2 + 3x3 = 9
−x2 + x3 = 1

x1 + 3x3 = 3
(4.2)
temos que a matriz ampliada de (2) é

2 1 3 9
 0 −1 1 1 
1 0 3 3

com esta disposição de linhas e colunas temos que a matriz acima não satisfaz
o Critério de Sassenfeld. Mas trocando a linha 1 com a linha 3 e, a partir
daí, trocamos a coluna 1 com a coluna 3, temos


3 0 1 3
 1 −1 0 1  .
3 1 2 9
Desta forma,
β1 = 1/3,
β2 = [(1)(1/3) + 0]/1 = 1/3,
β3 = [(3)(1/3) + (1)(1/3)]/2 = 2/3.
Portanto, β = max1≤i≤3 βi = 2/3 < 1, então vale o Critério de Sassenfeld
e temos garantia de convergência.
6
João M. S. Pitot
Referências
[1] Notas de Aula - Doherty Andrade
[2] Márcia A. G. Ruggiero, Vera L. R. Lopes Cálculo numérico: Aspectos
Teóricos e Computacionais. McGraw-Hill, 132-137, (1988).