Complexity theory of numerical linear algebra

AbstractIn this paper the statistical properties of problems that occur in numerical linear algebra are studied. Bounds are calculated for the average performance of the power method for the calculation of eigenvectors of symmetric and Hermitian matrices, thus an upper bound is found for the average complexity of eigenvector calculation. The condition number of a matrix is studied and sharp bounds are calculated for the average (and the variance) loss of precision encountered when one solves a system of linear equations