Gradiante

´
Universidad Politecnica de Madrid
´
Escuela Tecnica Superior de Ingenieros de Minas
´
´
´
Departamento de Matematica Aplicada y Metodos Informaticos

x0

r1

x1
x2= x* d1
*
d1

r0
f(x)=cte.

Resoluci´n de sistemas lineales de ecuaciones:
o
M´todo del gradiente conjugado
e
Ultano Kindel´n
a

´
Indice

1. Introducci´n
o

6

2. Notaci´n
o

7

3. Funcionescuadr´ticas
a

7

4. El m´todo del gradiente
e

11

5. El m´todo del gradiente conjugado
e

16

5.1. Introducci´n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
o

16

5.2. Determinaci´n de la direcci´n de descenso . . . . . . . . . . . . . . . . . .
o
o

16

5.3. Propiedades del m´todo del gradiente conjugado . . . . . . . . . . . . . .
e

205.4. Algoritmo del m´todo del gradiente conjugado . . . . . . . . . . . . . . .
e

21

A. Demostraci´n de la conjugaci´n de las direcciones de descenso
o
o

25

B. Condicionamiento de un sistema

27

´
Indice de Figuras

1.
2.
3.
4.

5.

6.

7.
8.

Representaci´n geom´trica de un sistema lineal de dos ecuaciones. La
o
e
soluci´n es el punto de intersecci´n deambas rectas. . . . . . . . . . . . .
o
o

8

Gr´fica de la forma cuadr´tica (5). El punto en donde esta funci´n
a
a
o
alcanza su valor m´
ınimo es la soluci´n de Ax = b. . . . . . . . . . . . . .
o

9

Curvas de nivel de la forma cuadr´tica (5). A cada elipse le corresponde
a
un valor constante de f . . . . . . . . . . . . . . . . . . . . . . . . . . . .

9

Gradiente de laforma cuadr´tica (5). Para cada x el gradiente apunta
a
en la direcci´n de m´ximo crecimiento de f y es ortogonal a la curva
o
a
de nivel que pasa por x . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

10

(a) Forma cuadr´tica con matriz definida positiva; (b) con matriz dea
finida negativa; (c) con matriz singular (y positiva), en este caso una
l´
ınea atraviesa el fondo delvalle (no hay un unico m´
´
ınimo); (d) con
una matriz indefinida; como en este caso el punto cr´
ıtico es un punto
de silla, los m´todos de descenso no funcionar´n correctamente. En die
a
mensi´n superior a dos, las matrices singulares tambi´n pueden tener
o
e
puntos de silla. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

11

El m´todo del gradiente: (a) Se comienzaen el punto (3, −1)t y se reae
liza la primera iteraci´n siguiendo la direcci´n de m´ximo descenso. (b)
o
o
a
Hay que encontrar el punto de lR2 en el que la curva (par´bola) interseca
ci´n de las dos superficies alcanza su m´
o
ınimo absoluto. (c) La par´bola
a
intersecci´n de las dos superficies. (d) El gradiente en el punto donde
o
se alcanza el m´
ınimo es ortogonal al gradiente enel punto obtenido en
la iteraci´n anterior. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
o

13

Dibujo de las dos primeras iteraciones del m´todo del gradiente sobre
e
t
1t
las curvas de nivel de la funci´n f (x) = 2 x Ax − b x. . . . . . . . . . . .
o

17

Dibujo de las dos primeras iteraciones del m´todo del gradiente conjue
t
gado sobre las curvas de nivel de lafunci´n f (x) = 1 xt Ax − b x. En
o
2
dos iteraciones se alcanza la soluci´n exacta del sistema Ax = b. . . . . .
o

18

´
Indice de Algoritmos

1.

Algoritmo que resuelve el sistema Ax = b mediante el m´todo del grae
diente. Versi´n preliminar. . . . . . . . . . . . . . . . . . . . . . . . . . . .
o

14

Algoritmo que resuelve el sistema Ax = b mediante el m´todo del graediente. Versi´n m´s eficiente con “memoria”. . . . . . . . . . . . . . . . .
o
a

15

Algoritmo que resuelve el sistema Ax = b mediante el m´todo del grae
diente. Versi´n m´s eficiente sin “memoria”. . . . . . . . . . . . . . . . . .
o
a

16

4.

Estructura general de los algoritmos de los m´todos de descenso. . . . . .
e

16

5.

Algoritmo que resuelve el sistema Ax = b mediante...