gradiente
e
e
Dami´n Ginestar Peir´
a
o
Departamento de Matem´tica Aplicada
a
Universidad Polit´cnica de Valencia
e
Curso 2012-2013
(UPV)
M´todos de gradiente. M´todos de Krylov
e
e
Curso 2012-2013
1 / 48
´
Indice
1
M´todo de descenso r´pido
e
a
2
M´todo del gradiente conjugado
e
3
M´todos de Krylov
e
M´todo delresiduo conjugado
e
m´todo GMRES
e
(UPV)
M´todos de gradiente. M´todos de Krylov
e
e
Curso 2012-2013
2 / 48
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. M´todos de Krylov
e
e
Curso 2012-2013
3 / 48
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. M´todos de Krylov
e
e
Curso 2012-2013
4 / 48
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φ en el punto yk es
φ(yk ) =
1 T
e Aek =
2 k
1 T
1
T
y Ayk − yk b + x T x
2 k
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 aproximaci´n actual.
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 ladirecci´n buscada rk .
o
Es decir, nuestro αk es la soluci´n
o
αk = argminβ φ(yk + βrk )
(UPV)
M´todos de gradiente. M´todos de Krylov
e
e
Curso 2012-2013
5 / 48
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. M´todos de Krylov
e
e
Curso 2012-2013
6 / 48
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. M´todos de Krylov
e
e
Curso 2012-2013
7 / 48
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. M´todos de Krylov
e
e
Curso 2012-2013
8 / 48
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 band 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. M´todos de Krylov
e
e
Curso 2012-2013
9 / 48
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(A)x||A ≤...
Regístrate para leer el documento completo.