Mestre

Cálculo Numérico / Métodos Numéricos

Sistemas lineares
Método dos Gradientes Conjugados

21 Nov 2008 . 15:31

.
16:46

Relembrando: método dos gradientes
Idéia básica. Para A simétrica > 0:
O vetor x que resolve Ax=b é o mesmo vetor x que minimiza: F(x) = ½xtAx - btx

Por que ?
Isso ocorre pois grad(F(x)) = 0 , condição necessária para mínimo implica Ax=b.
Além disso, Hessiana = A > 0

.
16:46

Como resolver Min F(x) = ½xtAx - btx ? chutamos um valor inicial: x0 andamos na direção de menor decrescimento naquele ponto: -grad(F(x0)), ou seja: x1 = x0 - s × grad(F(x0)) onde s é o valor do passo! (o quanto andamos nesta direção) .
16:46

Interpretação gráfica

passo direção Adaptado de http://www.dt.fee.unicamp.br/~valente/ia543.html - Prof. Paulo Valente
FEEC - Unicamp

.
16:46

Como achamos o passo ?
Buscamos o s que minimiza F(x + sr) r é a direção oposta ao gradiente: r = -grad(F) = b-Ax s é o passo

Min F(x + sr).
Isso ocorre quando dF/ds = 0.
Fazendo as contas:

.
16:46

Método dos Gradientes - Algoritmo
Dados A, b, max e Erro
1) x(0)=0
2) k = 0
3) r = b - Ax(k)
4) s = rT r/rTAr
5) x(k+1) = x(k) + s r
6) Se ||xk+1-xk||∞/||xk+1||∞ < Erro então faça solução
= x(k+1) e PARE
7) k = k+1
8) Se (k0, para x ≠ 0). A base do método dos
Gradientes Conjugados (CG) é a seguinte propriedade:
Propriedade (Cunha, 2000): É possível escolher n direções linearmente independentes, p1, p2,... pn, e por meio da minimização da função F(x(k) +skp(k)), em cada uma das direções separadamente, construir uma seqüência de aproximações que forneça o mínimo da função F(x) = ½ xTAx – bTx após n passos (n é o número de equações do sistema).

.
16:46

Idéia:
Se A é definida positiva e p1, p2... pn são n direções Aortogonais, então essas direções são LI.
A solução ótima pode ser escrita como combinação linear dessas n (dimensão de A) direções mais a direção b.
No algoritmo anterior, se a cada passos