Optimal perturbation bounds for the Hermitian eigenvalue problem

There is now a large literature on structured perturbation bounds for eigen value problems of the form Hx = lambda Mx, where H and M are Hermitian. These results give relative error bounds on th e ith eigenvalue, lambda(i), of the form \lambda(i) - <(lambda)over tilde>(i)\/\lambda(i)\ and bound the error in the ith eigenvector in terms of the relative gap, [GRAPHICS] In general, this theory usually restricts H to be nonsingular and M to be p ositive definite. We relax this restriction by allowing H to be singular. F or our results on eigenvalues we allow M to be positive semi-definite and f or a few results we allow it to be more general. For these problems, for ei genvalues that are not zero or infinity under perturbation, it is possible to obtain local relative error bounds. Thus, a wider class of problems may be characterized by this theory. Although it is impossible to give meaningf ul relative error bounds on eigenvalues that are not bounded away from zero , we show that the error in the subspace associated with those eigenvalues can be characterized meaningfully. (C) 2000 Elsevier Science Inc. All right s reserved.