mateasdfghjklñ

M´todo de descenso m´s r´pido y del gradiente
e
a a
conjugado para la resoluci´n de sistemas lineales
o
C´lculo Num´rico (A-F-O)/Elementos de C´lculo Num´rico (M)
a
e
a
e
SegundoCuatrimestre 2012
Dado el sistema Ax = b con A matriz sim´trica y definida positiva, sabemos
e
que (ver Kincaid, An´lisis Num´rico, pag. 210 en adelante) resolver este sistema
a
e
es equivalente aminimizar la forma cuadr´tica:
a
q(x) = x, Ax − 2 x, b .
El m´todo del descenso m´s r´pido consiste en dar una sucesi´n de valores
e
a a
o
xk tal que q(xk+1 ) ≤ q(xk ) y que la igualdad s´lo seproduzca en alg´n caso
o
u
especial. La idea gen´rica es obtener xk+1 a partir de xk y de otro vector vk
e
que puede ya estar dado o que se lo vaya construyendo durante la evoluci´n del
o
m´todo. Loque se busca es minimizar la forma cuadr´tica q(x) si nos movemos
e
a
desde x en una direcci´n v, es decir que se minimiza la funci´n de una variable
o
o
q(x + tv) en la variable t; tenemos queel m´
ınimo sobre este rayo se produce si
ˆ
t = v,b−Ax y por lo tanto
v,Av
ˆ
q(x + tv) = q(x) − v, b − Ax

2

v, Av

A partir de esto, se genera la sucesi´n
o
xk+1 = xk + tk vk
donde tk= vk , b − Axk vk , Avk y la sucesi´n vk es una conveniente (esta
o
elecci´n es la que da origen a los distintos m´todos).
o
e
Descenso m´s r´pido El m´todo del descenso m´s r´pido se definetomando
a a
e
a a
vk = − q(xk ) (o un m´ltiplo positivo de ´l). La practicidad del m´todo reside
u
e
e
en que el residuo rk = b − Axk apunta en la direcci´n de − q(xk ) (comproo
rk
o
barlo), porlo tanto tomamos vk = rk para generar la sucesi´n aproximante
xk . k
Direcci´n conjugada La idea es considerar una base {u1 , · · · , un } ortogoo
nal seg´n el producto interno u, v A = u, Av ,entonces vale que la secuencia
u
dada por
xk = xk−1 +

b − Axk−1 , uk
uk , Auk

1 ≤ k ≤ n,

arrancando desde un punto x0 cualquiera. Una gran ventaja de este m´todo
e
es que, en teor´ en n...