Math 6610 • Analysis of Numerical Methods I

{Eigenvalue Problems}

\partitem{a} Let \(A\) be a real \(n\times n\) matrix with simple eigenvalue
\(\lambda\), right eigenvector \(x\) (i.e., \(Ax=\lambda x\)), and left eigenvector
\(y\) (i.e., \(y^*A=\lambda y^*\)). Assume that \(\|x\|_2=\|y\|_2=1\). Consider the
perturbed matrix \(A+\delta A\), where \(\|\delta A\|_2/\|A\|_2=\epsilon\ll1\).
Show that the matrix \(A+\delta A\) has an eigenvalue \(\mu\) such that
\(|\lambda-\mu|\) is approximately \(\epsilon/|y^*x|\). (Note that this implies
that \(|\lambda-\mu|\leq(2/|y^*x|)\epsilon\) for \(\epsilon\) sufficiently small.)

\partitem{b} Consider a matrix \(A\) with double eigenvalue \(\lambda\) and a
perturbation \(\delta A\) of \(A\) as above. Must there be a constant \(C\) such that
\(A+\delta A\) has an eigenvalue \(\mu\) for which \(|\lambda-\mu|\leq C\epsilon\) for
all sufficiently small \(\epsilon\)? If yes, prove it. If no, construct and
analyze an example that shows such a \(C\) need not exist.

\partitem{c} Consider the problem of computing an eigenvalue/eigenvector pair of
a real symmetric \(m\times m\) matrix \(A\) with eigenvalues that satisfy
\(|\lambda_1|>|\lambda_2|>\cdots>|\lambda_m|\). One algorithm for trying to do
this is Power Iteration with Rayleigh Quotient approximation of the eigenvalue:

Guess \(v^{(0)}\) with \(\|v^{(0)}\|_2=1\).

Set \(\lambda^{(0)}=(v^{(0)})^TAv^{(0)}\).

For \(k=1,2,3,\ldots\)
\[
\begin{aligned}
  &\text{Let } w=Av^{(k-1)},\\
  &v^{(k)}=w/\|w\|_2,\\
  &\lambda^{(k)}=(v^{(k)})^TAv^{(k)}.
\end{aligned}
\]
End

Analyze the convergence of the approximate eigenvector \(v^{(k)}\) and the
approximate eigenvalue \(\lambda^{(k)}\). To what do these quantities converge,
and how fast do they converge?

\newpage