matrices y grafos

332 Lapso 2011-2

Especialista: Jesús Espinal Ingeniería de Sistemas Evaluador: Carmen Velásquez

UNIVERSIDAD NACIONAL ABIERTA AREA DE INGENIERÍA CARRERA DE INGENIERÍA DE SISTEMAS

TRABAJO PRACTICO: 1 ASIGNATURA: GRAFOS Y MATRICES CÓDIGO: 332 FECHA DE ENTREGA DE LAS ESPECIFICACIONES AL ESTUDIANTE: Adjunto a Primera Prueba Parcial.

FECHA DE DEVOLUCIÓN DEL INFORME POR EL ESTUDIANTE: Adjunto a Prueba Integral.

NOMBRE DEL ESTUDIANTE: Tirso R. FERNÁNDEZ M. CÉDULA DE IDENTIDAD: V-6.122.911 CORREO ELECTRÓNICO: [email protected] CENTRO LOCAL: Metropolitano (01) UNIDAD DE APOYO: San Antonio (04) CÓDIGO DE CARRERA: 236 NÚMERO DE ORIGINALES: 66

FIRMA DEL ESTUDIANTE:

LAPSO 2011-2

RESULTADOS DE CORRECCIÓN:

OBJ N°: 6 8 9 10

0:NL; 1:L

UNIVERSIDAD NACIONAL ABIERTA GRAFOS Y MATRICES (332)

Tirso Rubén FERNÁNDEZ C.I. V-6.122.911

Carrizal, 23 de Marzo del 2012

Trabajo Práctico: Métodos Numéricos Iterativos TABLA DE CONTENIDO

Universidad Nacional Abierta, GRAFOS Y MATRICES Tirso Rubén FERNÁNDEZ, V-6.122.911 3-66

TABLA DE CONTENIDO

1.1. ÍNDICE DE CONTENIDO

TABLA DE CONTENIDO.............................................................................................................................................3

1.1. Índice de Contenido................................................................................................................................3

1.2. Índice de Ilustraciones y Tablas .............................................................................................................5 1.2.1 Figuras ..........................................................................................................................................................5 1.2.2 Tablas ...........................................................................................................................................................5

2. RESUMEN ...........................................................................................................................................................7 3. INTRODUCCIÓN................................................................................................................................................7

3.1. DEFINICIÓN CONTEXTUAL ........................................................................................................................7 4. DESARROLLO TEÓRICO...................................................................................................................................10

4.1. OBJETIVO 6: Métodos de Jacobi y Gauss – Seidel..............................................................................10 4.1.1 Sistema de Ecuaciones Asociado con el Problema. ............................................................................10 4.1.2 Breve explicación Algoritmos de Jacobi y Gauss- Seidel.....................................................................11 4.1.3 Algoritmo JACOBI .....................................................................................................................................11 4.1.4 Algoritmo GAUSS–SEIDEL ..........................................................................................................................13 4.1.5 Reformulación Sistemas de Ecuaciones.................................................................................................14 4.1.6 Cálculo Términos de la Sucesión.............................................................................................................15 4.1.7 Convergencia de la Sucesión .................................................................................................................17 4.1.8 Análisis Comparativo de los Algoritmos..................................................................................................18

4.2. OBJETIVO 8: Algoritmo de CUTHILL–MCKEE (CM) ................................................................................19 4.2.1 Grafo Asociado al Problema...................................................................................................................19 4.2.2 Matriz Dispersa Asociada al Grafo..........................................................................................................20 4.2.3 Cálculo Ancho de Banda de la Matriz...................................................................................................21 4.2.4 Aplique el algoritmo Cuthill – Mc kee.....................................................................................................21 4.2.5 Calcule Nuevo Ancho de Banda de la Matriz. .....................................................................................22 4.2.6 Análisis de los resultados obtenidos referidos a la Compañía Manufacturera G & M......................22

4.3. OBJETIVO 9: Modelo de Grafos de Eliminación ..................................................................................23 4.3.1 Aplicación del Modelo de Grafos de Eliminación ................................................................................23 4.3.2 Análisis de lo Obtenido Referido a la Compañía..................................................................................27

4.4. OBJETIVO 10: ALGORITMO DE MÍNIMO GRADO...................................................................................28 4.4.1 Aplicación Algoritmo de Mínimo Grado................................................................................................28 4.4.2 Análisis de Resultado obtenido referido a la compañía manufacturera G & M...............................30

5. CONCLUSIONES..............................................................................................................................................31 5.1.1 Conclusiones .............................................................................................................................................31

6. REFERENCIAS...................................................................................................................................................32

6.1. Bibliográficas ..........................................................................................................................................32

6.2. Referencias WEB .....................................................................................................................................32 7. ANEXOS...........................................................................................................................................................33

7.1. IMPLEMENTACIÓN DE ALGORITMOS Y MODELOS EN EXCEL................................................................33

Trabajo Práctico: Métodos Numéricos Iterativos RESUMEN


7.1.1 PÁGINA DATOS DEL PROBLEMA ..............................................................................................................33 7.1.2 PÁGINA ALGORITMOS JACOBI Y GAUSS-SEIDELL...................................................................................34 7.1.3 PÁGINA ALGORITMO CUTHILL-McKEE.....................................................................................................35 7.1.4 PÁGINA MODELO DE GRAFOS DE ELIMINACIÓN...................................................................................36 7.1.5 PÁGINA ALGORITMO DE MÍNIMO GRADO.............................................................................................37 7.1.6 Programas Desarrollados para los Algoritmos .......................................................................................38

7.2. CONCEPTOS PRELIMINARES ...................................................................................................................52 7.2.1 Sistema de Ecuaciones Lineales (SEL).....................................................................................................52 7.2.2 Matriz Triangular ........................................................................................................................................53 7.2.3 Matriz Simétrica .........................................................................................................................................53 7.2.4 Matriz Definida Positiva.............................................................................................................................54 7.2.5 Matriz Indefinida........................................................................................................................................54 7.2.6 Matriz Diagonalmente Dominante y Diagonal Estrictamente Dominante.........................................54 7.2.7 Matriz Dispersa...........................................................................................................................................55 7.2.8 Sistemas de Gran Dimensión ...................................................................................................................57 7.2.9 Representación de Matrices con Grafos ...............................................................................................58

7.3. MÉTODOS ITERATIVOS BÁSICOS.............................................................................................................59 7.3.1 Algoritmo de Cuthill-Mckee (CM) ...........................................................................................................60 7.3.2 Algoritmo de Cuthill-McKee inverso (RCM)............................................................................................61 7.3.3 Algoritmo de Grado Mínimo....................................................................................................................62

8. ESPECIFICACIONES DEL TRABAJO .................................................................................................................63

8.1. Planteamiento del Problema ................................................................................................................63

8.2. INSTRUCCIONES GENERALES SOBRE EL TRABAJO PRÁCTICO...............................................................65

8.3. CRITERIO DE CORRECCIÓN ....................................................................................................................65 8.3.1 Objetivo Nos. 6, 8, 9, 10 ............................................................................................................................65

ACRÓNIMOS Y SIGLAS ..........................................................................................................................................66



1.2. ÍNDICE DE ILUSTRACIONES Y TABLAS

1.2.1 FIGURAS Figura 1. Representación de variables Xi, utilizadas por el método iterativo de Jacobi. .....................................................11 Figura 2. Algoritmo General para aplicación del Método Jacobi............................................................................................13 Figura 3. Ecuaciones representativas Algoritmo Gauss-Seidel. ..................................................................................................13 Figura 4. Algoritmo en Visual Basic para el Método Iterativo de Gauss-Seidel.......................................................................14 Figura 5.Grafo Asociado al Problema.............................................................................................................................................20 Figura 6.Modelo Grafo Eliminación, Iteración 0, Grafo GA. .......................................................................................................24 Figura 7.Modelo Grafo Eliminación, Iteración 1, Grafo GH1. .....................................................................................................25 Figura 8.Modelo Grafo Eliminación, Iteración 2, Grafo GH2. .....................................................................................................25 Figura 9.Modelo Grafo Eliminación, Iteración 3, Grafo GH3. .....................................................................................................26 Figura 10.Modelo Grafo Eliminación, Iteración 4, Grafo GH4. ...................................................................................................26 Figura 11.Modelo Grafo Eliminación, Iteración 5, Grafo GH5. ...................................................................................................26 Figura 12.Modelo Grafo Eliminación, Iteración 6, Grafo GH6. ...................................................................................................27 Figura 13.Modelo Grafo Eliminación, Iteración 7, Grafo GH7. ...................................................................................................27 Figura 14. Grafos Iteraciones de Algoritmo de Mínimo Grado. .................................................................................................29 Figura 15. Grafos Iteraciones de Algoritmo de Mínimo Grado. .................................................................................................30 Figura 16. Página Datos del Problema............................................................................................................................................33 Figura 17. Página Algoritmos Jacobi y Gauss-Seidel....................................................................................................................34 Figura 18. Página Algoritmo Cuthill-McKee....................................................................................................................................35 Figura 19. Página Modelo Grafos de Eliminación........................................................................................................................36 Figura 20.Pantalla Algoritmo de Mínimo Grado............................................................................................................................37 Figura 21. Sistema de Ecuación Lineal representado como Matriz. .........................................................................................53 Figura 22. Matriz Triangular Superior (U) e Inferior (L).. ..................................................................................................................53 Figura 23. Envolvente Matriz A..........................................................................................................................................................57 Figura 24.. Matriz Grafos de matrices dispersas 4x4.....................................................................................................................58 Figura 25. Grafo Asociado a una Matriz. ........................................................................................................................................59 Figura 26.. Grafo Asociado a una Matriz.......................................................................................................................................59 Figura 27. Ejemplo de aplicación del Algoritmo Cuthill-McKee.................................................................................................61 Figura 28. Ordenación de Ecuaciones por Algoritmo de Cuthill-McKee.................................................................................61 Figura 29. Ordenación de Ecuaciones por Algoritmo de Grado Mínimo. ...............................................................................62

1.2.2 TABLAS Tabla 1. Esquema de la magnitud de los problemas representados con SELS .......................................................................8 Tabla 2. Disponibilidad en horas máquinas por semana según el tipo de máquina. ...........................................................10 Tabla 3. Número Horas-Máquinas por unidad de productos.....................................................................................................10 Tabla 4. Matriz Asociada al Sistema de Ecuaciones del Problema. .........................................................................................11 Tabla 5. Matriz del Sistema de Ecuaciones. ...................................................................................................................................14 Tabla 6. Matriz Asociada al Sistema de Ecuaciones transformado del Problema.................................................................15 Tabla 7. Tabla Resultados Iteraciones Jacobi. ..............................................................................................................................16 Tabla 8. Tabla Resultados Iteraciones Gauss-Seidel.....................................................................................................................17 Tabla 9. Resultados Obtenidos de las Iteraciones Jacobi y Gauss-Seidel. ..............................................................................18 Tabla 10. Comparación Resultados Obtenidos de las Iteraciones Jacobi y Gauss-Seidel. .................................................18 Tabla 11. Análisis de Costo entre diferentes estados. ..................................................................................................................19 Tabla 12. Matriz para Construcción del Grafo Asociado al Problema.....................................................................................19 Tabla 13. Matriz Dispersa Asociada al Grafo (completa). .........................................................................................................20 Tabla 14. Matriz Dispersa Asociada al Grafo (completa). .........................................................................................................21 Tabla 15. Cálculo Ancho de banda Matriz Inicial. .......................................................................................................................21 Tabla 16. Resultado Iteraciones Cuthill-McKee. ............................................................................................................................21 Tabla 17. Cálculo Ancho de banda Matriz Envolvente Resultante. .........................................................................................22 Tabla 18. Iteraciones Modelo de Grafos de Eliminación.............................................................................................................23



Tabla 19. Iteraciones Modelo de Grafos de Eliminación (cont.). ..............................................................................................24 Tabla 20. Tabla Iteraciones Algoritmo de Mínimo Grado. ..........................................................................................................28 Tabla 21. Programa desarrollo Algoritmo Gauss-Seidel. ..............................................................................................................38 Tabla 22. Programa desarrollo Algoritmo Gauss-Seidel. ..............................................................................................................39 Tabla 23. Programa desarrollo Algoritmo Gauss-Seidel. ..............................................................................................................40 Tabla 24. Programa desarrollo Algoritmo Jacobi. ........................................................................................................................40 Tabla 25. Programa desarrollo Algoritmo Jacobi. ........................................................................................................................41 Tabla 26. Programas desarrollados para Cuthill-McKee. ............................................................................................................41 Tabla 27. Programas desarrollados para Cuthill-McKee. ............................................................................................................42 Tabla 28. Programas desarrollados para Cuthill-McKee. ............................................................................................................43 Tabla 29. Programas desarrollados para Cuthill-McKee. ............................................................................................................44 Tabla 30. Programas desarrollados para Cuthill-McKee. ............................................................................................................45 Tabla 31. Programas desarrollados para Cuthill-McKee. ............................................................................................................46 Tabla 32. Programas desarrollados para Cuthill-McKee. ............................................................................................................47 Tabla 33. Programas desarrollados para Modelo Grafos de Eliminación. ...............................................................................47 Tabla 34. Programas desarrollados para Modelo Grafos de Eliminación. ...............................................................................48 Tabla 35. Programas desarrollados para Modelo Grafos de Eliminación. ...............................................................................49 Tabla 36. Programas desarrollados para Algoritmo de Grado Mínimo....................................................................................50 Tabla 37. Programas desarrollados para Algoritmo de Grado Mínimo....................................................................................51 Tabla 38. Programas desarrollados para Algoritmo de Grado Mínimo....................................................................................52 Tabla 39. Disponibilidad en horas máquinas por semana según el tipo de máquina ..........................................................63 Tabla 40. Número Horas-Máquinas por unidad de productos...................................................................................................63 Tabla 41. Análisis de Costo entre diferentes estados. ..................................................................................................................64



2. RESUMEN

