Power iteration

<p>
In <a href="/facts/Mathematics/pxTouaz4">mathematics</a>, power iteration (also known as the power method) is an <a href="/facts/Eigenvalue_algorithm/AYecadB0">eigenvalue algorithm</a>: given a <a href="/facts/Diagonalizable/y3MkyTCy">diagonalizable</a> <a href="/facts/Matrix_(mathematics)/qa8FI4ko">matrix</a> 
  
    
      
        A
      
    
    {\displaystyle A}
  
, the algorithm will produce a number 
  
    
      
        λ
      
    
    {\displaystyle \lambda }
  
, which is the greatest (in absolute value) <a href="/facts/Eigenvalue/8TjEoT8u">eigenvalue</a> of 
  
    
      
        A
      
    
    {\displaystyle A}
  
, and a nonzero vector 
  
    
      
        v
      
    
    {\displaystyle v}
  
, which is a corresponding <a href="/facts/Eigenvector/8TjEoT8u">eigenvector</a> of 
  
    
      
        λ
      
    
    {\displaystyle \lambda }
  
, that is, 
  
    
      
        A
        v
        =
        λ
        v
      
    
    {\displaystyle Av=\lambda v}
  
.
The algorithm is also known as the <a href="/facts/Richard_von_Mises/LFVGPRad">Von Mises</a> iteration.
</p><p>Power iteration is a very simple algorithm, but it may converge slowly. The most time-consuming operation of the algorithm is the multiplication of matrix 
  
    
      
        A
      
    
    {\displaystyle A}
  
 by a vector, so it is effective for a very large <a href="/facts/Sparse_matrix/FFtN0XjR">sparse matrix</a> with appropriate implementation. The speed of convergence is like 
  
    
      
        (
        
          λ
          
            2
          
        
        
          /
        
        
          λ
          
            1
          
        
        
          )
          
            k
          
        
      
    
    {\displaystyle (\lambda _{2}/\lambda _{1})^{k}}
  
(see a later section). In words, convergence is exponential with base being the <a href="/facts/Spectral_gap/jQNDusvk">spectral gap</a>.
</p>

Power iteration open-in-new

Power iteration