Método de Gauss-Jacobi

Métodos iterativos são métodos que visam se aproximar da solução de forma gradativa. Eles partem de uma aproximação inicial e passo a passo a alteram, na expectativa de convergir à solução do problema.

No contexto da resolução de sistemas lineares, uma aproximação inicial é um vetor $x^0 = (x_1^0, x_2^0,\ldots,x_n^0)^T\in\mathbb{R}^n.$ Um método iterativo deve construir uma sequência de aproximações $x^1, x^2,\ldots,x^k,\ldots,$ onde cada $x^k\in\mathbb{R}^n.$ Claro que a intenção é que $x^k \rightarrow x,$ onde $x$ é a solução do sistema linear.

No vídeo criamos uma regra para definir $x^{(k+1)}$ a partir de $x^k.$ Em palavras, a coordenada $i$ de $x^k$ foi construída de forma a satisfazer a $i$-ésima equação do sistema linear, quando todas as demais coordenadas são impostas a partir do vetor $x^k.$ Ou seja, $x_i^{(k+1)}$ deve satisfazer $$ a_{i1}x_1^k + \cdots + a_{i(i-1)}x_{i-1}^k + 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,\ldots,x_{i-1}^k,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, para determinar $x_i^{(k+1)},$ basta deslocar-se a partir de $x^k$ em direção paralela ao $i$-ésimo eixo coordenado até atingir a superfície definida pela $i$-ésima equação. Logo, a ordem das equações do sistema linear influencia o processo. Este método é conhecido como método de Jacobi ou Gauss-Jacobi .

Vejamos em um exemplo de aplicação. 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-Jacobi 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+2x_3^k)/5\\ x_3^{(k+1)} = (9+3x_2^k)/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 = 15/4\\ x_2^1 = (10-x_1^0+2x_3^0)/5 = 15/5\\ x_3^1 = (9+3x_2^0)/6 = 18/6 \end{array}\right. $$ Portanto, $x^1=(3.75, 3, 3).$ Será que você consegue descobrir se $x^1$ é uma aproximação melhor ou pior para solução, quando comparado a $x^0$?

Veja que o custo de uma iteração do método de Gauss-Jacobi é tão somente o custo de avaliar as equações do sistema linear, portanto da ordem de $n^2$ operações. Por outro lado o processo de escalonamento ou decomposição LU consome ${2\over 3}n^3$ operações. Além disso, ao final de apenas um passo do método já temos uma nova aproximação. Portanto, se tivermos limitação de recursos, podemos realizar apenas o número possível de iterações deste método e sair com uma nova aproximação ao final. Em métodos diretos, se nem todas as operações forem feitas, não obtemos nem mesmo uma aproximação intermediária.

Como não há manipulação dos coeficientes do sistema linear, caso a matriz seja esparsa, essa estrutura não se perde com a aplicação do método de Gauss-Jacobi. Isto significa que não é necessário memória adicional para armazenar outros coeficientes que poderiam surgir se a matriz fosse manipulada (como acontece com a decomposição LU).

Entretanto, não temos apenas vantagens. Vimos pelo exemplo do vídeo que nem sempre o método converge e, mesmo quando converge, pode ser bem lento.

Resta-nos estudar quais critérios garantem a convergência deste método. Antes disso ainda, na próxima aula construiremos um segundo método iterativo também simples, porém mais rápido que o método de Gauss-Jacobi.

Referência

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

1. Escreva um algoritmo para o método de Jacobi e conte o número de operações realizadas em cada iteração do método. Implemente seu algoritmo em Octave.

2. Para cada sistema linear abaixo, aplique o método Jacobi 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.

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}$