Método de Gauss-Jacobi

Teoria Completa

FAAAAALA, AÍ!

E se o seu professor pede pra vc resolver pelo metodo de Gauss-Jacobi esse sistema linear abaixo?!

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

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

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

α 2 = a 21 + a 23 + … + a 2 n a 22

α k = ∑ j = 1   j ≠ k   n a k j ∙ 1 a k k

Definimos

α = α k   m á x  

Ou seja, o α deve ser igual ao α máximo, beleza?!

Então, se α < 1 , 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:

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

Vamos calcular α 1   de acordo com a fórmula acima:

α 1 = 3 + 1 6 = 4 6

Agora α 2   e α 3

α 2 = 4 + 3 9 = 7 9

α 3 = 1 + 1 3 = 2 3

O maior dos valores encontrados é o α 2 que é menor que 1 .

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

2 x 1 + 5 x 2 + x 3 = - 2 7 x 1 - 5 x 2 + x 3 = 4 2 x 1 + 3 x 2 - 8 x 3 = 12

não satisfaz o critério das linhas, já que temos de cara α 1 = 3 . 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:

7 x 1 - 5 x 2 + x 3 = 4 2 x 1 + 5 x 2 + x 3 = - 2 2 x 1 + 3 x 2 - 8 x 3 = 12

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 x 0 = - 1.8   5.5   7.3   e ε = 0.1

6 x + 3 y + z = 10 4 x + 9 y - 3 z = 16 x - y + 3 z = 14

Como esse método é iterativo, precisamos de uma aproximação inicial, vulgo chute inicial. Nesse caso, nosso chute inicial é x , y , z = - 1.8,5.5,7.3 . Aquele 0 em cima do x é 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 x   →   Pegamos a primeira equação e isolamos o x :

6 x + 3 y + z = 10

x k + 1 = 10 - 3 y k - z k 6

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

4 x + 9 y - 3 z = 16

y k + 1 = 16 - 4 x k + 3 z k 9

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

x - y + 3 z = 14

z k + 1 = 14 - x k + y k 3

Deu pra pegar o espírito né?! De forma geral, a função de iteração para um x i (iésima incognita) qualquer em um sistema de n equações é obtida pegando a iésima equação e isolando o x i .

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

Iteração 1:

x 1 = 10 - 3 y 0 - z 0 6

x 1 = 10 - 3 ∙ 5.5 - 7.3 6

x 1 = - 2.3

Mesmo procedimento para o y :

y 1 = 16 - 4 x 0 + 3 z 0 9

y 1 = 16 - 4 ∙ - 1.8 + 3 ∙ 7.3 9

y 1 = 5.0 1 _

Análogo para z :

z 1 = 14 - x 1 0 + y 0 3

z 1 = 14 + 1.8 + 5.5 3

z 1 = 7.1

Então ficamos com x 1 = - 2.3 ,   5.0 1 _ ,   7.1 .

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 x 0 = 0,0 , … , 0 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 x i k + 1 - x i k . 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 < ε

Ou seja, no nosso exemplo teremos:

x 1 1 - x 1 0 = 0.5 > ε

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:

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

Iteração 2:

x 2 = 10 - 3 y 1 - z 1 6

x 2 = 10 - 3 ∙ 5.0 1 _ - 7.1 6

x 2 = - 2.0 2 _

Para o y :

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

y 2 = 16 - 4 ∙ - 2.3 + 3 ∙ 7.1 9

y 2 = 5.1 6 _

Para o z :

z 2 = 14 - x 1 + z 1 3

z 2 = 14 + 2.3 + 5.0 1 _ 3

z 2 = 7.1 037 _

Então ficamos com y 2 = - 2.0 2 _ ,   5.1 6 _ ,   7.1 037 _ .

Critério de Parada

x 2 - x 1 = 0.2 7 _ > ε

Já deu pra pegar o espírito né?! Só pra não deixar o exemplo em aberto, na quarta iteração vamos obter x 4 = - 2.033,5.066,7.048 . E pelo critério de parada teremos:

x 1 4 - x 1 3 = 0.07 < ε

y 4 - y 3 = 0.02 < ε

z 4 - z 3 = 0.015 < ε

Como todos eles satisfazem, nossa aproximação é x _ = - 2.033,5.066,7.048 . Deu pra perceber que o valor exato é x = - 2,5 , 7 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 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   j ≠ i   n a i j ∙ x j 0

Passo 4. Se 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

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?!

Expandir

Exercício Resolvido #1

Lista 5 – Professora Susana – Questão 4

Dado o sistema:

x - 3 y + z = 5     2 y + 5 z = 9 2.1 x + y + z = 3

Calcule, pelo método de Gauss-Jacobi uma primeira aproximação X 1