3.3.1 Método de Gauss – determinante de matriz con Python

Referencia: Rodriguez 4.3.9 p129, Burden 9Ed 6.4 p396. Chapra 9.1.2 p250, pdf274.

El determinante de una matriz cuadrada triangular superior también puede calcularse como el producto de los coeficientes de la diagonal principal, considerando el número de cambios de fila del pivoteo.

det(A) = (-1)^k \prod_{i=1}^n a_{i,i}

Si observamos que en las secciones anteriores se tiene desarrollado los algoritmos  para obtener la matriz triangular superior en el método de Gauss, se usan como punto de partida para obtener los resultados del cálculo del determinante.


Ejercicio

Calcular el determinante de la matriz A.

A= \begin{pmatrix} 3 & -0.1 & -0.2 \\ 0.1 & 7 & -0.3 \\0.3 & -0.2 & 10 \end{pmatrix}

El  algoritmo para ejercicio se convierte en una extensión de los algoritmos anteriores.

A = np.array([[3. , -0.1, -0.2],
              [0.1,  7. , -0.3],
              [0.3, -0.2, 10.  ]])

Algoritmo en Python

El algoritmo parte de lo realizado en método de Gauss, indicando que la matriz a procesar es solamente A. Se mantienen los procedimientos de «pivoteo parcial por filas» y » eliminación hacia adelante»

Para contar el número de cambios de filas, en la sección de pivoteo se añade un contador cambiofilas en el condicional de cambio de filas.

Para el resultado del operador multiplicación, se usan todas las casillas de la diagonal al acumular las multiplicaciones.

Se aplica la operación de la fórmula planteada para el método, y se presenta el resultado.

# Determinante de una matriz A
# convirtiendo a diagonal superior 

import numpy as np

# INGRESO
A = np.array([[3. , -0.1, -0.2],
              [0.1,  7. , -0.3],
              [0.3, -0.2, 10.  ]])

# PROCEDIMIENTO

# Matriz aumentada
AB = np.copy(A)

# Pivoteo parcial por filas

cambiofila = 0  # contador

tamano = np.shape(AB)
n = tamano[0]
m = tamano[1]
# Para cada fila en AB
for i in range(0,n-1,1):
    # columna desde diagonal i en adelante
    columna  = abs(AB[i:,i])
    dondemax = np.argmax(columna)
    # dondemax no está en diagonal
    if (dondemax !=0):
        # intercambia filas
        
        cambiofila = cambiofila +1
        
        temporal = np.copy(AB[i,:])
        AB[i,:]  = AB[dondemax+i,:]
        AB[dondemax+i,:] = temporal
AB1 = np.copy(AB)

# eliminación hacia adelante
for i in range(0,n-1,1):
    pivote   = AB[i,i]
    adelante = i + 1
    for k in range(adelante,n,1):
        factor  = AB[k,i]/pivote
        AB[k,:] = AB[k,:] - AB[i,:]*factor

# calcula determinante
multiplica = 1
for i in range(0,n,1):
    multiplica = multiplica*AB[i,i]
determinante = ((-1)**cambiofila)*multiplica

# SALIDA
print('Pivoteo parcial por filas')
print(AB1)
print('eliminación hacia adelante')
print(AB)
print('determinante: ')
print(determinante)

el resultado obtenido es:

determinante: 
210.35299999999995

se verifica usando la función de numpy:

>>> np.linalg.det(A)
210.3529999999999

3.3 Método de Gauss con Python

Referencia: Chapra 9.2 p254 pdf278, Burden 6.1 p359. Rodríguez 4.3 p119

El método de Gauss realiza operaciones sobre la matriz aumentada y pivoteada por filas, añadiendo procedimientos con las siguientes fórmulas:

  • eliminación hacia adelante:
A_{k} = A_{k} -A_{i}\frac{a_{k,i}}{a_{i,i}}
  • sustitución  hacia atrás:
x_i = \frac{b_i^{(i-1)}-\sum_{j=i+1}^{n}a_{ij}^{(i-1)} x_{j}}{a_{ii}^{(i-1)}}

para i = n-1, n-2, …


Método de Gauss – Ejercicio resuelto

El método de Gauss opera sobre la matriz aumentada y pivoteada por filas, añadiendo el proceso de «eliminación hacia adelante» mediante la operación entre filas. Se continúa entonces desde el resultado del tema de 3.2 pivoteo parcial por filas para matrices:

