最大负特征值

计算科学 线性代数 特征值
2021-11-25 13:55:47

有没有一种有效的方法来找到矩阵的最大负特征值?所讨论的矩阵是马尔可夫矩阵。

通过分解矩阵来计算矩阵的全谱不是一个可接受的解决方案。

3个回答

@VictorMay 使用逆幂迭代提供了答案,但这当然很昂贵。如果你有一个估计λ¯>λi,即它是所有特征值(包括正值)的上界,则Aλ¯I是一个负定矩阵。然后,您可以应用幂迭代(而不是幂迭代)来按幅度查找最大的特征值。称它为μ. 由于矩阵是负定的,所以你知道最负的特征值Aλmin=μ+λ¯.

而逆幂迭代需要任何合理类型的初始矩阵分解,这需要O(n3)操作,以下向量迭代是O(n2)比如前向功率迭代。

例如,为了使这个初始步骤过于复杂,可以从转换为 Hessenberg 形式开始,使用 Gerschgorin 圆定位特征值,然后修改对角线,因为QTAQ+cI=QT(A+cI)Q. 然后分解得到的三对角矩阵。

更快的收敛可能证明初始成本的费用是合理的。前向迭代与因子线性收敛

qD=|λ2|+λ¯|λ1|+λ¯=1|λ1||λ2||λ1|+λ¯
,

在哪里λ1<λ2<λk是最小和第二小的特征值。

仅具有初始移位的逆幂迭代收敛于因子

qI=λ¯|λ1|λ¯|λ2|=1|λ1||λ2|λ¯|λ2|
,

由于结构上较小的分母将小于qD. 一个人只需要一个优势O(n)反向 PIu 使用较少的迭代来证明初始成本是合理的。

这是一种解决方案:添加Ainf的对角线元素。使用逆幂迭代计算所得矩阵的最小特征值。从得到的特征值中减去以获得的最大负特征值。AAinfA