Algoritmos101

s1Eva2025PAOII_T2 publicidad por provincia y medio de comunicación

por

Edison Del Rosario

Ejercicio: 1Eva2025PAOII_T2 publicidad por provincia y medio de comunicación

literal a

Planteamiento del sistema de ecuaciones

\begin{cases} 0.35x + 0.45y+ 0.2z+0.15w =540 \\ 1.2x+0.41y+0.35z+0.19w = 1250 \\ 0.1x+0.3y+0.7z+0.12w=1200 \end{cases}

siendo la variable libre con valor por ejemplo cinco, w =5

\begin{cases} 0.35x + 0.45y+ 0.2z =540-0.15(5) \\ 1.2x+0.41y+0.35z = 1250 -0.19(5)\\ 0.1x+0.3y+0.7z=1200 - 0.12(5)\end{cases}

la forma matricial del sistema es:

\begin{pmatrix} -0.35 & 0.45 & 0.2 \\ 1.2 & 0.41 & 0.35 \\ 0.1 & 0.3 & 0.7 \end{pmatrix} \begin{pmatrix} x \\ y \\ y \end{pmatrix} = \begin{pmatrix} 540-0.15(5) \\ 1250-0.19(5) \\ 1200-0.12(5) \end{pmatrix} \left( \begin{array}{rrr|r} 0.35 & 0.45 & 0.2 & 540-0.15(5) \\ 1.2 & 0.41 & 0.35 & 1250-0.19(5) \\ 0.1 & 0.3 & 0.7 & 1200-0.12(5) \end{array} \right)

Para el pivoteo parcial por filas, se usa la columna 0, el mayor valor está en la fila 1, por lo que se intercambia la fila 0 y 1.

\left( \begin{array}{rrr|r} 1.2 & 0.41 & 0.35 & 1250-0.19(5) \\ 0.35 & 0.45 & 0.2 & 540-0.15(5) \\ 0.1 & 0.3 & 0.7 & 1200-0.12(5) \end{array} \right)

Luego al observar la columna 1 desde la diagonal hacia abajo, se encuentra que el valor del pivote ya es el mayor, por lo que no ser requieren cambios de fila

literal b

Las expresiones para el método de Gauss-Seidel son:

1.2x+0.41y+0.35z = 1250-0.19(5) 0.35x+0.45y+0.2z = 540-0.15(5) 0.1x+0.3y+0.7z = 1200-0.12(5)

despejando la variable de la diagonal:

x = \dfrac{1250-0.19(5)-0.41y-0.35z}{1.2} y = \dfrac{540-0.15(5)-0.35x-0.2z}{0.45} z = \dfrac{1200-0.12(5)-0.1x-0.3y}{0.7}

el vector inicial se puede estimar considerando por ejemplo todas las variables independiente en cero

X0 =[ (1250-0.19(5))/1.2, (540-0.15(5))/0.45, (1200-0.12(5))/0.7]

X0 = [1040.87, 1198.33, 1713.42]

con lo que si las otra variables no son cero, se podría empezar con un número aproximadamente la mitad de lo calculado

X0 = [500, 550, 850]

la tolerancia será de 0.1, dado que el número de espacios publicitarios son de tipo entero

literal c

iteración = 0 , X0 =X0 = [500, 550, 850]

x_1= \dfrac{1250-0.19(5)-0.41(550)-0.35(850)}{1.2} =619.62 y_1 = \dfrac{540-0.15(5)-0.35(619.62)-0.2(850)}{0.45} =356.95 z_1 = \dfrac{1200-0.12(5)-0.1(619.62)-0.3(356.95)}{0.7}=1471.92

X1=[619.62, 356.95, 1471.92]

errado = max | [X1-X0] |

=max |[619.62, 356.95, 1471.92]-[500, 550, 850] |

= max | [119.62, 193.04, 671.92] | = 671.92

iteración = 1 , X1=[619.62, 356.95, 1471.92]

x_2 = \dfrac{1250-0.19(5)-0.41(356.95)-0.35(1471.92)}{1.2} = 489.60 y_2 = \dfrac{540-0.15(5)-0.35(489.60)-0.2(1471.92)}{0.45}= 159.45 z _2= \dfrac{1200-0.12(5)-0.1(489.60)-0.3(159.45)}{0.7} = 1575.14

X2 = [ 489.60, 159.45, 1575.14 ]

errado=max | [489.60, 159.45, 1575.14 ]-[619.62, 356.95, 1471.92] |

= max | [130.02, 197.50, 103.22] | = 197.50

iteración = 2 , X2 = [ 489.60, 159.45, 1575.14 ]

x_3 = \dfrac{1250-0.19(5)-0.41(159.45)-0.35(1575.14)}{1.2} = 526.97 y_3 = \dfrac{540-0.15(5)-0.35(526.97)-0.2(1575.14)}{0.45}= 84.50 z_3 = \dfrac{1200-0.12(5)-0.1(526.97)-0.3(84.50)}{0.7} =1601.92

X2 = [ 526.97, 84.50, 1601.92 ]

errado = max | [526.97, 84.50, 1601.92 ] -[489.60, 159.45, 1575.14 ]|

= max |[37.37, 74.94, 26.78]| = 74.94

literal d

El error disminuye en cada iteración , por lo que se estima que el método converge.

Usando el algoritmo, el resultado luego de 10 iteraciones es:

