幂迭代

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-为什么这些数字是随机的？显然我是从随机向量开始的，但我希望它会收敛。

问题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）。你得到的答案将仅仅取决于你是否做了偶数或奇数的迭代。