Referencia: Rodríguez cap4.0 Ejemplo 1 p105

\begin{cases} 4x_1+2x_2+5x_3 = 60.70 \\ 2x_1+5x_2+8x_3 = 92.90 \\ 5x_1+4x_2+3x_3 = 56.30 \end{cases}
matriz pivoteada por fila:
[[ 5.   4.   3.  56.3]
 [ 2.   5.   8.  92.9]
 [ 4.   2.   5.  60.7]]

Desarrollo Analítico – Ejercicio resuelto

Eliminación hacia adelante  o eliminación Gaussiana

Consiste en simplificar la matriz a una triangular superior, con ceros debajo de la diagonal, usando operaciones entre filas.

Los índices de fila y columna, A[i,j], se usan de forma semejante a la nomenclatura de los textos de Álgebra Lineal. Progresivamente para cada fila, se toma como referencia o pivote el elemento de la diagonal (i=j). Luego, se realizan operaciones con las filas inferiores para convertir los elementos por debajo de la diagonal en cero. Las operaciones incluyen el vector B debido a que se trabaja sobre la matriz aumentada AB.

matriz pivoteada por fila:
[[ 5.   4.   3.  56.3]
 [ 2.   5.   8.  92.9]
 [ 4.   2.   5.  60.7]]

iteración fila 1, operación fila 1 y 2

Para la fila 1, con posición i=0, se usa el elemento ai,i como pivote.

pivote = A[i,i] = AB[0,0] = 5

Para las filas de que están después de la diagonal se referencian como k

k= i+1 = 0+1 = 1

Se obtiene el factor escalar de la operación entre filas de la formula

A_{k} = A_{k} -A_{i}\frac{a_{k,i}}{pivote}
factor = AB[1,0]/pivote = 2/5

y se realiza la operación entre fila k y la fila i para actualizar la fila k,

       [ 2. 5.  8.  92.9]
-(2/5)*[ 5. 4.  3.  56.3]
__________________________
     = [ 0. 3.4 6.8 70.38]

con lo que la matriz aumentada AB se actualiza a:

AB =
[[ 5.    4.    3.   56.3 ]
 [ 0.    3.4   6.8  70.38]
 [ 4.    2.    5.   60.7 ]]

iteración fila 1, operación fila 1 y 3

se continúa con la siguiente fila, quedando la matriz aumentada con la columna debajo de la primera diagonal en cero:

k = i+1 = 2
factor = 4/5

        [ 4.  2.  5.   60.7] 
- (4/5)*[ 5.  4.  3.   56.3]
_____________________________
      = [ 0. -1.2 2.6  15.66]

AB =
[[ 5.    4.    3.   56.3 ]
 [ 0.    3.4   6.8  70.38]
 [ 0.   -1.2   2.6  15.66]]

Como ya se terminaron las operaciones con la primera posición de la diagonal, el siguiente paso es usar la segunda posición, i =2.

iteración fila 2

Para la fila 2, con posición i=1, se toma el elemento de la diagonal ai,i como pivote, la variable adelante indica la referencia de la tercera fila

i=1
pivote = A[i,i] = AB[1,1] = 3.4

Para las filas ubicadas adelante de la diagonal se referencian como k

adelante = i+1 = 1+1 = 2
k = adelante = 2

Para aplicar la fórmula por filas, se obtiene el factor .

factor = AB[2,1]/pivote  = -1,2/3.4 = - 0,3529

            [ 0. -1.2 2.6 15.66]
-(-1,2/3.4)*[ 0.  3.4 6.8 70.38]
________________________________
         =  [ 0.  0.  5.  40.5 ]

AB =
[[ 5.    4.    3.   56.3 ]
 [ 0.    3.4   6.8  70.38]
 [ 0.    0.    5.   40.5 ]]

Con lo que se completa el objetivo de tener ceros debajo de la diagonal.
Observe que no es necesario realizar operaciones para la última fila, por lo que k debe llegar solamente hasta la fila penúltima.

El resultado de la eliminación hacia adelante a ser usado en el próximo paso es:

Elimina hacia adelante
[[ 5.    4.    3.   56.3 ]
 [ 0.    3.4   6.8  70.38]
 [ 0.    0.    5.   40.5 ]]

Sustitución hacia atrás

La fórmula se interpreta para facilitar el algoritmo

