Introduction

In this chapter we treat the standard Hermitian, or most often real symmetric, eigenvalue problem (HEP),

$$Ax=\lambda x\,,$$ (16)

where $A=A^{\ast}$. It is the most commonly occurring algebraic eigenvalue problem, for which we have the most reliable theory and the most powerful algorithms available.

A summary of the basic theory about the Hermitian eigenvalue problem (4.1) is given in §2.2. It is known that the problem (4.1) has $n$ real eigenvalues $\lambda_i$, which we may order increasingly so that $\lambda_1 \leq \lambda_2 \leq \cdots \leq \lambda_n$. Note that several eigenvalues may coincide. In many applications the matrix $A$ is positive definite, $\lambda_1>0$ (or positive semidefinite, $\lambda_1\geq 0$). Even in the cases where positive definiteness can be used to advantage, we choose to treat Hermitian $A$ with a general distribution of eigenvalues in this chapter.

When $A$ is Hermitian, it is always possible to find $n$ mutually orthogonal eigenvectors, $x_i,\,i=1,\dots,n$, so that

$$A=X \Lambda X^{\ast},$$ (17)

where $\Lambda=\diag(\lambda_i)$, $X=[x_1,x_2,\dots,x_n]$, and $X^{\ast}X=I$. The eigenvectors $x_i$ are not unique; what is unique is the invariant subspace for each different eigenvalue. For a Hermitian matrix $A$, the invariant subspace is of the same dimension as the multiplicity of the eigenvalue. It is important to keep in mind that when certain eigenvalues coincide, their eigenvectors lose their individuality: there is no way of saying that one set of vectors are the eigenvectors of a multiple eigenvalue. Two different algorithms, and even two different runs with the same algorithm, will give different representative eigenvectors in the invariant subspace. On the other hand, a user is entitled to demand that an algorithm produce eigenvector approximations that are orthogonal to each other, even if the matrix has multiple eigenvalues.

The eigenvalues of $A$ are always well-conditioned. If a perturbation $E$ is added to the matrix $A$, then each of the eigenvalues is perturbed at most as far as the spectral norm $\Vert E\Vert _2$,

$$\vert\lambda_i(A+E)-\lambda_i(A)\vert\leq \Vert E\Vert _2\,.$$ (18)

There are several stronger results available, like the Wielandt-Hoffman inequality that says that the sum of squares of the differences between the eigenvalues is majorized by the sum of squares of the elements of $E$; see §4.8 and references therein. In many cases, one is interested in eigenvalues that are small compared to the norm $\Vert A\Vert$, and for such eigenvalues the inequality (4.3) is not very satisfactory, since it allows large relative perturbations for such small eigenvalues. It is possible to develop perturbation bounds for relative perturbations under certain additional assumptions.

There is no result as simple as (4.3) available for bounding the perturbation of eigenvectors: one has to add an assumption of separation between the eigenvalues. Let us cite the venerable $\sin \theta$ theorem of Davis and Kahan from [101].

Let us assume that $(\mu,z)$ is an approximation of the eigenpair $(\lambda_i, x_i)$ of $A$, where $z$ is normalized so that $\Vert z\Vert _2 = 1$. The ``best'' $\mu$ corresponding to $z$ is the Rayleigh quotient $\mu = z^{\ast} A z$, so we assume that $\mu$ has this value. Suppose that $\mu$ is closer to $\lambda_i$ than any other eigenvalues of $A$, and let $\delta$ be the gap between $\mu$ and any other eigenvalue: $\delta = \min_{\lambda_j \neq \lambda_i} \vert \mu - \lambda_j \vert$. Define the residual vector $r$ as $r=Az-\mu z$; then we have

$$\sin\angle(z,x_i)\leq\frac{\Vert r\Vert _2}{\delta}\,.$$ (19)

Under the same assumptions, we have the improved bound on the eigenvalue approximation, |-_i|{||r||_2,||r||_2^2}. The first alternative in this minimum is equivalent to the previous bound (4.3), since $\mu$ is an eigenvalue of the perturbed matrix $A+E$ with $E=-rz^{\ast}$ a rank-one perturbation of norm $\Vert E\Vert _2 = \Vert r\Vert _2$ (it is not necessary for $E$ to be Hermitian in the bound (4.3)). The reader is referred to §4.8 for further details.