Método iterativo para solução de sistemas lineares
Gradientes e Gradientes Conjugados
Silvia Maria Pereira Grandi dos Santos
USP - São Carlos/SP
Outubro 2008
Roteiro
I
Motivação;
I
Processos de Relaxação;
I
Estudo do caso f (x) = 12 xT Ax − bT x + x;
I
Método dos Gradientes;
I
Direção Conjugada;
I
Método dos Gradientes Conjugados;
I
Exemplo resolvido.
Motivação
Considere o sistema linear Ax = b. Deseja-se encontrar a solução x desse
sistema.
Muitas vezes, usar Métodos Exatos para encontrar a solução desse sistema é
tão eficiente quanto usar Métodos Iterativos, mas a situação pode se
complicar quando usamos Métodos Exatos em sistemas cuja matriz dos
coeficientes, A, é uma matriz esparsa (cheia de zeros).
O Método dos Gradientes é utilizado quando a matriz A é simétrica definida
positiva.
Processos de Relaxação
I
Dado um sistema Ax = b e um ponto para a aproximação inicial x(0) da
solução do sistema, queremos reduzir o resíduo dado por
r(0) = b − Ax(0)
até que este resíduo seja nulo.
I
Para que o resíduo diminua, tomamos uma direção v e corrigimos x(0)
nesta direção, ou seja,
x(1) = x(0) + λ~v de forma que r(1) = b − Ax(1) < r(0) .
I
Dessa forma, construimos uma sequência {x(k) } que converge para a
solução do sistema Ax = b, pois estamos considerando que o resíduo
diminua em cada passo do processo iterativo, ou seja,
r(k+1) < r(k) .
I
Quando k → ∞ temos r(k) → 0 e, dessa forma, Ax(k) → b e k(k) é uma
aproximação para a solução do sitema dado Ax = b.
Estudo de um caso específico
1
Para o estudo da função f (x) = xT Ax − bT x + c consideremos as seguintes
2
notações:
I
n
xT y representa o produto escalar
  de x com y no espaço R , assim
y1
n

£
¤ y2 
 X
T
x y = x1 x2 · · · xn  .  =
xi yi
 .. 
i=1
yn
I
Se x e y são vetores ortogonais, então xT y = 0
I
A é uma matriz definida positiva se, para todo vetor x não nulo, tem-se
xT Ax > 0
I
Lembre-se que (AB)T = BT AT .
Estudo de um caso específico
1
Considere f : Rn → R em que f (x) = xT Ax − bT x + c, A é uma matrix
2
n × n, b e x são vetores n × 1 e c uma constante.
·
¸
·
¸
3 2
2
Sejam A =
,b=
e c = 0. Nestas condições, o gráfico da
2 6
−8
função f pode ser visto na Figura 6.
450
400
350
300
250
200
150
100
50
0
8
6
4
2
0
-2
-4
-6
-8 -8
-6
-4
-2
0
2
4
6
8
O ponto de mínimo de f (x) neste caso é o ponto (2, −2).
Estudo de um caso específico
É possível mostrar que o ponto de mínimo de f (x) é a solução do sistema
Ax = b. De fato,
sabemos que o ponto de mínimo de f (x) é um ponto crítico, ou seja,
0
f (x) = ∇f (x) = 0.
n
n
X
1X
Mas f : Rn → R; f (x) =
aij xi xj −
bi xi + c. Assim
2
i,j=1
i=1


∂

 ∂x1 f (x)  
a11 x1 + a12 x2 + · · · a1n xn − b1
 ∂



a21 x1 + a22 x2 + · · · a2n xn − b2 
f (x)  


=
∂x2
∇f (x) = 

 = Ax − b
..


.


.


..


an1 x1 + an2 x2 + · · · ann xn − bn
 ∂

f (x)
∂xn
Fazendo ∇f (x) = 0 temos Ax − b = 0 ⇒ Ax = b, ou seja,
o ponto crítico de f (x) é o ponto x tal que Ax = b. Nos resta saber se
x; Ax = b é de mínimo ou de máximo.
Estudo de um caso específico
Sabemos que um ponto x é ponto de mínimo de f : Rn → R se J(f ) é
positiva definida.
 2

∂ 2 f (x)
∂ f (x) ∂ 2 f (x)
···
 ∂x2
∂x1 ∂x2
∂x1 ∂xn 
 2 1

2
 ∂ f (x) ∂ f (x)
∂ 2 f (x) 


···

∂x2 ∂xn 
∂x22
Como J =  ∂x2 ∂x1



..


.


2
 ∂ 2 f (x) ∂ 2 f (x)
∂ f (x) 
···
∂xn ∂x1 ∂xn ∂x2
∂xn2


