Intermediate Eigenvalues

We study briefly methods for finding intermediate eigenvalues, once we have found those of smallest and largest modulus. Although inverse iteration can be used to find any (simple) eigenvalue, we need an approximate value to use it, and this we may well not have.

If we know the dominant eigenvalue, $\lambda _1$ and its corresponding eigenvector, $\mbox{\boldmath$\space u $ } _1$, we can construct for the power method a starting vector $\mbox{\boldmath$\space x $ } _0=\sum _{i=2}^na_i\mbox{\boldmath$\space u $ } _i$ in which there is no component of $\mbox{\boldmath$\space u $ } _1$. This can be done with the help of orthogonality or biorthogonality properties, but we leave this investigation to the exercises. Such methods suffer from the drawback that rounding errors during the course of the calculation introduce a component of $\mbox{\boldmath$\space u $ } _1$, so that convergence reverts to $\mbox{\boldmath$\space u $ } _1$ unless re-orthogonalisation is used. The next two methods use a modified form of the matrix to achieve the same result.

Hotelling's Method for Hermitian A (1933)

Let $\{ \mbox{\boldmath$\space u $ } _1,\mbox{\boldmath$\space u $ } _2,\ldots ,\mbox{\boldmath$\space u $ } _n\}$ be an orthonormal set of eigenvectors of A and suppose we have already found $\lambda _1$ and $\mbox{\boldmath$\space u $ } _1$. We modify A into A₁ as follows:

$$A_1=A-\lambda _1\mbox{\boldmath$ u $ } _1\mbox{\boldmath$ u $ } _1^*,$$

which is also Hermitian since $\lambda _1$ is real. Then

$$A_1\mbox{\boldmath$ u $ } _1=A\mbox{\boldmath$ u $ } _1-\lamb... ...ath$ u $ } _1-\lambda _1\mbox{\boldmath$ u $ } _1=\mbox{\bf0}.$$

Also, for $i=2,3,\ldots ,n$,

$$A_1\mbox{\boldmath$ u $ } _i=A\mbox{\boldmath$ u $ } _i-\lamb... ...\mbox{\boldmath$ u $ } _i=\lambda _i\mbox{\boldmath$ u $ } _i,$$

since $\mbox{\boldmath$\space u $ } _i^*\mbox{\boldmath$\space u $ } _1=0$. Thus A₁ has the same eigenvectors and eigenvalues as A, except that $\lambda _1$ is replaced by 0. The power method for A₁ gives with the usual expansion of $\mbox{\boldmath$\space x $ } _0$

$$\mbox{\boldmath$ x $ } _m=A_1^m\mbox{\boldmath$ x $ } _0=\sum _{i=2}^na_i\lambda _i^m\mbox{\boldmath$ u $ } _i,$$

since $\lambda _1=0$, which looks like $a_2\lambda _2^m\mbox{\boldmath$\space u $ } _2$ for large m.

This method is better than the ordinary power method where $\mbox{\boldmath$\space x $ } _0$has had its $\mbox{\boldmath$\space u $ } _1$ component removed, but is still unstable because of the repeated powering of A₁, which depends on approximations for $\lambda _1$ and $\mbox{\boldmath$\space u $ } _1$. Also, even if A is sparse, A₁ will not be.

A Deflation Method for Unsymmetric Real A.

Let $\mbox{\boldmath$\space u $ } _1$ be an eigenvector with nonzero first component, normalized so that this is 1, and define

$$A_1=A-\mbox{\boldmath$ u $ } _1\mbox{\boldmath$ a $ } ^T=(I-\mbox{\boldmath$ u $ } _1\mbox{\boldmath$ e $ } _1^T)A,$$

where $\mbox{\boldmath$\space a $ } ^T=\mbox{\boldmath$\space e $ } _1^TA$ is the first row of A. Then

$$A_1\mbox{\boldmath$ u $ } _1=(I-\mbox{\boldmath$ u $ } _1\mbo... ...ath$ u $ } _1-\lambda _1\mbox{\boldmath$ u $ } _1=\mbox{\bf0}.$$

Now suppose that $\mbox{\boldmath$\space u $ } _2$ is another eigenvector of A with nonzerofirst component, scaled so that it is 1. Then

 

$$A_1(\mbox{\boldmath$ u $ } _1-\mbox{\boldmath$ u $ } _2) (I-\mbox{\boldmath$ u $ } _1\mbox{\boldmath$ e $ } _1^T)A(\mbox{\boldmath$ u $ } _1-\mbox{\boldmath$ u $ } _2)$$ =

