direita|thumb|Uma comparação da convergência do método de descida do gradiente com tamanho de passo ótimo (em verde) e o método do gradiente conjugado (em vermelho) para a minimização da forma quadrática com um sistema linear dado. O gradiente conjugado, assumindo aritmética exata, converge em no máximo n passos onde n é o tamanho da matriz do sistema (no exemplo, n=2).
Em matemática, o método do gradiente conjugado é um algoritmo para a solução numérica de sistemas de equações lineares, cuja matriz é simétrica e positiva definida. O método do gradiente conjugado é um método iterativo, então ele pode ser aplicado a sistemas esparsos que são grandes demais para ser tratados por métodos diretos como a decomposição de Cholesky. Tais sistemas surgem frequentemente quando se resolve numericamente equações diferenciais parciais.
O método do gradiente conjugado também pode ser utilizado para resolver problemas de otimização irrestritos como minimização de energia. É comumente atribuído aos matemáticos Magnus Hestenes e Eduard Stiefel, que o programaram no computador Z4 e o estudaram extensivamente.
O método do gradiente biconjugado fornece uma generalização a matrizes não simétricas. Diversos métodos do gradiente conjugado não lineares procuram o mínimo de problemas de otimização não lineares.
Descrição do problema Considera-se resolver o sistema de equações lineares
para o vetor , onde é uma matriz real simétrica (i.e., ) positiva definida (i.e., para todo ) e . Denota-se a solução única desse sistema por .
Derivação do método do gradiente conjugado O método do gradiente conjugado (CG) pode ser derivado sob diversas perspectivas. A abordagem a seguir busca minimizar uma função quadrática envolvendo a matriz e o vetor .
O método da descida rápida thumb|right|Descida do gradiente em 2D|250x250px
O método CG pode ser obtido a partir do método da descida rápida para resolver um sistema positivo definido acrescido de modificações que melhoram a taxa de convergência. Para resolver o sistema linear , onde é matriz positiva definida, encontra-se o mínimo de uma função quadrática cujo mínimo coincide com a solução do sistema. Considere a função
onde e . Para minimizar encontra-se o vetor tal que todas as derivadas parciais sejam nulas. O gradiente de é o vetor , então é ponto de mínimo somente se . Algumas manipulações algébricas mostram que
Como é simétrica,
e o mínimo de ocorre quando . Logo, o problema de otimização de encontrar o valor mínimo de uma função é equivalente a resolver . Como é positiva definida, é não singular, e . Portanto,
A revela o tipo de superfície gerado pela função . Como é uma matriz real e simétrica, o Teorema Espectral garante que existe uma matriz ortogonal tal que , onde é uma matriz diagonal contendo os autovalores de . Fazendo a mudança de coordenadas , i.e., , e substituindo na , obtém-se
notando que e que . Tem-se que , porque é positiva definida. Para , representa um paraboloide elíptico. Em geral, a transformação ortogonal preserva as distâncias e os ângulos entre os vetores, então é um paraboloide no . Isso garante que o ponto crítico onde o gradiente se anula () é o mínimo global da função.
Na descida rápida, o valor mínimo é encontrado iterativamente, tomando um ponto inicial e decaindo em direção a . Como a função quadrática decresce mais rapidamente na direção negativa do gradiente, a mostra que . Seja
o resíduo no ponto . Então o próprio resíduo aponta na direção de maior decrescimento da função partindo de e é chamado de vetor diretor. Se o resíduo é zero, o problema está resolvido, caso contrário, move-se ao longo da reta determinada pelo vetor diretor. Seja , onde é um escalar que determina o tamanho do passo na direção do resíduo . No método da descida rápida, minimiza para cada passo na reta correspondente. Para isso, considere a função
Usando a simetria de e a comutatividade do produto interno, tem-se
O mínimo de ocorre quando , e
Então, o mínimo ocorre quando . Move-se de a e depois usa e para computar , o próximo ponto em direção ao mínimo. Esse desenvolvimento motiva o algoritmo a seguir.
Entradas matriz simétrica positiva definida, lado direito , aproximação inicial , tolerância tol e número máximo de iterações maxiter.
Saídas solução aproximada , norma-2 do resíduo relativo e número de iterações
Inicialização
Algoritmo Enquanto for maior que a tolerância desejada e o número de iterações for menor que o número máximo de iterações, faça:
Se for suficientemente pequeno, então pare o ciclo. Fim Enquanto Se o número de iterações for maior que o número máximo de iterações, faça Retorna , ,
O método da descida rápida converge globalmente. Se e são, respectivamente, o maior e o menor autovalor de uma matriz simétrica , o número de condicionamento da matriz é dado por
Pode ser mostrado que
Definindo a função erro , a pode ser reescrita como
o que indica que o algoritmo da descida rápida converge independentemente do chute inicial , pois . Se é grande, então é próximo de 1 e a convergência é lenta. Isso pode ser visto geometricamente. Para qualquer matriz , as direções de buscas sucessivas são ortogonais. Sabendo que ,
Substituindo pelo valor de , vem
então . Se é o ponto atual na descida ao mínimo, o vetor de direção de busca é ortogonal ao conjunto de nível . A próxima direção de busca é ortogonal à direção de busca anterior e ao conjunto de nível . Para , esse caminho segue um padrão de zigue-zague que pode não ser o mais eficiente até o mínimo. Como os autovalores de uma matriz simétrica são iguais aos seus valores singulares, a forma das elipses que configuram as linhas de contorno da função dependem do número de condicionamento da matriz. Se é pequeno, as elipses são próximas de círculos, e a descida rápida converge rapidamente ao mínimo do paraboloide. Se é grande, essas elipses se tornam mais alongadas e estreitas; o paraboloide tem um cânion perto do mínimo que faz os valores de se moverem de um lado para o outro nas paredes íngremes do cânion, desacelerando a convergência.
Exemplo numérico
Aplicando o método da descida rápida às matrizes , e , , com , e tolerância de em ambos os casos, obtém-se a aproximação desejada em 21 iterações para a matriz e em 8462 iterações para a matriz .
Uma analogia para entender a descida rápida thumb|Neblina nas montanhas|249x249px
A intuição por trás da descida rápida pode ser ilustrada pelo seguinte cenário hipotético. Um grupo de pessoas encontra-se perdido nas montanhas e tenta descer de volta à entrada da trilha (i.e., tenta achar o mínimo global). Há uma densa neblina que torna a visibilidade extremamente baixa, então o caminho até a base da montanha não é visível e elas precisam usar informação local para se guiarem. Elas podem usar o método da descida rápida, que envolve calcular a declividade da ladeira na sua posição atual e prosseguir na direção com a maior declividade. Caso elas quisessem ir ao topo da montanha (i.e., o máximo global), bastava seguir a direção com maior aclive. Usando esse método, elas eventualmente encontrariam o caminho da descida, ou então ficariam presas em algum buraco (i.e., ponto de mínimo local ou ponto de sela), como um lago da montanha. No entanto, suponha que encontrar a direção de maior declive não é imediatamente óbvio por mera observação, mas que requer algum tipo de instrumento sofisticado para calcular que uma das pessoas coincidiu de trazer consigo para a trilha. Calcular a declividade em cada posição toma certo tempo, então elas devem minimizar o uso do instrumento caso elas queiram descer da montanha antes do pôr do sol. A dificuldade é então escolher a frequência com a qual calcular a declividade na posição atual, de modo a não perderem o rumo.
Nessa analogia, as pessoas representam o algoritmo, e o caminho a ser tomado para descer a montanha representa a sequência de configurações que o algoritmo vai explorar. A declividade da ladeira representa a inclinação da função naquele ponto. O instrumento usado para medir a declividade é a diferenciação. A direção que o grupo escolhe para descer a montanha é a direção do gradiente negativo da função naquele ponto. O tempo que elas caminham antes de fazer outra medição é o tamanho do passo.
Da descida rápida ao gradiente conjugado O método da descida rápida faz uma busca baseada no gradiente conforme , onde os são os vetores do resíduo. Esse algoritmo é um algoritmo guloso; ele resolve o problema de minimização de apenas localmente. Uma vez que as direções de busca são sucessivamente ortogonais, o caminho em zigue-zague pode desfazer o progresso passado e ainda repetir direções na descida ao mínimo da função . Uma alternativa é então escolher direções de busca de forma a não perder a minimização atingida em qualquer direção de busca anterior.
O método do gradiente conjugado computa , onde os vetores diretores são escolhidos tal que as aproximações decrescem muito mais rapidamente ao mínimo de . Isso pode ser feito exigindo que as direções de busca sejam conjugadas em relação a uma matriz , i.e., elas devem ser ortogonais após serem esticadas e distorcidas por . Desse modo, o método utiliza informações dos passos anteriores e evita o padrão de zigue-zague característico da descida rápida.
O gradiente conjugado como um método direto
Embora seja usado como um método iterativo, o método do gradiente conjugado foi originalmente desenvolvido por Hestenes e Stiefel como um método direto para resolver sistemas lineares positivo definidos que encontra a solução exata em passos, assim como a eliminação gaussiana com pivotamento parcial. Seja qual for a abordagem, toda derivação do método do gradiente conjugado se apoia em duas propriedades fundamentais:
Os vetores do resíduo são ortogonais: (); Os vetores diretores são -conjugados: ().
Para saber como escolher as direções de busca , é necessário definir a norma- (ou norma de energia). Dizemos que dois vetores não nulos e são conjugados em relação a uma matriz (ou -conjugados) se
Sendo simétrica e positiva definida, o lado esquerdo da equação define um produto interno
Então, dois vetores são -conjugados se, e somente se, eles são ortogonais com respeito a esse produto interno. Essa é uma relação simétrica: se é -conjugado a , então é -conjugado a . Suponha que
é um conjunto de vetores -conjugados dois a dois, i.e., para todo . Então forma uma base para , e podemos escrever a solução de nessa base:
Multiplicando pela esquerda a equação por , fica
Isolando , chegamos em
Isso resulta no seguinte método para resolver a equação matricial : encontre uma sequência de direções conjugadas, e então calcule os coeficientes .
O gradiente conjugado como um método iterativo
Se os vetores conjugados forem escolhidos cuidadosamente, é possível que nem todos eles sejam necessários para obter uma boa aproximação para a solução . Assim, o método do gradiente conjugado pode ser considerado como um método iterativo. Isso possibilita encontrar soluções aproximadas de sistemas de ordem suficientemente grande tal que o método direto levaria muito tempo para resolver.
Simlarmente ao método da descida rápida, o algoritmo começa com uma aproximação . A primeira direção de busca é tomada como . Os outros vetores da base serão conjugadas ao gradiente, então o nome método do gradiente conjugado. Observa que é também o resíduo proveniente do passo inicial do algoritmo.
Seja o resíduo no i-ésimo passo. Como notado acima, é o negativo do gradiente de no ponto , então a descida rápida exigiria um passo na direção . Dessa vez, no entanto, faz-se com que as direções sejam -conjugadas. Uma forma de fazer isso é exigindo que a próxima direção de busca seja construída do resíduo e de todas as direções de busca anteriores. Essa restrição de conjugação é um tipo de restrição de ortogonalização, logo o algoritmo pode ser visto como um exemplo do processo de Gram-Schmidt. Isso leva à expressão: