直接求不可约矩阵的前导特征向量的算法

计算科学 线性代数 本征系统
2021-11-28 01:08:26

根据 Perron-Frobenius 定理,只有正项的实矩阵(或具有称为不可约性的非负项的矩阵)将具有仅包含正项的唯一特征向量。其对应的特征值将是实数和正数,并且将是最大量级的特征值。

我有一种情况,我对这样的特征向量感兴趣。我目前正在使用 numpy 来查找所有特征值,然后取对应于最大量值的特征向量。问题在于,对于我的问题,当矩阵的大小变大时,结果开始变得疯狂,例如,以这种方式找到的特征向量可能没有所有正项。我想这是由于舍入错误。

因此,我想知道是否有一种算法可以通过利用以下事实来提供更好的结果:矩阵具有非负项并且不可约,以及我们只寻找特征向量其条目是积极的。由于存在可以利用其他矩阵属性(例如对称性)的算法,因此认为这是可能的似乎是合理的。(i)(ii)

在写这个问题时,我突然想到只迭代将起作用(从带有正条目的初始开始),但想象一下一个大矩阵收敛会很慢,所以我想我正在寻找比这更有效的算法。(不过我会试试的!)νt+1=Aνt|Aνt|ν0

当然,如果算法很容易实现和/或已经以可以从 Python 轻松调用的形式实现,那将是一个巨大的好处。

顺便说一句,如果它有任何不同,我的问题就是这个我发现当我增加矩阵大小(如上所述使用 Numpy 查找特征向量)时,它看起来正在收敛,但随后突然开始到处跳跃。的值越小,这种不稳定性就越严重λ

2个回答

您描述的计算的算法当然是所谓的幂法. 如果您有一个非退化的最大特征值,它将在您的情况下收敛。此外,如果您从只有正数项的初始猜测开始,则可以保证所有未来的迭代也是严格正数的,此外,四舍五入应该不是问题,因为在每个矩阵中-向量积,您只会将正项相加换句话说,如果您的问题具有您描述的属性,则此方法必须有效。x(k+1)=Ax(k)Ax(k)x(0)

如我的问题和 Wolfgang Bangerth 的回答中所述,我尝试了 power 方法。事实证明,对于我的应用程序来说,收敛速度并不算慢,尽管它确实取决于参数。所以在某种程度上,这是一个愚蠢的问题。

但是,我注意到有一种方法可以通过对矩阵进行重复平方来以指数方式提高该算法的速度。也就是说,让并迭代,其中是您喜欢的任何矩阵范数。(我只是将所有元素相加,因为无论如何它们都是正数。)这非常迅速地收敛到一个矩阵,该矩阵的每个列都与前导特征向量成比例。这是因为,所以迭代这个算法步进行幂迭代相同B0=ABn+1=Bn2Bn2Bnν0A2nν0n2n

尽管乘以大矩阵可能很慢(特别是在 numpy 中,不幸的是),但我发现这在大约 10 到 15 次迭代后趋于很好地收敛,所以总的来说它非常快。