Math 6610 • Analysis of Numerical Methods I

{Eigenvalue Problems}

\textbf{(a)} For the general eigenvalue problem of a nonsingular matrix \(A\), the
simplest method is the power method, which converges to the largest eigenvalue in
magnitude, assuming it is simple. The algorithm is the following:

\(i=0\)

\textit{repeat}
\[
\begin{aligned}
  y_{i+1} &= Ax_i,\\
  x_{i+1} &= y_{i+1}/\lVert y_{i+1}\rVert_2,\\
  \tilde{\lambda}_{i+1} &= x_{i+1}^T A x_{i+1},\\
  i &= i+1
\end{aligned}
\]
\textit{until convergence}

The inverse iteration algorithm takes advantage of the fact the if \(\sigma\) (the
shift) is closest to one of the simple eigenvalues \(\lambda\), then
\(1/(\lambda-\sigma)\) will be the largest eigenvalue in magnitude of the matrix
\((A-\sigma I)^{-1}\). Use this fact to construct the inverse iteration algorithm.
Note that we will not need to construct the explicit inverse of \(A-\sigma I\). How
fast does it converge to the desired eigenvalue? When do you expect the convergence
to be slow? How do we find the corresponding eigenvector?

\textbf{(b)} Now consider the symmetric eigenvalue problem where \(A\) is symmetric.
What is the Rayleigh quotient? The Rayleigh quotient method is the inverse
iteration algorithm described above applied to a symmetric matrix, when the shift is
chosen to be the Rayleigh quotient \(\rho_i\) of \(A\) and the updated vector \(x_i\).
Explain the rationale of choosing \(\rho_i\) to be the shift and determine the speed
of convergence of \(\rho_i\) to \(\lambda\).