Mathematics Qualifying Exam Question Bank

Department of Mathematics

Question

Math 6610 • Analysis of Numerical Methods I

Fall 2005 • Question 8

Question

Math 6610 • Analysis of Numerical Methods I Fall 2005 • Question 8

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 \): \[ \text {Solve }(A-\lambda ^{(k-1)}I)w=v^{(k-1)}\text { for }w, \] \[ v^{(k)}=\frac {w}{\lVert w\rVert _2}, \] \[ \lambda ^{(k)}=(v^{(k)})^TAv^{(k)}. \] Until convergence.

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\):
\[
  \text{Solve }(A-\lambda^{(k-1)}I)w=v^{(k-1)}\text{ for }w,
\]
\[
  v^{(k)}=\frac{w}{\lVert w\rVert_2},
\]
\[
  \lambda^{(k)}=(v^{(k)})^TAv^{(k)}.
\]
Until convergence.

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