Método dos gradientes e gradientes conjugados

1- Teoria

Tanto o método dos gradientes como o método dos gradientes conjugados são métodos iterativos para solução de sistemas lineares. Para compreendê-los é necessário conhecer o processo de relaxação explicado resumidamente a seguir:

Dado um sistema linear Ax + b = 0 , onde A é positiva definida (para todos menores principais Ak , det(Ak) > 0) e, x e b são vetores. Se v é uma aproximação da solução então:

r = Av + b é chamado resíduo.

O objetivo é fazer com que o resíduo se anule. Para isso, tomamos a função quadrática :

F(v) = ½ (Av,v) + (b,v)

Após algumas operações envolvendo esta função, concluímos que Av + b = 0 = grad F (v). Mas, desde que Av + b = r , podemos concluir que grad F (v) = r. Portanto, o objetivo é obter grad F (v) = 0, pois assim teremos r = 0. O príncipio básico do processo de relaxação consiste em escolher uma direção p e variar v nessa direção até F(v) atingir o ponto de mínimo, encontrando assim, a solução do sistema. Um parâmetro t é selecionado de tal forma que F é mínimo. Assim :

a) Método dos Gradientes

Dado um sistema com a matriz A positiva definida, construímos a função quadrática F(v). Para este método a direção p de relaxação é definido por:

E temos que:

Neste processo os resíduos consecutivos são ortogonais. Assim temos que:

Concluindo, dados v(0) e Е (precisão), seguimos os seguintes passos para a implementação do algoritmo:

caso contrário, b) .

b) Método dos Gradientes Conjugados

Dada a matriz A positiva definida , x e y são direções conjugadas se (Ax, y) = (x, Ay) = 0 . Possuindo o valor de v(0) , inicialmente calculamos r(0) = Av(0) + b e fazemos:

onde

então:

Considerando a passagem do passo k-1 para o passo k , tomamos p(k) tal que p(k) e p(k-1) sejam direções conjugadas. Assim:

onde αk-1 é determinado por :

Agora que é possível determinar a direção p(k) , encontramos o ponto de mínimo:

onde

Com esses