python - 快速有效地计算已知特征值的特征向量

Question

我的问题的简短版本:

如果我们已经知道属于特征向量的特征值，那么计算矩阵 A 的特征向量的最佳方法是什么？

更长的解释:

我有一个大的随机矩阵 A，因为它是随机的，所以它有一个非负左特征向量 x(这样 A^Tx=x )。

我正在寻找快速有效的方法来对这个向量进行数值计算。 (最好是在 MATLAB 或 numpy/scipy 中——因为它们都围绕着 ARPACK/LAPACK，任何一个都可以)。

我知道 1 是 A 的最大特征值，所以我知道调用类似这样的 Python 代码:

from scipy.sparse.linalg import eigs
vals, vecs = eigs(A, k=1)

将导致 vals = 1 和 vecs 等于我需要的向量。

但是，这里困扰我的是计算特征值通常比求解线性系统更难，而且一般来说，如果矩阵 M 具有特征值 l，然后找到合适的特征向量就是求解方程 (M - 1 * I) * x = 0，至少在理论上，这是一个运算比计算特征值更简单，因为我们只求解线性系统，更具体地说，找到矩阵的零空间。

但是，我发现 MATLAB 中的所有零空间计算方法都依赖于 svd 计算，这是我无法在我的大小的矩阵上执行的过程。我也不能调用线性方程的求解器，因为它们都只能找到一个解，而那个解是 0(是的，这是一个解，但不是我需要的那个)。

有什么方法可以避免调用类似 eigs 的函数来比计算最大特征值和伴随的特征向量更快地解决我的问题？

Answer 1

这是一种使用 Matlab 的方法:

1. 令x表示与特征值1相关联的(行)左^†特征向量。它满足线性方程组(或矩阵方程)xA = x，或x(A−I)=0。
2. 为避免该方程组的全零解，删除第一个方程并在其余方程中任意将 x 的第一个条目设置为 1。
3. 求解剩余的方程(x₁ = 1)以获得 x 的其他项。

使用 Matlab 的例子:

>> A = [.6 .1 .3
        .2 .7 .1
        .5 .1 .4]; %// example stochastic matrix
>> x = [1, -A(1, 2:end)/(A(2:end, 2:end)-eye(size(A,1)-1))]
x =
   1.000000000000000   0.529411764705882   0.588235294117647
>> x*A %// check
ans =
   1.000000000000000   0.529411764705882   0.588235294117647

注意代码-A(1, 2:end)/(A(2:end, 2:end)-eye(size(A,1)-1))是step 3.

在您的公式中，您将 x 定义为 A^T 的(列)右特征向量(例如A^Tx = x)。这只是上面代码中的 x.':

>> x = x.'
x =
   1.000000000000000
   0.529411764705882
   0.588235294117647
>> A.'*x %// check
ans =
   1.000000000000000
   0.529411764705882
   0.588235294117647

您当然可以归一化特征向量以求和 1:

>> x = x/sum(x)
x =
   0.472222222222222
   0.250000000000000
   0.277777777777778
>> A.'*x %'// check
ans =
   0.472222222222222
   0.250000000000000
   0.277777777777778

---

^{† 继 usual convention .等效地，这对应于转置矩阵的右特征向量。}