3.2 Pivoteo parcial por filas con Python

[ Ejercicio ] [ Matriz Aumentada ] [ Pivoteo filas ] [ algoritmo ] [ función ]

Referencia: Chapra 9.4.2 p268. Burden 6.2 p279. Rodríguez 4.0 p105pivoteo parcial por filas

Los métodos de solución a sistemas de ecuaciones en los primeros pasos usan la matriz aumentada y pivoteada por filas.

Como es un procedimiento usado en todos los métodos de la unidad, para simplificar se presenta como uno de los primeros algoritmos.diagonal dominante vs cima de montaña

El objetivo del pivoteo es ordenar la matriz para que en lo posible sea diagonal dominante.

|a_{i,i}| \geq \sum_{j=0 ; i\neq j}^n |a_{i,j}|

..


1. Ejercicio

Referencia: 1Eva_IIT2011_T2 Sistema de Ecuaciones, diagonal dominante

Considere el siguiente sistema de ecuaciones AX=B dado por:

\begin{cases} -2x+5y+9z=1\\7x+y+z=6\\-3x+7y-z=-26\end{cases}

Realice el pivoteo parcial por filas, de tal manera que la diagonal de A sea estrictamente dominante.

[ Ejercicio ] [ Matriz Aumentada ] [ Pivoteo filas ] [ algoritmo ] [ función ]
..


2. Matriz Aumentada

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

\begin{pmatrix} -2 & 5 & 9 \\ 7 & 1 & 1 \\-3 & 7 & -1 \end{pmatrix} \begin{pmatrix} x_0 \\ x_1 \\ x_2 \end{pmatrix} = \begin{pmatrix} 1 \\ 6 \\ -26 \end{pmatrix}

Para el algoritmo, las ecuaciones se escriben en forma de matriz A y vector B.

A = [[-2, 5, 9],
     [ 7, 1, 1],
     [-3, 7,-1]]

B = [1,6,-26]

Las matrices y vectores se procesan como arreglos np.array() de números reales. No se usan listas.

A = np.array(A,dtype=float)
B = np.array(B,dtype=float)

El vector B para la matriz aumentada se usa en forma de columna. Se aumenta una dimensión [B] y se aplica la transpuesta.

B_columna = np.transpose([B])
>>> B_columna
array([[  1],
       [  6],
       [-26]])

La matriz aumentada AB se forma al concatenar por columnas la matriz A con el vector B_columna,  usando el parámetro axis=1.

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

el resultado AB se muestra como:

>>> AB
array([[ -2. ,  5. ,   9. ,   1.],
       [  7. ,  1. ,   1. ,   6.],
       [ -3. ,  7. ,  -1. , -26.]])
\left( \begin{array}{rrr|r} -2 & 5 & 9 & 1 \\ 7 & 1 & 1 & 6 \\ -3 & 7 & -1 & -26 \end{array} \right)

En varios algoritmos se usa la matriz aumentada AB, para mantener el orden entre filas de A y B al aplicar cambios de fila.

[ Ejercicio ] [ Matriz Aumentada ] [ Pivoteo filas ] [ algoritmo ] [ función ]
..


3. Pivoteo parcial por filas

pivotea filas columna 0Para el pivoteo por filas de la matriz aumentada AB, tiene como primer paso revisar la primera columna, desde la posición diagonal hacia todas las filas por debajo, usando solo la magnitud de los coeficientes |A|.

La representación gráfica de la matriz A, permite visualizar los intercambios de fila.

>>> AB
array([[ -2. ,  5. ,   9. ,   1.],
       [  7. ,  1. ,   1. ,   6.],
       [ -3. ,  7. ,  -1. , -26.]])

Las instrucciones para seleccionar la columna, usar el valor absoluto y dónde se encuentra el máximo son:

columna = abs(AB[i:,i])
dondemax = np.argmax(columna)

Los valores de la columna se reducen a:

columna = [|-2.|,   fila=0
           | 7.|,   fila=1
           |-3.|]   fila=2
dondemax = 1

Si la magnitud de mayor valor no está en la diagonal (dondemax≠0), se realiza el intercambio entre la fila dondemax y la fila de la diagonal i en AB.

AB = [[  7. ,  1. ,   1. ,   6.],
      [ -2. ,  5. ,   9. ,   1.],
      [ -3. ,  7. ,  -1. , -26.]]

En éste paso se asegura que en la casilla AB[0,0] se encuentre el mayor valor de la columna 1.

El intercambio de filas requiere tres pasos: realizar una copia de la fila que se esta analizando en un vector temporal. Luego se copian los valores en la fila AB[dondemax+i] en la fila AB[i]. Finalmente actualizando la fila AB[dondemax+i] con los valores de temporal.

    if (dondemax !=0): # NO en diagonal
        # intercambia filas
        temporal = np.copy(AB[i,:])
        AB[i,:]  = AB[dondemax+i,:]
        AB[dondemax+i,:] = temporal

pivoteo por filas siguiente columnaSe repite el proceso anterior para la siguiente columna (j=1), pero siempre formada desde la diagonal (i=j).

La columna en éste paso se reduce el tamaño en una posición. Se consideran solo las magnitudes para la selección de dondemax.

AB = [[  7. ,  1. ,   1. ,   6.],
      [ -2. ,  5. ,   9. ,   1.],
      [ -3. ,  7. ,  -1. , -26.]]

Los valores de la columna se reducen a:

columna = [|5|,  fila=0
           |7|]  fila=1
dondemax = 1

En el ejercicio se encuentra que: la magnitud de mayor valor está en la fila=1, no en la diagonal. Se realiza el intercambio entre la fila ‘i’ y la fila (dondemax+i) de AB.

AB = ([[  7. ,  1. ,   1. ,   6.],
       [ -3. ,  7. ,  -1. , -26.],
       [ -2. ,  5. ,   9. ,   1.]]

pivoteo por filas completadoSe repite el proceso para la tercera columna desde la diagonal, que resulta tener solo una casilla (columna =[9]) y no ser requiere continuar.

En la gráfica se destaca el resultado del pivoteo por filas, acercando en lo posible a una matriz diagonal dominante.

Pivoteo parcial por filas AB:
[[  7. , 1. ,  1. ,   6.],
 [ -3. , 7. , -1. , -26.],
 [ -2. , 5. ,  9. ,   1.]]
A:
[[ 7. , 1. , 1.],
[ -3. , 7. , -1.],
[ -2. , 5. , 9.]]
B:
[6. , -26. , 1.]

Tarea: Revisar cuando en una columna se tiene dos valores mayores de igual valor. Ampliar el algoritmo. Considere como ejemplo del caso planteado: 1Eva_IT2011_T2_MN Alimentos para animales

[ Ejercicio ] [ Matriz Aumentada ] [ Pivoteo filas ] [ algoritmo ] [ función ]
..


4. 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).  Con la copia de la matriz, 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 después, 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
import numpy as np

# INGRESO
A = [[-2, 5, 9],
     [ 7, 1, 1],
     [-3, 7,-1]]
B = [1,6,-26]

# PROCEDIMIENTO
# Matrices como arreglo, numeros reales
A = np.array(A,dtype=float)
B = np.array(B,dtype=float)

# Matriz aumentada AB
B_columna = np.transpose([B])
AB  = np.concatenate((A,B_columna),axis=1)
AB0 = np.copy(AB) # copia de 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)
    
    if (dondemax !=0): # NO en diagonal
        # intercambia filas
        temporal = np.copy(AB[i,:])
        AB[i,:]  = AB[dondemax+i,:]
        AB[dondemax+i,:] = temporal
# Actualiza A y B pivoteado
A = AB[:,:n]
B = AB[:,n]

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

[ Ejercicio ] [ Matriz Aumentada ] [ Pivoteo filas ] [ algoritmo ] [ función ]
..


5. 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 algorítmicas.

# Pivoteo parcial por filas, funcion
import numpy as np

def pivoteafila(A,B,vertabla=False):
    '''
    Pivoteo parcial por filas, entrega matriz aumentada AB
    Si hay ceros en diagonal es matriz singular,
    Tarea: Revisar si diagonal tiene ceros
    '''
    A = np.array(A,dtype=float)
    B = np.array(B,dtype=float)
    # Matriz aumentada
    nB = len(np.shape(B))
    if nB == 1:
        B = np.transpose([B])
    AB  = np.concatenate((A,B),axis=1)
    
    if vertabla==True:
        print('Matriz aumentada')
        print(AB)
        print('Pivoteo parcial:')
    
    # Pivoteo por filas AB
    tamano = np.shape(AB)
    n = tamano[0]
    m = tamano[1]
    
    # Para cada fila en AB
    pivoteado = 0
    for i in range(0,n-1,1):
        # columna desde diagonal i en adelante
        columna = np.abs(AB[i:,i])
        dondemax = np.argmax(columna)
        
        # dondemax no es en diagonal
        if (dondemax != 0):
            # intercambia filas
            temporal = np.copy(AB[i,:])
            AB[i,:] = AB[dondemax+i,:]
            AB[dondemax+i,:] = temporal

            pivoteado = pivoteado + 1
            if vertabla==True:
                print(' ',pivoteado,
                      'intercambiar filas: ',i,
                      'con', dondemax+i)
    if vertabla==True:
        if pivoteado==0:
            print('  Pivoteo por filas NO requerido')
        else:
            print(AB)
    return(AB)

# INGRESO
A = [[-2, 5, 9],
     [ 7, 1, 1],
     [-3, 7,-1]]
B = [1,6,-26]

# PROCEDIMIENTO
AB = pivoteafila(A,B,vertabla=True)
n = len(AB)

# Actualiza A y B pivoteado
A = AB[:,:n]
B = AB[:,n]

# SALIDA
print('Pivoteo parcial por filas AB:')
print(AB)
print('A:')
print(A)
print('B:')
print(B)

El resultado del ejercicio es:

