Inverse iteration

In <a href="/facts/Numerical_analysis/QT9cYa9z">numerical analysis</a>, inverse iteration (also known as the inverse power method) is an <a href="/facts/Iterative_method/uKMAJhEh">iterative</a> <a href="/facts/Eigenvalue_algorithm/AYecadB0">eigenvalue algorithm</a>. It allows one to find an approximate
<a href="/facts/Eigenvector/8TjEoT8u">eigenvector</a> when an approximation to a corresponding <a href="/facts/Eigenvalue/8TjEoT8u">eigenvalue</a> is already known.
The method is conceptually similar to the <a href="/facts/Power_method/gLwIJmjV">power method</a>.
It appears to have originally been developed to compute resonance frequencies in the field of structural mechanics.
The inverse power iteration algorithm starts with an approximation 
 
 
 
 μ
 
 
 {\displaystyle \mu }
 
 for the <a href="/facts/Eigenvalue/8TjEoT8u">eigenvalue</a> corresponding to the desired <a href="/facts/Eigenvector/8TjEoT8u">eigenvector</a> and a vector 
 
 
 
 
 b
 
 0
 
 
 
 
 {\displaystyle b_{0}}
 
, either a randomly selected vector or an approximation to the eigenvector. The method is described by the iteration

 
 
 
 
 b
 
 k
 +
 1
 
 
 =
 
 
 
 (
 A
 −
 μ
 I
 
 )
 
 −
 1
 
 
 
 b
 
 k
 
 
 
 
 C
 
 k
 
 
 
 
 ,
 
 
 {\displaystyle b_{k+1}={\frac {(A-\mu I)^{-1}b_{k}}{C_{k}}},}

where 
 
 
 
 
 C
 
 k
 
 
 
 
 {\displaystyle C_{k}}
 
 are some constants usually chosen as 
 
 
 
 
 C
 
 k
 
 
 =
 ‖
 (
 A
 −
 μ
 I
 
 )
 
 −
 1
 
 
 
 b
 
 k
 
 
 ‖
 .
 
 
 {\displaystyle C_{k}=\|(A-\mu I)^{-1}b_{k}\|.}
 
 Since eigenvectors are defined up to multiplication by constant, the choice of 
 
 
 
 
 C
 
 k
 
 
 
 
 {\displaystyle C_{k}}
 
 can be arbitrary in theory; practical aspects of the choice of 
 
 
 
 
 C
 
 k
 
 
 
 
 {\displaystyle C_{k}}
 
 are discussed below.
At every iteration, the vector 
 
 
 
 
 b
 
 k
 
 
 
 
 {\displaystyle b_{k}}
 
 is multiplied by the matrix 
 
 
 
 (
 A
 −
 μ
 I
 
 )
 
 −
 1
 
 
 
 
 {\displaystyle (A-\mu I)^{-1}}
 
 and normalized.
It is exactly the same formula as in the <a href="/facts/Power_method/gLwIJmjV">power method</a>, except replacing the matrix 
 
 
 
 A
 
 
 {\displaystyle A}
 
 by 
 
 
 
 (
 A
 −
 μ
 I
 
 )
 
 −
 1
 
 
 .
 
 
 {\displaystyle (A-\mu I)^{-1}.}

The closer the approximation 
 
 
 
 μ
 
 
 {\displaystyle \mu }
 
 to the eigenvalue is chosen, the faster the algorithm converges; however, incorrect choice of 
 
 
 
 μ
 
 
 {\displaystyle \mu }
 
 can lead to slow convergence or to the convergence to an eigenvector other than the one desired. In practice, the method is used when a good approximation for the eigenvalue is known, and hence one needs only few (quite often just one) iterations.

Inverse iteration open-in-new

Inverse iteration