Este trabajo se centra en la optimización de los métodos numéricos para la solución de sistemas de ecuaciones lineales con matrices asociadas simétricas, indefinidas, dispersas y de gran dimensión. Los métodos se definen en entornos paralelos, haciendo uso de librerías de optimización y buscando el correcto manejo de las matrices dispersas para lograr la máxima optimización de los métodos definidos para la solución de sistemas de ecuaciones lineales con matrices asociadas que posean las características mencionadas.

3. INTRODUCCIÓN

La solución de sistemas de ecuaciones lineales es un tema de gran interés en el mundo de la computación actual. Son muchos los problemas que pueden resolverse utilizando estas técnicas, y en áreas tan variadas como se quiera. Por eso es de gran importancia el estudio de algoritmos que optimicen el uso de recursos computacionales como la memoria física y el tiempo de ejecución, a la vez que se encuentren soluciones correctas de manera óptima. Al estudiar las matrices generadas por los sistemas de ecuaciones se pueden observar ciertas características y propiedades, que pueden permitirnos en algunas ocasiones un tratamiento especial del problema mejorando los algoritmos tradicionales al explotar la estructura y las propiedades de la matriz.

3.1. DEFINICIÓN CONTEXTUAL

Los sistemas de ecuaciones lineales sirven para resolver múltiples problemas de todos los tipos imaginables en procesos naturales, en producción, en redes eléctricas, y en innumerables campos más. Los problemas varían en sus características y pueden ser resueltos con la ayuda de un computador de manera más eficiente si se trabaja explotando las características del problema mismo. El interés por la optimización de los métodos para la solución de sistemas de ecuaciones lineales ha generado diversos enfoques en cuanto a los métodos existentes para mejorar los algoritmos actuales. Aparecen entonces herramientas tan importantes como la computación paralela, librerías optimizadas con funciones básicas, librerías más avanzadas, tratamiento de la estructura de la matriz, etc. Todos estos enfoques no son mutuamente excluyentes, y por el contrario se intentará en este proyecto obtener el máximo provecho de cada uno de ellos, obteniendo un buen rendimiento global. Las aplicaciones son muchas, incluso en un enfoque tan específico como el de las matrices simétricas, dispersas e indefinidas. Entre ellas están los problemas de redes eléctricas, problemas de elementos finitos, y en general muchas aplicaciones de ingeniería, como por ejemplo el resultado de la discretización de ecuaciones diferenciales parciales en diferentes tipos de simulaciones. Cualquier optimización que se logre en este campo, será un gran aporte, debido a la gran cantidad de datos que suelen manejarse en estos casos, y a la necesidad de altos niveles de efi ciencia que se necesitan.

Trabajo Práctico: Métodos Numéricos Iterativos INTRODUCCIÓN


Además de los Métodos Directos para resolver un Sistema de Ecuaciones Lineales Simultáneas, existen los Métodos Iterativos cuya característica principal es que parten de una solución supuesta, u obtenida por otros métodos, y obtienen una solución mejorada según cierto criterio estipulado de tolerancia numérica (precisión). El mecanismo general mediante el cual los Métodos Iterativos realizan su funcionalidad se basa en operaciones repetidas de cálculo, calculando una solución y probando si ya se llegó al nivel de precisión estipulado. El problema principal de los Métodos Iterativos es que no siempre hay convergencia a una solución mejorada, o la convergencia se hace muy lentamente. Esto es especialmente cierto cuando se trata de grandes sistemas. Para tener una idea de lo que significa “grandes sistemas”; en la Tabla 1 se muestra a grandes rasgos la magnitud de problemas que es preciso resolver, en términos del número de incógnitas (m) de un Solución de Ecuaciones Lineales Simultáneas (SELS), de los requerimientos de memoria (en función de octetos), y del orden de magnitud en número de operaciones que implican los algoritmos.

Tabla 1. Esquema de la magnitud de los problemas representados con SELS

Esta tabla muestra que en unos 60 años la complejidad de los problemas, en número de operaciones, ha crecido constantemente; lo mismo las necesidades de almacenamiento. Esto ha implicado el tener que disponer de mejores máquinas de cómputo y de algoritmos más eficientes. Son muy variados los Métodos Iterativos que se han ideado y que se aplican a problemas prácticos en áreas técnicas y de ingenierías, el listado que a continuación se presenta se ha elegido teniendo en cuenta el estado del arte en el tema y la ejemplificación del desarrollo histórico de estos métodos, especialmente en la solución de grandes sistemas de ecuaciones lineales simultáneas; los métodos son: 1. Método de Jacobi; 2. Método de Gauss-Seidel; 3. Sobre Relajación Sucesiva (SOR); 4. Sobre Relajación Sucesiva Simétrica (SSOR); 5. Gradiente Conjugado (CG);

Trabajo Práctico: Métodos Numéricos Iterativos INTRODUCCIÓN


6. Mínimo Residual (MINRES) y LQ Simétrico (SYMLQ); 7. Gradientes Conjugados y Ecuaciones Normales (CGNE y CGNR); 8. Mínimo Residuo Generalizado (GMRES); 9. Gradiente Biconjugado (BiCG); 10. Cuasi-Mínimo Residuo (QMR); 11. Gradiente Conjugado Cuadrado (CGS); 12. Gradiente Biconjugado Estabilizado (Bi-CGSTAB); 13. Iteración de Chebyshev. Un método iterativo es un método que progresivamente va calculando aproximaciones a la solución de un problema. En Matemáticas, en un método iterativo se repite un mismo proceso de mejora sobre una solución aproximada: se espera que lo obtenido sea una solución más aproximada que la inicial. El proceso se repite sobre esta nueva solución hasta que el resultado más reciente satisfaga ciertos requisitos. A diferencia de los métodos directos, en los cuales se debe terminar el proceso para tener la respuesta, en los métodos iterativos se puede suspender el proceso al término de una iteración y se obtiene una aproximación a la solución. En este trabajo práctico se desarrollaran los algoritmos del Método de Jacobi y el correspondiente al Método de Gauss-Seidel.

Trabajo Práctico: Métodos Numéricos Iterativos DESARROLLO TEÓRICO


4. DESARROLLO TEÓRICO

4.1. OBJETIVO 6: MÉTODOS DE JACOBI Y GAUSS – SEIDEL

En esta sección veremos procedimientos iterativos para resolver un sistema de ecuaciones lineales (SEL). El primero de ellos conocido como el procedimiento de Jacobi basado en la idea de punto fijo y un segundo procedimiento conocido como método de Gauss-Seidel el cual es una modificación simple del procedimiento de Jacobi. Para estos métodos es de suma importancia el concepto de matriz diagonalmente dominante el cual se relaciona con la garantía de convergencia en la aplicación de estos métodos (ver apartado 7.2.6 Matriz Diagonalmente Dominante). En algunos casos es posible replantear el sistema para garantizar la convergencia.

4.1.1 SISTEMA DE ECUACIONES ASOCIADO CON EL PROBLEMA. El problema planteado establece: 14. La disponibilidad en horas máquinas por semana según el tipo de máquina:

TIEMPO DISPONIBLE TIPO DE MÁQUINA

(horas máquinas por semana) (horas máquinas por día) (5 días semana)

RECTIFICADORA 150 30 FRESADORA 500 100 TORNO 350 70

Tabla 2. Disponibilidad en horas máquinas por semana según el tipo de máquina.

15. El número de horas máquinas que se requerido para elaborar cada unidad de estos

productos:

PRODUCTOS TIPO DE MÁQUINA

1 2 3 RECTIFICADORA 3 0 6 FRESADORA 9 3 3 TORNO 4 5 0

Tabla 3. Número Horas-Máquinas por unidad de productos.

En primer lugar definimos las variables necesarias para representar las posibles decisiones. En este caso, corresponde a la cantidad de Horas disponibles (por máquina) y la cantidad de tiempo requerido para la producción de cada producto. Si de denominamos:



16. X1: Productos producidos del Producto 1, según los requerimientos de cada máquina. 17. X2: Productos producidos del Producto 2, según los requerimientos de cada máquina. 18. X3: Productos producidos del Producto 3, según los requerimientos de cada máquina. 19. bi: tiempo Disponible por máquina Entonces, el sistema de ecuaciones para la estimación de la producción, restringido al tiempo requerido por cada máquina para producir los tipos de productos, según la capacidad disponible, sería:


X1 X2 X3 bi

RECTIFICADORA 3 0 6 30 FRESADORA 9 3 3 100 TORNO 4 5 0 70

Tabla 4. Matriz Asociada al Sistema de Ecuaciones del Problema.

4.1.2 BREVE EXPLICACIÓN ALGORITMOS DE JACOBI Y GAUSS- SEIDEL.

4.1.3 ALGORITMO JACOBI Este Algoritmo es el método iterativo más simple para resolver sistemas de ecuaciones lineales y se aplica sólo a sistemas cuadrados, es decir a sistemas con tantas incógnitas como ecuaciones y esta basado en la idea del punto fijo. El Método de Jacobi, para resolver un Sistema de Ecuaciones Lineales Simultáneas (SELS), parte de la representación de cada elemento, Xi, del vector solución, X(), según se muestra en la siguiente figura, en la cual se despeja de cada ecuación i la variable Xi (i= 1,…,n).

Figura 1. Representación de variables Xi, utilizadas por el método iterativo de Jacobi.

En general, la ecuación genérica para Xi es así:



niXIaba

Xn

ijjjiji

iii ,....,2,1

