Error bounds on the power method for determining the largest eigenvalue of a symmetric, positive definite matrix

Let A be a positive definite, symmetric matrix. We wish to determine the largest eigenvalue, λ₁. We consider the power method, i.e. that of choosing a vector v₀ and setting v_k = A^kv₀; then the Rayleigh quotients R_k = (Av_k, v_k)/(v_k, v_k) usually converge to λ₁ as k → ∞ (here (u, v) denotes their inner product). In this paper we give two methods for determining how close R_k is to λ₁. They are both based on a bound on λ₁ ? R_k involving the difference of two consecutive Rayleigh quotients and a quantity ω_k. While we do not know how to directly calculate ω_k, we can given an algorithm for giving a good upper bound on it, at least with high probability. This leads to an upper bound for λ₁ ? R_k which is proportional to (λ₂/λ₁)^2k, which holds with a prescribed probability (the prescribed probability being an arbitrary δ > 0, with the upper bound depending on δ).