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.
títuloResumen 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,
página1/4
fecha de publicación13.11.2015
tamaño250.23 Kb.
tipoResumen
m.exam-10.com > Documentos > Resumen
  1   2   3   4

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

      1. TRABAJO DE DIPLOMA



Estudio e Implementación Amigable del método Gradiente Conjugado con el uso de precondicionadores
    1. AUTOR

  1. Lida González Álvarez




    1. TUTORES


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]

  1. La matriz A es no singular () y tiene una solución única dada por .

  2. La matriz A es singular y , entonces existen infinitas soluciones.

  3. La matriz A es singular y , entonces el sistema no tiene solución.

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

  • Método de Jacobi:

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

  • Método de Gauss-Seidel

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 .

  • SOR (Método de sobre relajación sucesiva)

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 .
  1   2   3   4

Añadir el documento a tu blog o sitio web

similar:

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, iconSolucion de sistemas de ecuaciones no lineales

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, iconUnidad 1 Empleo de sistemas numéricos y métodos de conteo

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, iconResumen Los deportistas se ven en la necesidad de mejorar sus marcas...

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, iconBibliografíA 271 prefacio a la edición de 1976 El presente libro...

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, iconResumen la andrología es una ciencia que tuvo gran desarrollo en...

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, iconResumen Elegimos el tema “Pánico en los Adolecentes” debido a que...

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, iconLa biología como ciencia-aplicaciones del método científico

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, iconResumen dentro del área de tratamiento de imágenes existe una gran...

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, iconPrograma ahora
Es un gran paso que este derecho universal se vea cada vez más simplificado, aunque preocupan reportes de que estos números no se...

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, iconComo consecuencia de la evolución de la normativa comunitaria y la...






© 2015
contactos
m.exam-10.com