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 A = 4 - 1 0 0 - 1 4 - 1 0 0 - 1 4 - 1 0 0 - 1 4 ; b = 1 1 1 1

MOSTRAR SOLUÇÃO COMPLETA

Passo 1

a Verificando o critério de Sassenfeld:

β 1 = 1 + 1 10 = 0.2

β 2 = 0.2 ∙ 1 + 1 10 = 0.12

β 3 = 0.2 ∙ 1 + 0.12 ∙ 1 10 = 0.032

Logo, β = 0.2 < 1 . O critério é satisfeito.

Passo 2

As funções de iteração são:

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

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

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

Visualmente podemos ver que a solução é simplesmente x = 1 , 1,1 né? Mas pra treinar um pouco vamos usar como aproximação inicial x 0 = 0.9,1 . 1,0.9 .

Iteração 1 :

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

x 1 1 = 1

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

x 2 1 = 1.01

x 3 1 = 12 - x 1 1 - x 2 1 10

x 3 1 = 0.999

Então temos x 1 = 1,1 . 01,0.999 .

Critério de Parada:

x 1 1 - x 1 0 = 0.1 > ε

Não atingimos o critério, então continuamos as iterações.

Iteração 2 :

x 1 2 = 12 - x 2 1 - x 3 1 10

x 1 2 = 0.9991

x 2 2 = 12 - x 1 2 - x 3 1 10

x 2 2 = 1.00019

x 3 2 = 12 - x 1 2 - x 2 2 10

x 3 2 = 1.00007

Então temos x 2 = 0.9991,1 . 00019,1.00007 .

Critério de Parada:

x 1 2 - x 1 1 = 0.0009 > ε

Não atingimos o critério, então continuamos as iterações.

Iteração 3 :

x 1 3 = 12 - x 2 2 - x 3 2 10

x 1 3 = 0.99997

x 2 3 = 12 - x 1 3 - x 3 2 10

x 2 3 = 1

x 3 3 = 12 - x 1 3 - x 2 3 10

x 3 3 = 1

Então temos x 3 = 0.99997,1 , 1 .

Critério de Parada:

x 1 3 - x 1 2 = 0.00087 > ε

Não atingimos o critério, então continuamos as iterações.

Iteração 4 :

x 1 4 = 12 - x 2 3 - x 3 3 10

x 1 4 = 1

x 2 4 = 12 - x 1 4 - x 3 3 10

x 2 4 = 1

x 3 4 = 12 - x 1 4 - x 2 4 10

x 3 4 = 1

Então temos x 4 = 1 , 1,1 .

Critério de Parada:

x 1 4 - x 1 3 = 2.6 × 10 - 5 < ε

x 2 4 - x 2 3 = 4.2 × 10 - 6 < ε

x 3 4 - x 3 3 = 3 × 10 - 6 < ε

Beleza, o critério de parada foi atingido! Então nossa aproximação é:

x = 1,1 , 1

Passo 3

b Aplicando o critério de Sassenfeld temos:

β 1 = 1 4 = 0.25 < 1

β 2 = 0.25 + 1 4 = 0.3125 < 1

β 3 = 0.3125 + 1 4 = 0.328125 < 1

β 4 = 0.328125 4 = 0.082 < 1

Logo, β = 0.328125 < 1 . O critério é satisfeito.

Passo 4

As funções de iteração são:

x 1 k + 1 = 1 + x 2 k 4

x 2 k + 1 = 1 + x 1 k + 1 + x 3 k 4

x 3 k + 1 = 1 + x 2 k + 1 + x 4 k 4

x 4 k + 1 = 1 + x 3 k + 1 4

Agora precisamos de um chute inicial. Se a gente jogar 0.5 em todas as variáveis dá valores bem próximos né? Então vamos usar x 0 = 0.5,0 . 5,0.5,0.5 .

Iteração 1 :

x 1 1 = 1 + x 2 0 4

x 1 1 = 0.375

x 2 1 = 1 + x 1 1 + x 3 0 4

x 2 1 = 0.46875

x 3 1 = 1 + x 2 1 + x 4 0 4

x 3 1 = 0.49219

x 4 1 = 1 + x 3 1 4

x 4 1 = 0.37 305

Então temos x 1 = 0.375 ,   0.46875 ,   0.49219 ,   0.37305 .

Critério de Parada:

x 1 1 - x 1 0 = 0.125 > ε

Não atingimos o critério, então continuamos as iterações.

Iteração 2 :

x 1 2 = 1 + x 2 1 4

x 1 2 = 0.36719

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

x 2 1 = 0.46484

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

x 3 2 = 0.45947

x 4 2 = 1 + x 3 2 4

x 4 2 = 0.36487

Então temos x 2 = 0.36719,0 . 46484,0.45947,0.36487 .

Critério de Parada:

x 1 2 - x 1 1 = 0.00781 > ε

Não atingimos o critério, então continuamos as iterações.

Iteração 3 :

x 1 3 = 1 + x 2 2 4

x 1 3 = 0.36621

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

x 2 3 = 0.45642

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

x 3 3 = 0.45532

x 4 3 = 1 + x 3 3 4

x 4 3 = 0.36383

Então temos x 3 = 0.36621,0 . 45642,0.45532,0.36383 .

Critério de Parada:

x 1 3 - x 1 2 = 0.00098 > ε

Não atingimos o critério, então continuamos as iterações.

Iteração 4 :

x 1 4 = 1 + x 2 3 4

x 1 4 = 0.36411

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

x 2 4 = 0.45486

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

x 3 4 = 0.45467

x 4 4 = 1 + x 3 4 4

x 4 4 = 0.36367

Então temos x 4 = 0.36411,0 . 45486,0.45467,0.36367 .

Critério de Parada:

x 1 4 - x 1 3 = 0.00211 > ε

Não atingimos o critério, então continuamos as iterações.

Iteração