Gauss-Seidel

1.7.2- Método de Gauss- Seidel
Suponhamos D = I, como foi feito para o método de Jacobi-Richardson.
Transformamos o sistema linear Ax = b como se segue:
(L* + I + R*)x = b*
(L* + I)x = - R*x + b*
x = - (L* + I)-1 R* x + (L* + I)-1 b*
O processo iterativo definido por:
X(k + 1) = - ( L* + I)-1 R* x(k) + (L* + I)-1b*
é chamado de Gauss-Seidel.
Explicitando as componentes, usando para isso a equaç ão do processo na forma:
(L* + I) x(k + 1) = - R*x(k) + b*
ou
X(k+1) = - L* x(k+1) – R* x(k) + b*
Resulta que o método de Gauss-Seidel consiste na determinação de uma sequência de
aproximantes de índice k
x1( k ) , x(2k ) , . . . , x(nk ) , k = 1, 2, 3, . . .
a partir de valores iniciais
x(10 ) , x(2o ) , . . . , x (no )
através do processo iterativo definido por:
∗
x1( k +1 ) = 0 - a 12
x (2k ) - . . . - a 1∗n x (nk ) + b1∗
x(2k +1) = - a ∗21 x 1( k +1 ) − 0 - a ∗23 x (3k ) - . . . - a ∗2(nk ) x (nk ) + b ∗2
x(3k +1 ) = - a ∗31 x (1k +1) - a ∗32 x (2k +1) − 0 - . . . - a ∗3 n x (nk ) + b ∗3
. . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . .
x(nk + 1 ) = - a ∗ni x 1(k +1) - a ∗n 2 x (2k +1) − a ∗n 3 x (3k +1) . .. − 0 + b ∗n .
34
Vemos por estas equações que as componentes de x(k+1) são calculadas
sucessivamente sem necessidade de se calcular ( L* + I)-1 .
Esse método difere do de Jacobi-Richardson por utilizarmos para o cálculo de uma
componente de x(k + 1) o valor mais recente das demais componentes.
1.7.2- Critério de convergência.
a) O Critério de Sassenfeld:
Aplicando o critério geral de convergência, calculemos:
B
∞
= ( L * + I) −1 R *
Recordemos que: B
∞
∞
= min k .
Portanto se k satisfazer a desigualdade Bx
Seja y = Bx
∞
≤ k x
∴ y = - (L* + I )-1 R*x
(L* + I)y = - R*x
ou
y = - L*y – R*x.
Assim o vetor y é obtido de x a partir das equações:



(I) 



Calculemos y
∞
y1 = 0 − a ∗12 x 2 − a ∗13 x 3 − L − a ∗1n x n
y 2 = − a ∗21 y 1 −0−a ∗23 x 3 − L − a ∗2 n x n
y 3 = − a ∗31 y 1 − a ∗31 y 2 − 0 − L − a ∗3n x n
M
y n = − a y 1 − a y 2 − a ∗n 3 y 3 − L − 0
∗
n1
∗
n2
Bx ∞ como y
=
yi
= max
∞
i
A partir das equações (I) conseguimos as seguintes majorações:
n
y1 =
∑ a *1j x j ≤
j=2
= β1 x
∞
n
∑
j= 2
n
∑a
a*1 j a j ≤
onde β 1 =
j= 2
n
∑a
j= 2
35
*
1j
*
1j
max x j
j
∞
teremos B ∞ ≤ k.
≤ β1 x
∴ y1
∞
n
∑a
*
= a 21y 1 +
y2
*
2j
j=3
x j ≤ a *21 β 1 x
n
∞
+ ∑ a *2 j x j
j= 3
n
≤ a *21 β 1 x
+ ∑ a *2 j max x j =
∞
j =3
n
*
= a 21 β 1 x
+ ∑ a *2 j x
∞
j= 3
n
= ( a *21 β 1 + ∑ a *2 j ) x
j= 3
∞
=
∞
= β2 x
∞
n
β 2 = ( a *21 β1 + ∑ a *2 j )
onde
j= 3
∴ y 2 ≤ β2 x ∞
Analogamente, obtemos:
yi ≤
≤
i− 1
∑a
j =1
βj x
*
ij
∞
i −1
∑ a *ij β j x
∑a
j= 1
i −1
j=1
onde B
∞
∞
xj ≤
*
ij
max x j
n
∑a
j= i + 1
j=i +1
*
ij
) x
∞
j
= βi x
∞
n
∑a
j= i +1
∴ y i ≤ βi x
Portanto: Bx
*
ij
n
= ( ∑ a *ij β j +
*
onde β i = ( ∑ a ij β j +
n
∑a
j= i + 1
+
∞
j= 1
i −1
+
= y
*
ij
∞
∞
)
.
= max y i ≤ max β i x
i
i
≤ max β i .
i
Podemos enunciar agora o Critério de Sassenfeld:
“O método de Gauss-Seidel converge se:
max β i < 1
i
onde os β i são calculados por recorrência através de:
βi =
i −1
∑
j= 1
a *ij β j +
n
∑a
j= i + 1
*
ij
.”
36
∞
b) Critério das linhas
“O método de Gauss-Seidel converge se o critério das linhas for satisfeito, isto é, se:
n
max
i
∑a
j =1
j≠i
*
ij
< 1.”
Para provar este critério basta verificar que a condição
n
max
i
implica β i < 1
∑a
j =1
j≠i
*
ij
<1
i = 1, 2, . . ., n.
De fato:
Para i = 1, temos:
n
β1 =
∑a
j=2
*
ij
≤ max ∑ aij* < 1 .
i
j=1
j≠1
Suponhamos β j < 1 para j = 1, 2, . . . , i - 1.
Então
i−1
βi =
∑a
j=1
n
*
ij
βj +
∑a
j =i +1
*
ij
n
≤ ∑ aij* ≤ max
j =1
j≠ 1
i
∑a
j= 1
j≠ 1
*
ij
< 1.
Portanto max β i < 1 e o critério de Sassenfeld é verificado.
Observações:
- Dado um sistema linear Ax=b pode acontecer que o método de jacobi-Richardson
aplicado a ele resulte convergente enquanto que o de Gauss-Seidel resulta divergente
e vice-versa.
- Se B não for apreciavelmente menor que 1 a convergência pode ser bastante lenta.
- A convergência para os métodos: Jacobi-Richardson e Gauss-Seidel não depende do
valor inicial x(0).
- Um permutação conveniente das linhas ou colunas de A antes de dividir cada
equação pelo coeficiente da diagonal principal pode reduzir o valor de B .
37
Exemplo 1.7.2:
Resolver o sistema:
5x1 + x2 + x3 = 5

