Gradientes Conjugados
Referência: “An Introduction to the Conjugate Gradient Method Without the Agonizing
Pain”, J. R. Shewchuk (Google)
Problema: como minimizar uma função de muitas variáveis,
conhecendo o valor da função e de seu gradiente em cada ponto?
Problema equivalente: sistemas de equações lineares
A matriz A é simétrica e positiva-definida:
, qualquer x
Forma quadrática
A função f (x) é minimizada pela solução do sistema
Exemplo:
2
Solução:  
 2
2
Solução:  
 2
Gradiente da forma quadrática
Se
e se A é simétrica,
Minimizar f é o mesmo que tornar seu gradiente
nulo, ou seja, resolver
2
Solução:  
 2
O método de “steepest descent”
Iniciar em um ponto x(0) e executar vários passos para x(1), x(2),
sempre nas direções contrárias aos gradientes (descida mais
íngreme):
Definições importantes:
Erro:
indica o quão longe estamos da solução
Resíduo:
Primeiro passo:
Qual o tamanho do passo?
Minimizar f ao longo de uma linha:
novo gradiente deve ser ortogonal
ao anterior
x(1)
x(0)
Calculando α:
Em resumo, o método de
“steepest descent”:
Em “steepest descent”, temos que dar vários passos na mesma
direção. O ideal seria se, em cada passo, eliminássemos
completamente a componente do erro naquela direção.
Infelizmente isso é
impossível, pois não
sabemos o erro. Se
soubéssemos o erro,
já teríamos a solução,
e o problema estaria
resolvido.
Em vez disso, podemos
fazer como na linha verde:
minimizar ao longo de
uma linha e depois tomar
a direção que nos leva até
o mínimo. Esta é a direção
conjugada
Direções conjugadas
Dois vetores d(i) e d(j) são conjugados (ou A-ortogonais) se
Vamos ver o que acontece
quando impomos que o erro
e(i+1) deve ser conjugado (e
não mais ortogonal) à direção
de busca anterior d(i)
Inicialmente, veremos que isto equivale a uma minimização na
direção d(i)
Onde usamos que Ae(i 1)  A( x(i 1)  x)  Ax(i 1)  b  f ( x(i 1) )  r(i 1)
Vamos agora encontrar o coeficiente α, impondo a condição
d (Ti ) Ae(i )   (i ) d (i )   0
 (i )  
d (Ti ) Ae(i )
T
(i )
d Ad(i )

d (Ti ) r(i )
d (Ti ) Ad(i )
Veremos agora que, se tivermos um conjunto de n direções
conjugadas, onde n é a dimensão dos espaço, veremos que esse
procedimento minimza a função em apenas n passos.
Para isto, expressamos o erro inicial em uma combinação linear
das direções:
 (i )   (i )
Ou seja, em cada passo eliminamos
a componente do erro na direção
correspondente, e esta componente
nunca mais aparece nos passos
seguintes
Conjugação de Gram-Schmidt
Precisamos então encontrar um conjunto de n direções conjugadas.
Isto pode ser feito pelo método de conjugação de Gram Schmidt:
Dado um conjunto de n vetores L.I. u(i):
Gradientes Conjugados
Usar como u(i) o conjunto dos resíduos (gradientes) para obter, por
Gram-Schmidt, as direções de busca.
Usando a identidade:
Obtemos:
Gradientes são
ortogonais
Definindo β(i) = βi,i-1 e a expressão para αi:
Finalmente, o algoritmo de gradientes conjugados:
Primeira direção é o resíduo inicial
Minimizar ao longo de d(i):
Calcular o novo gradiente (resíduo) r(i+1) e obter
Com isso, obter a nova direção
 ( i 1) 
r(Ti1) r( i 1)
d (Ti ) r( i )