Math 6610 • Analysis of Numerical Methods I

{Eigenvalue Problems}

\textbf{a)} Consider the problem of computing an eigenvalue/eigenvector pair of a
real symmetric \(m\times m\) matrix \(A\) with eigenvalues of distinct magnitudes. Two
algorithms for trying to do this are Power Iteration and Rayleigh Quotient
Iteration:

\begin{center}
\begin{tabular}{p{0.44\linewidth}p{0.44\linewidth}}
\textbf{Power Iteration} & \textbf{Rayleigh Quotient Iteration}\\
Guess \(v^{(0)}\) with \(\lVert v^{(0)}\rVert_2=1\).
&
Guess \(v^{(0)}\) with \(\lVert v^{(0)}\rVert_2=1\).\\
&
Set \(\lambda^{(0)}=(v^{(0)})^TAv^{(0)}\).\\
For \(k=1,2,3,\ldots\) & For \(k=1,2,3,\ldots\)\\
\(\quad w=Av^{(k-1)}\)
&
\(\quad\) Solve \((A-\lambda^{(k-1)}I)w=v^{(k-1)}\) for \(w\)\\
\(\quad v^{(k)}=w/\lVert w\rVert_2\)
&
\(\quad v^{(k)}=w/\lVert w\rVert_2\)\\
\(\quad \lambda^{(k)}=(v^{(k)})^TAv^{(k)}\)
&
\(\quad \lambda^{(k)}=(v^{(k)})^TAv^{(k)}\)\\
End & End
\end{tabular}
\end{center}

\textbf{i)} Analyze the convergence properties of the Power Iteration algorithm for
a generic guess \(v^0\).

\textbf{ii)} Suppose that the Rayleigh Quotient Iteration iterates \(\lambda^{(k)}\)
converge to a simple eigenvalue \(\lambda\) of \(A\). Analyze the speed of convergence
of \(\lambda^{(k)}\) to \(\lambda\).

\textbf{b)} Many algorithms for finding eigenvalues of a complex \(m\times m\) matrix
\(A\) are based on the existence of a Schur decomposition of \(A\), namely,
\(A=QTQ^*\) where \(Q\) is unitary and \(T\) is upper triangular. Prove that every matrix
\(A\) has a Schur decomposition and explain how knowing the Schur decomposition of
\(A\) would help one determine the eigenvalues of \(A\).