矩阵行列式

问题描述 投票：0回答：4

我有这个函数来获取矩阵的行列式

    def determinant(self) -> int:
        """
        Calculates the Determinant of matrix objects.
        Parameters
        ----------
        self
        Returns
        -------
        int
        Example
        -------
        >>> _matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
        >>> _matrix = Matrix(_matrix)
        >>> _matrix.determinant()
        0
        """
        if self.row != self.column:
            raise ValueError('Cannot get determinant of this matrix! Must be a square Matrix')
        else:
            def det(matrix):
                row = len(matrix)
                col = len(matrix[0])

                if (row, col) == (1, 1):
                    return matrix[0][0]

                # hard coding for 2x2
                elif (row, col) == (2, 2):
                    return matrix[0][0] * matrix[1][1] - matrix[0][1] * matrix[1][0]

                # using sarrus method to solve for 3x3, it's a little faster.
                elif (row, col) == (3, 3):
                    matrix1 = matrix[:]

                    # Extending matrix to use Sarrus Rule.
                    for i in range(row - 1):
                        _col = []
                        for j in range(col):
                            _col.append(matrix1[i][j])
                        matrix1.append(_col)

                    # Calculating Determinant
                    # Adding part
                    add_pointers = [(i, i) for i in range(row)]
                    result = 0
                    for pointer in range(row):
                        temp = 1
                        for tup in add_pointers:
                            i, j = tup
                            temp *= matrix1[i + pointer][j]
                        result += temp

                    # Subtracting part
                    sub_pointers = [((row - 1) - i, 0 + i) for i in range(row)]
                    for pointers in range(row):
                        temp = 1
                        for tup in sub_pointers:
                            i, j = tup
                            temp *= matrix1[i + pointers][j]
                        result -= temp
                    return result

                else:
                    sign = -1
                    result = 0
                    row1 = [matrix[0][i] * (sign ** i) for i in range(col)]
                    for x, y in enumerate(row1):
                        mat = matrix[:][1:]
                        sub_matrix = [[mat[i][j] for j in range(col) if j != x] for i in range(row - 1)]
                        result += y * det(sub_matrix)
                    return result

            return det(self.matrix)

我有 

2x2
和 
3x3
矩阵的硬编码行列式，然后我重新讨论其余的

正如你所看到的，它使用

nxn
矩阵的递归...我确信有一种更快的方法，这是非常慢的 建议使用该方法的 python 实现，谢谢

python recursion matrix
4个回答
0
投票

这里是通过切片和简单乘法求 3x3 矩阵行列式的 Python 代码

import numpy as np

def crossMulti(smallMatrix):
    # Calculate determinant of 2x2 matrix
    return (smallMatrix[0][0] * smallMatrix[1][1]) - (smallMatrix[1][0] * smallMatrix[0][1])

def Determinant(matrix):
    # Manual determinant calculation for 3x3 matrix
    a = matrix[0][0]
    b = matrix[0][1]
    c = matrix[0][2]
    det = (
        a * crossMulti(matrix[1:, 1:]) - 
        b * crossMulti(matrix[1:, [0, 2]]) + 
        c * crossMulti(matrix[1:, :2])
    )
    return det

matrix = np.array([[1, 2, 3], [4, 5, 6], [7, 8, 9]])
print("Matrix:")
print(matrix)
print()

print("Determinant using NumPy:", np.linalg.det(matrix))
print("Determinant using Manual Function:", Determinant(matrix))
-1
投票

最常见的最佳方法是 

list comprehension
或 
numpy
模块。

原因：几乎肯定会比 numpy 数组慢，因为 numpy 数组具有连续和同构的性质。简单来说，

for loops
基本上是同一类型的一个内存块，而
numpy
指向不同的内存块并且可以包含任何类型。
这是 numpy 示例（对于 2d）：


list


其中一条评论已经（正确地）指出了这一点：

https://numpy.org/doc/stable/reference/ generated/numpy.linalg.det.html

对于更一般的较大 m*n 矩阵，优势将是显着的。

    





    

    
    
    

    

        

            

                

                    
-1
投票

                    
                

            

        

        


import numpy as np

a = np.array([[1, 2], [3, 4]])
result = np.linalg.det(a)


print(result)




输出：


"""
M:
    M11 M12 M13
    M21 M22 M23
    M31 M32 M33

detM:
    M11 * det2D([ [M22, M23], [M32, M33] ]) - 
    M12 * det2D([ [M21, M23], [M31, M33] ]) + 
    M13 * det2D([ [M21, M22], [M31, M32] ])    
"""

