Método de Gauss-Seidel: explicação, aplicações, exemplos - Ciência - 2023

science
Método de Gauss-Seidel: explicação, aplicações, exemplos - Ciência
Método de Gauss-Seidel: explicação, aplicações, exemplos - Ciência

Contente

o Método Gauss-Seidel é um procedimento iterativo para encontrar soluções aproximadas para um sistema de equações algébricas lineares com precisão escolhida arbitrariamente. O método é aplicado a matrizes quadradas com elementos diferentes de zero em suas diagonais e a convergência é garantida se a matriz for diagonalmente dominante.

Foi criado por Carl Friedrich Gauss (1777-1855), que deu uma demonstração privada a um de seus alunos em 1823. Posteriormente, foi formalmente publicado por Philipp Ludwig von Seidel (1821-1896) em 1874, daí o nome de ambos os matemáticos.

Para uma compreensão completa do método, é necessário saber que uma matriz é diagonalmente dominante quando o valor absoluto do elemento diagonal de cada linha é maior ou igual à soma dos valores absolutos dos demais elementos dessa mesma linha.


Matematicamente, é expresso assim:

Explicação usando um caso simples

Para ilustrar em que consiste o método de Gauss-Seidel, tomaremos um caso simples, no qual os valores de X e Y podem ser encontrados no sistema 2 × 2 de equações lineares mostrado abaixo:

5X + 2Y = 1

X - 4Y = 0

Passos a seguir

1- Primeiramente, é necessário determinar se a convergência é segura. Observa-se imediatamente que, de fato, é um sistema diagonalmente dominante, pois na primeira linha o primeiro coeficiente tem um valor absoluto superior aos demais da primeira linha:

|5|>|2|

Da mesma forma, o segundo coeficiente na segunda linha também é diagonalmente dominante:

|-4|>|1|

2- As variáveis ​​X e Y são resolvidas:


X = (1 - 2Y) / 5

Y = X / 4

3- Um valor inicial arbitrário, denominado "semente", é colocado: Xo = 1, I = 2.

4-A iteração começa: para obter a primeira aproximação X1, Y1, a semente é substituída na primeira equação da etapa 2 e o resultado na segunda equação da etapa 2:

X1 = (1 - 2 I) / 5 = (1 - 2 × 2) / 5 = -3/5

Y1 = X1 / 4 = (-3/5) / 4 = -3/20

5- Procedemos de forma semelhante para obter a segunda aproximação da solução do sistema de equações:

X2 = (1 - 2 Y1) / 5 = (1 - 2x (-3/20)) / 5 = 13/50

Y2 = X2 / 4 = (13/50) / 4 = 13/200

6- Terceira iteração:

X3 = (1 - 2 Y2) / 5 = (1 - 2 (13/200)) / 5 = 87/500

Y3 = X3 / 4 = (87/500) / 4 = 87/2000

7- Quarta iteração, como iteração final deste caso ilustrativo:

X4 = (1 - 2 Y3) / 5 = (1 - 2 (87/2000)) / 5 = 913/5000

Y4 = X4 / 4 = (913/5000) / 4 = 913/20000

Esses valores concordam muito bem com a solução encontrada por outros métodos de resolução. O leitor pode verificar isso rapidamente com a ajuda de um programa matemático online.


Análise de método

Como pode ser visto, no método de Gauss-Seidel, os valores aproximados obtidos para a variável anterior nessa mesma etapa devem ser substituídos na variável seguinte. Isso o diferencia de outros métodos iterativos, como o de Jacobi, em que cada etapa requer as aproximações da etapa anterior.

O método Gauss-Seidel não é um procedimento paralelo, enquanto o método Gauss-Jordan é. É também a razão pela qual o método Gauss-Seidel tem uma convergência mais rápida - em menos etapas - do que o método Jordan.

Quanto à condição de matriz diagonalmente dominante, isso nem sempre é satisfeito. No entanto, na maioria dos casos, simplesmente trocar as linhas do sistema original é suficiente para que a condição seja atendida. Além disso, o método quase sempre converge, mesmo quando a condição de dominância diagonal não é atendida.

O resultado anterior, obtido por quatro iterações do método Gauss-Seidel, pode ser escrito na forma decimal:

X4 = 0,1826

Y4 = 0,04565

A solução exata para o sistema de equações proposto é:

X = 2/11 = 0,1818

Y = 1/22 = 0,04545.

Portanto, apenas 4 iterações geram um resultado com um milésimo de precisão (0,001).

A Figura 1 ilustra como as iterações sucessivas convergem rapidamente para a solução exata.

Formulários

O método de Gauss-Seidel não se limita apenas a um sistema 2 × 2 de equações lineares. O procedimento anterior pode ser generalizado para resolver um sistema linear de n equações com n incógnitas, que é representado em uma matriz como esta:

PARAX = b

Onde PARA é uma matriz n x n, Enquanto X é o vetor n componentes das n variáveis ​​a serem calculadas; Y b é um vetor que contém os valores dos termos independentes.

Para generalizar a sequência de iterações aplicadas no caso ilustrativo a um sistema n x n, a partir do qual a variável deve ser calculada XI, a seguinte fórmula será aplicada:

Nesta equação:

– k é o índice para o valor obtido na iteração k.

-k + 1 indica o novo valor no próximo.

O número final de iterações é determinado quando o valor obtido na iteração k + 1 Difere do obtido imediatamente antes, por um valor ε que é precisamente a precisão desejada.

Exemplos do método Gauss-Seidel

- Exemplo 1

Escreva um algoritmo geral para calcular o vetor de soluções aproximadas X de um sistema linear de equações nxn, dada a matriz de coeficientes PARA, o vetor de termos independentes b, o número de iterações (iter) e o valor inicial ou "semente" do vetor X.

Solução

O algoritmo consiste em dois ciclos “To”, um para o número de iterações e outro para o número de variáveis. Seria o seguinte:

Para k ∊ [1..iter]

Para i ∊ [1..n]

X [i]: = (1 / A [i, i]) * (b [i] - ∑j = 1n(A [i, j] * X [j]) + A [i, i] * X [i])

- Exemplo 2

Verifique o funcionamento do algoritmo anterior aplicando-o em um software matemático Estúdio SMath grátis para usar, disponível para Windows e Android. Tome como exemplo o caso da matriz 2 × 2 que nos ajudou a ilustrar o método de Gauss-Seidel.

Solução

- Exemplo 3

Aplique o algoritmo de Gauss-Seidel para o seguinte sistema de equações 3 × 3, que foi previamente ordenado de forma que os coeficientes da diagonal sejam dominantes (ou seja, de maior valor absoluto do que os valores absolutos dos coeficientes de a mesma linha):

9 X1 + 2 X2 - X3 = -2

7 X1 + 8 X2 + 5 X3 = 3

3 X1 + 4 X2 - 10 X3 = 6

Use o vetor nulo como uma semente e considere cinco iterações. Comente o resultado.

Solução

Para o mesmo sistema com 10 iterações em vez de 5, os seguintes resultados são obtidos: X1 = -0,485; X2 = 1,0123; X3 = -0,3406

Isso nos diz que cinco iterações são suficientes para obter três casas decimais de precisão e que o método converge rapidamente para a solução.

- Exemplo 4

Usando o algoritmo de Gauss-Seidel fornecido acima, encontre a solução para o sistema de equações 4 × 4 fornecido abaixo:

10 x1 - x2 + 2 x3 + 0 x4 = 6

-1 x1 + 11 x2 - 1 x3 + 3 x4 = 25

2 x1 - 1 x2 + 10 x3 - 1 x4 = -11

0 x1 + 3 x2 - 1 x3 + 8 x4 = 15

Para iniciar o método, faça uso desta semente:

x1 = 0, x2 = 0, x3 = 0 e x4 = 0

Considere 10 iterações e estime o erro do resultado, comparando com a iteração número 11.

Solução

Ao comparar com a próxima iteração (número 11), o resultado é idêntico. As maiores diferenças entre as duas iterações são da ordem de 2 × 10-8, o que significa que a solução mostrada tem uma precisão de pelo menos sete casas decimais.

Referências

  1. Métodos de solução iterativa. Gauss-Seidel. Recuperado de: cimat.mx
  2. Métodos numéricos. Gauss-Seidel. Recuperado de: test.cua.uam.mx
  3. Numérico: método de Gauss-Seidel. Recuperado de: aprendeenlinea.udea.edu.co
  4. Wikipedia. Método de Gauss-Seidel. Recuperado de: en. wikipedia.com
  5. Wikipedia. Método de Gauss-Seidel. Recuperado de: es.wikipedia.com