Método de Gauss-Seidel

O método de Gauss-Seidel é um método iterativo para resolução de sistemas de equações lineares. O seu nome é uma homenagem aos matemáticos alemães Carl Friedrich Gauss e Philipp Ludwig von Seidel. É semelhante ao método de Jacobi (e como tal, obedece ao mesmo critério de convergência). É condição suficiente de convergência que a matriz seja estritamente diagonal dominante, i. e., fica garantida a convergência da sucessão de valores gerados para a solução exacta do sistema linear.

Procuramos a solução do conjunto de equações lineares, expressadas em termos de matriz como

A iteração Gauss-Seidel é

$x^{(k+1)} = \left( {D - L} \right)^{ - 1} \left( {U x^{(k)} + b} \right),$

onde $A=D+L+U$; as matrizes $D$, $L$, e $U$ representam respectivamente os coeficientes da matriz $A$: a diagonal, triangular estritamente inferior, e triangular estritamente superior; e $k$ é o contador da iteração. Esta expressão matricial é utilizada principalmente para analisar o método. Quando implementada, Gauss-Seidel, uma aproximação explícita de entrada por entrada é utilizada:

$x^{(k+1)}_i = \frac{1}{a_{ii}} \left(b_i - \sum_{j<i}a_{ij}x^{(k+1)}_j-\sum_{j>i}a_{ij}x^{(k)}_j\right),\, i=1,2,\ldots,n.$

Diferenciando-se do método de Gauss-Jacob:

$x^{(k+1)}_i = \frac{1}{a_{ii}} \left(b_i - \sum_{j=1,j\ne i}^{n} a_{ij}x_{j}^{(k)}\right),\, i=1,2,\ldots,n$

Sendo que o método de Gauss-Seidel apresenta convergência mais rápida que este último.

Note que o cálculo de $x^{(k+1)}_i$ utiliza apenas os elementos de $x^{(k+1)}\,$ que já havia sido calculada e apenas aqueles elementos de $x^{(k)}\,$ já haviam avançado para a iteração $k+1$. Isto significa que nenhum armazenamento adicional é necessário, e que computacionalmente pode ser substituído ($x^{(k)}\,$ por $x^{(k+1)}\,$). A iteração geralmente continua até que a solução esteja dentro da tolerância especificada.

Pseudocódigo

escolher uma aproximação inicial x = (x1, …, xn)
fazer até convergir:
  para i := (1, …, n):
    σ = 0
    para j := (1, …, i-1, i+1 , …, n):
      σ = σ + aij * xj
    próximo j
    xi = (bi - σ) / aii
  próximo i
próximo fazer

Exemplo

Utilizando a equação dois, vamos calcular uma iteração da matriz, sendo que a análise da convergência é dada pela diagonal dominante, ou seja, o a soma dos módulos de todos os elementos em que i difere de j de uma dada linha tem que ser menor do que o módulo do elemento em que i é igual a j nesta mesma linha. Verificado isso, parte-se para a próxima etapa:

Matriz:

$\,\!\left\{\begin{matrix}4x_{1}-x_{2}-x_{3}=-1\\-x_{1}+4x_{2}-x_{3}-x_{4}=2\\-x_{1}-x_{2}+4x_{3}-x_{4}-x_{5}=6\\-x_{2}-x_{3}+4x_{4}-x_{5}=2\\-x_{3}-x_{4}+4x_{5}=-1\end{matrix}\right.$

Em que bi é igual:

$b_{i} = \begin{pmatrix} -1\\ 2\\ 6\\ 2\\ -1\\ \end{pmatrix}$

Usando a equação: $x^{(k+1)}_i = \sum_{j=1,j\ne i}^{n} \frac{a_{ij}}{a_{ii}}+x_{j}^{(k)}+\frac{b_{i}}{a_{ii}},\, i=1,2,\ldots,n$

Obtemos o sistema :

$\,\!\left\{\begin{matrix}x^{(k+1)} = -\frac{1}{4}+0.25x_{2}^{(k)}+0.25x_{3}^{(k)}\\ \\ x^{(k+1)} = \frac{1}{2}+0.25x_{1}^{(k)}+0.25x_{3}^{(k)}+0.25x_{4}^{(k)}\\ \\ x^{(k+1)} = \frac{3}{2}+0.25x_{1}^{(k)}+0.25x_{2}^{(k)}+0.25x_{4}^{(k)}+0.25x_{5}^{(k)} \\ \\ x^{(k+1)} = \frac{1}{2}+0.25x_{2}^{(k)}+0.25x_{3}^{(k)}+0.25x_{5}^{(k)}\\ \\ x^{(k+1)} = -\frac{1}{4}+0.25x_{3}^{(k)}+0.25x_{4}^{(k)}\end{matrix}\right.$

Utilizando a pressuposição inicial de vetor nulo:

$x^{(0)} = \begin{pmatrix} 0\\ 0\\ 0\\ 0\\ 0\\ \end{pmatrix}$

É necessário notar que, ao fazer as iterações, o x que recebe o valor é substituido e jogado na equação de baixo. Por exemplo:

$x^{(1)} = -\frac{1}{4}+0.25x_{2}^{(k)}+0.25x_{3}^{(k)}$

Resulta em:

$x^{(1)} = -\frac{1}{4}+0.25*0+0.25*0$

Que resulta em:

$x^{(1)} = -0.25$

Como esse é jogado na equação seguinte, no caso x2:

$x^{(2)} = \frac{1}{2}+0.25x_{1}^{(k)}+0.25x_{3}^{(k)}+0.25x_{4}^{(k)}$

Após a substituição essa ficará assim:

$x^{(2)} = \frac{1}{2}+0.25*(-0.25)+0.25*0+0.25*0$

Ou seja, somente o valor de x1 está definido, pois uma iteração já havia sido feita, o resto dos x's assumem seu valor inicial, no caso, zero. Por fim, após uma iteração temos:

$\,\!\left\{\begin{matrix}x_{1}^{(1)} = -0.25 \\ \\x_{2}^{(1)} = 0.4375 \\ \\x_{3}^{(1)} = 1.546875 \\ \\x_{4}^{(1)} = 0.99609375 \\ \\x_{5}^{(1)} = 0.3857421875 \end{matrix}\right.$

Calculando o Erro

O cálculo do erro consiste em se pegar a maior diferença entre as raizes da iteração k-1 e k, e dividi-las por o valor de x máximo da iteração atual;

$x^{(2)} = \frac{{MAX}_|x_{1}^{(1)}-x_{1}^{(0)}|}{\frac{MAX}{1<=i<=n}|x_{i}^{(k)}|}$

Diferenças:

$\,\!\left\{\begin{matrix}|x_{1}^{(1)}-x_{1}^{(0)}| = |-0.25-0| = 0.25 \\ \\|x_{2}^{(1)}-x_{2}^{(0)}| = 0.4375 \\ \\|x_{3}^{(1)}-x_{3}^{(0)}| = 1.546875 \\ \\|x_{4}^{(1)}-x_{4}^{(0)}| = 0.99609375 \\ \\|x_{5}^{(1)}-x_{5}^{(0)}| = 0.3857421875 \end{matrix}\right.$

Erro da primeira iteração:

$MR^{(1)} = \frac{1.546875}{1.546875} = 1$

Ligações externas

• Algoritmo em pseudo-código (em português)
• Código fonte da implementação do método em GNU Octave