As usual in numerical linear algebra, we will use the backward error analysis model to assess the accuracy of the results. We will first give perturbation theorems that tell how much a perturbation of the data, in this case matrix elements, will change the results, eigenvalues, singular values and vectors. We will also provide a posteriori methods to measure the backward error for computed solutions.

In the simplest cases, the perturbation theorems give a
bound for the perturbation of the eigenvalues as a multiple
of the perturbation of the matrix elements. The multiplier
is called a *condition number*. For eigenvectors
we also need information about the distance between the different
eigenvalues, as well as the angles between left and right eigenvectors.
In degenerate cases, the best we can get is an asymptotic
series, possibly involving fractional powers of the perturbation.

We will discuss what to do when a simple condition number
based bound is not practical. If we do not have good
bounds for individual eigenvectors, then a better
conditioned invariant (or deflating or reducing) subspace
of higher dimension may be available. We can also derive a
bound for the norm of the resolvent and find *pseudospectra*.

For iterative algorithms *a posteriori* methods are used to compute
the backward error, often using computed
residuals. It is possible to compute, or at least estimate,
the residual during the computation as part of monitoring
for convergence.

We will show when stronger results as e.g. small relative error bounds for small eigenvalues exist. This is of importance, specially when an ill conditioned matrix comes from the discretization of a well conditioned continuous problem.

Wed Jun 21 02:35:11 EDT 1995