1

)(;1

(3.1)

Con base a la ecuación 3.1 se elabora el algoritmo del Método Iterativo de Jacobi.

4.1.3.1 Orden conveniente para Jacobi En ciertas ocasiones al aplicar Jacobi la matriz no es diagonalmente dominante y por tanto no existirá garantía de convergencia. Sin embargo, en algunos casos será posible reordenar las incógnitas en otra manera de forma que la nueva matriz de coeficientes sea diagonalmente dominante. Esto se puede detectar revisando todos los posibles ordenamientos de las incógnitas y ver cómo es la matriz resultante. Claro que esto conlleva un bueno número de pruebas pues el número posible de ordenamientos en n variables es (n − 1)! pero cuando n es reducido es sencillo.

4.1.3.2 Descripción del Método de JACOBI El Método Iterativo de Jacobi puede describirse por los siguientes pasos: 1. Establecer un nivel de precisión ε. 2. Suponer un vector solución inicial XIn para el sistema de ecuaciones. 3. Reemplazar XIn en el lado derecho de las ecuaciones 3.2 y asignar los resultados a un

nuevo vector XF, así:

n

ijj

jijiii

i XIaba

XF1

*1

ni ,.....,2,1 (3.2)

Conocido XI reemplazarlo en las siguientes ecuaciones y obtener XF 4. Calcular la diferencia entre la solución inicial XI y la solución final XF: ||XI – XF|| (norma de

la diferencia entre los dos vectores).

4.1. Si esta diferencia es menor o igual que el nivel de precisión ε, entonces el vector solución del sistema es XF.

4.2. De lo contrario, se reemplaza XI por XF, y con estos nuevos valores realizamos los cálculos del paso 2. XI(i) = XF(i), para todo i=1,…,n.

En la Siguiente figura se muestra la implementación del algoritmo computacional para la implementación de este método.



Figura 2. Algoritmo General para aplicación del Método Jacobi.

4.1.4 ALGORITMO GAUSS–SEIDEL Existe otro método Iterativo conocido como método de Gauss-Seidel el cual es una modificación simple del procedimiento de Jacobi. El Método Gauss-Seidel parte de una solución inicial y calcula una nueva solución. En la figura siguiente se muestran las ecuaciones para la representación de cada elemento (ecuaciones (a) hasta la (g)); la fórmula (h) es la expresión genérica para calcular cada elemento Xi del vector solución X(); este método utiliza inmediatamente las Xi que va calculando.

11

11

11

1 a

Xab

X

n

jj

jj

22

1213

22

2 a

XaXab

X

n

jjj

33

2321314

32

3 a

XaXaXab

X

n

jjj

(a) (b) (c)

44

3432421415

44

4 a

XaXaXaXab

X

n

jjj

55

4543532521516

55

5 a

XaXaXaXaXab

X

n

jjj

(d) (e)

1,1

1

111

1

nn

i

kkik

n

njjjnn

n a

XaXab

X

nn

n

njj

jnjn

n a

Xab

X

;1 ni

a

Xab

Xnn

n

ijj

jiji

i ,...,2,1;1

(f) (g) (h)

Figura 3. Ecuaciones representativas Algoritmo Gauss-Seidel.



Basado en las fórmulas mostradas en la Figura anterior se muestra el programa para desarrollar el algoritmo Gauss-Seidel.

Figura 4. Algoritmo en Visual Basic para el Método Iterativo de Gauss-Seidel.

4.1.5 REFORMULACIÓN SISTEMAS DE ECUACIONES El sistema obtenido en el apartado 4.1.1 (Tabla 4. Matriz Asociada al Sistema de Ecuaciones del Problema.), para que pueda converger en los Métodos de Jacobi o Gauss-Seidel debe: 1. Ser una Matriz cuadrada. 2. No contener ceros en la Diagonal. 3. Ser una Matriz Diagonal Dominante. Si se observa la Matriz obtenida:

X1 X2 X3 bi

3 0 6 30 9 3 3 100 4 5 0 70

Tabla 5. Matriz del Sistema de Ecuaciones.



1. Contiene un elemento de una diagonal en cero (posición 3, 3); y 2. La matriz no es diagonalmente dominante. Por esto se requiere realizar una transformación de la Matriz para cumplir con los requerimientos, para esto: 1. Se intercambian la Fila 2 y la Fila 3; y 2. Se intercambia la Columna 3 y la Columna 1. Entonces, el sistema transformado de ecuaciones para la estimación de la producción, restringido al tiempo requerido por cada máquina para producir los tipos de productos, según la capacidad disponible, sería:


X1 X2 X3 bi

RECTIFICADORA 6 0 3 30 TORNO 0 5 4 70 FRESADORA 3 3 9 100

Tabla 6. Matriz Asociada al Sistema de Ecuaciones transformado del Problema.

La nueva definición de las variables sería: 1. X1: Productos producidos del Producto 3, según los requerimientos de cada máquina. 2. X2: Productos producidos del Producto 2, según los requerimientos de cada máquina. 3. X3: Productos producidos del Producto 1, según los requerimientos de cada máquina. 4. bi: tiempo Disponible por máquina Con esta transformación se logra que la matriz sea Diagonal Estrictamente Dominante, osea en Dominante por Filas y Columnas, con esto se asegura la convergencia de ambos algoritmos. Esta será la Matriz a utilizar para la aplicación de los algoritmos de Jacobi y Gauss-Seidell.

4.1.6 CÁLCULO TÉRMINOS DE LA SUCESIÓN Para el cálculo de los términos de la sucesión se desarrollaron los algoritmos de Jacobi y Gauss-Seidell, en una hoja de cálculo de Excel, aprovechando las bondades de programación de macros en lenguaje Visual Basic y la facilidad de mostrar y registrar los Datos obtenidos de las iteraciones en la propia hoja de cálculo (ver apartado 7.1 IMPLEMENTACIÓN DE ALGORITMOS Y MODELOS EN EXCEL). A continuación se muestran los términos obtenidos de la sucesión, generados a partir del punto Po = (20, 50, 15) para ambos Métodos.



4.1.6.1 Tablas de Resultados ALgoritmo Jacobi

X1 X2 X3 bi 6,0000 0,0000 3,0000 30,0000 0,0000 5,0000 4,0000 70,0000 3,0000 3,0000 9,0000 100,0000

VALORES INICIALES DEL PROBLEMA

X1(0)= X2(0)= X3(0)= PRECISIÓN 50,0000 15,0000 20,0000 0,00100

TABLA RESULTADOS ITERACIONES ALGORITMO JACOBI

i X1 X2 X3 X1 (i+1) X2 (i+1) X3 (i+1) Error(i) 0 50,0000 15,0000 20,0000 -5,0000 -2,0000 -10,5556 65,1739 1 -5,0000 -2,0000 -10,5556 10,2778 22,4444 13,4444 37,5092 2 10,2778 22,4444 13,4444 -1,7222 3,2444 0,2037 26,2289 3 -1,7222 3,2444 0,2037 4,8981 13,8370 10,6037 16,2540 4 4,8981 13,8370 10,6037 -0,3019 5,5170 4,8660 11,3659 5 -0,3019 5,5170 4,8660 2,5670 10,1072 9,3727 7,0434 6 2,5670 10,1072 9,3727 0,3136 6,5018 6,8864 4,9252 7 0,3136 6,5018 6,8864 1,5568 8,4909 8,8393 3,0521 8 1,5568 8,4909 8,8393 0,5804 6,9286 7,7619 2,1343 9 0,5804 6,9286 7,7619 1,1191 7,7905 8,6081 1,3226 10 1,1191 7,7905 8,6081 0,6959 7,1135 8,1413 0,9248 11 0,6959 7,1135 8,1413 0,9294 7,4870 8,5080 0,5731 12 0,9294 7,4870 8,5080 0,7460 7,1936 8,3057 0,4008 13 0,7460 7,1936 8,3057 0,8472 7,3555 8,4646 0,2484 14 0,8472 7,3555 8,4646 0,7677 7,2283 8,3769 0,1737 15 0,7677 7,2283 8,3769 0,8116 7,2985 8,4458 0,1076 16 0,8116 7,2985 8,4458 0,7771 7,2434 8,4078 0,0753 17 0,7771 7,2434 8,4078 0,7961 7,2738 8,4376 0,0466 18 0,7961 7,2738 8,4376 0,7812 7,2499 8,4211 0,0326 19 0,7812 7,2499 8,4211 0,7894 7,2631 8,4341 0,0202 20 0,7894 7,2631 8,4341 0,7830 7,2527 8,4269 0,0141 21 0,7830 7,2527 8,4269 0,7865 7,2584 8,4325 0,0088 22 0,7865 7,2584 8,4325 0,7837 7,2540 8,4295 0,0061 23 0,7837 7,2540 8,4295 0,7853 7,2564 8,4319 0,0038 24 0,7853 7,2564 8,4319 0,7841 7,2545 8,4305 0,0027 25 0,7841 7,2545 8,4305 0,7847 7,2556 8,4316 0,0016 26 0,7847 7,2556 8,4316 0,7842 7,2547 8,4310 0,0011 27 0,7842 7,2547 8,4310 0,7845 7,2552 8,4315 0,0007

X1 X2 X3

VALORES FINALES: 0,7842 7,2547 8,4310

Tabla 7. Tabla Resultados Iteraciones Jacobi.



4.1.6.2 Tablas de Resultados ALgoritmo Gauss-Seidel

X1 X2 X3 bi 6,0000 0,0000 3,0000 30,0000 0,0000 5,0000 4,0000 70,0000 3,0000 3,0000 9,0000 100,0000

VALORES INICIALES DEL PROBLEMA

X1(0)= X2(0)= X3(0)= PRECISIÓN 50,0000 15,0000 20,0000 0,00100

TABLA RESULTADOS ITERACIONES ALGORITMO GAUSS-SEIDEL

i X1 X2 X3 Error(i) 0 50,0000 15,0000 20,0000 6,8057 1 -5,0000 -2,0000 13,4444 2,9491 2 -1,7222 3,2444 10,6037 1,2780 3 -0,3019 5,5170 9,3727 0,5538 4 0,3136 6,5018 8,8393 0,2400 5 0,5804 6,9286 8,6081 0,1040 6 0,6959 7,1135 8,5080 0,0451 7 0,7460 7,1936 8,4646 0,0195 8 0,7677 7,2283 8,4458 0,0085 9 0,7771 7,2434 8,4376 0,0037 10 0,7812 7,2499 8,4341 0,0016 11 0,7830 7,2527 8,4325 0,0007 12 0,7837 7,2540 8,4319 0,0000

X1 X2 X3

VALORES FINALES: 0,7837 7,2540 8,4319

Tabla 8. Tabla Resultados Iteraciones Gauss-Seidel.

4.1.7 CONVERGENCIA DE LA SUCESIÓN Uno de los principales problemas de los métodos iterativos es la garantía de que el método va a converger, es decir, va a producir una sucesión de aproximaciones cada vez efectivamente más próximas a la solución. En el caso del método de Jacobi no existe una condición exacta para la convergencia. La condición que mejor garantiza la convergencia, pero en caso de no cumplirse puede o no haberla es si la matriz de coeficientes original del sistema de ecuaciones es diagonalmente dominante. En la aplicación práctica del algoritmo verificamos que si no aseguramos la dominancia de la diagonal el método no converge. En la siguiente Tabla se muestran los resultados obtenidos por ambos métodos.



VALORES FINALES X1 X2 X3 ALGORITMO JACOBI 0,7842 7,2547 8,4310 ALGORITMO GAUSS-SEIDELL 0,7837 7,2540 8,4319

Tabla 9. Resultados Obtenidos de las Iteraciones Jacobi y Gauss-Seidel.

De las iteraciones podemos concluir que: 1. Ambos métodos convergen a los puntos: X1= 0,78, X2= 7,25 y X3= 8,43. 2. El error en ambos métodos, se observa como va disminuyendo y ambos satisfacen el

requerimiento de ser menor a 0,001 (Precisión).

4.1.8 ANÁLISIS COMPARATIVO DE LOS ALGORITMOS Del análisis comparativo de los Algoritmos, según sus resultados y su convergencia se pude concluir. 1. El Método de Gauss-Seidel convergió más rápido que el Jacobi, 12 y 27 iteraciones

respectivamente. 2. Analizando el error se observa que ambos métodos dan soluciones muy similares, como se

muestra en la siguiente Tabla:

JACOBI GAUSS-SEIDEL bi bi Error(i) bi Error(i)

30,0000 29,9982 0,0018 29,9979 0,0021 70,0000 69,9975 0,0025 69,9976 0,0024

100,0000 99,9957 0,0043 100,0002 -0,0002 Tabla 10. Comparación Resultados Obtenidos de las Iteraciones Jacobi y Gauss-Seidel.

3. Analice los dos algoritmos y su incidencia en el problema de la Compañía Manufacturera

G & M.



4.2. OBJETIVO 8: ALGORITMO DE CUTHILL–MCKEE (CM)

La compañía manufacturera M & G esta analizando los costos entre los diferentes estados de un país obteniendo los siguientes resultados:

A B C D E F G H A - 4 - 6 - 3 - 6 B 4 - 2 - 4 - 3 - C - 2 - 5 - 2 - 3 D 6 - 5 - 1 - 6 - E - 4 - 1 - 7 - 1 F 3 - 2 - 7 - 1 - G - 3 - 6 - 1 - 3 H 6 - 3 - 1 - 3 -

Tabla 11. Análisis de Costo entre diferentes estados.

4.2.1 GRAFO ASOCIADO AL PROBLEMA De la matriz de análisis de Costo, asumiendo los guiones “-“, como posiciones vacías y para efectos prácticos de programación se sustituyo las letras A hasta H, por 1 hasta 8 respectivamente.

1 2 3 4 5 6 7 8 1 - 4 - 6 - 3 - 6 2 4 - 2 - 4 - 3 - 3 - 2 - 5 - 2 - 3 4 6 - 5 - 1 - 6 - 5 - 4 - 1 - 7 - 1 6 3 - 2 - 7 - 1 - 7 - 3 - 6 - 1 - 3 8 6 - 3 - 1 - 3 -

Tabla 12. Matriz para Construcción del Grafo Asociado al Problema.



El Grafo obtenido es mostrado en la siguiente figura:

Figura 5.Grafo Asociado al Problema.

4.2.2 MATRIZ DISPERSA ASOCIADA AL GRAFO. Para la construcción de la Matriz dispersa asociada al Grafo, se asumió los valores de costos como “*” y el resto de las posiciones como blancos, de aquí obtenemos:

1 2 3 4 5 6 7 8 1 1 * * * * 2 * 2 * * * 3 * 3 * * * 4 * * 4 * * 5 * * 5 * * 6 * * * 6 * 7 * * * 7 * 8 * * * * 8

Tabla 13. Matriz Dispersa Asociada al Grafo (completa).

Como se observa la matriz Dispersa es simétrica, por tanto para efectos de la aplicación del Método de Cuthill-McKee, se utilizará una matriz Triangular Inferior, como se muestra en la siguiente Tabla.



1 2 3 4 5 6 7 8 1 1 2 * 2 3 * 3 4 * * 4 5 * * 5 6 * * * 6 7 * * * 7 8 * * * * 8

Tabla 14. Matriz Dispersa Asociada al Grafo (completa).

Esta será la Matriz a aplicar en el Algoritmo desarrollado en Excel.

4.2.3 CÁLCULO ANCHO DE BANDA DE LA MATRIZ Los resultados obtenidos del cálculo de los parámetros, por medio del programa realizado en Excel, para la matriz inicial son mostrados en la siguiente tabla: MATRIZ INICIAL DE DATOS (ENVOLVENTE ORIGINAL)

nxn 1 2 3 4 5 6 7 8 GRADO VÉRTICE GRADO FILA

GRADO COL. ξi(A) βi(A)= i-ξi(A)

1 1 4 0 4 1 0 2 * 2 7 1 6 1 1 3 * 3 7 2 5 1 2 4 * * 4 7 3 4 1 3 5 * * 5 7 4 3 1 4 6 * * * 6 6 4 2 2 4 7 * * * 7 6 5 1 2 5 8 * * * * 8 6 6 0 2 6

VÉRTICE INICIO: 2 CONTORNO INICIAL: 31 ANCHO DE BANDA (β): 7

Tabla 15. Cálculo Ancho de banda Matriz Inicial.

4.2.4 APLIQUE EL ALGORITMO CUTHILL – MC KEE. A continuación se muestra el resultado de la Iteraciones del Método Cuthill-McKee, obtenidos mediante el programa desarrollado en Excel.

ITERACIÓN No. VÉRTICE (ETIQUETA GRAFO) VECINOS NO ETIQUETADOS GRADO NUEVA ETIQUETA

1 V2 V1 4 V2 2 V3 4 V3 3 V5 4 V4 4 V7 4 V5 5 V1 V4 4 V6 6 V6 4 V7 7 V8 4 V8

Tabla 16. Resultado Iteraciones Cuthill-McKee.



4.2.5 CALCULE NUEVO ANCHO DE BANDA DE LA MATRIZ. El cálculo a la matriz reordenada, después de la aplicación del Método Cuthill-McKee es: ENVOLVENTE RESULTANTE (APLICADO MÉTODO )

nxn 1 2 3 4 5 6 7 8 GRADO VÉRTICE

GRADO FILA

GRADO COL. ξi(A) βi(A)= i-ξi(A)

1 2 4 0 4 1 0 2 * 1 7 1 6 1 1 3 * 0 3 7 2 5 1 2 4 * 0 0 5 7 3 4 1 3 5 * 0 0 0 7 7 4 3 1 4 6 * * * * 4 6 4 2 2 4 7 * * * * 0 6 6 5 1 2 5 8 * * * * 0 0 8 6 6 0 2 6

VÉRTICE INICIO: 2 CONTORNO FINAL: 25 ANCHO DE BANDA (β): 6

Tabla 17. Cálculo Ancho de banda Matriz Envolvente Resultante.

4.2.6 ANÁLISIS DE LOS RESULTADOS OBTENIDOS REFERIDOS A LA COMPAÑÍA MANUFACTURERA G & M.



4.3. OBJETIVO 9: MODELO DE GRAFOS DE ELIMINACIÓN

4.3.1 APLICACIÓN DEL MODELO DE GRAFOS DE ELIMINACIÓN A partir de la Matriz Dispersa obtenida en el Apartado anterior y por medio del programa desarrollado en Excel, para la ejecución del Modelo de Grafos de Eliminación se obtuvo los siguientes resultados:

APLICACIÓN ALGORITMO MODELO GRAFOS DE ELIMINACIÓN

ITERACIÓN 0: MATRIZ INICIAL (A=Ao=Ho) 1 * 2 * 3 * * 4 * * 5 * * * 6 * * * 7 * * * * 8

ITERACIÓN 1: MATRIZ H1 2 Ø Ø Ø * 3 Ø * 4 Ø Ø * * 5 Ø * Ø * 6 Ø * * * 7 Ø * Ø * Ø * 8

ITERACIÓN 2: MATRIZ H2 3 Ø Ø Ø Ø Ø Ø 4 Ø Ø Ø Ø Ø Ø 5 Ø Ø Ø Ø Ø Ø 6 Ø Ø Ø Ø Ø Ø 7 Ø Ø Ø Ø Ø Ø 8

ITERACIÓN 3: MATRIZ H3 4 Ø Ø Ø Ø Ø 5 Ø Ø Ø Ø Ø 6 Ø Ø Ø Ø Ø 7 Ø Ø Ø Ø Ø 8

ITERACIÓN 4: MATRIZ H4 5 Ø Ø Ø Ø 6 Ø Ø Ø Ø 7 Ø Ø Ø Ø 8

Tabla 18. Iteraciones Modelo de Grafos de Eliminación.



ITERACIÓN 5: MATRIZ H5

6 Ø Ø Ø 7 Ø Ø Ø 8

ITERACIÓN 6: MATRIZ H6 7 Ø Ø 8

ITERACIÓN 7: MATRIZ H7 8

Tabla 19. Iteraciones Modelo de Grafos de Eliminación (cont.).

La secuencia de Grafos de Eliminación obtenidos en la aplicación del Modelo de Grafos de Eliminación se muestran a continuación.

ITERACIÓN 0: GRAFO GA

Figura 6.Modelo Grafo Eliminación, Iteración 0, Grafo GA.



ITERACIÓN 1: GRAFO GH1

Figura 7.Modelo Grafo Eliminación, Iteración 1, Grafo GH1.









4.3.2 ANÁLISIS DE LO OBTENIDO REFERIDO A LA COMPAÑÍA



4.4. OBJETIVO 10: ALGORITMO DE MÍNIMO GRADO

4.4.1 APLICACIÓN ALGORITMO DE MÍNIMO GRADO A continuación se muestran los resultados de las iteraciones después de aplicado al Algoritmo de Mínimo Grado, al problema bajo estudio (Objetivo 8), mediante el programa desarrollado en Excel para la ejecución de este algoritmo. MATRIZ INICIAL DE DATOS

1 2 3 4 5 6 7 8 GRADO VÉRTICE

GRADO FILA

GRADO COL. ξi(A) βi(A)= i-

ξi(A) 1 1 0 4 4 1 0 2 * 2 1 3 4 1 1 3 * 3 1 3 4 2 1 4 * * 4 2 2 4 1 3 5 * * 5 2 2 4 2 3 6 * * * 6 3 1 4 1 5 7 * * * 7 3 1 4 2 5 8 * * * * 8 4 0 4 1 7

VÉRTICE INICIO: 1 ANCHO DE BANDA (β): 7 DATOS MATRIZ INICIAL ITERACIÓN No. VÉRTICE GRADO VECINOS NO ELIMINADOS

1 V1 4 V2, V4, V6, V8 2 V2 4 V1, V3, V5, V7 3 V3 4 V2, V4, V6, V8 4 V4 4 V1, V3, V5, V7 5 V5 4 V2, V4, V6, V8 6 V6 4 V1, V3, V5, V7 7 V7 4 V2, V4, V6, V8 8 V8 4 V1, V3, V5, V7

DATOS ALGORITMO MÍNIMO GRADO

ITERACIÓN No. VÉRTICE MÍNIMO GRADO GRADO VECINOS NO ELIMINADOS

1 V1 4 V2, V4, V6, V8 2 V2 3 V3, V5, V7 3 V3 3 V4, V6, V8 4 V4 2 V5, V7 5 V5 2 V6, V8 6 V6 1 V7 7 V7 1 V8

Tabla 20. Tabla Iteraciones Algoritmo de Mínimo Grado.



GA=G0

G1

G2

Figura 14. Grafos Iteraciones de Algoritmo de Mínimo Grado.



G3

G4

G5

G6

Figura 15. Grafos Iteraciones de Algoritmo de Mínimo Grado.

4.4.2 ANÁLISIS DE RESULTADO OBTENIDO REFERIDO A LA COMPAÑÍA MANUFACTURERA G & M

Trabajo Práctico: Métodos Numéricos Iterativos CONCLUSIONES


5. CONCLUSIONES

1. Ventajas y Desventajas iterativos sobre los métodos directos 1.1. Los métodos iterativos calculan aproximaciones a la solución. 1.2. Los métodos iterativos se usan cuando no se conoce un método para obtener la

solución en forma exacta. 1.3. También se utilizan cuando el método para determinar la solución exacta requiere

mucho tiempo de cálculo, cuando una respuesta aproximada es adecuada, y cuando el número de iteraciones es relativamente reducido.

5.1.1 CONCLUSIONES sobre el grafo asociado, su matriz dispersa y el ancho de banda Reordenar las matrices para reducir el número de elementos de relleno presenta tres ventajas fundamentales: Una disminución del número de posiciones de memoria que se han de reservar para los

nuevos elementos que se harán distintos de cero en un proceso de factorización. Una disminución del número de operaciones a realizar y, por lo tanto, el tiempo total de

cálculo para factorizar la matriz y resolver el correspondiente sistema. Una mejora de la estabilidad numérica del proceso global de resolución del sistema al

disminuir el número de elementos a considerar y por tanto disminuir la probabilidad de encontrar grandes diferencias entre ellos, errores de cancelación, entre otros.

Trabajo Práctico: Métodos Numéricos Iterativos REFERENCIAS


6. REFERENCIAS

6.1. BIBLIOGRÁFICAS

[1] Texto UNA “GRAFOS Y MATRICES” (Código 332). [2] QUINTANA HERNÁNDEZ Pedro Alberto; Métodos numéricos con aplicaciones en Excel. [3] MONTOYA, William Álvarez; Notas de Clase – 3004578 – Algoritmos y Programación [4] CCIR/ITESM, Departamento de Matemáticas, Métodos Iterativos para Resolver Sistemas

Lineales, 17 de julio de 2009. [5] CUTHILL, E. y MCKEE, J.; Reducing the Bandwidth of Sparse Symmetric Matrices. 24th Nat.

Conf. ACM, páginas 157-172, 1969. [6] CUTHILL, E.; Several Strategies for Reducing the Bandwith of Matrices, Papers of the

Symposium on Sparse Matrices and their Applications, IBM Thomas J. Watson Research Center, New York, 1971.

[7] DE LA FUENTE O’CONNOR, José Luis; Sistemas Lineales de Grandes Dimensiones: Matrices Dispersas; Universidad Politécnica de Madrid, Escuela Técnica Superior de Ingenieros Industriales.

[8] Universidad Politécnica de Madrid [9] ALMEIDA BENÍTEZ, Pedro Ramón y FRANCO BRAÑAS, José Ramón ([email protected]);

Reducción del Ancho de Banda de Matrices en el Algoritmo Go-Away para Mallas Regulares; Departamento de Matemáticas, Universidad de Las Palmas de Gran Canaria; Departamento de Análisis Matemático, Universidad de La Laguna.

[10] JARAMILLO J., Juan David; VIDAL MACIÁ, Antonio M.; y CORREA ZABALA , Francisco José; Métodos Directos para aa Solución de Sistemas de Ecuaciones Lineales Simétricos, Indefinidos, Dispersos y de Gran Dimensión; DOCUMENTO 40-022006; UNIVERSIDAD EAFIT; Medellín, Febrero de 2006.

[11] GINESTAR PEIRÓ, Damián; Matrices Dispersas; Departamento de Matemática Aplicada, Universidad Politécnica de Valencia; Curso 2009-2010

[12] ERSAVAS, Bulut F.; Sparse Matrix Ordering and Gaussian Elimination; ECE 3652 - Fundamentals of Computer Engineering; Term Paper; [email protected]; December 8, 2002.

6.2. REFERENCIAS WEB

[13] http://www.uv.es/diaz/mn/node25.html [14] http://es.wikipedia.org/wiki/Teor%C3%ADa_de_grafos. [15] http://www.unalmed.edu.co/~walvarem/. [16] http://xue.unalmed.edu.co/~walvarem/ [17] www.eng-tips.com/viewthread.cfm?qid=11754&page=18 [18] http://es.wikipedia.org/wiki/Matriz_de_diagonal_estrictamente_dominante [19] http://www.revistaciencias.com/publicaciones/EEAAupyyFlGVXhDnhI.php [20] http://www.acatlan.unam.mx/acatlecas/mn/sistemas.htm [21] http://www.construccion.uniovi.es/escal3d/Bases/Solve/ANEXO3.htm

Trabajo Práctico: Métodos Numéricos Iterativos ANEXOS


7. ANEXOS

7.1. IMPLEMENTACIÓN DE ALGORITMOS Y MODELOS EN EXCEL

Para el desarrollo del presente trabajo se implementaron los diferentes algoritmos solicitados en según los objetivos. Para esta implementación se selección la Hoja de Cálculo de Excel, como base para el desarrollo de los diferentes algoritmos, métodos y modelos, por su versatilidad de programación de macros mediante el lenguaje Visual Basic y la facilidad de poder registrar los datos de las iteraciones (creación de reportes) y también permitió la graficación de los Grafos de los métodos que lo requirieron. A continuación se dará una breve explicación de la implementación de los diferentes algoritmos en Excel, utilizados para el desarrollo del presente trabajo.

7.1.1 PÁGINA DATOS DEL PROBLEMA La primera Página del programa es la hoja de “Datos del Problema”, que es donde se ingresan los Datos para los diferentes algoritmos, tales como: matrices, número de variables, precisión, entre otros. El archivo contentivo del programa es: “Trabajo Práctico Grafos-Matrices (332) (2011-2)”, este archivo al ser abierto automáticamente iniciará en la pantalla del programa implementado. La pantalla de Datos Generales del Sistema es mostrada en la siguiente figura.

Figura 16. Página Datos del Problema.



En esta pantalla se selecciona el algoritmo a trabajar y se pueden introducir los datos necesarios para su ejecución.

7.1.2 PÁGINA ALGORITMOS JACOBI Y GAUSS-SEIDELL En esta Página se desarrollan los algoritmos Jacobi y Gauss-Seidel. Aquí se realizan las iteraciones y también se pueden cambiar los valores iniciales y registrar el resultado de las iteraciones. El resultado será almacenado en la Hoja “JACOBI” si esta seleccionado el método Jacobi o en caso contario se almacenará en la Hoja “GAUSS-SEIDEL”.

Figura 17. Página Algoritmos Jacobi y Gauss-Seidel.



7.1.3 PÁGINA ALGORITMO CUTHILL-MCKEE En esta Página se desarrolla el método Cuthill-McKee. En ella se puede seleccionar las diferentes opciones relacionadas con este algoritmo al igual se puede realizar el registro de las iteraciones realizadas. También esta pantalla permite seleccionar si se quiere ver el resultado de las iteraciones o los parámetros de la Matriz inicial o resultante. Los datos de este método son almacenados en la Hoja “CUTHILL-McKEE”, al momento de seleccionara la opción “Registrar”. Como opción adicional se implemento el Método Cuthill-McKee Inverso.

Figura 18. Página Algoritmo Cuthill-McKee.



7.1.4 PÁGINA MODELO DE GRAFOS DE ELIMINACIÓN En esta Página se desarrolla el Modelo de Grafos de Eliminación. La matriz inicial de trabajo de este método es introducido en la Página de “Datos del Problema”, y en esta sólo se realizan las iteraciones. Las iteraciones se realizan paso a paso, mediante el botón “Continuar” y podrá ser detenida en cualquier momento mediante el botón “Parar”. El resultado de la iteración se irá mostrando a medida que pulsemos “Continuar”. Al finalizar la iteración se habilitará el botón “Dibujar Grafo”, de forma de poder dibujara los Grafos asociados a los resultados de las iteraciones, en la Hoja “MODELOS GRAFOS ELIMINACIÓN”. A diferencia de los otros métodos, pos su característica, este método va registrando a medida que se pulsa “Continuar”.

Figura 19. Página Modelo Grafos de Eliminación.



7.1.5 PÁGINA ALGORITMO DE MÍNIMO GRADO En esta Página se implementa el Algoritmo de Mínimo Grado. Al igual que el método anterior los datos son introducidos en la Página “Datos del Problema” y en esta se desarrolla el algoritmo. Se podrá pasar de iteración en iteración mediante el botón “Continuar” y se puede salir de la iteración mediante el botón “Parar”. Al finalizar se podrá registrar el resultado de las iteraciones mediante el botón “Registrar” o “Dibujar Grafo”.

Figura 20.Pantalla Algoritmo de Mínimo Grado.

En cualquier momento se puede salir de la Pantalla Principal e ir a las hojas para revisar los resultados, pulsando el botón “Salir”. Si se desea regresar a la Pantalla General, en cada Hoja se encontrará un Botón denominado “Iniciar Programa” que nos llevara de nuevo al programa principal. Con este desarrollo sólo se pretendió implementar los diferentes algoritmos, métodos y modelos de forma de cumplir con los requisitos de la materia y poder de una forma más sencilla poder simular el problema bajo estudio.



7.1.6 PROGRAMAS DESARROLLADOS PARA LOS ALGORITMOS A continuación se muestran las rutinas básicas desarrolladas para la implementación de cada uno de los algoritmos. Sólo se muestran las rutinas que directamente desarrollan los métodos, ya que se desarrollaron otra gran cantidad e rutinas para el manejo, registro y graficación de los diferentes métodos. Esta rutinas pueden ser vistas, habilitando la opción de Visual Basic del Excel e ir pasando por las diferentes Hojas y Módulos.

7.1.6.1 Programas Jacobi y Gauss-Seidel ' Public Sub IterarGaussSeidel() HojaActual = ActiveSheet.Name Sheets(HojaTrabajo).Activate ActualizarValores pFilaIxGS = cFilaFormato pColIx = cPColIx nFilMat = nNumVar nColMat = nNumVar nNumIterMax = cMaxIter Cells(pFilaIxGS + 1, 1) = nPrecision ' ReDim MatrizA(nNumVar, nNumVar) ReDim VectorXI(nNumVar, 1) ReDim VectorXFGS(nNumVar, 1) ReDim VectorB(nNumVar, 1) ReDim MatrizResJGS(nNumIterMax + 1, nNumVar * 2 + 1) ' 'Transfiere Datos de Grid Matriz A para Matriz A For I = 1 To nNumVar For j = 1 To nNumVar If UFProyecto.MSHFlexGrid1.TextMatrix(I, j) <> "" Then nValorAij = CDbl(UFProyecto.MSHFlexGrid1.TextMatrix(I, j)) Else nValorAij = 0 End If MatrizA(I, j) = nValorAij Next j nValorBij = CDbl(UFProyecto.MSHFlexGrid1.TextMatrix(I, j)) VectorB(I, 1) = nValorBij Next I 'Transfiere Valores Iniciales del Grid a Vector XI (Valores Iniciales) For I = 1 To nNumVar nValorX0 = CDbl(UFProyecto.MSHFlexGrid2.TextMatrix(1, I)) VectorXI(I, 1) = nValorX0 Next I ' nIter = 0 nTimeIni = Time TestMD = MatrizDominante(MatrizA) If TestMD Then '

Tabla 21. Programa desarrollo Algoritmo Gauss-Seidel.



' Do 'Escribe resultados en Matriz de Resultados y en Vector Inicial For I = 1 To nNumVar MatrizResJGS(nIter + 1, I) = VectorXI(I, 1) 'If nIter <> 0 Then ' MatrizResJGS(nIter + 1, nNumVar + i) = VectorXFGS(i, 1) 'End If VectorXFGS(I, 1) = VectorXI(I, 1) '.. X(i) se halló por Gauss Next I nSuma = 0 nGSError = 0 'Cálculo Primera variable For j = 2 To nNumVar nSuma = nSuma + MatrizA(1, j) * VectorXFGS(j, 1) Next j If MatrizA(1, 1) <> 0 Then VectorXFGS(1, 1) = (VectorB(1, 1) - nSuma) / MatrizA(1, 1) Else VectorXFGS(1) = 0 End If nGSError = nGSError + (VectorXFGS(1, 1) - VectorXI(1, 1)) ^ 2 'Se transfiere resultado de primera Variable a Vector Valores Iniciales VectorXI(1, 1) = VectorXFGS(1, 1) ' 'Calculo segunda y n-esima variables For I = 2 To nNumVar nSum1 = 0 nSum2 = 0 For j = I + 1 To nNumVar nSum1 = nSum1 + MatrizA(I, j) * VectorXFGS(j, 1) Next j For k = 1 To I - 1 nSum2 = nSum2 + MatrizA(I, k) * VectorXFGS(k, 1) Next k If MatrizA(I, I) <> 0 Then VectorXFGS(I, 1) = (VectorB(I, 1) - nSum1 - nSum2) / MatrizA(I, I) Else VectorXFGS(I) = 0 End If nGSError = nGSError + (VectorXFGS(I, 1) - VectorXI(I, 1)) ^ 2 'Se transfiere el valor de la Variable I a Vector Inicial VectorXI(I, 1) = VectorXFGS(I, 1) Next I nGSError = Sqr(nGSError) 'Calcula Error MatrizResJGS(nIter, nNumVar * 2 + 1) = nGSError 'Escribe Error en Tabla 'pFila = pFila + 1 nIter = nIter + 1 Loop Until (nGSError <= nPrecision Or nIter >= nNumIterMax + 1) ' nTimeFinal = Time ' Asigna hora de finalización. If nNumIter <> nIter - 1 Then nNumIter = nIter - 1 End If '




' UFProyecto.TBNumIterJGS.Value = CInt(nNumIter) nTiempoTotal = (nTimeFinal - nTimeIni) 'Calcula tiempo total. UFProyecto.TBTiempoJGS.Text = Format(nTiempoTotal, "##,##0.00000000000000000000") 'Transfiere Datos Almacenados en Matriz Resultados a Grid Call TransferirResultadosJGS UFProyecto.CBRegistrarJGS.Enabled = True ' Else 'Matriz No Dominante MsgBox ("MATRIZ NO DOMINANTE, Iteración GAUSS-SEIDEL no Iniciada") End If End Sub '


' Public Sub IterarJacobi() HojaActual = ActiveSheet.Name Sheets(HojaTrabajo).Activate ActualizarValores pFilaIxJ = cFilaFormato pColIx = cPColIx nFilMat = nNumVar nColMat = nNumVar ' nNumIterMax = cMaxIter Cells(pFilaIxJ + 1, 1) = nPrecision ' ReDim MatrizA(nNumVar, nNumVar) ReDim VectorXI(nNumVar, 1) ReDim VectorXFJ(nNumVar, 1) ReDim VectorB(nNumVar, 1) ReDim MatrizResJGS(nNumIterMax + 1, nNumVar * 2 + 1) ' 'Transfiere Datos de Grid para Matriz A For I = 1 To nNumVar For j = 1 To nNumVar nValorAij = CDbl(UFProyecto.MSHFlexGrid1.TextMatrix(I, j)) MatrizA(I, j) = nValorAij Next j ' nValorBij = CDbl(UFProyecto.MSHFlexGrid1.TextMatrix(I, j)) VectorB(I, 1) = nValorBij ' Next I 'Transfiere Valores Iniciales del Grid a Matriz For I = 1 To nNumVar nValorX0 = CDbl(UFProyecto.MSHFlexGrid2.TextMatrix(1, I)) VectorXI(I, 1) = nValorX0 Next I '

Tabla 24. Programa desarrollo Algoritmo Jacobi.



UFProyecto.TBNumIterJGS.Value = CInt(nNumIter) nTiempoTotal = (nTimeFinal - nTimeIni) 'Calcula tiempo total. UFProyecto.TBTiempoJGS.Text = Format(nTiempoTotal, "##,##0.00000000000000000000") 'Transfiere Datos Almacenados en Matriz Resultados a Grid Call TransferirResultadosJGS UFProyecto.CBRegistrarJGS.Enabled = True Else 'Matriz no Dominante MsgBox ("MATRIZ DE DATOS NO DOMINANTE, , Iteración JACOBI no Iniciada") End If ' End Sub '

Tabla 25. Programa desarrollo Algoritmo Jacobi.

7.1.6.2 Programas Implementación Algoritmo Cuthill-McKee ' Public Sub IteraCuthilMcKee() nNumVarA = Sheets(HPAR).Cells(cFilaIniACM, cPColIxDat) nVertIni = Sheets(HPAR).Cells(cFilaIniACM, cPColIxDat + 1) ' nFilMaxMat = nNumVar nColMaxMat = nNumVar + 0 'cColMat ReDim MatrizVecinos(nNumVar, nNumVar) 'Inicializa Matriz de vecinos ReDim MatrizGradosCM(nNumVar, 4) ' '+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 'Comienzo Reordenamiento de Vértices por Método Cuthill-McKee (Pasos 1 al 2) ' Call CalculaParametrosMatriz(MatrizIniCM) nBandaMaxI = nBandaMax nNumIter = 1 pColEtiq = 0 pColGrado = 0 ' Erase MatrizResCM ReDim MatrizResCM(nFilMaxMat, nColMaxMat) 'Redimensiona Matriz de trabajo ReDim ListaSec(0, nNumVar + 1) 'Redimensiona Lista de Secuencias ReDim ListaVec(0, nNumVar + 1) 'Redimensiona Lista de Secuencias ReDim MatrizTablaCM(nNumVar * nNumVar, 4) 'Redimensiona Tabla Registro de Resultado ' nVertIter = nVertIni ListaSec(0, 1) = nVertIni 'Coloca Vértice inicial el Lista de Secuencias ListaSec(0, 0) = 1 'Inicializa Puntero Final de Lista de secuencias ListaSec(0, nNumVar + 1) = 1 'Inicializa Puntero Inicial de Lista de Secuencia MatrizResCM(nVertIter, pColEtiq) = -1 'Etiqueta Vértice Inicio Do nVertIter = ListaSec(0, ListaSec(0, nNumVar + 1)) 'Lee vértice a verificar de Lista de Secuencias '

Tabla 26. Programas desarrollados para Cuthill-McKee.



'Recorre Lista de Vecinos del Vértice bajo prueba ReDim ListaVec(0, nNumVar + 1) 'Redimensiona Lista de Secuencias ListaVec(0, 0) = 0 'Inicializa Contador de Lista de Vecinos nGradoVert = Abs(MatrizVecinos(nVertIter, pColGrado)) 'Obtiene grado del vértice If nGradoVert > 0 Then For I = 1 To nGradoVert nVec = MatrizVecinos(nVertIter, I) If MatrizVecinos(nVec, pColGrado) > 0 Then 'Verifica si Vértice i ha sido etiquetado 'Vecino no ha sido etiquetado MatrizVecinos(nVec, pColGrado) = _ Abs(MatrizVecinos(nVec, pColGrado)) * -1 'Marca como Etiquetado Vértice vecino ListaVec(0, ListaVec(0, 0) + 1) = nVec ListaVec(0, 0) = ListaVec(0, 0) + 1 'Incrementa contador de Lista de Vecinos If ListaVec(0, 0) > nNumVar Then Stop End If End If Next I If ListaVec(0, 0) <> 0 Then 'Verifica si tiene vecinos 'Tiene vecinos, se ordenan según su grado Call OrdenaVertVec(nVertIter) MatrizVecinos(nVertIter, pColGrado) = _ Abs(MatrizVecinos(nVertIter, pColGrado)) * -1 'Marca como Etiquetado Vértice bajo Prueba 'ListaSec(0, nNumVar + 1) = ListaSec(0, nNumVar + 1) + 1 'Incrementa puntero inicio de Lista de Secuencias Else 'No tiene vecinos o ya fueron etiquetados 'nNumIter = nNumIter + 1 'ListaSec(0, nNumVar + 1) = ListaSec(0, nNumVar + 1) + 1 'Incrementa puntero inicio de Lista de Secuencias End If End If ' If ListaVec(0, 0) <> 0 Then 'Actualiza nuevas Etiquetas de Vértices nPosSec = ListaSec(0, nNumVar + 1) nPosVec = 1 For j = nPosSec To ListaSec(0, 0) nVec = ListaSec(0, j) 'ListaVec(0, nEtq) If Len(MatrizResCM(nVec, pColEtiq)) = 0 Then MatrizResCM(nVec, pColEtiq) = j 'nEtq + 1 If MatrizResCM(nVec, pColEtiq) < 0 Then Stop End If End If Next j End If ' ListaSec(0, nNumVar + 1) = ListaSec(0, nNumVar + 1) + 1 'Incrementa puntero inicio de Lista de Secuencias ' Call EscribirDatosIterCM 'Stop Loop While ListaSec(0, 0) < nNumVar 'Final de Reordenación de Vértices




nPuntSec = 1 Do nEtqVVert = ListaSec(0, nPuntSec) 'Lee etiqueta vieja nGrado = Abs(MatrizVecinos(nEtqVVert, pColGrado)) 'Obtiene Grado del Vértice nEtqNVert = nPuntSec 'Obtiene nueva Etiqueta MatrizResCM(nEtqNVert, nEtqNVert) = Abs(nEtqVVert) 'Coloca etiqueta Vieja en la Diagonal nueva nPunt = 1 Do nVec = MatrizVecinos(nEtqVVert, nPunt) 'Obtiene Vecino de Vértice nEtqVec = Abs(MatrizResCM(nVec, pColEtiq)) 'Obtiene Etiqueta de Vécino nModo = 0 'Modo de relleno: 1= Filas, 2= Columnas If nVec >= nEtqVVert Then 'Vecino mayor que vértice, Lee por Filas, Columna fija nValor = MatrizIniCM(nVec, nEtqVVert) 'Obtiene Valor de Fila nModo = 1 Else 'Vecino menor que Vértice, Lee por Columnas, fila fija nValor = MatrizIniCM(nEtqVVert, nVec) 'Obtiene Valor de Columna nModo = 2 End If ' 'Esctritura de Valor en nueva localización If nEtqVec >= nEtqNVert Then If nEtqVec = nEtqNVert Then MatrizResCM(nEtqVVert, nEtqNVert) = nValor Else MatrizResCM(nEtqVec, nEtqNVert) = nValor End If Else MatrizResCM(nEtqNVert, nEtqVec) = nValor End If nPunt = nPunt + 1 Loop While nPunt < nGrado + 1 nPuntSec = nPuntSec + 1 Loop While nPuntSec < nNumVar + 1 ' End Sub ' Public Sub OrdenaVertVec(nVertIter) pColGF = nNumVar + 1 pColGC = nNumVar + 2 'Tiene Vecinos se ordena según grados de manera ascendente ' For w = 1 To ListaVec(0, 0) - 1 'Obtiene primer vecino nVec = ListaVec(0, w) nGradoVec = Abs(MatrizVecinos(nVec, 0)) 'Obtiene grado de Primer Vecino nPos = w ' For k = w + 1 To ListaVec(0, 0) nVec1 = ListaVec(0, k) If Len(nVec1) <> 0 Then 'Verifica si vértice tiene vecinos




'Tiene vecino(s) nGradoVec1 = Abs(MatrizVecinos(nVec1, 0)) 'Obtiene grado de i-ésimo Vecino If nGradoVec > nGradoVec1 Then 'Intercambia posición ListaVec(0, k) = nVec ListaVec(0, nPos) = nVec1 nPos = k End If Else 'No tiene Vecinos Exit For End If Next k 'Transfiere Vértices Vecinos a Lista de Secuencias ListaSec(0, ListaSec(0, 0) + w) = ListaVec(0, w) ' Next w ListaSec(0, ListaSec(0, 0) + w) = ListaVec(0, w) 'Transfiere último Vecino a Lista de Secuencias ListaSec(0, 0) = ListaSec(0, 0) + ListaVec(0, 0) 'Incrementa puntero Final de Secuencias End Sub ' Public Sub CalculaParametrosMatriz(MatrizTemp) 'Cálcula Grado de Matriz, por Filas y Columnas ReDim MatrizGradosCM(nNumVar, 4) 'Inicializa Matriz de Grados y Ancho de Banda ReDim MatrizVecinos(nNumVar, nNumVar) 'Inicializa Matriz de Vecinos ' pCol = 1 pColGF = pCol pColGC = pCol + 1 pColEp = pCol + 2 pColBe = pCol + 3 ' nBanda = 0 nBandaMax = 0 nContorno = 0 MatrizGradosCM(0, 0) = 0 ' For nVert = 1 To nNumVar 'Grado por Fila bFlag = True MatrizGradosCM(nVert, pColGF) = 0 'Inicializa Grado Fila For pCol = 1 To nVert If pCol <> nVert Then If Len(MatrizTemp(nVert, pCol)) <> 0 Then 'Verifica si existe un elemento 'Existe Adyacencia en Columna MatrizVecinos(nVert, MatrizVecinos(nVert, 0) + 1) = pCol 'Almacena Vecino MatrizVecinos(nVert, 0) = MatrizVecinos(nVert, 0) + 1 'Incrementa Contador de Vecinos MatrizGradosCM(nVert, pColGF) = MatrizGradosCM(nVert, pColGF) + 1 'Incrementa contador grados por filas If bFlag Then 'Stop 'nEp = pCol




MatrizGradosCM(nVert, pColEp) = pCol 'Almacena Ei nBanda = nVert - MatrizGradosCM(nVert, pColEp) 'Calcula Banda MatrizGradosCM(nVert, pColBe) = nBanda 'Almacena Banda If nBanda > nBandaMax Then 'Verifica si es máxima banda nBandaMax = nBanda 'Actualiza Máx. Banda End If bFlag = False End If End If End If Next pCol 'Grado por Columna MatrizGradosCM(nVert, pColGC) = 0 'Inicializa Grado Columna For pFil = nVert + 1 To nNumVar If Len(MatrizTemp(pFil, nVert)) <> 0 Then 'Verifica si existe un elemento 'Existe Adyacencia en Fila MatrizVecinos(nVert, MatrizVecinos(nVert, 0) + 1) = pFil 'Almacena Vecino MatrizVecinos(nVert, 0) = MatrizVecinos(nVert, 0) + 1 'Incrementa Contador de Vecinos MatrizGradosCM(nVert, pColGC) = MatrizGradosCM(nVert, pColGC) + 1 'Incrementa contador grados por filas If bFlag Then MatrizGradosCM(nVert, pColEp) = pFil - 1 'Almacena Ei 'Calcula los Ancho de Banda nBanda = nVert - MatrizGradosCM(nVert, pColEp) 'Calcula Banda MatrizGradosCM(nVert, pColBe) = nBanda 'Almacena Banda If nBanda > nBandaMax Then 'Verifica si es máxima banda nBandaMax = nBanda 'Actualiza Máx. Banda End If bFlag = False End If End If Next pFil MatrizGradosCM(nVert, 0) = MatrizGradosCM(nVert, pColGF) _ + MatrizGradosCM(nVert, pColGC) 'Almacena Grado del Vértice nContorno = nContorno + MatrizGradosCM(nVert, 0) Next nVert MatrizGradosCM(0, 0) = nContorno - 1 ' End Sub ' Public Sub LeerDatosMatrizCM() 'Revisar nNumVar = Sheets(HPAR).Cells(cFilaIniACM, cPColIxDat + 0) ReDim MatrizIniCM(nNumVar, nNumVar) With UFProyecto.MSHFlexGrid1 pFilMat = .Rows - 1 pColMat = .Cols - 1 For I = 1 To pFilMat For j = 1 To pColMat nValorMat = .TextMatrix(I, j) If Len(nValorMat) <> 0 Then If IsNumeric(nValorMat) Then MatrizIniCM(I, j) = CDbl(nValorMat)




MatrizIniCM(I, j) = nValorMat End If End If Next j Next I End With End Sub ' ' '*********************************************************************************************************************** ' 'Nombre Procedimiento: Calcula Contorno ' 'Objeto: Rutina para selecciona nodo inicial de CUTHILL-McKEE ' 'Entrada(s): Combo Box: CBNodoIniCM ' ' 'Salida(s): ' 'Estatus: Lista ' 'Ultima Revisión: 17/03/2012 ' 'Comentarios: ' '*********************************************************************************************************************** 'Public Sub CalculaContorno() pCol = 1 pColGF = pCol pColGC = pCol + 1 ' 'If Not (FlagIterCM) Then ' Call LeerDatosMatrizCM Call CalculaParametrosMatriz(MatrizIniCM) UFProyecto.TBContornoICM.Value = MatrizGradosCM(0, 0) ' UFProyecto.TBBandaCMI.Value = nBandaMax 'End If ' ' If FlagIterCM Then 'Matriz Resultante ' Call CalculaParametrosMatriz(MatrizResCM) ' UFProyecto.TBBandaCMR.Value = nBandaMax ' nContornoF = MatrizGradosCM(0, 0) ' UFProyecto.TBContornoFCM.Value = MatrizGradosCM(0, 0) nVert = 2 nContornoF = 0 Do pFila = nVert pCol = nVert For I = pFila + 1 To nNumVar


Trabajo Práctico: Métodos Numéricos Iterativos TABLA DE CONTENIDO


If Len(MatrizResCM(I, pCol - 1)) <> 0 Then If Len(MatrizResCM(I, pCol)) = 0 Then MatrizResCM(I, pCol) = 0 End If nContornoF = nContronoF + 1 End If Next I nVert = nVert + 1 Loop While nVert <= nNumVar End If ' End Sub '


7.1.6.3 Programas Implementación Modelo Grafos de Eliminación ' Public Sub IterarMGE() Const tMensaje = "¿DESEA CONTINUAR ITERACIÓN?" Const tTítulo = "MODELO GRAFOS DE ELIMINACIÓN" Const tEstilo = vbYesNo + vbQuestion + vbDefaultButton2 nNumVar = Sheets(HPAR).Cells(cFilaIniMGE, cPColIxDat) nVertIter = Sheets(HPAR).Cells(cFilaIniMGE, cPColIxDat + 1) ReDim MatrizGrafos(nNumVar, 2) nFilMaxMat = nNumVar nColMaxMat = nNumVar 'cColMat UFProyecto.CBContinuarMGE.Visible = True UFProyecto.CBPararMGE.Visible = True FlagContinuarMGE = True FlagPararMGE = True FlgVecinos = False Call LimpiaHojaMGE(1) Call IniMSHFlexGrid7 ' '+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 'Comienzo Eliminación de Vértices por Modelo Grafos de Eliminación ' 'Call CalculaParametrosMatrizMGE(MatrizMGEIni, nNumVar) nNumIter = 0 pColEtiq = 0 pColGrado = 0 FlagIterMGE = False ' MatrizMGERes = MatrizMGEIni 'Transfiere matriz inicial a Matriz resultados Call EscribeDatosIteracionMGE(MatrizMGERes, nNumIter) 'Muestra Matriz Inicial Call CalculaParametrosMatrizMGE(MatrizMGERes, nNumVar) Call EscribeTablaIteracionMGE(nNumIter) UFProyecto.LMatrizH.Caption = "Matriz H" & nNumIter UFProyecto.TBNumIterMGE.Value = nNumIter '

Tabla 33. Programas desarrollados para Modelo Grafos de Eliminación.



Do nCont = nCont + 1 DoEvents If Not (FlagPararMGE) Then Exit Sub End If Loop While FlagContinuarMGE ' 'Call DibujarGrafosMGE(MatrizMGERes, nNumIter) 'nNumIter = nNumIter + 1 nNumVarMEG = nNumVar Do UFProyecto.CBContinuarMGE.Visible = True UFProyecto.CBPararMGE.Visible = True FlagContinuarMGE = True FlagPararMGE = True ' ReDim ListaVec(0, nNumVar) 'Redimensiona Lista de Vecinos ListaVec(0, 0) = 0 'Inicializa Puntero Inicio Lista de Vecinos nGrado = MatrizVecinos(nVertIter, pColGrado) 'Obtiene grado de vértice MatrizMGERes(nVertIter, nVertIter) = "" 'Elimina diagonal MatrizVecinos(nVertIter, pColGrado) = _ Abs(MatrizVecinos(nVertIter, pColGrado)) * -1 'Marca Vértice como eliminado 'Obtiene lista de Vecinos de Vértice For I = 1 To nGrado nVec = MatrizVecinos(nVertIter, I) If MatrizVecinos(nVec, pColGrado) > 0 Then 'Verifica si tiene vecinos 'Tiene Vecinos ListaVec(0, I) = nVec 'Coloca vecino en lista vecinos ListaVec(0, 0) = ListaVec(0, 0) + 1 'Incrementa contador de vecinos End If Next I ' If ListaVec(0, 0) > 0 Then 'Verifica que vértice tiene Vecinos FlgVecinos = True 'Elimina Adyacencias de Vértice For I = 1 To ListaVec(0, 0) nVec = ListaVec(0, I) MatrizMGERes(nVertIter, nVec) = "" 'Anula diagonal superior MatrizMGERes(nVec, nVertIter) = "" 'Anula diagonal inferior Next I 'Crea Vértices de relleno, entre vecinos del vértice eliminado For I = 1 To ListaVec(0, 0) - 1 nVec = ListaVec(0, I) For j = I + 1 To ListaVec(0, 0) nVecNext = ListaVec(0, j) If Len(nVecNext) <> 0 Then 'Verifica que exista vecino siguiente If Len(MatrizMGERes(nVec, nVecNext)) = 0 Or _ MatrizMGERes(nVec, nVecNext) = cCharRelleno Then MatrizMGERes(nVec, nVecNext) = cCharRelleno MatrizMGERes(nVecNext, nVec) = cCharRelleno End If End If Next j




Next I ' With UFProyecto.MSHFlexGrid7 .TextMatrix(nNumIter + 1, 1) = "V" & nVertIter ' If ListaVec(0, 0) <> 0 Then For I = 1 To nGrado nVec = ListaVec(0, I) .TextMatrix(nNumIter + 1, 2) = .TextMatrix(nNumIter + 1, 2) & "V" & nVec & ", " Next I .TextMatrix(nNumIter + 1, 2) = Left(.TextMatrix(nNumIter + 1, 2), _ Len(.TextMatrix(nNumIter + 1, 2)) - 2) End If ' End With FlgVecinos = False ' Call EscribeDatosIteracionMGE(MatrizMGERes, nNumIter + 1) Call CalculaParametrosMatrizMGE(MatrizMGERes, nNumVar) Call EscribeTablaIteracionMGE(nNumIter + 1) End If ' nNumIter = nNumIter + 1 UFProyecto.LMatrizH.Caption = "Matriz H" & nNumIter UFProyecto.TBNumIterMGE.Value = nNumIter ' nVertIter = nVertIter + 1 nCont = 0 ' Do nCont = nCont + 1 DoEvents If Not (FlagPararMGE) Then Exit Sub End If Loop While FlagContinuarMGE ' Loop While nVertIter < nNumVar ' FlagIterMGE = True UFProyecto.CBContinuarMGE.Visible = False UFProyecto.CBPararMGE.Visible = False FlagContinuarMGE = False FlagPararMGE = False End Sub '




7.1.6.4 Programas Algoritmo de Grado Mínimo ' Public Sub IterarAMG() nNumVar = Sheets(HPAR).Cells(cFilaIniAMG, cPColIxDat) nVertIter = Sheets(HPAR).Cells(cFilaIniAMG, cPColIxDat + 1) ReDim MatrizGrafos(nNumVar - 1, nNumVar + 1) ReDim MatrizTrabajo(nNumVar - 1, nNumVar + 1) nFilMaxMat = nNumVar nColMaxMat = nNumVar 'cColMat UFProyecto.CBContinuarAMG.Visible = True UFProyecto.CBPararAMG.Visible = True FlagContinuarAMG = True FlagPararAMG = True FlgVecinos = False Call IniMSHFlexGrid10 ' '+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 'Comienzo Eliminación de Vértices por Modelo Algoritmo Mínimo Grado ' nNumIter = 0 pColEtiq = 0 pColGrado = 0 FlagIterAMG = False nNumVarAMG = nNumVar FlagPrimero = True ' MatrizAMGRes = MatrizAMGIni 'Transfiere matriz inicial a Matriz resultados Call CalculaParametrosMatrizAMG(MatrizAMGRes, nNumVarAMG) UFProyecto.LTituloAMG.Visible = True UFProyecto.LTituloAMG.Caption = "AMG PASO: " & nNumIter UFProyecto.TBNumIteracionesAMG.Value = nNumIter Call IniMSHFlexGrid10 ' Do nCont = nCont + 1 DoEvents If Not (FlagPararAMG) Then GoTo SalidaParar End If Loop While FlagContinuarAMG ' Do UFProyecto.CBContinuarAMG.Visible = True UFProyecto.CBPararAMG.Visible = True FlagContinuarAMG = True FlagPararAMG = True ' ReDim ListaVec(0, nNumVar) 'Redimensiona Lista de Vecinos ListaVec(0, 0) = 0 'Inicializa Puntero Inicio Lista de Vecinos ' 'Verificar Mínimo Grado

Tabla 36. Programas desarrollados para Algoritmo de Grado Mínimo.



nGradoMenor = nNumVar * nNumVar + 1 For I = 1 To nNumVar If MatrizVecinos(I, pColGrado) < nGradoMenor And Len(MatrizVecinos(I, pColGrado)) <> 0 Then 'Obtiene grado de vértice nGradoMenor = MatrizVecinos(I, pColGrado) nVertIter = I End If Next I If FlagPrimero Then UFProyecto.TBVerticeIAMG.Value = nVertIter FlagPrimero = False End If MatrizVecinos(nVertIter, pColGrado) = "" MatrizAMGRes(nVertIter, nVertIter) = "" 'Elimina diagonal ' 'Obtiene lista de Vecinos de Vértice For I = 1 To nGradoMenor nVec = MatrizVecinos(nVertIter, I) If MatrizVecinos(nVec, pColGrado) > 0 Then 'Verifica si tiene vecinos 'Tiene Vecinos ListaVec(0, I) = nVec 'Coloca vecino en lista vecinos ListaVec(0, 0) = ListaVec(0, 0) + 1 'Incrementa contador de vecinos End If Next I ' If ListaVec(0, 0) > 0 Then 'Verifica que vértice tiene Vecinos FlgVecinos = True 'Elimina Adyacencias de Vértice For I = 1 To ListaVec(0, 0) nVec = ListaVec(0, I) MatrizAMGRes(nVertIter, nVec) = "" 'Anula diagonal superior MatrizAMGRes(nVec, nVertIter) = "" 'Anula diagonal inferior Next I ' With UFProyecto.MSHFlexGrid10 .TextMatrix(nNumIter + 1, 1) = "V" & nVertIter MatrizTrabajo(nNumIter + 1, 1) = nVertIter 'Almacena Vértice Iteración .TextMatrix(nNumIter + 1, 2) = nGradoMenor MatrizTrabajo(nNumIter + 1, 0) = nGradoMenor 'Almacena Grado del Vértice ' If ListaVec(0, 0) <> 0 Then For I = 1 To nGradoMenor nVec = ListaVec(0, I) .TextMatrix(nNumIter + 1, 3) = .TextMatrix(nNumIter + 1, 3) & "V" & nVec & ", " MatrizTrabajo(nNumIter + 1, I + 1) = nVec Next I .TextMatrix(nNumIter + 1, 3) = Left(.TextMatrix(nNumIter + 1, 3), _ Len(.TextMatrix(nNumIter + 1, 3)) - 2) End If ' End With FlgVecinos = False Call CalculaParametrosMatrizAMG(MatrizAMGRes, nNumVar) End If




' nNumIter = nNumIter + 1 UFProyecto.LTituloAMG.Caption = "AMG PASO: " & nNumIter UFProyecto.TBNumIteracionesAMG.Value = nNumIter ' nCont = 0 Do nCont = nCont + 1 DoEvents If Not (FlagPararAMG) Then GoTo SalidaParar End If Loop While FlagContinuarAMG ' Loop While nNumIter < nNumVar - 1 ' FlagIterAMG = True SalidaParar: UFProyecto.CBContinuarAMG.Visible = False UFProyecto.CBPararAMG.Visible = False FlagContinuarAMG = False FlagPararAMG = False End Sub '


7.2. CONCEPTOS PRELIMINARES

Para el desarrollo de este trabajo se utilizaron diferentes conceptos básicos de los temas aquí tratados. Para su mayor comprensión, y debido a la importancia que poseen, se hace en este apartado un breve repaso sobre las definiciones y propiedades de dichos conceptos, buscando con ello que el documento sea autocontenido

7.2.1 SISTEMA DE ECUACIONES LINEALES (SEL) Un sistema de ecuaciones lineales es un conjunto de m ecuaciones con n incógnitas, cuya solución es un conjunto de valores para las incógnitas con el que se satisfacen todas las ecuaciones. En nuestro caso se asumirá que siempre hay la misma cantidad de ecuaciones que de incógnitas (matriz nxn), para los cuales hay una única solución, cuando ésta existe. En el planteamiento matemático de muchos problemas realistas los sistemas de ecuaciones algebraicas, y de una manera especial los lineales, aparecen de manera natural. También se presentan con frecuencia cuando se hace una discretización de ecuaciones diferenciales ordinarias y en derivadas parciales. Para hallar la solución al sistema con ayuda de un computador se utilizan diferentes métodos. Para el manejo del sistema se hace uso de una matriz que representa los coeficientes de las



incógnitas en cada ecuación, un vector de términos independientes y un vector solución, como lo muestra el siguiente ejemplo.

A x b

Sistemas Ecuación Inicial Representado de manera Matricial como Ax = b Figura 21. Sistema de Ecuación Lineal representado como Matriz.

El objetivo es encontrar los valores del vector x mediante algún método numérico. La matriz de coeficientes A puede tener diferentes propiedades que pueden ser explotadas en la resolución del sistema. Para mayor comprensión se explican algunas propiedades con detalle.

7.2.2 MATRIZ TRIANGULAR Una matriz es Triangular Superior (UPPER) si cumple que 0,, jiji aji . Es decir, cada

elemento de A ubicado por debajo de la diagonal principal tiene valor nulo. De igual manera se puede decir que matriz es Triangular Inferior (LOWER) cuando cumple que

0,, jiji aji . Los siguientes son ejemplos de Matriz Triangular Inferior (L) y Superior (U).

Figura 22. Matriz Triangular Superior (U) e Inferior (L)..

7.2.3 MATRIZ SIMÉTRICA Una matriz es simétrica si se cumple que aij = aji. Es decir, cada elemento de A ubicado en la fila i, columna j, es igual al elemento ubicado en la fila j, columna i. En este tipo de matrices se pueden ahorrar espacios de memoria en su almacenamiento, ya que con almacenar los elementos localizados por debajo de la diagonal principal de la misma (triángulo inferior), se conocen los valores de los elementos ubicados por encima de la diagonal superior (triángulo superior), y viceversa. Del mismo modo podemos ahorrar operaciones al aplicar algoritmos que exploten esta estructura.



7.2.4 MATRIZ DEFINIDA POSITIVA

Una matriz nxnRA es definida positiva si es simétrica y 00 xyRxxAX nT . Los sistemas

con matrices asociadas definidas positivas constituyen una de las clases más importantes de problemas Ax = b [4]. Las matrices definidas positivas tienen una diagonal de peso, es decir con valores relativamente grandes. Además, las matrices definidas positivas cumplen las siguientes propiedades:

1) Una matriz A definida positiva es no singular. 2) Si una matriz A es definida positiva entonces todas sus submatrices principales son

