Teorema de Laplace em Java

Por
|

Introdução

Para quem não conhece, o Teorema de Laplace tem como finalidade o cálculo de determinantes de matrizes de qualquer ordem.

Em geral, no ensino médio, aprendemos a calcular determinantes de matrizes de ordem dois e de ordem três (Regra de Sarrus) e alguns artifícios para cálculos de determinantes, como redução de ordem da matriz se a mesma obedece a certas condições (Regra de Chió, por exemplo).

Entretanto, de forma geral, para matrizes de ordem quatro ou superior temos que usar o Teorema de Laplace para calcular o determinante. Abaixo, segue um exemplo de determinante resolvido utilizando o teorema.

Determinante via Teorema de Laplace

Não irei dar detalhes do teorema porque não é o objetivo da postagem.

Caso tenha interesse em aprender o teorema, recomendo o seguinte artigo do site "Brasil Escola" feito por Gabriel Alessandro de Oliveira da "Equipe Brasil Escola" (acesso em 18/11/2013): http://www.brasilescola.com/matematica/teorema-laplace.htm.

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.

Utilizei recursividade. É importante salientar que o Teorema de Laplace não é um método eficiente para calcular determinantes. Na prática, sua complexidade no tempo é de O(n!), que é pior que a complexidade exponencial.

Além disso, ele tem um custo grande de memória também, pois a cada chamada recursiva ele aloca memória para as matrizes que serão utilizadas no cálculo dos cofatores. Em síntese, não utilize este algoritmo em situações práticas. Ele é útil para fins didáticos ou para calcular determinantes de matrizes pequenas.

Se você precisar de um método mais eficiente, você pode utilizar a decomposição LU (ou LUP) combinada com o Teorema de Binet. Esse é o método mais eficiente que eu conheço (pelo menos até a escrita deste texto).

        public class TeoremaDeLaplace {
                //parte-se do pressuposto que a matriz seja válida
                public static double laplace(double[][] matriz){
                    double determinante = 0;
                    if(matriz.length == 1){
                        determinante = matriz[0][0];
                    }else if(matriz.length == 2){
                        determinante = matriz[0][0]*matriz[1][1] - matriz[0][1]*matriz[1][0];
                    }else if(matriz.length == 3){
                        determinante = matriz[0][0]*matriz[1][1]*matriz[2][2]
                                    +matriz[0][1]*matriz[1][2]*matriz[2][0]
                                    +matriz[0][2]*matriz[1][0]*matriz[2][1]
                                    -matriz[0][2]*matriz[1][1]*matriz[2][0]
                                    -matriz[0][0]*matriz[1][2]*matriz[2][1]
                                    -matriz[0][1]*matriz[1][0]*matriz[2][2];
                    }else{
                        double[][] aux;
                        int i_aux, j_aux, linha, coluna, i;            

                        for(i = 0; i < matriz.length; i++){

                            if(matriz[0][i] != 0){
                                aux = new double[matriz.length - 1][matriz.length - 1];
                                i_aux = 0;
                                j_aux = 0;

                                for(linha = 1; linha < matriz.length; linha++){
                                    for(coluna = 0; coluna < matriz.length; coluna++){
                                        if(coluna != i){
                                            aux[i_aux][j_aux] = matriz[linha][coluna];
                                            j_aux++;
                                        }
                                    }

                                    i_aux++;
                                    j_aux = 0;
                                }

                                determinante += Math.pow(-1, i)*matriz[0][i]*laplace(aux);
                            }

                        }
                    }
                    return determinante;
                }
            }
        

Observe que este algoritmo recursivo considera três casos básicos:

  • quando a matriz é de ordem um (o determinante é o único elemento que a matriz possui);
  • quando a matriz é de ordem dois;
  • quando a matriz é de ordem três (regra de Sarrus).

Nos três casos o custo computacional é constante.

Observe também a linha do cálculo do sinal do cofator:

Math.pow(-1, i)*matriz[0][i]*laplace(aux).

Essa linha foi modificada pois o algoritmo sempre escolhe a primeira linha, cujo índice é zero (i + 0 = i).

O fato do primeiro índice das matrizes em Java ser zero é irrelevante. O sinal do cofator é dado por (-1)i+j. Se somarmos 1 (um) em cada índice para que o índice inicial seja 1 (um), então temos:

(-1)(i+1)+(j+1).

Desenvolvendo a expressão temos:

(-1)i+1+j+1

(-1)i+j+2

(-1)i+j(-1)2

(-1)i+j.

Ou seja, o deslocamento dos índices não faz diferença.

Download

Clique no link a seguir para realizar o download do código fonte: Teorema de Laplace (Projeto NetBeans 8).

Decomposição LU e Teorema de Binet

Conforme mencionei antes, o Teorema de Laplace não é um método eficiente para calcular determinantes, pois a sua complexidade é de O(n!). Entretanto, é possível calcular determinantes de forma eficiente utilizando a decomposição LU e o Teorema de Binet.

A decomposição LU consiste em fatorar uma matriz quadrada A como o produto de uma matriz triangular inferior (L) e uma matriz triangular superior (U). Para isso, a matriz A não pode ser singular (se for singular, a fatoração não é única). Isto é,

A = LU.

Por outro lado, o Teorema de Binet nos diz que o determinante do produto de matrizes quadradas é igual ao produto de seus determinantes. Ou seja,

det(AB) = det(A)det(B).

Isto é, se combinarmos a decomposição LU e o Teorema de Binet, temos

det(A) = det(L)det(U).

Como L e U são matrizes triangulares, então os seus respectivos determinantes podem ser calculados em tempo O(n). Isso ocorre porque, para calcular o determinante de uma matriz triangular, basta multiplicar os elementos da diagonal principal.

Por outro lado, a decomposição LU tem complexidade igual a O(n³).

Portanto, teríamos um algoritmo com complexidade O(n³) para calcular determinantes (não precisamos considerar a complexidade O(n) do cálculo de determinantes, pois O(n³) é maior). Obviamente, um algoritmo com complexidade O(n³) é bem melhor do que um algoritmo com complexidade O(n!).

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

Laplace expansion (Wikipedia). Disponível em: <https://en.wikipedia.org/wiki/Laplace_expansion>. Acesso em 20/07/2017.

Observações

Esta postagem foi atualizada em 20/07/2017.

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.

3 comentários:

  1. Que obra prima esse artigo. Sapoha de Laplace é muito difícil de entender mas olhando via código java você já começa a ter uma clareza na mente.

    ResponderExcluir
  2. Obrigado por compartilhar. Apenas um comentário: creio que a linha 42 deva ser:

    determinante += Math.pow(-1, i+1)*matriz[0][i]*laplace(aux);

    a fim de adequar o sinal do cofator.

    ResponderExcluir
    Respostas
    1. Boa noite, Pedro. Obrigado pela leitura!

      Eu fiz uma atualização nesta postagem e respondi sua dúvida no meio do texto:

      "O fato do primeiro índice das matrizes em Java ser zero é irrelevante. O sinal do cofator é dado por (-1)^(i+j). Se somarmos 1 (um) em cada índice para que o índice inicial seja 1 (um), então temos:

      (-1)^((i+1)+(j+1)).

      Desenvolvendo a expressão temos:
      (-1)^(i+1+j+1)
      (-1)^(i+j+2)
      (-1)^(i+j)(-1)^2
      (-1)^(i+j).

      Ou seja, o deslocamento dos índices não faz diferença."

      Excluir