Método de Gauss-Seidel

Teoria Completa

Continuando nosso estudo de métodos iterativos, chegamos ao método de Gauss-Seidel. E não é só o nome que é parecido com o de Gauss-Jacobi não! O método é essencialmente o mesmo, a diferença são os valores que usamos na nossa função de iteração. E claro, temos o nome de Gauss de novo . . .

Ele também recebe uma aproximação inicial e vai melhorando ela por meio de repetidas iterações até chegarmos a uma precisão mínima desejada. Para vermos a diferença vamos ver como o método é aplicado:

Resolva o sistema linear abaixo com x 0 = - 1.8 5.5 7.3 e ε = 0.1

6 x 1 + 3 x 2 + x 3 = 10 4 x 1 + 9 x 2 - 3 x 3 = 16 x 1 - x 2 + 3 x 3 = 14

Usando como aproximação inicial x 1 , x 2 , x 3 = - 1.8,5.5,7.3 . A função de iteração é encontrada exatamente da mesma maneira que no método de Gauss-Jacobi:

Função de iteração para o x 1 →Pegamos a primeira equação e isolamos o x 1 :

6 x 1 + 3 x 2 + x 3 = 10

x 1 k + 1 = 10 - 3 x 2 k - x 3 k 6

Função de iteração para o x 2 →Pegamos a segunda equação e isolamos o x 2 :

4 x 1 + 9 x 2 - 3 x 3 = 16

x 2 k + 1 = 16 - 4 x 1 k + 1 + 3 x 3 k 9

Função de iteração para o x 3 →Pegamos a terceira equação e isolamos o x 3 :

x 1 - x 2 + 3 x 3 = 14

x 3 k + 1 = 14 - x 1 k + 1 + x 2 k + 1 3

Deu pra perceber a diferença? Como na hora que vamos calcular x 2 k + 1 nós já calculamos x 1 k + 1 , nós usamos esse mais “atualizado” ao invés de usarmos o da iteração k . O mesmo acontece no x 3 k + 1 , onde nós já calculamos x 1 k + 1 e x 2 k + 1 .

Ou seja, nós já aproveitamos os valores encontrados em cada iteração ao invés de ficar usando os da última. O que faz todo sentido né? Se o método gera uma sequência que converge para a solução, então usar o x 1 de uma iteração maior deve nos dar resultados melhores e mais rápidos!

Continuando o processo, o que faremos agora é aplicar essas funções de iteração nas nossas aproximações iniciais:

Iteração 1:

x 1 1 = 10 - 3 x 2 0 - x 3 0 6

x 1 1 = 10 - 3 ∙ 5.5 - 7.3 6

x 1 1 = - 2.3

Aqui não temos nenhuma informação além das aproximações iniciais então usamos elas mesmo.

x 2 1 = 16 - 4 x 1 1 + 3 x 3 0 9

x 2 1 = 16 - 4 ∙ - 2.3 + 3 ∙ 7.3 9

x 2 1 = 5.2 3 ¯

Opa, agora já tínhamos x 1 1 então usamos ele ao invés do x 1 0 !

x 3 1 = 14 - x 1 1 + x 2 1 3

x 3 1 = 14 + 2.3 + 5.2 3 ¯ 3

x 3 1 = 7.1 7 ¯

E aqui já tínhamos x 1 1 e x 2 1 calculados, então foram eles que entraram.

Então ficamos com x 1 = - 2.3 ,   5.2 3 ¯ , 7.1 7 - .

Critério de Parada

Novamente usamos as diferenças x i k + 1 - x i k como critério de parada. Quando a maior dessas diferenças for menor que o erro, podemos parar as iterações.

m a x x i k + 1 - x i k < ε

Outro critério que também é usado é o erro relativo:

m a x x i k + 1 - x i k max ⁡ x i k + 1 < ε

Beleza? É exatamente o mesmo procedimento, você só vai usar os valores x i mais “atualizados”.

Critério de Convergência

Uma condição suficiente (sempre que for satisfeita vai convergir, mas dá pra convergir sem ela também) para a convergência do método de Gauss-Seidel é o critério de Sassenfeld. Ele diz o seguinte, sejam

β 1 = a 12 + a 13 + … + a 1 n a 11

β 2 = a 21 β 1 + a 23 + … + a 2 n a 22

β 3 = a 31 β 1 + a 32 β 2 + … + a 3 n a 33

β k = a k 1 β 1 + a k 2 β 2 + ⋯ + a k k - 1 β k - 1 + a k k + 1 + … + a k n a k k

β k = ∑ j = 1 k - 1 a k j ∙ β j + ∑ j = k + 1 n a k j ∙ 1 a k k

Ou seja, é bem parecido com o critério das linhas né? A diferença é que os β que calculamos entram na fórmula dos β seguintes! No β 2 nós já tínhamos calculado o β 1 , então ele entrou multiplicando o termo da coluna 1 a 21 !

Depois disso, definimos

β = max 1 ≤ k ≤ n ⁡ β k

Então, se β < 1 , o critério de Sassenfeld é satisfeito e o método irá convergir. Por exemplo, no sistema que resolvemos ali em cima:

6 x 1 + 3 x 2 + x 3 = 10 4 x 1 + 9 x 2 - 3 x 3 = 16 x 1 - x 2 + 3 x 3 = 14

