幂迭代

Question

我正在尝试理解幂迭代法来计算矩阵的特征值。

我按照维基百科上的算法进行了操作：

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 - 有一个在线矩阵计算器，当我输入：

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

这个幂法对你的矩阵不收敛。

根据维基百科的解释：

收敛是几何级数，比例为 |lambda_2 / lambda_1|

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

另一种理解方式是，你的矩阵会把一对数 (a,b) 反转成 (b,a)。你得到的结果将取决于你进行的迭代次数是偶数还是奇数。