x_i = \frac{b_i^{(i-1)}-\sum_{j=i+1}^{n}a_{ij}^{(i-1)} x_{j}}{a_{ii}^{(i-1)}}

Para una fila i, el vector b[i] representa el valor de la constante en la fila i de la matriz aumentada, a[i] se refiere los valores de los coeficientes de la ecuación, de los que se usan los que se encuentran a la derecha de la diagonal.

Las operaciones se realizan de abajo hacia arriba desde la última fila. Para el ejercicio presentado se tiene que:

utlfila = n-1 = 3-1 = 2
ultcolumna = m-1 = 4-1 = 3

la matriz a procesar es:

Elimina hacia adelante
[[ 5.    4.    3.   56.3 ]
 [ 0.    3.4   6.8  70.38]
 [ 0.    0.    5.   40.5 ]]

iteración 1, fila 3, i=2

Empieza desde la última fila de la matriz,

[ 0. 0. 5. 40.5 ]
0 x_1 + 0 x_2 + 5 x_3 = 40.5

El valor de la constante es b = 40.5 y no existen elementos hacia la derecha de la diagonal. No se usa la ultima columna que es de las constantes:

5 x_3 = 40.5 x_3 = 40.5/5 = 8.1

la respuesta se interpreta en el vector X como:

X= \begin{pmatrix} x_1 \\ x_2 \\ x_3 \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \\ 8.1 \end{pmatrix}

iteración 2, fila 2,  i = 1

De la penúltima fila se obtiene la ecuación para encontrar x2

[ 0. 3.4 6.8 70.38]
0x_1 + 3.4 x_2 +6.8 x_3 = 70.38

se observa que b = 70.38 y  a la derecha de a diagonal se tiene un solo valor de [6.8].

3.4 x_2 = 70.38 -6.8 x_3

usa el valor de x3 encontrado en la iteración anterior

3.4 x_2 = 70.38 -6.8 (8.1)

Muestra la ecuación para la segunda fila.

x_2 = (70.38 -6.8 (8.1))/3.4 = 4.5

la respuesta se interpreta en el vector X como:

X= \begin{pmatrix} 0 \\ 4.5 \\ 8.1 \end{pmatrix}

iteración 3 fila 1, i=0

se sigue el mismo proceso para la siguiente incógnita X1 que se interpreta como

[ 5. 4. 3. 56.3 ]
5x_1 + 4 x_2 + 3x_3 = 56.3 5x_1 = 56.3 - ( 4 x_2 + 3x_3) x_1 = \frac{56.3 - ( 4 x_2 + 3x_3)}{5}

realice las operaciones con los valores encontrados para X2 y X3

Se encuentra que la solución al sistema de ecuaciones es:

X= \begin{pmatrix} 2.8\\ 4.5 \\ 8.1 \end{pmatrix}
por sustitución hacia atras
el vector solución X es:
[[2.8]
 [4.5]
 [8.1]]

Verificar respuesta

Para verificar que el resultado es correcto, se usa el producto punto entre la matriz a y el vector resultado X. La operación A.X = B debe dar el vector B.

verificar que A.X = B
[[60.7]
 [92.9]
 [56.3]]

Método de Gauss con Algoritmo en Python

El algoritmo en su primera parte reutiliza lo desarrollado en Python para la matriz aumentada y pivoteo parcial por filas.

Recordar: Asegurar que los arreglos sean de tipo Real (float), para que no se considere el vector como entero y realice operaciones entre enteros, generando errores por truncamiento.

La parte nueva a desarrollar corresponde al procedimiento de «eliminación hacia adelante» y el procedimiento de «sustitución hacia atrás».

# Método de Gauss
# Solución a Sistemas de Ecuaciones
# de la forma A.X=B

import numpy as np

# INGRESO
A = np.array([[4,2,5],
              [2,5,8],
              [5,4,3]])

B = np.array([[60.70],
              [92.90],
              [56.30]])

# PROCEDIMIENTO
casicero = 1e-15 # Considerar como 0

# Evitar truncamiento en operaciones
A = np.array(A,dtype=float) 

# Matriz aumentada
AB  = np.concatenate((A,B),axis=1)
AB0 = np.copy(AB)

# Pivoteo parcial por filas
tamano = np.shape(AB)
n = tamano[0]
m = tamano[1]

