Método de Jacobi-Richardson

Teoria Completa

Introdução aos métodos iterativos

Fala meus jovenzitos, tudo na boa? Vamos começar agora, um assunto que é show de bola, mas que as vezes não é muito valorizado. Algumas universidades nem estudam o coitado, se você não vê esse conteúdo na facul ou não é um mega curioso e louco por aprendizado... pode pular para o próximo conteúdo que é bem convencional.

Agora, se você é do grupo que precisa aprender ou tá curioso com esse negócio, vem comigo que é só sucesso!!!! A primeira coisa que vamos fazer, é retomar conceitos sobre métodos iterativos que abordamos em outros conteúdos, e se você não lembra tá tudo bem!

Vamos partir do mais abstrato possível. Os métodos iterativos funcionam através das iterações, que são basicamente etapas para encontrar uma resposta. E essas etapas sempre dependem das etapas anteriores. Até aí tudo ok né?

Uma coisa importante nos métodos iterativos é que precisamos sempre saber se o resultados que estamos conseguindo a cada iteação está convergindo para a solução real ou não. E para saber se estamos “chegando lá” temos critérios de parada que vai nos guiar e falar “hey filhão, já pode parar aí beleza?” ou até mesmo “Amada, pare agora”.

Agora que conseguimos dar uma pincelada em conceitos bem importantes, vamos para o que interessa aqui. Que raios é o método de Jacobi-Richardson? Esse maluco é o mesmo do Gauss-Jacobi? Hahhahahaaha

Vem comigo, que vamos aprender a calcular essa parada aí!

Jacobi-Richardson

O método de Jacobi-Richardson é um método iterativo para resolver sistemas lineares. Tá, mas como é que ele vai fazer isso?

Imagine que nós temos um sistema qualquer de A x = b .

Por exemplo:

a 11 x 1 + a 12 x 2 = b 1

a 21 x 1 + a 22 x 2 = b 2

Mas a nossa matriz pode ter ordem n de linhas e colunas!

De acordo com o Jacobi-Richarson a nossa matriz A do sistema, pode ser separada em:

A = L + D + R

Onde :

L : Matriz triangular inferior formada pela parte inferior de A;

D : Matriz diagonal formada pela diagonal de A;

R : Matriz triangular superior formada pela parte superior de A.

Representando em termos de matriz, fica mais ou menos assim:

A nossa matriz A   ( 3 × 3 ) :

A = L + D + R

A = a 11 a 12 a 13 a 21 a 22 a 23 a 31 a 32 a 33

Através de uma séeeeerie de cálculos e modificações matemáticas, e entendendo que o d e t ( D ) ≠ 0 , conseguimos chegar na nossa queridinha função iteração:

x ( k + 1 ) = - D - 1 L + R x ( k ) + D - 1 b

Maaaas, por via de regra e para facilitar nossa vida, são feitas mais algumas modificações para que a gente não tenha que calcular D:

x ( k + 1 ) = - L * + R * x ( k ) + b *

E é com essa função que ós iremos trabalhar!

Aqui nesse processo iterativo de Jacobi-Richardson, vamos convergir de modo que:

L * + R * < 1

Mas não se desespere, você já vai ver que tudo nesse mundo ainda faz sentido. Afinal, antes de calcularmos o sistema, temos que cumprir um passo muito importante: ver se o nosso sistema satisfaz o critério de convergência!

Alô Alô Convergência!

Acabamos de embarcar num ponto importantíssimo do nosso problema, ver se o sistema satisfaz ou não o critério de convergência, que é basicamente o que vai garantir se nós podemos achar a solução do probleminha ou não!

O primeiro critério a ser atendido é: a nossa matriz é diagonal dominante ?

Eita! Como assim?

Um matriz diagonal dominante tem o módulo do elemento da diagonal maior que a soma dos módulos de todos os outros elementos da linha, se esse critério é atendido, nós automaticamente matamos todos os outros e B   =   - L   *   +   R *     .

Então, o critério das linhas será satisfeito se:

| a 11 | = | a 12 | + | a 13 |

| a 22 = | a 21 + a 23

| a 33 | = | a 31 | + | a 32 |

Isso tudo, até a ordem n.

