Método do Gradiente e Gradiente Conjugado

Método do Gradiente e Gradientes Conjugados

Uma outra classe de métodos que permite a resolução numérica de equações é a classe dos métodos de optimização.
Considerando uma equação da forma f(x)=0, é claro que f(x)=0 sse f(x)f(x)=0.
Ora, os pontos z que verificam a equação equivalente f(z)²=0 são também os pontos de mínimo absoluto da função f ², que é não negativa.
Ou seja, se existirem, os zeros de f são os pontos de mínimo absoluto de f ².
De forma semelhante, no caso de funções com várias variáveis, usando a norma euclidiana, obtemos:

F(x)= 0 <=> ||F(x)||²=0 <=> F(x). F(x)=0

e, se existirem, as soluções de F(x)= 0 são os pontos de mínimo absoluto de f(x)= F(x). F(x).

Portanto, podemos utilizar métodos de optimização para a resolução de equações ou sistemas de equações. Sabemos que quando as funções são regulares, um ponto de mínimo relativo é um ponto crítico, que anula a derivada, ou o gradiente. Assim, por outro lado, os métodos para a resolução de equações, também são usados como métodos de optimização. No entanto, há outros métodos específicos para os problemas optimização. Iremos ver (brevemente) o método do gradiente e o método do gradiente conjugado, aplicados à resolução de alguns sistemas.

Seja A uma matriz simétrica e definida positiva, e consideremos uma forma quadrática auxiliar:

f(x)= (1/2) x^TAx -b^Tx + c,

que transforma vectores em números reais. Como a forma é quadrática, há apenas um vector que minimiza f e é exactamente o ponto crítico, solução de

f(x)=0, e neste caso,

f(x) = (1/2)(A^T+A)x-b = Ax -b.

Assim, se encontrarmos o ponto de mínimo, ele será solução do sistema linear Ax = b.

Consideramos métodos iterativos de optimização do tipo

x⁽ⁿ⁺¹⁾= x⁽ⁿ⁾+ a_nr⁽ⁿ⁾ ,

de forma a que haja uma descida, ou seja, f (x⁽ⁿ⁺¹⁾) < f (x⁽ⁿ⁾). O vector r⁽ⁿ⁾ define a direcção de descida.

Método do Gradiente
No caso do método do gradiente (ou declive máximo - steepest descent), a direcção de descida escolhida é

r⁽ⁿ⁾ = -f(x⁽ⁿ⁾) = b - Ax⁽ⁿ⁾,

que neste caso de sistemas lineares é também designado por resíduo.
Resta encontrar o valor a_nque minimiza f, de entre os possíveis valores x⁽ⁿ⁾+ ar⁽ⁿ⁾. Encontramos o ponto de mínimo, derivando f (nesses pontos) em ordem a a, ou seja,

d/da f (x⁽ⁿ⁾+ ar⁽ⁿ⁾) = f(x⁽ⁿ⁾+ ar⁽ⁿ⁾) . r⁽ⁿ⁾
= (b - A(x⁽ⁿ⁾+ar⁽ⁿ⁾)). r⁽ⁿ⁾
= (b - Ax⁽ⁿ⁾). r⁽ⁿ⁾-aAr⁽ⁿ⁾. r⁽ⁿ⁾
= r⁽ⁿ⁾. r⁽ⁿ⁾-aAr⁽ⁿ⁾. r⁽ⁿ⁾.

Assim, o valor mínimo a_nserá obtido com o zero da derivada,

r⁽ⁿ⁾. r⁽ⁿ⁾-a_nAr⁽ⁿ⁾. r⁽ⁿ⁾= 0 <=> a_n= r⁽ⁿ⁾. r⁽ⁿ⁾/(Ar⁽ⁿ⁾. r⁽ⁿ⁾).

Em conclusão, dado um vector inicial x⁽⁰⁾, o método do gradiente resume-se à iteração

x⁽ⁿ⁺¹⁾= x⁽ⁿ⁾+

r⁽ⁿ⁾. r⁽ⁿ⁾r⁽ⁿ⁾. Ar⁽ⁿ⁾

r⁽ⁿ⁾, com r⁽ⁿ⁾ = b - Ax⁽ⁿ⁾.

