Por que os gradientes conjugados exigem uma matriz simétrica definida positiva?

Se A é SDP, a função quadrática é estritamente convexa e fica definido o produto interno A com o qual se constroem as direções conjugadas. Sem essas propriedades as garantias clássicas do método não valem.

Por que o sistema bidimensional se resolve em dois passos?

Em aritmética exata o método minimiza sobre um subespaço de Krylov que cresce e termina em no máximo n iterações para um sistema SDP de dimensão n. Na demonstração bidimensional a solução chega com no máximo duas direções independentes.

Em que os gradientes conjugados superam a descida mais íngreme?

A descida mais íngreme segue −∇f e nas elipses alongadas ziguezagueia. As direções conjugadas não repetem as direções A já escolhidas, de modo que num poço mal condicionado a convergência é bem mais rápida.

Gradientes conjugados

Sistema SDP Ax=b como minimização de uma forma quadrática: curvas de nível, gradientes conjugados contra a descida mais íngreme, norma do resíduo e número de condição.

Em aritmética exata os gradientes conjugados alcançam a solução 2D em no máximo duas iterações. As iterações extras aqui mostram sobretudo o resíduo na escala de arredondamento e como a trajetória se afasta da descida mais íngreme.

Gráficos

Sobre o modelo

Os gradientes conjugados resolvem Ax = b quando A é simétrica definida positiva, o que equivale a minimizar f(x) = ½ xᵀ A x − bᵀ x. No exemplo bidimensional as curvas de nível são elipses, a solução exata é o centro delas e o resíduo vale b − Ax. O método escolhe direções de busca A-conjugadas. Do mesmo ponto parte também a descida mais íngreme: nas elipses alongadas ela ziguezagueia. O número de condição κ = λ_max/λ_min define o quanto o poço se alonga. Em aritmética exata os gradientes conjugados terminam em no máximo n passos num sistema SDP de dimensão n.

Para quem: Álgebra linear numérica, computação científica, otimização e resolvedores de equações diferenciais parciais.

Conceitos-chave

gradientes conjugados
matriz simétrica definida positiva
norma do resíduo
minimização quadrática
número de condição
descida mais íngreme

Como funciona

Para uma matriz simétrica definida positiva, o sistema Ax=b equivale a minimizar f(x)=1/2 x^T A x − b^T x. As curvas de nível dessa função são elipses, e a solução x\* fica no centro delas. O método dos gradientes conjugados constrói direções p_k conjugadas no produto interno (·,·)_A e escolhe o passo α_k=(r_k^T r_k)/(p_k^T A p_k). No caso bidimensional, com aritmética exata bastam duas iterações; um κ grande alonga as elipses e atrasa métodos aparentados, por exemplo a descida mais íngreme.

Fórmulas principais

Os gradientes conjugados resolvem Ax=b ao minimizar f(x)=1/2 x^T A x − b^T x para A SDP

α_k=(r_k^T r_k)/(p_k^T A p_k), β_k=(r_{k+1}^T r_{k+1})/(r_k^T r_k)

Perguntas frequentes

Por que os gradientes conjugados exigem uma matriz simétrica definida positiva?: Se A é SDP, a função quadrática é estritamente convexa e fica definido o produto interno A com o qual se constroem as direções conjugadas. Sem essas propriedades as garantias clássicas do método não valem.
Por que o sistema bidimensional se resolve em dois passos?: Em aritmética exata o método minimiza sobre um subespaço de Krylov que cresce e termina em no máximo n iterações para um sistema SDP de dimensão n. Na demonstração bidimensional a solução chega com no máximo duas direções independentes.
Em que os gradientes conjugados superam a descida mais íngreme?: A descida mais íngreme segue −∇f e nas elipses alongadas ziguezagueia. As direções conjugadas não repetem as direções A já escolhidas, de modo que num poço mal condicionado a convergência é bem mais rápida.

Continue com temas próximos desta categoria — ou todos os 85 em «Visualização matemática».

Toda a categoria →

NovoEscola

Gradiente descendente

Abrir o simulador

Curvas de nível de f(x, y) e trajetória (x, y) ← (x, y) − η∇f; tigela ou poço elíptico.

NovoUniversidade / pesquisa

Elementos finitos: equação de Poisson

Abrir o simulador

Elementos P1 triangulares para −Δu = f no quadrado: montagem das matrizes de rigidez, nós de Dirichlet prescritos ou fluxo natural de Neumann, solução pelos gradientes conjugados, potencial como membrana colorida.

NovoUniversidade / pesquisa

Geometria de PCA / SVD

Abrir o simulador

Elipse de covariância e redução de dimensão pela decomposição em valores singulares: componentes principais, variância explicada e erro de reconstrução de posto 1.

NovoUniversidade / pesquisa

Otimizadores de gradiente descendente

Abrir o simulador

Comparação de SGD, momento e Adam num relevo bidimensional da função de perda: taxa de aprendizado, curvatura, estabilidade e trajetórias das iterações.

NovoUniversidade / pesquisa

Partículas em um campo de escoamento

Abrir o simulador

Campo sintético v(x, y, t); transporte com fronteiras periódicas; à vontade, uma rede de setas.

NovoUniversidade / pesquisa

Equação do calor: diferenças finitas

Abrir o simulador

Equação unidimensional u_t = αu_xx: FTCS explícito e Euler implícito retrógrado; mude r = αΔt/Δx², veja a explosão do esquema explícito se r > 1/2 e compare a difusão numérica.

Gradientes conjugados

Gráficos

Sobre o modelo

Como funciona

Fórmulas principais

Perguntas frequentes

Simuladores relacionados

Gradiente descendente

Elementos finitos: equação de Poisson

Geometria de PCA / SVD

Otimizadores de gradiente descendente

Partículas em um campo de escoamento

Equação do calor: diferenças finitas

Gradientes conjugados

Gráficos

Sobre o modelo

Como funciona

Fórmulas principais

Perguntas frequentes