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

Question

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

Answer 1

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

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