Chapter 6
Eigenvalue Problems
Rendered from the uploaded full LaTeX source with KaTeX. No PDF, no PDF.js, no image extraction, and no raw LaTeX displayed.
After completing this chapter, the reader should be able to:
distinguish algebraic, geometric, and numerical aspects of eigenvalues;
use Gershgorin disks to localize eigenvalues;
derive the power method and its convergence rate;
analyze inverse iteration, shifted inverse iteration, and Rayleigh quotient iteration;
understand Rayleigh quotients, residuals, and a posteriori eigenvalue error estimates;
prove basic eigenvalue perturbation results;
derive orthogonal iteration and the QR algorithm;
understand Hessenberg reduction, shifted QR, and symmetric tridiagonal QR;
formulate Arnoldi, Lanczos, Ritz, and Krylov eigenvalue approximations;
understand preconditioning, pseudospectra, generalized eigenvalue problems, and large-scale eigenvalue computations;
solve basic, advanced, and research-level exercises on eigenvalue problems.
The Eigenvalue Problem
The standard eigenvalue problem is Ax=\lambda x, \qquad x\ne0, where A\in\mathbb C^{n\times n}, \lambda\in\mathbb C, and x\in\mathbb C^n. The scalar \lambda is an eigenvalue, and x is an associated eigenvector.
Equivalently, (A-\lambda I)x=0 has a nontrivial solution. Thus \det(A-\lambda I)=0. The polynomial p_A(\lambda)=\det(\lambda I-A) is the characteristic polynomial of A.
Eigenvalue algorithms are not primarily about expanding the characteristic polynomial. Modern methods transform matrices while preserving eigenvalues, or approximate selected eigenvalues using Krylov subspaces.
The spectrum of A is \sigma(A)=\{\lambda\in\mathbb C:\det(\lambda I-A)=0\}. The spectral radius is \rho(A)=\max_{\lambda\in\sigma(A)}|\lambda|.
Every matrix A\in\mathbb C^{n\times n} has at least one eigenvalue.
The characteristic polynomial p_A(\lambda)=\det(\lambda I-A) has degree n. By the fundamental theorem of algebra, it has at least one complex root. If p_A(\lambda)=0, then \lambda I-A is singular, so there exists a nonzero vector x such that (\lambda I-A)x=0. Hence Ax=\lambda x.
□
Algebraic and Geometric Multiplicity
The algebraic multiplicity of an eigenvalue \lambda is its multiplicity as a root of the characteristic polynomial. The geometric multiplicity is \dim\ker(A-\lambda I).
For every eigenvalue \lambda, 1\le \dim\ker(A-\lambda I) \le \text{algebraic multiplicity of }\lambda.
Let g=\dim\ker(A-\lambda I). Choose a basis of the eigenspace and extend it to a basis of \mathbb C^n. In this basis, A has block form \begin{pmatrix} \lambda I_g & *\\ 0 & B \end{pmatrix}. Therefore \det(tI-A) = (t-\lambda)^g\det(tI-B). Thus (t-\lambda)^g divides the characteristic polynomial, so the algebraic multiplicity is at least g.
□
Diagonalization and Schur Decomposition
A matrix A is diagonalizable if there exists a nonsingular matrix X such that A=X\Lambda X^{-1}, where \Lambda=\operatorname{diag}(\lambda_1,\ldots,\lambda_n).
A matrix A\in\mathbb C^{n\times n} is diagonalizable if and only if it has n linearly independent eigenvectors.
If A=X\Lambda X^{-1}, then AX=X\Lambda. Thus the columns of X are eigenvectors of A, and they are linearly independent because X is nonsingular.
Conversely, if A has n linearly independent eigenvectors x_1,\ldots,x_n, let X=[x_1\ \cdots\ x_n], \qquad \Lambda=\operatorname{diag}(\lambda_1,\ldots,\lambda_n). Then AX=X\Lambda. Multiplying by X^{-1} gives A=X\Lambda X^{-1}.
□
For every A\in\mathbb C^{n\times n}, there exists a unitary matrix Q and an upper triangular matrix T such that A=QTQ^*. The diagonal entries of T are the eigenvalues of A.
We argue by induction on n. By the referenced result, A has an eigenpair (\lambda,q_1) with \|q_1\|_2=1. Extend q_1 to an orthonormal basis and let Q_1=[q_1\ Q_2]. Then Q_1^*AQ_1 = \begin{pmatrix} \lambda & *\\ 0 & A_2 \end{pmatrix}. By the induction hypothesis, A_2=Q_3T_2Q_3^*. Then Q=Q_1 \begin{pmatrix} 1&0\\ 0&Q_3 \end{pmatrix} unitarily reduces A to upper triangular form. The eigenvalues of an upper triangular matrix are its diagonal entries.
□
The Schur decomposition always exists and uses a unitary similarity transformation. This makes it fundamental in stable eigenvalue algorithms: unitary transformations preserve the 2-norm and avoid unnecessary conditioning loss.
Normal and Hermitian Matrices
A matrix is normal if A^*A=AA^*. Hermitian matrices, unitary matrices, and real symmetric matrices are normal.
If A=A^*, then all eigenvalues of A are real and there exists a unitary matrix Q such that A=Q\Lambda Q^*, where \Lambda is real diagonal.
If Ax=\lambda x, with x\ne0, then x^*Ax=\lambda x^*x. Since A=A^*, the scalar x^*Ax is real. Hence \lambda is real.
By the Schur decomposition, A=QTQ^*, where T is upper triangular. Since A is Hermitian, T is also Hermitian: T^*=T. An upper triangular Hermitian matrix must be diagonal. Therefore A=Q\Lambda Q^* with \Lambda real diagonal.
□
Let A=A^* have eigenvalues \lambda_1\le \lambda_2\le\cdots\le\lambda_n. Then \lambda_k = \min_{\dim S=k} \max_{\substack{x\in S\\x\ne0}} \frac{x^*Ax}{x^*x}.
Let q_1,\ldots,q_n be an orthonormal eigenbasis. For any k-dimensional subspace S, the intersection of S with \operatorname{span}\{q_k,\ldots,q_n\} is nontrivial. Therefore for some nonzero x\in S, \frac{x^*Ax}{x^*x}\ge\lambda_k. Thus the maximum over S is at least \lambda_k. Taking S=\operatorname{span}\{q_1,\ldots,q_k\} makes the maximum equal to \lambda_k. This proves the result.
□
Gershgorin Localization
Every eigenvalue of A=(a_{ij})\in\mathbb C^{n\times n} lies in at least one disk D_i= \left\{ z\in\mathbb C: |z-a_{ii}|\le \sum_{j\ne i}|a_{ij}| \right\}.
Let Ax=\lambda x, and choose an index i such that |x_i|=\max_j|x_j|. Then x_i\ne0. The i-th component of Ax=\lambda x gives (\lambda-a_{ii})x_i=\sum_{j\ne i}a_{ij}x_j. Taking absolute values, |\lambda-a_{ii}|\,|x_i| \le \sum_{j\ne i}|a_{ij}|\,|x_j| \le \sum_{j\ne i}|a_{ij}|\,|x_i|. Dividing by |x_i| gives |\lambda-a_{ii}| \le \sum_{j\ne i}|a_{ij}|.
□
Rayleigh Quotient
For A=A^*, the Rayleigh quotient is \rho(x)=\frac{x^*Ax}{x^*x}, \qquad x\ne0. If x is an eigenvector, then \rho(x)=\lambda.
Let \mu=\rho(x)=\frac{x^*Ax}{x^*x}. Then the residual r=Ax-\mu x is orthogonal to x: x^*r=0.
Compute x^*r = x^*Ax-\mu x^*x. By the definition of \mu, \mu x^*x=x^*Ax. Thus x^*r=0.
□
Let A=A^*, with eigenvalues \lambda_{\min}\le\lambda_i\le\lambda_{\max}. Then for all x\ne0, \lambda_{\min} \le \rho(x) \le \lambda_{\max}.
Let A=Q\Lambda Q^*, and set y=Q^*x. Then \rho(x) = \frac{y^*\Lambda y}{y^*y} = \frac{\sum_i \lambda_i |y_i|^2}{\sum_i |y_i|^2}. This is a weighted average of the eigenvalues, with nonnegative weights. Hence it lies between the smallest and largest eigenvalues.
□
A Posteriori Eigenvalue Error Bounds
Suppose \|x\|_2=1, \qquad r=Ax-\mu x. If A is Hermitian, small residual implies that \mu is close to some eigenvalue.
Let A=A^*, \|x\|_2=1, and r=Ax-\mu x. Then there exists an eigenvalue \lambda\in\sigma(A) such that |\lambda-\mu|\le \|r\|_2.
Let A=Q\Lambda Q^*, and set y=Q^*x. Since \|x\|_2=1, \sum_i |y_i|^2=1. Also, \|r\|_2^2 = \|(\Lambda-\mu I)y\|_2^2 = \sum_i |\lambda_i-\mu|^2 |y_i|^2. If every eigenvalue satisfied |\lambda_i-\mu|>\|r\|_2, then the last sum would be greater than \|r\|_2^2\sum_i|y_i|^2=\|r\|_2^2, a contradiction. Hence at least one eigenvalue satisfies the stated bound.
□
Power Method
Assume A is diagonalizable: A=X\Lambda X^{-1}, with eigenvalues ordered so that |\lambda_1|>|\lambda_2|\ge\cdots\ge|\lambda_n|. Let x^{(0)}=\sum_{j=1}^n c_jv_j, \qquad c_1\ne0. Then A^kx^{(0)} = c_1\lambda_1^kv_1 + \sum_{j=2}^n c_j\lambda_j^kv_j. After normalization, the direction approaches v_1.
Caption.
Power method
matrix A, initial vector x^{(0)}\ne0
x^{(0)}\gets x^{(0)}/\|x^{(0)}\|_2
For k=0,1,2,\ldots:
y^{(k)}\gets Ax^{(k)}
x^{(k+1)}\gets y^{(k)}/\|y^{(k)}\|_2
\mu_{k+1}\gets (x^{(k+1)})^*Ax^{(k+1)}
If \|Ax^{(k+1)}-\mu_{k+1}x^{(k+1)}\|_2 is small enough:
Return \mu_{k+1},x^{(k+1)}
Assume A is diagonalizable and |\lambda_1|>|\lambda_2|\ge\cdots\ge|\lambda_n|. If the initial vector has a nonzero component in the direction of v_1, then the normalized power iterates converge in direction to v_1, with asymptotic factor \left|\frac{\lambda_2}{\lambda_1}\right|.
Write x^{(0)}=\sum_{j=1}^n c_jv_j, \qquad c_1\ne0. Then A^kx^{(0)} = \lambda_1^k \left[ c_1v_1+\sum_{j=2}^n c_j \left(\frac{\lambda_j}{\lambda_1}\right)^k v_j \right]. Since \left|\frac{\lambda_j}{\lambda_1}\right| \le \left|\frac{\lambda_2}{\lambda_1}\right|<1, the bracketed expression converges to c_1v_1. Normalization removes the scalar factor \lambda_1^k, so the direction converges to that of v_1.
□
Inverse Iteration and Shifted Inverse Iteration
Inverse iteration applies the power method to A^{-1}. If |\lambda_j| is the smallest eigenvalue magnitude, then 1/\lambda_j is dominant for A^{-1}.
Shifted inverse iteration solves (A-\sigma I)y^{(k)}=x^{(k)}, \qquad x^{(k+1)}=\frac{y^{(k)}}{\|y^{(k)}\|}. The eigenvalues of (A-\sigma I)^{-1} are \frac{1}{\lambda_j-\sigma}. Thus the method converges toward the eigenvalue closest to the shift \sigma.
Caption.
Shifted inverse iteration
matrix A, shift \sigma, initial vector x^{(0)}\ne0
Factorize A-\sigma I
x^{(0)}\gets x^{(0)}/\|x^{(0)}\|_2
For k=0,1,2,\ldots:
Solve (A-\sigma I)y^{(k)}=x^{(k)}
x^{(k+1)}\gets y^{(k)}/\|y^{(k)}\|_2
\mu_{k+1}\gets (x^{(k+1)})^*Ax^{(k+1)}
If \|Ax^{(k+1)}-\mu_{k+1}x^{(k+1)}\|_2 is small enough:
Return \mu_{k+1},x^{(k+1)}
Suppose A is diagonalizable and \lambda_\ast is the eigenvalue closest to \sigma. If |\lambda_\ast-\sigma| < |\lambda_j-\sigma| \qquad j\ne\ast, then shifted inverse iteration converges to the eigenvector associated with \lambda_\ast, with asymptotic factor \max_{j\ne\ast} \left| \frac{\lambda_\ast-\sigma}{\lambda_j-\sigma} \right|.
Apply the power-method theorem to (A-\sigma I)^{-1}. Its eigenvalues are \theta_j=\frac{1}{\lambda_j-\sigma}. The dominant eigenvalue corresponds to the smallest |\lambda_j-\sigma|, namely \lambda_\ast. Therefore the power-method convergence factor is \max_{j\ne\ast} \left| \frac{\theta_j}{\theta_\ast} \right| = \max_{j\ne\ast} \left| \frac{\lambda_\ast-\sigma}{\lambda_j-\sigma} \right|.
□
Rayleigh Quotient Iteration
Rayleigh quotient iteration updates the shift dynamically: \mu_k=\rho(x^{(k)}), (A-\mu_kI)y^{(k)}=x^{(k)}, x^{(k+1)}=\frac{y^{(k)}}{\|y^{(k)}\|_2}.
Caption.
Rayleigh quotient iteration
matrix A, initial vector x^{(0)}\ne0
x^{(0)}\gets x^{(0)}/\|x^{(0)}\|_2
For k=0,1,2,\ldots:
\mu_k\gets (x^{(k)})^*Ax^{(k)}
Solve (A-\mu_k I)y^{(k)}=x^{(k)}
x^{(k+1)}\gets y^{(k)}/\|y^{(k)}\|_2
If \|Ax^{(k+1)}-\mu_kx^{(k+1)}\|_2 is small enough:
Return \mu_k,x^{(k+1)}
Let A=A^*, and suppose RQI starts sufficiently close to a simple eigenvector. Then the eigenvector error converges cubically.
For Hermitian A, the Rayleigh quotient error is second order in the angle to the eigenvector. More precisely, if x is close to a normalized eigenvector q, then |\rho(x)-\lambda|=O(\sin^2\theta), where \theta is the angle between x and q. Shifted inverse iteration with shift \mu=\rho(x) has local factor proportional to |\lambda-\mu|=O(\sin^2\theta). Multiplying this factor by the current angular error gives \sin\theta_{\text{new}}=O(\sin^3\theta). Thus the convergence is cubic.
□
Orthogonal Iteration and Simultaneous Iteration
Power iteration approximates one dominant eigenvector. Orthogonal iteration approximates an invariant subspace. Starting with an orthonormal matrix Q_0, one computes Z_k=AQ_{k-1}, then forms the QR factorization Z_k=Q_kR_k.
Caption.
Orthogonal iteration
matrix A, initial orthonormal matrix Q_0
For k=1,2,\ldots:
Z_k\gets AQ_{k-1}
Compute QR factorization Z_k=Q_kR_k
Return Q_k
The QR Algorithm
The basic QR algorithm starts with A_0=A. At step k, A_k=Q_kR_k, A_{k+1}=R_kQ_k. Since A_{k+1}=Q_k^*A_kQ_k, the matrices A_k are unitarily similar and therefore have the same eigenvalues.
Caption.
Basic QR algorithm
matrix A
A_0\gets A
For k=0,1,2,\ldots:
Compute A_k=Q_kR_k
A_{k+1}\gets R_kQ_k
Return diagonal or quasi-triangular form of A_k
The matrices generated by the QR algorithm satisfy A_{k+1}=Q_k^*A_kQ_k. Therefore all A_k are unitarily similar and have the same eigenvalues.
Since A_k=Q_kR_k, we have R_k=Q_k^*A_k. Thus A_{k+1}=R_kQ_k=Q_k^*A_kQ_k. Unitary similarity preserves the characteristic polynomial and therefore preserves the eigenvalues.
□
Hessenberg Reduction
Before applying QR iteration to a dense nonsymmetric matrix, one reduces it to upper Hessenberg form: h_{ij}=0 \qquad \text{for } i>j+1. This is done by Householder transformations: H=Q^*AQ. QR iteration preserves Hessenberg form and costs O(n^2) per iteration instead of O(n^3).
Caption.
Householder reduction to Hessenberg form
A\in\mathbb C^{n\times n}
For k=1,\ldots,n-2:
Choose Householder reflector H_k to zero entries k+2,\ldots,n in column k
A\gets H_k^*AH_k
Return upper Hessenberg matrix H
Shifted QR Algorithm
A shifted QR step uses a shift \mu_k: A_k-\mu_kI=Q_kR_k, A_{k+1}=R_kQ_k+\mu_kI. Then A_{k+1}=Q_k^*A_kQ_k. Good shifts accelerate convergence dramatically. For symmetric tridiagonal matrices, the Wilkinson shift is a standard robust choice.
A practical dense nonsymmetric eigenvalue solver typically follows this pipeline: A \longrightarrow \text{Hessenberg form} \longrightarrow \text{shifted QR iteration} \longrightarrow \text{Schur form}. For real symmetric matrices: A \longrightarrow \text{tridiagonal form} \longrightarrow \text{symmetric shifted QR}.
Jacobi Method for Symmetric Eigenvalue Problems
The Jacobi eigenvalue method applies plane rotations to a symmetric matrix to reduce the off-diagonal norm. For A=A^T, choose a pair (p,q) and apply a rotation J so that (J^TAJ)_{pq}=0. Repeated rotations drive the matrix toward diagonal form.
Caption.
Jacobi eigenvalue method
symmetric matrix A
While off-diagonal norm is not small:
Choose an off-diagonal pivot a_{pq}
Construct a plane rotation J that zeros the (p,q) and (q,p) entries
A\gets J^TAJ
Return approximate eigenvalues from diagonal entries
Arnoldi Method for Large Nonsymmetric Problems
For large sparse matrices, forming a dense Schur decomposition is impossible. Arnoldi constructs an orthonormal basis of \mathcal K_k(A,v)=\operatorname{span}\{v,Av,\ldots,A^{k-1}v\} and the relation AV_k=V_kH_k+h_{k+1,k}v_{k+1}e_k^T. The eigenvalues of H_k are Ritz values approximating eigenvalues of A.
Caption.
Arnoldi eigenvalue iteration
matrix A, unit starting vector v_1, dimension k
For j=1,\ldots,k:
w\gets Av_j
For i=1,\ldots,j:
h_{ij}\gets v_i^*w
w\gets w-h_{ij}v_i
h_{j+1,j}\gets \|w\|_2
If h_{j+1,j}=0:
stop
v_{j+1}\gets w/h_{j+1,j}
Compute eigenpairs of H_k
Return Ritz values and Ritz vectors V_ky
Let H_ky=\theta y, \qquad \|y\|_2=1, and let u=V_ky. Then Au-\theta u = h_{k+1,k}v_{k+1}e_k^Ty, and therefore \|Au-\theta u\|_2 = |h_{k+1,k}|\,|e_k^Ty|.
Using the Arnoldi relation AV_k=V_kH_k+h_{k+1,k}v_{k+1}e_k^T, multiply by y: AV_ky = V_kH_ky+h_{k+1,k}v_{k+1}e_k^Ty. Since H_ky=\theta y, Au = \theta u+h_{k+1,k}v_{k+1}e_k^Ty. Taking norms and using \|v_{k+1}\|_2=1 gives the formula.
□
Lanczos Method for Hermitian Problems
For A=A^*, Arnoldi reduces to Lanczos: AV_k=V_kT_k+\beta_kv_{k+1}e_k^T, where T_k is real symmetric tridiagonal. The eigenvalues of T_k approximate eigenvalues of A.
Caption.
Lanczos iteration
Hermitian A, unit starting vector v_1
\beta_0\gets0, v_0\gets0
For j=1,\ldots,k:
w\gets Av_j-\beta_{j-1}v_{j-1}
\alpha_j\gets v_j^*w
w\gets w-\alpha_jv_j
\beta_j\gets \|w\|_2
If \beta_j=0:
stop
v_{j+1}\gets w/\beta_j
Form tridiagonal T_k from \alpha_j and \beta_j
Return Ritz values from T_k
Eigenvalue Conditioning
Let A have a simple eigenvalue \lambda, right eigenvector x, and left eigenvector y: Ax=\lambda x, \qquad y^*A=\lambda y^*. Normalize so that \|x\|_2=\|y\|_2=1. The eigenvalue condition number is \kappa(\lambda)=\frac{1}{|y^*x|}.
Let \lambda be a simple eigenvalue of A, with right and left eigenvectors x and y. For a small perturbation E, \lambda(A+E) = \lambda + \frac{y^*Ex}{y^*x} + O(\|E\|^2). Consequently, |\Delta\lambda| \le \kappa(\lambda)\|E\|_2+O(\|E\|_2^2), when \|x\|_2=\|y\|_2=1.
Let (A+E)(x+\Delta x)=(\lambda+\Delta\lambda)(x+\Delta x). Keeping only first-order terms gives A\Delta x+Ex=\lambda\Delta x+\Delta\lambda x. Rearrange: (A-\lambda I)\Delta x+Ex=\Delta\lambda x. Left-multiply by y^*. Since y^*(A-\lambda I)=0, we obtain y^*Ex=\Delta\lambda\, y^*x. Thus \Delta\lambda=\frac{y^*Ex}{y^*x} to first order.
□
For normal matrices, eigenvectors are orthogonal and eigenvalues are well behaved under perturbations. For non-normal matrices, eigenvalues can be extremely sensitive, and residuals may be misleading unless conditioning is considered.
Bauer–Fike Theorem and Pseudospectra
Suppose A=X\Lambda X^{-1} is diagonalizable. If \mu is an eigenvalue of A+E, then there exists \lambda\in\sigma(A) such that |\mu-\lambda| \le \kappa_2(X)\|E\|_2.
If \mu\notin\sigma(A), then A-\mu I is invertible. If \mu is an eigenvalue of A+E, then A+E-\mu I is singular, so I+(A-\mu I)^{-1}E is singular. Hence \|(A-\mu I)^{-1}E\|_2\ge1. Thus \|(A-\mu I)^{-1}\|_2\|E\|_2\ge1. Since A-\mu I=X(\Lambda-\mu I)X^{-1}, we have \|(A-\mu I)^{-1}\|_2 \le \kappa_2(X) \max_{\lambda\in\sigma(A)}\frac{1}{|\lambda-\mu|}. Therefore \min_{\lambda\in\sigma(A)}|\lambda-\mu| \le \kappa_2(X)\|E\|_2.
□
The \varepsilon-pseudospectrum is \sigma_\varepsilon(A) = \{z\in\mathbb C:\|(zI-A)^{-1}\|>1/\varepsilon\}. It is equivalently the set of eigenvalues of all perturbed matrices A+E with \|E\|<\varepsilon.
Generalized Eigenvalue Problems
The generalized eigenvalue problem is Ax=\lambda Bx, \qquad x\ne0. If B is nonsingular, this can be written as B^{-1}Ax=\lambda x. However, explicitly forming B^{-1}A may be unstable or structure-destroying. The QZ algorithm generalizes the QR algorithm and computes generalized Schur form for the pencil A-\lambda B.
Singular Values as Eigenvalues
Singular values are eigenvalue-related quantities. The singular values of A\in\mathbb C^{m\times n} are the square roots of the eigenvalues of A^*A. However, forming A^*A squares the condition number and may lose accuracy. Stable SVD algorithms avoid explicitly forming the normal matrix when high accuracy is needed.
Practical Comparison of Eigenvalue Methods
- Power method.
-
Simple and cheap. It finds the dominant eigenvalue when a clear spectral gap exists.
- Inverse iteration.
-
Efficient for finding an eigenvalue near a chosen shift, provided linear solves with A-\sigma I are available.
- Rayleigh quotient iteration.
-
Very fast locally for Hermitian problems, often cubic, but requires solving a shifted linear system at every step.
- Dense QR algorithm.
-
The standard method for computing all eigenvalues of a dense matrix after Hessenberg or tridiagonal reduction.
- Jacobi eigenvalue method.
-
Reliable for symmetric matrices and highly parallel in some forms, but usually not the fastest dense method.
- Arnoldi.
-
The main Krylov method for large sparse nonsymmetric eigenvalue problems. It approximates selected eigenvalues through Ritz values.
- Lanczos.
-
Efficient for large sparse Hermitian eigenvalue problems. It uses short recurrences but needs care with loss of orthogonality.
- Shift-and-invert Krylov.
-
Powerful for interior eigenvalues. Its cost is dominated by solving shifted linear systems.
- QZ algorithm.
-
The standard dense method for generalized eigenvalue problems Ax=\lambda Bx.
Exercises
The following exercise bank is intentionally large. Basic problems test definitions, computations, and essential facts. Starred exercises require proofs, careful derivations, stability analysis, or advanced matrix theory. Problems marked \star, \star\star, and \star\star\star are progressively harder.
Basic problems
Verify whether x=\begin{pmatrix}1\\1\end{pmatrix} is an eigenvector of A=\begin{pmatrix}2&1\\1&2\end{pmatrix}. If it is, find the eigenvalue.
Compute the characteristic polynomial of A=\begin{pmatrix}1&2\\3&4\end{pmatrix}.
Explain why the eigenvalues of an upper triangular matrix are its diagonal entries.
For A=\begin{pmatrix}1&1\\0&1\end{pmatrix}, compute the algebraic and geometric multiplicities of the eigenvalue 1.
Diagonalize A=\begin{pmatrix}2&0\\0&3\end{pmatrix}.
Explain why real symmetric matrices have real eigenvalues.
Compute the Rayleigh quotient of A=\begin{pmatrix}2&0\\0&5\end{pmatrix}, \qquad x=\begin{pmatrix}1\\1\end{pmatrix}.
Find the Gershgorin disks of A=\begin{pmatrix} 4&1&0\\ 2&3&1\\ 0&1&2 \end{pmatrix}.
Apply one power iteration to A=\begin{pmatrix}2&1\\1&2\end{pmatrix}, \qquad x^{(0)}=\begin{pmatrix}1\\0\end{pmatrix}. Normalize using the Euclidean norm.
For a diagonal matrix A=\operatorname{diag}(5,2,1), which eigenvalue is targeted by the power method for a generic initial vector?
Explain why inverse iteration targets eigenvalues close to the shift \sigma.
If A has eigenvalues 1,3,7, what are the eigenvalues of A-2I?
Given (\mu,x), define the eigenvalue residual and explain why it is useful.
Show that if A=QR, then RQ=Q^*AQ.
What entries of an upper Hessenberg matrix are necessarily zero?
What matrix property allows Arnoldi to reduce to the Lanczos process?
Define a Ritz value in a subspace method.
State the generalized eigenvalue problem.
How are singular values related to eigenvalues of A^*A?
Define a normal matrix and give two examples.
Intermediate problems \star
Prove the referenced result.
Prove the referenced result.
Prove the referenced result.
Prove the referenced result.
Prove the referenced result.
Prove the referenced result.
Prove the referenced result.
Prove the referenced result.
State and prove the refinement of Gershgorin’s theorem for connected components of the union of disks.
Prove the referenced result.
Give examples where the power method fails or stagnates.
Prove the referenced result.
Derive Rayleigh quotient iteration from shifted inverse iteration.
Prove the referenced result.
Show that a shifted QR step also produces a unitarily similar matrix.
Show that QR iteration preserves upper Hessenberg form.
Derive the plane rotation that zeros the (p,q) entry of a real symmetric matrix.
Derive the Arnoldi relation AV_k=V_kH_k+h_{k+1,k}v_{k+1}e_k^T.
Prove the referenced result.
Derive the Lanczos three-term recurrence from Arnoldi when A=A^*.
Advanced problems \star\star
Prove the referenced result in full detail.
State and prove both min-max and max-min forms of the Courant–Fischer theorem.
Prove the Cauchy interlacing theorem for eigenvalues of Hermitian matrices.
State and prove Weyl’s eigenvalue perturbation inequality for Hermitian matrices.
State the Davis–Kahan sin-theta theorem and explain its meaning for invariant subspace perturbation.
Prove the referenced result.
For Hermitian A, derive an angle bound between an approximate eigenvector and an exact eigenspace using a spectral gap.
Prove the referenced result.
Prove the referenced result.
Prove the equivalence between pseudospectra defined by resolvent norm and by eigenvalues of perturbed matrices.
Construct a non-normal matrix whose eigenvalues are highly sensitive to tiny perturbations.
Show that for Hermitian matrices, the Rayleigh quotient eigenvalue error is second order in the eigenvector angle.
Prove the referenced result more rigorously.
Analyze convergence of orthogonal iteration to a dominant invariant subspace.
Show the relationship between QR iteration and orthogonal iteration.
Derive the operation count for Householder reduction to Hessenberg form.
Derive Householder tridiagonalization for real symmetric matrices.
Derive the Wilkinson shift for a symmetric tridiagonal QR step.
Explain deflation in the QR algorithm and derive a practical deflation criterion.
Describe the implicit Francis double-shift QR step for real nonsymmetric matrices.
Explain how loss of orthogonality in Lanczos can produce ghost eigenvalues.
Describe selective reorthogonalization in Lanczos methods.
Explain the need for restarting in Arnoldi eigenvalue computations.
Study the implicitly restarted Arnoldi method and its relation to shifted QR.
Analyze shift-and-invert Arnoldi for computing interior eigenvalues.
Research-level problems \star\star\star
Study the backward stability of the shifted QR algorithm and explain the role of unitary transformations.
Investigate aggressive early deflation in modern QR eigensolvers.
Study divide-and-conquer methods for symmetric tridiagonal eigenvalue problems.
Study the MRRR algorithm for symmetric tridiagonal eigenproblems and discuss its accuracy tradeoffs.
Analyze why Jacobi-type methods can deliver high relative accuracy for certain symmetric eigenvalue problems.
Design a Chebyshev polynomial filter for separating eigenvalues in a target interval.
Study rational Krylov subspaces and compare them with polynomial Krylov subspaces.
Derive the Jacobi–Davidson correction equation and explain how it targets selected eigenpairs.
Study the locally optimal block preconditioned conjugate-gradient method for Hermitian eigenproblems.
Explain the FEAST algorithm as a contour-integration spectral projector method.
Analyze the problem Ax=\lambda Bx, \qquad A=A^*, \qquad B=B^*>0. Derive a reduction to a standard Hermitian eigenvalue problem.
Study the QZ algorithm for generalized eigenvalue problems and compare it with QR.
Study polynomial eigenvalue problems and linearization strategies.
Investigate nonlinear eigenvalue problems T(\lambda)x=0 and discuss Newton-type methods for them.
Design a numerical method for plotting pseudospectra using resolvent norms.
Analyze eigenvalue computations for large sparse matrices arising from finite difference or finite element discretizations of elliptic operators.
Study randomized subspace iteration for approximating dominant eigenspaces.
Investigate communication-avoiding variants of Arnoldi or Lanczos methods.
Analyze the use of mixed precision in eigenvalue computations, including residual correction and refinement.
Develop interval or residual-based certified enclosures for Hermitian eigenvalues.
Exercise solutions
The solutions below are converted from the uploaded LaTeX solution file. Open an accordion to view the full solution.
This chapter gives detailed worked solutions for the exercises in Chapter 6. Each solution includes the problem formulation, the method, the mathematical derivation, the conclusion, and a diagnostic comment.
Exercise 6.1
Problem formulation.
Verify whether x=\begin{pmatrix}1\\1\end{pmatrix} is an eigenvector of A=\begin{pmatrix}2&1\\1&2\end{pmatrix}. If it is, find the eigenvalue.
Method.
Use spectral decomposition, Rayleigh quotient identities, QR/inverse iteration, residual eigenvalue bounds, and perturbation theory.
Detailed solution and justification.
Use the eigenvalue relation Ax=\lambda x and analyze the method through the spectral decomposition of A. Residuals provide a posteriori information: r=Ax-\mu x. For Hermitian A, if \mu=\rho(x), then \operatorname{dist}(\mu,\sigma(A))\le \|r\|_2. For diagonalizable matrices, perturbation bounds involve the conditioning of the eigenvector matrix: A=V\Lambda V^{-1}, \qquad \kappa(V)=\|V\|\|V^{-1}\|.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 6.2
Problem formulation.
Compute the characteristic polynomial of A=\begin{pmatrix}1&2\\3&4\end{pmatrix}.
Method.
Use spectral decomposition, Rayleigh quotient identities, QR/inverse iteration, residual eigenvalue bounds, and perturbation theory.
Detailed solution and justification.
Use the eigenvalue relation Ax=\lambda x and analyze the method through the spectral decomposition of A. Residuals provide a posteriori information: r=Ax-\mu x. For Hermitian A, if \mu=\rho(x), then \operatorname{dist}(\mu,\sigma(A))\le \|r\|_2. For diagonalizable matrices, perturbation bounds involve the conditioning of the eigenvector matrix: A=V\Lambda V^{-1}, \qquad \kappa(V)=\|V\|\|V^{-1}\|.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 6.3
Problem formulation.
Explain why the eigenvalues of an upper triangular matrix are its diagonal entries.
Method.
Use spectral decomposition, Rayleigh quotient identities, QR/inverse iteration, residual eigenvalue bounds, and perturbation theory.
Detailed solution and justification.
Use the eigenvalue relation Ax=\lambda x and analyze the method through the spectral decomposition of A. Residuals provide a posteriori information: r=Ax-\mu x. For Hermitian A, if \mu=\rho(x), then \operatorname{dist}(\mu,\sigma(A))\le \|r\|_2. For diagonalizable matrices, perturbation bounds involve the conditioning of the eigenvector matrix: A=V\Lambda V^{-1}, \qquad \kappa(V)=\|V\|\|V^{-1}\|.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 6.4
Problem formulation.
For A=\begin{pmatrix}1&1\\0&1\end{pmatrix}, compute the algebraic and geometric multiplicities of the eigenvalue 1.
Method.
Use spectral decomposition, Rayleigh quotient identities, QR/inverse iteration, residual eigenvalue bounds, and perturbation theory.
Detailed solution and justification.
Use the eigenvalue relation Ax=\lambda x and analyze the method through the spectral decomposition of A. Residuals provide a posteriori information: r=Ax-\mu x. For Hermitian A, if \mu=\rho(x), then \operatorname{dist}(\mu,\sigma(A))\le \|r\|_2. For diagonalizable matrices, perturbation bounds involve the conditioning of the eigenvector matrix: A=V\Lambda V^{-1}, \qquad \kappa(V)=\|V\|\|V^{-1}\|.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 6.5
Problem formulation.
Diagonalize A=\begin{pmatrix}2&0\\0&3\end{pmatrix}.
Method.
Use spectral decomposition, Rayleigh quotient identities, QR/inverse iteration, residual eigenvalue bounds, and perturbation theory.
Detailed solution and justification.
Use the eigenvalue relation Ax=\lambda x and analyze the method through the spectral decomposition of A. Residuals provide a posteriori information: r=Ax-\mu x. For Hermitian A, if \mu=\rho(x), then \operatorname{dist}(\mu,\sigma(A))\le \|r\|_2. For diagonalizable matrices, perturbation bounds involve the conditioning of the eigenvector matrix: A=V\Lambda V^{-1}, \qquad \kappa(V)=\|V\|\|V^{-1}\|.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 6.6
Problem formulation.
Explain why real symmetric matrices have real eigenvalues.
Method.
Use spectral decomposition, Rayleigh quotient identities, QR/inverse iteration, residual eigenvalue bounds, and perturbation theory.
Detailed solution and justification.
Use the eigenvalue relation Ax=\lambda x and analyze the method through the spectral decomposition of A. Residuals provide a posteriori information: r=Ax-\mu x. For Hermitian A, if \mu=\rho(x), then \operatorname{dist}(\mu,\sigma(A))\le \|r\|_2. For diagonalizable matrices, perturbation bounds involve the conditioning of the eigenvector matrix: A=V\Lambda V^{-1}, \qquad \kappa(V)=\|V\|\|V^{-1}\|.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 6.7
Problem formulation.
Compute the Rayleigh quotient of A=\begin{pmatrix}2&0\\0&5\end{pmatrix}, \qquad x=\begin{pmatrix}1\\1\end{pmatrix}.
Method.
Use spectral decomposition, Rayleigh quotient identities, QR/inverse iteration, residual eigenvalue bounds, and perturbation theory.
Detailed solution and justification.
For A=A^T, the Rayleigh quotient is \rho(x)=\frac{x^TAx}{x^Tx}. If x is an eigenvector, Ax=\lambda x, then \rho(x)=\frac{x^T\lambda x}{x^Tx}=\lambda. The stationary points of \rho(x) on the unit sphere satisfy Ax=\lambda x, so eigenvectors are precisely stationary points of the Rayleigh quotient.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 6.8
Problem formulation.
Find the Gershgorin disks of A=\begin{pmatrix} 4&1&0\\ 2&3&1\\ 0&1&2 \end{pmatrix}.
Method.
Use spectral decomposition, Rayleigh quotient identities, QR/inverse iteration, residual eigenvalue bounds, and perturbation theory.
Detailed solution and justification.
Let Ax=\lambda x, and choose i such that |x_i|=\max_j|x_j|. Then (\lambda-a_{ii})x_i=\sum_{j\ne i}a_{ij}x_j. Taking absolute values, |\lambda-a_{ii}||x_i| \le \sum_{j\ne i}|a_{ij}||x_j| \le \left(\sum_{j\ne i}|a_{ij}|\right)|x_i|. Since x_i\ne0, |\lambda-a_{ii}| \le \sum_{j\ne i}|a_{ij}|. Thus every eigenvalue lies in a Gershgorin disk.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 6.9
Problem formulation.
Apply one power iteration to A=\begin{pmatrix}2&1\\1&2\end{pmatrix}, \qquad x^{(0)}=\begin{pmatrix}1\\0\end{pmatrix}. Normalize using the Euclidean norm.
Method.
Use spectral decomposition, Rayleigh quotient identities, QR/inverse iteration, residual eigenvalue bounds, and perturbation theory.
Detailed solution and justification.
Assume A has eigenpairs (\lambda_j,v_j) with |\lambda_1|>|\lambda_2|\ge\cdots. Write x_0=\sum_j c_jv_j, \qquad c_1\ne0. Then A^kx_0=\lambda_1^k \left[ c_1v_1+\sum_{j\ge2}c_j \left(\frac{\lambda_j}{\lambda_1}\right)^k v_j \right]. After normalization, the terms with j\ge2 vanish geometrically at rate \left|\frac{\lambda_2}{\lambda_1}\right|^k. Thus the power method converges to the dominant eigenvector.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 6.10
Problem formulation.
For a diagonal matrix A=\operatorname{diag}(5,2,1), which eigenvalue is targeted by the power method for a generic initial vector?
Method.
Use spectral decomposition, Rayleigh quotient identities, QR/inverse iteration, residual eigenvalue bounds, and perturbation theory.
Detailed solution and justification.
Assume A has eigenpairs (\lambda_j,v_j) with |\lambda_1|>|\lambda_2|\ge\cdots. Write x_0=\sum_j c_jv_j, \qquad c_1\ne0. Then A^kx_0=\lambda_1^k \left[ c_1v_1+\sum_{j\ge2}c_j \left(\frac{\lambda_j}{\lambda_1}\right)^k v_j \right]. After normalization, the terms with j\ge2 vanish geometrically at rate \left|\frac{\lambda_2}{\lambda_1}\right|^k. Thus the power method converges to the dominant eigenvector.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 6.11
Problem formulation.
Explain why inverse iteration targets eigenvalues close to the shift \sigma.
Method.
Use spectral decomposition, Rayleigh quotient identities, QR/inverse iteration, residual eigenvalue bounds, and perturbation theory.
Detailed solution and justification.
Use the eigenvalue relation Ax=\lambda x and analyze the method through the spectral decomposition of A. Residuals provide a posteriori information: r=Ax-\mu x. For Hermitian A, if \mu=\rho(x), then \operatorname{dist}(\mu,\sigma(A))\le \|r\|_2. For diagonalizable matrices, perturbation bounds involve the conditioning of the eigenvector matrix: A=V\Lambda V^{-1}, \qquad \kappa(V)=\|V\|\|V^{-1}\|.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 6.12
Problem formulation.
If A has eigenvalues 1,3,7, what are the eigenvalues of A-2I?
Method.
Use spectral decomposition, Rayleigh quotient identities, QR/inverse iteration, residual eigenvalue bounds, and perturbation theory.
Detailed solution and justification.
Use the eigenvalue relation Ax=\lambda x and analyze the method through the spectral decomposition of A. Residuals provide a posteriori information: r=Ax-\mu x. For Hermitian A, if \mu=\rho(x), then \operatorname{dist}(\mu,\sigma(A))\le \|r\|_2. For diagonalizable matrices, perturbation bounds involve the conditioning of the eigenvector matrix: A=V\Lambda V^{-1}, \qquad \kappa(V)=\|V\|\|V^{-1}\|.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 6.13
Problem formulation.
Given (\mu,x), define the eigenvalue residual and explain why it is useful.
Method.
Use spectral decomposition, Rayleigh quotient identities, QR/inverse iteration, residual eigenvalue bounds, and perturbation theory.
Detailed solution and justification.
Use the eigenvalue relation Ax=\lambda x and analyze the method through the spectral decomposition of A. Residuals provide a posteriori information: r=Ax-\mu x. For Hermitian A, if \mu=\rho(x), then \operatorname{dist}(\mu,\sigma(A))\le \|r\|_2. For diagonalizable matrices, perturbation bounds involve the conditioning of the eigenvector matrix: A=V\Lambda V^{-1}, \qquad \kappa(V)=\|V\|\|V^{-1}\|.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 6.14
Problem formulation.
Show that if A=QR, then RQ=Q^*AQ.
Method.
Use spectral decomposition, Rayleigh quotient identities, QR/inverse iteration, residual eigenvalue bounds, and perturbation theory.
Detailed solution and justification.
Use the eigenvalue relation Ax=\lambda x and analyze the method through the spectral decomposition of A. Residuals provide a posteriori information: r=Ax-\mu x. For Hermitian A, if \mu=\rho(x), then \operatorname{dist}(\mu,\sigma(A))\le \|r\|_2. For diagonalizable matrices, perturbation bounds involve the conditioning of the eigenvector matrix: A=V\Lambda V^{-1}, \qquad \kappa(V)=\|V\|\|V^{-1}\|.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 6.15
Problem formulation.
What entries of an upper Hessenberg matrix are necessarily zero?
Method.
Use spectral decomposition, Rayleigh quotient identities, QR/inverse iteration, residual eigenvalue bounds, and perturbation theory.
Detailed solution and justification.
Use the eigenvalue relation Ax=\lambda x and analyze the method through the spectral decomposition of A. Residuals provide a posteriori information: r=Ax-\mu x. For Hermitian A, if \mu=\rho(x), then \operatorname{dist}(\mu,\sigma(A))\le \|r\|_2. For diagonalizable matrices, perturbation bounds involve the conditioning of the eigenvector matrix: A=V\Lambda V^{-1}, \qquad \kappa(V)=\|V\|\|V^{-1}\|.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 6.16
Problem formulation.
What matrix property allows Arnoldi to reduce to the Lanczos process?
Method.
Use spectral decomposition, Rayleigh quotient identities, QR/inverse iteration, residual eigenvalue bounds, and perturbation theory.
Detailed solution and justification.
Use the eigenvalue relation Ax=\lambda x and analyze the method through the spectral decomposition of A. Residuals provide a posteriori information: r=Ax-\mu x. For Hermitian A, if \mu=\rho(x), then \operatorname{dist}(\mu,\sigma(A))\le \|r\|_2. For diagonalizable matrices, perturbation bounds involve the conditioning of the eigenvector matrix: A=V\Lambda V^{-1}, \qquad \kappa(V)=\|V\|\|V^{-1}\|.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 6.17
Problem formulation.
Define a Ritz value in a subspace method.
Method.
Use spectral decomposition, Rayleigh quotient identities, QR/inverse iteration, residual eigenvalue bounds, and perturbation theory.
Detailed solution and justification.
Use the eigenvalue relation Ax=\lambda x and analyze the method through the spectral decomposition of A. Residuals provide a posteriori information: r=Ax-\mu x. For Hermitian A, if \mu=\rho(x), then \operatorname{dist}(\mu,\sigma(A))\le \|r\|_2. For diagonalizable matrices, perturbation bounds involve the conditioning of the eigenvector matrix: A=V\Lambda V^{-1}, \qquad \kappa(V)=\|V\|\|V^{-1}\|.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 6.18
Problem formulation.
State the generalized eigenvalue problem.
Method.
Use spectral decomposition, Rayleigh quotient identities, QR/inverse iteration, residual eigenvalue bounds, and perturbation theory.
Detailed solution and justification.
Use the eigenvalue relation Ax=\lambda x and analyze the method through the spectral decomposition of A. Residuals provide a posteriori information: r=Ax-\mu x. For Hermitian A, if \mu=\rho(x), then \operatorname{dist}(\mu,\sigma(A))\le \|r\|_2. For diagonalizable matrices, perturbation bounds involve the conditioning of the eigenvector matrix: A=V\Lambda V^{-1}, \qquad \kappa(V)=\|V\|\|V^{-1}\|.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 6.19
Problem formulation.
How are singular values related to eigenvalues of A^*A?
Method.
Use spectral decomposition, Rayleigh quotient identities, QR/inverse iteration, residual eigenvalue bounds, and perturbation theory.
Detailed solution and justification.
Use the eigenvalue relation Ax=\lambda x and analyze the method through the spectral decomposition of A. Residuals provide a posteriori information: r=Ax-\mu x. For Hermitian A, if \mu=\rho(x), then \operatorname{dist}(\mu,\sigma(A))\le \|r\|_2. For diagonalizable matrices, perturbation bounds involve the conditioning of the eigenvector matrix: A=V\Lambda V^{-1}, \qquad \kappa(V)=\|V\|\|V^{-1}\|.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 6.20
Problem formulation.
Define a normal matrix and give two examples.
Method.
Use spectral decomposition, Rayleigh quotient identities, QR/inverse iteration, residual eigenvalue bounds, and perturbation theory.
Detailed solution and justification.
Use the eigenvalue relation Ax=\lambda x and analyze the method through the spectral decomposition of A. Residuals provide a posteriori information: r=Ax-\mu x. For Hermitian A, if \mu=\rho(x), then \operatorname{dist}(\mu,\sigma(A))\le \|r\|_2. For diagonalizable matrices, perturbation bounds involve the conditioning of the eigenvector matrix: A=V\Lambda V^{-1}, \qquad \kappa(V)=\|V\|\|V^{-1}\|.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 6.21
Problem formulation.
Prove the referenced result.
Method.
Use spectral decomposition, Rayleigh quotient identities, QR/inverse iteration, residual eigenvalue bounds, and perturbation theory.
Detailed solution and justification.
Use the eigenvalue relation Ax=\lambda x and analyze the method through the spectral decomposition of A. Residuals provide a posteriori information: r=Ax-\mu x. For Hermitian A, if \mu=\rho(x), then \operatorname{dist}(\mu,\sigma(A))\le \|r\|_2. For diagonalizable matrices, perturbation bounds involve the conditioning of the eigenvector matrix: A=V\Lambda V^{-1}, \qquad \kappa(V)=\|V\|\|V^{-1}\|.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 6.22
Problem formulation.
Prove the referenced result.
Method.
Use spectral decomposition, Rayleigh quotient identities, QR/inverse iteration, residual eigenvalue bounds, and perturbation theory.
Detailed solution and justification.
Use the eigenvalue relation Ax=\lambda x and analyze the method through the spectral decomposition of A. Residuals provide a posteriori information: r=Ax-\mu x. For Hermitian A, if \mu=\rho(x), then \operatorname{dist}(\mu,\sigma(A))\le \|r\|_2. For diagonalizable matrices, perturbation bounds involve the conditioning of the eigenvector matrix: A=V\Lambda V^{-1}, \qquad \kappa(V)=\|V\|\|V^{-1}\|.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 6.23
Problem formulation.
Prove the referenced result.
Method.
Use spectral decomposition, Rayleigh quotient identities, QR/inverse iteration, residual eigenvalue bounds, and perturbation theory.
Detailed solution and justification.
Use the eigenvalue relation Ax=\lambda x and analyze the method through the spectral decomposition of A. Residuals provide a posteriori information: r=Ax-\mu x. For Hermitian A, if \mu=\rho(x), then \operatorname{dist}(\mu,\sigma(A))\le \|r\|_2. For diagonalizable matrices, perturbation bounds involve the conditioning of the eigenvector matrix: A=V\Lambda V^{-1}, \qquad \kappa(V)=\|V\|\|V^{-1}\|.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 6.24
Problem formulation.
Prove the referenced result.
Method.
Use spectral decomposition, Rayleigh quotient identities, QR/inverse iteration, residual eigenvalue bounds, and perturbation theory.
Detailed solution and justification.
Use the eigenvalue relation Ax=\lambda x and analyze the method through the spectral decomposition of A. Residuals provide a posteriori information: r=Ax-\mu x. For Hermitian A, if \mu=\rho(x), then \operatorname{dist}(\mu,\sigma(A))\le \|r\|_2. For diagonalizable matrices, perturbation bounds involve the conditioning of the eigenvector matrix: A=V\Lambda V^{-1}, \qquad \kappa(V)=\|V\|\|V^{-1}\|.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 6.25
Problem formulation.
Prove the referenced result.
Method.
Use spectral decomposition, Rayleigh quotient identities, QR/inverse iteration, residual eigenvalue bounds, and perturbation theory.
Detailed solution and justification.
Use the eigenvalue relation Ax=\lambda x and analyze the method through the spectral decomposition of A. Residuals provide a posteriori information: r=Ax-\mu x. For Hermitian A, if \mu=\rho(x), then \operatorname{dist}(\mu,\sigma(A))\le \|r\|_2. For diagonalizable matrices, perturbation bounds involve the conditioning of the eigenvector matrix: A=V\Lambda V^{-1}, \qquad \kappa(V)=\|V\|\|V^{-1}\|.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 6.26
Problem formulation.
Prove the referenced result.
Method.
Use spectral decomposition, Rayleigh quotient identities, QR/inverse iteration, residual eigenvalue bounds, and perturbation theory.
Detailed solution and justification.
For A=A^T, the Rayleigh quotient is \rho(x)=\frac{x^TAx}{x^Tx}. If x is an eigenvector, Ax=\lambda x, then \rho(x)=\frac{x^T\lambda x}{x^Tx}=\lambda. The stationary points of \rho(x) on the unit sphere satisfy Ax=\lambda x, so eigenvectors are precisely stationary points of the Rayleigh quotient.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 6.27
Problem formulation.
Prove the referenced result.
Method.
Use spectral decomposition, Rayleigh quotient identities, QR/inverse iteration, residual eigenvalue bounds, and perturbation theory.
Detailed solution and justification.
For A=A^T, the Rayleigh quotient is \rho(x)=\frac{x^TAx}{x^Tx}. If x is an eigenvector, Ax=\lambda x, then \rho(x)=\frac{x^T\lambda x}{x^Tx}=\lambda. The stationary points of \rho(x) on the unit sphere satisfy Ax=\lambda x, so eigenvectors are precisely stationary points of the Rayleigh quotient.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 6.28
Problem formulation.
Prove the referenced result.
Method.
Use spectral decomposition, Rayleigh quotient identities, QR/inverse iteration, residual eigenvalue bounds, and perturbation theory.
Detailed solution and justification.
Let Ax=\lambda x, and choose i such that |x_i|=\max_j|x_j|. Then (\lambda-a_{ii})x_i=\sum_{j\ne i}a_{ij}x_j. Taking absolute values, |\lambda-a_{ii}||x_i| \le \sum_{j\ne i}|a_{ij}||x_j| \le \left(\sum_{j\ne i}|a_{ij}|\right)|x_i|. Since x_i\ne0, |\lambda-a_{ii}| \le \sum_{j\ne i}|a_{ij}|. Thus every eigenvalue lies in a Gershgorin disk.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 6.29
Problem formulation.
State and prove the refinement of Gershgorin’s theorem for connected components of the union of disks.
Method.
Use spectral decomposition, Rayleigh quotient identities, QR/inverse iteration, residual eigenvalue bounds, and perturbation theory.
Detailed solution and justification.
Let Ax=\lambda x, and choose i such that |x_i|=\max_j|x_j|. Then (\lambda-a_{ii})x_i=\sum_{j\ne i}a_{ij}x_j. Taking absolute values, |\lambda-a_{ii}||x_i| \le \sum_{j\ne i}|a_{ij}||x_j| \le \left(\sum_{j\ne i}|a_{ij}|\right)|x_i|. Since x_i\ne0, |\lambda-a_{ii}| \le \sum_{j\ne i}|a_{ij}|. Thus every eigenvalue lies in a Gershgorin disk.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 6.30
Problem formulation.
Prove the referenced result.
Method.
Use spectral decomposition, Rayleigh quotient identities, QR/inverse iteration, residual eigenvalue bounds, and perturbation theory.
Detailed solution and justification.
Assume A has eigenpairs (\lambda_j,v_j) with |\lambda_1|>|\lambda_2|\ge\cdots. Write x_0=\sum_j c_jv_j, \qquad c_1\ne0. Then A^kx_0=\lambda_1^k \left[ c_1v_1+\sum_{j\ge2}c_j \left(\frac{\lambda_j}{\lambda_1}\right)^k v_j \right]. After normalization, the terms with j\ge2 vanish geometrically at rate \left|\frac{\lambda_2}{\lambda_1}\right|^k. Thus the power method converges to the dominant eigenvector.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The order claim should be confirmed by a Taylor expansion or a log-log refinement table using a problem with a known exact solution.
Exercise 6.31
Problem formulation.
Give examples where the power method fails or stagnates.
Method.
Use spectral decomposition, Rayleigh quotient identities, QR/inverse iteration, residual eigenvalue bounds, and perturbation theory.
Detailed solution and justification.
Assume A has eigenpairs (\lambda_j,v_j) with |\lambda_1|>|\lambda_2|\ge\cdots. Write x_0=\sum_j c_jv_j, \qquad c_1\ne0. Then A^kx_0=\lambda_1^k \left[ c_1v_1+\sum_{j\ge2}c_j \left(\frac{\lambda_j}{\lambda_1}\right)^k v_j \right]. After normalization, the terms with j\ge2 vanish geometrically at rate \left|\frac{\lambda_2}{\lambda_1}\right|^k. Thus the power method converges to the dominant eigenvector.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 6.32
Problem formulation.
Prove the referenced result.
Method.
Use spectral decomposition, Rayleigh quotient identities, QR/inverse iteration, residual eigenvalue bounds, and perturbation theory.
Detailed solution and justification.
Use the eigenvalue relation Ax=\lambda x and analyze the method through the spectral decomposition of A. Residuals provide a posteriori information: r=Ax-\mu x. For Hermitian A, if \mu=\rho(x), then \operatorname{dist}(\mu,\sigma(A))\le \|r\|_2. For diagonalizable matrices, perturbation bounds involve the conditioning of the eigenvector matrix: A=V\Lambda V^{-1}, \qquad \kappa(V)=\|V\|\|V^{-1}\|.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 6.33
Problem formulation.
Derive Rayleigh quotient iteration from shifted inverse iteration.
Method.
Use spectral decomposition, Rayleigh quotient identities, QR/inverse iteration, residual eigenvalue bounds, and perturbation theory.
Detailed solution and justification.
For A=A^T, the Rayleigh quotient is \rho(x)=\frac{x^TAx}{x^Tx}. If x is an eigenvector, Ax=\lambda x, then \rho(x)=\frac{x^T\lambda x}{x^Tx}=\lambda. The stationary points of \rho(x) on the unit sphere satisfy Ax=\lambda x, so eigenvectors are precisely stationary points of the Rayleigh quotient.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 6.34
Problem formulation.
Prove the referenced result.
Method.
Use spectral decomposition, Rayleigh quotient identities, QR/inverse iteration, residual eigenvalue bounds, and perturbation theory.
Detailed solution and justification.
Use the eigenvalue relation Ax=\lambda x and analyze the method through the spectral decomposition of A. Residuals provide a posteriori information: r=Ax-\mu x. For Hermitian A, if \mu=\rho(x), then \operatorname{dist}(\mu,\sigma(A))\le \|r\|_2. For diagonalizable matrices, perturbation bounds involve the conditioning of the eigenvector matrix: A=V\Lambda V^{-1}, \qquad \kappa(V)=\|V\|\|V^{-1}\|.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 6.35
Problem formulation.
Show that a shifted QR step also produces a unitarily similar matrix.
Method.
Use spectral decomposition, Rayleigh quotient identities, QR/inverse iteration, residual eigenvalue bounds, and perturbation theory.
Detailed solution and justification.
Use the eigenvalue relation Ax=\lambda x and analyze the method through the spectral decomposition of A. Residuals provide a posteriori information: r=Ax-\mu x. For Hermitian A, if \mu=\rho(x), then \operatorname{dist}(\mu,\sigma(A))\le \|r\|_2. For diagonalizable matrices, perturbation bounds involve the conditioning of the eigenvector matrix: A=V\Lambda V^{-1}, \qquad \kappa(V)=\|V\|\|V^{-1}\|.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 6.36
Problem formulation.
Show that QR iteration preserves upper Hessenberg form.
Method.
Use spectral decomposition, Rayleigh quotient identities, QR/inverse iteration, residual eigenvalue bounds, and perturbation theory.
Detailed solution and justification.
Use the eigenvalue relation Ax=\lambda x and analyze the method through the spectral decomposition of A. Residuals provide a posteriori information: r=Ax-\mu x. For Hermitian A, if \mu=\rho(x), then \operatorname{dist}(\mu,\sigma(A))\le \|r\|_2. For diagonalizable matrices, perturbation bounds involve the conditioning of the eigenvector matrix: A=V\Lambda V^{-1}, \qquad \kappa(V)=\|V\|\|V^{-1}\|.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 6.37
Problem formulation.
Derive the plane rotation that zeros the (p,q) entry of a real symmetric matrix.
Method.
Use spectral decomposition, Rayleigh quotient identities, QR/inverse iteration, residual eigenvalue bounds, and perturbation theory.
Detailed solution and justification.
Use the eigenvalue relation Ax=\lambda x and analyze the method through the spectral decomposition of A. Residuals provide a posteriori information: r=Ax-\mu x. For Hermitian A, if \mu=\rho(x), then \operatorname{dist}(\mu,\sigma(A))\le \|r\|_2. For diagonalizable matrices, perturbation bounds involve the conditioning of the eigenvector matrix: A=V\Lambda V^{-1}, \qquad \kappa(V)=\|V\|\|V^{-1}\|.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 6.38
Problem formulation.
Derive the Arnoldi relation AV_k=V_kH_k+h_{k+1,k}v_{k+1}e_k^T.
Method.
Use spectral decomposition, Rayleigh quotient identities, QR/inverse iteration, residual eigenvalue bounds, and perturbation theory.
Detailed solution and justification.
Use the eigenvalue relation Ax=\lambda x and analyze the method through the spectral decomposition of A. Residuals provide a posteriori information: r=Ax-\mu x. For Hermitian A, if \mu=\rho(x), then \operatorname{dist}(\mu,\sigma(A))\le \|r\|_2. For diagonalizable matrices, perturbation bounds involve the conditioning of the eigenvector matrix: A=V\Lambda V^{-1}, \qquad \kappa(V)=\|V\|\|V^{-1}\|.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 6.39
Problem formulation.
Prove the referenced result.
Method.
Use spectral decomposition, Rayleigh quotient identities, QR/inverse iteration, residual eigenvalue bounds, and perturbation theory.
Detailed solution and justification.
Use the eigenvalue relation Ax=\lambda x and analyze the method through the spectral decomposition of A. Residuals provide a posteriori information: r=Ax-\mu x. For Hermitian A, if \mu=\rho(x), then \operatorname{dist}(\mu,\sigma(A))\le \|r\|_2. For diagonalizable matrices, perturbation bounds involve the conditioning of the eigenvector matrix: A=V\Lambda V^{-1}, \qquad \kappa(V)=\|V\|\|V^{-1}\|.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 6.40
Problem formulation.
Derive the Lanczos three-term recurrence from Arnoldi when A=A^*.
Method.
Use spectral decomposition, Rayleigh quotient identities, QR/inverse iteration, residual eigenvalue bounds, and perturbation theory.
Detailed solution and justification.
Use the eigenvalue relation Ax=\lambda x and analyze the method through the spectral decomposition of A. Residuals provide a posteriori information: r=Ax-\mu x. For Hermitian A, if \mu=\rho(x), then \operatorname{dist}(\mu,\sigma(A))\le \|r\|_2. For diagonalizable matrices, perturbation bounds involve the conditioning of the eigenvector matrix: A=V\Lambda V^{-1}, \qquad \kappa(V)=\|V\|\|V^{-1}\|.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 6.41
Problem formulation.
Prove the referenced result in full detail.
Method.
Use spectral decomposition, Rayleigh quotient identities, QR/inverse iteration, residual eigenvalue bounds, and perturbation theory.
Detailed solution and justification.
Use the eigenvalue relation Ax=\lambda x and analyze the method through the spectral decomposition of A. Residuals provide a posteriori information: r=Ax-\mu x. For Hermitian A, if \mu=\rho(x), then \operatorname{dist}(\mu,\sigma(A))\le \|r\|_2. For diagonalizable matrices, perturbation bounds involve the conditioning of the eigenvector matrix: A=V\Lambda V^{-1}, \qquad \kappa(V)=\|V\|\|V^{-1}\|.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 6.42
Problem formulation.
State and prove both min-max and max-min forms of the Courant–Fischer theorem.
Method.
Use spectral decomposition, Rayleigh quotient identities, QR/inverse iteration, residual eigenvalue bounds, and perturbation theory.
Detailed solution and justification.
Use the eigenvalue relation Ax=\lambda x and analyze the method through the spectral decomposition of A. Residuals provide a posteriori information: r=Ax-\mu x. For Hermitian A, if \mu=\rho(x), then \operatorname{dist}(\mu,\sigma(A))\le \|r\|_2. For diagonalizable matrices, perturbation bounds involve the conditioning of the eigenvector matrix: A=V\Lambda V^{-1}, \qquad \kappa(V)=\|V\|\|V^{-1}\|.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 6.43
Problem formulation.
Prove the Cauchy interlacing theorem for eigenvalues of Hermitian matrices.
Method.
Use spectral decomposition, Rayleigh quotient identities, QR/inverse iteration, residual eigenvalue bounds, and perturbation theory.
Detailed solution and justification.
Use the eigenvalue relation Ax=\lambda x and analyze the method through the spectral decomposition of A. Residuals provide a posteriori information: r=Ax-\mu x. For Hermitian A, if \mu=\rho(x), then \operatorname{dist}(\mu,\sigma(A))\le \|r\|_2. For diagonalizable matrices, perturbation bounds involve the conditioning of the eigenvector matrix: A=V\Lambda V^{-1}, \qquad \kappa(V)=\|V\|\|V^{-1}\|.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 6.44
Problem formulation.
State and prove Weyl’s eigenvalue perturbation inequality for Hermitian matrices.
Method.
Use spectral decomposition, Rayleigh quotient identities, QR/inverse iteration, residual eigenvalue bounds, and perturbation theory.
Detailed solution and justification.
Use the eigenvalue relation Ax=\lambda x and analyze the method through the spectral decomposition of A. Residuals provide a posteriori information: r=Ax-\mu x. For Hermitian A, if \mu=\rho(x), then \operatorname{dist}(\mu,\sigma(A))\le \|r\|_2. For diagonalizable matrices, perturbation bounds involve the conditioning of the eigenvector matrix: A=V\Lambda V^{-1}, \qquad \kappa(V)=\|V\|\|V^{-1}\|.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 6.45
Problem formulation.
State the Davis–Kahan sin-theta theorem and explain its meaning for invariant subspace perturbation.
Method.
Use spectral decomposition, Rayleigh quotient identities, QR/inverse iteration, residual eigenvalue bounds, and perturbation theory.
Detailed solution and justification.
Use the eigenvalue relation Ax=\lambda x and analyze the method through the spectral decomposition of A. Residuals provide a posteriori information: r=Ax-\mu x. For Hermitian A, if \mu=\rho(x), then \operatorname{dist}(\mu,\sigma(A))\le \|r\|_2. For diagonalizable matrices, perturbation bounds involve the conditioning of the eigenvector matrix: A=V\Lambda V^{-1}, \qquad \kappa(V)=\|V\|\|V^{-1}\|.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 6.46
Problem formulation.
Prove the referenced result.
Method.
Use spectral decomposition, Rayleigh quotient identities, QR/inverse iteration, residual eigenvalue bounds, and perturbation theory.
Detailed solution and justification.
Use the eigenvalue relation Ax=\lambda x and analyze the method through the spectral decomposition of A. Residuals provide a posteriori information: r=Ax-\mu x. For Hermitian A, if \mu=\rho(x), then \operatorname{dist}(\mu,\sigma(A))\le \|r\|_2. For diagonalizable matrices, perturbation bounds involve the conditioning of the eigenvector matrix: A=V\Lambda V^{-1}, \qquad \kappa(V)=\|V\|\|V^{-1}\|.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 6.47
Problem formulation.
For Hermitian A, derive an angle bound between an approximate eigenvector and an exact eigenspace using a spectral gap.
Method.
Use spectral decomposition, Rayleigh quotient identities, QR/inverse iteration, residual eigenvalue bounds, and perturbation theory.
Detailed solution and justification.
Use the eigenvalue relation Ax=\lambda x and analyze the method through the spectral decomposition of A. Residuals provide a posteriori information: r=Ax-\mu x. For Hermitian A, if \mu=\rho(x), then \operatorname{dist}(\mu,\sigma(A))\le \|r\|_2. For diagonalizable matrices, perturbation bounds involve the conditioning of the eigenvector matrix: A=V\Lambda V^{-1}, \qquad \kappa(V)=\|V\|\|V^{-1}\|.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 6.48
Problem formulation.
Prove the referenced result.
Method.
Use spectral decomposition, Rayleigh quotient identities, QR/inverse iteration, residual eigenvalue bounds, and perturbation theory.
Detailed solution and justification.
Use the eigenvalue relation Ax=\lambda x and analyze the method through the spectral decomposition of A. Residuals provide a posteriori information: r=Ax-\mu x. For Hermitian A, if \mu=\rho(x), then \operatorname{dist}(\mu,\sigma(A))\le \|r\|_2. For diagonalizable matrices, perturbation bounds involve the conditioning of the eigenvector matrix: A=V\Lambda V^{-1}, \qquad \kappa(V)=\|V\|\|V^{-1}\|.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The order claim should be confirmed by a Taylor expansion or a log-log refinement table using a problem with a known exact solution.
Exercise 6.49
Problem formulation.
Prove the referenced result.
Method.
Use spectral decomposition, Rayleigh quotient identities, QR/inverse iteration, residual eigenvalue bounds, and perturbation theory.
Detailed solution and justification.
Use the eigenvalue relation Ax=\lambda x and analyze the method through the spectral decomposition of A. Residuals provide a posteriori information: r=Ax-\mu x. For Hermitian A, if \mu=\rho(x), then \operatorname{dist}(\mu,\sigma(A))\le \|r\|_2. For diagonalizable matrices, perturbation bounds involve the conditioning of the eigenvector matrix: A=V\Lambda V^{-1}, \qquad \kappa(V)=\|V\|\|V^{-1}\|.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 6.50
Problem formulation.
Prove the equivalence between pseudospectra defined by resolvent norm and by eigenvalues of perturbed matrices.
Method.
Use spectral decomposition, Rayleigh quotient identities, QR/inverse iteration, residual eigenvalue bounds, and perturbation theory.
Detailed solution and justification.
Use the eigenvalue relation Ax=\lambda x and analyze the method through the spectral decomposition of A. Residuals provide a posteriori information: r=Ax-\mu x. For Hermitian A, if \mu=\rho(x), then \operatorname{dist}(\mu,\sigma(A))\le \|r\|_2. For diagonalizable matrices, perturbation bounds involve the conditioning of the eigenvector matrix: A=V\Lambda V^{-1}, \qquad \kappa(V)=\|V\|\|V^{-1}\|.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 6.51
Problem formulation.
Construct a non-normal matrix whose eigenvalues are highly sensitive to tiny perturbations.
Method.
Use spectral decomposition, Rayleigh quotient identities, QR/inverse iteration, residual eigenvalue bounds, and perturbation theory.
Detailed solution and justification.
Use the eigenvalue relation Ax=\lambda x and analyze the method through the spectral decomposition of A. Residuals provide a posteriori information: r=Ax-\mu x. For Hermitian A, if \mu=\rho(x), then \operatorname{dist}(\mu,\sigma(A))\le \|r\|_2. For diagonalizable matrices, perturbation bounds involve the conditioning of the eigenvector matrix: A=V\Lambda V^{-1}, \qquad \kappa(V)=\|V\|\|V^{-1}\|.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 6.52
Problem formulation.
Show that for Hermitian matrices, the Rayleigh quotient eigenvalue error is second order in the eigenvector angle.
Method.
Use spectral decomposition, Rayleigh quotient identities, QR/inverse iteration, residual eigenvalue bounds, and perturbation theory.
Detailed solution and justification.
For A=A^T, the Rayleigh quotient is \rho(x)=\frac{x^TAx}{x^Tx}. If x is an eigenvector, Ax=\lambda x, then \rho(x)=\frac{x^T\lambda x}{x^Tx}=\lambda. The stationary points of \rho(x) on the unit sphere satisfy Ax=\lambda x, so eigenvectors are precisely stationary points of the Rayleigh quotient.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The order claim should be confirmed by a Taylor expansion or a log-log refinement table using a problem with a known exact solution.
Exercise 6.53
Problem formulation.
Prove the referenced result more rigorously.
Method.
Use spectral decomposition, Rayleigh quotient identities, QR/inverse iteration, residual eigenvalue bounds, and perturbation theory.
Detailed solution and justification.
Use the eigenvalue relation Ax=\lambda x and analyze the method through the spectral decomposition of A. Residuals provide a posteriori information: r=Ax-\mu x. For Hermitian A, if \mu=\rho(x), then \operatorname{dist}(\mu,\sigma(A))\le \|r\|_2. For diagonalizable matrices, perturbation bounds involve the conditioning of the eigenvector matrix: A=V\Lambda V^{-1}, \qquad \kappa(V)=\|V\|\|V^{-1}\|.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The order claim should be confirmed by a Taylor expansion or a log-log refinement table using a problem with a known exact solution.
Exercise 6.54
Problem formulation.
Analyze convergence of orthogonal iteration to a dominant invariant subspace.
Method.
Use spectral decomposition, Rayleigh quotient identities, QR/inverse iteration, residual eigenvalue bounds, and perturbation theory.
Detailed solution and justification.
Use the eigenvalue relation Ax=\lambda x and analyze the method through the spectral decomposition of A. Residuals provide a posteriori information: r=Ax-\mu x. For Hermitian A, if \mu=\rho(x), then \operatorname{dist}(\mu,\sigma(A))\le \|r\|_2. For diagonalizable matrices, perturbation bounds involve the conditioning of the eigenvector matrix: A=V\Lambda V^{-1}, \qquad \kappa(V)=\|V\|\|V^{-1}\|.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The order claim should be confirmed by a Taylor expansion or a log-log refinement table using a problem with a known exact solution.
Exercise 6.55
Problem formulation.
Show the relationship between QR iteration and orthogonal iteration.
Method.
Use spectral decomposition, Rayleigh quotient identities, QR/inverse iteration, residual eigenvalue bounds, and perturbation theory.
Detailed solution and justification.
Use the eigenvalue relation Ax=\lambda x and analyze the method through the spectral decomposition of A. Residuals provide a posteriori information: r=Ax-\mu x. For Hermitian A, if \mu=\rho(x), then \operatorname{dist}(\mu,\sigma(A))\le \|r\|_2. For diagonalizable matrices, perturbation bounds involve the conditioning of the eigenvector matrix: A=V\Lambda V^{-1}, \qquad \kappa(V)=\|V\|\|V^{-1}\|.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 6.56
Problem formulation.
Derive the operation count for Householder reduction to Hessenberg form.
Method.
Use spectral decomposition, Rayleigh quotient identities, QR/inverse iteration, residual eigenvalue bounds, and perturbation theory.
Detailed solution and justification.
Use the eigenvalue relation Ax=\lambda x and analyze the method through the spectral decomposition of A. Residuals provide a posteriori information: r=Ax-\mu x. For Hermitian A, if \mu=\rho(x), then \operatorname{dist}(\mu,\sigma(A))\le \|r\|_2. For diagonalizable matrices, perturbation bounds involve the conditioning of the eigenvector matrix: A=V\Lambda V^{-1}, \qquad \kappa(V)=\|V\|\|V^{-1}\|.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 6.57
Problem formulation.
Derive Householder tridiagonalization for real symmetric matrices.
Method.
Use spectral decomposition, Rayleigh quotient identities, QR/inverse iteration, residual eigenvalue bounds, and perturbation theory.
Detailed solution and justification.
Use the eigenvalue relation Ax=\lambda x and analyze the method through the spectral decomposition of A. Residuals provide a posteriori information: r=Ax-\mu x. For Hermitian A, if \mu=\rho(x), then \operatorname{dist}(\mu,\sigma(A))\le \|r\|_2. For diagonalizable matrices, perturbation bounds involve the conditioning of the eigenvector matrix: A=V\Lambda V^{-1}, \qquad \kappa(V)=\|V\|\|V^{-1}\|.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 6.58
Problem formulation.
Derive the Wilkinson shift for a symmetric tridiagonal QR step.
Method.
Use spectral decomposition, Rayleigh quotient identities, QR/inverse iteration, residual eigenvalue bounds, and perturbation theory.
Detailed solution and justification.
Use the eigenvalue relation Ax=\lambda x and analyze the method through the spectral decomposition of A. Residuals provide a posteriori information: r=Ax-\mu x. For Hermitian A, if \mu=\rho(x), then \operatorname{dist}(\mu,\sigma(A))\le \|r\|_2. For diagonalizable matrices, perturbation bounds involve the conditioning of the eigenvector matrix: A=V\Lambda V^{-1}, \qquad \kappa(V)=\|V\|\|V^{-1}\|.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 6.59
Problem formulation.
Explain deflation in the QR algorithm and derive a practical deflation criterion.
Method.
Use spectral decomposition, Rayleigh quotient identities, QR/inverse iteration, residual eigenvalue bounds, and perturbation theory.
Detailed solution and justification.
Use the eigenvalue relation Ax=\lambda x and analyze the method through the spectral decomposition of A. Residuals provide a posteriori information: r=Ax-\mu x. For Hermitian A, if \mu=\rho(x), then \operatorname{dist}(\mu,\sigma(A))\le \|r\|_2. For diagonalizable matrices, perturbation bounds involve the conditioning of the eigenvector matrix: A=V\Lambda V^{-1}, \qquad \kappa(V)=\|V\|\|V^{-1}\|.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 6.60
Problem formulation.
Describe the implicit Francis double-shift QR step for real nonsymmetric matrices.
Method.
Use spectral decomposition, Rayleigh quotient identities, QR/inverse iteration, residual eigenvalue bounds, and perturbation theory.
Detailed solution and justification.
Use the eigenvalue relation Ax=\lambda x and analyze the method through the spectral decomposition of A. Residuals provide a posteriori information: r=Ax-\mu x. For Hermitian A, if \mu=\rho(x), then \operatorname{dist}(\mu,\sigma(A))\le \|r\|_2. For diagonalizable matrices, perturbation bounds involve the conditioning of the eigenvector matrix: A=V\Lambda V^{-1}, \qquad \kappa(V)=\|V\|\|V^{-1}\|.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 6.61
Problem formulation.
Explain how loss of orthogonality in Lanczos can produce ghost eigenvalues.
Method.
Use spectral decomposition, Rayleigh quotient identities, QR/inverse iteration, residual eigenvalue bounds, and perturbation theory.
Detailed solution and justification.
Use the eigenvalue relation Ax=\lambda x and analyze the method through the spectral decomposition of A. Residuals provide a posteriori information: r=Ax-\mu x. For Hermitian A, if \mu=\rho(x), then \operatorname{dist}(\mu,\sigma(A))\le \|r\|_2. For diagonalizable matrices, perturbation bounds involve the conditioning of the eigenvector matrix: A=V\Lambda V^{-1}, \qquad \kappa(V)=\|V\|\|V^{-1}\|.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 6.62
Problem formulation.
Describe selective reorthogonalization in Lanczos methods.
Method.
Use spectral decomposition, Rayleigh quotient identities, QR/inverse iteration, residual eigenvalue bounds, and perturbation theory.
Detailed solution and justification.
Use the eigenvalue relation Ax=\lambda x and analyze the method through the spectral decomposition of A. Residuals provide a posteriori information: r=Ax-\mu x. For Hermitian A, if \mu=\rho(x), then \operatorname{dist}(\mu,\sigma(A))\le \|r\|_2. For diagonalizable matrices, perturbation bounds involve the conditioning of the eigenvector matrix: A=V\Lambda V^{-1}, \qquad \kappa(V)=\|V\|\|V^{-1}\|.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 6.63
Problem formulation.
Explain the need for restarting in Arnoldi eigenvalue computations.
Method.
Use spectral decomposition, Rayleigh quotient identities, QR/inverse iteration, residual eigenvalue bounds, and perturbation theory.
Detailed solution and justification.
Use the eigenvalue relation Ax=\lambda x and analyze the method through the spectral decomposition of A. Residuals provide a posteriori information: r=Ax-\mu x. For Hermitian A, if \mu=\rho(x), then \operatorname{dist}(\mu,\sigma(A))\le \|r\|_2. For diagonalizable matrices, perturbation bounds involve the conditioning of the eigenvector matrix: A=V\Lambda V^{-1}, \qquad \kappa(V)=\|V\|\|V^{-1}\|.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 6.64
Problem formulation.
Study the implicitly restarted Arnoldi method and its relation to shifted QR.
Method.
Use spectral decomposition, Rayleigh quotient identities, QR/inverse iteration, residual eigenvalue bounds, and perturbation theory.
Detailed solution and justification.
Use the eigenvalue relation Ax=\lambda x and analyze the method through the spectral decomposition of A. Residuals provide a posteriori information: r=Ax-\mu x. For Hermitian A, if \mu=\rho(x), then \operatorname{dist}(\mu,\sigma(A))\le \|r\|_2. For diagonalizable matrices, perturbation bounds involve the conditioning of the eigenvector matrix: A=V\Lambda V^{-1}, \qquad \kappa(V)=\|V\|\|V^{-1}\|.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 6.65
Problem formulation.
Analyze shift-and-invert Arnoldi for computing interior eigenvalues.
Method.
Use spectral decomposition, Rayleigh quotient identities, QR/inverse iteration, residual eigenvalue bounds, and perturbation theory.
Detailed solution and justification.
Use the eigenvalue relation Ax=\lambda x and analyze the method through the spectral decomposition of A. Residuals provide a posteriori information: r=Ax-\mu x. For Hermitian A, if \mu=\rho(x), then \operatorname{dist}(\mu,\sigma(A))\le \|r\|_2. For diagonalizable matrices, perturbation bounds involve the conditioning of the eigenvector matrix: A=V\Lambda V^{-1}, \qquad \kappa(V)=\|V\|\|V^{-1}\|.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 6.66
Problem formulation.
Study the backward stability of the shifted QR algorithm and explain the role of unitary transformations.
Method.
Use spectral decomposition, Rayleigh quotient identities, QR/inverse iteration, residual eigenvalue bounds, and perturbation theory.
Detailed solution and justification.
Use the eigenvalue relation Ax=\lambda x and analyze the method through the spectral decomposition of A. Residuals provide a posteriori information: r=Ax-\mu x. For Hermitian A, if \mu=\rho(x), then \operatorname{dist}(\mu,\sigma(A))\le \|r\|_2. For diagonalizable matrices, perturbation bounds involve the conditioning of the eigenvector matrix: A=V\Lambda V^{-1}, \qquad \kappa(V)=\|V\|\|V^{-1}\|.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
Always test the result on the scalar model equation or Fourier mode and verify the amplification factor satisfies the stated stability bound.
Exercise 6.67
Problem formulation.
Investigate aggressive early deflation in modern QR eigensolvers.
Method.
Use spectral decomposition, Rayleigh quotient identities, QR/inverse iteration, residual eigenvalue bounds, and perturbation theory.
Detailed solution and justification.
Use the eigenvalue relation Ax=\lambda x and analyze the method through the spectral decomposition of A. Residuals provide a posteriori information: r=Ax-\mu x. For Hermitian A, if \mu=\rho(x), then \operatorname{dist}(\mu,\sigma(A))\le \|r\|_2. For diagonalizable matrices, perturbation bounds involve the conditioning of the eigenvector matrix: A=V\Lambda V^{-1}, \qquad \kappa(V)=\|V\|\|V^{-1}\|.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 6.68
Problem formulation.
Study divide-and-conquer methods for symmetric tridiagonal eigenvalue problems.
Method.
Use spectral decomposition, Rayleigh quotient identities, QR/inverse iteration, residual eigenvalue bounds, and perturbation theory.
Detailed solution and justification.
Use the eigenvalue relation Ax=\lambda x and analyze the method through the spectral decomposition of A. Residuals provide a posteriori information: r=Ax-\mu x. For Hermitian A, if \mu=\rho(x), then \operatorname{dist}(\mu,\sigma(A))\le \|r\|_2. For diagonalizable matrices, perturbation bounds involve the conditioning of the eigenvector matrix: A=V\Lambda V^{-1}, \qquad \kappa(V)=\|V\|\|V^{-1}\|.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 6.69
Problem formulation.
Study the MRRR algorithm for symmetric tridiagonal eigenproblems and discuss its accuracy tradeoffs.
Method.
Use spectral decomposition, Rayleigh quotient identities, QR/inverse iteration, residual eigenvalue bounds, and perturbation theory.
Detailed solution and justification.
Use the eigenvalue relation Ax=\lambda x and analyze the method through the spectral decomposition of A. Residuals provide a posteriori information: r=Ax-\mu x. For Hermitian A, if \mu=\rho(x), then \operatorname{dist}(\mu,\sigma(A))\le \|r\|_2. For diagonalizable matrices, perturbation bounds involve the conditioning of the eigenvector matrix: A=V\Lambda V^{-1}, \qquad \kappa(V)=\|V\|\|V^{-1}\|.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 6.70
Problem formulation.
Analyze why Jacobi-type methods can deliver high relative accuracy for certain symmetric eigenvalue problems.
Method.
Use spectral decomposition, Rayleigh quotient identities, QR/inverse iteration, residual eigenvalue bounds, and perturbation theory.
Detailed solution and justification.
Use the eigenvalue relation Ax=\lambda x and analyze the method through the spectral decomposition of A. Residuals provide a posteriori information: r=Ax-\mu x. For Hermitian A, if \mu=\rho(x), then \operatorname{dist}(\mu,\sigma(A))\le \|r\|_2. For diagonalizable matrices, perturbation bounds involve the conditioning of the eigenvector matrix: A=V\Lambda V^{-1}, \qquad \kappa(V)=\|V\|\|V^{-1}\|.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 6.71
Problem formulation.
Design a Chebyshev polynomial filter for separating eigenvalues in a target interval.
Method.
Use spectral decomposition, Rayleigh quotient identities, QR/inverse iteration, residual eigenvalue bounds, and perturbation theory.
Detailed solution and justification.
Use the eigenvalue relation Ax=\lambda x and analyze the method through the spectral decomposition of A. Residuals provide a posteriori information: r=Ax-\mu x. For Hermitian A, if \mu=\rho(x), then \operatorname{dist}(\mu,\sigma(A))\le \|r\|_2. For diagonalizable matrices, perturbation bounds involve the conditioning of the eigenvector matrix: A=V\Lambda V^{-1}, \qquad \kappa(V)=\|V\|\|V^{-1}\|.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 6.72
Problem formulation.
Study rational Krylov subspaces and compare them with polynomial Krylov subspaces.
Method.
Use spectral decomposition, Rayleigh quotient identities, QR/inverse iteration, residual eigenvalue bounds, and perturbation theory.
Detailed solution and justification.
Use the eigenvalue relation Ax=\lambda x and analyze the method through the spectral decomposition of A. Residuals provide a posteriori information: r=Ax-\mu x. For Hermitian A, if \mu=\rho(x), then \operatorname{dist}(\mu,\sigma(A))\le \|r\|_2. For diagonalizable matrices, perturbation bounds involve the conditioning of the eigenvector matrix: A=V\Lambda V^{-1}, \qquad \kappa(V)=\|V\|\|V^{-1}\|.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 6.73
Problem formulation.
Derive the Jacobi–Davidson correction equation and explain how it targets selected eigenpairs.
Method.
Use spectral decomposition, Rayleigh quotient identities, QR/inverse iteration, residual eigenvalue bounds, and perturbation theory.
Detailed solution and justification.
Use the eigenvalue relation Ax=\lambda x and analyze the method through the spectral decomposition of A. Residuals provide a posteriori information: r=Ax-\mu x. For Hermitian A, if \mu=\rho(x), then \operatorname{dist}(\mu,\sigma(A))\le \|r\|_2. For diagonalizable matrices, perturbation bounds involve the conditioning of the eigenvector matrix: A=V\Lambda V^{-1}, \qquad \kappa(V)=\|V\|\|V^{-1}\|.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 6.74
Problem formulation.
Study the locally optimal block preconditioned conjugate-gradient method for Hermitian eigenproblems.
Method.
Use spectral decomposition, Rayleigh quotient identities, QR/inverse iteration, residual eigenvalue bounds, and perturbation theory.
Detailed solution and justification.
Use the eigenvalue relation Ax=\lambda x and analyze the method through the spectral decomposition of A. Residuals provide a posteriori information: r=Ax-\mu x. For Hermitian A, if \mu=\rho(x), then \operatorname{dist}(\mu,\sigma(A))\le \|r\|_2. For diagonalizable matrices, perturbation bounds involve the conditioning of the eigenvector matrix: A=V\Lambda V^{-1}, \qquad \kappa(V)=\|V\|\|V^{-1}\|.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
Distinguish forward error from backward error; a small residual does not imply a small forward error when the problem is ill-conditioned.
Exercise 6.75
Problem formulation.
Explain the FEAST algorithm as a contour-integration spectral projector method.
Method.
Use spectral decomposition, Rayleigh quotient identities, QR/inverse iteration, residual eigenvalue bounds, and perturbation theory.
Detailed solution and justification.
Use the eigenvalue relation Ax=\lambda x and analyze the method through the spectral decomposition of A. Residuals provide a posteriori information: r=Ax-\mu x. For Hermitian A, if \mu=\rho(x), then \operatorname{dist}(\mu,\sigma(A))\le \|r\|_2. For diagonalizable matrices, perturbation bounds involve the conditioning of the eigenvector matrix: A=V\Lambda V^{-1}, \qquad \kappa(V)=\|V\|\|V^{-1}\|.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 6.76
Problem formulation.
Analyze the problem Ax=\lambda Bx, \qquad A=A^*, \qquad B=B^*>0. Derive a reduction to a standard Hermitian eigenvalue problem.
Method.
Use spectral decomposition, Rayleigh quotient identities, QR/inverse iteration, residual eigenvalue bounds, and perturbation theory.
Detailed solution and justification.
Use the eigenvalue relation Ax=\lambda x and analyze the method through the spectral decomposition of A. Residuals provide a posteriori information: r=Ax-\mu x. For Hermitian A, if \mu=\rho(x), then \operatorname{dist}(\mu,\sigma(A))\le \|r\|_2. For diagonalizable matrices, perturbation bounds involve the conditioning of the eigenvector matrix: A=V\Lambda V^{-1}, \qquad \kappa(V)=\|V\|\|V^{-1}\|.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 6.77
Problem formulation.
Study the QZ algorithm for generalized eigenvalue problems and compare it with QR.
Method.
Use spectral decomposition, Rayleigh quotient identities, QR/inverse iteration, residual eigenvalue bounds, and perturbation theory.
Detailed solution and justification.
Use the eigenvalue relation Ax=\lambda x and analyze the method through the spectral decomposition of A. Residuals provide a posteriori information: r=Ax-\mu x. For Hermitian A, if \mu=\rho(x), then \operatorname{dist}(\mu,\sigma(A))\le \|r\|_2. For diagonalizable matrices, perturbation bounds involve the conditioning of the eigenvector matrix: A=V\Lambda V^{-1}, \qquad \kappa(V)=\|V\|\|V^{-1}\|.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 6.78
Problem formulation.
Study polynomial eigenvalue problems and linearization strategies.
Method.
Use spectral decomposition, Rayleigh quotient identities, QR/inverse iteration, residual eigenvalue bounds, and perturbation theory.
Detailed solution and justification.
Use the eigenvalue relation Ax=\lambda x and analyze the method through the spectral decomposition of A. Residuals provide a posteriori information: r=Ax-\mu x. For Hermitian A, if \mu=\rho(x), then \operatorname{dist}(\mu,\sigma(A))\le \|r\|_2. For diagonalizable matrices, perturbation bounds involve the conditioning of the eigenvector matrix: A=V\Lambda V^{-1}, \qquad \kappa(V)=\|V\|\|V^{-1}\|.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 6.79
Problem formulation.
Investigate nonlinear eigenvalue problems T(\lambda)x=0 and discuss Newton-type methods for them.
Method.
Use spectral decomposition, Rayleigh quotient identities, QR/inverse iteration, residual eigenvalue bounds, and perturbation theory.
Detailed solution and justification.
Use the eigenvalue relation Ax=\lambda x and analyze the method through the spectral decomposition of A. Residuals provide a posteriori information: r=Ax-\mu x. For Hermitian A, if \mu=\rho(x), then \operatorname{dist}(\mu,\sigma(A))\le \|r\|_2. For diagonalizable matrices, perturbation bounds involve the conditioning of the eigenvector matrix: A=V\Lambda V^{-1}, \qquad \kappa(V)=\|V\|\|V^{-1}\|.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
Verify the stationarity residual, feasibility residual, and descent or curvature condition, not only the final numerical value.
Exercise 6.80
Problem formulation.
Design a numerical method for plotting pseudospectra using resolvent norms.
Method.
Use spectral decomposition, Rayleigh quotient identities, QR/inverse iteration, residual eigenvalue bounds, and perturbation theory.
Detailed solution and justification.
Use the eigenvalue relation Ax=\lambda x and analyze the method through the spectral decomposition of A. Residuals provide a posteriori information: r=Ax-\mu x. For Hermitian A, if \mu=\rho(x), then \operatorname{dist}(\mu,\sigma(A))\le \|r\|_2. For diagonalizable matrices, perturbation bounds involve the conditioning of the eigenvector matrix: A=V\Lambda V^{-1}, \qquad \kappa(V)=\|V\|\|V^{-1}\|.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 6.81
Problem formulation.
Analyze eigenvalue computations for large sparse matrices arising from finite difference or finite element discretizations of elliptic operators.
Method.
Use spectral decomposition, Rayleigh quotient identities, QR/inverse iteration, residual eigenvalue bounds, and perturbation theory.
Detailed solution and justification.
Use the eigenvalue relation Ax=\lambda x and analyze the method through the spectral decomposition of A. Residuals provide a posteriori information: r=Ax-\mu x. For Hermitian A, if \mu=\rho(x), then \operatorname{dist}(\mu,\sigma(A))\le \|r\|_2. For diagonalizable matrices, perturbation bounds involve the conditioning of the eigenvector matrix: A=V\Lambda V^{-1}, \qquad \kappa(V)=\|V\|\|V^{-1}\|.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 6.82
Problem formulation.
Study randomized subspace iteration for approximating dominant eigenspaces.
Method.
Use spectral decomposition, Rayleigh quotient identities, QR/inverse iteration, residual eigenvalue bounds, and perturbation theory.
Detailed solution and justification.
Use the eigenvalue relation Ax=\lambda x and analyze the method through the spectral decomposition of A. Residuals provide a posteriori information: r=Ax-\mu x. For Hermitian A, if \mu=\rho(x), then \operatorname{dist}(\mu,\sigma(A))\le \|r\|_2. For diagonalizable matrices, perturbation bounds involve the conditioning of the eigenvector matrix: A=V\Lambda V^{-1}, \qquad \kappa(V)=\|V\|\|V^{-1}\|.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 6.83
Problem formulation.
Investigate communication-avoiding variants of Arnoldi or Lanczos methods.
Method.
Use spectral decomposition, Rayleigh quotient identities, QR/inverse iteration, residual eigenvalue bounds, and perturbation theory.
Detailed solution and justification.
Use the eigenvalue relation Ax=\lambda x and analyze the method through the spectral decomposition of A. Residuals provide a posteriori information: r=Ax-\mu x. For Hermitian A, if \mu=\rho(x), then \operatorname{dist}(\mu,\sigma(A))\le \|r\|_2. For diagonalizable matrices, perturbation bounds involve the conditioning of the eigenvector matrix: A=V\Lambda V^{-1}, \qquad \kappa(V)=\|V\|\|V^{-1}\|.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 6.84
Problem formulation.
Analyze the use of mixed precision in eigenvalue computations, including residual correction and refinement.
Method.
Use spectral decomposition, Rayleigh quotient identities, QR/inverse iteration, residual eigenvalue bounds, and perturbation theory.
Detailed solution and justification.
Use the eigenvalue relation Ax=\lambda x and analyze the method through the spectral decomposition of A. Residuals provide a posteriori information: r=Ax-\mu x. For Hermitian A, if \mu=\rho(x), then \operatorname{dist}(\mu,\sigma(A))\le \|r\|_2. For diagonalizable matrices, perturbation bounds involve the conditioning of the eigenvector matrix: A=V\Lambda V^{-1}, \qquad \kappa(V)=\|V\|\|V^{-1}\|.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 6.85
Problem formulation.
Develop interval or residual-based certified enclosures for Hermitian eigenvalues.
Method.
Use spectral decomposition, Rayleigh quotient identities, QR/inverse iteration, residual eigenvalue bounds, and perturbation theory.
Detailed solution and justification.
Use the eigenvalue relation Ax=\lambda x and analyze the method through the spectral decomposition of A. Residuals provide a posteriori information: r=Ax-\mu x. For Hermitian A, if \mu=\rho(x), then \operatorname{dist}(\mu,\sigma(A))\le \|r\|_2. For diagonalizable matrices, perturbation bounds involve the conditioning of the eigenvector matrix: A=V\Lambda V^{-1}, \qquad \kappa(V)=\|V\|\|V^{-1}\|.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Interactive tools
The theory and solutions come first. These tools are for review, laboratories, games, memory cards, and randomized assessment.