Método de Gauss-Jacobi

Teoria Completa

Vamos entrar agora no método iterativo de Gauss-Jacobi (já percebeu que a bagaça toda tem o nome do Gauss no meio? O cara foi muito mito!).

Bom, voltando ao assunto, como um 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.

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

Como esse método é iterativo, precisamos de uma aproximação inicial, vulgo chute inicial. Nesse caso, nosso chute inicial é x 1 , x 2 , x 3 = - 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 vai usar? Nós vamos tirar essas funções do próprio sistema, se liga:

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 + 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 + x 2 k 3

Deu pra pegar o espírito né? De forma geral, a função de iteração para um x i 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 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

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

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

x 2 1 = 5.0 1 ¯

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

x 3 1 = 14 + 1.8 + 5.5 3

x 3 1 = 7.1

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

Critério de Parada

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 < ε

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 < ε

Vamos usar aqui o erro absoluto:

x 1 1 - x 1 0 = 0.5 > ε

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.

Iteração 2:

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

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

x 1 2 = - 2.0 2 ¯

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

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

x 2 2 = 5.1 6 ¯

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

x 3 2 = 14 + 2.3 + 5.0 1 ¯ 3

x 3 2 = 7.1 037 ¯

Então ficamos com x 2 = - 2.0 2 ¯ ,   5.1 6 ¯ ,   7.1 037 ¯ .

Critério de Parada

x 1 2 - x 1 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 < ε

x 2 4 - x 2 3 = 0.02 < ε

x 3 4 - x 3 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

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

α = max 1 ≤ k ≤ n ⁡ α k

Então, se α < 1 , o critério das linhas é 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 + 3 9 = 7 9

α 3 = 1 + 1 3 = 2 3

O máximo aí é 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. 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 (testa aí)! 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.

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é.

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

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.

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 , partindo de X 0 = 0 , 0,0 t e usando o sistema de forma tal que a convergência do método esteja garantida.

MOSTRAR SOLUÇÃO COMPLETA

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 L 1 ↔ L 2 :

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