Método del gradiente

Método del gradiente conjugado



Introducción

El método del gradiente conjugado es el método iterativo mas utilizado para resolver grandes sistemas lineales de ecuaciones. El método del gradiente conjugado es efectivo para sistemas de la forma
Ax=b

Estos sistemas de ecuaciones aparecen en la aplicación de técnicas numéricas de gran importancia como por ejemplo los métodos dediferencias finitas o elementos finitos para resolver ecuaciones diferenciales en derivadas parciales. También surgen en la resolución de problemas de ingeniería importantes como el análisis estructural o la teoría de circuitos.

El método del gradiente conjugado es un caso particular de método de descenso. Los métodos de descenso están especialmente indicados para la resolución de sistemas huecos(sistemas lineales cuya matriz de coeficientes tiene un número importante de ceros). Si A es una matriz llena suele ser más aconsejable factorizar la matriz A y después resolver el sistema mediante la técnica de remonte (método directo). El tiempo consumido factorizando la matriz A es más o menos el mismo que el necesario para resolver el sistema por un método iterativo y una vez que la matriz decoeficientes esta factorizada, el sistema se puede resolver rápidamente para múltiples valores de b. Por el contrario si la matriz A es una matriz hueca, en su factorización triangular aparecerán muchos elementos nulos, con el consiguiente desperdicio de operaciones y memoria. Los métodos de descenso, y en general los métodos iterativos, consiguen ahorrar memoria y operaciones operando únicamentesobre los elementos no nulos.

El orden que se ha seguido para la elaboración de estos apuntes es el siguiente: En el apartado 3 se repasan algunas ideas básicas de optimización de funciones de varias variables, con el objetivo de mostrar la equivalencia entre resolver el sistema Ax = b y hallar el mínimo de una función cuadrática cuando A es una matriz simétrica y definida positiva. El interés deestudiar el método del gradiente radica en su utilidad pedagógica para introducir el método del gradiente conjugado y no en su eficacia para resolver sistemas lineales puesto que no puede competir en velocidad de convergencia con este ultimo. Se explica el método del gradiente conjugado demostrando las propiedades más importantes del mismo, exceptuando la demostración de la conjugación de lasdirecciones de descenso que por su longitud se incluye separadamente en un apéndice.


Funciones cuadráticas

Se dice que es una matriz definida positiva. Si además es simétrica se dirá que es una matriz simétrica definida positiva.
En lo sucesivo se denominará función cuadrática a toda función escalar definida sobre un espacio vectorial de dimensión n de la forma:





en donde A esuna matriz cuadrada, x y b son vectores y c es una constante escalar. Se demostrará posteriormente que si A es una matriz simétrica definida positiva, f alcanza un mínimo en la solución de Ax = b.

A lo largo de estos apuntes se ilustraran algunos de los conceptos que vayan surgiendo con el siguiente ejemplo:



En general la solución x se encuentra en el punto de intersección de nhiperplanos, cada uno de ellos de







10
8
6
x2
4 –2x1+4x2=8

2
3x1–2x2=4
–2 0 2 4 6 8

–2 x1

–4






Dimensión n- 1. Para este problema, la solución es x= (4, 4)t. La correspondiente forma cuadrática es


Un dibujo con las curvas de nivel de f aparece en la figura. Debido a que la matriz A esdefinida positiva, la superficie definida por f en lR2 tiene la forma de un paraboloide.


El gradiente de una función de n variables es:




Todo lo anterior implica que la solución de Ax=b se puede calcular buscando el punto x* que minimice f(x).
El hecho de que en f sea un paraboloide permite interpretar geométricamente el que A sea una matriz definida positiva: la función f alcanza un...