4

在 Matlab 中检查矩阵是否对称正定的最快（运行时间）方法是什么？我已经针对大小（维度）从 10000 到 100000 不等的大量稀疏矩阵运行了这个测试？

编辑：

Cholesky 对于我的目的来说成本过高。如果它表明矩阵可能是 spd，我首先需要进行脏检查，然后我可能会使用 CHOL 更可靠地只检查那些矩阵

4

5 回答 5

3

如此处所述，您可以使用chol函数来检查矩阵是否为 PD。

CHOL 函数提供可选的第二个输出参数“p”，如果发现矩阵是正定的，则​​该参数为零。如果 CHOL 函数只提供了一个输出参数，并且还给出了一个非正定矩阵，则 CHOL 函数将返回错误。注意：CHOL 期望其输入矩阵是对称的，并且只查看矩阵的上三角部分。

至于对称性，您可以使用以下功能：

issym = @(m) isequal(tril(x), triu(x)');
于 2013-05-22T06:46:20.327 回答
2

我认为要有效地做到这一点，这是一个不平凡的问题。如果矩阵不是正定矩阵，Cholesky 算法将失败，因此最好自己实现，这也有一个优势，即当算法失败时，由于输入不是正定矩阵，人们可以控制该怎么做。我使用 C# 而不是 Matlab 进行数学编程，而我的 Cholesky 实现只有几行代码，所以并不难。如果您使用其他人的算法，则取决于它的实现方式，如果您输入非对称矩阵，您可能会得到误导性结果，因为某些实现假设矩阵是对称的。我能想到的唯一快速预测试是检查矩阵迹线，如果矩阵是 SPD，这将是肯定的。

于 2013-05-22T07:59:38.300 回答
1

我想你可能会看看你的矩阵的特征值，并检查它们是否都是不同的和实值的。

因此，您可能会认为调用eig函数如下：

[V,D] = eig(A)

我希望这有帮助

于 2013-05-22T06:52:35.290 回答
0

您可以通过使用Gershgorin 定理（用于估计特征值）从考虑中消除一些矩阵来稍微精简该领域。

结果是，如果将每一行（对角线上的元素除外）上元素的绝对值相加，则得到半径r k。相应的特征值必须位于对角线上的值的半径范围内，即a kk。因此，如果所有k的 a kk > r k，则您的矩阵是 PD。如果某个k的kk <= r k，您的矩阵可能仍然是 PD，因为这意味着一个或多个 Gershgorin 圆盘横跨虚轴（或零），并且实际特征值可能在任一侧。

假设issymmetric(A)成功，类似于：

r = sum(abs(A),2)-diag(A);
if length(find(r>diag(A))) == 0,
    % No circles cross the origin: A is PD
else
    % A might still be PD: do some other test
end

使用矩阵 对此进行快速'n'dirty 测试M=sprandsym(n,n,d)+c*speye(n,n)，其中一些是 PD，而另一些不是（玩弄n、d和c），似乎表明它识别了许多但不是全部的 SPD 矩阵（如预期的那样），但是与“大” n（及其潜在的 Cholesky）相比，它非常便宜。对于您的特定矩阵，它可能有效，也可能无效。YMMV，我猜。eig()

很明显，我还没有弄清楚所有细节，但我相信你明白了。

于 2018-08-01T02:51:13.143 回答
0

关于上面提到的trace测试：假设矩阵A是：

A =
    1.0000    1.6000
    1.6000    1.0000

然后

trace(A) is 2

但是 A 的特征值为 eig(A)

ans =
   -0.6000
    2.6000

因此，特征值并不都是正的。因此，该矩阵不是 SPD，但其迹线 > 0。基于此反例，我怀疑迹线测试不是结论性的。

于 2018-07-31T23:55:58.033 回答