Math 6610 • Analysis of Numerical Methods I

{Eigenvalue Problems}
Let \(\lambda\) be a simple eigenvalue of \(A\) (not necessarily symmetric), with right
eigenvector \(x\) (i.e., \(Ax=\lambda x\)), and left eigenvector \(y\) (i.e.,
\(y^*A=\lambda y^*\)). Assume that \(\lVert x\rVert_2=\lVert y\rVert_2=1\). Let
\(\lambda+\delta\lambda\) be the corresponding eigenvalue of \(A+\delta A\).

\textbf{a)} Show that
\[
  \delta\lambda=\frac{y^*\delta A x}{y^*x}+O(\lVert\delta A\rVert^2),
\]
and derive an upper bound for \(\lvert\delta\lambda\rvert\). What is the condition
number for \(\lambda\) with respect to changes in \(A\)?

\textbf{b)} Consider the matrix
\[
  \begin{bmatrix}
    0 & 1 & 0 & \cdots & 0\\
    0 & 0 & 1 & \ddots & 0\\
    \vdots & \ddots & \ddots & \ddots & 1\\
    \epsilon & 0 & \cdots & 0 & 0
  \end{bmatrix}.
\]
Compute \(d\lambda/d\epsilon\) and show that the condition number becomes infinite as
\(\epsilon\) approaches zero.

\textbf{c)} Describe the power method for finding the eigenvalue of the largest
absolute magnitude, and inverse iteration for the eigenvalue closest to a given
value. How fast do you expect these algorithms to converge?