Premium
Estimating a largest eigenvector by Lanczos and polynomial algorithms with a random start
Author(s) -
Leyk Zbigniew,
Woźniakowski Henryk
Publication year - 1998
Publication title -
numerical linear algebra with applications
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.02
H-Index - 53
eISSN - 1099-1506
pISSN - 1070-5325
DOI - 10.1002/(sici)1099-1506(199805/06)5:3<147::aid-nla128>3.0.co;2-2
Subject(s) - mathematics , eigenvalues and eigenvectors , residual , lanczos resampling , random matrix , matrix (chemical analysis) , polynomial , randomized algorithm , distribution (mathematics) , algorithm , lanczos algorithm , combinatorics , mathematical analysis , quantum mechanics , physics , materials science , composite material
We study Lanczos and polynomial algorithms with random start for estimating an eigenvector corresponding to the largest eigenvalue of an n × n large symmetric positive definite matrix. We analyze the two error criteria: the randomized error and the randomized residual error. For the randomized error, we prove that it is not possible to get distribution‐free bounds, i.e., the bounds must depend on the distribution of eigenvalues of the matrix. We supply such bounds and show that they depend on the ratio of the two largest eigenvalues. For the randomized residual error, distribution‐free bounds exist and are provided in the paper. We also provide asymptotic bounds, as well as bounds depending on the ratio of the two largest eigenvalues. The bounds for the Lanczos algorithm may be helpful in a practical implementation and termination of this algorithm. © 1998 John Wiley & Sons, Ltd.