You are granted permission for the non-commercial reproduction, distribution, display, and performance of this technical report in any format. However, this permission is only for a period of 45 (forty-five) days from the most recent time that you verified that this technical report is still available from the Department of Computer Science of the University of Maryland at College Park under terms that include this permission. All other rights are reserved by the author(s).
A Note on Conjugate Gradient Convergence. Aaron E. Naiman. Ivo M. Babuska. Howard C. Elman. August 1995.
The one-dimensional discrete Poisson equation on a uniform grid with $n$ points produces a linear system of equations with a symmetric positive-definite coefficient matrix. Hence, the conjugate gradient method can be used, and standard analysis gives an upper bound of $O(n)$ on the number of iterations required for convergence. This paper introduces a systematically defined set of solutions dependent on a parameter $\beta$, and for several values of $\beta$, presents exact analytic expressions for the number of steps $k(\beta,\tau,n)$ needed to achieve accuracy $\tau$. The asymptotic behavior of these expressions has the form $O(n^{\alpha})$ as $n \to \infty$ and $O(\tau^{\gamma})$ as $\tau \to \infty$. In particular, two choices of $\beta$ corresponding to nonsmooth solutions give $\alpha=0$, i.e., iteration counts independent of $n$; this is in contrast to the standard bounds. The standard asymptotic convergence behavior, $\alpha=1$, is seen for a relatively smooth solution. Numerical examples illustrate and supplement the analysis. (Also cross-referenced as UMIACS-TR-95-86) University of Maryland Institute for Advanced Computer Studies, Dept. of Computer Science, Univ. of Maryland,
Last Generated Fri Aug 11 04:01:01 EDT 2000