jueves, 9 de junio de 2011

Método de Montante en C


René Mario Montante Pardo

El mexicano René Mario Montante Pardo desarrolló en 1973 un método numérico que resuelve un sistema de ecuaciones en álgebra lineal utilizando solamente enteros, a diferencia del método de Gauss. No sólo eso, sino que con el mismo método se obtiene el determinante y la inversa de la matriz. El método es el más exacto que hay para encontrar la solución de un sistema de ecuaciones, ya que las presenta al final en forma de fracción y no pierde información en el camino, lo cual sí pasa con el método de Gauss - Jordan.

El método consiste en formar la matriz  extendida C  con las entradas de la matriz de coeficientes del sistema, la matriz identidad y el vector  de las entradas independientes del sistema. Posteriormente es necesario ir cambiando las entradas de C por medio de la siguiente fórmula:

para k != i

C(k, l) = [(C(i,i)*C(k,l) - C(k,i)*C(i,l)]/pant;


Se utiliza un par de variables auxiliares llamadas pact (pivote actual) y pant ( pivote anterior). Al inicio pant = 1; y pact = C(i,i). Donde i corre desde 1 hasta N, N el número de ecuaciones del sistema. Los pivotes van tomando los valores de la diagonal principal. Al final, el número que queda en la diagonal principal es el determinante, lo que queda en lugar de la matriz identidad es la inversa y la última columna corresponde a la solución del sistema multiplicada por el último pivote actual (pact).
Como ejemplo, sea el sistema de ecuaciones

2x - y +  z  = 2
 x     + 3z  = 4
    2y + 2z  = 4

Al añadir la matriz unidad se obtiene:

  2      -1       1       1       0       0       2
  1       0       3       0       1       0       4
  0       2       2       0       0       1       4

en el primer paso ( i = 1) pact = 2 y pant = 1. Después del primer ciclo se obtiene

  2      -1       1       1       0       0       2
  0       1       5      -1       2       0       6
  0       4       4       0       0       2       8

Aquí i = 2, pact = 1 y pant = 2. Al terminar este ciclo la matriz es:

  1       0       3       0       1       0       4
  0       1       5      -1       2       0       6
  0       0      -8       2      -4       1      -8

Aquí i = 3, pact = -8 y pant = 1. Después de éste ciclo finalmente se obtiene la matriz:

 -8       0       0      -6       4      -3      -8
  0      -8       0      -2       4      -5      -8
  0       0      -8       2      -4       1      -8

En lugar de la matriz del sistema se obtuvo

 -8   0   0
  0  -8   0
  0   0  -8

Lo cual indica que el determinante de la matriz

2   -1   1
1    0   3
0    2   2

es -8

En tanto que la inversa de esta matriz es:

         -6   4   -3
(1/-8)   -2   4   -5
          2  -4    1

y la solución del sistema es

       
       -8        1
(-1/8) -8    =   1
       -8        1 

Lo cual indica que x = 1, y = 1, z = 1 es la solución.
A continuación se presenta el algoritmo en C. Este programa es completo, en el sentido de que es, creo, bastante amable con el usuario. Se puede cambiar la variable Tamano para resolver sistemas de cualquier tamaño.

#include <stdio.h>
#define Tamano 3
// La variable Tamano controla el numero de ecuaciones del sistema
// se puede cambiar facilmente para resolver sistemas de cualquier
// tamano

// Prototipos de funciones
void Recibe(int Arreglo[][2*Tamano + 1]);
void Imprime(int Array[][2*Tamano + 1]);
void Calcula(int C[][2*Tamano + 1]);

int main()
{  // Abre main

int i;
int j;

printf("\nEste programa usa el metodo de Montante para calcular");
printf(" el determinante, la matriz inversa y la solucion de un");
printf(" sistema de %d ecuaciones lineales con %d incognitas.\n", Tamano, Tamano);

// Se define una matriz que incluye la matriz de coeficientes, la unidad de 
// Tamano X Tamano y los terminos independientes del sistema
int Matriz[Tamano][2*Tamano + 1] = { {0, 0} };

// Llamada a la funcion Recibe
Recibe(Matriz);

// Llamada a la funcion Imprime
Imprime(Matriz);

// Llamada a la funcion Calcula
Calcula(Matriz);
  
// Se llama a la funcion Imprime
Imprime(Matriz);

// Se imprime el determinante
printf("\n\nEl determinante de la matriz es: %d\n", Matriz[0][0]);    

// Se imprime la matriz inversa
printf("\n\n\nEsta es la matriz inversa:\n \n");
  
for ( j = 0; j < Tamano; j++ )
{    // Abre for
for ( i = Tamano; i < 2*Tamano; i++ )
{      // Abre for anidado
printf("\t%3d\t", Matriz[j][i]);  
}      // cierra for anidado
 
printf("\n");

if ( Tamano/2 - 1 == j )
printf("(1/%d)", Matriz[0][0]); 
}    // Cierra for 


// Se imprime la solucion del sistema
printf("\n\n\nA continuacion se presentan las soluciones del sistema.");
printf(" Los numeros de la izquierda se refieren a la variable. \n"); 
for ( i = 0; i < Tamano; i++ )
{   // Abre for
printf("%3d\t = %6d/%d\n", i + 1, Matriz[i][2*Tamano], Matriz[0][0]); 
}   // Cierra for
return 0;
}  // Cierra main


////////////////////////////////////////////////////////////
//FUNCION RECIBE
/////////////////////////////////////////////////////////////

void Recibe( int Arreglo[][2*Tamano + 1])

{    // Abre funcion Recibe 

int i;
int j;
int k;
int l;
int m;

// Este par de ciclos reciben los coeficientes del sistema
printf("\nSE RECIBEN LOS COEFICIENTES DEL SISTEMA: \n");
for ( i = 0; i < Tamano; i++ )
for ( j = 0; j < Tamano; j++ ) 
{  // Abre for
printf("\nPor favor introduzca el coeficiente %d de la ecuacion %d: ", j + 1, i + 1);
scanf("%d", &Arreglo[i][j]);
}  // Cierra for

// Este ciclo adiciona la matriz unidad de TamanoXTamano 
for ( k = 0; k < Tamano; k++ )
Arreglo[k][Tamano + k] = 1; 

// Este ciclo recibe los terminos independientes 
printf("\nSE RECIBEN LOS TERMINOS INDEPENDIENTES. \n");
for ( m = 0; m < Tamano; m++ )
{  // Abre for
printf("\nIntroduzca el termino independiente de la ecuacion %d: ", m + 1);
scanf("%d", &Arreglo[m][2*Tamano ]); 
 }  // Cierra for 
 }         // Cierra funcion Recibe

//////////////////////////////////////////////////
//FUNCION IMPRIME
////////////////////////////////////////////////// 

void Imprime(int Array[][2*Tamano + 1]) 

{        // Abre la funcion Imprime
int i;
int j;
  
printf("\n\n");
for ( i = 0; i < Tamano; i++ )
{   // Abre for 

for ( j = 0; j < 2*Tamano + 1; j++ )
{    // Abre for anidado
printf("%3d\t", Array[i][j]); 
}    // Cierra for anidado 
  
printf("\n");
}    // Cierra for

}        // Cierra la funcion Imprime


///////////////////////////////////////////////////////
//FUNCION CALCULA
///////////////////////////////////////////////////////

void Calcula(int C[][2*Tamano + 1])

{     // Abre funcion Calcula
/*+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
+ El algoritmo requiere que se haga una copia de la matriz original       +
+ Solo debe alterarse la matriz C cuando i se incrementa, esto se         +
+ Introducir la sentencia                                                 +  
+   B[k][l] = ( (C[i][i]*C[k][l]) - (C[k][i]*C[i][l]) )/pant;             +
+                                                                         +
+ hace en la parte principal de la funcion                                +
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/

// Se definen las variables pact (pivote actual) y pant(pivote anterior)   
// ademas de variables controladoras de ciclos                             
                                                                        
int B[Tamano][2*Tamano + 1];                                            
int pant = 1;  // Al principio pant = 1                                  
int pact;                                                               
int l;                                                                  
int k;                                                                  
int i = 0;                                                              
int j;                                                 
int s; 
int t;

// El pivote siempre va tomando valores consecutivos de la diagonal
// principal, esto se controla con la variable i en el siguiente ciclo
// for
for ( i = 0; i < Tamano; i++ )
{   // Abre for
// Se cambia el valor de pact
pact = C[i][i];

/* Descomente estas lineas para ver la impresion de estas variables
  printf ("\npact = %d", pact);
  printf ("\npant = %d", pant);
  */

// Los siguientes ciclos controlan las columnas y las filas respectivamente
for ( l = 0; l < 2*Tamano + 1; l++)
for ( k = 0; k < Tamano; k++ )
{  // Abre for anidado
  // El renglon sobre el que se ha tomado el pivote actual se deja intacta
  // esto se logra con el siguiente condicional
if ( k != i )
{    // Abre if
  // La asignacion de valores no se hace directamente sobre la matriz C sino sobre
  // una copia. Esto porque de lo contrario se estaria modificando la matriz con 
  // la que se calcula cada vez que se asigna un nuevo valor

B[k][l] = ( (C[i][i]*C[k][l]) - (C[k][i]*C[i][l]) )/pant;

}    // Cierra if
}  // Cierra for anidado 


// Se asigna los valores de la matriz A a la matriz C
   
for ( s = 0; s < Tamano; s++ )
{   // Abre for anidado
for ( t = 0; t < 2*Tamano + 1; t++ )
{    // Abre for anidado
   //Como el renglon del pivote actual (pact) no se modifico
   //entonces no se asigna en la variable original
if ( s != i)
C[s][t] = B[s][t] ; 
}    // Cierra for anidado 
}

  /* Descomente estas lineas para ver la evolucion del algoritmo
     cada vez que cambia i 
  printf("\n");
  Imprime(C);
  */

// Se cambia el valor de pant
pant = pact; 

}   // Cierra for
  
}     // Cierra funcion Calcula