Matriz aumentada
[[3.50000e-01 4.50000e-01 2.00000e-01 5.37500e+02]
[1.20000e+00 4.10000e-01 3.50000e-01 1.24905e+03]
[1.00000e-01 3.00000e-01 7.00000e-01 1.19940e+03]]
Pivoteo parcial:
1 intercambiar filas: 0 y 1
AB
[[1.20000e+00 4.10000e-01 3.50000e-01 1.24905e+03]
[3.50000e-01 4.50000e-01 2.00000e-01 5.37500e+02]
[1.00000e-01 3.00000e-01 7.00000e-01 1.19940e+03]]
Iteraciones Gauss-Seidel
itera,[X]
errado,[diferencia]
0 [500. 550. 800.]
nan
1 [ 619.625 356.9583 1471.9286]
671.9285714285713 [119.625 193.0417 671.9286]
2 [ 489.6017 159.4526 1575.1486]
197.50571538800702 [130.0233 197.5057 103.2201]
3 [ 526.977 84.5074 1601.9287]
74.94523526150007 [37.3753 74.9452 26.7801]
4 [ 544.7724 58.7642 1610.4193]
25.74314554013919 [17.7954 25.7431 8.4906]
5 [ 551.0916 50.0757 1613.2402]
8.688487997115615 [6.3192 8.6885 2.8209]
6 [ 553.2374 47.1531 1614.1862]
2.9226923643758127 [2.1458 2.9227 0.946 ]
7 [ 553.9601 46.1705 1614.5041]
0.9825295158950382 [0.7227 0.9825 0.3178]
8 [ 554.2031 45.8403 1614.6109]
0.33025930633446166 [0.243 0.3303 0.1068]
9 [ 554.2847 45.7293 1614.6468]
0.1110080156455382 [0.0817 0.111 0.0359]
10 [ 554.3122 45.6919 1614.6589]
0.03731226893541617 [0.0275 0.0373 0.0121]
Metodo de Jacobi
numero de condición: 6.0782105438630545
X: [ 554.3122 45.6919 1614.6589]
errado: 0.03731226893541617
iteraciones: 10

literal e

el número de condición es 6.07 que es relativamente bajo, "cercano a 1" por lo que el sistema no tiene grandes variaciones en el resultado antes pequeños cambios en los valores de entrada.

literal f

EL resultado del algoritmo se ha mostrado en el literal e

Las instrucciones en Python usadas son:

import numpy as np

def gauss_seidel(A,B,X0,tolera, iteramax=100, vertabla=False, precision=4):
    ''' Método de Gauss Seidel, tolerancia, vector inicial X0
        para mostrar iteraciones: vertabla=True
    '''
    # Matrices como arreglo, numeros reales
    A = np.array(A, dtype=float)
    B = np.array(B, dtype=float)
    X0 = np.array(X0, dtype=float)
    tamano = np.shape(A)
    n = tamano[0]
    m = tamano[1]
 
    # valores iniciales
    diferencia = 2*tolera*np.ones(n, dtype=float)
    errado = 2*tolera # np.max(diferencia)
 
    tabla = [np.copy(X0)] # tabla de iteraciones
    tabla = np.concatenate((tabla,[[np.nan]]),
                            axis=1) # añade errado
 
    if vertabla==True:
        print('Iteraciones Gauss-Seidel')
        print('itera,[X]')
        print('   errado,[diferencia]')
        print(0,X0)
        print(' ',np.nan)
        np.set_printoptions(precision)
 
    itera = 0 # Gauss-Sediel
    X = np.copy(X0)
    while (errado>tolera and itera<iteramax):
 
        for i in range(0,n,1): # una ecuacion
            suma = B[i]
            for j in range(0,m,1):
                if (i!=j):
                    suma = suma-A[i,j]*X[j]
            nuevo = suma/A[i,i]
            diferencia[i] = np.abs(nuevo-X[i])
            X[i] = nuevo
        errado = np.max(diferencia)
 
        Xfila= np.concatenate((X,[errado]),axis=0)
        tabla = np.concatenate((tabla,[Xfila]),axis = 0)
        itera = itera + 1
        if vertabla==True:
            print(itera, X)
            print(' ', errado,diferencia)
 
    # No converge
    if (itera>iteramax):
        X = np.nan
        print('No converge,iteramax superado')
    return(X,tabla)
 
def pivoteafila(A,B,vertabla=False):
    '''
    Pivotea 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,'y', dondemax+i)
    if vertabla==True:
        if pivoteado==0:
            print('  Pivoteo por filas NO requerido')
        else:
            print('AB')
            print(AB)
    return(AB)
 
# PROGRAMA Búsqueda de solucion  --------
# INGRESO

A = [[0.35,0.45,0.2],
     [1.2,0.41,0.35],
     [0.1,0.3,0.7]]

B = [540-0.5*5,1250-0.19*5,1200-0.12*5]
 
X0 = [500,550,800]
tolera = 0.1
iteramax = 100
verdecimal = 4
 
# PROCEDIMIENTO
AB = pivoteafila(A,B,vertabla=True)
n,m = np.shape(AB)
A = AB[:,:n] # separa en A y B
B = AB[:,n]
 
[X, tabla] = gauss_seidel(A,B,X0,tolera,
                          iteramax=100,
                          vertabla=True,
                          precision=verdecimal)
n_itera = len(tabla)-1
errado = tabla[-1,-1]
 
# numero de condicion
ncond = np.linalg.cond(A)
 
# SALIDA
print('Metodo de Jacobi')
print('numero de condición:', ncond)
print('X: ',X)
print('errado:',errado)
print('iteraciones:', n_itera)

Ejemplos