3x1 + x2 + x3 = 6
3x + x + 6x = 0
 1
2
3
pelo método de Gauss-Seidel com x(0) = (0,0,0)t e ε < 10-2 .
Solução:
Dividindo cada equação pelo correspondente elemento da diagonal principal
obtemos:
x1 + 0.2x2 + 0. 2 x3 = 1
0.75x1 +
x2 + 0. 25x3 = 1.5
0.5 x1 + 0.5x2 +
x3 = 0
Temos:
n
max
i
∑a
j =1
j≠i
*
ij
=1
Portanto, por esse critério não podemos garantir convergência. Mas aplicando o
critério de Sassenfeld, temos:
β 1 = 0.2 + 0.2 = 0.4
β 2 = 0.75 ( 0.4) + 0.25 = 0.3 + 0.25 = 0.55
β 3 = 0.5 ( 0.4) + (0.5) (0.55) = 0.2 + 0.275 = 0.475
∴max βi = 0.55 < 1
i
Logo temos o critério de convergência satisfeito.
Efetuando-se as iterações definidas por:
x1( k +1) = − 0.2 x 2( k ) − 0.2 x3( k ) + 1
x 2( k +1) = − 0.75x1( k +1) − 0.25x 3( k ) + 15
.
x 3( k +1) = − 0.5x1( k +1) − 0.5x 2( k +1)
a partir de x(0) = (0,0,0)t , resultam os seguintes valores:
K
0
1
2
x1
0
1
1.025
x2
0
0.75
0.95
x3
0
-0.875
-0.9875
38
3
1.0075
0.99125
-0.999375
4
1.001625
0.998625
-1.000125
Observações:
- Para ε < 10 -2 temos que a solução do sistema é
x = (1.00 ; 0.99 ; -1.00) t
- A solução exata do sistema proposto é x = (1, 1, -1)t.
1.7.3-
Exercícios:
1.7.3.1) Resolver o sistema:
10x1 + x 2
− x3
= 10

+ 10 x2 + x 3
= 12
 x1
 2x
+ 10x 3 = 11
 1 − x2
pelo método de Jacobi-Richardson com x(0) = (0,0,0)t e ε < 10 -3 .
1.7.3.2) Dado o sistema:
10x1 + x 2
+ x3
= 10

+ 10 x2 + 8 x3 = 20
 x1
 7x
+ 10x 3 = 20
 1 + x2
a) Verificar a possibilidade de aplicação do método iterativo de jacobi-Richardson.
b) Se possível, resolvê-lo pelo método do item a).
1.7.3.3) Dado o sistema:
 4 x1 + 2 x2 + 6 x 3 = 1

 4 x1 − x2 + 3 x3 = 2
 − x + 5x + 3x = 3
 1
2
3
Mostrar que reordenando as equações e incógnitas poderemos fazer com que o
critério de Sassenfeld seja satisfeito, mas não o das linhas.
1.7.3.4) Dado o sistema
 5 x1 + 2 x2 + x 3
=
7

3
 − x1 + 4 x2 + 2 x 3 =
 2 x − 3x
+ 10x 3 = − 1
 1
2
a) Verificar a convergência usando o critério das linhas e o critério de Sassenfeld.
b) Reslover o sistema por:
b.1- Jacobi-Richardson.
b.2- Gauss-Seidel.
Efetuar, em ambos os casos, duas iterações partindo-se d0 vetor x(0) = (-2.4; 5; 0.3) t .
39
1.7.3.5) Calcular u2, u3 , u4 e u5 resolvendo a equação de diferenças
(*) un+2 + un+1 + un = n
com as condições de contorno u1 = 0 e u6 = 1
Observação: Escrever (*) para n = 1, 2, 3 e 4 e resolver o sistema resultante pelo
Método de Gauss-Seidel.
1.7.3.6) Dado o sistema:
 4 1 1  x1   6 

   
 1 6 1  x2  =  8 

   
 2 1 8  x3  11
a) Verificar a convergência usando o critério de Sassenfeld.
b) Resolver pelo Método de Gauss-Seidel ( 3 iterações a partir do vetor nulo).
40