Topic
Rayleigh Quotient Iteration
Courses
Courses whose questions include this topic tag.
Questions
This topic is tagged for 14 questions
-
Fall 2025 • Question 4
Solution of a nonlinear fixed point problem
Consider the fixed-point problem \(x = g(x)\) for a continuously differentiable real-valued function \(g\) and assume that it has a solution \(\alpha \) for which \(|g'(\alpha )| < 1\). State and prove a convergence theorem for fixed point iteration \(x^{(k+1)} = g(x^{(k)})\) for this problem. Note: Do not assume more about the function \(g\) than is stated in the problem.
-
Fall 2024 • Question 3
(Eigenvalues and Eigenvectors).
- State the Rayleigh Quotient Iteration Algorithm to find eigenvalues/eigenvectors for general real symmetric matrix \(A \in \mathbb {R}^{m \times m}\).
- Prove that the spectrum (the set of all eigenvalues) of any matrix \(A \in \mathbb {C}^{m \times m}\) is contained in the union of the following \(m\) disks, \(D_i\), in the complex plane: \[ D_i = \left \{z \in \mathbb {C} : |z - a_{ii}| \le \sum _{\substack {j=1\\ j\ne i}}^m |a_{ij}|\right \},\qquad 1 \le i \le m. \]
-
Fall 2023 • Question 4
Solution of a nonlinear fixed point problem
Consider the fixed-point problem \(x = g(x)\) for a continuously differentiable real-valued function \(g\) and assume that it has a solution \(\alpha \) for which \(|g'(\alpha )| < 1\). State and prove a convergence theorem for fixed point iteration \(x^{(k+1)} = g(x^{(k)})\) for this problem. Note: Do not assume more about the function \(g\) than is stated in the problem.
-
Spring 2020 • Question 4
Numerical Algorithm to Find Eigenvalues/Eigenvectors
State the Rayleigh Quotient Iteration Algorithm to find eigenvalues/eigenvectors for general real symmetric matrix \(A\in \mathbb {R}^{m\times m}\).
-
Spring 2016 • Question 2
Numerical Algorithm to Find Eigenvectors/Eigenvalues
State the Inverse Iteration Algorithm to find eigenvectors/eigenvalues for general real symmetric matrix \(A\in \mathbb {R}^{m\times m}\).
-
Spring 2010 • Question 8
{Numerical Methods for ODEs:} Consider the Linear Multistep Method \[ y_{n+2}-\frac{4}{3}y_{n+1}+\frac{1}{3}y_n=\frac{2}{3}k f_{n+2} \] for solving an initial value problem \(y'=f(y,x)\), \(y(0)=\eta\). You may assume that \(f\) is Lipschitz continuous with respect to \(y\) uniformly for all \(x\). **a)** Analyze the consistency, stability, accuracy, and convergence properties of this method. **b)** Sketch a graph of the solution to the following initial value problem. \[ y'=-10^8[y-\cos(x)]-\sin(x),\qquad y(0)=2. \] Would it be more reasonable to use this method or Euler's method for this problem? What would you consider in choosing a timestep \(k\) for each of the methods? Justify your answer. **Fact 1:** A real symmetric \(n\times n\) matrix \(A\) can be diagonalized by an orthogonal similarity transformation, and \(A\)'s eigenvalues are real. **Fact 2:** The \((N-1)\times(N-1)\) matrix \(M\) defined by \[ M= \begin{bmatrix} -2 & 1 & 0 & \cdots & 0 & 0\\ 1 & -2 & 1 & \ddots & \vdots & \vdots\\ 0 & 1 & -2 & \ddots & 0 & 0\\ \vdots & \ddots & \ddots & \ddots & 1 & 0\\ 0 & \cdots & 0 & 1 & -2 & 1\\ 0 & \cdots & 0 & 0 & 1 & -2 \end{bmatrix} \] has eigenvalues \[ \mu_l=-4\sin^2\left(\frac{\pi l}{2N}\right), \qquad l=1,2,\ldots,N-1. \] **Fact 3:** The \((N+1)\times(N+1)\) matrix: \[ \begin{bmatrix} -1 & 1 & 0 & \cdots & 0 & 0\\ 1 & -2 & 1 & \ddots & \vdots & \vdots\\ 0 & 1 & -2 & \ddots & 0 & 0\\ \vdots & \ddots & \ddots & \ddots & 1 & 0\\ 0 & \cdots & 0 & 1 & -2 & 1\\ 0 & \cdots & 0 & 0 & 1 & -1 \end{bmatrix} \] has eigenvalues \[ \mu_l=-4\sin^2\left(\frac{\pi l}{2(N+1)}\right), \qquad l=0,1,\ldots,N. \] **Fact 4:** For a real \(n\times n\) matrix \(A\), the Rayleigh quotient of a vector \(x\in\mathbb{R}^n\) is the scalar \[ r(x)=\frac{x^T Ax}{x^T x}. \] The gradient of \(r(x)\) is \[ \nabla r(x)=\frac{2}{x^T x}(Ax-r(x)x). \] If \(x\) is an eigenvector of \(A\) then \(r(x)\) is the corresponding eigenvalue and \(\nabla r(x)=0\).
-
Fall 2007 • 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 \(\|x\|_2=\|y\|_2=1\). Consider the perturbed matrix \(A+\delta A\), where \(\|\delta A\|_2/\|A\|_2=\epsilon\ll1\). Show that the matrix \(A+\delta A\) has an eigenvalue \(\mu\) such that \(|\lambda-\mu|\) is approximately \(\epsilon/|y^*x|\). (Note that this implies that \(|\lambda-\mu|\leq(2/|y^*x|)\epsilon\) for \(\epsilon\) sufficiently small.) **b)** Consider a matrix \(A\) with double eigenvalue \(\lambda\) and a perturbation \(\delta A\) of \(A\) as above. Must there be a constant \(C\) such that \(A+\delta A\) has an eigenvalue \(\mu\) for which \(|\lambda-\mu|\leq C\epsilon\) for all sufficiently small \(\epsilon\)? If yes, prove it. If no, construct and analyze an example that shows such a \(C\) need not exist. **c)** Consider the problem of computing an eigenvalue/eigenvector pair of a real symmetric \(m\times m\) matrix \(A\) with eigenvalues that satisfy \(|\lambda_1|>|\lambda_2|>\cdots>|\lambda_m|\). One algorithm for trying to do this is Power Iteration with Rayleigh Quotient approximation of the eigenvalue: Guess \(v^{(0)}\) with \(\|v^{(0)}\|_2=1\). Set \(\lambda^{(0)}=(v^{(0)})^TAv^{(0)}\). For \(k=1,2,3,\ldots\) \[ \begin{aligned} &\text{Let } w=Av^{(k-1)},\\ &v^{(k)}=w/\|w\|_2,\\ &\lambda^{(k)}=(v^{(k)})^TAv^{(k)}. \end{aligned} \] End Analyze the convergence of the approximate eigenvector \(v^{(k)}\) and the approximate eigenvalue \(\lambda^{(k)}\). To what do these quantities converge, and how fast do they converge?
-
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 \).
-
Winter 2005 • 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 \): \[ \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)}. \] 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 \).
-
Fall 2002 • Question 3
Eigenvalue Problems
(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\)
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} \] 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?
(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 \).
-
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 \).
-
Fall 1998 • Question 4
Eigenvalue Problems
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:
Power Iteration
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
i) Analyze the convergence properties of the Power Iteration algorithm for a generic guess \(v^0\).
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 \).
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\).
-
Fall 1998 • Question 8
**Finite-Element Methods** Consider the problem \[ -u''+u=f,\qquad \text{on }[0,1] \] with \(u(0)=0\) and \(u(1)=1\). Derive a variational formulations of this problem (be sure to define the space on which your variational problem is to be solved). Formulate a Galerkin finite-element method for the variational problem using piecewise linear functions. Prove that the linear system which arises in the finite-element method has a solution. In what sense is the solution optimal? **Fact 1:** A real symmetric \(n\times n\) matrix \(A\) can be diagonalized by an orthogonal similarity transformation, and \(A\)'s eigenvalues are real. **Fact 2:** The \((N-1)\times(N-1)\) matrix \(M\) defined by \[ m_{ij}= \begin{cases} 2, & i=j,\\ -1, & \lvert i-j\rvert=1,\\ 0, & \text{otherwise}, \end{cases} \] has eigenvalues \[ \mu_l=4\sin^2\left(\frac{\pi l}{2N}\right),\qquad l=1,2,\ldots,N-1. \] **Fact 3:** The \((N+1)\times(N+1)\) matrix: \[ \begin{bmatrix} -1 & 1 & 0 & \cdots & 0 & 0\\ 1 & -2 & 1 & \ddots & 0 & 0\\ 0 & 1 & -2 & \ddots & 0 & 0\\ \vdots & \ddots & \ddots & \ddots & 1 & 0\\ 0 & 0 & 0 & 1 & -2 & 1\\ 0 & 0 & 0 & 0 & 1 & -1 \end{bmatrix} \] has eigenvalues \[ \mu_l=-4\sin^2\left(\frac{\pi l}{2(N+1)}\right),\qquad l=0,1,\ldots,N. \] **Fact 4:** For a real \(n\times n\) matrix \(A\), the Rayleigh quotient of a vector \(x\in\mathbb{R}^n\) is the scalar \[ r(x)=\frac{x^TAx}{x^Tx}. \] The gradient of \(r(x)\) is \[ \nabla r(x)=\frac{2}{x^Tx}(Ax-r(x)x). \] If \(x\) is an eigenvector of \(A\) then \(r(x)\) is the corresponding eigenvalue and \(\nabla r(x)=0\).
-
Fall 1997 • Question 7
Broyden’s Method Consider the nonlinear system: \[ F(x)=0\qquad \text {where }F:\mathbb {R}^n\to \mathbb {R}^n \] and the iteration \[ x^{(k+1)}=x^{(k)}-(A^{(k)})^{-1}F(x^{(k)}) \] where \(x^{(0)}\in \mathbb {R}^n\) is given.
Newton’s Method is defined by the choice \(A^{(k)}=F'(x)\) where \(F'(x)\) is the Jacobean matrix of \(F\). An alternative choice for \(A^{(k+1)}\) is made in Broyden’s Method and is motivated as follows:
Let \(A^{(0)}\) be a given and suitably chosen matrix. The scalar Secant Method suggests imposing on \(A^{(k+1)}\) the condition \[ A^{(k+1)}(x^{(k+1)}-x^{(k)})=F(x^{(k+1)})-F(x^{(k)}). \] This however does not uniquely determine \(A^{k+1}\) as it does not give any information on how \(A^{k+1}\) acts on vectors perpendicular to \((x^{(k+1)}-x^{(k)})\). Thus require also that: \[ A^{(k+1)}t=A^{(k)}t \qquad \text {for all }t\in \mathbb {R}^n\text { such that } t^T(x^{(k+1)}-x^{(k)})=0 \] Use these conditions to derive an explicit expression for \(A^{(k+1)}\) in terms of \(A^{(k)}\), \(x^{(k)}\), and \(x^{(k+1)}\).