Método de Gauss-Jacobi (II)

Na construção do método de Gauss-Jacobi, em cada linha do sistema linear mantivemos à esquerda o elemento da diagonal e passamos à direta do sinal de igual todo os demais. Isso que fizemos intuitivamente pode ser feito de maneira formal. Para tanto, escrevemos a matriz $A$ como uma soma, da seguinte forma. Seja $D$ a matriz contendo apenas a diagonal de $A,$ e $M = A-D,$ ou seja, os uma matriz com os demais elementos de $A$ (no vídeo $M=L+U$). Com essa separação (ou spliting) de $A$ em duas parcelas, formalmente, o sistema linear fica \begin{align*} Ax &= b\\ (D+M)x & = b\\ Dx & = -Mx +b \end{align*} Lembrando que no método de Gauss-Jacobi o vetor $x$ à esquerda do igual representa o novo iterando e o vetor $x$ à direita do igual representa o iterando atual, temos que o método na forma matricial é \begin{equation}\label{sl13-gj} Dx^{(k+1)} = -Mx^{(k)}+b. \end{equation} Por construção, a equação acima se verifica para $x^*,$ solução do sistema linear. Desta forma, definido $\phi(x) = -D^{-1}M+D^{-1}b$ temos a função de iteração do método, que automaticamente satisfaz a propriedade de ponto fixo. Isto é o que precisávamos para encaixar o método de Gauss-Jacobi no protótipo geral de métodos iterativos estacionários da aula anterior.

Para completar as hipóteses do teorema de convergência, precisamos analisar a norma da matriz $B^J \equiv -D^{-1}M.$ Se $A = (a_{ij}),$ então $B^J$ assume a forma $$B^J=-\begin{pmatrix} a_{11}^{-1} & & & & \\ & a_{22}^{-1} & & & \\ & & a_{33}^{-1} & & & \\ & & & \ddots& \\ & & & & a_{nn}^{-1} \end{pmatrix} \begin{pmatrix} 0& a_{12} & a_{13} & & a_{1n} \\ a_{21} & 0& a_{23} & \cdots & a_{2n} \\ a_{31} & a_{32} & 0 & & a_{3n} \\ & \vdots & & \ddots& \vdots \\ a_{n1} & a_{n2} & a_{n3} & \cdots & 0 \end{pmatrix}. $$ Computando o produto, chegamos a \begin{equation}\label{sl13-bj} B^J=- \begin{pmatrix} 0& a_{12}/a_{11} & a_{13}/a_{11} & & a_{1n}/a_{11} \\ a_{21}/a_{22} & 0& a_{23}/a_{22} & \cdots & a_{2n}/a_{22} \\ a_{31}/a_{33} & a_{32}/a_{33} & 0 & & a_{3n}/a_{33} \\ & \vdots & & \ddots& \vdots \\ a_{n1}/a_{nn} & a_{n2}/a_{nn} & a_{n3}/a_{nn} & \cdots & 0 \end{pmatrix}. \end{equation}

O teorema de convergência garante a convergência se $\|B^J\|\lt 1,$ onde a norma usada é livre. Se esta condição se cumprir em alguma norma, isso já será suficiente. Pela estrutura da matriz $B^J,$ é fácil computar sua norma infinito. A norma infinito de uma matriz é a maior norma 1 das linhas da matriz. Portanto, $\|B^J\|_\infty \lt 1$ se $\|b^i\|_1 \lt1,$ para todo $i$, onde $b^i$ é a $i$-ésima linha de $B^J.$ De \eqref{sl13-bj}, vemos que a norma 1 (soma das componentes do vetor em módulo) de $b^i$ é $$ \|b^i\|_1 = {1\over |a_{ii}|} \left(|a_{11}| +\cdots + |a_{i,i-1}| + |a_{i,i+1}| + \cdots |a_{nn}|\right). $$ Para que todas as linhas tenham norma menor que 1, basta então que $$ \sum_{\stackrel{k=1}{k\ne i}}^n |a_{ik}| \lt |a_{ii}|, \quad i=1,2,\ldots,n. $$ Esta condição é conhecida como critério das linhas e uma matriz $A$ que a satisfaça é dita uma matriz diagonalmente dominante por linhas.

