Teorema de Laplace em C

Por
|

Numa postagem antiga, eu apresentei a implementação do teorema de Laplace em Java, que é utilizado para o cálculo de determinantes (Teorema de Laplace em Java). Nesta postagem, apresento o mesmo algoritmo codificado na linguagem C.

O teorema de Laplace utiliza uma expansão em cofatores para realizar o cálculo de determinantes. Entretanto, não é um método eficiente para isso, pois sua complexidade no tempo é de O(n!). Isto é, ele é de ordem exponencial (na prática, é pior do que uma exponencial).

Como esta postagem é complementar, então não irei prolongá-la. Caso o leitor queira mais informações, sugiro que o mesmo acesse a postagem do algoritmo em Java. A postagem contém informações que não requer conhecimentos de Java para compreender.

Algoritmo

O algoritmo a seguir escolhe sempre a primeira linha no cálculo do determinante. É recomendado conhecer previamente o Teorema de Laplace antes de analisar o algoritmo.

        #include <stdio.h>
        #include <stdlib.h>
        //Código por Henrique Felipe (GitHub: HenriqueIni) 
        //Supõe-se que a matriz 'a' é válida e de ordem n × n
        double detLaplace(int n, double a[n][n]){
            if(n == 1){
                //Caso básico: matriz 1x1
                return a[0][0];
            }else{
                double det = 0;
                int i, row, col, j_aux, i_aux;

                //Escolhe a primeira linha para calcular os cofatores
                for(i = 0; i < n; i++){
                    //ignora os zeros (zero vezes qualquer número é igual zero)
                    if (a[0][i] != 0) {
                        double aux[n - 1][n - 1];
                        i_aux = 0;
                        j_aux = 0;
                        //Gera as matrizes para calcular os cofatores
                        for(row = 1; row < n; row++){
                            for(col = 0; col < n; col++){
                                if(col != i){
                                    aux[i_aux][j_aux] = a[row][col];
                                    j_aux++;
                                }
                            }
                            i_aux++;
                            j_aux = 0;
                        }
                        double factor = (i % 2 == 0)? a[0][i] : -a[0][i];
                        det = det + factor * detLaplace(n - 1, aux);
                    }
                }
                return det;
            }
        }
        //Testes
        int main() {
            double a[5][5] = {{1,8,3,5,0},
                              {0,-1,7,9,1},
                              {0,0,3,2,4},
                              {0,0,0,-6,-1},
                              {0,0,0,0,2}};
            printf("%.16f\n", detLaplace(5, a));
            double b[3][3] = {{2,-2,-1},
                              {3,-4,1},
                              {1,1,5}};
            printf("%.16f\n", detLaplace(3, b));
            return 0;
        }
        

Referências

DANTE, L. R. Matemática, Volume único. 1ª edição. São Paulo: Ática, 2005.

MELO, J. P. B. C.; FILHO, V. S. Álgebra Linear. Universidade Cruzeiro do Sul - LFTC

Siga o blog por e-mail

Receba notificações de novas postagens e novidades do blog por e-mail.

Importante: utilize o bom senso na hora de comentar. Acesse a política de privacidade para maiores informações sobre comentários.

Nenhum comentário:

Postar um comentário