Uma coisa importante aqui é, devemos atender pelo menos um dos critérios para poder efetuar os cálculos.

O próximo critério é o critério das linhas : Para calcular o critério das linhas, devemos primeiro retornar a nossa matriz e vamos pegar o termo dominante de cada linha (linha 1: a 11 , linha 2:   a 22 , linha 3: a 33 ). E dividiremos os demais temos pelos termos dominantes, por exemplo:

a * 12 = a 12 a 11

a * 13 = a 13 a 11

a * 21 = a 21 a 22

a * 23 = a 23 a 22

a * 31 = a 31 a 33

a * 32 = a 32 a 33

MARCA BEM ESSE PASSO, USAREMOS EXATAMENTE O MESMO NO CRITÉRIO DAS COLUNAS!

Alíás, se a matriz tiver a extensão b, nós calculamos um b novo para cada linha também beleza? É só dividir o valor de b atual, pelo valor do termo “dominante”.

b * = b n a n n

Aí então, montamos um novo sisteminha com essa alteração e também fazemos a norma dos termos da mesma linha (exceto o termo dominante):

| a * 12 | + a * 13 < 1

a * 21 + a * 23 < 1

a * 31 + a * 32 < 1

O máximo valor obtido da soma de cada um desses grupos deve ser menor que 1!

E por fim, temos o critério das coluna! O critério das colunas vai usar aqueles temos que calculamos no critério das linhas, a única diferença é que dessa vez somaremos os termos que pertencem a cada coluna (com exceção do termo dominante), assim:

| a * 21 | + a * 31

a * 12 + a * 32

a * 13 + a * 23

O critério continua valendo, o máximo valor obtido da soma de cada um desses grupos deve ser menor que 1!

Bora Calcular!

Agora nós já aprendemos a definir os critérios de convergência, para calcular, nós montamos uma matriz nova né? Com essa carinha aqui:

a * 12 x 1 + a * 13 x 2 = b * 1 a * 21 x 1 + a * 23 x 2 = b * 2 a * 31 x 1 + a * 32 x 2 = b * 3

Sabe qual é a nossa função iteração?

EXATAMENTE, o nosso sistema!

x 1 ( k + 1 ) = a * 12 x 2 + a * 13 x 3 = b * 1 x 2 ( k + 1 ) + a * 21 x 2 + a * 23 x 3 = b * 2 x 3 ( k + 1 ) = a * 31 x 2 + a * 32 x 3 = b * 3

Quer dizer que é só montar o sisteminha maroto e resolver????

ISSO MEXXXXXXMO!

Geralmente, o prof vai te dar um conjunto de valores iniciais, você vai basicamente jogar esses valores no lugar de x até chegar em um valor novo de x ( k + 1 ) , aí você vê se atendeu o critério de parada ou não. Aí meu caro, se não atender ao critério, você usa esses valores novos de   x até atingir o critério de parada.

É só olhar na tabelinha, e ver qual quem será meu novo valor a ser usado.

E qual é o critério de parada?

Os erros absolutos e relativos, entre cada termo:

Vamos fazer exercício, que vai ficar bem mais fácil de entender!

Expandir

Exercício Resolvido #1

Adaptado livro de Cálculo Numérico UFF- Jacumina

Utilize os critérios das linhas para garantir convergência:

MOSTRAR SOLUÇÃO COMPLETA

Passo 1

Um ponto importante em Jacobi-Richardson é que o critério das linhas será satisfeito se:

Na verdade, diferente de outros métodos, se nós conseguirmos garantir qualquer um, tipo, qualquer critério mesmo...Pasme, aí garantimos a convergência.

É isso mesmo, garantir um critério só já é sucesso.

Vemos que uma matriz qualquer A é estritamente diagonar dominante se a soma dos termos a i j da linha i for menor (em módulo) que o termo dominante da linha a i i .

Tendo o nosso sistema:

Existem duas maneiras de satisfazer o critério das linhas, primeiro é testar se a matriz é estritamente diagonal dominante e o outro falaremos no passo 2.

Vamos entender em termos de linhas e colunas:

| a 11 | = | a 12 | + | a 13 |

| a 22 = | a 2 1 + a 2 3

