sábado, 23 de octubre de 2010

.: Iteración :.

:: Gauss-Jordan ::



Materia. Lab de Leng de Progr

Hora. V1(Jueves)

Volviendo a tocar el tema acerca de iteración de la clase de Lenguajes de Programación, les muestro lo que es el algoritmo para la solución de un sistema de ecuaciones lineales por el método Gauss-Jordan.
Antes de comenzar, noten que a continuación, les dejo los archivos para descargar en lenguaje C y en Perl.
La implementación en C sería el siguiente:

#include <stdio.h>

#define ren 3
#define col 4

int main(void) {
    int  i, j, k;
    float A[ren][col], fact, piv;
   
    //Captura de Datos en la matriz
   
    for (i = 0; i  < ren; i++) {
        for (j = 0; j < col; j++) {
            printf("Elemento [%d][%d] = ", i + 1, j + 1);
            scanf("%f", &A[i][j]);
        }
    }
   
    //Impresión de la matriz original
   
    for (i = 0; i  < ren; i++) {
        printf("\n");
       
        for (j = 0; j < col; j++) {
            printf("%.2f\t", A[i][j]);
        }
    }

    //Algoritmo Gauss Jordan
   
    for (k = 0; k < ren; k++) {
         piv = A[k][k];
        
         for (j = 0; j < col; j++) {
             A[k][j] = A[k][j] / piv;
         }
            
         for (i = 0; i < ren; i++) {
              if (i != k) {
                  fact = - A[i][k];
                      
                  for (j = 0; j < col; j++) {
                       A[i][j] = A[i][j] + fact * A[k][j];
                  }
              }
         }
    }
     
    //Impresión de la matriz escalonada
   
    for (i = 0; i  < ren; i++) {
        printf("\n");
       
        for (j = 0; j < col; j++) {
            printf("%.2f\t", A[i][j]);
        }
    }
   
    return 0;
}
A continuación, vamos a resolver lo que es un sistema de ecuaciones basándonos en el proceso del algoritmo para que puedan apreciar cómo funciona.
Mi sistema sería el siguiente.
Al ordenar las ecuaciones en la matriz tendremos lo siguiente:
Vamos a ver cómo funciona nuestro código una vez que entra al algoritmo de Gauss-Jordan línea por línea.
Primero entramos a un FOR que va desde 0 hasta lo que es el valor de la constante ren. Es decir, empezamos a analizar nuestra matriz por las filas.
Al inicio de este FOR elegimos un elemento pivote para comenzar a convertir en 1 la diagonal principal de nuestra matriz.
for (k = 0; k < ren; k++) {    <--- k = 0
         piv = A[k][k];   <--- Elemento pivote
        
         ...
Lo siguiente es dividir todos los elementos de la primera fila entre lo que es el pivote, de acuerdo a cómo recordamos el proceso manual de Guss-Jordan que vimos en “Algebra para Ingeniería” en el primer semestre.
Y si se dan cuenta, en este paso, se trabaja en base a las columnas, de tal forma que se hagan las divisiones en toda la fila, como ya menciono anteriormente.
for (k = 0; k < ren; k++) {    <--- k = 0
         piv = A[k][k];   <--- Elemento pivote
        
         for (j = 0; j < col; j++) {      <--- k = 0; j = 0
             A[k][j] = A[k][j] / piv;          <--- División
         }
            
         ...
Ahora, lo siguiente por hacer es tratar de obtener los ceros debajo de nuestra fila con la cual estamos trabajando.
Para esto hay que definir un factor que nos permita dicha acción. En este caso, se ha definido que el factor sea el elemento negativo [i][k] de nuestra matriz.
Sin embargo, tenemos una condición antes de definir el factor, la cual dice que i debe ser diferente de k  y como en este punto i == k, se incrementa el valor de i en una unidad. Esto se debe al hecho de que tratamos de obtener los ceros en el resto de la matriz.
No podemos aplicar las operaciones de conversión que vienen más adelante en la fila en la que se encuentra nuestro pivote, puesto que es la fila en la cual nos estamos basando para hacer las conversiones.
Si observamos el proceso de nuestro algoritmo, vemos que en este punto i = 1 y k = 0.
for (k = 0; k < ren; k++) {    <--- k = 0
         piv = A[k][k];   <--- Elemento pivote
        
         for (j = 0; j < col; j++) {      <--- k = 0; j = 0
             A[k][j] = A[k][j] / piv;     <--- División
         }
            
         for (i = 0; i < ren; i++) {      <--- i = 1
            if (i != k) {         <--- Se cumple condición
               fact = - A[i][k];  <--- Definimos del factor
                      
               for (j = 0; j < col; j++) {<--- j = 0; i = 1; k =0
                       A[i][j] = A[i][j] + fact * A[k][j];
                  }
            }
         }
    }

Como ya pudieron darse cuenta, una vez que se pudo definir el factor que usaremos, entramos a un nuevo FOR el cual se encargara de las operaciones necesarias para la obtención de los ceros.
En estas operaciones que se harán, cabe mencionar que se las aplicará a las filas restantes de la matriz.
Como pueden darse cuenta, en el FOR donde está la operación, ya tenemos el contador i que es el que nos indica que trabajará sobre la fila i  en la cual se encuentre. Pero también tenemos el contador j  el cual aplicará la operación de conversión de dicha fila i elemento por elemento, teniendo como límite el número de columnas.
Al momento de llegar a ese límite, nuestro contador i se incrementará, lo cual significa que cambiará de fila.
La operación de conversión que estaremos usando es la siguiente:
A[i][j] = A[i][j] + fact * A[k][j];

Ahora veremos cómo queda nuestra matriz:
Aun más a fondo
Es posible que no se pueda visualizar del todo bien las operaciones realizadas con nuestra matriz, por lo que observen el siguiente proceso:
Nosotros tuvimos después de las divisiones con el pivote la siguiente matriz:
De acuerdo a nuestro algoritmo, para la conversión de la segunda fila, factor será 3:
fact = - A[i][k] = 3      <--- i = 1; k = 0
Para las operaciones de transformación, de acuerdo a la operación es así:
A[i][j] = A[i][j] + fact * A[k][j]

Tenemos que recordar que en esta operación la multiplicación se realiza primero y después la suma. Entonces nuestras operaciones se visualizarían mejor así para la segunda fila:

Ahora bien, para la conversión de la tercera fila, factor será 3:
fact = - A[i][k] = 2      <--- i = 2; k = 0
Y nuestras operaciones quedarían así:

NOTA. Recuerden que ya para el proceso de la tercera fila, se invalido el FOR que contenía las operaciones; de modo que regreso al FOR con el contador “i” que manipula las filas. Eso significa que para el proceso de la tercera fila i = 2 y el factor ahora vale 2.
Por consiguiente, nuestra matriz, ahora es de esta forma:
Continuando con la explicación
Como pueden ver, nuestro algoritmo todavía no termina.
Si recuerdan, el algoritmo completo inicia con un FOR que maneja como contador una k que va desde 0 hasta el valor de “ren. Recuerden, esto se debe al hecho de que nuestro proceso de Gauss-Jordán hará las transformaciones tomando una fila de referencia, de donde se tomará nuestro pivote.
Al principio, donde k = 0 tomo el pivote en la posición [k][k] = [0][0] de nuestra matriz.
Por consiguiente, se deduce que se harán transformaciones dependiendo del número de filas contenidas en nuestra matriz.
Al inicio del programa, nuestra matriz solía ser:
Ya que comenzó nuestro programa, nuestra matriz se convirtió en:

En esta ocasión, k = 1, por lo que ahora nuestro pivote se encuentra en la posición [1][1] = 0.5. Nuestra fila de referencia es la segunda. Y es aquí donde volvemos a empezar todo de nuevo.
Al final de todo el proceso, tendremos la siguiente matriz:
Y nuevamente con el valor de k = 2, nuestro pivote estará en la posición [2][2] = -1, perteneciente a la tercera fila, la cual será en esta ocasión la fila de referencia. Se vuelve a correr todo el proceso.
El resultado del paso final sería:
Para Finalizar
Nuestro sistema de ecuaciones planteado:
Tiene como resultados:
  • X = 2
  • Y = 3
  • Z = -1
Comentarios.
Si se dan cuenta, en lenguaje C los arreglos no son de memoria dinámica, por lo que debemos darles un límite forzosamente.
Es por esta razón por la cual nos limitamos a 3 ecuaciones en la matriz.
Sin embargo, al realizar la implementación en Perl, recordé algo de los arreglos en este lenguaje: Tienen memoria dinámica.
Esto me facilito a hacer más eficiente el código de implementación en C, pidiendo el número de ecuaciones antes de capturar datos. Por consiguiente, el algoritmo se convirtió en algo funcional para N cantidad de ecuaciones, mientras que en C debemos de estar modificando los límites del arreglo para manejar más ecuaciones.
En lenguaje C es un completo desperdicio dar más espacio a los arreglos si no se va a usar esa memoria separada.
En Perl, sólo separa la que va a necesitar. Pero en fin, ustedes ya lo verán si se deciden a correr los dos códigos para comprobar.
Cualquier comentario al respecto, son bienvenidos.
Saludos a todos.

1 comentario: