Why do we not need information of the eigenvalues of $A$ for the CG method, but we do need it for the Chebyshev method?

64 Views Asked by At

I'm currently reading up on information about the Chebyshev method and the Conjugate Gradient method for finding the solution of a system $$A\mathbf{u}=\mathbf{f}$$ where $A$ is an SPD matrix, but I am getting confused about something. For the Chebyshev method we know for the iterands that $$||\mathbf{y}^k-\mathbf{u}||_2\leq 2\Big(\frac{\sqrt{\kappa_2(M^{-1}A)}-1}{\sqrt{\kappa_2(M^{-1}A)}+1}\Big)^k ||\mathbf{u}-\mathbf{u}^0||_2$$

Where for the CG method we have that the iterates satisfy $$||\mathbf{u}-\mathbf{u}^k||\leq 2\Big(\frac{\sqrt{\kappa_2(A)}-1}{\sqrt{\kappa_2(A)}+1}\Big)^k ||\mathbf{u}-\mathbf{u}^0||$$ Where $\kappa_2(A)$ denotes the condition number of $A$.

As becomes obvious, both inequalities contain the condition number. However, in my literature it says that for application of the CG method, we do not need knowledge of the eigenvalues, whereas for the Chebyshev method, we do. Why is this? Does this have nothing to do with these bounds on the iterates?

Perhaps my explanation is a bit vague and perhaps the mentioned bounds are irrelevant for the necessity of knowledge of the eigenvalues, but I mentioned them anyway. Any explanation is appreciated!