Abstract

Recently, the authors obtained an upper bound on the error for the conjugate gradient method, which is valid in an asymptotic setting as the size of the linear systems tends to infinity. The estimate depends on the asymptotic distribution of eigenvalues, and the ratio between the size and the number of iterations. Such error bounds are related to the existence of polynomials with value $1$ at $0$ whose supnorm on the spectrum is as small as possible. A possible strategy for constructing such a polynomial $p$ is to select a set $S$, to specify that every eigenvalue outside $S$ is a zero of $p$, and then to minimize the supnorm of $p$ on $S$. Here we show that this strategy can never give a better asymptotic upper bound than the one we obtained before. We also discuss the case where equality is met.