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

✍ Scribed by Joel Friedman

• Publisher: Elsevier Science
• Year: 1998
• Tongue: English
• Weight: 957 KB
• Volume: 280
• Category: Article
• ISSN: 0024-3795
• DOI: 10.1016/s0024-3795(98)10020-4

✦ Synopsis

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 v. and setting vk = Akvo; then the Rayleigh quotients Rk = (Auk, vk)/( ok, ok) usually converge to 21 as k -+ 03 (here (u, v) denotes their inner product). In this paper we give two methods for determining how close Rk is to il. They are both based on a bound on I, -Rk involving the difference of two consecutive Rayleigh quotients and a quantity wk. While we do not know how to directly calculate wk, we can give an algorithm for giving a good upper bound on it, at least with high probability. This leads to an upper bound for R, -Rk which is proportional to (1,/n,)", which holds with a prescribed probability (the prescribed probability being an arbitrary 6 > 0, with the upper bound depending on 6).