a11 a12 · · · a1n
 a21 a22 · · · a2n 


= .
=A
 ..

an1
an2
···
ann
e A é uma matriz positiva definida por hipótese, segue o ponto x tal que
Ax = b é ponto de mínimo de f (x). Dessa forma, se encontrarmos o ponto
de mínimo de f (x) encontramos a solução do sistema Ax = b.
Estudo de um caso específico
Sabemos que ∇f (x), num dado ponto x, aponta a direção de maior
crescimento da função f .
Método dos Gradientes
Dada uma aproximação inicial x(0) para a solução do sistema Ax = b, é seria
natural pensarmos em tomar a direção oposta a ∇f (x) para a correção de
x(0) , pois −∇f (x) aponta na direção que f decresce mais rapidamente (o
ponto de mínimo de f é a solução do sistema Ax = b).
Pelos cálculos feitos anteriormente, sabemos que
−∇f (x(i) ) = b − Ax(i) = r(i) .
Dessa forma, tomando x(0) = (−2, −2), sabemos em qual direção caminhar,
mas não sabemos o quanto caminhar.
Método dos Gradientes
Método dos Gradientes
Como x(1) = x(0) + λr(0) e λ minimiza f (x(1) ) quando a derivada direcional
∂f (x(1) )
= 0.
∂λ
Mas
³ 0
´T
∂f (x(1) ) ³ 0 (1) ´T ∂x(1)
= f (x )
= f (x(1) ) r(0) .
∂λ
∂λ
³ 0
´T
Igualando essa expressão a zero temos f (x(1) ) r(0) = 0 que nos sugere
0
que λ será escolhido de forma que r(0) e f (x(1) ) sejam ortogonais.
0
Para determinar λ usamos o fato de f (x(1) = −r(1) . Dessa forma, teremos
Método dos Gradientes
¡ (1) ¢T (0)
r
r =0
Substituindo r(1) nessa expressão
¡
¢T
b − Ax(1) r(0) = 0
Como x(1) = x(0) + λr(0) temos
¡
¡
¢¢T (0)
b − A x(0) + λr(0)
r =0
¡
¢T
¡
¢T
b − Ax(0) r(0) − λ Ar(0) r(0) = 0
¢T
¡
¢T
¡
b − Ax(0) r(0) = λ Ar(0) r(0)
¡ ¢T
¡ (0) ¢T (0)
r = λ r(0) Ar(0)
r
Logo
¡ (0) ¢T (0)
r
r
λ = ¡ ¢T
(0)
r
Ar(0)
Método dos Gradientes
Colocando todas essas informações juntas, temos
dada uma aproximação inicial x(0) para a solução do sistema Ax = b, o
processo iterativo, conhecido como Método dos Gradientes, é dado
por
I
r(i) = b − Ax(i)
(i)
¡ (0) ¢T (0)
r
r
= ¡ ¢T
(0)
r
Ar(0)
I
λ
I
x(i+1) = x(i) + λ(i) r(i)
Método dos Gradientes
Intuitivamente, temos
Método dos Gradientes
Exemplo: Usando
uma solução
· o Método
¸
·dos
¸ Gradientes,·obtenha
¸
aproximada para
4 1
5
0
x=
com x(0) =
e ² = 10−1 .
1 3
4
0
Abrir arquivo Exemplo1.xls e arquivo Exemplo1.mws
Método dos Gradientes Conjugados
Método dos Gradientes Conjugados
Método dos Gradientes Conjugados
É possível, no Método dos Gradientes, uma direção que está sendo adotada
na iteração i ter sido usada em iterações anteriores, como pode ser visto na
Figura 15.
Para evitar que se tome várias vezes uma mesma direção r(i) para a correção
de x(i) , o Método dos Gradientes Conjugados propõe uma modificação no
Método dos Gradientes.
O Método dos Gradientes Conjugados sugere que, dada uma aproximação
inicial x(0) para o sistema n × n, Ax = b, tomemos um conjunto de direções
conjugadas {d0 , d1 , · · · , dn−1 } e em até n iterações, teremos encontrado uma
aproximação satisfatória para a solução do sistema.
Dois vetores x e y são conjugados se xT Ay = yT Ax = 0.
Método dos Gradientes Conjugados
Método dos Gradientes Conjugados
Dado x(0) , faça d0 = r0 = b − Ax
x(1) = x(0) + λ(0) d(0) .
e
x(1)
será obtido fazendo
Para obter o tamanho do passo λ(0) , procedemos como no caso do Método
dos
¡ Gradientes:
¢
¢T dx(1)
d f (x(1) )
0 ¡
= f x(1)
= −r(1)T d(0) .
dλ
dλ
¡ ¢
Como queremos que λ minimize f x(1) , fazemos
¡
¢
r(1)T d(0) = 0 → d(0)T r(1) = 0 → d(0)T b − Ax(1) = 0
Substituindo x(1) nessa expressão concluimos que
r(0)T r(0)
λ(0) = (0)T (0)
d Ad
Método dos Gradientes Conjugados
Para que r(1) = r(0) − λ(0) Ad(0) seja ortogonal à nova direção
d(1) = r(1) + β (1) d(0) é preciso escolher um valor para β (1) conveniente.
Assim
µ
r
(1)T (1)
d
=0
→
r
(0)
r(0)T r(0)
− (0)T (0) Ad(0)
d Ad
¶T
¡
¢
r(1) + β (1) d(0) = 0
r(0)T r(0)
r(0)T r(0)
r(0)T r(1) +β (1) r(0)T d(0) −d(0)T A (0)T (0) r(1) −β (1) d(0)T A (0)T (0) d(0) =
d Ad
d Ad
0
Simplificando temos β (1) = −
d(0)T Ar1
r(1)T Ad0
=
−
d(0)T Ad(0)
d(0)T Ad(0)
Assim a nova direção é dada por d(1) = r(1) + β (1) d(0)
Método dos Gradientes Conjugados
Podemos resumir o Método dos Gradientes Conjugados por, dado x(0) inicial
I
d(0) = r(0) = b − Ax(0)
I
Para i = 0, 1, ...
r(i)T r(i)
d(i)T Ad(i)
I
λ(i) =
I
x(i+1) = x(i) + λ(i) d(i)
I
r(i+1) = r(i) − λ(i) Ad(i)
I
β (i+1) = −
I
d(i+1) = r(i+1) + β (i+1) d(i)
r(i+1)T Ad(i)
d(i)T Ad(i)
Método dos Gradientes Conjugados
Podemos simplificar um pouco mais a expressão de β (i+1) considerando
r(i+1) = r(i) − λ(i) Ad(i) , pois dessa forma temos
Ad(i) = −
¢
1 ¡ (i+1)
(i)
r
−
r
λ(i)
Fazendo r(i+1) Ad(i) e d(i)T Ad(i) temos
¢
¢
1 ¡
1 ¡
r(i+1)T Ad(i) = − (i) r(i+1)T r(i+1) − r(i+1)T r(i) = − (i) r(i+1)T r(i+1)
λ
λ
e
¢
¢
1 ¡
1 ¡
d(i)T Ad(i) = − (i) d(i)T r(i+1) − d(i)T r(i) = − (i) −d(i)T r(i) =
λ
λ
1 (i)T (i)
d
r
λ(i)
Método dos Gradientes Conjugados
Substituindo
d(i)T Ad(i)
1
= (i) d(i)T r(i)
λ
β (i+1) = −
−
1 ¡ (i+1)T (i+1) ¢
r
r
λ(i)
em β (i+1) temos
r(i+1)T Ad(i) = −
e
1 ¡ (i+1)T (i+1) ¢
r
r
r(i+1)T r(i+1)
r(i+1)T r(i+1)
λ(i)
=
=
(i)T
(i)
1 (i)T (i)
d r
r(i)T r(i)
d r
(i)
λ
Método dos Gradientes Conjugados
Dessa forma, dado x(0) uma aproximação inicial do sistema Ax = b, o
Método dos Gradientes Conjugados é dado por
I
d(0) = r(0) = b − Ax(0)
I
Para i = 0, 1, ...
r(i)T r(i)
d(i)T Ad(i)
I
λ(i) =
I
x(i+1) = x(i) + λ(i) d(i)
I
r(i+1) = r(i) − λ(i) Ad(i)
I
β (i+1) =
I
d(i+1) = r(i+1) + β (i+1) d(i)
r(i+1)T r(i+1)
r(i)T r(i)
Método dos Gradientes Conjugados
Método dos Gradientes Conjugados
Exemplo:
uma solução
·
¸ Obtenha
· ¸
· ¸ aproximada para o sistema
4 1
5
0
x=
com x(0) =
e ² = 10−1 .
1 3
4
0
Abrir arquivo Exemplo2.xls e arquivo Exemplo2.mws
Referências
I
Shewchuk, J R. An Introduction to the Conjugate Gradient Method
Without the Agonizing Pain Edition 1 14 . School of Computer Science
Carnegie Mellon University Pittsburgh. PA, 1994.
I
Franco, N B. Cálculo Numérico. Editora: Pearson / Prentice Hal. 2006.
I
Todas as figuras (exceto a primeira) foram extraídas de Shewchuk,
1994.