Shifted inverse iteration

We can apply the w:power method to find the largest eigenvalue and the w:inverse power method to find the smallest eigenvalue of a given matrix. We can also find the middle eigenvalue by the shifted inverse power method. Before explaining this method, I'd like to introduce some theorems which are very necessary to understand it.

Background Theorems

Suppose that λ and a nonzero vector V are an eigenpair of A. If α is any constant, then λ- α and V are an eigenpair of the matrix ${\displaystyle (A-\alpha I)}$.

Suppose that λ and a nonzero vector V are an eigenpair of A. If  λ is not equal to α, then 1/(λ -α) and V are an eigenpair of the matrix ${\displaystyle (A-\alpha I)^{-1}}$.


Shifted inverse power method

Assume that the n×n matrix A has distinct w:eigenvalues ${\displaystyle \lambda _{1}}$, ${\displaystyle \lambda _{2}}$,....${\displaystyle \lambda _{n}}$ and consider the eigenvalue ${\displaystyle \lambda _{j}}$. Then a constant α can be chosen so that

${\displaystyle \sigma _{1}}$=1 / (${\displaystyle \lambda _{j}}$ - α)

is the dominant eigenvalue of ${\displaystyle (A-\alpha I)^{-1}}$. Furthermore, if ${\displaystyle X_{0}}$, which is the initial guess vector, is chosen appropriately , then the sequences ${\displaystyle \left(X_{k}\right)}$ defined by

${\displaystyle Y_{k}=(A-\alpha I)^{-1}X_{k}}$
${\displaystyle X_{k+1}={\frac {Y_{k}}{\|Y_{k}\|}}}$

and ${\displaystyle \left(c_{k+1}\right)}$ defined by

${\displaystyle c_{k+1}={\frac {Y_{k}^{\top }X_{k}}{X_{k}^{\top }X_{k}}}}$ (w:Rayleigh quotient)

will converge to the dominant eigenpair ${\displaystyle \sigma _{1}}$, ${\displaystyle X_{k+1}}$ will converge to the corresponding eigenvector ${\displaystyle V_{1}}$ of the matrix ${\displaystyle (A-\alpha I)^{-1}}$. Therefore, the corresponding eigenvalue for the matrix A is given by

${\displaystyle \lambda _{j}=1/\sigma _{1}+\alpha }$.

Example

Use the shifted inverse power method to find the eigenpairs of the matrix

${\displaystyle A=\left[{\begin{array}{c c c}0&11&-5\\-2&17&-7\\-4&26&-10\end{array}}\right]}$.

Use the fact that the eigenvalues of A are ${\displaystyle \lambda _{1}}$=4, ${\displaystyle \lambda _{2}}$=2, ${\displaystyle \lambda _{3}}$=1, and select an appropriate α and starting vector for each case.

Case1: For the eigenvalue ${\displaystyle \lambda _{1}}$=4, we select α=4.2 and the starting vector

${\displaystyle X_{0}=\left[{\begin{array}{c}1\\1\\1\\\end{array}}\right]}$.

First we can get

${\displaystyle (A-4.2I)=\left[{\begin{array}{c c c}-4.2&11&-5\\-2&12.8&-7\\-4&26&-14.2\end{array}}\right]}$

and then we can apply the shifted inverse power method

${\displaystyle Y_{k}}$=${\displaystyle (A-\alpha I)^{-1}}$${\displaystyle X_{k}}$.

Therefore,

${\displaystyle \left[{\begin{array}{c c c}-4.2&11&-5\\-2&12.8&-7\\-4&26&-14.2\end{array}}\right]}$ ${\displaystyle Y_{0}}$ = ${\displaystyle X_{0}=\left[{\begin{array}{c}1\\1\\1\\\end{array}}\right]}$.

Solving this system of equations, we get

${\displaystyle Y_{0}=\left[{\begin{array}{c}-9.545454545\\-14.09090909\\-23.18181818\\\end{array}}\right]}$.

Next we can compute

${\displaystyle c_{1}}$=${\displaystyle {\frac {Y_{0}^{\top }X_{0}}{X_{0}^{\top }X_{0}}}.}$ ,

so ${\displaystyle c_{1}}$=-15.606060605. Since

${\displaystyle X_{k+1}={\frac {Y_{k}}{\|Y_{k}\|}}.}$,

it implies

${\displaystyle X_{1}=\left[{\begin{array}{c}-0.4117\\-0.6078\\-1\\\end{array}}\right]}$.

We continue doing the second iteration:

${\displaystyle \left[{\begin{array}{c c c}-4.2&11&-5\\-2&12.8&-7\\-4&26&-14.2\end{array}}\right]}$ ${\displaystyle Y_{1}}$ = ${\displaystyle X_{1}=\left[{\begin{array}{c}-0.4117\\-0.6078\\-1\\\end{array}}\right]}$.

Thus

${\displaystyle Y_{1}=\left[{\begin{array}{c}2.14795\\3.21746\\5.35650\\\end{array}}\right]}$.

It implies ${\displaystyle c_{2}}$=-5.326069 and

${\displaystyle X_{2}=\left[{\begin{array}{c}0.400998\\0.600665\\1\\\end{array}}\right]}$.

We should continue the iteration and finally we got the sequence ${\displaystyle \left(c_{k}\right)}$ will converge to ${\displaystyle \sigma _{1}=-5}$, which is the dominant eigenvalue of ${\displaystyle (A-4.2I)^{-1}}$, and the sequences ${\displaystyle \left(X_{k}\right)}$ converges to

${\displaystyle V_{1}=\left[{\begin{array}{c}0.4\\0.6\\1\\\end{array}}\right]}$

after 9 iterations. We can get the eigenvalue ${\displaystyle \lambda _{1}}$ of A by the formula:

${\displaystyle \lambda _{1}}$ = 1 / ${\displaystyle \sigma _{1}}$ + α= 1/(-5) + 4.2 =4.

We can apply the same approach to find another two eigenvalues of the given matrix A.

Exercise

Use the shifted inverse power method to find the eigenvalue

${\displaystyle \lambda _{2}}$=2

for the same matrix A as the example above, given the starting vector

${\displaystyle X_{0}=\left[{\begin{array}{c}1\\1\\1\\\end{array}}\right]}$,

α=2.1.

Exercise

Use w:Matlab to do the shifted inverse power method to find the eigenvalue ${\displaystyle \lambda _{2}}$=5.1433 for the given matrix

${\displaystyle A=\left[{\begin{array}{c c c}6&2&-1\\2&5&1\\-1&1&4\end{array}}\right]}$.

The starting vector is

${\displaystyle X_{0}=\left[{\begin{array}{c}1\\1\\3\\\end{array}}\right]}$,

α=6.