definidas positivas. En particular, todas las entradas de la diagonal son positivas. 3) Si una matriz A es definida positiva entonces existe una factorización A = LDMT, y la

matriz diagonal D tiene valores positivos. 4) Si una matriz A es simétrica y definida positiva entonces existe una matriz triangular

inferior única G con entradas positivas en la diagonal, tal que A = GGT (factorización de Cholesky).

5) Una matriz simétrica A es definida positiva si y sólo si sus primeras submatrices principales tienen determinante positivo.

7.2.5 MATRIZ INDEFINIDA Una matriz A es considerada indefinida cuando su forma cuadrática XT Ax toma valores tanto positivos como negativos. Aunque la matriz A puede tener una factorización LDLT, las entradas en los factores pueden tener una magnitud arbitraria.

7.2.6 MATRIZ DIAGONALMENTE DOMINANTE Y DIAGONAL ESTRICTAMENTE DOMINANTE 7.2.6.1 Matriz Diagonalmente Dominante Matriz Diagonalmente Dominante: si en cada uno de los renglones, el valor absoluto del elemento de la diagonal principal es mayor que la suma de los valores absolutos de los elementos restantes del mismo renglón. A veces la matriz de un sistema de ecuaciones no es diagonalmente dominante pero cuando se cambian el orden de las ecuaciones y las incógnitas el nuevo sistema puede tener matriz de coeficientes diagonalmente dominante.

