sábado, 31 de mayo de 2014

Cálculo de la determinante de una matriz de Orden n

En este artículo voy a mostrarles la manera de calcular la determinante de una matriz de orden n. Cuando la matriz es de orden 2 o 3, es sencillo calcular la determinante pero ya cuando hablamos de matrices de órdenes superiores, apoyarnos en algún algoritmo computacional es una excelente idea. Para éste ejemplo, vamos a calcular al determinante de la siguiente matriz:


La idea es convertir a la matriz mediante operaciones elementales en una matriz triangular equivalente, pues en este caso la determinante estará dada por el producto de todos los términos de la diagonal principal, multiplicada por -1 si se hizo un número impar de cambios.

El algoritmo es el siguiente:

1.- Buscamos la fila con el mayor elemento en valor absoluto de la primera columna. En nuestro ejemplo, el mayor elemento de 1, 2 y 1 es 2, ubicado en la segunda fila. Ahora intercambiamos la segunda fila con la primera obteniendo la siguiente matriz:


2.- Mediante operaciones elementales, hacemos ceros todos los elementos de la primera columna, excepto la primera fila.



Ahora hacemos cero la primera columna de la tercera fila.


3.- Ahora buscamos la fila con el mayor elemento en valor absoluto de la segunda columna, excepto la primera fila pues ya ha sido procesada. En este caso, como ambos son igual, no es necesario hacer un cambio.

4.- Mediante operaciones elementales hacemos ceros todos los elementos de la segunda columna pero sin alterar la primera y segunda fila. Con esto la matriz nos quedaría de la siguiente manera:


Ahora calculamos la matriz multiplicando los elementos de la diagonal. El resultado obtenido es -2 y como el número de cambios fue impar, entonces multiplicamos por .1 obteniendo 2 como resultado final. La implementación en Java de este algoritmo es la siguiente:

public class MatrizUtil {

    public static double[][] intercambiarFilasMatriz(double[][] matriz, int i, int j) {
        double temp;
        for (int k = 0; k < matriz[0].length; k++) {
            temp = matriz[i][k];
            matriz[i][k] = matriz[j][k];
            matriz[j][k] = temp;
        }
        return matriz;
    }

    public static void imprimirMatriz(double[][] matriz) {
        for (int i = 0; i < matriz.length; i++) {
            for (int j = 0; j < matriz[0].length; j++) {
                System.out.print(matriz[i][j] + " ");
            }
            System.out.println("");
        }
    }

    public static int pivoteMatriz(double[][] matriz, int i) {
        int piv = i;
        double v = matriz[i][i];
        for (int j = i + 1; j < matriz.length; j++) {
            if (Math.abs(matriz[j][i]) > v) {
                v = matriz[j][i];
                piv = j;
            }
        }
        return piv;
    }

    /**
     * 
     * @param m es una matriz cuadrada
     * @return 
     */
    public static int eliminaAdelante(double[][] m) {
        int numeroIntercambios = 0;
        int filaPivote = -1;
        for (int columnaEvaluada = 0; columnaEvaluada < m.length; columnaEvaluada++) {
            filaPivote = pivoteMatriz(m, columnaEvaluada);
            if (filaPivote != columnaEvaluada) {
                m = intercambiarFilasMatriz(m, columnaEvaluada, filaPivote);
                numeroIntercambios++;
            }
            for (int i = columnaEvaluada + 1; i < m.length; i++) {
                for (int j = columnaEvaluada + 1; j < m.length; j++) {
                    if (m[columnaEvaluada][columnaEvaluada] == 0) {
                        System.out.println("Error, división por cero");
                        System.exit(1);
                    } else {
                        m[i][j] = m[i][j] - (m[i][columnaEvaluada] * m[columnaEvaluada][j] / m[columnaEvaluada][columnaEvaluada]);
                    }
                }
                m[i][columnaEvaluada] = 0;
            }
        }
        return numeroIntercambios;
    }

    public static double det(double[][] m) {
        int numeroIntercambios = MatrizUtil.eliminaAdelante(m);
        double det = 1;
        for (int i = 0; i < m.length; i++) {
            det *= m[i][i];
        }
        if (numeroIntercambios % 2 == 1) {
            det = -det;
        }
        return det;
    }
}
Ahora, podemos percatarnos que para convertir a cero algunos elementos de la matriz utilizamos una fórmula la cual se muestra a continuación:
m[i][j] = m[i][j] - (m[i][columnaEvaluada] * m[columnaEvaluada][j] / m[columnaEvaluada]
Esta fórmula se obtiene de la siguiente manera:

Dada la matriz:


Para convertir a 0 un determinado elemento debemos hacer la siguiente operación elemental: 


La constante obtenida se aplicará a toda la fila pues es una operación elemental, quedando de la fórmula tal como está en la implementación:


También les comparto el método main de prueba:
public static void main(String[] args) {
    double[][] matriz = {{1, 0, 2}, {2, 1, 1}, {1, 1, 1}};
    System.out.println(MatrizUtil.det(matriz));
}
Espero que este artículo les sea de utilidad, hasta una próxima publicación.

0 comentarios:

Publicar un comentario