# 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({-Ux^{(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_{i}^{(k+1)}={\frac {1}{a_{ii}}}\left(b_{i}-\sum _{j<i}a_{ij}x_{j}^{(k+1)}-\sum _{j>i}a_{ij}x_{j}^{(k)}\right),\,i=1,2,\ldots ,n.$
Diferenciando-se do método de Gauss-Jacob:
    $x_{i}^{(k+1)}={\frac {1}{a_{ii}}}\left(b_{i}-\sum _{j=1,j\neq 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_{i}^{(k+1)}$ 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

O pseudocódigo a seguir descreve um algoritmo baseado no método de Gauss-Seidel. As variáveis de entrada são: a matriz de coeficientes $A$, o vetor dos termos constantes $b$, a tolerância $TOL$ para o critério de parada e o número máximo de iterações. A saída é a aproximação calculada da solução de $Ax=b$ ou mensagem de que o critério de parada não foi satisfeito.

### Javascript

Abaixo é apresentado a resolução utilizando a linguagem JavaScript.

## 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_{i}^{(k+1)}=\sum _{j=1,j\neq 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-1)}+0.25x_{4}^{(k-1)}$
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 raízes da iteração k-1 e k, e dividi-las por o valor de x máximo da iteração atual;
    $erro^{(k)}={\frac {\max \left|x_{i}^{(k)}-x_{i}^{(k-1)}\right|}{\displaystyle \max _{1\leq i\leq n}\left|x_{i}^{(k)}\right|}}$
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$