7.2.6.2 Matriz Diagonal Estrictamente Dominante En matemáticas, y concretamente en álgebra lineal, una matriz es Diagonal Estrictamente Dominante, cuando lo es por filas o por columnas. 1. Lo es por filas cuando, para todas las filas, el valor absoluto del elemento de la diagonal de

esa fila es estrictamente mayor que la suma de los valores absolutos del resto de elementos de esa fila.

2. Lo es por columnas cuando, para todas las columnas, el valor absoluto del elemento de la diagonal de esa columna es estrictamente mayor que la suma de los valores absolutos del resto de elementos de esa columna.

Formalmente, se dice que la matriz A de n x n es Estrictamente Diagonal Dominante cuando se satisface:



Se puede enunciar a partir de esta definición el siguiente teorema de convergencia aplicable a los procesos iterativos de Jacobi y Gauss Seidel: Sea A una matriz cuadrada, si A es diagonal dominante, los métodos iterativos de Jacobi y Gauss-Seidel convergen a la solución del sistema de ecuaciones Ax=b.

7.2.7 MATRIZ DISPERSA Una matriz A se considera dispersa cuando un alto porcentaje de sus elementos son ceros. En nuestro caso consideraremos las matrices dispersas en cuanto pueda optimizarse la computación de la misma mediante el uso de estructuras especiales para el almacenamiento. Las matrices dispersas nos ahorran operaciones en las que su resultado se conoce de antemano, como productos y sumas con ceros. Hay muchas aplicaciones que dan lugar a tener que manejar matrices que tienen gran cantidad de sus elementos nulos. Estas matrices se denominan matrices dispersas. Se puede dar una definición informal de matriz dispersa, como aquella matriz que tiene suficientes ceros de forma que vale la pena tener esto en cuenta. De este modo, evitando operaciones sobre los elementos que son cero se ahorra tiempo de computación y no guardando los elementos nulos se ahorra en memoria. Para manejar estas matrices se trata de aprovechar el hecho que tienen gran cantidad de elementos nulos para no almacenar dichos elementos, con lo que ello supone de ahorro en memoria y en tiempo de computación. Para poder trabajar con las matrices sin almacenar los elementos nulos se utilizan distintos esquemas de almacenamiento.