# Para cada fila en AB
for i in range(0,n-1,1):
    # columna desde diagonal i en adelante
    columna  = abs(AB[i:,i])
    dondemax = np.argmax(columna)
    
    # dondemax no está en diagonal
    if (dondemax !=0):
        # intercambia filas
        temporal = np.copy(AB[i,:])
        AB[i,:] = AB[dondemax+i,:]
        AB[dondemax+i,:] = temporal
AB1 = np.copy(AB)

# eliminación hacia adelante
for i in range(0,n-1,1):
    pivote   = AB[i,i]
    adelante = i + 1
    for k in range(adelante,n,1):
        factor  = AB[k,i]/pivote
        AB[k,:] = AB[k,:] - AB[i,:]*factor

# sustitución hacia atrás
ultfila = n-1
ultcolumna = m-1
X = np.zeros(n,dtype=float)

for i in range(ultfila,0-1,-1):
    suma = 0
    for j in range(i+1,ultcolumna,1):
        suma = suma + AB[i,j]*X[j]
    b = AB[i,ultcolumna]
    X[i] = (b-suma)/AB[i,i]

X = np.transpose([X])


# SALIDA
print('Matriz aumentada:')
print(AB0)
print('Pivoteo parcial por filas')
print(AB1)
print('eliminación hacia adelante')
print(AB)
print('solución: ')
print(X)

Tarea

Revisar cuando la matriz pivoteada por filas tienen un elemento cero o muy cercano a cero pues la matriz sería singular. El valor considerado como casi cero podría ser 1×10-15

A estas alturas, por la cantidad de líneas de instrucción es recomendable reutilizar bloques de algoritmos usando funciones def-return. Por ejemplo: pivoteo por filas, eliminación hacia adelante, sustitución hacia atrás

3.2 Pivoteo parcial por filas con Python

Referencia: Chapra 9.4.2 p268, pdf 292. Burden 9Ed 6.2 p372. Rodriguez 4.0 p105

Los métodos de solución a sistema de ecuaciones, tienen en los primeros pasos en común usar la matriz aumentada y pivoteada por filas. Para compartir estos pasos y simplificar la presentación de los métodos, se presentan como una de las primeros algoritmos a implementar.

Para mostrar todo el desarrollo del proceso se usa como referencia un ejercicio.


Ejercicio

Referencia: Rodriguez cap4.0 Ejemplo 1 pdf.105

Ejemplo 1. Un comerciante compra tres productos A, B, C, pero en las facturas únicamente consta la cantidad comprada en Kg y el valor total de la compra. Se necesita determinar el precio unitario de cada producto.  Dispone de solo tres facturas con los siguientes datos:

Ejemplo:
Cantidad Valor ($)
Factura X1 X2 X3 Pagado
1 4 2 5 60.70
2 2 5 8 92.90
3 5 4 3 56.30

Los precios unitarios se pueden representar por las variables x1, x2, x3 para escribir el sistema de ecuaciones que muestran las relaciónes de cantidad, precio y valor pagado:

\begin{cases} 4x_1+2x_2+5x_3 = 60.70 \\ 2x_1+5x_2+8x_3 = 92.90 \\ 5x_1+4x_2+3x_3 = 56.30 \end{cases}

Sistema de ecuaciones como Matriz y Vector

El sistema de ecuaciones se escribe en la forma algebraica como matrices y vectoresl de la forma Ax=B

\begin{pmatrix} 4 & 2 & 5 \\ 2 & 5 & 8 \\5 & 4 & 3 \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \\ x_3 \end{pmatrix} = \begin{pmatrix} 60.70 \\ 92.90 \\ 56.30 \end{pmatrix}

Para el algoritmo la matriz A y el vector B se escriben como arreglos.

A = np.array([[4,2,5],
              [2,5,8],
              [5,4,3]])

B = np.array([[60.70],
              [92.90],
              [56.30]])

Observe que:

  • Las matrices y vectores se ingresan con arreglos de la libreria numpy
  • el vector B se escribe en forma de columna
  • No se usan listas, de ser el caso se convierten hacia arreglos con np.array()

Si el vector B está como fila, se aumenta una dimensión [B] y se aplica la transpuesta

Bfila = np.array([60.70,92.90,56.30])
Bcolumna = np.transpose([Bfila])
print(Bcolumna)
>>> Bcolumna
array([[60.7],
       [92.9],
       [56.3]])

En el desarrollo de las soluciones, para mantener sincronía entre las operaciones entre filas de la matriz A y el vector B se usa la matriz aumentada.


Matriz Aumentada

Se realiza al concatenar la matriz A con el vector B en forma de columnas (axis=1).

AB = np.concatenate((A,B),axis=1)

el resultado AB se muestra como:

>>> AB
array([[ 4. ,  2. ,  5. , 60.7],
       [ 2. ,  5. ,  8. , 92.9],
       [ 5. ,  4. ,  3. , 56.3]])

Pivoteo parcial por filas

Para el pivoteo por fila de la matriz aumentada AB, tiene como primer paso revisar la primera columna desde la diagonal en adelante.

columna = [|4|,
           |2|,
           |5|]
dondemax = 2

El procedimiento de pivoteo se realiza si la posición dónde se encuentra el valor de  mayor magnitud no corresponde a la diagonal de la matriz (posición 0 de la columna).

En el ejercicio se encuentra que la magnitud de mayor valor está en la última fila, por lo que en AB se realiza el intercambio entre la fila 3 y la fila 1

AB = [[ 5. , 4. , 3. , 56.3],
      [ 2. , 5. , 8. , 92.9],
      [ 4. , 2. , 5. , 60.7]]

Se repite al paso anterior, pero para la segunda columna formada desde la diagonal.

columna = [|5|,
           |2|]
dondemax = 0

como la posición dondemax es la primera, índice 0, se determina que ya está en la diagonal de AB y no es necesario realizar el intercambio de filas.

Se repite el proceso para la tercera columna desde la diagonal, que resulta tener solo una casilla (columna =[5]) y no ser requiere continuar.

El resultado del pivoteo por fila se muestra como:

matriz pivoteada por fila:
AB = [[ 5. ,  4. ,  3. , 56.3],
      [ 2. ,  5. ,  8. , 92.9],
      [ 4. ,  2. ,  5. , 60.7]]

Algoritmo en Python

Para realizar el algoritmo, es de recordar que para realizar operaciones en una matriz sin alterar la original, se usa una copia de la matriz (np.copy). Se puede comparar y observar los cambios entre la matriz original y la copia a la que se aplicaron cambios

Si no es necesaria la comparación entre el antes y despues, no se realiza la copia y se ahorra el espacio de memoria, detalle importante para matrices de «gran tamaño» y una computadora con «limitada» memoria.

# Pivoteo parcial por filas
# Solución a Sistemas de Ecuaciones

import numpy as np

# INGRESO
A = np.array([[4,2,5],
              [2,5,8],
              [5,4,3]])

B = np.array([[60.70],
              [92.90],
              [56.30]])

# PROCEDIMIENTO
# Matriz aumentada
AB  = np.concatenate((A,B),axis=1)
AB0 = np.copy(AB)

# Pivoteo parcial por filas
tamano = np.shape(AB)
n = tamano[0]
m = tamano[1]

# Para cada fila en AB
for i in range(0,n-1,1):
    # columna desde diagonal i en adelante
    columna = abs(AB[i:,i])
    dondemax = np.argmax(columna)
    
    # dondemax no está en diagonal
    if (dondemax !=0):
        # intercambia filas
        temporal = np.copy(AB[i,:])
        AB[i,:]  = AB[dondemax+i,:]
        AB[dondemax+i,:] = temporal

# SALIDA
print('Matriz aumentada:')
print(AB0)
print('Pivoteo parcial por filas')
print(AB)

Función pivoteafila(M)

Los bloques de cada procedimiento que se repiten en otros métodos se convierten a funciones def-return, empaquetando las soluciones algoritmicas a problemas resueltos.

Se usa la matriz M para generalizar y diferenciar de A que es usada en los ejercicios en realizados en adelante.

def pivoteafila(M):
    '''
    Pivotea parcial por filas
    Si hay ceros en diagonal es matriz singular,
    Tarea: Revisar si diagonal tiene ceros
    '''
    # Pivoteo por filas AB
    tamano = np.shape(M)
    n = tamano[0]
    m = tamano[1]
    
    # Para cada fila en AB
    for i in range(0,n-1,1):
        # columna desde diagonal i en adelante
        columna = np.abs(M[i:,i])
        dondemax = np.argmax(columna)
        
        # dondemax no es en diagonal
        if (dondemax != 0):
            # intercambia filas
            temporal = np.copy(M[i,:])
            M[i,:] = M[dondemax+i,:]
            M[dondemax+i,:] = temporal
    return(M)