0
$\begingroup$

Let $A \in \mathbb{R}^{n \times n}$ be SPD. The error estimate for the conjugate gradient method is given by \begin{equation} \|x_* - x_m \|_A \leq 2 \left( \frac{\sqrt{\kappa}-1}{\sqrt{\kappa}+1} \right)^m \| x_* - x_0 \|_A \end{equation} where $x_*$ is the exact solution, $x_j$ are the approximate solutions of $Ax=b$, and \begin{equation} \kappa = \frac{\lambda_{max}(A)}{\lambda_{min}(A)}. \end{equation} 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?

$\endgroup$
1
$\begingroup$

You may find the ideas in this and this. Maybe you may find some pointers and/or theorems also in this book (in the section on the convergence rate of CG).

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.