7.2.7.1 Matrices en Banda Uno de los tipos de matrices dispersas más habituales. Son matrices cuyos elementos están contenidos en una estrecha banda, normalmente alrededor de la diagonal principal de la matriz. Surgen muy frecuentemente en modelos matemáticos de situaciones físicas donde sólo se influyen las variables que representan magnitudes cercanas en el espacio, en el tiempo, etc. En matemáticas una matriz se le llama Matriz Banda cuando es una matriz donde los valores no nulos son confinados en un entorno de la diagonal principal, formando una banda de valores no nulos que completan la diagonal principal de la matriz y más diagonales en cada uno de sus costados. Escrito formalmente, una matriz n×n A=(ai,j ) es una matriz banda si todos sus elementos son cero fuera de una zona diagonal cuyo rango se determina por las constantes k1 y k2:



Los valores k1 y k2 son el semiancho de banda izquierdo y derecho respectivamente. El ancho de banda de una matriz es k1 + k2 + 1, y se puede definir como el número menor de diagonales adyacentes con valores no nulos. Una matriz banda con k1 = k2 = 0 es una matriz diagonal Una matriz banda con k1 = k2 = 1 es una matriz tridiagonal; cuando k1 = k2 = 2 se tiene una matriz pentadiagonal y así sucesivamente. Una matriz banda con k1 = k2 = p, dependiendo del número p, se le puede llamar matriz p-banda, formalmente se puede definir como:

