Estimating a largest eigenvector by Lanczos and polynomial algorithms with a random start (Q4940818)

The authors study methods for estimating an eigenvector \(u\) corresponding to the largest eigenvalue \(\lambda _1\) of an \(n\times n\) large symmetric positive definite matrix \(A\). Denoting the \(\lambda _1\)-eigenspace by \(V\) and an approximation of \(u\) by \(u_k(b)\), where \(b\) stands for a random initial vector, they define the randomized (RE) and randomized residual error (RRE). The RE evaluates the distance between \(u_k(b)\) and \(V\) and gives the expectation with respect to random vectors \(b\). Similarly, the RRE gives the expectation based on the relative residual \(\|Au_k(b)-\lambda _1 u_k(b)\|/\lambda _1\) and random \(b\). To get \(u_k\) the Lanczos or the power algorithm is used which means that \(u_k\) belongs to the Krylov subspace \(K_k=\operatorname {span}\{b,Ab,\dots ,A^{k-1}b\}\). It is shown that if \(k<n\) is fixed then an \(n\times n\) s.p.d.m.\ \(A_k\) exists such that the RE is large for any polynomial algorithm in \(K_k\). By a reference, asymptotic rates of convergence are displayed for the RE and the power method if \(A\) is fixed and \(k\to \infty \). The authors calculate upper bounds of the RE for the Lanczos method. The bounds depend on the ratio of the two largest eigenvalues. As regards the RRE, besides convergence rate estimates dependent on the eigenvalue ratio, eigenvalue-free upper and lower bounds are given for the power algorithm. Similar results are presented for the Lanczos method, too. The theory is illustrated by numerical tests which indicate some overestimation of both errors.