Matriz aumentada
[[ -2.   5.   9.   1.]
 [  7.   1.   1.   6.]
 [ -3.   7.  -1. -26.]]
Pivoteo parcial:
  1 intercambiar filas:  0 con 1
  2 intercambiar filas:  1 con 2
[[  7.   1.   1.   6.]
 [ -3.   7.  -1. -26.]
 [ -2.   5.   9.   1.]]
Pivoteo parcial por filas AB:
[[  7.   1.   1.   6.]
 [ -3.   7.  -1. -26.]
 [ -2.   5.   9.   1.]]
A:
[[ 7.  1.  1.]
 [-3.  7. -1.]
 [-2.  5.  9.]]
B:
[  6. -26.   1.]

[ Ejercicio ] [ Matriz Aumentada ] [ Pivoteo filas ] [ algoritmo ] [ función ]


6. Gráfica de Matriz A en 3D

Instrucciones para la gráfica en 3D de una matriz A. Las alturas de las barras son relativas a los valores de la casilla A[i,j]

# Matriz A como Barras3D
import numpy as np
import matplotlib.pyplot as plt

# INGRESO
##A = [[-2, 5, 9],
##     [ 7, 1, 1],
##     [-3, 7,-1]]
##titulo = 'matriz A'

##A = [[ 7, 1, 1],
##     [-2, 5, 9],
##     [-3, 7,-1]]
##titulo = 'A pivotea fila0 y fila1'

##A = [[ 7, 1, 1],
##     [-3, 7,-1],
##     [-2, 5, 9]]
##titulo = 'A pivotea fila1 y fila2'

A = [[ 7, 1, 1],
     [-3, 7,-1],
     [-2, 5, 9]]
titulo='A: Pivoteo por Filas'

# PROCEDIMIENTO
A = np.array(A, dtype=float)
n,m = np.shape(A)

# para grafica 3D
xi = np.arange(0,n,1)
yj = np.arange(0,m,1)
Xi,Yj = np.meshgrid(xi,yj)

A_min = np.min([np.min(A),-3])
A_max = np.max([np.max(A),9])

# SALIDA
# Grafica barras 3D
fig3D = plt.figure()
graf3D = fig3D.add_subplot(111,projection='3d')

AT = np.transpose(A) # filas en x, columnas en y
h = 0.5 # Barras ancho y profundidad
color_A = AT.ravel()/A_max
color_ij = plt.cm.rainbow(color_A)

graf3D.bar3d(Xi.ravel(),Yj.ravel(),
             np.zeros(n*m),h,h,
             AT.ravel(),color=color_ij)

# escala eje z
graf3D.set_zlim(A_min,A_max)
# etiqueta
graf3D.set_xlabel('filas i')
graf3D.set_ylabel('columnas j')
graf3D.set_zlabel('A[i,j]')
graf3D.set_title(titulo)
# etiquetas ejes
graf3D.xaxis.set_ticks(xi + h/2)
graf3D.xaxis.set_ticklabels(xi)
graf3D.yaxis.set_ticks(yj + h/2)
graf3D.yaxis.set_ticklabels(yj)
# Barra de color
color_escala = plt.Normalize(A_min,A_max)
color_barra = plt.cm.ScalarMappable(norm=color_escala,
                cmap=plt.colormaps["rainbow"])
fig3D.colorbar(color_barra,ax=graf3D,label="A[i,j]")

graf3D.view_init(35,35)
plt.show()

 

[ Ejercicio ] [ Matriz Aumentada ] [ Pivoteo filas ] [ algoritmo ] [ función ]


7. Ejercicio 2

Referencia: Rodríguez 4.0 p105,  1Eva_IT2010_T3_MN Precio artículosvende frutas

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 X0 X1 X2 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 x0, x1, x2 para escribir el sistema de ecuaciones que muestran las relaciones de cantidad, precio y valor pagado:

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

Desarrollo

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

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

La matriz aumentada usando el algoritmo tiene como resultado:

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

En varios algoritmos se usa la matriz aumentada AB, para mantener el orden entre filas al aplicar cambios de fila.

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

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

Los valores de la columna se reducen a:

columna = [|4|,   fila=0
           |2|,   fila=1
           |5|]   fila=2
dondemax = 2

En el ejercicio se encuentra que: la magnitud de mayor valor está en la última fila, no en la diagonal. Se realiza el intercambio entre la fila 2 y la fila 0 de AB.

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

Se repite el proceso anterior para la siguiente columna, pero siempre formada desde la diagonal.

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

Los valores de la columna se reducen a:

columna = [|5|,  fila=0
           |2|]  fila=1
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 a continuación:

Pivoteo parcial por filas AB:
[[ 5.   4.   3.  56.3]
 [ 2.   5.   8.  92.9]
 [ 4.   2.   5.  60.7]]
A:
[[5. 4. 3.]
 [2. 5. 8.]
 [4. 2. 5.]]
B:
[56.3 92.9 60.7]

[ Ejercicio ] [ Matriz Aumentada ] [ Pivoteo filas ] [ algoritmo ] [ función ]