0
$\begingroup$

In my textbook they describe the power method for finding the largest eigenvalue for a nonsingular matrix A. They present the following algorithm

input n, A, x, M  
output 0,x  
for k=1 to M do  
    y <- Ax
    r <- y_1 / x_1
    x <- y / ||y||
    output k, x, r
end do

There is then an assignment where you should run this algorithm on the following input $$Z = \left[\begin{array}{ccc}{3} & {2} & {1} \\ {0} & {2} & {0} \\ {0} & {0} & {1}\end{array}\right], \quad x=(0,0,6)^{T}, \quad M=50, \quad n=3$$

I dont understand how this should work, or if i am misreading the pseudocode?

$\endgroup$
  • $\begingroup$ $r$ should converge towards the largest eigenvalue. $\endgroup$ – user488081 Oct 12 '19 at 17:15
  • $\begingroup$ Kincaid and Cheney is a pretty standard text, which has been pretty thoroughly vetted since it was first published. Are you sure that you have copied everything down correctly? Can you please tell us what page(s) you are finding this on? $\endgroup$ – Xander Henderson Oct 12 '19 at 17:17
  • $\begingroup$ Are you sure it is $r \gets y_1/x_1$ and not $r \gets \|y\|_1/\|x\|_1$? $\endgroup$ – user856 Oct 12 '19 at 18:02
1
$\begingroup$

There are two caveats to the algorithm. First is that the starting vector $x$ should have a non-zero projection on the eigenvector with the eigenvalue of largest absolute value. The algorithm is based on the assumption that a geometric progression with constant ratio the largest absolute value will dominate all of the other geometric progressions with the other eigenvalues assuming that they have strictly smaller absolute values. Picking a random starting vector $x$ will almost certainly be sufficient to avoid the problem.

Second is that in the limit, the vector $y$ will be a multiple of $x$ with ratio the desired eigenvalue. That means that any coordinate of $y$ will approximately be a constant multiple of the same coordinate of $x$. If the coordinate of $x$ is zero, then division by it is not possible, so you have to pick a nonzero coordinate (which must exist assuming nonsingular $A$) instead. There can be other variations which work.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ With the norm you lose the sign, that is, you approximate the absolute value of the eigenvalue. $\endgroup$ – Lutz Lehmann Oct 12 '19 at 18:42
  • $\begingroup$ The Rayleigh quotient $x^TAx/x^Tx$ will give you the eigenvalue including the sign. $\endgroup$ – Carl Christian Oct 12 '19 at 18:48
  • $\begingroup$ @CarlChristian : Yes, but that additional computation has to be added to the algorithm, preferably organized in a way that avoids duplicate computations. $\endgroup$ – Lutz Lehmann Oct 12 '19 at 20:23
  • $\begingroup$ @Lutz: Yes, we must replace the search for a nonzero component of $x$ with the statement $r \gets y^Tx$. Since $y = Ax$ and $x$ is normalized this is the only change. $\endgroup$ – Carl Christian Oct 12 '19 at 21:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy