Resumen la resolución mediante métodos numéricos de aplicaciones cada vez más complejas en el área de la ciencia y la técnica ha traído como consecuencia la necesidad creciente de resolver sistemas de ecuaciones lineales a gran escala,
descargar 250.23 Kb.
|
32 Trabajo publicado en www.ilustrados.com La mayor Comunidad de difusión del conocimiento            Universidad de la Habana Facultad de Matemática y Computación Estudio e Implementación Amigable del método Gradiente Conjugado con el uso de precondicionadores Lic. Isidro Abelló Ugalde Msc. Ángela M. León Mecías. RESUMEN La resolución mediante métodos numéricos de aplicaciones cada vez más complejas en el área de la ciencia y la técnica ha traído como consecuencia la necesidad creciente de resolver sistemas de ecuaciones lineales a gran escala, provenientes de la discretización de los modelos matemáticos de dichos problemas. Con el objetivo de contar con herramientas eficientes y de fácil manipulación por el usuario se desarrolló este trabajo. Se realizó un estudio de los métodos iterativos y se seleccionó el método del gradiente conjugado por ser de gran efectividad en la resolución de sistemas dispersos de grandes dimensiones y además porque la estructura de las matrices que provienen de las aplicaciones, son frecuentemente simétricas y definidas positivas. Como las matrices pueden tener un número de condición elevado, es decir estar mal condicionadas también se tuvo en cuenta el estudio de técnicas para precondicionar los sistemas. Se implementó una aplicación de fácil manipulación, proporcionando una interfaz cómoda a los usuarios, con el objetivo de resolver sistemas de ecuaciones lineales mediante el método “Gradiente Conjugado”[4][10][11], dando la posibilidad de precondicionar el sistema, para lo cual se programaron los precondicionadores de Jacobi y Cholesky Incompleto. Se utilizó para esto el paquete de software Matlab en su versión 6.5. INDICE TRABAJO DE DIPLOMA 1 AUTOR 1 Lida González Álvarez 1 TUTORES 1 AUTOR 1 Lida González Álvarez 1 TUTORES 1 Introducción La necesidad de resolver sistemas de ecuaciones lineales (SEL) aparece en una gran cantidad de problemas científicos. Como ejemplos, podemos citar los SEL que aparecen al resolver ecuaciones diferenciales usando métodos de discretización como son diferencias finitas y elementos finitos. Otras fuentes frecuentes son problemas de aproximación de funciones, problemas inversos, etc. Debido a la frecuencia con que problemas diversos conducen a la resolución de sistemas de ecuaciones lineales de grandes dimensiones y esparcidos, es uno de los objetivos del presente trabajo realizar un estudio de los métodos iterativos para resolver los mismos, en particular el método de “Gradiente Conjugado” [4][10][11], el cual ha demostrado ser de los más eficientes. El desarrollo de una implementación del mismo con una interfaz clara y amigable es otra de nuestras metas así como la introducción de los precondicionadores para el caso de matrices mal condicionadas. Este trabajo consta de 5 capítulos distribuidos de la siguiente manera: En el primero contiene resultados auxiliares sobre la teoría de la existencia de la solución para SEL, así como métodos de solución. El segundo capítulo contempla lo referente a los métodos iterativos para resolver sistemas de ecuaciones lineales. El tercero aborda detalladamente el método de gradiente conjugado y el uso de los precondicionadores. Las especificaciones sobre la aplicación que se realizó se dan en el cuarto capitulo de este trabajo y en el quinto se realiza una discusión de los resultados numéricos obtenidos al correr algunos ejemplos de sistema de ecuaciones lineales provenientes de aplicaciones. Finalmente aparecen las conclusiones y algunas recomendaciones para trabajos futuros. Capítulo 1 Presentación general del problema En una gran cantidad de problemas de investigación científica, al resolver los modelos matemáticos que los simulan, se emplean métodos numéricos de discretización que conducen en algún momento a resolver sistemas de ecuaciones lineales de menor o mayor tamaño. La resolución de un sistema de ecuaciones lineales aparece también en procesos de optimización lineales o no lineales, por ello resulta de gran importancia conocer cuándo un sistema de ecuaciones lineales tiene solución única, o infinitas soluciones, o sencillamente no la tiene. Un sistema de ecuaciones lineales es un conjunto de ecuaciones lineales que podemos escribir de manera general como:  Un sistema así denotado cuenta con “n” ecuaciones y “m” incógnitas, los valores  se llaman coeficientes del sistema, los  términos independientes del sistema y los  incógnitas del sistema. La forma matricial sería: Cuando resolvemos un sistema de ecuaciones lineales podemos distinguir 3 situaciones, [2]
Los métodos que se emplean para resolver sistemas de ecuaciones lineales dependen en gran medida de la estructura de la matriz A, así por ejemplo: diremos que una matriz es cuadrada si  , es decir si tiene igual cantidad de incógnitas y ecuaciones; es simétrica si  y definida positiva si para todo vector  se verifica que  .Los métodos para la resolución de sistemas lineales podemos dividirlos en 2 grupos: los directos y los iterativos. Los métodos directos después de un número finito de pasos conducen a la solución exacta del problema si se evitaran los errores de redondeo, es decir en una aritmética exacta. Estos métodos no son factibles para aplicarlos a sistemas grandes (miles o decenas de miles de ecuaciones) pues requieren un mayor número de operaciones y esto traería mayores errores de redondeo y consecuentemente inestabilidad en la solución, además los requerimientos de almacenamiento serían muy grandes. Consideremos el problema a resolver  no singular y  con N grande, por ejemplo tomemos  y  , [1]. Para el método de eliminación de Gauss, método directo estándar en la solución de sistemas lineales, se estima que se requiere un almacenamiento del orden  , esto sería  para el caso de  y  para el caso de  . El número de operaciones en punto flotante para este mismo método se considera que es de  , así para tendríamos  y  para . Si tenemos una computadora que realiza  operaciones en punto flotante por segundo, considerada rápida para el estándar actual, encontrar la solución del sistema con dimensión tardaría más de 13 años corriendo a tiempo completo, y para uno con dimensión tomaría 291 años. Si el sistema surge por ejemplo, de la discretización de una ecuación diferencial, la matriz A típicamente tiene grandes dimensiones y pocos valores distintos de ceros, para resolver sistemas con estas características no es factible utilizar métodos directos, para ello entonces se utilizan los métodos iterativos a los cuales dedicaré el próximo capítulo. Capítulo 2 Métodos Iterativos para resolver sistemas de ecuaciones lineales Muchos de los grandes problemas que se plantean habitualmente en la industria y en la técnica conducen a tener que resolver sistemas de ecuaciones lineales muy grandes (miles o decenas de miles de ecuaciones e incógnitas), donde las matrices aunque de gran dimensión, tienen pocos componentes distintos de cero, tal es el caso de los problemas que surgen en el análisis y planificación de sistemas electrónicos de generación de transporte de energía , en problemas de contorno para ecuaciones en derivadas parciales, en análisis de estructuras mecánicas mediante elementos finitos, etc. Consideremos el problema a resolver    no singular ,  , N grande.La aplicación en estos casos de métodos directos traería algunas dificultades como: mayores requerimientos de almacenamiento y mayor número de operaciones. Una forma más clásica de resolver estos problemas de grandes dimensiones son los métodos iterativos. 2.1 Métodos Iterativos Métodos Iterativos: Son aquellos que se basan en la construcción de una sucesión de vectores, que bajo ciertas condiciones converja a la solución exacta, es decir partiendo de una aproximación inicial de la solución  , generar una sucesión  que converja a la solución del sistema. El cálculo de estas aproximaciones a la solución se realiza básicamente mediante productos matriz-vector lo cual requiere en muchos casos poco costo computacional.Los métodos iterativos son de programación sencilla pero la convergencia puede ser lenta. Éstos se emplean rara vez para resolver problemas de dimensiones pequeñas ya que el tiempo requerido para lograr una precisión suficiente excede al de las técnicas directas. Los métodos iterativos se clasifican en métodos estacionarios y no estacionarios, los primeros, más antiguos, simples y mejores de entender que los segundos que son a su vez más efectivos. 2.1.1 Métodos Estacionarios De manera general estos pueden expresarse como:   donde será equivalente a . La elección particular de B (matriz de iteración) y c definirán cada método, donde se tiene en cuenta la descomposición de la matriz A como sigue [10] : ,  , y  
Se elige  y  , a la matriz B la llamaremos en esto caso matriz de Jacobi.La expresión general del método quedará entonces:   donde   y  
Para este método  y  y llamaremos a B matriz de Gauss-Seidel.La expresión general del método quedará entonces:    y  mantiene la expresión dada en  y  .
Este método surge con el fin de acelerar la convergencia del método de Gauss-Seidel y para ello se introduce el parámetro  para relajar la recurrencia en cada iteración.Su expresión general tiene la forma:   en este caso  y  , cuando  equivale al método de Gauss-Seidel.De manera general estos métodos estacionarios convergen cuando la matriz del sistema es de diagonal dominante y lo hacen lentamente. 2.1.2 Métodos No Estacionarios Se consideran los más eficaces para resolver sistemas de ecuaciones lineales. Estos métodos difieren de los estacionarios en que las variables contienen información que varía para cada iteración. También se les llama métodos de minimización1. La mayoría de estas técnicas iterativas no estacionarias utilizan procesos de proyección, es decir extraen la solución aproximada del sistema de un subespacio  . Si m es la dimensión de  , en general se imponen m restricciones para extraer tal aproximación que definirán a  como el subespacio de restricciones.Sea una aproximación inicial de la solución de  , con  residuo inicial y  la solución de   Corrigiendo el valor de la aproximación inicial obtendremos la solución exacta del problema, esto quedaría Para encontrar una solución aproximada de  se sigue la siguiente idea:Escoger una sucesión de subespacios  ,  tal que   y aproximar  por  . Para calcular un vector aproximado a partir de  se necesita una base de fácil de computar.Considerando tomaremos el conjunto de vectores base  tal que   Sea  la matriz que tiene como vectores columnas  Entonces cualquier  podrá ser expresado como  , donde  . |
) y tiene una solución única dada por 
.
, entonces existen infinitas soluciones.
, entonces el sistema no tiene solución.Añadir el documento a tu blog o sitio web
