Talk:Power iteration

Added an Algorithm

I added an algorithm to calculate the power iteration in a C program. Comments/Questions? Rankmaniac42 (talk) 03:51, 12 November 2008 (UTC)

In the algorithm, shouldn't you have a b=tmp, instead of r=tmp? You want to update and move away from the initial b values. --76.100.191.59 (talk) 02:59, 24 April 2009 (UTC)

I think there is an error in the algorithm,.

tmp[i] += b[j]*A[j][i];

should be changed to

tmp[i] += b[j]*A[i][j];

Reference in Networkx (python graph library) source code and other code references on the web.

https://networkx.lanl.gov/trac/browser/networkx/trunk/networkx/algorithms/centrality/eigenvector.py

http://adorio-research.org/wordpress/?p=1308

What do you think?--4nT0 (talk) 13:17, 28 August 2010 (UTC)

Should be something like this instead, I think. (See algorithm description on the page for Primary Component Analysis)

   for(i=0; i<n; i++)
        tmp[i] = 0;
   
   for(i=0; i<n; i++)
   {
       bdotx = 0;
       
       for (j=0; j<n; j++)
           bdotx += A[i][j] * b[j];
       
       for (j=0; j<n; j++)
           tmp[i] += bdotx * A[i][j];
   }

Finding the 2nd Eigenvalue

I would like to add the following - please let me know if there are any comments.

In order to find the second eigenvalue, the Power Method can be used on the following matrix:

$A'=A-\lambda _{1}w_{1}w_{1}^{T}$

where

$w_{i}={\frac {v_{i}}{|v_{i}|}}$.

The matrix $A'$ has the same eigenvectors and eigenvalues as $A$ with the exception that $\lambda _{1}=0$. To see this we multiply by $w_{1}$

${\begin{aligned}A'w_{1}&=Aw_{1}-\lambda _{1}w_{1}w_{1}^{T}w_{1}\\&=\lambda _{1}w_{1}-\lambda _{1}w_{1}\\&=0\end{aligned}}$

for any other eigenvector we have

${\begin{aligned}A'w_{2}&=Aw_{2}-\lambda _{1}w_{1}w_{1}^{T}w_{2}\\&=\lambda _{2}w_{1}\\\end{aligned}}$

since $w_{1}$ and $w_{2}$ are orthogonal to each other. --Adieyal 15:05, 5 July 2007 (UTC)

Why are $w_{1}$ and $w_{2}$ orthogonal to each other? If I understand you correctly, $w_{1}$ and $w_{2}$ are (normalized) eigenvectors. Eigenvectors of a general matrix are not orthogonal, but eigenvalues of a symmetric matrix (and, more generally, a normal matrix) are. Perhaps you're assuming that A is symmetric? -- Jitse Niesen (talk) 20:48, 6 July 2007 (UTC)

Clearly you're right - I'm not sure why I thought that the matrix was symmetric. Regardless, the above method is still useful for symmetric matrices. --Adieyal 17:50, 29 July 2007 (UTC)

Is this the procedure called deflation? Anyway, feel free to add it in, preferably with a reference. It would be great if you could check the rest of the article and rewrite the parts where you can improve on it. -- Jitse Niesen (talk) 04:12, 30 July 2007 (UTC)

For w2, surely A'w2 should be lambda2 X w2, not lambda1 X w1 since the inner product term disappears, and Aw2=lambda2 X w2 by definition. Sorry about my formatting. —Preceding unsigned comment added by 147.114.226.173 (talk) 12:21, 10 July 2008 (UTC)

The Power Method uses Power Iteration and deflation to try to estimate all eigenvalues and vectors of a matrix of any size, by repeating this step after each eigenpair has been found. I propose that a new article Power Method be made to describe this complete process. (see http://distance-ed.math.tamu.edu/Math640/chapter6/node4.html at the bottom) Also, power iteration can be performed on the inverse of a matrix to find the smallest eigenvector. It is also very widely used in practice for engineering applications when dealing with large matricies. 192.102.214.6 (talk) 12:23, 15 August 2008 (UTC)

Also see http://www.maths.lancs.ac.uk/~gilbert/m306c/node10.html . The term Power Method is also very widely known. 192.102.214.6 (talk) 13:02, 15 August 2008 (UTC)

Broken links

I think the first reference to http://www4.ncsu.edu/~ipsen/ps/slides_imacs.pdf is broken. Please check. —Preceding unsigned comment added by 81.33.18.197 (talk) 09:31, 4 October 2007 (UTC)

multiple eigenvalues by power method

"However, it will find only one eigenvalue (the one with the greatest absolute value) and it may converge only slowly."

---

I guess it is a matter of semantics, but this statement is not true for all power methods. It is certainly true for the power method presented in the article, but it is not true for the power method presented in

"Multiple extremal eigenpairs by the power method," Journal of Computational Physics, Volume 227 , Issue 19 (October 2008)

Maybe different names are needed for these slightly different "power methods?" Certainly the statements:

"The power iteration is a very simple algorithm. It does not compute a matrix decomposition, and hence it can be used when A is a very large sparse matrix."

are true for the aforementioned alternate power method.

Nooseweak

---

The lines:

   for(k=0; k<n; k++){
        norm_factor += tmp[k];
   }

are not calculating a vector norm - just look at the wikipedia definition of a norm. I guess it should mean:

   for(k=0; k<n; k++){
        norm_factor += abs(tmp[k]);
   }

Which would refer to the 1-Norm (Manhattan-Norm)

Konan —Preceding unsigned comment added by 93.134.111.116 (talk) 21:41, 17 May 2011 (UTC)

The code presented is inaccurate

The algorithm illustrated by the code appears to be innacurate. The normalisation of the generated vector (which is the product of the matrix and the previous eigenvector) is done by finding the maximum element in the vector, and not by finding the magnitude of the vector. This does not affect the outcome of the power method in itself, but it can affect the outcome of variations of the power method, such as the Inverse Power Method, the Shifted Power Method, and the Shifted Inverse Power Method.

Sources: > http://math.fullerton.edu/mathews/n2003/PowerMethodMod.html > http://math.bard.edu/greg/math301/NumericalAnalysis.pdf > http://macs.citadel.edu/chenm/344.dir/08.dir/lect4_2.pdf — Preceding unsigned comment added by Krodh (talk • contribs) 12:39, 21 March 2012 (UTC)

Why does the introduction have the assumption that the matrix is diagonalizable?

The proof given in the analysis section does not use this assumption. — Preceding unsigned comment added by 73.42.179.192 (talk) 02:51, 26 November 2020 (UTC)