\magnification=\magstep1
\nopagenumbers
\centerline{Mathematics 172 -- Numerical Analysis 2}
\centerline{Discussion 4 -- A First Numerical Eigenvalue Technique}
\centerline{April 15, 1999}
\bigskip
\noindent
{\bf Situation}
\bigskip
\noindent
Suppose we have a (real) $n \times n$ matrix $A$, and
\bigskip
\item{$\bullet$} Assume that $A$ is
{\it diagonalizable\/}.  
Recall: (by definition) this means that there is a basis of ${\bf R}^n$ -- 
$\beta = \{ x_1, \ldots, x_n \}$ which consists of eigenvectors of $A$:
$$Ax_i = \lambda_i x_i$$
for each $i = 1, \ldots, n$, and some scalars $\lambda_i$ (the eigenvalues).
\item{$\bullet$}  Moreover, assume that there is a {\it unique\/} 
{\it largest eigenvalue in absolute value\/}, say $\lambda_1$: 
$|\lambda_1| > |\lambda_j|$ for all $j = 2, \ldots, n$.
We will call $\lambda_1$ the {\it dominant eigenvalue\/}.
\bigskip
\noindent
If we take an arbitrary non-zero vector $x$ and 
expand it in terms of the basis $\beta$ consisting of eigenvectors
of $A$:
$$x = c_1 x_1 + c_2 x_2 + \ldots + c_n x_n\ ,\leqno(1)$$
then the expansion of $A^k x$ be for a general $k \ge 1$
will be 
$$\eqalign{
A^k x &= c_1 A^k x_1 + c_2 A^k x_2 + \cdots + c_n A^k x_n\cr 
      &= c_1 \lambda_1^k x_1 + c_2 \lambda_2^k x_2 + \cdots +
         c_n \lambda_n^k x_n\cr}$$
It is not difficult to show that if we define 
$$\|x\|_\beta = \max_{1\le i \le n} |c_i|$$
using the coefficients from the expansion (1), then we get a vector
norm on ${\bf R}^n$ (similar to the $\infty$ norm, but using 
the $\beta$-coordinates of vectors rather than the standard coordinates).
We can assume from the start that $\|x_i\|_\beta = 1$ also, if we 
like.
\bigskip
\noindent
{\bf Questions}
\bigskip
\item{$\bullet$} Assuming $c_1 \ne 0$, what is the vector of 
$\beta$-norm = 1 in the direction of $A^k x$ for large $k$?  What happens 
to that vector as 
$k \to \infty$?  Does this give you an idea for a numerical technique to 
determine $\lambda_1$?  (Note:  To determine $\lambda_1$, it may help
also to think about determining $x_1$, since $Ax_1 = \lambda_1 x_1$.)
\bigskip
\item{$\bullet$}  This ``power method'' yields only the dominant
eigenvalue of $A$.  But we might also possibly apply a similar idea with
matrices {\it derived from\/} $A$ to get other eigenvalues.  For 
instance, how are the eigenvalues of $A^{-1}$ related to the eigenvalues
of $A$ (assuming of course that $A^{-1}$ exists!)?  If we apply the 
method above using the matrix $A^{-1}$, what do we get as $k \to \infty$?
\bigskip
\item{$\bullet$}  If we apply the 
method above using the matrix $(A-sI)^{-1}$, what do we get as 
$k \to \infty$?  Explain.
\bye
