In numerical analysis, inverse iteration (also known as the inverse power method) is an iterative eigenvalue algorithm. It allows one to find an approximateeigenvector when an approximation to a corresponding eigenvalue is already known.The method is conceptually similar to the power method.It appears to have originally been developed to compute resonance frequencies in the field of structural mechanics.[1]
The inverse power iteration algorithm starts with an approximation
\mu
b0
where
Ck
Ck=\|(A-\muI)-1bk\|.
Ck
Ck
At every iteration, the vector
bk
(A-\muI)-1
A
(A-\muI)-1.
\mu
\mu
The basic idea of the power iteration is choosing an initial vector
b
Ab,A2b,A3b,...
The inverse iteration does the same for the matrix
(A-\muI)-1
(A-\muI)-1
(λ1-\mu)-1,...,(λn-\mu)-1,
λi
A
(λ1-\mu),...,(λn-\mu).
A
(A-\muI)-1
Conclusion: The method converges to the eigenvector of the matrix
A
\mu.
In particular, taking
\mu=0
(A)-1bk
A-1
1 | |
λN |
A
Let us analyze the rate of convergence of the method.
The power method is known to converge linearly to the limit, more precisely:
hence for the inverse iteration method similar result sounds as:
This is a key formula for understanding the method's convergence. It shows that if
\mu
λ
\mu-λ=\epsilon
|\epsilon|/|λ+\epsilon-λclosest~to~|
\epsilon
\mu
λ
|\epsilon|
|\epsilon|/|λ-λclosestto|
\mu
\epsilon
The inverse iteration algorithm requires solving a linear system or calculation of the inverse matrix.For non-structured matrices (not sparse, not Toeplitz,...) this requires
O(n3)
The method is defined by the formula:
There are, however, multiple options for its implementation.
We can rewrite the formula in the following way:
emphasizing that to find the next approximation
bk+1
(A-\muI)-1
The choice depends also on the number of iterations. Naively, if at each iteration one solves a linear system, the complexity will be k O(n3), where k is number of iterations; similarly, calculating the inverse matrix and applying it at each iteration is of complexity k O(n3).Note, however, that if the eigenvalue estimate
\mu
(A-\muI)
Inverting the matrix will typically have a greater initial cost, but lower cost at each iteration. Conversely, solving systems of linear equations will typically have a lesser initial cost, but require more operations for each iteration.
If it is necessary to perform many iterations (or few iterations, but for many eigenvectors), then it might be wise to bring the matrix to the upper Hessenberg form first (for symmetric matrix this will be tridiagonal form). Which costs arithmetic operations using a technique based on Householder reduction), with a finite sequence of orthogonal similarity transforms, somewhat like a two-sided QR decomposition.[2] [3] (For QR decomposition, the Householder rotations are multiplied only on the left, but for the Hessenberg case they are multiplied on both left and right.) For symmetric matrices this procedure costs arithmetic operations using a technique based on Householder reduction.[2] [3]
Solution of the system of linear equations for the tridiagonal matrix costs
O(n)
O(n3)+kO(n)
k
Also transformation to the Hessenberg form involves square roots and the division operation, which are not universally supported by hardware.
On general purpose processors (e.g. produced by Intel) the execution time of addition, multiplication and division is approximately equal. But on embedded and/or low energy consuming hardware (digital signal processors, FPGA, ASIC) division may not be supported by hardware, and so should be avoided. Choosing
Ck=
nk | |
2 |
k
When implementing the algorithm using fixed-point arithmetic, the choice of the constant
Ck
bk
Ck
bk
The main application of the method is the situation when an approximation to an eigenvalue is found and one needs to find the corresponding approximate eigenvector. In such a situation the inverse iteration is the main and probably the only method to use.
Typically, the method is used in combination with some other method which finds approximate eigenvalues: the standard example is the bisection eigenvalue algorithm, another example is the Rayleigh quotient iteration, which is actually the same inverse iteration with the choice of the approximate eigenvalue as the Rayleigh quotient corresponding to the vector obtained on the previous step of the iteration.
There are some situations where the method can be used by itself, however they are quite marginal.
The dominant eigenvalue can be easily estimated for any matrix. For any induced norm it is true that
\left\|A\right\|\ge|λ|,
λ
In some real-time applications one needs to find eigenvectors for matrices with a speed of millions of matrices per second. In such applications, typically the statistics of matrices is known in advance and one can take as an approximate eigenvalue the average eigenvalue for some large matrix sample.Better, one may calculate the mean ratio of the eigenvalues to the trace or the norm of the matrix and estimate the average eigenvalue as the trace or norm multiplied by the average value of that ratio. Clearly such a method can be used only with discretion and only when high precision is not critical. This approach of estimating an average eigenvalue can be combined with other methods to avoid excessively large error.