$$\lambda _1\mbox{\boldmath$ u $ } _1-\lambda _2\mbox{\boldmath$ u $ } _2-(\lambda _1-\lambda _2)\mbox{\boldmath$ u $ } _1$$ =

$$\lambda _2(\mbox{\boldmath$ u $ } _1-\mbox{\boldmath$ u $ } _2).$$ = (9.1)

We note that the first row of A₁ is zero, so that the first component of $A_1\mbox{\boldmath$\space u $ } =\lambda \mbox{\boldmath$\space u $ }$ must be zero. Thus, the first column of A₁ plays no role in its eigenproblem, since its elements multiply the zero of $\mbox{\boldmath$\space u $ }$. We can therefore replace the problem of finding the eigenvalues and eigenvectors of A₁ by finding those for the deflated matrix A₁' obtained by removing the first row and column of A₁. If A₁' has an eigenvalue $\lambda _2$ with corresponding eigenvector $\mbox{\boldmath$\space v $ } _2$, then we may write $A_1\mbox{\boldmath$\space u $ } _2=\lambda _2\mbox{\boldmath$\space u $ } _2$as

$$\left[ \begin{array}{c\vert c}0 & \mbox{\bf0}^T\\ \hline \vdo... ...gin{array}{c}0\\ \mbox{\boldmath$ v $ } _2\end{array} \right],$$

where $\left[ \begin{array}{c}0\\ \mbox{\boldmath$\space v $ } _2\end{array} \right]=\mbox{\boldmath$\space w $ } _2$ is the eigenvector of A₁ corresponding to $\lambda _2$. Comparing this with (9.1), we must have $\mbox{\boldmath$\space u $ } _1-\mbox{\boldmath$\space u $ } _2=k\mbox{\boldmath$\space w $ } _2$, where k is a scalar. Multiplying this equation by $\mbox{\boldmath$\space a $ } ^T=\mbox{\boldmath$\space e $ } _1^TA$, we obtain

$$\begin{eqnarray*}\mbox{\boldmath$ e $ } _1^TA\mbox{\boldmath$ u $ } _1-\mbox{\bo... ...a _2 & = & k\mbox{\boldmath$ a $ } ^T\mbox{\boldmath$ w $ } _2, \end{eqnarray*}$$

so $k=\frac{\lambda _1-\lambda _2}{\mbox{\boldmath$\space a $ } ^T\mbox{\boldmath$ w $ } _2}$, giving

$$\mbox{\boldmath$ u $ } _2=\mbox{\boldmath$ u $ } _1-\frac{\la... ... a $ } ^T\mbox{\boldmath$ w $ } _2}\mbox{\boldmath$ w $ } _2.$$ (9.2)

In practice it may happen that the first component of $\mbox{\boldmath$\space u $ } _1$ is zero; we overcome this by pivoting, that is by choosing the largest component of $\mbox{\boldmath$\space u $ } _1$ in place of the first, as the following example illustrates.Example.  The matrix A below has an eigenvalue $\lambda _1=-2$ and corresponding eigenvector $\mbox{\boldmath$\space u $ } _1=[1,2,-5]^T$. Deflate it and hence find a second eigenpair.

$$A=\left[ \begin{array}{rrr}2 & 3 & 2\\ 10 & 3 & 4\\ 3 & 6 & 1\end{array} \right].$$

Scaling $\mbox{\boldmath$\space u $ } _1$ by its largest component, which is its last, it becomes [-1/5,-2/5,1]^T. We now find

$$A_1=A-\left[ \begin{array}{r}-1/5\\ -2/5\\ 1\end{array} \righ... .../5 & 11/5\\ 56/5 & 27/5 & 22/5\\ 0 & 0 & 0\end{array} \right].$$

Thus we take the deflated matrix as $A_1'=\left[ \begin{array}{cc}13/5 & 21/5\\ 56/5 & 27/5\end{array} \right]$, for which there is an eigenpair $\lambda _2=-3,~ \mbox{\boldmath$\space v $ } _2=[-3,4]^T$. Using $\mbox{\boldmath$\space w $ } _2=[-3,4,0]^T$ in (9.2) (remembering that $\mbox{\boldmath$\space a $ } ^T$ is the last row of A), we find $\mbox{\boldmath$\space u $ } _2=[0,-2/3,1]$.We now turn to methods of solving the eigenproblem which involve transforming the matrix.