MEtodos De Gradiente

M´todos de gradiente. Precondicionadores
e
Dami´n Ginestar Peir´
a
o
Departamento de Matem´tica Aplicada
a
Universidad Polit´cnica de Valencia
e

Curso 2011-2012

(UPV)

M´todos de gradiente. Precondicionadores
e

Curso 2011-2012

1 / 24

´
Indice

1

M´todo de descenso r´pido
e
a

2

M´todo del gradiente conjugado
e

3

Precondicionadores
Introducci´n
oPrecondicionadores cl´sicos
a

(UPV)

M´todos de gradiente. Precondicionadores
e

Curso 2011-2012

2 / 24

M´todo de descenso r´pido
e
a

Resolver Ax = b, con A sim´trica y definida positiva (SPD).
e
Definimos la funci´n cuadr´tica
o
a

φ Rn → R

1
1
φ(y ) = (y − x )T A(y − x ) = e T Ae .
2
2
Se tiene φ(y ) ≥ 0 ∀y = 0 ( definici´n de matriz SPD).
o
Error e = y − x .Teorema
La soluci´n del sistema Ax = b es el m´
o
ınimo de la funci´n φ(y ).
o

(UPV)

M´todos de gradiente. Precondicionadores
e

Curso 2011-2012

3 / 24

M´todo de descenso r´pido
e
a

φ(y ) = 1 (y − x )T A(y − x ) = 1 e T Ae
2
2
φ (yk ) = constant representa un hiperelipsoide en un espacio de
dimensi´n n.
o
El centro geom´trico es la soluci´n x del sistema lineal (m´e
o
ınimo).
Construir una sucesi´n {yk } tal que limk →∞ yk = x .
o
yk +1 = yk + αk pk
Hace falta determinar la direcci´n pk y α.
o

(UPV)

M´todos de gradiente. Precondicionadores
e

Curso 2011-2012

4 / 24

M´todo de descenso r´pido
e
a
Este m´todo construye una sucesi´n que va hacia el centro del
e
o
hiperelipsoide en la direcci´n del gradiente.
o
El gradiente de φ enel punto yk es
φ(yk ) =

1T
e Aek =
2k

1T
1
T
y Ayk − yk b + x T x
2k
2

= Ayk − b = −rk

Como la direcci´n del vector gradiente es hacia fuera, la direcci´n
o
o
buscada coincide con el residuo rk en la actual aproximaci´n.
o
En consecuencia la nueva aproximaci´n es
o
yk +1 = yk + αk rk
donde αk es una constante a determinar. ¿C´mo? Minimizando φ(y )
o
en la direcci´nbuscada rk .
o
Es decir, nuestro αk es la soluci´n
o
αk = argminβ φ(yk + β rk )
(UPV)

M´todos de gradiente. Precondicionadores
e

Curso 2011-2012

5 / 24

M´todo de descenso r´pido
e
a

Desarrollando la funci´n φ(yk + β rk ) se tiene un polinomio de segundo
o
grado en la variable β .
φ(yk + β rk ) = (yk + β rk − x )T A(yk + β rk − x )
= (yk + β rk − x )T (Ayk + β Ark − b)
=(yk + β rk − x )T (β Ark − rk )
= (β rk − ek )T (β Ark − rk )
T
T
T
= β 2 rk Ark − β rk rk + ek Ark + x T rk
T
T
= β 2 rk Ark − 2β rk rk + const.

(UPV)

M´todos de gradiente. Precondicionadores
e

Curso 2011-2012

6 / 24

M´todo de descenso r´pido
e
a

T
ınimo de φ se alcanza cuando
Como rk Ark > 0 el m´

αk ≡ β =

T
rk rk
T
rk Ark

Otra forma:
∂φ
Resolver ∂β= 0.

(UPV)

M´todos de gradiente. Precondicionadores
e

Curso 2011-2012

7 / 24

M´todo de descenso r´pido
e
a
La k + 1 iteraci´n se puede representar como
o
rk
αk
yk +1

= b − Axk
T
rk rk
=T
rk Ark
= yk + αk rk

Notar que el coste computacional es principalmente dos productos
matriz-vector.
De yk +1 = yk + αk rk se sigue que
rk +1 = b − Axk +1 = b − Axk − Aαk rk =rk − αk Ark ,
Los residuos consecutivos rk +1 , rk son ortogonales (demostraci´n:
o
Ejercicio).
El error ek +1 es A ortogonal a la direcci´n rk . (demostraci´n:
o
o
Ejercicio).
(UPV)

M´todos de gradiente. Precondicionadores
e

Curso 2011-2012

8 / 24

M´todo de descenso r´pido
e
a

Algoritmo: Descenso r´pido
a
Input: y0 , A, b, kmax , tol
r0 = b − Ay0 , k = 0
while rk >tol b and k < kmax do
1
2
3
4
5

z = Ark
r T rk
αk = k
z T rk
yk +1 = yk + αk rk
rk +1 = rk − αk z
k =k +1

end while

(UPV)

M´todos de gradiente. Precondicionadores
e

Curso 2011-2012

9 / 24

M´todo de descenso r´pido
e
a
Lema
Sea A sim´trica definida positiva y sean 0 < λn ≤ · · · ≤ λ2 ≤ λ1 sus
e
valores propios. Si P (t ) es un polinomio real, entonces
||P...