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

Let A be a positive definite, symmetric matrix. We wish to determine the largest eigenvalue, λ1. We consider the power method, i.e. that of choosing a vector v0 and setting vk = Akv0; then the Rayleigh quotients Rk = (Avk, vk)/(vk, vk) usually converge to λ1 as k → ∞ (here (u, v) denotes their inner product). In this paper we give two methods for determining how close Rk is to λ1. They are both based on a bound on λ1 − Rk 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 λ1 − Rk which is proportional to (λ2/λ1)2k, which holds with a prescribed probability (the prescribed probability being an arbitrary δ > 0, with the upper bound depending on δ).