JACOBIS METHOD IS MORE ACCURATE THAN QR

It is shown that Jacobi's method (with a proper stopping criterion) computes small eigenvalues of symmetric positive definite matrices with a uniformly better relative accuracy bound than QR, divide and conquer, traditional bisection, or any algorithm which first involves tridiagonalizing the matrix. Modulo an assumption based on extensive numerical tests, Jacobi's method is optimally accurate in the following sense: if the matrix is such that small relative errors in its entries cause small relative errors in its eigenvalues, Jacobi will compute them with nearly this accuracy. In other words, as long as the initial matrix has small relative errors in each component, even using infinite precision will not improve on Jacobi (modulo factors of dimensionality). It is also shown that the eigenvectors are computed more accurately by Jacobi than previously thought possible. Similar results are proved for using one-sided Jacobi for the singular value decomposition of a general matrix.