Um critério de paragem consiste em exigir que || r⁽ⁿ⁾||² = r⁽ⁿ⁾. r⁽ⁿ⁾ < e, com e pequeno,
notando que isso implica que Ax⁽ⁿ⁾ é próximo de b.

Observação: Aqui o método do gradiente está aplicado ao caso de sistemas lineares, em que a função f é apenas auxiliar, nem tão pouco aparece na expressão do método. No entanto, este método pode ser utilizado para minimizar funções diferenciáveis, nesse caso mais geral, r⁽ⁿ⁾ = -f(x⁽ⁿ⁾).

Método das Direcções Conjugadas
Começamos por definir direcções conjugadas.
Como assumimos que a matriz A é definida positiva, há um produto interno associado a essa matriz <u,v>_A= u . Av = u^TAv.

Com este produto interno, dois vectores dizem-se A-ortogonais se <u,v>_A= u . Av = 0, como sinónimo diz-se que as direcções u e v são conjugadas.

Seja N a dimensão da matriz A e sejam d⁽⁰⁾, ..., d^(N-1) direcções conjugadas, que constituem uma base A-ortogonal em R^N.

Se considerarmos d⁽ⁿ⁾ como direcções de descida, temos a iteração

x⁽ⁿ⁺¹⁾= x⁽ⁿ⁾+ a_nd⁽ⁿ⁾ , e queremos agora encontrar o valor a_nque minimiza f, de entre os possíveis valores x⁽ⁿ⁾+ ad⁽ⁿ⁾.

De forma, semelhante, podemos obter

d/da f (x⁽ⁿ⁾+ ad⁽ⁿ⁾) = r⁽ⁿ⁾. d⁽ⁿ⁾-aAd⁽ⁿ⁾. d⁽ⁿ⁾, e assim a_n= r⁽ⁿ⁾. d⁽ⁿ⁾/(d⁽ⁿ⁾. Ad⁽ⁿ⁾), com r⁽ⁿ⁾ = b - Ax⁽ⁿ⁾.

Obtemos de forma genérica, um método de direcções conjugadas:

x⁽ⁿ⁺¹⁾= x⁽ⁿ⁾+

r⁽ⁿ⁾. d⁽ⁿ⁾d⁽ⁿ⁾. Ad⁽ⁿ⁾

d⁽ⁿ⁾,

mas ainda não definimos as direcções d⁽ⁿ⁾, apenas assumimos que existiam a priori, e eram conjugadas.

Teorema: Um método de direcções conjugadas atinge a solução ao fim de N iterações.
Demonstração:
Consideremos o erro na iterada n, definido por e⁽ⁿ⁾= x - x⁽ⁿ⁾.
Reparamos que

e⁽ⁿ⁺¹⁾= e⁽ⁿ⁾-

r⁽ⁿ⁾. d⁽ⁿ⁾d⁽ⁿ⁾. Ad⁽ⁿ⁾

d⁽ⁿ⁾,

e mantendo a notação a_n= r⁽ⁿ⁾. d⁽ⁿ⁾ / (d⁽ⁿ⁾. Ad⁽ⁿ⁾), podemos escrever recursivamente e^(N),

e^(N)= e^(N-1)-a_N-1d^(N-1) = ... = e⁽⁰⁾- a_N-1d^(N-1) - ... - a₀d⁽⁰⁾

Por outro lado, podemos escrever e⁽⁰⁾ na base A-ortogonal d⁽⁰⁾, ..., d^(N-1) através das projecções A-ortogonais

e⁽⁰⁾= P_N-1d^(N-1) + ... + P₀d⁽⁰⁾

em que P_n é a projecção A-ortogonal de e⁽⁰⁾ na direcção d⁽ⁿ⁾, ou seja

P_n = < e⁽⁰⁾, d⁽ⁿ⁾>_A/ < d⁽ⁿ⁾, d⁽ⁿ⁾>_A = (e⁽⁰⁾. Ad⁽ⁿ⁾) / (d⁽ⁿ⁾. Ad⁽ⁿ⁾).

