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 $(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 $(A-\alpha I)^{-1}$.

Shifted inverse power method

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

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

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

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

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

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

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

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

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

Example

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

$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 $\lambda _{1}$=4, $\lambda _{2}$=2, $\lambda _{3}$=1, and select an appropriate α and starting vector for each case.

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

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

First we can get

$(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

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

Therefore,

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

Solving this system of equations, we get

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

Next we can compute

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

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

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

it implies

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

We continue doing the second iteration:

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

Thus

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

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

$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 $\left(c_{k}\right)$ will converge to $\sigma _{1}=-5$, which is the dominant eigenvalue of $(A-4.2I)^{-1}$, and the sequences $\left(X_{k}\right)$ converges to

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

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

$\lambda _{1}$ = 1 / $\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

$\lambda _{2}$=2

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

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

α=2.1.

Solution:

For the eigenvalue

$\lambda _{1}$=2,

we select α=2.1 and the starting vector

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

First we can get

$(A-2.1I)=\left[{\begin{array}{c c c}-2.1&11&-5\\-2&14.9&-7\\-4&26&-12.1\end{array}}\right]$.

Therefore,

$\left[{\begin{array}{c c c}-2.1&11&-5\\-2&14.9&-7\\-4&26&-12.1\end{array}}\right]$ $Y_{0}$ = $X_{0}=\left[{\begin{array}{c}1\\1\\1\\\end{array}}\right]$.

So

$Y_{0}=\left[{\begin{array}{c}11.05263158\\21.57894737\\42.63157895\\\end{array}}\right]$

and

$c_{1}=25.0877193$

It implies

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

After 7 iterations,we got

$\sigma _{1}=-10$

and

$V_{1}=\left[{\begin{array}{c}0.25\\0.5\\1\\\end{array}}\right]$.

Doing some computation, We got

$\lambda _{1}$ = 1 / $\sigma _{1}$ + α= 1/(-10) + 2.1 =2.

 

Exercise

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

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

The starting vector is

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

α=6.

Solution:

First we can get

$(A-6I)=\left[{\begin{array}{c c c}0&2&-1\\2&-1&1\\-1&1&-2\end{array}}\right]$.

Then we can apply the method mentioned above to find the middle eigenvalue of the matrix. Below is the Matlab code for this question.

for i=1:7
    y=linsolve(A,x);
    e=(y'*x)/(x'*x);
    x=y/norm(y);
end

We can find that the sequence Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:6011/en.wikiversity.org/v1/":): {\displaystyle \left( c_{k} \right)} will converge to $\sigma _{2}=-1.167238857441354$ after 7 iterations. Doing some computation, We got

$\lambda _{2}$ = 1 / $\sigma _{2}$ + α= 1/(-1.167238857441354) + 6 = 5.143277321839636

which is approximately equal to 5.1433, the middle eigenvalue of the matrix.

 

 

Reference

• Yu-Kai Hong,An introduction to the Power Method and (shifted/Inverse) Power Method,2007
• John H.Mathews,Kurtis D.Fink,Numerical method using Matlab,4th edition,2004