miércoles, 20 de agosto de 2014

Calculo de un determinante mediante recursividad en MATLAB


El calculo de un determinante mediante recursividad o formalmente conocido como Teorema o Desarrollo de Laplace, consiste en calcular el determinante de una matriz cuadrada de $nxn$ mediante una descomposición en suma de determinantes menores, es decir, ir reduciendo en $n-1$ dimensiones. El desarrollo se puede hacer por filas o columnas.

La función recursiva para calcular el determinante utilizando el desarrollo en la primera fila puede expresarse como sigue:

Fuente: Wikipedia

Donde $a_{1,k}$ hace referencia al elemento ubicado en la primera fila y k-ésima columna, y $\alpha_{1,k}$ es el adjunto del elemento mencionado anteriormente.

Basado en la referencia anterior se implementó la siguiente función en MATLAB:




Ahora veamos un poco más detallado lo que implica cada línea de la función anterior: en la línea 2 se crea una vector idx cuyos valores son los números en el intervalo [1  n]  y que servirá para obtener, mediante un masking, los indices en fila y columna pertenecientes al adjunto correspondiente (véase linea 7 y 8). El ciclo for se implementa desde un valor unitario hasta el número de filas/columnas de la matriz de entrada X, y enseguida con la sentencia if  se comprueba si la matriz de entrada es de dimensiones unitarias (con lo cual se retorna la entrada misma) o bien si es de dimensiones mayores, con lo cual se implementa el algoritmo recursivo. Finalmente, habrán de sumarse todos los valores obtenidos en cada iteración del ciclo for, para ello se utiliza la función sum.


El costo de la recursividad

Por regla general, un algoritmo recursivo suele ser lento en ejecución. Por lo cual siempre es recomendable buscar o implementar otras técnicas de programación. En este caso, el ejemplo que hemos dado es puramente con fines didácticos, pero para mostrar un "poco" de lo ya dicho he decido "contar" el número de "llamadas" que se hacen a la función durante la ejecución para matrices de diversos tamaños. En la siguiente tabla se muestran las "llamadas" correspondientes para una matriz de $nxn$:

Dimensión de la matriz
Número de llamadas
1
1
2
3
3
10
4
41
5
206
6
1237
7
8660
8
69281

Como se observa el número de "llamadas" a la función crece de forma exponencial, lo cual se traduce en un gasto computacional considerable cuando las dimensiones de la matriz son mayores a un par de decenas e incluso menos. Se adjunta una gráfica correspondiente a la tabla anterior.


martes, 12 de agosto de 2014

Sentencia continue en MATLAB


La sentencia continue es útil para controlar las ejecuciones dentro de un bucle, permite ignorar cualquier instrucción posterior al llamado de esta y continuar con el siguiente ciclo. Por ejemplo, véase el siguiente código:

for i=1:5
    disp(i);
    continue;
    disp(i^2);
end

Si ejecutamos lo anterior MATLAB imprimirá en pantalla los valores del 1 al 5, pero no llegará a "imprimir" los valores resultantes de elevarlos al cuadrado. Se preguntará el lector, esto para qué me sirve si pude no escribir las instrucciones posteriores o bien comentarlas para evitar su ejecución, y toda la razón tendrá, pero, ahora veamos un ejemplo más significativo y en el cual puede resultar más interesante la utilidad de continue:

for i=1:5
    ifrem(i,2)==0
        continue;
    end
    disp(i);
end

Revisemos lo anterior: al "correr" el script MATLAB nos devolverá en pantalla todos los números impares en el intervalo de ejecución, dado que si se cumple la condición de que el residuo de la división entera $i/2$ es nulo entonces ignorará la instrucción disp que se encuentra enseguida y pasará a ejecutarse la siguiente iteración.

La referencia "online" que proporciona MathWorks muestra un ejemplo del conteo de líneas de un archivo de texto, en el cual la sentencia continue se utiliza para evitar adicionar aquellas líneas en blanco. Puede ver el ejemplo en el siguiente link:

Sentencia continue