Ajude a manter o site livre, gratuito e sem propagandas. Colabore!
O método do gradiente conjugado é um dos métodos mais eficientes para a resolução de sistemas lineares
| (1.119) |
com matriz simétrica positiva definida e . Foi desenvolvido por Magnus Hestenes2020endnote: 20Magnus R. Hestenes, 1906 - 1991, matemático americano estadunidense. Fonte: Wikipedia. e Eduard Stiefel2121endnote: 21Eduard Stiefel, 1909 - 1978, matemático suíço. Fonte: Wikipédia. em 1952.
A ideia é encontrar a solução do sistema linear como o ponto de mínimo da função quadrática
| (1.120) |
onde denota o produto interno usual em .
Note que é estritamente convexa, pois é simétrica positiva definida. Assim, possui um único ponto de mínimo global, que é a solução do sistema linear . De fato, supondo solução do sistema, temos
| (1.121) | |||
| (1.122) |
Logo, como é simétrica positiva definida, temos que é mínimo se, e somente se, , i.e. .
Ainda, observamos que o gradiente de é dado por
| (1.123) |
i.e. é igual ao vetor oposto do resíduo do sistema linear
| (1.124) |
A solução é o único vetor tal que . Mais ainda, lembrando que o gradiente aponta na direção de maior crescimento da função, temos que o resíduo aponta na direção de maior decrescimento de . Isto nos motiva a considerar o método do gradiente (ou método da descida mais íngrime), que consiste nas iterações
| (1.125) |
onde é o resíduo na iteração e é um tamanho do passo escolhido, com uma aproximação inicial da solução do sistema. Em outras palavras, o método do gradiente constrói uma sequência de aproximações da solução do sistema, movendo-se na direção do resíduo do sistema linear.
Podemos escolher o tamanho do passo de modo a minimizar ao longo da direção do resíduo . Isto é, escolhemos como
| (1.126) |
o que é conhecido como busca linear exata. Fazendo as contas, obtemos
| (1.127) |
Com tudo isso, temos a iteração do método do gradiente
| (1.128) | |||
| (1.129) |
Observamos que o cálculo de requer o produto e que o resíduo requer o produto . Essas multiplicações matriz-vetor são os passos computacionalmente mais custosos da iteração. Assim, para economizar uma multiplicação por iteração, podemos atualizar o resíduo como
| (1.130) |
evitando o cálculo de .
O método do gradiente conjugado é uma melhoria do método do gradiente, que constrói as aproximações na forma
| (1.131) |
onde é uma direção de busca conjugada as direções anteriores . Isto é, as direções de busca satisfazem
| (1.132) |
para todo . A primeira direção de busca é escolhida como o resíduo inicial, i.e. . As demais direções são construídas como combinações lineares do resíduo atual e da direção de busca anterior, i.e.
| (1.133) |
onde é escolhido de modo a garantir a conjugação das direções. Pode-se mostrar (consulte [9]) que a escolha
| (1.134) |
garante a conjugação das direções de busca. O tamanho do passo é escolhido como no método do gradiente, i.e.
| (1.135) |
Em resumo, a iteração do método do gradiente conjugado é dada por
| (1.136) | |||
| (1.137) | |||
| (1.138) | |||
| (1.139) | |||
| (1.140) |
Considere o problema de Poisson2222endnote: 22Siméon Denis Poisson, 1781 - 1840, matemático francês. Fonte: Wikipédia:Siméon Denis Poisson. 2D
| (1.141) | |||
| (1.142) |
onde a fonte é dada por
| (1.143) |
Discretizando o problema com diferenças finitas centrais em uma malha uniforme de pontos, obtemos um sistema linear , onde é uma matriz esparsa simétrica positiva definida de ordem e é o vetor que contém os valores aproximados de nos nodos da malha, .
A seguinte tabela mostra o número de iterações necessárias para a convergência do método do gradiente (MG) e do método do gradiente conjugado (MGC), para diferentes tamanhos de malha. O critério de parada é dado por e .
| MG | MGC | |
|---|---|---|
| 11 | 203 | 11 |
| 21 | 808 | 48 |
| 41 | 3190 | 97 |
| 81 | 12702 | 196 |
Para matriz simétrica positiva definida, o método do gradiente conjugado converge para a solução do sistema linear em no máximo iterações (desconsiderando-se erros de arredondamentos), onde é a ordem da matriz [3, Teorema 7.32].
Aplique o método do gradiente para resolver o sistema linear , com
| (1.144) |
e . Usando uma aproximação inicial , faça uma análise geométrica das iterações do método.
Dica: faça um gráfico de contorno do funcional e mostre as iterações do método do gradiente sobre o gráfico.
Aplique o método do gradiente conjugado para resolver o sistema linear , com
| (1.145) |
e . Usando uma aproximação inicial , faça uma análise geométrica das iterações do método.
Dica: faça um gráfico de contorno do funcional e mostre as iterações do método do gradiente sobre o gráfico.
Para matriz simétrica positiva definida, mostre que, se
| (1.146) |
então,
| (1.147) |
Considere a seguinte equação diferencial parcial de difusão-advecção com condições de contorno de Dirichlet homogêneas
| (1.148) |
Aplique o método de diferenças finitas com fórmulas de diferenças centrais para obter um problema discreto que aproxime a solução. Então, aplique o método do gradiente conjugado para resolver o sistema linear. Considere e . Compare os resultados.
Use um esquema upwind para a discretização do problema de difusão-advecção do Exemplo 1.4.4. I.e., use a fórmula de diferenças central para a discretização do termo de difusão e a fórmula de diferenças progressiva para o termo de advecção. Verifique que o sistema linear resultante não é simétrico. Entretanto, como é não-singular, é simétrica positiva definida. Assim, aplique os métodos do gradiente e do gradiente conjugado para resolver o sistema normal
| (1.149) |
Analise a convergência dos métodos para diferentes tamanho de malha. Por fim, compare os resultados com os obtidos no Exemplo 1.4.4.
Aproveito para agradecer a todas/os que de forma assídua ou esporádica contribuem enviando correções, sugestões e críticas!

Este texto é disponibilizado nos termos da Licença Creative Commons Atribuição-CompartilhaIgual 4.0 Internacional. Ícones e elementos gráficos podem estar sujeitos a condições adicionais.