Una matriz con k1 = 0, k2 = n−1, se obtiene la definición de una matriz triangular inferior. De forma similar, para k1 = n−1, k2 = 0, se obtiene la definición de una matriz triangular superior. Ejemplo:

La matriz anterior tiene un ancho de banda de 3 y recibe el nombre especial de Matriz Tridiagonal.

7.2.7.1.1 Definición 1: Ancho de Banda Una matriz mxnRA se dice tiene un ancho de banda de filas w si:

)1(,1

iimi

flwimáxw wi

Donde, wi es el ancho de banda de la fila i, }0:.{ ijajmínfi y }0:.{ ijajmáxli Para que sea de interés estudiarla como dispersa, w << n. De cada fila i se almacenan todos los elementos de subíndice ij tales que lijfi .

7.2.7.1.2 Definición 2: Envolvente de una Matriz El conjunto de elementos que forman la envolvente de una matriz A, Env(A), es:

}1;:),{()( nilijfijiAEnv La envolvente de la matriz A, es la que forman los elementos inscritos en el polígono, ver ¡Error! No se encuentra el origen de la referencia..



Figura 23. Envolvente Matriz A.

7.2.7.1.3 Definición 3: Ancho de Banda de una Matriz Simétrica (SEMIBANDA)

El Ancho de Banda (o Semibanda) β, de una Matriz Simétrica B y nxnRB , se define como:

)1(,1

ini

fimáx i

donde, βi es el ancho de banda de la fila i (o simplemente el ancho de banda i-ésimo) de B. De forma similar a como se definió anteriormente, la envolvente de una Matriz Simétrica B, Env(B), se define como:

}1;:),{()( nilijfijiBEnv

7.2.8 SISTEMAS DE GRAN DIMENSIÓN Los sistemas de ecuaciones se consideran de gran dimensión cuando se trabaja con miles de incógnitas y los costos de computación son elevados. En estos casos se debe prestar mucha atención a minimizar los errores de redondeo y truncamiento que puedan generar los algoritmos. Al mismo tiempo se desea minimizar los tiempos de ejecución y el almacenamiento en memoria, utilizando algoritmos eficientes y con soluciones adecuadas en tiempos aceptables. En problemas de ingeniería y aplicaciones reales aparecen frecuentemente sistemas de este tipo.



La resolución de sistemas de ecuaciones algebraicas que son lineales de gran dimensión subyace en la solución numérica de problemas de la mecánica del continuo y muchos otros problemas de ingeniería, llegando a constituir en muchos casos el principal factor de costo computacional.

7.2.9 REPRESENTACIÓN DE MATRICES CON GRAFOS La teoría de grafos constituye una herramienta bastante útil para la representación de matrices dispersas, ayudando en la búsqueda de precondicionadores y algoritmos paralelos. Un grafo se representa formalmente mediante dos conjuntos, un conjunto de vértices V = { v1, v2 …, vn } y un conjunto de aristas E formado por pares (vi, vj ) donde vi y vj son elementos de V. Así, VxVE . El grafo G = (E,V) puede representarse mediante un conjunto de puntos en el plano que representan el conjunto E y unidos por líneas que representan la relación V. Cuando esta relación es simétrica el grafo es no dirigido (figura 6b), y en otro caso se debe dar dirección a las relaciones mediante fl echas y se dice que el grafo es dirigido (figura 6a).

Figura 24.. Matriz Grafos de matrices dispersas 4x4.

En el caso de las matrices dispersas, el conjunto V representa las n incógnitas del sistema y E es una relación que indica que existe una arista del nodo i al nodo j cuando 0ija . Así pues, la arista representa la relación “la ecuación i incluye la incógnita j”. Cuando la matriz es simétrica el grafo es no dirigido. Una de sus aplicaciones puede verse en la implementación paralela de la eliminación Gaussiana, buscando las variables que son independientes en una cierta fase de la eliminación. Estas son variables que no dependen la una de la otra de acuerdo a la relación establecida en E. Así, las filas de dichas incógnitas pueden usarse como pivotes simultáneamente. En matrices diagonales cada incógnita es independiente, mientras que en una matriz densa todas dependen de todas; las matrices dispersas están entre ambos extremos.

7.2.9.1 Grafo de una Matriz Dispersa Hay una relación directa entre en patrón de una matriz dispersa y su grafo asociado.



Un grafo dirigido o digrafo consiste en un conjunto de nodos o vértices y aristas dirigidas entre los nodos.

Para una matriz cuadrada A, se asocia un nodo con cada fila. Si aij es un elemento no nulo (entrada) de una matriz dispersa, hay una arista dirigida del nodo i a j.

Matriz Dispersa Grafo Asociado

Figura 25. Grafo Asociado a una Matriz.

Para matrices simétricas, si hay una conexión del nodo i al nodo j, se tendrá también una conexión del nodo j al i. De este modo las matrices simétricas se representan mediante un grafo no dirigido.

Matriz Simétrica Grafo No Dirigido Asociado Figura 26.. Grafo Asociado a una Matriz.

7.3. MÉTODOS ITERATIVOS BÁSICOS

Los métodos iterativos parten de una solución inicial y van modificando sus valores hasta alcanzar una convergencia deseada cuando ésta sea posible. Se dividen en estacionarios y no estacionarios. Los métodos estacionarios son métodos clásicos como Jacobi, Gauss-Seidel o SOR y tienen una convergencia más lenta, aunque su programación es mucho más simple y son más fáciles de entender. Los métodos no estacionarios tienen una mayor convergencia. La utilización masiva de los ordenadores y el aumento constante de su capacidad y velocidad de cálculo, han permitido que los estudios científicos, tecnológicos y de ingeniería utilicen cada vez más modelos matemáticos para interpretar, simular y optimizar fenómenos de diversa complejidad, y que esos modelos crezcan extraordinariamente en magnitud y exactitud. Muchos de estos modelos conllevan enfrentarse con sistemas de ecuaciones de un tamaño tal -decenas o cientos de miles de variables- que hace sólo unos pocos años eran casi inimaginables que se pudiesen tratar.



7.3.1 ALGORITMO DE CUTHILL-MCKEE (CM) La teoría de grafos es una herramienta de gran utilidad para el estudio de los sistemas sparse (dispersos). La distribución de las entradas no nulas de una matriz puede ser representada mediante un grafo y ser utilizado este para visualizar lo que ocurre durante la computación. En el subcampo matemático de la teoría de matrices, el algoritmo de Cuthill-McKee es un algoritmo para reducir el ancho de banda de una matriz simétrica dispersa (es decir, la distancia máxima entre dos vértices adyacentes). El algoritmo invertido de Cuthill-McKee (RCM, por las siglas inglesas Reverse Cuthill-McKee) es el mismo algoritmo pero con los índices resultantes invertidos. En el ámbito práctico, emplear este último es generalmente una mejor solución. Dada una matriz simétrica A, si la entrada aij de A es distinta de cero, los nodos i y j están conectados en el grafo mediante una arista. La Eliminación Gaussiana en la matriz queda reflejada en el grafo al eliminar el nodo correspondiente y aparecer nuevas conexiones entre los nodos restantes, correspondiendo cada una de ellas a un fill-in en A. El método más ampliamente utilizado para la transformación en banda de una matriz sparse es el conocido con el nombre de Algoritmo de Cuthill-McKee (CM) [6]. La idea del algoritmo es muy simple: Si a es un vértice ya renumerado y b es un vértice no renumerado aún, conectado al vértice a mediante una arista en el grafo, para minimizar la anchura de la fila asociada a b es evidente que el vértice b se debe renumerar lo antes posible, inmediatamente después del vértice a.

7.3.1.1 Algoritmo Dada una matriz simétrica n×n, se visualiza como la matriz de adyacencia de un grafo. El algoritmo de Cuthill-McKee es entonces una renumeración de los vértices del grafo con el objetivo de reducir el ancho de banda de su matriz de adyacencia. El algoritmo produce una n-tupla ordenada R de vértices, que es el nuevo orden de los vértices.

1) Primero, se elige un vértice periférico x y se realiza la asignación R := ({x}). 2) A continuación, para i = 1, 2, ...; y se iteran las próximas instrucciones mientras |R| < n 3) Construir el conjunto de adyacencia Ai de Ri (siendo Ri el i-ésimo componente de R)

