Primeira vez aqui? Seja bem vindo e cheque o FAQ!
x

Cálculo do determinante de uma matriz: eliminação Gaussiana ou teorema de Laplace, qual o algoritmo mais eficiente?

+2 votos
583 visitas
perguntada Jun 22 em Matemática por JoaoMaria (71 pontos)  
republicada Jun 23 por JoaoMaria
Compartilhe

1 Resposta

+2 votos
respondida Jun 22 por JoaoMaria (71 pontos)  
editado Jul 7 por JoaoMaria

Para responder esta pergunta, iniciaremos por definir esses dois métodos de cálculo de determinantes: o método da eliminação gaussiana e o método do teorema de Laplace (matriz de cofatores). Após, apresentamos o programa em python contendo a implementação dos dois algoritmos. Por fim, é realizada a análise comparativa da eficiência de cada um deles.

1 - Cálculo do determinante utilizando a eliminação gaussiana
Eliminação de Gauss (ou método de escalonamento) é um método de cálculo de determinantes de matrizes normalmente utilizado para resolver sistemas de equações lineares. O método consiste em aplicar sucessivas operações elementares em uma matriz, para transformar e facilitar a resolução, tendo este os mesmos resultados que o método de cofatores.
No entanto, uma matriz ter seu determinante por esse método deve satisfazer as seguintes condições:
- Todas as linhas não-nulas estão acima de qualquer linha composta só de zeros.
- O pivô de cada linha está numa coluna à direita do pivô da linha acima.
- Todos os elementos de uma coluna abaixo de um pivô são zero.
Se a matriz obedece essas condições dizemos que ela é escalonada.
Dessa forma, para aplicar o método da eliminação gaussiana deve-se aplicar três operações básicas:
1.Somar a uma linha um múltiplo de outra linha.
2.Trocar duas linhas entre si.
3.Multiplicar todos os elementos de uma linha por uma constante não-nula.
Usando essas operações, a matriz será transformada em uma matriz triangular superior (forma escalonada) e, posteriormente, ser posta em sua forma escalonada reduzida. Esta forma final, por sua vez, é única e independente da sequência de operações de linha usadas, sendo mais fácil de resolver que a versão original da matriz.
Assim, as operações por linhas são:
1) \(L_i↔L_j;i,j∈\{1,2,...,n\}\) (permutação de linhas)
2) \(L_i=k⋅L_i;k∈R;i,∈\{1,2,...,n\} \) (multiplicação por escalar)
3) \(L_i=L_I−k⋅L_j;k∈R;i,j∈\{1,2,...,n\} \) (soma com múltiplo de outra linha; \(a−b \) simplesmente a soma \(a+(−b)\) )
Cabe salientar que a permutação de linhas, também conhecido como pivotagem, pode ser uma operação supérflua, nomeadamente em situações em que a matriz é diagonal dominante. Diz-se que um matriz de ordem \(n\) é diagonal dominante se:
\[|a_{ii}| \ge \sum_{\overset{j=1}{ j\ne i}}^{N} |a_{ij}| (i=1,2,\dots,n)\]
Há também a questão da perda de precisão da solução quando se utiliza pivots, logo deve ser evitada a utilização de pivots de magnitude reduzida

Ao final de todo o processo obtém-se uma matriz na qual todos os elementos abaixo da diagonal principal são nulos \(( a_{ij}=0,\forall i>j )\) , ou seja, uma matriz triangular superior.
Nesse ponto para obtermos o determinante, basta simplesmente multiplicarmos os elementos da diagonal principal.

2 - Cálculo do determinante utilizando o teorema de Laplace
O teorema de Laplace é uma expressão para o determinante de uma matriz quadrada qualquer. Por ele, o determinante de uma matriz A∈M_nxn (K) é igual à soma algébrica dos produtos dos elementos de uma linha (ou coluna) pelos respectivos cofatores (ou complementos algébricos).
O cofator do elemento \(a_{(i,j)}=(-1)^{(i+j)} \mid M_{ij} \mid \),
em que \(M_{ij}\) representa a matriz que se obtém da matriz original pela eliminação da i-ésima linha e da j-ésima coluna. Dessa forma:
\[det⁡(A)=a_{i,1} A_{i,1}+a_{i,2} A_{i,2}+\dots+a_{i,n} A_{i,n}\]
ou
\[det⁡(A)=a_{1,j} A_{1,j}+a_(2,j) A_{2,j}+\dots+a_{n,j} A_{n,j}\]
ou ainda
\[A^{(-1)}=det⁡〖(A)^{(-1)} 〗.adj(A)\]
conforme seja escolhida a i-ésima linha ou a j-ésima coluna.

3 – Implementação dos algoritmos
Abaixo, são apresentados os algoritmos codificados em Python. Nele, além das funções que calculam o determinante em cada um dos métodos, inicialmente é apresentado uma variação do algoritmo da eliminação gaussiana sem a utilização de pivô (solução possível quando a matriz tem algumas características adicionais. Além do programa principal, utilizado para receber o nome do arquivo contendo a matriz; realizar a validação da matriz; fazer a chamada de cada uma das funções de cálculo e apresentar os resultados, o código também Contém uma função para ler a matriz a partir de um arquivo informado.
Obs. Ao longo dos códigos são colocados comentários para melhor explicá-los

código inicial em python que importa bibliotecas necessárias:

import numpy as np
import copy

Algoritmo que calcula o determinante utilizando o método da eliminação Gaussiana sem pivô, para matrizes que são diagonal dominante. o que torna a complexidade do algoritmo menor :

def calc_det_gauss_sem_pivo(mat, n):
    val_det = 1
    for i in range(n):
        for j in range(i + 1, n):
            if mat[i][i]==0: # evita a divisão por zero quando o denominador é igual a zero
                t=0
            else:
                t = mat[j][i] / mat[i][i]
            for k in range(i + 1, n):
                mat[j][k] -= t * mat[i][k]
            mat[j][i] = 0
        val_det *= mat[i][i] # calcula o determinante multiplicando somente os elementos da diagonal principal

    print("Matriz triangular U - método da eliminação gaussiana sem pivô ")
    print(np.matrix(mat))
    return val_det

Algoritmo que calcula o determinante utilizando o método da eliminação Gaussiana com pivô. Perceba que, par evitar o problema de precisão, evita-se pivots com magnitude reduzida utilizando-se a linha com maior vaor na coluna \(i\) :

def calc_det_gauss_com_pivo(mat, n):
    val_det = 1
    for i in range(n):
        k = i
        for j in range(i + 1, n): # Descobre a linha com maior valor na coluna i
            if abs(mat[j][i]) > abs(mat[k][i]):
                k = j
        if k != i: # se a coluna com maior valor for diferente da coluna i faz a troca e troca o sinal do determinante
            mat[i], mat[k] = mat[k], mat[i]
            val_det = -val_det
        for j in range(i + 1, n):
            if mat[i][i]==0: # evita a divisão por zero quando o denominador é igual a zero
                t=0
            else:
                t = mat[j][i] / mat[i][i]
            for k in range(i + 1, n):
                mat[j][k] -= t * mat[i][k]
            mat[j][i] = 0
        val_det *= mat[i][i] # calcula o determinante multiplicando somente os elementos da diagonal principal

    print("Matriz triangular U - método da eliminação gaussiana com pivô ")
    print(np.matrix(mat))
    return val_det

Algoritmo que avalia se a matriz é diagonal dominante. ela retorna True caso a matriz seja diagonal dominante e False caso contrário

def avaliaMat(mat, n):
    for i in range(n):
        sLin = 0
        for j in range(n):
            if i!= j:
               sLin+=abs(mat[i][j])
        if abs(mat[i][i])<sLin:
            return False
    return True

Algoritmo que calcula o determinante utilizando o teorema de Laplace:

# Funcao que calcula o determinante de uma matriz pelo metodo de cófatores
def calc_det_cofat(matriz):
    mat=copy.deepcopy(matriz)
    if len(mat) == 1:  # Fim de cada pilha de recursão
        return mat[0][0]
    else:
        val_det = 0
        tam=len(mat)
    #print(np.matrix(mat), " Matriz: ")
        for x in list(range(tam)):  #  na primeira linha encontrando cofatores
            val_det += mat[0][x] * (-1) ** (2 + x) * calc_det_cofat(menor(mat, x))  # Somatorio dos elementos multiplicado por  seus cofactores
        #   print("det: = ", val_det, " Obtido com ", mat[0][x] * (-1) ** (2 + x) )
        return val_det


# Funcao que retorna a Matriz menor
def menor(mat, i):

        mat_menor = copy.deepcopy(mat)

        del mat_menor[0]  # Retira a primeira linha
        for k in list(range(len(mat_menor))):  # Retira a coluna i
            del mat_menor[k][i]
        return mat_menor

Rotina que lê a matriz do arquivo informado:

def le_matriz(arq):
    return [[float(x) for x in line.split()] for line in arq]

Abaixo está a rotina principal, que é responsável por:
1 - receber o nome do arquivo onde se encontra a matriz ( arquivo .txt);
2 - verificar se a matriz é quadrada;
3 - Chamar a função que avalia se a matriz é diagonal dominante
4- chamar as funções que calculam o determinante pelos dois métodos e,
5 - apresentar os resultados.

if __name__ == "__main__":
"""Este programa le arquivo contendo uma matriz e calcula o determinante pelos seguintes metodos:
      1 - eliminacao gaussiana
      2 - Cófatores"""
nome_arq = input('Entre com o nome do arquivo de dados =>')
# nome_arq="C:\\Users\joaoo\\Google Drive\\Doutorado\\Disciplinas\\Metodos_Computacionais_em_Economia\\Atividades\\MatrizGauss.txt "
nome_arq = "MatrizGauss.txt "
arq = open(nome_arq, "r")
matriz = le_matriz(arq.readlines())
lin = len(matriz)
col = len(matriz[0])
if lin != col:
    print("Matriz [", col, "X", lin, "] não é quadrada")
    print(np.matrix(matriz))
else:

    print(np.matrix(matriz), " [", lin, "X", col, "]")
    if avaliaMat(matriz, lin):
        print("a matriz é diagonal dominante")
    else:
        print("a matriz NÃO é diagonal dominante")

    ds = calc_det_gauss_sem_pivo(matriz, lin)
    print("seu determinante calculado por eliminação gaussiana sem pivô é = ", ds)

    arq = open(nome_arq, "r")
    matriz = le_matriz(arq.readlines())
    print(np.matrix(matriz), " [", lin, "X", col, "]")
    dp = calc_det_gauss_com_pivo(matriz, lin)
    print("seu determinante calculado por eliminação gaussiana com pivô é = ", dp)

    arq = open(nome_arq, "r")
    matriz = le_matriz(arq.readlines())
    print(np.matrix(matriz), " [", lin, "X", col, "]")
    df = calc_det_cofat(matriz)
    print("seu determinante calculado por cofatores é = ", df)

4 - Análise do desempenho
O método de Laplace, ou método de cófatores, de cálculo de determinantes para matrizes quadradas de ordem \(n\) , tem complexidade computacional igual a \(O(n!)\).
Isso se deve ao fato que para calcularmos o determinante de ordem ordem \(n\), temos que calcular \(n\) determinantes de ordem \(n - 1\). Para calcularmos o determinante de ordem ordem \(n - 1 \), temos que calcular \(n - 1 \) determinantes de ordem \(n - 2\).
Já a complexidade computacional da redução Gaussiana é \(O(n^3)\).
Portanto, conclui-se que para matrizes de ordem \(n\le5\), o método de cófatores é mais eficiente (\(n!= 120 < 125=n^3\)). Todavia, para \(n\ge 6\) a eliminação Gaussiana torna-se bem mais eficiente. Veja o exemplo para \(n=10\): (\(n^3= 1000 < 3.628.800=n!\)).

comentou Jul 6 por Pedro Antero (26 pontos)  
Excelente explicação. Explorou bem o lado teórico e discutiu a importante questão da complexidade computacional. O código está funcionando perfeitamente e muito bem organizado.
Percebi apenas uma pequeno *typo*:
*dp = calc_det_gauss_com_pivo(matriz, lin)
print('seu determinante calculado por eliminação gaussiana sem pivô é = ', dp)* Nesse caso a referência deveria apontar para calc_det_gauss_sem_pivo(matriz, lin), correto?

Outro ponto: não seria interessante incluir um teste para checar se a matriz é diagonal dominante para utilização do caso sem pivô?
comentou Jul 7 por JoaoMaria (71 pontos)  
o *Typo*  foi corrigido.
Também foi incluída a função AvaliaMat que retorna True se a matriz for diagonal dominante e False caso contrário.
Muito obrigado  pela sugestão e pela avaliação
...