| a 33 | = | a 3 1 | + | a 3 2 |

Agora, testaremos se a matriz é estritamente dominante:

| a 11 = | a 12 + a 13 = 2 + 1 < | 10 |

| a 22 = | a 21 + a 23 = 1 + 1 < | 5 |

| a 33 = | a 31 + a 32 = 2 + 3 < | 10 |

Apenas com esse critério, já garantimos que Jacobi-Richardson pode ser implementado!

Passo 2

Para calcular o critério das linhas propriamente dito, voltaremos láaaaaa pra nossa matriz:

Faremos o seguinte, vamos pegar o termo dominante de cada linha (linha 1: a 11 , linha 2:   a 22 , linha 3: a 33 ). E dividiremos os demais temos pelos termos dominantes:

a 12 = a 12 a 1 1 = 2 10 = 0,2

a 1 3 = a 1 3 a 11 = 1 10 = 0,1

a 2 1 = a 2 1 a 22 = 1 5 = 0,2

a 23 = a 2 3 a 22 = 1 10 = 0 , 2

a 31 = a 31 a 33 = 2 10 = 0,2

a 32 = a 3 2 a 33 = 3 10 = 0 , 3

Montando a função temos:

Mesmo não sendo necessário, já que garantimos a convergência no passo anterior, podemos calcular novamente os módulos assim:

| a 11 = | a 12 + a 13 = 0,2 + 0 , 1 = 0,3

| a 22 = | a 21 + a 23 = 0,2 + 0,2 = 0,4

| a 33 = | a 31 + a 32 = 0 , 2 + 0 , 3 = 0,5

Perceba que 0,5 foi o maior valor obtido, então é o nosso máximo, e o valor máximo deve ser sempre menor que 1. Então se 0,5

Resposta

0,5 < 1  

Critério atendido

Exercício Resolvido #2

Adaptado livro de Cálculo Numérico UFF- Jacumina

Ainda com o exercício anterior, calcule o critério de colunas necessário para garantir a convergência:

MOSTRAR SOLUÇÃO COMPLETA

Passo 1

Apesar de sabermos que o critério das linhas e da dominância já foram atendidos, é importante aprender a calcular o critério das colunas também.

Tendo o nosso sistema:

Masssss, vamos usar a função divisão que obtivemos no exercício anterior:

Mas como o nome do método já diz, testaremos as colunas

| a 21 | + a 3 1 = 0,2 + 0,2 = 0,4

a 1 2 + a 3 2 = 0,2 + 0,3 = 0 , 5

a 1 3 + a 2 3 = 0,1 + 0 , , 2 = 0,3

Nesse caso, 0,5

Apenas com esse critério, já garantimos que Jacobi-Richardson pode ser implementado!

Resposta

Critério atendido

Exercício Resolvido #3

Adaptado livro de Cálculo Numérico UFF- Jacumina

Utilize os critérios das linhas para garantir convergência:

MOSTRAR SOLUÇÃO COMPLETA

Passo 1

Um ponto importante em Jacobi-Richardson é que o critério das linhas será satisfeito se:

Para calcular o critério das linhas propriamente dito, voltaremos láaaaaa pra nossa matriz:

Faremos o seguinte, vamos pegar o termo dominante de cada linha (linha 1: a 11 , linha 2:   a 22 , linha 3: a 33 ). E dividiremos os demais temos pelos termos dominantes:

a 12 = a 12 a 11 = 1 10 = 0 , 1

a 13 = a 13 a 11 = - 1 10 = -   0,1

a 21 = a 21 a 22 = 1 10 = 0 , 1

a 23 = a 23 a 22 = 1 10 = 0 , 1

a 31 = a 31 a 33 = 2 10 = 0,2

a 32 = a 32 a 33 = - 1 10 = - 0 , 1

1 x 1 + 0 , 1 x 2 - 0,1 x 3 0,1 x 1 + 1 x 2 + 0,1 x 3 0 , 2 x 1 - 0,1 x 2 + 1 x 3

Passo 2

Mesmo não sendo necessário, já que garantimos a convergência no passo anterior, podemos calcular novamente os módulos assim:

| a 11 = | a 12 + a 13 = 0 , 1 + - 0,1 = 0 , 2