Math 6610 • Analysis of Numerical Methods I

{Eigenvalue Problems}

\textbf{a)} (8\%) QR iteration can be viewed as an extension of the power method. We
assume \(n\times n\) real symmetric, nonsingular matrix \(A\), with distinct eigenvalues.
Here is the algorithm of orthogonal iteration for two linearly independent vectors
\(z_1\) and \(z_2\), listed in an \(n\times 2\) matrix \(Z_0=[z_1,z_2]\):

\(i=0\)

\textit{repeat}
\[
\begin{aligned}
  Y_{i+1} &= AZ_i,\\
  \text{QR Factor }Y_{i+1} &= Z_{i+1}R_{i+1},\\
  i &= i+1
\end{aligned}
\]
\textit{until convergence}

Notice that \(Y_i,Z_i\) are \(n\times 2\) matrices, and \(R_i\) is a \(2\times 2\) upper
triangular matrix. Our assumptions allow us to write \(A=S\Lambda S^{-1}\), where
\(\Lambda\) is a diagonal matrix containing all eigenvalues
\(\lvert\lambda_1\rvert>\lvert\lambda_2\rvert>\cdots>\lvert\lambda_n\rvert\),
\(S=[s_1,s_2,\ldots,s_n]\) contains all the eigenvectors.

Show that
\[
  \operatorname{span}\{Z_{i+1}\}
  =
  \operatorname{span}\{Y_{i+1}\}
  =
  \operatorname{span}\{AZ_i\},
\]
so
\[
  \operatorname{span}\{Z_i\}
  =
  \operatorname{span}\{A^iZ_0\}
  =
  \operatorname{span}\{S\Lambda^iS^{-1}Z_0\}.
\]
Analyze it by writing
\[
  S\Lambda^iS^{-1}Z_0=\lambda_2^i S D_i(S^{-1}Z_0).
\]
Derive the diagonal \(D_i\) and the \(n\times 2\) matrix \(Z'_0=S^{-1}Z_0\), find the
limiting span of \(Z_i\) as \(i\to\infty\). How do we obtain the approximating
eigenvalues \(\lambda_1,\lambda_2\) and approximating eigenvectors \(s_1\) and \(s_2\),
once iterations are terminated?

\textbf{b)} (6\%) Assume that we can continue this extension to \(n\) linearly
independent vectors, contained in an \(n\times n\) nonsingular \(Z_0\); in particular
when \(Z_0=I\), we will have the method of QR iteration. Describe the QR algorithm
(without shift) and argue for the rate of convergence based on the analysis in part
\textbf{a)}.

\textbf{c)} (6\%) To speed up convergence, we should use shifting. Describe the QR
iteration with a shift, and make a suggestion as what shift should be used. How fast
is the convergence?