Estimating the Largest Eigenvalue by the Power and Lanczos Algorithms with a Random Start

This paper addresses the problem of computing an approximation to the largest eigenvalue of an $n \times n$ large symmetric positive definite matrix with relative error at most $\varepsilon $. Only algorithms that use Krylov information $[b,Ab, \cdots ,A^k b]$ consisting of k matrix-vector multiplications for some unit vector b are considered. If the vector b is chosen deterministically, then the problem cannot be solved no matter how many matrix-vector multiplications are performed and what algorithm is used. If, however, the vector b is chosen randomly with respect to the uniform distribution over the unit sphere, then the problem can be solved on the average and probabilistically. More precisely, for a randomly chosen vector b, the power and Lanczos algorithms are studied. For the power algorithm (method), sharp bounds on the average relative error and on the probabilistic relative failure are proven. For the Lanczos algorithm only upper bounds are presented. In particular, $\ln ( n )/( n ) k $ charact...