GRAFO Y MATRICES

UNIVERSIDAD NACIONAL ABIERTA

AREA DE INGENIERIA

CARRERA INGENIERIA DE SISTEMAS

TRABAJO PRACTICO

ASIGNATURA: GRAFOS Y MATRICES

CODIGO: 332

NOMBRE DEL ESTUDIANTE: ERASMO RAFAEL VOLWEIDER M.

CEDULA DE IDENTIDAD: 8.896.291

CENTRO LOCAL: BOLIVAR

CODIGO DE CARRERA: 236

NUMERO DE ORIGINALES: 01

LAPSO: 2006-2

FECHA: ENERO DE 2007

FIRMA DEL ESTUDIANTE

INTRODUCCION

Con el propósito de cumplir con los requisitos para aprobar la asignatura Grafos y Matrices, código 332, se ha elaborado el presente informe que contempla el desarrollo y solución de los problemas planteados en el trabajo practico de la materia. El trabajo practico, esta relacionado con los objetivos 6, 8 , 9 y 10.

En el objetivo 6, se soluciona un sistema de ecuaciones mediante los métodos iterativos Jacobi y Gauss – Seidel. En el objetivo 8 se construye un grafo y la matriz dispersa a partir de una matriz de datos y se aplica al grafo el algoritmo de Cuthill – McKee. Y en los objetivos 9 y 10 se aplican al grafo el Modelo de Grafos de Eliminación y el Algoritmo de Mínimo Grado.

Se pretende no solo resolver las situaciones planteadas en cada objetivo; sino también que el conocimiento a obtener sea significativo para el estudiante, de lo cual se pueda aplicar luego en situaciones reales.

OBJETIVO 6

Dado el siguiente Sistema de Ecuaciones Lineales:

4x1 - x2 + x3 + 3x4 = 14

- x1 + 5x2 + x3 + x4 = -1

2x1 x2 + 4x3 + 2x4 = 18

x2 - x3 + 7x4 = 10

a. Una breve explicación de los Métodos de Jacobi y Gauss-Seidel.

De manera general, estos métodos parten de rescribir el sistema siguiendo al del punto fijo como: Ax = b, siendo A una matriz cuadrada de orden n; y luego buscar una matriz B y un vector C de tal forma de obtener una ecuación, equivalente a la anterior:

x = Bx + C (1)

La diferencia consiste en que en el punto fijo se trabaja con funciones reales, pero en los métodos iterativos se trabaja con matrices.

Siguiendo el método, para resolver el sistema, se parte de un vector inicial, el cual denominadores x(0), a fin de obtener una sucesión de vectores x(1), x(2), ... , x(m), convergente al vector solución x de (1).

Los métodos de Jacobi y Gauss-Seidel se basan en escribir el sistema de ecuaciones en la forma:

x1

x2

xn =

=

= (b1 – a21x2 – a31x3 –    – an1xn) / a11

(b2 – a12x1 – a32x3 –    – an2xn) / a22

(bn – a1nx1 – a2nx2 –    – ) / ann

Método Iterativo de Jacobi

Es llamado Método de la Iteraciones Simultaneas, porque en cada iteración k se usa completamente para calcular , así que al final del paso se tienen simultáneamente y .

La ecuación que define el Método de Jacobi o Método de las Iteraciones Simultaneas es la siguiente:

Para k >= 1, i = 1, ... ,n (2)

Método Iterativo de Gauss-Seidel

La modificación para el método de Jacobi fue hecha por Gauss y Seidel, los cuales obtuvieron una formula similar a (2) pero que aminoraba considerablemente un problema que presenta Jacobi. El problema de Jacobi consiste que en cada iteración k, se conocen algunas componentes del vector de aproximación a la solución x (m), la cuales, una vez finalizado ese paso, no vuelven a ser usadas para calcular las restantes, eso representa un problema computacional, puesto que son datos que permanecen ociosamente en la estructura de almacenamiento.

La ecuación obtenida por Gauss y Seidel, que define el Método de las Iteraciones Sucesivas o de Gauss-Seidel es la siguiente:

(3)

En ambos métodos para determinar cuando terminar de iterar se emplea la condición:

(4)

En el caso de nuestro problema se utilizó como criterio d convergencia 10-4

b. Calcule los primeros 3 términos de la sucesión a partir del punto P0 (0, -2, 2, 1) utilizando los algoritmos antes mencionados.

Para resolver este punto se elaboraron dos programas, de lo cual se obtuvieron los siguientes resultados:

METODO DE JACOBI

m X1(m) X2(m) X3(m) X4(m)

0 0 -2 2 1

1 1,75000 -0,80000 4,00000 2,00000

2 0,80000 -1,05000 2,62500 2,11429

3 0,99554 -0,98786 3,04286 1,95357

4 1,02714 -1,00018 3,02545 2,00439

5 0,99030 -1,00054 2,98423 2,00366

6 1,00106 -0,99952 3,00302 1,99782

7 1,00100 -0,99996 3,00056 2,00036

8 0,99960 -0,99998 2,99932 2,00007

9 1,00012 -0,99996 3,00016 1,99990

10 1,00004 -0,99999 2,99999 2,00002

11 0,99999 -0,99999 2,99997 2,00000

Vector Solución en 11 Iteraciones

0,99999 -0,99999 2,99997 2,00000

METODO DE GAUSS –SEIDEL

m X1(m) X2(m) X3(m) X4(m)

0 0 -2 2 1

1 1,75000 -0,45000 3,12500 1,93929

2 1,15179 -0,98250 2,95446 1,99099

3 1,02251 -0,98459 2,99325 1,99683

4 1,00792 -0,99643 2,99763 1,99915

5 1,00212 -0,99893 2,99936 1,99976

6 1,00061 -0,99970 2,99982 1,99993

7 1,00017 -0,99992 2,99995 1,99998

8 1,00005 -0,99998 2,99999 1,99999

9 1,00001 -0,99999 3,00000 2,00000

Vector Solución en 9 Iteraciones

1,00001 -0,99999 3,00000 2,00000

Los programas se desarrollaron en lenguaje Turbo Pascal 7.0. El primer programa, Csistecua.pas, crea un archivo con el sistema de ecuación cargado desde el teclado; el segundo, Jacobi.pas, resuelve el problema, permite ver y cambiar el vector inicial, el numero de iteraciones máxima a utilizar y el criterio de convergencia (4) a utilizar para determinar cuando terminar de iterar.

Claro esta que no solo se calcularon los tres primeros términos sino que se aprovecho el programa para determinar el numero de iteraciones necesarias para llegar a la convergencia.

c. Explique si la sucesión converge y a que punto o no y porque con cada algoritmo

Método de Jacobi

...