Portanto, basta agora ver que para cada n temos P_n = a_n , para concluir que e^(N)= 0, ou seja que x^(N) é a solução exacta.
De facto, atendendo às expressões de P_n e de a_n basta ver que r⁽ⁿ⁾. d⁽ⁿ⁾= e⁽⁰⁾. Ad⁽ⁿ⁾.
Ora, Ae⁽ⁿ⁾= Ax-Ax⁽ⁿ⁾= b-Ax⁽ⁿ⁾= r⁽ⁿ⁾, portanto

d⁽ⁿ⁾. r⁽ⁿ⁾= d⁽ⁿ⁾. Ae⁽ⁿ⁾= d⁽ⁿ⁾. A(e⁽⁰⁾- a_n-1d^(n-1) - ... - a₀d⁽⁰⁾)
= d⁽ⁿ⁾. Ae⁽⁰⁾- a_n-1d⁽ⁿ⁾. Ad^(n-1) - ... - a₀d⁽ⁿ⁾. Ad⁽⁰⁾
= d⁽ⁿ⁾.Ae⁽⁰⁾- 0 - ... - 0, porque d^(n-1), ..., d⁽⁰⁾ são A-ortogonais a d⁽ⁿ⁾.

Método dos Gradientes Conjugados
Consideramos agora o caso particular do método das direcções conjugadas, em que elas são obtidas através do gradiente.
Recordamos que no caso linear o gradiente é dado pelo resíduo r⁽ⁿ⁾ = b - Ax⁽ⁿ⁾.
Através de um processo de ortogonalização (ou melhor, A-ortogonalização) de Gram-Schmidt, através dos sucessivos resíduos (gradientes) podemos construir as direcções d⁽ⁿ⁾ que serão conjugadas (A-ortogonais).
Assim, podemos resumir o Método dos Gradientes Conjugados,

1º) Dado x⁽⁰⁾ definimos d⁽⁰⁾ = r⁽⁰⁾ = b-Ax⁽⁰⁾ ,

2º) Definimos x⁽ⁿ⁺¹⁾= x⁽ⁿ⁾+ a_nd⁽ⁿ⁾ , com a_n= r⁽ⁿ⁾. d⁽ⁿ⁾ / (d⁽ⁿ⁾. Ad⁽ⁿ⁾)

3º) Definimos r⁽ⁿ⁺¹⁾= r⁽ⁿ⁾- a_nAd⁽ⁿ⁾ , e d⁽ⁿ⁺¹⁾= r⁽ⁿ⁺¹⁾+ b_nd⁽ⁿ⁾, com b_n= r⁽ⁿ⁺¹⁾. r⁽ⁿ⁺¹⁾ / (r⁽ⁿ⁾. r⁽ⁿ⁾)

4º) Regressamos ao 2º passo, até que sejam efectuados N passos.

Nota: Apesar de termos demonstrado que o método atinge a solução exacta ao fim de N passos, um mau condicionamento da matriz poderá impedir que a solução seja efectivamente obtida. Nesse caso há que utilizar um critério de paragem, p.ex: exigindo que o resíduo seja suficientemente pequeno.

Observação: De forma alternativa, mas menos eficiente, podemos escrever o método na forma equivalente:
1º) É dado x⁽⁰⁾ .
2º) Definimos

r⁽ⁿ⁾= b - Ax⁽ⁿ⁾
se n=0, d⁽⁰⁾ = r⁽⁰⁾,
se n>0, d⁽ⁿ⁾ = r⁽ⁿ⁾ + (r⁽ⁿ⁾.r⁽ⁿ⁾)/(r^(n-1).r^(n-1))d^(n-1),
x⁽ⁿ⁺¹⁾ = x⁽ⁿ⁾ + (r⁽ⁿ⁾.r⁽ⁿ⁾)/(d⁽ⁿ⁾. Ad⁽ⁿ⁾)d⁽ⁿ⁾

3º) Regressamos ao 2º passo (até que sejam efectuados N passos).

Apesar de ser equivalente, neste caso aparecem dois produtos pela matriz A, mais concretamente Ax⁽ⁿ⁾ e Ad⁽ⁿ⁾, o que implica um maior número de operações. Por isso é preferível utilizar o algoritmo anterior, onde aparece apenas um produto, o Ad⁽ⁿ⁾.