Figura 4.1 Vista de la ventana de entrada de datos principal
La ventana de datos adicionales (Figura 4.2) se divide en 2 grupos, uno para la entrada de datos más comunes y otro para datos más avanzados, en el primer grupo se encuentran las condiciones de parada como cantidad de iteraciones o tolerancia (en este caso la habitual para el método que es con respecto a la norma 2 de los residuales  ), la aproximación inicial de la solución y la matriz de precondicionamiento que se desee utilizar. El segundo apartado de datos avanzados contempla la cantidad de pasos del algoritmo que se deben esperar para corregir el valor del residual.
Cada uno de estos parámetros tiene un valor por defecto que se muestra en el edit correspondiente.
Figura 4.2 Vista de la ventana de entrada de datos adicionales
Para la programación de la función se aprovechó el código de la función pcg de matlab, programada de manera bastante eficiente, a ésta se le adicionó como parámetro el valor para la corrección del residual y se introdujo el cambio respectivo a la función resultante. Las funciones iterapp, itermsg e iterchk programadas conjuntamente con la función pcg fueron utilizadas también, la primera para efectuar el producto de la matriz por un vector mediante la función definida para esto, la segunda para dar información sobre el fin de la ejecución del método gradiente conjugado y la última para determinar si se entró la matriz explícitamente o una función para operar con ella.
Para precondicionar el sistema se tuvo en cuenta el precondicionador de Jacobi y el de Cholesky incompleto , para este último se utilizó la función cholinc de matlab a la cual se le pasa como parámetro la matriz y una tolerancia necesaria para la descomposición incompleta de ésta, el precondicionador de Jacobi si se programó para la aplicación.
En la ventana de datos principal como ya se mencionó se ofrecen las opciones de ver la estructura de la matriz así como su número de condición, para esto nos apoyamos en las funciones spy para el primer caso y para el segundo cond o condest según la matriz fuera o no sparse 1
La ventana que muestra la solución alcanzada durante la ejecución del método tiene la opción de ver un gráfico de tolerancia contra cantidad de iteraciones que nos da idea de cual fue el comportamiento del método, esto se logró con la función plot de matlab.
La aplicación se desarrolló apoyándose en la interfaz grafica de usuario (GUI) de la versión 6.5 del paquete de software MatLab (Matrix Laboratory).
MatLab es un programa interactivo para cálculo numérico y tratamiento de datos. Contiene muchas herramientas y utilidades que permiten además diversas funcionalidades, como la presentación gráfica en 2 y 3 dimensiones, contando también con un potente lenguaje de programación.
Los GUI nos permiten crear botones, menús, edit y otros objetos para el intercambio de información con el usuario. La primera vez que se crea o se corre un GUI se crean 2 tipos de ficheros uno de extensión m y uno de extensión fig, el .fig contiene una descripción completa del diseño de la figura y las componentes de la interfaz gráfica (botones, menús, etc) y el .m contiene el conjunto de funciones asociadas a cada objeto que son las que se programan para responder a cada acción que se realice sobre éstos.
CAPITULO 5 Resultados de la Aplicación
Para mostrar algunos resultados se tomará una muestra de sistemas con matrices de características diferentes.
Caso1:
Este primer caso cuenta con una matriz que tiene un número de condición 3.058770*105, por lo que podemos considerarla mal condicionada. La figura 1.1 muestra un esbozo de la estructura de ésta. De los 3844 elementos que tiene solo 1306 son distintos de cero.
Figura 5.1 Esbozo de la estructura de la matriz Caso1
Sin alterar el valor de tolerancia por defecto (10-6) se necesitan 120 iteraciones para alcanzar la convergencia, esto sin utilizar precondicionamiento, utilizando el precondicionador de Jacobi se logra converger en 81 iteraciones y con el de Cholesky Incompleto con tolerancia 1 se necesitan 93 iteraciones (Figuras 5.2 a y b)
 
(a) (b)
Figura 5.2 Gradiente Conjugado con Precondicionamiento de Jacobi (a) y Cholesky Incompleto con tolerancia 1 (b) aplicado a la matriz caso1.
Ambos precondicionadores cumplieron la función de mejorar la condición de la matriz original y con ello lograr acelerar la convergencia en cierta medida, otra clase de precondicionador quizás sería más efectivo.
Caso 2:
La nueva matriz proviene de la discretización por el método de Elementos Finitos de una ecuación de Poisson , utilizando una malla cuadrada de 10x10 nodos.
La ecuación de Poisson puede modelar diferentes procesos, como distribución estacionaria del calor, ecuación estática del movimiento, etc.
La matriz tiene 10000 elementos de los cuales sólo 460 son distintos de cero y un número de condición 69,86337 más pequeño que en el caso anterior (Figura 5.3)
 Figura 5.3 Estructura de la matriz caso2
En este caso la convergencia se alcanza en 27 iteraciones para el caso del sistema precondicionado y sin precondicionar, es decir no mejora con el precondicionamiento.
Caso 3:
Esta matriz se obtiene al aplicar el método de elementos finitos a una ecuación elíptica bidimensional, tomando como elemento de discretización un cuadrilátero de 8 nodos.
Es una matriz sparse de dimensión 133, de sus 17689 elementos 1789 son distintos de cero y su número de condición es 3996 (Figura 5.4).
Figura 5.4 Estructura de la matriz caso 3
El método de gradiente conjugado sin precondicionar aplicado al sistema anterior requiere efectuar 101 iteraciones, reduciéndose a 48 con el precondicionador de Cholesky incompleto y a 28 con el precondicionador de Jacobi (Figura 5.5).
 
(a) (b)
Figura 5.5 Gradiente Conjugado con Precondicionamiento de Jacobi (a) y Cholesky Incompleto con tolerancia 1 (b) aplicado a la matriz caso1.
En este caso es notable la mejoría usando precondicionamiento.
Caso 4:
En este caso la matriz proviene de la aplicación del método de diferencias finitas a un problema de fronteras para una ecuación de Laplace bidimensional con coeficientes discontinuos. La matriz es de dimensión 49, con número de condición bien pequeño 1,5 y de sus 2401 elementos solo 145 son distintos de cero (Ver Figura 5.6).
Figura 5.6 Estructura de la matriz caso 4.
La convergencia se alcanzó para el caso precondicionado en 4 iteraciones e igual número utilizando el precondicionador de Cholesky Incompleto, para el caso del precondicionador de Jacobi disminuye en una iteración. (Ver Figura 5.7)
 
(b)
Figura 5.7 Gradiente Conjugado con precondicionamiento de Jacobi (a) y precondicionamiento de Cholesky Incompleto (b).
CONCLUSIONES
Se estudió con profundidad el método “Gradiente Conjugado” y el uso de los precondicionadores para el caso de matrices mal condicionadas.
Se desarrolló una aplicación con una interfaz fácil de manipular que incluye la mejora de la implementación del Gradiente Conjugado con que cuenta MatLab, la implementación de los precondicionadores de Jacobi y Cholesky Incompleto.
Se realizó una experimentación numérica (4 casos) para comparar los métodos citados, utilizando matrices provenientes de diferentes aplicaciones. Para todos los casos el precondicionador de Jacobi fue más efectivo, en el primero el sistema está muy mal condicionado y se nota la mejora al aplicar precondicionador , aunque quizás otra clase de precondicionador resulte más efectiva; el segundo caso es de menor condición y no hubo mejoras al precondicionar. En el caso 3 es más notable la mejoría en la convergencia al precondicionar el sistema, su número de condición también es bastante elevado aunque no como el caso1. En el último caso la matriz está muy bien condicionada y se alcanza la convergencia en solo 4 pasos, el precondicionador de Jacobi redujo la cantidad de iteraciones a 3, no así con Cholesky incompleto que tardó 4 iteraciones en converger.
RECOMENDACIONES
El trabajo presentado se considera concluido en su primera versión. En una revisión posterior deberán tenerse en cuenta los siguientes aspectos.
Incluir la implementación de los restantes métodos iterativos no estacionarios que aparecen en la ventana principal de la aplicación, agregando si se desea algún otro método que no este aquí incluido.
Incluir otras técnicas de precondicionamiento, de mayor complejidad, podrían ser algunas multinivel.
Ampliar la experimentación numérica.
BIBLIOGRAFÍA
Bunse-Gerstner A, A short introduction to iterative methods for large linear systems, Zentrum fuer Technomathematik, Fachbereich Mathematik/Informatik, Universitaet Bremen, Germany, 2003.
de la Fuente O´Connor José L., Tecnologías Computacionales para sistemas de ecuaciones, optimización lineal y entera, Editorial Reverté, 1993.Duff, S.I.; Erisman, A.M. and Reid J.K. Direct Methods for Sparse. Matrices. Ed. Oxford Science publications. 1986.
Golub Gene H., Van Loan Charles F., Matrix Computations second edition , The Johns Hopkins University Press, Baltimore and London, 1990.
Hestenes Magnus R. and Eduard Stiefel, Methods of Conjugate Gradients for Solving Linear Systems, J. Res. Natl. Bur. Stand.49,409-436, 1952.
Jones Mark T, An Improve Incomplete Cholesky Factorization, Argonne National Laboratory, 1992.
Latsis Symposium, Iterative Solvers for Large Linear Systems, ETH Zurich, 2002.
Lawson, Terry. Algebra Linear.Ed. Edgard-Blücher LTDA. 1996.
MatLab, The Language of Technical Computing Versión 6.5
Meurant Gérard, Numerical Experiments with Algebraic Multilevel Preconditioners, Electronic Transactions on Numerical Analysis, Volume 12, 2001.
Saad Yousef, Iterative Methods for Sparse Linear Systems, Second edition, Copyright , 2000.
Shewchuk Jonathan R, An Introduction to the Conjugate Gradient Method Without the Agonizing Pain, School of Computer Science Carnegie Mellon University, 1994.
Datos del Autor
Licenciada en Ciencia de la Computación. Universidad de la Habana, 2003
Profesor Instructor de la Universidad de las Ciencias Informáticas.
Email : lida@uci.cu
|
de la ecuación 
es el vector para el cual la forma cuadrática 
alcanza su mínimo, cuyo valor es: 
.
es un valor propio de A si y sólo si 
y éste se define como sigue:
una matriz cuadrada de dimensión N , 
, es un valor propio de A si existe 
no nulo , tal que :
