Assume that the n×n matrix A has distinct w:eigenvalues
λ 1 {\displaystyle \lambda _{1}} , λ 2 {\displaystyle \lambda _{2}} ,....λ n {\displaystyle \lambda _{n}}
and consider the eigenvalue
λ j {\displaystyle \lambda _{j}} .
Then a constant α can be chosen so that
σ 1 {\displaystyle \sigma _{1}} =1 / (λ j {\displaystyle \lambda _{j}} - α)is the dominant eigenvalue of
( A − α I ) − 1 {\displaystyle (A-\alpha I)^{-1}} .
Furthermore, if
X 0 {\displaystyle X_{0}} , which is the initial guess vector, is chosen appropriately , then the sequences
( X k ) {\displaystyle \left(X_{k}\right)} defined by
Y k = ( A − α I ) − 1 X k {\displaystyle Y_{k}=(A-\alpha I)^{-1}X_{k}}
X k + 1 = Y k ‖ Y k ‖ {\displaystyle X_{k+1}={\frac {Y_{k}}{\|Y_{k}\|}}} and ( c k + 1 ) {\displaystyle \left(c_{k+1}\right)}
defined by
c k + 1 = Y k ⊤ X k X k ⊤ X k {\displaystyle c_{k+1}={\frac {Y_{k}^{\top }X_{k}}{X_{k}^{\top }X_{k}}}} (w:Rayleigh quotient )will converge to the dominant eigenpair
σ 1 {\displaystyle \sigma _{1}} ,
X k + 1 {\displaystyle X_{k+1}} will converge to the corresponding eigenvector V 1 {\displaystyle V_{1}}
of the matrix
( A − α I ) − 1 {\displaystyle (A-\alpha I)^{-1}} .
Therefore, the corresponding eigenvalue for the matrix A is given by
λ j = 1 / σ 1 + α {\displaystyle \lambda _{j}=1/\sigma _{1}+\alpha } .
Use the shifted inverse power method to find the eigenpairs of the matrix
A = [ 0 11 − 5 − 2 17 − 7 − 4 26 − 10 ] {\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
λ 1 {\displaystyle \lambda _{1}} =4,
λ 2 {\displaystyle \lambda _{2}} =2,
λ 3 {\displaystyle \lambda _{3}} =1,
and select an appropriate α and starting vector for each case.
Case1: For the eigenvalue
λ 1 {\displaystyle \lambda _{1}} =4,
we select α=4.2 and the starting vector
X 0 = [ 1 1 1 ] {\displaystyle X_{0}=\left[{\begin{array}{c}1\\1\\1\\\end{array}}\right]} .
First we can get
( A − 4.2 I ) = [ − 4.2 11 − 5 − 2 12.8 − 7 − 4 26 − 14.2 ] {\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
Y k {\displaystyle Y_{k}} =( A − α I ) − 1 {\displaystyle (A-\alpha I)^{-1}} X k {\displaystyle X_{k}} .
Therefore,
[ − 4.2 11 − 5 − 2 12.8 − 7 − 4 26 − 14.2 ] {\displaystyle \left[{\begin{array}{c c c}-4.2&11&-5\\-2&12.8&-7\\-4&26&-14.2\end{array}}\right]} Y 0 {\displaystyle Y_{0}} = X 0 = [ 1 1 1 ] {\displaystyle X_{0}=\left[{\begin{array}{c}1\\1\\1\\\end{array}}\right]} .
Solving this system of equations, we get
Y 0 = [ − 9.545454545 − 14.09090909 − 23.18181818 ] {\displaystyle Y_{0}=\left[{\begin{array}{c}-9.545454545\\-14.09090909\\-23.18181818\\\end{array}}\right]} .
Next we can compute
c 1 {\displaystyle c_{1}} =Y 0 ⊤ X 0 X 0 ⊤ X 0 . {\displaystyle {\frac {Y_{0}^{\top }X_{0}}{X_{0}^{\top }X_{0}}}.} ,
so
c 1 {\displaystyle c_{1}} =-15.606060605.
Since
X k + 1 = Y k ‖ Y k ‖ . {\displaystyle X_{k+1}={\frac {Y_{k}}{\|Y_{k}\|}}.} ,
it implies
X 1 = [ − 0.4117 − 0.6078 − 1 ] {\displaystyle X_{1}=\left[{\begin{array}{c}-0.4117\\-0.6078\\-1\\\end{array}}\right]} .
We continue doing the second iteration:
[ − 4.2 11 − 5 − 2 12.8 − 7 − 4 26 − 14.2 ] {\displaystyle \left[{\begin{array}{c c c}-4.2&11&-5\\-2&12.8&-7\\-4&26&-14.2\end{array}}\right]} Y 1 {\displaystyle Y_{1}} = X 1 = [ − 0.4117 − 0.6078 − 1 ] {\displaystyle X_{1}=\left[{\begin{array}{c}-0.4117\\-0.6078\\-1\\\end{array}}\right]} .
Thus
Y 1 = [ 2.14795 3.21746 5.35650 ] {\displaystyle Y_{1}=\left[{\begin{array}{c}2.14795\\3.21746\\5.35650\\\end{array}}\right]} .
It implies
c 2 {\displaystyle c_{2}} =-5.326069
and
X 2 = [ 0.400998 0.600665 1 ] {\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
( c k ) {\displaystyle \left(c_{k}\right)}
will converge to
σ 1 = − 5 {\displaystyle \sigma _{1}=-5} ,
which is the dominant eigenvalue of
( A − 4.2 I ) − 1 {\displaystyle (A-4.2I)^{-1}} ,
and the sequences
( X k ) {\displaystyle \left(X_{k}\right)}
converges to
V 1 = [ 0.4 0.6 1 ] {\displaystyle V_{1}=\left[{\begin{array}{c}0.4\\0.6\\1\\\end{array}}\right]}
after 9 iterations. We can get the eigenvalue
λ 1 {\displaystyle \lambda _{1}}
of A by the formula:
λ 1 {\displaystyle \lambda _{1}} = 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
edit
Use the shifted inverse power method to find the eigenvalue
λ 2 {\displaystyle \lambda _{2}} =2
for the same matrix A as the example above, given the starting vector
X 0 = [ 1 1 1 ] {\displaystyle X_{0}=\left[{\begin{array}{c}1\\1\\1\\\end{array}}\right]} ,
α=2.1.
For the eigenvalue
λ 1 {\displaystyle \lambda _{1}} =2,
we select α=2.1 and the starting vector
X 0 = [ 1 1 1 ] {\displaystyle X_{0}=\left[{\begin{array}{c}1\\1\\1\\\end{array}}\right]} .
First we can get
( A − 2.1 I ) = [ − 2.1 11 − 5 − 2 14.9 − 7 − 4 26 − 12.1 ] {\displaystyle (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,
[ − 2.1 11 − 5 − 2 14.9 − 7 − 4 26 − 12.1 ] {\displaystyle \left[{\begin{array}{c c c}-2.1&11&-5\\-2&14.9&-7\\-4&26&-12.1\end{array}}\right]} Y 0 {\displaystyle Y_{0}} = X 0 = [ 1 1 1 ] {\displaystyle X_{0}=\left[{\begin{array}{c}1\\1\\1\\\end{array}}\right]} .
So
Y 0 = [ 11.05263158 21.57894737 42.63157895 ] {\displaystyle Y_{0}=\left[{\begin{array}{c}11.05263158\\21.57894737\\42.63157895\\\end{array}}\right]}
and
c 1 = 25.0877193 {\displaystyle c_{1}=25.0877193}
It implies
X 1 = [ 0.2592592593 0.5061728395 1 ] {\displaystyle X_{1}=\left[{\begin{array}{c}0.2592592593\\0.5061728395\\1\\\end{array}}\right]} .
After 7 iterations,we got
σ 1 = − 10 {\displaystyle \sigma _{1}=-10}
and
V 1 = [ 0.25 0.5 1 ] {\displaystyle V_{1}=\left[{\begin{array}{c}0.25\\0.5\\1\\\end{array}}\right]} .
Doing some computation, We got
λ 1 {\displaystyle \lambda _{1}} = 1 / σ 1 {\displaystyle \sigma _{1}} + α= 1/(-10) + 2.1 =2.
Exercise
edit
Use w:Matlab to do the shifted inverse power method to find the eigenvalue
λ 2 {\displaystyle \lambda _{2}} =5.1433
for the given matrix
A = [ 6 2 − 1 2 5 1 − 1 1 4 ] {\displaystyle 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 = [ 1 1 3 ] {\displaystyle X_{0}=\left[{\begin{array}{c}1\\1\\3\\\end{array}}\right]} ,
α=6.
First we can get
( A − 6 I ) = [ 0 2 − 1 2 − 1 1 − 1 1 − 2 ] {\displaystyle (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
( c k ) {\displaystyle \left(c_{k}\right)}
will converge to
σ 2 = − 1.167238857441354 {\displaystyle \sigma _{2}=-1.167238857441354}
after 7 iterations.
Doing some computation, We got
λ 2 {\displaystyle \lambda _{2}} = 1 / σ 2 {\displaystyle \sigma _{2}} + α= 1/(-1.167238857441354) + 6 = 5.143277321839636
which is approximately equal to 5.1433, the middle eigenvalue of the matrix.