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

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

这是一种方法:

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))是第3步.

在您的公式中,您将x定义为A ^T的(列)右特征向量(使得A ^T x = 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

^{†遵循惯例.等价地,这对应于转置矩阵的右特征向量; 见下文.}