python - 幂迭代

Question

我试图了解计算矩阵特征值的幂迭代。

我遵循了 en.wikipedia.org/wiki/Power_iteration#The_method 中的算法:

from math import sqrt

def powerIteration(A):

    b = [random() for i in range(len(A))]
    tmp = [0] * len(A)

    for iteration in range(10000):

        for i in range(0, len(A)):
            tmp[i] = 0
            for j in range(0, len(A)):
                tmp[i] += A[i][j] * b[j]

        normSq = 0
        for k in range(0, len(A)):
            normSq += tmp[k] * tmp[k]
        norm = sqrt(normSq)

        for i in range(len(A)):
            b[i] = tmp[i] / norm

    return b

当我运行 powerMethod([[0.0, 1.0], [1.0, 0.0]]) 时，它返回随机数字对，例如:[0.348454142915605, 0.9373258293064111] 或 [0.741752215683863, 0.6706740270266026]

问题 #1 - 为什么这些数字是随机的？显然，我从随机向量 b 开始，但我希望它会收敛。

问题 #2 - 有这个 Online Matrix Calculator当我喂食时:

0 1
1 0

它返回:

Eigenvalues:
( 1.000, 0.000i)
(-1.000, 0.000i)

Eigenvectors:
( 0.707, 0.000i) (-0.707, 0.000i)
( 0.707, 0.000i) ( 0.707, 0.000i)

如果我理解正确，返回 b 应该得到这些特征向量之一，但事实并非如此。为什么输出如此不同？

问题 #3 - 我应该在上面的算法中添加什么，以便它返回一个特征值(在这个例子中它是 1 或 -1)？ (如果理解正确，幂迭代仅返回一个特征值。)我如何实际计算一个特征值？

Answer 1

对于您的矩阵，幂法不收敛。

来自维基百科页面:

The convergence is geometric, with ratio |lambda_2 / lambda_1|

Lambda_1 和 lambda_2 是绝对值最高的两个特征值。在你的例子中它们是 1 和 -1 所以收敛比是 |1/-1| = 1。换句话说，误差在每次迭代中都保持不变，因此幂法不起作用。

理解这一点的另一种方式是，您的矩阵采用一对 (a,b) 并将其反转为 (b,a)。您得到的答案将仅取决于您进行的迭代次数是偶数还是奇数。