8 comentarios:

  1. :) Muy bien. Aunque creo que se debe especificar que este método está pensado para coeficientes enteros de cada una de las variables (en tu código si lo manejas así)... del hecho de que calcule la inversa también se desprende que sólo debe funcionar para sistemas de nxn...

    Saludos y gracias :)

    ResponderEliminar
  2. por que al digitar todos los coeficientes, se sale el programa?.

    ResponderEliminar
    Respuestas
    1. No me queda claro a qué te refieres exactamente. Si se sale debe ser un error. Probablemente estás haciendo referencia a algún elemento de arreglo que no es accesible. Ten cuidado con que las matrices sean de tamaño adecuado, sobre todo si estás cambiando el tamaño en el código. Si puedes ser más específico, tal vez te pueda ayudar mejor.

      Eliminar
  3. Gracias funciona a la perfeccion, el programa, Se te agradece el codigo.

    ResponderEliminar
  4. Por que cuando hemos ingresado los valores al programa correctamente, al finalizar esperamos el resultado pero el programa se sale sin motivo alguno, estoy utilizando C ++ para compilar, de todos modos muchas gracias por el algoritmo :)

    ResponderEliminar
    Respuestas
    1. Seguro tiene que ver con que el programa se ejecuta tan rápido que no lo ves.
      Si estás programando en Windows agréga al final la instrucción
      cin.get();
      y eso hará que la ejecución se detenga.
      ¡Saludos!

      Eliminar
  5. como seria de una matriz de 4x4

    ResponderEliminar

Related Posts Plugin for WordPress, Blogger...