Ajude a manter o site livre, gratuito e sem propagandas. Colabore!
O GMRES (do inglês, Generalized Minimal Residual Method2525endnote: 25Desenvolvido por Yousef Saad e H. Schultz, 1986. Fonte: Wikipedia.) é um método de subespaço de Krylov2626endnote: 26Alexei Nikolajewitsch Krylov, 1863 - 1945, engenheiro e matemático russo. Fonte: Wikipédia. e é considerado uma das mais eficientes técnicas para a resolução de sistemas lineares gerais e de grande porte (esparsos).
A ideia básica é resolver o sistema linear
(1.179) |
por um método de projeção (lembremos da Seção 1.5). Isto é, buscamos uma solução aproximada no subespaço afim de dimensão , impondo-se a condição de Petrov2727endnote: 27Georgi Iwanowitsch Petrov, 1912 - 1987, engenheiro soviético. Fonte: Wikipedia.-Galerkin2828endnote: 28Boris Galerkin, 1871 - 1945, engenheiro e matemático soviético. Fonte: Wikipédia.
(1.180) |
onde também é um subespaço de dimensão . Quando é um subespaço de Krylov, i.e.
(1.181) |
temos um método de subespaço de Krylov, onde é o resíduo inicial, i.e.
(1.182) |
sendo uma aproximação inicial para a solução do sistema. Notamos que com isso, temos que a aproximação calculada é tal que
(1.183) |
onde é um dado polinômio de grau . No caso particular de , temos
(1.184) |
Diferentes versões deste método são obtidas pelas escolhas do subespaço e formas de precondicionamento do sistema.
O GMRES é o método de subespaço de Krylov em que se assume e
(1.185) |
onde é o vetor normalizado do resíduo inicial para uma dada aproximação inicial da solução do sistema .
Vamos derivar o método observando que qualquer vetor em pode ser escrito como segue
(1.186) |
onde, é a matriz cujas colunas formam uma base ortonormal de e . Para computar esta base, podemos usar o método de Gram2929endnote: 29Jørgen Pedersen Gram, 1850 - 1916, matemático dinamarquês. Fonte: Wikipédia.-Schmidt3030endnote: 30Erhard Schmidt, 1876 - 1959, matemático alemão. Fonte: Wikipédia. Arnoldi3131endnote: 31Walter Edwin Arnoldi, 1917 - 1995, engenheiro americano estadunidense. Fonte: Wikipédia.-modificado [6, Subseção 6.3]:
Dado de norma 1
Para :
Para :
Se , então pare.
Seja, então, a matriz de Hessenberg3232endnote: 32Karl Adolf Hessenberg, 1904 - 1959, engenheiro e matemático alemão. Fonte: Wikipédia. cujas entradas não nulas são computadas pelo algoritmo acima (Passos 2(a)i-ii). Definimos
(1.187) | |||
(1.188) | |||
(1.189) | |||
(1.190) | |||
(1.191) |
onde é o vetor canônico e . Uma vez que é uma matriz ortonormal, temos
(1.192) |
A aproximação GMRES é então obtida como
(1.193) |
onde
(1.194) |
Observamos que este último é um pequeno problema de minimização, sendo que requer a solução de um sistema de mínimos quadrados, sendo normalmente pequeno.
Consideremos o seguinte problema de difusão-advecção 2D
(1.195) | |||
(1.196) |
onde é o coeficiente de difusão, é o campo de advecção e a fonte é dada por
(1.197) |
Consulte o Exemplo 1.5.1 para mais detalhes.
Assumimos uma malha espacial uniforme de , com tamanho de malha . Denotamos , onde e , para . Aplicando um espuema upwind para a advecção e diferenças finitas centrais para a difusão, obtemos o seguinte esquema de diferenças finitas
(1.198) | |||
(1.199) |
para , onde . As condições de contorno são dadas por , para . Por fim, consideramos a enumeração dos nodos da malha para obtermos o sistema linear
(1.200) |
onde é uma matriz esparsa de ordem , é o vetor das incógnitas e é o vetor da fonte.
Observando que é apenas positiva definida (i.e. é simétrica positiva definida), aplicamos a iteração do mínimo resíduo para resolver o sistema linear. A seguinte tabela mostra o número de iterações necessárias para a convergência do método, para diferentes tamanhos de malha. O critério de parada é dado por e e número máximo de iterações . Verifique!
GMRES | ||
---|---|---|
11 | 24 | |
21 | 46 | |
41 | 50 |
Pode-se mostrar que o GMRES converge em ao menos passos.
No algoritmo acima, o método Arnoldi-modificado de Gram-Schmidt é utilizado. Uma versão numericamente mais eficiente é obtida quando a transformação de Householder3333endnote: 33Alston Scott Householder, 1904 - 1993, matemático americano estadunidense. Fonte: Wikipédia. é utilizada. Consulte mais em [6, Subsetion 6.5.2].
O GMRES com reinicialização é uma variação do método para sistemas que requerem uma aproximação GMRES com grande. Nestes casos, o método original pode demandar um custo muito alto de memória computacional. A alternativa consiste em assumir pequeno e, caso não suficiente, recalcular a aproximação GMRES com . Este algoritmo pode ser descrito como segue.
Aplique o método GMRES para resolver o sistema linear , com
(1.201) |
e . Usando uma aproximação inicial , faça uma análise geométrica das iterações.
Dica: faça um gráfico de contorno da norma e mostre as iterações do método sobre o gráfico.
Aplique o método GMRES para resolver o sistema linear , com
(1.202) |
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 da norma e mostre as iterações do método sobre o gráfico.
Aplique o método GMRES para resolver o sistema linear , com
(1.203) |
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 da norma e mostre as iterações do método sobre o gráfico.
Considere o problema de difusão-advecção 2D do Exemplo 1.6.1, discretizado com o esquema upwind. Aplique a iteração da descida mais íngrime do resíduo para resolver o sistema linear resultante para os seguintes coeficientes de advecção:
;
;
.
Analise a convergência do método para diferentes tamanho de malha.
Dica: lembre-se que o esquema upwind deve ser adaptado para cada caso.
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 GMRES (do inglês, Generalized Minimal Residual Method2525endnote: 25Desenvolvido por Yousef Saad e H. Schultz, 1986. Fonte: Wikipedia.) é um método de subespaço de Krylov2626endnote: 26Alexei Nikolajewitsch Krylov, 1863 - 1945, engenheiro e matemático russo. Fonte: Wikipédia. e é considerado uma das mais eficientes técnicas para a resolução de sistemas lineares gerais e de grande porte (esparsos).
A ideia básica é resolver o sistema linear
(1.179) |
por um método de projeção (lembremos da Seção 1.5). Isto é, buscamos uma solução aproximada no subespaço afim de dimensão , impondo-se a condição de Petrov2727endnote: 27Georgi Iwanowitsch Petrov, 1912 - 1987, engenheiro soviético. Fonte: Wikipedia.-Galerkin2828endnote: 28Boris Galerkin, 1871 - 1945, engenheiro e matemático soviético. Fonte: Wikipédia.
(1.180) |
onde também é um subespaço de dimensão . Quando é um subespaço de Krylov, i.e.
(1.181) |
temos um método de subespaço de Krylov, onde é o resíduo inicial, i.e.
(1.182) |
sendo uma aproximação inicial para a solução do sistema. Notamos que com isso, temos que a aproximação calculada é tal que
(1.183) |
onde é um dado polinômio de grau . No caso particular de , temos
(1.184) |
Diferentes versões deste método são obtidas pelas escolhas do subespaço e formas de precondicionamento do sistema.
O GMRES é o método de subespaço de Krylov em que se assume e
(1.185) |
onde é o vetor normalizado do resíduo inicial para uma dada aproximação inicial da solução do sistema .
Vamos derivar o método observando que qualquer vetor em pode ser escrito como segue
(1.186) |
onde, é a matriz cujas colunas formam uma base ortonormal de e . Para computar esta base, podemos usar o método de Gram2929endnote: 29Jørgen Pedersen Gram, 1850 - 1916, matemático dinamarquês. Fonte: Wikipédia.-Schmidt3030endnote: 30Erhard Schmidt, 1876 - 1959, matemático alemão. Fonte: Wikipédia. Arnoldi3131endnote: 31Walter Edwin Arnoldi, 1917 - 1995, engenheiro americano estadunidense. Fonte: Wikipédia.-modificado [6, Subseção 6.3]:
Dado de norma 1
Para :
Para :
Se , então pare.
Seja, então, a matriz de Hessenberg3232endnote: 32Karl Adolf Hessenberg, 1904 - 1959, engenheiro e matemático alemão. Fonte: Wikipédia. cujas entradas não nulas são computadas pelo algoritmo acima (Passos 2(a)i-ii). Definimos
(1.187) | |||
(1.188) | |||
(1.189) | |||
(1.190) | |||
(1.191) |
onde é o vetor canônico e . Uma vez que é uma matriz ortonormal, temos
(1.192) |
A aproximação GMRES é então obtida como
(1.193) |
onde
(1.194) |
Observamos que este último é um pequeno problema de minimização, sendo que requer a solução de um sistema de mínimos quadrados, sendo normalmente pequeno.
Consideremos o seguinte problema de difusão-advecção 2D
(1.195) | |||
(1.196) |
onde é o coeficiente de difusão, é o campo de advecção e a fonte é dada por
(1.197) |
Consulte o Exemplo 1.5.1 para mais detalhes.
Assumimos uma malha espacial uniforme de , com tamanho de malha . Denotamos , onde e , para . Aplicando um espuema upwind para a advecção e diferenças finitas centrais para a difusão, obtemos o seguinte esquema de diferenças finitas
(1.198) | |||
(1.199) |
para , onde . As condições de contorno são dadas por , para . Por fim, consideramos a enumeração dos nodos da malha para obtermos o sistema linear
(1.200) |
onde é uma matriz esparsa de ordem , é o vetor das incógnitas e é o vetor da fonte.
Observando que é apenas positiva definida (i.e. é simétrica positiva definida), aplicamos a iteração do mínimo resíduo para resolver o sistema linear. A seguinte tabela mostra o número de iterações necessárias para a convergência do método, para diferentes tamanhos de malha. O critério de parada é dado por e e número máximo de iterações . Verifique!
GMRES | ||
---|---|---|
11 | 24 | |
21 | 46 | |
41 | 50 |
Pode-se mostrar que o GMRES converge em ao menos passos.
No algoritmo acima, o método Arnoldi-modificado de Gram-Schmidt é utilizado. Uma versão numericamente mais eficiente é obtida quando a transformação de Householder3333endnote: 33Alston Scott Householder, 1904 - 1993, matemático americano estadunidense. Fonte: Wikipédia. é utilizada. Consulte mais em [6, Subsetion 6.5.2].
O GMRES com reinicialização é uma variação do método para sistemas que requerem uma aproximação GMRES com grande. Nestes casos, o método original pode demandar um custo muito alto de memória computacional. A alternativa consiste em assumir pequeno e, caso não suficiente, recalcular a aproximação GMRES com . Este algoritmo pode ser descrito como segue.
Aplique o método GMRES para resolver o sistema linear , com
(1.201) |
e . Usando uma aproximação inicial , faça uma análise geométrica das iterações.
Dica: faça um gráfico de contorno da norma e mostre as iterações do método sobre o gráfico.
Aplique o método GMRES para resolver o sistema linear , com
(1.202) |
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 da norma e mostre as iterações do método sobre o gráfico.
Aplique o método GMRES para resolver o sistema linear , com
(1.203) |
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 da norma e mostre as iterações do método sobre o gráfico.
Considere o problema de difusão-advecção 2D do Exemplo 1.6.1, discretizado com o esquema upwind. Aplique a iteração da descida mais íngrime do resíduo para resolver o sistema linear resultante para os seguintes coeficientes de advecção:
;
;
.
Analise a convergência do método para diferentes tamanho de malha.
Dica: lembre-se que o esquema upwind deve ser adaptado para cada caso.
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.