Método de Gauss-Seidel

A ideia do método de Gauss-Seidel é usar melhores aproximações assim que disponíveis. Tão logo uma coordenadas do próximo iterando já esteja disponível, ela já é prontamente utilizada, ainda na mesma iteração do método de Gauss-Seidel.

De fato, o método de Gauss-Seidel é muito parecido com o método de Gauss-Jacobi, com a exceção de que $x_i^{(k+1)}$ deve satisfazer $$ a_{i1}x_1^{(k+1)} + \cdots + a_{i(i-1)}x_{i-1}^{(k+1)} + a_{ii}x_i^{(k+1)} + a_{i(i+1)}x_{i+1}^k + \cdots + a_{in}x_n^k = b_i.$$

Definindo $x_i^{(k+1)}$ desta forma, o ponto de coordenadas $(x_1^{(k+1)},\ldots,x_{i-1}^{(k+1)}, x_i^{(k+1)},x_{i+1}^k,\ldots,x_n^k)$ pertence à superfície definida pela $i$-ésima equação do sistema linear. Geometricamente, uma iteração do método de Gauss-Seidel consiste em partir de $x^k,$ deslocar-se paralelo ao eixo cartesiano da primeira coordenada até atingir a superfície definida pela primeira equação; depois a partir desse ponto de intersecção, deslocar-se paralelo ao eixo cartesiano da segunda coordenada até atingir a superfície definida pela segunda equação, e assim sucessivamente até a intersecção com a superfície definida pela última equação do sistema linear. Assim como no método de Gauss-Jacobi, também aqui a ordem das equações do sistema linear influencia o processo.

Vejamos em um exemplo como aplicar o método de Gauss-Seidel. Considere o sistema linear $$ \left\{ \begin{array}{rrrcr} 4 x_1 & - 2x_2 &- x_3 & = & 8\\ x_1 & + 5x_2 &-2x_3 & = & 10\\ & - 3x_2 &+6x_3&=& 9 \end{array}\right. $$ A iteração de Gauss-Seidel fica $$ \left\{ \begin{array}{l} x_1^{(k+1)} = (8+2x_2^k+x_3^k)/4\\ x_2^{(k+1)} = (10-x_1^{(k+1)}+2x_3^k)/5\\ x_3^{(k+1)} = (9+3x_2^{(k+1)})/6 \end{array}\right. $$ Para iniciar o método é preciso fornecer uma aproximação inicial. Digamos que $x^0 = (1,2,3)^T.$ Então, para $k=0$ na fórmula de iteração acima, teríamos que $$ \left\{ \begin{array}{l} x_1^1 = (8+2x_2^0+x_3^0)/4 = 3.75\\ x_2^1 = (10-x_1^1+2x_3^0)/5 = 2.45\\ x_3^1 = (9+3x_2^1)/6 = 2.725 \end{array}\right. $$ Portanto, $x^1=(3.75, 2.45, 2.725).$ Quando aplicamos a este mesmo exemplo o método de Gauss-Jacobi, na aula passada, obtivemos $(3.75,3,3).$ Será que você consegue descobrir se $x^1,$ obtido pelo método de Gauss-Seidel foi melhor que o obtido pelo método de Gauss-Jacobi?

Veja que o custo de uma iteração do método de Gauss-Seidel é rigorosamente o mesmo que o custo de uma iteração do método de Gauss-Jacobi, uma vez que são feitas as mesmas contas, apenas com valores diferentes para as coordenadas dos pontos intermediários.

O método de Gauss-Seidel sofre dos mesmos problemas que o método de Gauss-Jacobi. Ele também pode não convergir, além de poder ser lento.

Com esses dois exemplos de métodos iterativos para sistemas lineares está na hora de tentar entender quando esses métodos convergem e o que determina a velocidade deles. Esse será o assunto da próxima aula.

Referência

David S. Watkins. Fundamentals of Matrix Computations. John Wiley & Sons, 2ª ed., 2002.

1. Escreva um algoritmo para o método de Gauss-Seidel. Compare o custo computacional deste algoritmo com o custo do algoritmo para o método de Gauss-Jacobi.

2. Para cada sistema linear abaixo, aplique o método de Gauss-Seidel e descubra se o método está convergindo ou não. Caso o método não esteja convergindo, experimente trocar a ordem das equações para verificar se isso afeta a convergência. Compare com os resultados do exercício análogo da aula anterior e veja se de fato o método de Gauss-Seidel foi mais rápido.

1. $\left[\begin{array}{rrr} 4 & 1 & -2 \\ 2 & 3 & 0 \\ 2 & -2 & 6 \end{array}\right]x = \begin{bmatrix}3 \\ 5 \\ 1\end{bmatrix}$
2. $\left[\begin{array}{rrr} 5 & \hphantom{-}1 & -1 \\ 2 & 6 & 0 \\ 3 & 1 & 8 \end{array}\right]x = \begin{bmatrix}1.0 \\ 1.5 \\ 2.0\end{bmatrix}$
3. $\left[\begin{array}{rrr} 2 & 5 & -2 \\ 6 & 3 & 0 \\ 3 & -2 & 6 \end{array}\right]x = \begin{bmatrix}1 \\ 2 \\ 1\end{bmatrix}$