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

Estimating the Largest Eigenvalue by the Power and Lanczos Algorithms with a Random Start
 Author(s):

Kuczynski, Jacek
Wozniakowski, Henryk
 Date:

1989
 Type:

Technical reports
 Department(s):

Computer Science
 Persistent URL:

http://hdl.handle.net/10022/AC:P:12129
 Series:

Columbia University Computer Science Technical Reports
 Part Number:

CUCS46589
 Publisher:

Department of Computer Science, Columbia University
 Publisher Location:

New York
 Abstract:

This paper addresses the problem of computing an approximation to the largest eigenvalue of an n x n large symmetric positive definite matrix with relative error at most ε. Only algorithms that use Krylov information [b, Ab, . .. , Akb] consisting of k matrixvector 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 matrixvector 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 )/k characterizes the average relative error of the power algorithm, whereas O( ( ln ( n )/ k )2 ) is an upper bound on the average relative error of the Lanczos algorithm. In the probabilistic case, the algorithm is characterized by its probabilistic relative failure, which is defined as the measure of the set of vectors b for which the algorithm fails. It is shown that the probabilistic relative failure goes to zero roughly as sqrt n (1  ε) ^k for the power algorithm and at most as sqrt n e^{  (2k  1)\sqrt ε } for the Lanczos algorithm. These bounds are for a worst case distribution of eigenvalues which may depend on k. The behavior in the average and probabilistic cases of the two algorithms for a fixed matrix A is also studied as the number of matrixvector multiplications k increases. The bounds for the power algorithm depend then on the ratio of the two largest eigenvalues and their multiplicities. The bounds for the Lanczos algorithm depend on the ratio between the difference of the two largest eigenvalues and the difference of the largest and the smallest eigenvalues.
 Subject(s):

Computer science
 Item views
 392
 Metadata:

text  xml
 Suggested Citation:
 Jacek Kuczynski, Henryk Wozniakowski, 1989, Estimating the Largest Eigenvalue by the Power and Lanczos Algorithms with a Random Start, Columbia University Academic Commons, http://hdl.handle.net/10022/AC:P:12129.