Editing Inverse iteration (section)

== Theory and convergence ==

The basic idea of the [[power iteration]] is choosing an initial vector <math>b</math> (either an [[eigenvector]] approximation or a [[random]] vector) and iteratively calculating <math>Ab, A^{2}b, A^{3}b,...</math>.  Except for a set of zero [[Measure (mathematics)|measure]], for any initial vector, the result will converge to an [[eigenvector]] corresponding to the dominant [[eigenvalue]].

The inverse iteration does the same for the matrix  <math>(A - \mu I)^{-1}</math>, so it converges to the eigenvector corresponding to the dominant eigenvalue of the matrix <math>(A - \mu I)^{-1}</math>. 
Eigenvalues of this matrix are  <math>(\lambda_1 - \mu)^{-1},...,(\lambda_n - \mu)^{-1}, </math> where  <math> \lambda_i </math> are eigenvalues of <math>A</math>.
The largest of these numbers corresponds to the smallest of <math>(\lambda_1 - \mu),...,(\lambda_n - \mu). </math> The eigenvectors of <math>A</math> and of <math>(A - \mu I)^{-1}</math> are the same, since

<math display="block">
Av=\lambda v \Leftrightarrow
(A-\mu I)v = \lambda v - \mu v \Leftrightarrow
(\lambda - \mu)^{-1} v = (A-\mu I)^{-1} v
</math>

'''Conclusion''': The method converges to the eigenvector of the matrix <math>A</math> corresponding to the closest eigenvalue to  <math>\mu .</math>

In particular, taking <math>\mu=0</math> we see that  <math>(A)^{-1}b_k </math>
converges to the eigenvector corresponding to the eigenvalue of <math>A^{-1}</math> with the largest magnitude <math>\frac{1}{\lambda _N}</math> and thus can be used to determine the smallest magnitude eigenvalue of <math>A</math> since they are inversely related.

=== Speed of  convergence ===

Let us analyze the [[rate of convergence]] of the method.

The [[power method]] is known to [[Rate of convergence#Convergence speed for iterative methods|converge linearly]] to the limit, more precisely:

<math display="block"> \mathrm{Distance}( b^\mathrm{ideal},  b^{k}_\mathrm{Power~Method})=O \left(   \left| \frac{\lambda_\mathrm{subdominant} }{\lambda_\mathrm{dominant} } \right|^k \right), </math>

hence for the inverse iteration method similar result sounds as:

<math display="block"> \mathrm{Distance}( b^\mathrm{ideal},  b^{k}_\mathrm{Inverse~iteration})=O \left(   \left| \frac{\mu -\lambda_{\mathrm{closest~ to~ }\mu}   }{\mu - \lambda_{\mathrm{second~ closest~ to~} \mu} } \right|^k \right). </math>

This is a key formula for understanding the method's convergence. It shows that if <math>\mu</math> is chosen close enough to some  eigenvalue  <math>\lambda </math>, for example <math> \mu- \lambda = \epsilon </math> each iteration will improve the accuracy <math> |\epsilon| /|\lambda +\epsilon - \lambda_{\mathrm{closest~ to~} \lambda} |  </math>  times. (We use that for small enough <math>\epsilon</math> "closest to <math>\mu</math>" and "closest to <math>\lambda </math>" is the same.) For small enough  <math> |\epsilon|</math> it is approximately the same as  <math> |\epsilon| /|\lambda  - \lambda_{\text{closest to } \lambda}|  </math>. Hence if one is able to find <math>\mu </math>, such that the <math> \epsilon </math> will be small enough, then very few iterations may be satisfactory.

=== Complexity ===

The inverse iteration algorithm requires solving a [[System of linear equations|linear system]] or calculation of the inverse matrix.
For non-structured matrices (not sparse, not Toeplitz,...) this requires <math>O(n^{3})</math> operations.