Predicting the Behavior of Finite Precision Lanczos and Conjugate Gradient Computations

It is demonstrated that finite precision Lanczos and conjugate gradient computations for solving a symmetric positive definite linear system $Ax = b$ or computing the eigenvalues of A behave very similarly to the exact algorithms applied to any of a certain class of larger matrices. This class consists of matrices $\hat{A} $ which have many eigenvalues spread throughout tiny intervals about the eigenvalues of A. The width of these intervals is a modest multiple of the machine precision times the norm of A. This analogy appears to hold, provided only that the algorithms are not run for huge numbers of steps. Numerical examples are given to show that many of the phenomena observed in finite precision computations with A can also be observed in the exact algorithms applied to such a matrix $\hat{A} $.