Ajude a manter o site livre, gratuito e sem propagandas. Colabore!
Começamos observando que se é uma matriz positiva definida4040endnote: 40 é simétrica e para todo ., temos que é solução de
(3.280) |
se, e somente se, é solução do seguinte problema de minimização
(3.281) |
De fato, sejam a solução de (3.280) e a solução de (3.281), então
(3.282) | ||||
(3.283) | ||||
(3.284) |
O segundo termo é independente de e, como é positiva definida, temos
(3.285) |
Logo, o mínimo de ocorre quando , i.e. .
A iteração do Método do Gradiente tem a forma
(3.286) | ||||
para , onde é o tamanho do passo e é o vetor direção de busca.
Para escolhermos a direção , tomamos a fórmula de Taylor de em torno da aproximação
(3.287) |
onde denota o gradiente de , i.e.
(3.288) | ||||
(3.289) |
De , segue que se
(3.290) |
então , para suficientemente pequeno. Em particular, podemos escolher
(3.291) |
se .
Do exposto acima, temos a iteração do Método do Gradiente
(3.292) | ||||
com , onde é o resíduo
(3.293) |
Consideramos o sistema com
(3.294) | ||||
(3.295) |
Na Tabela 3.3 temos os resultados do emprego do método do gradiente com e com passo constante .
k | ||
---|---|---|
0 | ||
1 | ||
2 | ||
3 | ||
4 | ||
5 | ||
6 | ||
7 | ||
8 | ||
9 | ||
10 |
Para a escolha do passo, podemos usar o Método da Pesquisa Linear. A ideia é escolher o passo tal que
(3.296) |
Observando que é função apenas de , temos que seu mínimo ocorre em seu ponto crítico, i.e.
(3.297) | |||
(3.298) | |||
(3.299) | |||
(3.300) | |||
(3.301) |
donde
(3.302) |
Consideramos o sistema com
(3.303) | ||||
(3.304) |
Na Tabela 3.4 temos os resultados do emprego do método do gradiente com e com passo escolhido conforme (3.302).
k | |||
---|---|---|---|
Considere o sistema linear com
(3.305) | ||||
(3.306) |
Por tentativa e erro, encontre um valor para tal que o Método do Gradiente converge para solução do sistema em menos de iterações. Use
(3.307) |
como aproximação inicial e assuma o critério de parada
(3.308) |
onde é o resíduo do sistema e .
,
Considere o sistema linear com
(3.309) | ||||
(3.310) |
Por tentativa e erro, encontre um valor para tal que o Método do Gradiente converge para solução do sistema em menos de iterações. Use
(3.311) |
como aproximação inicial e assuma o critério de parada
(3.312) |
onde é o resíduo do sistema e .
,
Considere o sistema linear dado no Exercício 3.4.1. Utilizando a mesma aproximação inicial e tolerância, aplique o Método do Gradiente com Pesquisa Linear. Quantas iterações são necessárias até a convergência e qual o valor médio de utilizado durante as iterações?
,
Considere o sistema linear dado no Exercício 3.4.2. Utilizando a mesma aproximação inicial e tolerância, aplique o Método do Gradiente com Pesquisa Linear. Quantas iterações são necessárias até a convergência e qual o valor médio de utilizado durante as iterações?
,
Considere o problema de Laplace
(3.313) | ||||
(3.314) |
A discretização pelo Método das Diferenças Finitas em uma malha uniforme , , , leva ao seguinte sistema linear
(3.315) | |||
(3.316) | |||
(3.317) |
onde . Com , aplique o Método do Gradiente com Pesquisa Linear para computar a solução deste sistema quando . Quantas iterações são necessárias para obter-se a convergência do método com critério de convergência
(3.318) |
onde, é o resíduo e .
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!
Começamos observando que se é uma matriz positiva definida4040endnote: 40 é simétrica e para todo ., temos que é solução de
(3.280) |
se, e somente se, é solução do seguinte problema de minimização
(3.281) |
De fato, sejam a solução de (3.280) e a solução de (3.281), então
(3.282) | ||||
(3.283) | ||||
(3.284) |
O segundo termo é independente de e, como é positiva definida, temos
(3.285) |
Logo, o mínimo de ocorre quando , i.e. .
A iteração do Método do Gradiente tem a forma
(3.286) | ||||
para , onde é o tamanho do passo e é o vetor direção de busca.
Para escolhermos a direção , tomamos a fórmula de Taylor de em torno da aproximação
(3.287) |
onde denota o gradiente de , i.e.
(3.288) | ||||
(3.289) |
De , segue que se
(3.290) |
então , para suficientemente pequeno. Em particular, podemos escolher
(3.291) |
se .
Do exposto acima, temos a iteração do Método do Gradiente
(3.292) | ||||
com , onde é o resíduo
(3.293) |
Consideramos o sistema com
(3.294) | ||||
(3.295) |
Na Tabela 3.3 temos os resultados do emprego do método do gradiente com e com passo constante .
k | ||
---|---|---|
0 | ||
1 | ||
2 | ||
3 | ||
4 | ||
5 | ||
6 | ||
7 | ||
8 | ||
9 | ||
10 |
Para a escolha do passo, podemos usar o Método da Pesquisa Linear. A ideia é escolher o passo tal que
(3.296) |
Observando que é função apenas de , temos que seu mínimo ocorre em seu ponto crítico, i.e.
(3.297) | |||
(3.298) | |||
(3.299) | |||
(3.300) | |||
(3.301) |
donde
(3.302) |
Consideramos o sistema com
(3.303) | ||||
(3.304) |
Na Tabela 3.4 temos os resultados do emprego do método do gradiente com e com passo escolhido conforme (3.302).
k | |||
---|---|---|---|
Considere o sistema linear com
(3.305) | ||||
(3.306) |
Por tentativa e erro, encontre um valor para tal que o Método do Gradiente converge para solução do sistema em menos de iterações. Use
(3.307) |
como aproximação inicial e assuma o critério de parada
(3.308) |
onde é o resíduo do sistema e .
,
Considere o sistema linear com
(3.309) | ||||
(3.310) |
Por tentativa e erro, encontre um valor para tal que o Método do Gradiente converge para solução do sistema em menos de iterações. Use
(3.311) |
como aproximação inicial e assuma o critério de parada
(3.312) |
onde é o resíduo do sistema e .
,
Considere o sistema linear dado no Exercício 3.4.1. Utilizando a mesma aproximação inicial e tolerância, aplique o Método do Gradiente com Pesquisa Linear. Quantas iterações são necessárias até a convergência e qual o valor médio de utilizado durante as iterações?
,
Considere o sistema linear dado no Exercício 3.4.2. Utilizando a mesma aproximação inicial e tolerância, aplique o Método do Gradiente com Pesquisa Linear. Quantas iterações são necessárias até a convergência e qual o valor médio de utilizado durante as iterações?
,
Considere o problema de Laplace
(3.313) | ||||
(3.314) |
A discretização pelo Método das Diferenças Finitas em uma malha uniforme , , , leva ao seguinte sistema linear
(3.315) | |||
(3.316) | |||
(3.317) |
onde . Com , aplique o Método do Gradiente com Pesquisa Linear para computar a solução deste sistema quando . Quantas iterações são necessárias para obter-se a convergência do método com critério de convergência
(3.318) |
onde, é o resíduo e .
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.