β 1 = 3 + 1 6 = 4 6

β 2 = 4 × 4 6 + 3 9 = 17 27

β 3 = 1 × 4 6 + 1 × 17 27 3 = 35 81

O máximo aí é o β 1 que é menor que 1 . Logo, o critério de Sassenfeld é satisfeito e o método com certeza converge. Além disso, quanto menor for o β , mais rápida será a convergência.

Uma observação interessante é que essa multiplicação por β aumenta as chances do método convergir em relação ao método de Gauss-Jacobi. Se um sistema satisfaz o critério das linhas ele satisfaz o critério de Sassenfeld também! Mas nem todo sistema que satisfaz o critério de Sassenfeld satisfaz o das linhas.

Novamente, temos como consequência o fato de que a ordem das equações pode influenciar o resultado do método apesar de não alterar em nada o sistema. Vamos sempre alterar a ordem das equações de forma a satisfazer o critério de Sassenfeld.

Obs.: Assim como em Gauss-Jacobi, se esse critério for satisfeito você pode usar qualquer chute inicial que quiser que o método vai convergir! Quanto melhor o chute, mais rápido vamos convergir, mas podemos escolher qualquer vetor como aproximação inicial.

Interpretação Geométrica

Vamos dar uma olhada na interpretação geométrica desse problema em um sistema com 2 equações e 2 icógnitas:

Sistema com solução única (método converge):

Sistema com solução única (método diverge):

Sistema sem solução:

Sistema com infinitas soluções:

Sacou? Em um sistema com solução única a sequência gerada pode convergir ou divergir. Em um sistema sem solução vamos ficar fazendo iterações pra sempre sem nunca chegar num resultado. E em um sistema com infinitas soluções teremos um resultado na primeira iteração haha. Lembrando que isso é uma interpretação do caso 2 × 2 pra ajudar vocês a visualizar!

Algoritmo

Partiu algoritmo! O que precisamos fazer aqui é algumas pequenas modificações no algoritmo de Gauss-Jacobi, já que eles são bem parecidos.

Passo 1. Dados iniciais (o que seu programa vai receber de você):

a. Matriz A n × n

b. Vetor b

c. Vetor aproximação inicial x 0 = x 1 0 , x 2 0 , … , x n 0

d. Erro ε

Passo 2. Definimos um contador de iterações k = 1

Passo 3. Para i variando de 1 a n , defina x i = 1 a i i b i - ∑ j = 1 i - 1 a i j ∙ x j - ∑ j = i + 1 n a i j ∙ x j 0

Passo 4. Se max 1 ≤ i ≤ n ⁡ x i - x i 0 < ε , FIM e retorne x 1 , x 2 , … , x n . Caso contrário, continue para o Passo 5

Passo 5. k = k + 1

Passo 6. Para i variando de 1 a n , defina x i 0 = x i

Passo 7. Volte para o passo 3

O único passo alterado com relação ao de Gauss-Jacobi foi o Passo 3, que é justamente a definição das novas aproximações. Nela, aproveitamos os x j já calculados onde j < i e usamos os x j 0 da iteração anterior apenas para j > i .

E repito, como estamos tratando de métodos iterativos é interessante definirmos também um número máximo de iterações.

Expandir

Exercício Resolvido #1

Lista 3 – Professora Angela – UFRJ – Questão 11

Dar exemplo de um sistema de equações 2 × 2 que não seja diagonal dominante, mas seja convergente usando o método de Gauss-Seidel.

Obs.: Um sistema é diagonal dominante se para todas as linhas da matriz de coeficientes, o módulo do valor da matriz na diagonal é maior que a soma dos módulos de todos os demais valores (não-diagonais) daquela linha. 

MOSTRAR SOLUÇÃO COMPLETA

Passo 1

-

Beleza, o enunciado dá uma breve explicação do que é um sistema diagonal dominante. Em um sistema 2 × 2 isso significa:

a 11 x 1 + a 12 x 2 = b 1 a 21 x 1 + a 22 x 2 = b 2

a 11 > a 12

a 22 > a 21

E para que o sistema convirja pelo método de Gauss-Seidel temos que satisfazer o critério de Sassenfeld, que em um sistema 2 × 2 fica:

β 1 = a 12 a 11

β 2 = a 21 β 1 a 22

E queremos que β 1 < 1 e β 2 < 1 . Para que isso seja satisfeito sem usarmos um sistema diagonal dominante, basta que a 12 < a 11 e que a 21 = a 22 por exemplo. Se liga:

2 x 1 + x 2 = 3 x 1 + x 2 = 2

No sistema acima temos:

β 1 = 1 2 = 0.5 < 1

β 2 = 1 ∙ 0.5 1 = 0.5 < 1

Logo, o sistema converge pelo método de Gauss-Seidel, mas o sistema não é diagonal dominante.

Resposta

Exercício Resolvido #2

Márcia A. Gomes Ruggiero e Vera Lúcia da Rocha Lopes, Cálculo Numérico – Aspectos Teóricos e Computacionais, 2ª ed. São Paulo: MAKRON Books, 1996, pag 185, exercício 22.

Em cada caso verifique se o critério de Sassenfeld é satisfeito e resolva por Gauss-Seidel com ε = 0.0001 , se possível:

a A = 10 1 1 1 10 1 1 1 10 ; b = 12 12 12

b