Observe as três matrizes de exemplo a seguir. $$ \left( \begin{array}{rrr} 4 & 2 & -1 \\ 0 & -3 & 1 \\ -2 & 2 & -6 \end{array} \right) $$ Esta matriz é diagonalmente dominante por linhas. Logo, caso o método de Gauss-Jacobi seja aplicado a um sistema linear que tenha esta matriz de coeficientes, seguramente conseguiremos uma sequência de iterandos convergente à solução do sistema linear. Já o mesmo não pode ser dito da próxima matriz. $$ \left( \begin{array}{rrr} 5 & 2 & 2 \\ 6 & -3 & 1 \\ -1 & 2 & 7 \end{array} \right) $$ Como o critério das linhas falha por conta da segunda linha, não há como garantir a convergência do método de Gauss-Seidel. Entretanto, ela até pode acontecer, se houver alguma outra norma para a qual a condição geral do teorema se cumpra. Porém isso é difícil de ser descoberto. Observe esta última matriz. $$ \left( \begin{array}{rrr} 6 & -3 & 1 \\ 2 & -3 & 7 \\ -1 & 5 & 1 \end{array} \right) $$ Para esta, o critério das linhas também não é satisfeito. Porém, diferentemente do que aconteceu no exemplo anterior, caso a segunda linha seja permutada com a terceira, o critério é cumprido. Como trocar linhas não altera a solução do sistema linear, essa é uma opção que podemos usar para tentar garantir a convergência do método de Gauss-Jacobi. Mas lembre-se! Se permutar linhas na matriz, deve permutar igualmente os elementos do vetor independente do sistema linear, $b.$

Vale destacar que a construção da matriz $B^J$ não é feita na prática, sendo apenas um recurso teórico para analisar a convergência do método. Na prática, o método é usado como em \eqref{sl13-gj}. Vejamos um exemplo de uso com o Octave.

> A = [5 -2 1; 1 -4 -2; 2 2 -7];
> b = [6; 3; 8];
> D = diag(diag(A))          # Matriz com a diagonal de A
D =

Diagonal Matrix

   5   0   0
   0  -4   0
   0   0  -7

> x = [0; 0; 0];             # aproximação inicial
> norm(A*x-b,inf)            # resíduo na aproximação inicial
ans =  8
> x = D\(-A*x+D*x+b)         # passo de Gauss-Jacobi: Dx = -Mx + b
x =

   1.20000
  -0.75000
  -1.14286

> norm(A*x-b,inf)            # resíduo depois da primeira iteração
ans =  3.4857
> x = D\(-A*x+D*x+b);
> norm(A*x-b,inf)            # resíduo depois da segunda iteração
ans =  1.6143
> for p=1:20; x = D\(-A*x+D*x+b); end    # mais 20 iterações
> norm(A*x-b,inf)            # resíduo
ans =  0.00000015015

Neste exemplo, o resíduo, isto é, a norma de $Ax^{(k)}-b,$ foi computado a cada iteração para observar se as interações estão progredindo da direção de obter um vetor que satisfaça o sistema linear. Outro comentário é que poderíamos ter definido uma matriz $M$ para guardar $A-D,$ poderem isso significaria duplicar o espaço de memória necessário. Claro que nesse exemplo não seria problema algum, mas em essência uma vantagem dos métodos iterativos é não precisar de memória adicional.

Por fim, para tornar o método em um algoritmo é importante definir um critério de parada, ao invés de rodá-lo uma quantidade determinada de passos. Esse critério pode ser baseado no resíduo ou, como é mais comum e barato, na norma do passo (diferença entre dois iterandos consecutivos).

Na próxima aula, de forma análoga ao que fizemos aqui, analisaremos como o método de Gauss-Seidel.

Referências

C.T. Kelley. Iterative Methods for Linear and Nonlinear Equations. SIAM. 1995.

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, explique se é possível (e como) aplicar o método Jacobi para aproximar a solução do sistema de maneira a ter garantia de 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} 2 & 5 & -2 \\\ 6 & 3 & 0 \\\ 3 & -2 & 6 \end{array}\right]x = \begin{bmatrix}1 \\\ 2 \\\ 1\end{bmatrix}$
3. $\left[\begin{array}{rrr} 2 & 5 & 8 \\\ 6 & 3 & -1 \\\ 3 & -2 & 6 \end{array}\right]x = \begin{bmatrix}7 \\\ 3 \\\ 3\end{bmatrix}$
4. $\left[\begin{array}{rrr} 6 & -3 & 2 \\\ 4 & 7 & 4 \\\ 1 & 2 & -8 \end{array}\right]x = \begin{bmatrix}4 \\\ 4 \\\ 6\end{bmatrix}$

3. Considere o sistema linear $ \begin{bmatrix} 4&3&2\\1&5&0\\1&1&3 \end{bmatrix}x = \begin{bmatrix}4\\9\\4 \end{bmatrix}.$

1. É possível garantir a convergência do método de Jacobi para este sistema?
2. Aplique o método de Jacobi, a partir de $x^{(0)} = (1,1,1)^T.$ Calcule o resíduo na norma infinito em cada iteração, ou seja $\|Ax^{(k)}-b\|_\infty.$ O que você observou? Qual poderia ser uma explicação plausível para o comportamento observado?