Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4626902 | Applied Mathematics and Computation | 2015 | 8 Pages |
Abstract
In this paper, we develop new methods for approximating dominant eigenvector of column-stochastic matrices. We analyze the Google matrix, and present an averaging scheme with linear rate of convergence in terms of 1-norm distance. For extending this convergence result onto general case, we assume existence of a positive row in the matrix. Our new numerical scheme, the Reduced Power Method (RPM), can be seen as a proper averaging of the power iterates of a reduced stochastic matrix. We analyze also the usual Power Method (PM) and obtain convenient conditions for its linear rate of convergence with respect to 1-norm.
Related Topics
Physical Sciences and Engineering
Mathematics
Applied Mathematics
Authors
Yurii Nesterov, Arkadi Nemirovski,