Na primeira aula sobre o método de Gauss-Jacobi vimos exemplos em que o método gerava uma sequência convergente e outros em que a sequência era divergente. Só não vimos porque isso acontecia. Esse é o assunto desta aula.
1
2
3
4
Escrever a matriz como serviu para...
A. construir uma função de iteração.
B. relacionar o método de Gauss-Jacobi com a decomposição LU.
C. relacionar a iteração de Gauss-Jacobi com um método iterativo geral.
É correto afirmar que...
A. o cálculo da matriz é simples.
B. para aplicar o método de Gauss-Jacobi, precisa ser construída explicitamente.
C. se então
Podemos dizer que o método de Gauss-Jacobi produzirá uma sequência convergente...
A. se a matriz for não singular.
B. se a diagonal de for não nula.
C. se os elementos da digaonal de forem maiores que todos os elementos fora da diagonal.
D. se para cada linha de a soma dos valores absolutos dos elementos fora da diagonal for menor que o valor absoluto do elemento na diagonal.
Sobre a matriz de iteração podemos afirmar que...
A. sempre tem diagonal positiva.
B. sempre tem norma menor que 1.
C. se o método de Gauss-Jacobi será convergente.
D. mesmo que o método de Gauss-Jacobi ainda pode ser convergente.
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 como uma soma, da seguinte forma. Seja a matriz contendo apenas a diagonal de e ou seja, os uma matriz com os demais elementos de (no vídeo ). Com essa separação (ou spliting) de em duas parcelas, formalmente, o sistema linear fica Lembrando que no método de Gauss-Jacobi o vetor à esquerda do igual representa o novo iterando e o vetor à direita do igual representa o iterando atual, temos que o método na forma matricial é Por construção, a equação acima se verifica para solução do sistema linear. Desta forma, definido 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 Se então assume a forma Computando o produto, chegamos a
O teorema de convergência garante a convergência se onde a norma usada é livre. Se esta condição se cumprir em alguma norma, isso já será suficiente. Pela estrutura da matriz é fácil computar sua norma infinito. A norma infinito de uma matriz é a maior norma 1 das linhas da matriz. Portanto, se para todo , onde é a -ésima linha de De , vemos que a norma 1 (soma das componentes do vetor em módulo) de é Para que todas as linhas tenham norma menor que 1, basta então que Esta condição é conhecida como critério das linhas e uma matriz que a satisfaça é dita uma matriz diagonalmente dominante por linhas.
Observe as três matrizes de exemplo a seguir. 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. 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. 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,
Vale destacar que a construção da matriz 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 . 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 inicialnorm(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çõesnorm(A*x-b,inf) # resíduo
ans = 1.7410e-07
Neste exemplo, o resíduo, isto é, a norma de 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 para guardar 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.
3. Considere o sistema linear
É possível garantir a convergência do método de Jacobi para este sistema?
Aplique o método de Jacobi, a partir de Calcule o resíduo na norma infinito em cada iteração, ou seja O que você observou? Qual poderia ser uma explicação plausível para o comportamento observado?