Método dos gradientes Conjugados

MÉTODO DOS GRADIENTES CONJUGADOS (Métodos Numéricos – Maria Cristina C. Cunha)

Os métodos gradientes conjugados têm sido estudados a partir da década de 50, motivados pela solução de sistemas provenientes da discretização de equações diferenciais parciais e viabilizados pela entrada dos computadores nos cálculos científicos. Vários autores citam os trabalhos de Hestenes e Stiefel, de 1952, como base do que foi desenvolvido posteriormente.
Consideraremos que a matriz do sistema linear seja simétrica e positiva definida, isto é, AT=A e xT Ax > 0, para qualquer x não-nulo.

Idéia básica dos métodos do tipo gradiente, para resolver o sistema Ax = b é minimizar a função de x = (x1, x2 , ..., xn )

(1)
Para simplificar, quando abrirmos as equações matriciais, o faremos supondo n = 2, embora o desenvolvimento seja o mesmo para um número arbitrário de componentes. Por exemplo, para verificar que F(x) é uma função quadrática nas componentes do vetor x, tomamos n = 2 em (1):

onde foi usada a simetria da matriz A.

As curvas de nível da função F(x) são definidas por F(x1,x2) = constante e, portanto, são elipses. Assim, o gráfico de F(x) é um parabolóide e esta função tem um único mínimo.
O mínimo da função é atingido no vetor x que anula o gradiente da função,

grad (2)

Sendo assim, grad F(x1,x2) = 0 significa Ax = b, isto é, a solução do sistema de equações lineares minimiza a função quadrática e vice-versa.
Como é conhecido do Cálculo Diferencial, o vetor gradiente aponta a direção do máximo da função. Portanto é natural que, nos passos de busca do mínimo, caminhemos na direção contrário ao gradiente, isto é:

x(k+1) = x(k) – sk grad F( x(k) ) . (3)

Assim, a aproximação num passo k+1 é calculada a partir da aproximação no passo anterior, caminhando na direção contrária ao gradiente. O parâmetro real sk regula o tamanho do passo na k-ésima iteração.
Usando (2), temos que a direção de descida é – grad F( x(k) ) = b – Ax(k) =