找到矩阵行列式的最佳算法是什么？

Question

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

Answer 1

这是一个广泛的讨论.

有很多算法.

一个简单的方法是进行LU分解.然后,因为

 det M = det LU = det L * det U

和两个L和U是三角形,行列式的对角线元素的乘积L和U.那是O(n^3).存在更有效的算法.

Answer 2

减少行

找到nxn矩阵的行列式的最简单方法(实际上并不是坏方法)是通过行减少.通过记住关于决定因素的一些简单规则,我们可以在以下形式中解决:

det(A)=α*det(R),其中R是原始矩阵A的行梯形形式,α是一些系数.

以行梯形形式找到矩阵的行列式非常简单; 你只需找到对角线的产物.解决原矩阵的行列式一个然后就归结为您找到列梯形形式计算α [R .

你需要知道什么

什么是行梯队形式？

请参阅此链接以获取简单的定义
注意:并非所有定义都要求前导条目使用1,并且此算法不需要.

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

交换行,添加另一行的倍数等.

您从决定因素的行操作属性中导出α

1. 如果B是通过将A行乘以某个非零常数ß而得到的矩阵,那么

   det(B)=ß*det(A)

   • 换句话说,你可以通过将它拉出行列式前面来从行中"分解"一个常量.

2. 如果B是通过交换两行A获得的矩阵,那么

   det(B)= -det(A)

   • 如果您交换行,请翻转符号.

3. 如果B是通过将一行的倍数添加到A中的另一行而获得的矩阵,那么

   det(B)= det(A)

   • 决定因素不会改变.

请注意,在大多数情况下,你只能使用规则3找到行列式(当我的A的对角线没有零时,我相信),并且在所有情况下只有规则2和3.规则1对人类进行数学运算很有帮助纸,试图避免分数.

例

(我做了不必要的步骤来更清楚地演示每条规则)
| 2 3 3 1 | A=| 0 4 3 -3 | | 2 -1 -1 -3 | | 0 -4 -3 2 | R2 <-> R3, -? -> ? (Rule 2) | 2 3 3 1 | -| 2 -1 -1 -3 | | 0 4 3 -3 | | 0 -4 -3 2 | R2 - R1 -> R2 (Rule 3) | 2 3 3 1 | -| 0 -4 -4 -4 | | 0 4 3 -3 | | 0 -4 -3 2 | R2/(-4) -> R2, -4? -> ? (Rule 1) | 2 3 3 1 | 4| 0 1 1 1 | | 0 4 3 -3 | | 0 -4 -3 2 | R3 - 4R2 -> R3, R4 + 4R2 -> R4 (Rule 3, applied twice) | 2 3 3 1 | 4| 0 1 1 1 | | 0 0 -1 -7 | | 0 0 1 6 | R4 + R3 -> R3 | 2 3 3 1 | 4| 0 1 1 1 | = 4 ( 2 * 1 * -1 * -1 ) = 8 | 0 0 -1 -7 | | 0 0 0 -1 |

Answer 3

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

根据我自己的经验,您可以在现有的矩阵库(如Alglib)中轻松找到LU或QR分解算法.算法本身并不是很简单.