首先，是的，这些都是基于初始的三对角化（通常引用为$\frac{4}{3}n^3$翻牌）。DSYEV 只是 DSYEVX 的一个更易于使用的版本，所以我们暂时忽略它。基本分类如下：

• DSYEVX：三对角隐式移动 QR（凸出追逐）
• DSYEVD：分而治之（按等级 1 修改拼接）
• DSYEVR：使用多重相对鲁棒表示 (MRRR) 算法（对称 dqds）

这些算法中的每一个的失败次数都高度依赖于特征值分布。例如，如果您的矩阵具有几乎退化的密集特征值簇，则这些算法往往具有降低的收敛顺序。充其量你有$O(n^2)$在三对角特征问题中失败，最坏的情况是$O(n^3)$如果您的集群大小为$O(n)$. 有关更详细的分析，请参阅此工作说明。

既然你想要特征向量，让我们看看它们提取的失败次数。隐式移位 QR 不断更新用于归约的正交矩阵，因此它总是在$O(n^3)$当需要特征向量时（基本上，每个 QR 凸起扫描都需要$O(n^2)$，你需要$O(n)$通常扫）。

对于 D&C 和 MRRR，教科书的描述是先计算特征值，然后通过逆迭代提取特征向量。这需要$O(n)$每个特征向量工作，因为通常 1-2 次迭代就足够了，所以它会是$O(n^2)$找到特征值后，努力获取所有特征向量。然而，在实践中，Lapack 做了一些更复杂的事情。

我对 D&C 不熟悉，但看看源代码，看起来它会随着它不断更新特征向量，所以它的运行时间可能介于两者之间$O(n^2)$和$O(n^3)$. 对于MRRR，本文分析了逆迭代的失败。在实践中，特征向量必须在整个算法中更新，并在检测到聚类时重新正交化。此过程的一些细节可以在 DSYEVR 的界面中进行控制，并且与 D&C 一样，实际运行时间介于二次和三次之间。