Estimate extreme eigenvalues with CG

Question

CG may be used to estimate the extremal eigenvalues of a SPD matrix (by computing eigenvalues of tridiagonal matrix associated with the Lanczos algorithm). After a few iterations the largest eigenvalue is generally well approximated whereas the smallest is generally overestimated.

Is there a way to have some estimate of the quality of those approximate eigenvalues?

Thank you.

What exactly do you mean by the "quality" of the approximation? — Paul, Oct 05 '12 at 17:33
@JackPoulson - I'm okay with letting this stand as a separate question, do you mind moving your comment to an answer? — Aron Ahmadia, Oct 06 '12 at 03:42
I would like to have some lower and upper bounds on the approximation I get. I'll have a look to the paper, thank you ! — Tom, Oct 08 '12 at 06:33

score 2 · Answer 1 · answered Nov 07 '18 at 02:08

This question is very related to another SE question on condition number estimates which contains relevant materials.

As @Jack_Poulson mentioned, the following paper contains a detailed discussion on the asked topic:

J. Kuczyński and H. Woźniakowski, "Estimating the Largest Eigenvalue by the Power and Lanczos Algorithms with a Random Start," SIAM J. Matrix Anal. Appl., vol. 13, no. 4, pp. 1094–1122. Downloadable version of a slightly different version of this paper is available here.

Estimate extreme eigenvalues with CG

1 Answers1

Linked