import numpy as np

def det3D(M):
    a = M[0][0] * det2D(np.array([ [ M[1][1],M[1][2] ], [ M[2][1],M[2][2] ] ]))
    b = M[0][1] * det2D(np.array([ [ M[1][0],M[1][2] ], [ M[2][0],M[2][2] ] ]))
    c = M[0][2] * det2D(np.array([ [ M[1][0],M[1][1] ], [ M[2][0],M[2][1] ] ]))
    return a - b + c


def det2D(M):
    return M[0][0]*M[1,1] - M[0][1] * M[1][0]


M = [ [1,0,0], [0,2,2], [0,2,4] ]
A = det3D(M)
B = round(np.linalg.det(M))
print(A)
print(B)
print(A == B)


    



    

    
    
    

    

        

            

                

                    
-1
投票

                    
                

            

        

        


注意：有两种方法可以找到行列式，在大型矩阵的最佳情况下，
4
4
True

 的运行速度比 
smartDetNxN
 快 35 倍以上。
detNxN


输出：


import numpy as np

# compute partial determinant terms
def terms(M, col = 1, row = 1):
    return [x[:col-1] + x[col:] for x in M[0:row-1] + M[row:]]

# compute determinant using first row
def detNxN(M):
    N = len(M[0])
    # Recursion Base: 2x2 determenant
    if (N == 2): 
        M = np.array(M)
        return M[0][0] * M[1,1] - M[0][1] * M[1][0]
    # Recursion Loop
    else: 
        rowValues = M[:1][0]
        colsSigns = [1 if (col % 2 == 0) else -1 for col in range(N)]
        colsDets = [detNxN(terms(M, col + 1)) for col in range(N)]
        return sum([rowValues[col] * colsSigns[col] * colsDets[col] for col in range(N)])

# compute determinant using optimum row while skipping zero value columns
def smartDetNxN(M):
    N = len(M[0])
    # Recursion Base: 2x2 determenant
    if (N == 2): 
        M = np.array(M)
        return M[0][0] * M[1,1] - M[0][1] * M[1][0]
    # Recursion Loop
    else: 
        # find optimun row
        flatM = [len(np.flatnonzero(x)) for x in M]
        row = flatM.index(min(flatM))
        rowSign = 1 if (row % 2 == 0) else -1
        rowValues = M[row]
        # compute partial determinants
        colsSigns = [1 if (col % 2 == 0) else -1 for col in range(N)]
        colsDets = [smartDetNxN(terms(M, col + 1, row + 1)) if (rowValues[col] != 0) else 0 for col in range(N)]
        return sum([rowValues[col] * rowSign * colsSigns[col] * colsDets[col] for col in range(N)])

# test case for matrix
def testCase(M):
    print()
    N1 = len(M[0])
    N2 = len(M[0])
    A = smartDetNxN(M)
    B = round(np.linalg.det(M))
    print("Matrix %ix%i:" % (N1, N2))
    print("Actual detM = %d, Expected detM = %d " % (A, B))
    print("Test Pass:", A == B)

# main
def main():   
    # Matrix 2 x 2
    M1 = [[1,2,],[0,1]] 
    testCase(M1)
    
    # Matrix 3 x 3
    M2 = [[1,2,3],[2,1,2],[3,2,1]]
    testCase(M2)
    
    # Matrix 4 x 4
    M3 = [[1,2,3,4], [2,1,0,3], [3,0,1,2], [4,0,0,1]]
    testCase(M3)
    
    # Matrix 10 x 10
    M4 = [
        [0,1,2,3,4,5,6,7,8,9],
        [1,1,0,0,0,0,0,0,0,8],
        [2,0,1,0,0,0,0,0,0,7],
        [3,0,0,1,0,0,0,0,0,6],
        [4,0,0,0,1,0,0,0,0,5],
        [5,0,0,0,0,1,0,0,0,4],
        [6,0,0,0,0,0,1,0,0,3],
        [7,0,0,0,0,0,0,1,0,2],
        [8,0,0,0,0,0,0,0,1,1],
        [9,0,0,0,0,0,0,0,0,0],
    ]
    testCase(M4)
main()


    
	

    

    


  

  

    
最新问题


  





  

    © www.soinside.com 2019 - 2025. All rights reserved.