Método de Gauss-Jacobi
Teoria
FAAAAALA, AÍ!
E se o seu professor pede pra vc resolver pelo metodo de Gauss-Jacobi esse sistema linear abaixo?!
Você pira?? Calma!! Para encontrarmos essa solução, o nosso velho e bom amigo Gauss inventou um método iterativo que vai nos ajudar! Sim! Estou falando do nosso amigo que está em quase todas as bagaças: Gauss-Jacobi (Provavelmente um dos caras mais populares na Matemática).
O objetivo desse método é encontrar uma aproximação desejada para a solução de sistemas lineares. Porém, para poder aplicar esse método, precisamos primeiro falar sobre convergência, pois só poderemos aplicar esse método se o sistema linear convergir. Show de bola?!
Critério de Convergência
Uma condição suficiente para a convergência do método de Gauss-Jacobi é o critério das linhas. Ele diz o seguinte:
Sejam
Definimos
Ou seja, o deve ser igual ao máximo, beleza?!
Então, se , o critério das linhas é satisfeito e o método irá convergir.
Vamos ver um exemplo para entender na prática como funciona?
Exemplo
Imagine que temos o seguinte sistema:
Vamos calcular de acordo com a fórmula acima:
Agora e
O maior dos valores encontrados é o que é menor que .
Logo, o critério das linhas é satisfeito e o método com certeza converge.
Uma consequência interessante desse critério de convergência é que a ordem das equações pode influenciar o resultado do método apesar de não alterar em nada o sistema. Por exemplo, o sistema linear abaixo
não satisfaz o critério das linhas, já que temos de cara . Logo, pode ser que o método convirja, mas pode ser que não convirja também. Não podemos afirmar nada! No entanto, se trocarmos as duas primeiras equações de lugar ficamos com:
Que é equivalente ao sistema original e satisfaz o critério das linhas (Pode testar)! Ou seja, agora temos certeza que o método vai convergir, então é mais seguro usarmos nesse sistema ;)
Então, sempre que um sistema não satisfizer o critério tenta rearrumar as equações ou fazer alguma combinação entre elas pra tentar satisfazer na marra haha.
Método de Gauss-Jacobi
Bom, voltando ao assunto, como o método é iterativo, ele consiste em melhorar uma aproximação inicial por meio de repetidas iterações até chegarmos a uma precisão mínima desejada.
O melhor jeito de entender esse método é vendo um exemplo prático, então eu vou explicando tudinho enquanto resolvemos.
Exemplo
Resolva o sistema linear abaixo com e
Como esse método é iterativo, precisamos de uma aproximação inicial, vulgo chute inicial. Nesse caso, nosso chute inicial é . Aquele em cima do é o número da iteração em que estamos ;)
Beleza, e qual será a função de iteração que a gente deve usar? Nós vamos tirar essas funções do próprio sistema, se liga:
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 y:
Função de iteração para o Pegamos a terceira equação e isolamos o :
Deu pra pegar o espírito né?! De forma geral, a função de iteração para um (iésima incognita) qualquer em um sistema de equações é obtida pegando a iésima equação e isolando o .
Continuando o processo, o que faremos agora é aplicar essas funções de iteração nas nossas aproximações iniciais:
Iteração 1:
Mesmo procedimento para o :
Análogo para :
Então ficamos com .
Obs.: Quando eu disse que o método com certeza converge quando o critério das linhas é satisfeito eu tava falando muito sério! Tipo, para qualquer chute inicial!!! Ou seja, quando tiver complicado ou se você só tiver sem paciência para achar uma aproximação pro vetor solução, pode simplesmente usar que vai convergir! Pode usar quaisquer valores na verdade, mas zeros são mais fáceis de trabalhar né.
Critério de Parada
Essas iterações uma hora precisam parar, concorda?! Vamos ver agora quando podemos parar de fazer as iterações porque encontramos uma aproximação boa o suficiente, beleza?!
O critério de parada normalmente usado são as diferenças . Quando a maior dessas diferenças for menor que o erro, podemos parar as iterações.
Ou seja, no nosso exemplo teremos:
Show de bola?!
Repare que se esse já deu maior e o que consideramos é o máximo, então com certeza o critério de parada não foi atingido haha. Continuamos as iterações.
Outro critério que também pode ser usado é o erro relativo:
Iteração 2:
Para o
Para o :
Então ficamos com .
Critério de Parada
Já deu pra pegar o espírito né?! Só pra não deixar o exemplo em aberto, na quarta iteração vamos obter . E pelo critério de parada teremos:
Como todos eles satisfazem, nossa aproximação é . Deu pra perceber que o valor exato é né?! haha
Algoritmo
Terminada toda a teoria, vamos para o algoritmo!
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
E é isso aí! Como estamos tratando de métodos iterativos que precisam alcançar um critério para parar, é interessante definirmos também um número máximo de iterações para não corrermos o risco de acabarmos em um loop infinito, beleza?!
Exemplo
Método de Gauss-Jacobi
Exemplo
Critério de Parada
Algoritmo
Exercícios Resolvidos
Exercício Resolvido #1
Lista 5 – Professora Susana – Questão 4
Dado o sistema:
Calcule, pelo método de Gauss-Jacobi uma primeira aproximação , partindo de e usando o sistema de forma tal que a convergência do método esteja garantida.
Passo 1
Para que a convergência do método esteja garantida precisamos atender ao critério das linhas. Para isso podemos fazer as trocas :
E em seguida a troca :
Dessa forma temos:
Então o critério das linhas é atendido e a convergência é garantida.
Passo 2
As funções de iteração são:
E temos
Iteração :
Pronto, obtemos nossa aproximação .
Resposta
.
Exercício Resolvido #2
Lista 3 – Professora Juliana – UFRJ – Questão 6 adaptada
Sejam
Mostre que o método de Gauss-Jacobi converge para .
Resolva usando Gauss-Jacobi com três dígitos de precisão e aproximação inicial .
Passo 1
Aplicando o critério das linhas temos:
Então, o critério das linhas é atendido e a convergência é garantida.
Passo 2
As funções de iteração são:
E temos
E como queremos três dígitos de precisão vamos usar . Assim garantimos que as três primeiras casas decimais estarão corretas.
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 :
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 é:
Resposta
Exercício Resolvido #3
Lista 3 – Professor Daniel – UFRJ – Questão 10
Em cada sistema linear abaixo, verifique o critério das linhas e resolva pelo método de Gauss-Jacobi com uma precisão .
Passo 1
Aplicando o critério das linhas temos:
Então, o critério das linhas é atendido e a convergência é garantida.
Passo 2
As funções de iteração são:
Agora precisamos de um chute inicial. Não precisa nem pensar muito pra perceber que a solução é né? Então vamos usar como aproximação inicial com .
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 :
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 das linhas temos:
Então, o critério das linhas é atendido e a convergência é garantida.
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 como chute inicial e
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 :
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 é:
Resposta
Exercício Resolvido #4
Richard L. Burden e J. Douglas Faires, Numerical Analysis, 9ª ed. Brooks/Cole, Cengage Learning, pag 460, exercício 5 adaptado.
Use o método de Gauss-Jacobi para resolver os sistemas abaixo utilizando e .
Passo 1
As funções de iteração são:
Como aproximação inicial temos e .
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 :
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 2
As funções de iteração são:
e .
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 :
Então temos .
Critério de Parada:
Beleza, o critério de parada foi atingido! Então nossa aproximação é:
Resposta
Exercício Resolvido #5
Richard L. Burden e J. Douglas Faires, Numerical Analysis, 9ª ed. Brooks/Cole, Cengage Learning, pag 460, exercício 6 adaptado.
Use o método de Gauss-Jacobi para resolver os sistemas abaixo utilizando e .
Passo 1
As funções de iteração são:
Como aproximação inicial temos e .
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 :
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 2
As funções de iteração são:
e .
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 :
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 é:
Resposta
Exercício Resolvido #6
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 157, exemplo 10 adaptado.
Resolva o sistema linear:
Pelo método de Gauss-Jacobi com e
Passo 1
Já que é para resolver, bora achar as equações de iteração. Pra isso, basta a gente isolar na primeira equação o , na segunda o e na terceira o
Passo 2
Iteração 1:
Será que já podemos parar?
Critério de Parada:
Deu ruim logo de cara hein!! Então precisamos de mais iterações.
Iteração 2:
Será que já podemos parar?
Critério de Parada:
Puuutz furou no segundo =(
Bora fazer mais iterações!!
Iteração 3:
Será que já podemos parar?
Critério de Parada:
AEEEEW ATÉ QUE ENFIM!!!
Resposta
Exercício Resolvido #7
Lista de Exercícios – FEI (Adaptado)
Resolva o sistema linear:
Pelo método de Gauss-Jacobi com e
Passo 1
A primeira coisa a se fazer vai ser achar as equações de iteração. Pra isso, basta a gente isolar na primeira equação o , na segunda o e na terceira o
Passo 2
Iteração 1:
Será que já podemos parar?
Critério de Parada:
Deu ruim logo de cara hein!! Então precisamos de mais iterações.
Iteração 2:
Será que já podemos parar?
Critério de Parada:
Puuutz furou no segundo =(
Bora fazer mais iterações!!
Iteração 3:
Será que já podemos parar?
Critério de Parada:
Iteração 4:
Será que já podemos parar?
Critério de Parada:
MEU DEUS QUE LOUCURAAAA, ainda não acabou....BORA FAZEr Mais uma ITERAÇão
Iteração 5:
Será que já podemos parar?
Critério de Parada:
Precisa mais uma iteração malukooo
Iteração 6:
Será que já podemos parar?
Critério de Parada:
Tá quaaaase, QUE QUE A GENTE FEZ PRA MERECER ISSOOOO?
Iteração 7:
Será que já podemos parar?
Critério de Parada:
BATEEEU ....BATEUUU, atendeu o critério de parada
Resposta
Exercício Resolvido #8
Lista de Exercícios - FEI
Resolva o sistema linear:
Pelo método de Gauss-Jacobi com e
Passo 1
A primeira coisa a se fazer vai ser achar as equações de iteração. Pra isso, basta em cada equação a gente isolar uma variável.
Passo 2
Iteração 1:
Será que já podemos parar?
Critério de Parada:
Deu ruim logo de cara hein!! Então precisamos de mais iterações.
Iteração 2:
Será que já podemos parar?
Critério de Parada:
Puuutz furou =(
Bora fazer mais iterações!!
Iteração 3:
Será que já podemos parar?
Critério de Parada:
Iteração 4:
Será que já podemos parar?
Critério de Parada:
MEU DEUS QUE LOUCURAAAA, falhou no últimooo. Acho que mais uma iteração já deve dar...
Iteração 5:
Será que já podemos parar?
Critério de Parada:
ATENDEU TODOOOS, então tá resolvido!!