计算科学 - 计算实稀疏矩阵的特征多项式 - 吾爱随笔录

计算科学线性代数算法稀疏矩阵

2021-11-24 08:49:11

给定一个通用稀疏矩阵与~~m << n~~（校正：）非零元素（通常是 )。是通用的，因为它没有特定的属性（例如正定性），并且没有假设结构（例如带状）。 $A \in \mathbb{R}^{n\times n}$ $m \ll n^2$ $m \in {\cal O}(n)$ $A$

有哪些好的数值的特征多项式或最小多项式？ $A$

3个回答

如果复杂度不是一个障碍，那么您可能想看看 Danilevskii 方法。它在俄罗斯关于数值线性代数的文献中非常有名，但英语中的信息并不多。你可以从这个链接开始。 $O(n^3)$

这个想法相当简单：通过“类似高斯消元”的相似变换，矩阵逐渐简化为Frobenius 范式。如果您找不到信息，我可以使算法更详细。

您可以使用数值方法，如 QR 分解或幂法及其实数（逆幂等）来计算通用矩阵的特征值。之后，您可以通过分解来计算特征多项式： (λ-λ1)(λ-λ2)...(λ-λn)=0 其中 λi 是计算的特征值。以下是关于幂和 QR 方法的简短介绍：

顺便说一句：你想说你有个条目吗？如果确实则大多数行和列将完全为空，并且特征多项式实际上可能不是而是。 $m \ll O(n^2)$ $m \ll O(n)$ $n$ $O(m)$

其它你可能感兴趣的问题