A Note on Conjugate Gradient Convergence
| dc.contributor.author | Naiman, Aaron E. | en_US |
| dc.contributor.author | Babuska, Ivo M. | en_US |
| dc.contributor.author | Elman, Howard C. | en_US |
| dc.date.accessioned | 2004-05-31T22:34:21Z | |
| dc.date.available | 2004-05-31T22:34:21Z | |
| dc.date.created | 1995-08 | en_US |
| dc.date.issued | 1998-10-15 | en_US |
| dc.description.abstract | 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) | en_US |
| dc.format.extent | 356163 bytes | |
| dc.format.mimetype | application/postscript | |
| dc.identifier.uri | http://hdl.handle.net/1903/754 | |
| dc.language.iso | en_US | |
| dc.relation.isAvailableAt | Digital Repository at the University of Maryland | en_US |
| dc.relation.isAvailableAt | University of Maryland (College Park, Md.) | en_US |
| dc.relation.isAvailableAt | Tech Reports in Computer Science and Engineering | en_US |
| dc.relation.isAvailableAt | UMIACS Technical Reports | en_US |
| dc.relation.ispartofseries | UM Computer Science Department; CS-TR-3516 | en_US |
| dc.relation.ispartofseries | UMIACS; UMIACS-TR-95-86 | en_US |
| dc.title | A Note on Conjugate Gradient Convergence | en_US |
| dc.type | Technical Report | en_US |