algorithm - 检查矩阵是否为奇异的快速方法？（不可逆，det = 0）

Question

检查一个小方阵（<16*16 个元素）是否为奇异（不可逆，det = 0）的最快算法是什么（链接到 C 或 C++ 示例会很酷）？

Answer 1

最好的方法是通过 SVD 计算条件数并检查它是否大于 1 / epsilon，其中 epsilon 是机器精度。

如果您允许假阴性（即矩阵有缺陷，但您的算法可能无法检测到它），您可以使用维基百科文章中的 max(a_ii) / min(a_ii) 公式作为条件数的代理，但是您必须首先计算 QR 分解（该公式适用于三角矩阵）：A = QR 与 R 正交，然后 cond(A) = cond(Q)。还有一些技术可以用 O(N) 操作计算 Q 的条件数，但有更复杂的。

Answer 2

我同意高斯消元法。http://math.nist.gov/javanumerics/jama/doc/Jama/LUDecomposition.html文档 LU 分解 - 从矩阵构造 LU 分解后，您可以调用其上的方法来获取行列式。我的猜测是，至少值得将其与任何更专业的方案进行比较。

Answer 3

在 R 中，差异很接近，但 qr 分解胜出。尝试以下操作：

    Sig <- matrix(rnorm(16),4,4)
    
    a <- Sys.time()
    for(j in 1:1000){
      out <- svd(Sig)
      cond <- any(out$d < 1e-10)
    }
    Sys.time()-a
    
    a <- Sys.time()
    for(j in 1:1000){
      out <- qr(Sig)
      cond <- out$rank < NROW(Sig)
    }
    Sys.time()-a

Answer 4

最快的方法可能是为您希望处理的每个大小矩阵硬编码一个行列式函数。

这是 N = 3 的一些伪代码，但是如果您查看行列式的莱布尼茨公式，则所有 N 的模式都应该是清晰的。

function is_singular3(matrix) {
    det = matrix[1][1]*matrix[2][2]*matrix[3][3]
        - matrix[1][1]*matrix[2][3]*matrix[3][2]
        - matrix[1][2]*matrix[2][1]*matrix[3][3]
        + matrix[1][2]*matrix[2][3]*matrix[3][1]
        + matrix[1][3]*matrix[2][1]*matrix[3][2]
        - matrix[1][3]*matrix[2][2]*matrix[3][1];

     if(det==0) return true
     else return false
}