Estimate extreme eigenvalues with CG

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.

• Please see this paper from this question. – Jack Poulson Oct 5 '12 at 16:47
• What exactly do you mean by the "quality" of the approximation? – Paul Oct 5 '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 6 '12 at 3: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 8 '12 at 6:33

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: