30

谁能告诉我找到大小矩阵行列式值的最佳算法是N x N什么？

4

4 回答 4

34

这是一个广泛的讨论。

有很多算法。

一个简单的就是取LU分解。那么，由于

 det M = det LU = det L * det U

和L和U都是三角形的，行列式是 和 的对角线元素的L乘积U。那就是O(n^3)。存在更有效的算法。

于 2010-03-12T19:27:29.240 回答
11

行减少

找到 nxn 矩阵的行列式的最简单方法（实际上并不是一个坏方法）是通过行缩减。通过记住一些关于行列式的简单规则，我们可以解决以下形式：

det( A ) = α * det( R )，其中R是原始矩阵A的行梯形形式，α 是某个系数。

找到行梯形矩阵的行列式非常容易；您只需找到对角线的乘积。当您找到行梯形R时，求解原始矩阵A的行列式就可以归结为计算 α 。

你需要知道的

什么是行梯形？

有关简单定义，请参见此 [链接](http://stattrek.com/matrix-algebra/echelon-form.aspx)
**注意：** 并非所有定义都要求前导条目为 1，因此没有必要算法。

您可以使用基本行操作找到 R

交换行，添加另一行的倍数等。

您从行列式的行操作的属性中推导出 α

  1. 如果B是通过将A的一行乘以某个非零常数 ß 获得的矩阵，则

    det( B ) = ß * det( A )

    • 换句话说，您基本上可以通过将其从行列式前面拉出来从一行中“分解”出一个常数。

  2. 如果B是通过交换两行A获得的矩阵，则

    det( B ) = -det( A )

    • 如果你交换行，翻转标志。

  3. 如果B是通过将一行的倍数与A中的另一行相加获得的矩阵，则

    去（乙）=去（甲）

    • 行列式不变。

请注意，在大多数情况下，您可以仅使用规则 3 找到行列式（我相信当 A 的对角线没有零时），并且在所有情况下仅使用规则 2 和 3。规则 1 对人类进行数学运算很有帮助纸，尽量避免分数。

例子

（我做了不必要的步骤来更清楚地展示每条规则） 

  | 2 3 3 1 |
一个=| 0 4 3 -3 |
  | 2 -1 -1 -3 |
  | 0 -4 -3 2 |
R 2   R 3 , -α -> α (规则 2)
  | 2 3 3 1 |
 -| 2 -1 -1 -3 |
  | 0 4 3 -3 |
  | 0 -4 -3 2 |
R 2 - R 1 -> R 2（规则 3）
  | 2 3 3 1 |
 -| 0 -4 -4 -4 |
  | 0 4 3 -3 |
  | 0 -4 -3 2 |
R 2 /(-4) -> R 2 , -4α -> α (规则 1)
  | 2 3 3 1 |
 4| 0 1 1 1 |
  | 0 4 3 -3 |
  | 0 -4 -3 2 |
R 3 - 4R 2 -> R 3 , R 4 + 4R 2 -> R 4（规则 3，应用两次）
  | 2 3 3 1 |
 4| 0 1 1 1 |
  | 0 0 -1 -7 |
  | 0 0 1 6 |
R 4 + R 3 -> R 3
  | 2 3 3 1 |
 4| 0 1 1 1 | = 4 ( 2 * 1 * -1 * -1 ) = 8
  | 0 0 -1 -7 |
  | 0 0 0 -1 |

def echelon_form(A, size):
    for i in range(size - 1):
        for j in range(size - 1, i, -1):
            if A[j][i] == 0:
                continue
            else:
                try:
                    req_ratio = A[j][i] / A[j - 1][i]
                    # A[j] = A[j] - req_ratio*A[j-1]
                except ZeroDivisionError:
                    # A[j], A[j-1] = A[j-1], A[j]
                    for x in range(size):
                        temp = A[j][x]
                        A[j][x] = A[j-1][x]
                        A[j-1][x] = temp
                    continue
                for k in range(size):
                    A[j][k] = A[j][k] - req_ratio * A[j - 1][k]
    return A
于 2016-07-02T04:19:12.700 回答
8

如果您进行了初步研究，您可能会发现当 N>=4 时，矩阵行列式的计算变得非常复杂。关于算法，我会向您指出关于矩阵行列式的维基百科文章，特别是“算法实现”部分。

根据我自己的经验，您可以在现有的矩阵库（如Alglib ）中轻松找到 LU 或 QR 分解算法。算法本身虽然不是很简单。

于 2010-03-12T19:27:55.763 回答
0

我对 LU 分解不太熟悉，但我知道为了得到 L 或 U，您需要将初始矩阵设为三角形（U 的上三角或 L 的下三角）。但是，一旦你得到一些 nxn 矩阵 A 的三角形矩阵，并假设你的代码使用的唯一操作是 Rb - k*Ra，你可以从 i=0 求解 det(A) = Π T(i,i)到 n （即 det(A) = T(0,0) x T(1,1) x ... x T(n,n)) 用于三角矩阵 T。查看此链接以了解我在说什么关于。http://matrix.reshish.com/determinant.php

于 2015-11-25T13:14:16.320 回答