Remote Access Mathematics of Computation
Green Open Access

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
DOI: https://doi.org/10.1090/S0025-5718-07-01922-9
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?)

  • 1. O. Axelsson, Iterative solution methods, Cambridge University Press, New York, 1996. MR 1276069 (95f:65005)
  • 2. B. Beckermann, On the numerical condition of polynomial bases: Estimates for the condition number of Vandermonde, Krylov and Hankel matrices, Habilitationsschrift, Universität Hannover, April 1996; see http://math.univ-lille1.fr/~bbecker/abstract/Habilitationsschrift_Beckermann.pdf.
  • 3. P. Borwein and T. Erdélyi, Polynomials and polynomial inequalities, Graduate Texts in Mathematics, vol. 161, Springer, New York, 1995. MR 1367960 (97e:41001)
  • 4. J. Demmel, Applied numerical linear algebra, SIAM, Philadelphia, 1997. MR 1463942 (98m:65001)
  • 5. M. Engeli, Th. Ginsburg, H. Rutishauser, and E. Stiefel, Refined iterative methods for computation of the solution and the eigenvalues of self-adjoint boundary value problems, Birkhäuser Verlag, Basel/Stuttgart, 1959. MR 0145689 (26:3218)
  • 6. V. N. Faddeeva, Computational methods of linear algebra, Dover Publications, New York, 1959, Translated from the Russia by Curtis D. Benster. MR 0400669 (53:4500)
  • 7. G. H. Golub and C. F. Van Loan, Matrix computations, 3rd ed., Johns Hopkins University Press, Baltimore, Maryland, 1996. MR 1417720 (97g:65006)
  • 8. I. S. Gradshteyn and I. M. Ryzhik, Table of integrals, series, and products, Academic Press, New York, 1980, Corrected and Enlarged Edition prepared by A. Jeffrey, incorporated the fourth edition prepared by Yu. V. Geronimus and M. Yu. Tseytlin, translaed from the Russian by Scripta Technica, Inc. MR 1773820 (2001c:00002)
  • 9. A. Greenbaum, Comparision of splittings used with the conjugate gradient algorithm, Numer. Math. 33 (1979), 181-194. MR 0549448 (80k:65035)
  • 10. -, Iterative methods for solving linear systems, SIAM, Philadelphia, 1997. MR 1474725 (98j:65023)
  • 11. M. R. Hestenes and E. Stiefel, Methods of conjugate gradients for solving linear systems, J. Res. Nat. Bur. Standards 49 (1952), 409-436. MR 0060307 (15,651a)
  • 12. I. C. F. Ipsen, Expressions and bounds for the GMRES residual, BIT 40 (2000), no. 3, 524-535. MR 1780406 (2001g:65032)
  • 13. S. Kaniel, Estimates for some computational techniques in linear algebra, Math. Comp. 20 (1966), no. 95, 369-378. MR 0234618 (38:2934)
  • 14. R.-C. Li, Sharpness in rates of convergence for CG and symmetric Lanczos methods, Technical Report 2005-01, Department of Mathematics, University of Kentucky, 2005, Available at http://www.ms.uky.edu/~math/MAreport/.
  • 15. -, Vandermonde matrices with Chebyshev nodes, Technical Report 2005-02, Department of Mathematics, University of Kentucky, 2005, Available at http://www.ms.uky.edu/~math/MAreport/, Lin. Alg. Appl., to appear.
  • 16. J. Liesen, M. Rozlozník, and Z. Strakos, Least squares residuals and minimal residual methods, SIAM J. Sci. Comput. 23 (2002), no. 5, 1503-1525. MR 1885072 (2003a:65033)
  • 17. J. Liesen and P. Tichý, The worst-case GMRES for normal matrices, BIT 44 (2004), no. 1, 79-98. MR 2057363 (2005d:65046)
  • 18. G. Meinardus, Über eine Verallgemeinerung einer Ungleichung von L. V. Kantorowitsch, Numer. Math. 5 (1963), 14-23. MR 0160311 (28:3525)
  • 19. Y. Saad, Iterative methods for sparse linear systems, 2nd ed., SIAM, Philadelphia, 2003. MR 1990645 (2004h:65002)
  • 20. G. L. G. Sleijpen and A. van der Sluis, Further results on the convergence behavior of conjugate-gradients and Ritz values, Linear Algebra Appl. 246 (1996), 233-378. MR 1407670 (97j:65067)
  • 21. G. W. Stewart and J.-G. Sun, Matrix perturbation theory, Academic Press, Boston, 1990. MR 1061154 (92a:65017)
  • 22. L. N. Trefethen and D. Bau, III, Numerical linear algebra, SIAM, Philadelphia, 1997. MR 1444820 (98k:65002)
  • 23. K. Zhou, J. C. Doyle, and K. Glover, Robust and optimal control, Prentice Hall, 1995.

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
Email: rcli@.uta.edu

DOI: https://doi.org/10.1090/S0025-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.

American Mathematical Society