UNA Trabajo práctico: Grafos y Matrices (332)¶
Objetivo 6¶
Resuelva el sistema de ecuaciones lineales mostrado a continuación, aplicando los algoritmos de los Métodos de Jacobi y de Gauss-Seidel:
$$ \left\{ \begin{align*} -x_1 + 11x_2 - x_3 + 3x_4 &= 25 \\ 2x_1 - x_2 + 2x_3 - x_4 &= -11 \\ 10x_1 - x_2 + 2x_3 + 0x_4 &= 6 \\ 6x_1 + 3x_2 - x_3 - x_4 &= 15 \end{align*} \right. $$a. Elabore una breve explicación del algoritmo de los métodos de Jacobi y de Gauss-Seidel
El método de Jacobi busca resolver un sistema de ecuaciones lineales $Ax = B$ a partir de una aproximación inicial $x_0 = (x_1, ..., x_n)$, siendo $n$ el número de variables y también el número de ecuaciones en el sistema. El procedimiento consiste en despejar de cada ecuación una variable, es decir, $x_1$ se despeja de la primera ecuación, $x_2$ de la segunda, etc. A cada una de las expresiones resultantes se les introduce los valores de las variables de la aproximación inicial, y los resultados se utilizarán en la siguiente iteración. Este proceso se repite hasta que se alcanza un número máximo de iteraciones o hasta que se alcance alguna otra condición de convergencia apropiada.
El método de Gauss-Seidel es bastante similar al de Jacobi, con la diferencia de que para hallar la siguiente aproximación de $x_i$ se utilizan los últimos valores conocidos de las demás variables. Es decir, $x_1$ se calcula con los valores de la iteración anterior, mientras que $x_2$ se calcula con esos valores pero con el nuevo valor de $x_1$, y así sucesivamente.
A continuación se presenta la implementación en Python de estos procedimientos, usando la librería Pandas para mostrar la tabla de resultados:
import pandas as pd
# DEFINICIÓN DE DATOS ::..
# Los sistemas de ecuaciones lineales se representarán como un
# arreglo bidimensional. Es decir, su representación consiste
# en un arreglo cuyos ítems corresponden a cada fila del sistema,
# y cada fila es representada por un arreglo cuyos ítems son los
# coeficientes de cada variable y el valor constante.
# Sistema de ecuaciones del enunciado:
sist1 = [[-1, 11, -1, 3, 25],
[ 2, -1, 10, -1, -11],
[10, -1, 2, 0, 6],
[ 6, 3, -1, -1, 15]]
# Aproximación inicial de la solución:
x_0 = [0, 0, 0, 0]
# DEFINICIÓN DE FUNCIONES ::..
def aproximar_xi_jacobi(fila, i, xa):
"""Calcula el valor aproximado de x_i a partir de la
fila (ecuación lineal) dada y los valores anteriores
de las variables."""
# Separar los coeficientes y la constante:
a = fila[:-1]
b = fila[-1:][0]
# Calcular el valor de x_i despejando la expresión original:
x_i = b
for k in range(len(a)):
if k != i:
x_i -= a[k]*xa[k]
x_i /= a[i]
return x_i
def jacobi(sistema, x_0, max_iter):
"""Aplica el método de Jacobi para hallar la solución
aproximada del sistema de ecuaciones lineales dado
a partir de una aproximación inicial x_0."""
# Aplicar el procedimiento iterativamente:
x = [x_0]
for k in range(max_iter):
xa = x[k]
x.append([aproximar_xi_jacobi(fila, i, xa)
for i, fila in enumerate(sistema)])
# Crear tabla de resultados:
cols = [f"x_{i}" for i in range(len(x_0))]
resultados = pd.DataFrame(x, columns = cols)
return resultados
def aproximar_x_gauss_seidel(sistema, xa):
"""Calcula el valor aproximado de x a partir del
sistema (ecuaciones) dado y los valores anteriores
de las variables."""
x = xa[:]
# Para cada variable:
for i in range(len(xa)):
# Aplicar la aproximación de Jacobi con los valores
# anteriores, tomando en cuenta el último valor
# calculado de las variables anteriores:
fila = sistema[i]
x[i] = aproximar_xi_jacobi(fila, i, x)
return x
def gauss_seidel(sistema, x_0, max_iter):
"""Aplica el método de Jacobi para hallar la solución
aproximada del sistema de ecuaciones lineales dado
a partir de una aproximación inicial x_0."""
# Aplicar el procedimiento iterativamente:
x = [x_0]
for k in range(max_iter):
xa = x[k]
x.append(aproximar_x_gauss_seidel(sistema, xa))
# Crear tabla de resultados:
cols = [f"x_{i}" for i in range(len(x_0))]
resultados = pd.DataFrame(x, columns = cols)
return resultados
b. Calcule las primeras 4 iteraciones para cada uno de los métodos utilizando los algoritmos de cada uno, partiendo de la aproximación inicial $x_0 = (0, 0, 0, 0)^T$. (Use tablas de resultados, donde señale los valores obtenidos de cada iteración de acuerdo al método utilizado).
Para hacer esto aplicamos las funciones definidas en la sección anterior con un número máximo de 4 iteraciones:
# Solución mediante el método de Jacobi
jacobi(sist1, x_0, 4)
# Solución mediante el método de Gauss-Seidel
gauss_seidel(sist1, x_0, 4)
c. Explique, si la sucesión converge o no con los algoritmos antes mencionados, a qué punto y por qué.
A simple vista parece que ninguno de los dos convergen, sino que los valores crecen (o decrecen) infinitamente. Comprobando con más iteraciones:
jacobi(sist1, x_0, 309)
gauss_seidel(sist1, x_0, 178)
Esto ocurre porque ambos métodos solo garantizan la convergencia para sistemas cuya matriz de coeficientes sea estrictamente diagonalmente dominante, es decir, que para cada fila el valor absoluto de su elemento diagonal sea mayor o igual a la sumatoria de los valores absolutos de los demás ítems. Empezando en la primera fila se comprueba que el sistema no cumple dicha condición: $$ -x_1 + 11x_2 - x_3 + 3x_4 = 25 \\ 1 \geq 11 + 1 + 3 ~~ \text{(no se cumple)} $$
Modifiquemos el sistema de ecuaciones original para que su matriz de coeficientes sea estrictamente diagonalmente dominante:
$$ \left\{ \begin{align*} -15x_1 + 11x_2 - x_3 + 3x_4 &= 25 \\ 2x_1 - 13x_2 + 2x_3 - x_4 &= -11 \\ 10x_1 - x_2 + 12x_3 + 0x_4 &= 6 \\ 6x_1 + 3x_2 - x_3 - 11x_4 &= 15 \end{align*} \right. $$A continuación, aplicamos los métodos creados anteriormente a este nuevo sistema:
sist2 = [[-15, 11, -1, 3, 25],
[ 2, -13, 10, -1, -11],
[ 10, -1, 12, 0, 6],
[ 6, 3, -1, -11, 15]]
jacobi(sist2, x_0, 100)
gauss_seidel(sist2, x_0, 100)
Como se puede observar, en ambos casos se llega a la solución con apenas 100 iteraciones.
Objetivo 8¶
Dado el siguiente grafo:
Con dichas distancias, analice los métodos de ordenamiento de matrices aplicando el Método de Banda y de la Envolvente, y realice lo que se le indica a continuación:
a) Analice y halle la matriz dispersa asociada al grafo:
Un grafo no dirigido consiste de un conjunto de vértices (V) y un conjunto de aristas (E) representadas como pares no ordenados de vértices. Este grafo de 8 vértices y 11 aristas se puede representar entonces como:
$$ G = (V, E) \\ V = \{1, 2, 3, 4, 5, 6, 7, 8\} \\ E = \left\{(1,2), (1,3), (1,4), (2,6), (3,4), (3,5), (3,7), (4,5), (5,8), (6,7), (7,8)\right\} $$A su vez, este grafo se puede representar como una matriz simétrica 8x8 con 22 elementos no nulos correspondientes a los pares no ordenados y sus reflejos con respecto al eje de simetría. Como la gran mayoría de los elementos de la matriz serán ceros ($64 - 22 = 42$), será una matriz dispersa. La matriz obtenida a partir del grafo será la siguiente:
$$ \begin{pmatrix} 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 1 & 1 & 0 & 1 & 0 \\ 1 & 0 & 1 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 \end{pmatrix} $$b) Calcule el ancho de banda de la matriz:
El ancho de banda de una matriz es el número $k$ tal que $a_{ij} = 0$ si $\left|i - j\right| > k$. Es decir, es el número de bandas diagonales en las que se encuentran los elementos no nulos. En el caso de la matriz dispersa del grafo, su ancho de banda es 4 porque todos los 1 están dentro de una franja de cuatro diagonales a cada lado de la principal.
También se puede calcular el ancho de banda de forma algorítmica, como se muestra a continuación:
def ancho_de_banda(matriz):
"""Calcula el ancho de banda de una matriz cuadrada."""
n = len(matriz)
# Para cada valor de k < n:
for k in range(n):
# Variable que determina si se cumple que todos
# los valores fuera de la franja son ceros:
condicion = True
# Recorrer cada elemento
for i in range(n):
for j in range(n):
# Si se encuentra un elemento no nulo
# fuera de la franja:
if abs(i - j) > k and matriz[i][j] != 0:
# Se cambia la variable
condicion = False
# Si la condición se cumplió para todos los
# valores fuera de la franja, se encontró k
if condicion:
return k
# Matriz dispersa del grafo
m = [[0, 1, 1, 1, 0, 0, 0, 0],
[1, 0, 0, 0, 0, 1, 0, 0],
[1, 0, 0, 1, 1, 0, 1, 0],
[1, 0, 1, 0, 1, 0, 0, 0],
[0, 0, 1, 1, 0, 0, 0, 1],
[0, 1, 0, 0, 0, 0, 1, 0],
[0, 0, 1, 0, 0, 1, 0, 1],
[0, 0, 0, 0, 1, 0, 1, 0]]
# Ancho de banda de la matriz:
ancho_de_banda(m)