Error Analysis of Update Methods for the Symmetric Eigenvalue Problem

Cuppen’s divide-and-conquer method for solving the symmetric tridiagonal eigenvalue problem has been shown to be very efficient on shared memory multiprocessor architectures. In this paper, some error analysis issues concerning this method are resolved. The method is shown to be stable and a slightly different stopping criterion for finding the zeroes of the spectral function is suggested. These error analysis results extend to general update methods for the symmetric eigenvalue problem. That is, good backward error bounds are obtained for methods to find the eigenvalues and eigenvectors of $A + \rho ww^T $, given those of A. These results can also be used to analyze a new fast method for finding the eigenvalues of banded, symmetric Toeplitz matrices.