Método de Gauss-Seidel

Predefinição:Sem fontes 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_i^{(k+1)}=\frac{1}{a_{ii}}(b_i-\sum _{j<i}{a}_{ij}{x}_j^{(k+1)}-\sum _{j>i}{a}_{ij}{x}_j^{(k)}),i=1,2,\dots ,n.$

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

$x_i^{(k+1)}=\frac{1}{a_{ii}}(b_i-\sum _{j=1,j\ne i}^n{a}_{ij}{x}_j^{(k)}),i=1,2,\dots ,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.

escolher uma aproximação inicial xo = (xo1, …, xon)
faça k = 1.
enquanto k <= N faça:
  para i := (1, …, n):
    σ = 0.
    para j := (1, …, i-1):
      σ = σ + aij * xj
    fim para.
    para j := (i+1, …, n):
      σ = σ + aij * xoj
    fim para.
    xi = (bi - σ) / aii
  fim para.
  se ||x-xo|| <= TOL então:
    retorna x.
  fim se
  xo = x.
  k = k+1.
fim enquanto.
imprime mensagem "Número máximo de iterações excedido."

Javascript

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

function norm(Matrix) {
    //Requer implementação ou inclusão de bibliotecas de terceiros
}
/*
* A = Matriz
* b = Resultado da matriz
*/
function gaussSeidel(A, b) {
	var X = new Array();
	var x = new Array();
	for (var k = 0; k < b.length; k++)
	{
		X[k] = 0; //Math.floor((Math.random() * 10000) + 1);
	}
	var E = 0.00001; //precisao, tolerância
	var m = 1000; //número máximo de iterações
	var ni = 0; //contador de iterações
	var continuar = true;

	while (continuar && ni < m) {
	    for (var i=0; i < b.length; i++) {
	        soma = 0;
	        for (var j = 0; j < i; j++) {
                	soma = soma + A[i][j] * x[j];
	        }
	        for (var j = i + 1; j < b.length; j++) {
                	soma = soma + A[i][j] * X[j];
	        }
		x[i] = (b[i] - soma) / A[i][i];
	    }
	    // se | x - xo | < Tolerância
	    if (Math.abs(math.norm(x) - math.norm(X)) < E) {
	        continuar = false;
	    } else {
	        X=x.slice(0);
	    }
	    ni = ni + 1;
	}
	return x;
}

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:

$\{\begin{array}{c}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{array}$

Em que bi é igual:

$b_i=\left(\begin{array}{c}-1\\ 2\\ 6\\ 2\\ -1\end{array}\right)$

Usando a equação: $x_i^{(k+1)}=\sum _{j=1,j\ne i}^n\frac{a_{ij}}{a_{ii}}+x_j^{(k)}+\frac{b_i}{a_{ii}},i=1,2,\dots ,n$

Obtemos o sistema :

$\{\begin{array}{c}{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{array}$

Utilizando a pressuposição inicial de vetor nulo:

$x^{(0)}=\left(\begin{array}{c}0\\ 0\\ 0\\ 0\\ 0\end{array}\right)$

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

$\{\begin{array}{c}{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{array}$

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;

$err{o}^{(k)}=\frac{\max |x_i^{(k)}-x_i^{(k-1)}|}{\underset{1\le i\le n}{\max }\left|x_i^{(k)}\right|}$

Diferenças:

$\{\begin{array}{c}|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{array}$

Erro da primeira iteração:

$M{R}^{(1)}=\frac{1.546875}{1.546875}=1$

Ligações externas

• Predefinição:Link
• Predefinição:Link da implementação do método em GNU Octave