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)^T$ 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, temos $$ \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)^T.$ Quando aplicamos a este mesmo exemplo o método de Gauss-Jacobi, visto na aula passada, obtemos $(3.75,3,3)^T.$ 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 produzem sequências convergentes e o que determina a velocidade deles. Este é 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}$