excluyendo aquellos vértices que ya estuvieran en R.

·\R: ii RAdyA ni ,.....,2,1 (3.2.1.1)

4) Ordenar Ai siguiendo una ordenación ascendente de los vértices. 5) Añadir Ai al conjunto resultado R.

En otras palabras, numerar los vértices de acuerdo a una particular búsqueda en anchura transversal, donde los vértices vecinos son visitados en orden de menor a mayor.



En la Figura 27. , se representa una Matriz Simétrica A y su grafo asociado. A la derecha, se representa la matriz A’, que ha sido reordenada mediante el algoritmo de Cuthill-McKee (CM). Se puede apreciar el reordenamiento en forma de banda de dicha matriz A’. Se ha elegido como inicial el vértice j (en un extremo del grafo y con pocas conexiones), aunque existen procedimientos más refinados para dicha elección (ver [10,14]).

Matriz Simétrica Inicial Grafo Asociado Matriz Reordenada

Figura 27. Ejemplo de aplicación del Algoritmo Cuthill-McKee.

7.3.1.2 Ordenamiento Cuthill-McKee Si las matrices son de estructura simétrica y se almacenan según un esquema de perfil o envolvente, también interesa poder disponer de un procedimiento de ordenación que compacte los elementos cerca de la diagonal principal de la matriz. Este es el caso del algoritmo de Cuthill-McKee. El resultado de aplicar a una matriz simétrica 35 × 35 este algoritmo se ilustra en la figura.

(a)

(b)

Figura 28. Ordenación de Ecuaciones por Algoritmo de Cuthill-McKee.

7.3.2 ALGORITMO DE CUTHILL-MCKEE INVERSO (RCM) El algoritmo de Cuthill-McKee proporciona un método sencillo para reordenar una matriz dispersa con objeto de reducir el efecto fill-in transformando la matriz en una matriz banda. La



ordenación resultante al invertir el algoritmo de Cuthill-Mckee resulta frecuentemente mejor que el original, en términos de reducción de perfil, manteniendo la anchura de banda.

7.3.2.1 Algoritmo Reordenación de Cuthil-McKee inverso 1. Construir el Grafo asociado a la matriz A, g(x) = (V, E) 2. Determinar un nodo inicial (pseudo-periférico) y renumerarlo como x1. 3. Renumerar los nodos conectados a xi en orden ascendente de grado. 4. Efectuar el ordenamiento inverso.

7.3.3 ALGORITMO DE GRADO MÍNIMO En el análisis numérico del algoritmo de grado mínimo es un algoritmo utilizado para permutar las filas y columnas de una matriz dispersa simétrica antes de aplicar la descomposición de Cholesky, para reducir el número de ceros no en el factor de Cholesky. Esto se traduce en reducción de los requerimientos de almacenamiento y los medios que el factor de Cholesky, o en ocasiones un factor de Cholesky incompleta utilizado como un preacondicionador (por ejemplo en el algoritmo de lo previamente gradiente conjugado) se puede aplicar con menos operaciones de aritmética. Algoritmos de grado mínimo se suele utilizar en el método de elementos finitos en la reordenación de los nodos se pueden realizar sólo en función de la topología de la malla, en lugar de los coeficientes de la ecuación diferencial parcial, resultando en ahorros por eficiencia en la misma malla se utiliza para una variedad de valores de los coeficientes. Si las filas y las columnas del mismo sistema se reordenan de acuerdo con el Algoritmo de Grado Mínimo (que se desarrolla en este trabajo) se obtiene un patrón de elementos distintos de cero como el de la siguiente figura.

(a)

(b)

Figura 29. Ordenación de Ecuaciones por Algoritmo de Grado Mínimo.

Para definir una ordenación óptima es necesario tener en cuenta la estructura de la matriz, el esquema que define cómo se almacena la matriz y el tipo de operaciones que con ella se van a realizar.

Trabajo Práctico: Métodos Numéricos Iterativos ESPECIFICACIONES DEL TRABAJO


8. ESPECIFICACIONES DEL TRABAJO

TRABAJO PRÁCTICO GRAFOS Y MATRICES (332)

LAPSO 2011-2 ESPECIFICACIONES: Este trabajo práctico se basará en las unidades 7 y 8, objetivo 6 del modulo II y en las unidades 10, 11 y 12, objetivos 8, 9 y 10 del módulo III; donde podrá utilizar lenguajes de programación o aplicaciones de paquetes matemáticos para resolver los ejercicios propuestos en el.

8.1. PLANTEAMIENTO DEL PROBLEMA

OBJETIVO 6 CRITERIO DE DOMINIO 1/1 1. La compañía manufacturera G & M descontinuó la producción de cierta línea de

productos, ésta medida creó un exceso considerable de capacidad de producción. La administración quiere dedicar este exceso a tres de sus productos, la siguiente tabla resume la disponibilidad en horas máquinas por semana según el tipo de máquina:

TIPO DE MÁQUINA TIEMPO DISPONIBLE (horas máquinas por semana)

RECTIFICADORA 150 FRESADORA 500 TORNO 350

Tabla 39. Disponibilidad en horas máquinas por semana según el tipo de máquina

El número de horas máquinas que se requieren para elaborar cada unidad de estos productos de la compañía G & M es:


1 2 3 RECTIFICADORA 3 0 6 FRESADORA 9 3 3 TORNO 4 5 0

Tabla 40. Número Horas-Máquinas por unidad de productos.

Analice los métodos de Jacobi y Gauss Seidel para resolver sistemas de ecuaciones lineales y responda lo siguiente: a) Dado el problema planteado anteriormente, construya el sistema de ecuaciones

asociado con el problema. b) De una breve explicación de los Algoritmos de Jacobi y Gauss- Seidel.



c) Reformule el sistema de ecuaciones encontrado en (a). d) Calcule los términos de la sucesión (los que considere necesarios), generada a partir del

punto Po = (20, 50, 15) e) Utilizando los algoritmos antes mencionados. (use tablas de resultados, donde señale los

valores obtenidos de cada iteración según el Algoritmo). f) Explique si la sucesión converge a que punto o no. g) De un análisis comparativo de los Algoritmos, según sus resultados y una conclusión sobre

cuál de los dos converge más rápido a la solución exacta. h) Analice los dos algoritmos y su incidencia en el problema de la Compañía Manufacturera

G & M. Observación: Se admite el uso de cualquier lenguaje de programación para realizar los cálculos de una forma más eficiente. En caso de utilizar las herramientas mencionadas, incluya como anexos en el informe la forma como fueron empleadas, así como el algoritmo del programa utilizado. OBJETIVO 8 CRITERIO DE DOMINIO 1/1 2. La compañía manufacturera M & G esta analizando los costos entre los diferentes estados

de un país obteniendo los siguientes resultados:

A B C D E F G H A - 4 - 6 - 3 - 6 B 4 - 2 - 4 - 3 - C - 2 - 5 - 2 - 3 D 6 - 5 - 1 - 6 - E - 4 - 1 - 7 - 1 F 3 - 2 - 7 - 1 - G - 3 - 6 - 1 - 3 H 6 - 3 - 1 - 3 -

Tabla 41. Análisis de Costo entre diferentes estados.

Analice el algoritmo de Cuthill – McKee y realice lo que se le indica a continuación: a) Construya el grafo asociado al problema. b) Halle la matriz dispersa asociada al grafo. c) Calcule el ancho de banda de la matriz. d) Aplique el algoritmo Cuthill – Mc kee e) Calcule el nuevo ancho de banda de la matriz. f) Análisis de los resultados obtenidos referidos a la Compañía Manufacturera G & M. OBJETIVO 9 CRITERIO DE DOMINIO 1/1 3. Dado el grafo de la Compañía Manufacturera G & M que obtuvo en el Objetivo No. 8.

Aplique el Modelo de Grafos de Eliminación a dicho grafo y de un Análisis de lo obtenido referido a la compañía.

OBJETIVO 10 CRITERIO DE DOMINIO 1/1



4. Aplique el algoritmo de Mínimo Grado al grafo logrado en el objetivo No. 8. De un análisis de lo obtenido referido a la compañía manufacturera G & M.

8.2. INSTRUCCIONES GENERALES SOBRE EL TRABAJO PRÁCTICO

El estudiante deberá resolver el trabajo individualmente y entregar un informe que contenga lo siguiente: Una introducción. Exposición detallada de la solución matemática de los problemas y la respuesta a todas las

preguntas. Presentación de los resultados con las debidas especificaciones. Análisis de los resultados obtenidos.

8.3. CRITERIO DE CORRECCIÓN

8.3.1 OBJETIVO NOS. 6, 8, 9, 10 Para considerar logrado los objetivos el estudiante debe presentar un informe que contenga todos los aspectos requeridos en estos objetivos y aplicar de forma correcta los algoritmos correspondientes. NOTA: El trabajo práctico debe ser remitido al nivel central (Coordinación de Ing. de Sistemas) única y exclusivamente a través de su Centro Local. NO HABRÁ PRORROGA, para la entrega de los mismos en la fecha establecida en el PLAN DE CURSO. Especialista de Contenido: Prof. Jesús Espinal Correo: [email protected]



ACRÓNIMOS Y SIGLAS

SIGLAS DESCRIPCIÓN SEL Solución de Ecuaciones Lineales SELS Solución de Ecuaciones Lineales Simultáneas SPARSE

FILL-IN (Relleno)

Una dificultad que se presenta durante el proceso de factorización de la matriz A es que dicho proceso origina entradas no nulas en posiciones de L que eran nulas en A. Este hecho se conoce con el nombre de efecto Fill-In, que implica un aumento de la demanda de almacenamiento, mayor número de operaciones y, por tanto, un incremento en los errores de redondeo.

matrices y grafos

Documents