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 e
Usando como aproximação inicial . 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 →Pegamos a primeira equação e isolamos o :
Função de iteração para o →Pegamos a segunda equação e isolamos o :
Função de iteração para o →Pegamos a terceira equação e isolamos o :
Deu pra perceber a diferença? Como na hora que vamos calcular nós já calculamos , nós usamos esse mais “atualizado” ao invés de usarmos o da iteração . O mesmo acontece no , onde nós já calculamos e .
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 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:
Aqui não temos nenhuma informação além das aproximações iniciais então usamos elas mesmo.
Opa, agora já tínhamos então usamos ele ao invés do !
E aqui já tínhamos e calculados, então foram eles que entraram.
Então ficamos com .
Critério de Parada
Novamente usamos as diferenças como critério de parada. Quando a maior dessas diferenças for menor que o erro, podemos parar as iterações.
Outro critério que também é usado é o erro relativo:
Beleza? É exatamente o mesmo procedimento, você só vai usar os valores 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
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 nós já tínhamos calculado o , então ele entrou multiplicando o termo da coluna !
Depois disso, definimos
Então, se , o critério de Sassenfeld é satisfeito e o método irá convergir. Por exemplo, no sistema que resolvemos ali em cima:
O máximo aí é o que é menor que . 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 equações e 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 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
b. Vetor
c. Vetor aproximação inicial
d. Erro
Passo 2. Definimos um contador de iterações
Passo 3. Para variando de a , defina
Passo 4. Se , FIM e retorne . Caso contrário, continue para o Passo 5
Passo 5.
Passo 6. Para variando de a , defina
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 já calculados onde e usamos os da iteração anterior apenas para .
E repito, como estamos tratando de métodos iterativos é interessante definirmos também um número máximo de iterações.
Exercício Resolvido #1
Dar exemplo de um sistema de equações 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.
Passo 1
Beleza, o enunciado dá uma breve explicação do que é um sistema diagonal dominante. Em um sistema isso significa:
E para que o sistema convirja pelo método de Gauss-Seidel temos que satisfazer o critério de Sassenfeld, que em um sistema fica:
E queremos que e . Para que isso seja satisfeito sem usarmos um sistema diagonal dominante, basta que e que por exemplo. Se liga:
No sistema acima temos:
Logo, o sistema converge pelo método de Gauss-Seidel, mas o sistema não é diagonal dominante.
Resposta
Exercício Resolvido #2
Em cada caso verifique se o critério de Sassenfeld é satisfeito e resolva por Gauss-Seidel com , se possível:
Passo 1
Verificando o critério de Sassenfeld:
Logo, . O critério é satisfeito.
Passo 2
As funções de iteração são:
Visualmente podemos ver que a solução é simplesmente né? Mas pra treinar um pouco vamos usar como aproximação inicial .
Iteração :
Então temos .
Critério de Parada:
Não atingimos o critério, então continuamos as iterações.
Iteração :
Então temos .
Critério de Parada:
Não atingimos o critério, então continuamos as iterações.
Iteração :
Então temos .
Critério de Parada:
Não atingimos o critério, então continuamos as iterações.
Iteração :
Então temos .
Critério de Parada:
Beleza, o critério de parada foi atingido! Então nossa aproximação é:
Passo 3
Aplicando o critério de Sassenfeld temos:
Logo, . O critério é satisfeito.
Passo 4
As funções de iteração são:
Agora precisamos de um chute inicial. Se a gente jogar em todas as variáveis dá valores bem próximos né? Então vamos usar .
Iteração :
Então temos .
Critério de Parada:
Não atingimos o critério, então continuamos as iterações.
Iteração :
Então temos .
Critério de Parada:
Não atingimos o critério, então continuamos as iterações.
Iteração :
Então temos .
Critério de Parada:
Não atingimos o critério, então continuamos as iterações.
Iteração :
Então temos .
Critério de Parada:
Não atingimos o critério, então continuamos as iterações.
Iteração