Mathematics Qualifying Exam Question Bank

Department of Mathematics

Question

Math 6610 • Analysis of Numerical Methods I

Fall 2001 • Question 4

Question

Math 6610 • Analysis of Numerical Methods I Fall 2001 • Question 4

Eigenvalue Problems

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 \(\lVert x\rVert _2=\lVert y\rVert _2=1\). Show that the condition number for \(\lambda \) to changes in \(A\) is given by \(s(\lambda )=1/\lvert y^*x\rvert \). Give an example of a matrix \(A\) which has a badly conditioned eigenvalue, and another matrix \(A\) which has only well-conditioned eigenvalues.

b) Consider the problem of computing an eigenvalue/eigenvector pair of a real symmetric \(m\times m\) matrix \(A\) with eigenvalues of distinct magnitudes. One algorithm for trying to do this is Rayleigh Quotient Iteration:

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

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

For \(k=1,2,3,\ldots \) \[ \begin {aligned} &\text {Solve }(A-\lambda ^{(k-1)}I)w=v^{(k-1)}\text { for }w,\\ &v^{(k)}=w/\lVert w\rVert _2,\\ &\lambda ^{(k)}=(v^{(k)})^TAv^{(k)}. \end {aligned} \] End

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 \).

{Eigenvalue Problems}

\textbf{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 \(\lVert x\rVert_2=\lVert y\rVert_2=1\). Show that
the condition number for \(\lambda\) to changes in \(A\) is given by
\(s(\lambda)=1/\lvert y^*x\rvert\). Give an example of a matrix \(A\) which has a badly
conditioned eigenvalue, and another matrix \(A\) which has only well-conditioned
eigenvalues.

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

Guess \(v^{(0)}\) with \(\lVert v^{(0)}\rVert_2=1\).

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

For \(k=1,2,3,\ldots\)
\[
\begin{aligned}
  &\text{Solve }(A-\lambda^{(k-1)}I)w=v^{(k-1)}\text{ for }w,\\
  &v^{(k)}=w/\lVert w\rVert_2,\\
  &\lambda^{(k)}=(v^{(k)})^TAv^{(k)}.
\end{aligned}
\]
End

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\).

Topic Tags

Conditioning, Sensitivity, and Perturbation Bounds Consistency, Stability, and Convergence Eigenvalues, Spectral Radius, and Gershgorin Theorem Rayleigh Quotient Iteration