# Improved error estimate for Conjugate Gradient Method

Let $A \in \mathbb{R}^{n \times n}$ be SPD. The error estimate for the conjugate gradient method is given by $$\|x_* - x_m \|_A \leq 2 \left( \frac{\sqrt{\kappa}-1}{\sqrt{\kappa}+1} \right)^m \| x_* - x_0 \|_A$$ where $x_*$ is the exact solution, $x_j$ are the approximate solutions of $Ax=b$, and $$\kappa = \frac{\lambda_{max}(A)}{\lambda_{min}(A)}.$$ Assume that the eigenvalues of $A$ satisfy $0 < \lambda_1 \leq \lambda_2 \leq \, ... \, \leq \lambda_{n-1} << \lambda_n$. I would like to find an improved error estimate for this assumption. Any suggestions?

Let $\Pi_k$ denotes a set of polynomials $p$ of the degree at most $k$ such that $p(0)=1$. The development of the classical CG convergence bound starts with the bound $$\frac{\|e_k\|_A}{\|e_0\|_A}\leq\min_{p\in\Pi_k}\max_{i=1,\ldots,n}\left|p(\lambda_i)\right| \leq\min_{p\in\Pi_k}\max_{\lambda\in[\lambda_1,\lambda_n]}\left|p(\lambda)\right|$$ and using Chebyshev polynomials (with some scaling and shifting) to bound the maximum.
If the spectrum has a few large outliers, say, $\lambda_1\leq\cdots\leq\lambda_m\ll\lambda_{m+1}\leq\cdots\leq\lambda_n$ (somewhat generalizing your assumptions), the idea is quite simple. In the first min-max problem, take (as a "candidate" to get rid of the minimum) a polynomial of the form $$p(\lambda)=q_{n-m}(\lambda)\tilde{p}(\lambda),$$ where $q_{n-m}\in\Pi_{n-m}$ and $\tilde{p}\in\Pi_{k-n+m}$ (for $k=n-m,n-m+1,\ldots$) and such that $q_{n-m}$ is zero for $\lambda=\lambda_i$, $i=m+1,\ldots,n$. Such a polynomial is simple: $$q_{n-m}(\lambda)=\left(1-\frac{\lambda}{\lambda_{m+1}}\right)\cdots\left(1-\frac{\lambda}{\lambda_n}\right).$$ The effect of this choice is that the maximum then does not depend on the values of $p$ at these points (since the polynomial attains zero there): $$\min_{p\in\Pi_k}\max_{i=1,\ldots,n}\left|p(\lambda_i)\right| \leq \min_{\tilde{p}\in\Pi_{k-n+m}}\max_{i=1,\ldots,m}\left|\tilde{p}(\lambda_i)\right|.$$ Now, on the rest, use the same machinery as for the "classical" bound: $$\min_{\tilde{p}\in\Pi_{k-n+m}}\max_{i=1,\ldots,m}\left|\tilde{p}(\lambda_i)\right|\leq\min_{\tilde{p}\in\Pi_{k-n+m}}\max_{\lambda\in[\lambda_1,\lambda_m]}\left|\tilde{p}(\lambda)\right| \leq 2\left(\frac{\sqrt{\kappa_m}-1}{\sqrt{\kappa_m}+1}\right)^{k-n+m},$$ where $\kappa_m:=\lambda_m/\lambda_1$ is by assumption much smaller than $\kappa$. Note that this bound is "active" for $k=n-m,n-m+1,\ldots$ (to make the candidate polynomial annihilate all outliers) and that you should be aware of rounding errors.