Una introducción a los métodos iterativos de Krylov y precondicionadores

Tesis

Resumen *

En muchas aplicaciones de la ingeniería y problemas científicos, necesitamos resolver diferentes sistemas de ecuaciones diferenciales que se resuelven numéricamente discretizando por métodos con malla como ser diferencias finitas (MDF), elementos finitos (MEF), volúmenes finitos (MVF). Estos procesos de discretización nos llevan, en general, a resolver un sistema algebraico de ecuaciones lineales de la forma:Ax = b, donde A es una matriz real inversible n×n, no simétrica y rala (sparse), x es el vector de incógnitase e y es el vector de coeficientes.Estos sistemas pueden ser muy grandes, como por ejemplo en problemas de mecánica de los fluidos, donde cada ecuación describe cómo el valor de un parámetro desconocido (como ser la velocidad, presión, energía cinética turbulenta del fluido) depende de valores vecinos también desconocidos. Las incógnitas surgen de un mallado del dominio de nuestro problema, y el número de elementos del mallado determinan la dimensión del sistema lineal en cuestión. Cada elemento de la malla está asociado con uno o más incógnitas que describen cómo estas incógnitas están relacionadas con otras incógnitas vecinas. Estas relaciones están determinadas por el modelo físico en estudio. Para simular modelos realistas, es necesario tener muchos elementos y como consecuencia muchas ecuaciones a resolver en poco tiempo (real time). Una propiedad remarcable de estos sistemas lineales es que, en las aplicaciones, cada ecuación contiene sólo unas pocas incógnitas, y por ende, la matriz de coeficientes tiene muchos ceros (matrices sparse). En general, la cantidad de elementos no nulos puede llegar a ser un número menor al uno por ciento de los coeficientes de A. Esta propiedad será de gran importancia para la eficiencia de los métodos iterativos.Para resolver numéricamente estos sistemas lineales, existen actualmente dos grandes categorías de métodos: los métodos directos y los métodos iterativos.Los métodos directos obtienen la solución, salvo errores de redondeo, en un número finito de pasos y son apropiados para sistemas pequeños y densos pero en general, necesitamos almacenar las n^2 entradas de la matriz y realizar (2/3)n^3 operaciones aritméticas aproximadamente. Los métodos iterativos en cambio, producen una sucesión de soluciones aproximadas a la solución de nuestro sistema, con un costo computacional usualmente del orden n por iteración. Más aún, el proceso iterativo se puede suspender cuando se ha obtenido una precisión deseada o cuando se ha realizado un cierto número de iteraciones (criterios de detención). Por estas razones, este tipo de métodos es apropiado para resolver grandes sistemas lineales y con matrices sparse.A su vez, dentro de los métodos iterativos existe un conjunto de métodos que son considerados como las técnicas iterativas más importantes para resolver grandes sistemas lineales, las cuales están basados en procesos de proyección. Un proceso de proyección consiste en encontrar una solución aproximada dentro de un cierto subespacio de R^n que denominamos "subespacio de busqueda" de dimension m << n al cual pertenece la solucion aproximada. En general, m restricciones deben ser impuestas para poder obtener una solucion aproximada. Una forma de describir estas restricciones es imponer m condiciones independientes, usualmente que el vector b-Ax este restringido a ser ortogonal a m vectores linealmente independientes. Esto define otro subespacio de dimension m denominado "subespacio de restricciones".La eficiencia y robutez de las técnicas iterativas son mejoradas utilizando técnicas de precondicionamiento. Precondicionar es simplemente una forma de transformar el sistema original por otro que tiene la misma solución, pero el cual es probablemente más fácil de resolver con un método iterativo. No existen teorías generales sobre cómo precondicionar un sistema, salvo técnicas específicas que muchas veces dependen de la naturaleza del problema. Información suministrada por el agente en SIGEVA