Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

Mobile Device Pairing
Green Open Access
Mathematics of Computation
Mathematics of Computation
ISSN 1088-6842(online) ISSN 0025-5718(print)


On Meinardus' examples for the conjugate gradient method

Author: Ren-Cang Li
Journal: Math. Comp. 77 (2008), 335-352
MSC (2000): Primary 65F10
Published electronically: September 17, 2007
MathSciNet review: 2353956
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: The conjugate gradient (CG) method is widely used to solve a positive definite linear system $ Ax=b$ of order $ N$. It is well known that the relative residual of the $ k$th approximate solution by CG (with the initial approximation $ x_0=0$) is bounded above by

$\displaystyle 2\left[\Delta_{\kappa}^k+\Delta_{\kappa}^{-k}\right]^{-1}$   with$\displaystyle \quad \Delta_{\kappa}=\frac {\sqrt{\kappa}+1}{\sqrt{\kappa}-1}, $

where $ \kappa\equiv\kappa(A)=\Vert A\Vert _2\Vert A^{-1}\Vert _2$ is $ A$'s spectral condition number. In 1963, Meinardus (Numer. Math., 5 (1963), pp. 14-23) gave an example to achieve this bound for $ k=N-1$ but without saying anything about all other $ 1\le k<N-1$. This very example can be used to show that the bound is sharp for any given $ k$ by constructing examples to attain the bound, but such examples depend on $ k$ and for them the $ (k+1)$th residual is exactly zero. Therefore it would be interesting to know if there is any example on which the CG relative residuals are comparable to the bound for all $ 1\le k\le N-1$. There are two contributions in this paper:
  1. A closed formula for the CG residuals for all $ 1\le k\le N-1$ on Meinardus' example is obtained, and in particular it implies that the bound is always within a factor of $ \sqrt 2$ of the actual residuals;
  2. A complete characterization of extreme positive linear systems for which the $ k$th CG residual achieves the bound is also presented.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 65F10

Retrieve articles in all journals with MSC (2000): 65F10

Additional Information

Ren-Cang Li
Affiliation: Department of Mathematics, University of Texas at Arlington, P.O. Box 19408, Arlington, Texas 76019-0408

PII: S 0025-5718(07)01922-9
Keywords: Conjugate gradient method, Krylov subspace, rate of convergence, Vandermonde matrix, condition number
Received by editor(s): September 20, 2005
Received by editor(s) in revised form: January 9, 2006
Published electronically: September 17, 2007
Additional Notes: This work was supported in part by the National Science Foundation CAREER award under Grant No. CCR-9875201 and by the National Science Foundation under Grant No. DMS-0510664.
Article copyright: © Copyright 2007 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.