Code Python pour le déterminant de la matrice N x N

Question

mon code ne fonctionne que pour la matrice 3x3 comment faire une modification pour travailler pour la matrice N x N? `

alist = [] 

def det(m): 
if len(m) > 2: 
    for i in range(len(m)): 
     new_m = deepcopy(m) 
     minor(new_m,i) 
     multiplier = m[i][0] * math.pow(-1,i) 
     recursive = det(new_m) 
     alist.append(multiplier * recursive) 
else: 
    return (m[0][0]*m[1][1] - m[0][1]*m[1][0]) 

def minor(matrix,row): 
    length = len(matrix) 
    for i in range(length): 
     matrix[i].pop(0) 
    matrix.pop(row) 
    return matrix 

Answer 1

Vous devez utiliser la bibliothèque numpy ils offrent un grand outil pour calculer le déterminant d'une matrice:

import numpy 
matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]] 
det = numpy.linalg.det(matrix) 

Answer 2

Comme Rory Daulton mentionne, et comme je suis assez sûr que des milliers de personnes ont déjà mentionné, nous ne pouvons pas calculer un déterminant général par la méthode des mineurs. Cette méthode n'a qu'une valeur théorique (par exemple, pour prouver que le déterminant d'une matrice diagonale est le produit de ses éléments diagonaux). À moins que l'on vous demande spécifiquement de mettre en œuvre une telle solution (et uniquement à des fins éducatives), vous devriez opter pour l'élimination gaussienne, la factorisation de Choleski, et ainsi de suite.

Answer 3

La fonction det_recursive fonctionne pour une matrice carrée de n'importe quelle taille. Cependant, comme il utilise la méthode naïve récursive pour étendre la formule de Laplace, il est très lent pour les matrices de grande taille.

Une autre technique consiste à transformer la matrice en une forme triangulaire supérieure en utilisant la technique d'élimination de gauss. Alors le déterminant de la matrice est simplement le produit des éléments diagonaux de la forme transformée triangulaire de la matrice originale.

Fondamentalement, numpy est le plus rapide, mais en interne, il utilise une sorte de méthode de transformation de matrice linéaire similaire à ce que fait l'élimination de gauss. Cependant, je ne suis pas sûr de ce que c'est exactement!

In[1] 
import numpy as np 

In[2] 
mat = np.random.rand(9,9) 
print("numpy asnwer = ", np.linalg.det(mat)) 

Out[2] 
numpy asnwer = 0.016770106020608373 

In[3] 
def det_recursive(A): 
    if A.shape[0] != A.shape[1]: 
     raise ValueError('matrix {} is not Square'.format(A)) 

    sol = 0 
    if A.shape != (1,1): 
     for i in range(A.shape[0]): 
      sol = sol + (-1)**i * A[i, 0] * det_recursive(np.delete(np.delete(A, 0, axis= 1), i, axis= 0)) 
     return sol 
    else: 
     return A[0,0] 
​ 

In[4] 
print("recursive asnwer = ", det_recursive(mat)) 

Out[4] 
recursive asnwer = 0.016770106020608397 

In[5] 
def det_gauss_elimination(a,tol=1.0e-9): 
    """ 
    calculate determinant using gauss-elimination method 
    """ 
    a = np.copy(a) 

    assert(a.shape[0] == a.shape[1]) 
    n = a.shape[0] 

    # Set up scale factors 
    s = np.zeros(n) 

    mult = 0 
    for i in range(n): 
     s[i] = max(np.abs(a[i,:])) # find the max of each row 
    for k in range(0, n-1): #pivot row 
     # Row interchange, if needed 
     p = np.argmax(np.abs(a[k:n,k])/s[k:n]) + k 
     if abs(a[p,k]) < tol: 
      raise Exception("Matrix is singular") 
     if p != k: 
      a[[k,p],:] = a[[p, k],:] 
      s[k],s[p] = s[p],s[k] 
      mult = mult + 1 
​ 
     # convert a to upper triangular matrix 
     for i in range(k+1,n): 
      if a[i,k] != 0.0: # skip if a(i,k) is already zero 
       lam = a [i,k]/a[k,k] 
       a[i,k:n] = a[i,k:n] - lam*a[k,k:n] 
​ 
    deter = np.prod(np.diag(a))* (-1)**mult 
    return deter 

In[6] 
print("gauss elimination asnwer = ", det_gauss_elimination(mat)) 

Out[6] 
gauss elimination asnwer = 0.016770106020608383 

In[7] 
print("numpy time") 
%timeit -n3 -r3 np.linalg.det(mat) 
print("\nrecursion time") 
%timeit -n3 -r3 det_recursive(mat) 
print("\ngauss_elimination time") 
%timeit -n3 -r3 det_gauss_elimination(mat) 

Out[7] 
numpy time 
40.8 µs ± 17.2 µs per loop (mean ± std. dev. of 3 runs, 3 loops each) 

recursion time 
10.1 s ± 128 ms per loop (mean ± std. dev. of 3 runs, 3 loops each) 

gauss_elimination time 
472 µs ± 106 µs per loop (mean ± std. dev. of 3 runs, 3 loops each)