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 [6]) 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 [1, 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.
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 [6]) 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 [1, 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.