电源迭代 [英] Power iteration

问题描述

我想了解电源的迭代计算矩阵的特征值。

I'm trying to understand the power iteration to calculate the eigenvalues of a matrix.

我跟着从 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]

When I run powerMethod([[0.0, 1.0], [1.0, 0.0]]) it returns random pair of numbers, such as: [0.348454142915605, 0.9373258293064111] or [0.741752215683863, 0.6706740270266026]

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

Question #1 - why are those numbers random? Obviously I started with random vector b but I hoped it would converge.

问题＃2 - 有这个在线矩阵计算器当我养活其中：

Question #2 - there is this Online Matrix Calculator to which when I feed:

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 应该得到这些特征向量中的一个，但事实并非如此。为什么输出如此不同？

If I understood correctly, returning b should get one of those eigenvectors, but it does not. Why is the output so different?

问题＃3 - 我应该怎么添加到上面的算法，使其返回某个特征值（在本例中为1或-1）？ （如果理解正确，电源迭代的回报只有一个特征值。）我怎么居然计算一个特征值？

Question #3 - what should I add to the above algorithm so that it returns one eigenvalue (In this example it is either 1 or -1)? (If understood correctly, the power iteration returns just one eigenvalue.) How do I actually calculate one eigenvalue?

推荐答案

电力法不收敛你的矩阵。

The power method does not converge for your matrix.

从维基百科的页面：

收敛是几何形状的，有比   | lambda_2 / lambda_1 |

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

Lambda_1和lambda_2是两个绝对值最高的特征值。在你的情况下，他们是1和-1所以收敛比为| 1 / -1 | = 1换句话说，错误保持不变，在每次迭代所以电源方法不起作用。

Lambda_1 and lambda_2 are the two highest absolute value eigenvalues. In your case they are 1 and -1 so the convergence ratio is |1/-1| = 1. In other words the error stays the same at each iteration so the power method does not work.

理解本的另一种方式是，你的矩阵需要的一对（A，B），并反转之成为（B，A）。你得到的答案会简单地取决于是否执行偶数或奇数迭代。

Another way of understanding this is that your matrix takes a pair (a,b) and reverses it to become (b,a). The answer you get will simply depend on whether you do an even or odd number of iterations.

这篇关于电源迭代的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！