On Meinardus’ examples for the conjugate gradient method
HTML articles powered by AMS MathViewer
- by Ren-Cang Li PDF
- Math. Comp. 77 (2008), 335-352 Request permission
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 \[ 2\left [\Delta _{\kappa }^k+\Delta _{\kappa }^{-k}\right ]^{-1} \quad \mbox {with}\quad \Delta _{\kappa }=\frac {\sqrt {\kappa }+1}{\sqrt {\kappa }-1}, \] where $\kappa \equiv \kappa (A)=\|A\|_2\|A^{-1}\|_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:
-
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;
-
A complete characterization of extreme positive linear systems for which the $k$th CG residual achieves the bound is also presented.
References
- Owe Axelsson, Iterative solution methods, Cambridge University Press, Cambridge, 1994. MR 1276069, DOI 10.1017/CBO9780511624100
- 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.
- Peter Borwein and Tamás Erdélyi, Polynomials and polynomial inequalities, Graduate Texts in Mathematics, vol. 161, Springer-Verlag, New York, 1995. MR 1367960, DOI 10.1007/978-1-4612-0793-1
- James W. Demmel, Applied numerical linear algebra, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1997. MR 1463942, DOI 10.1137/1.9781611971446
- 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, Mitt. Inst. Angew. Math. Zürich 8 (1959), 107. MR 145689
- D. K. Faddeev and V. N. Faddeeva, Computational methods of linear algebra, Zap. Naučn. Sem. Leningrad. Otdel. Mat. Inst. Steklov. 54 (1975), 3–228, 265 (Russian). Computational methods of linear algebra, Parallel computations. MR 0400669
- Gene H. Golub and Charles F. Van Loan, Matrix computations, 3rd ed., Johns Hopkins Studies in the Mathematical Sciences, Johns Hopkins University Press, Baltimore, MD, 1996. MR 1417720
- I. S. Gradshteyn and I. M. Ryzhik, Table of integrals, series, and products, 6th ed., Academic Press, Inc., San Diego, CA, 2000. Translated from the Russian; Translation edited and with a preface by Alan Jeffrey and Daniel Zwillinger. MR 1773820
- A. Greenbaum, Comparison of splittings used with the conjugate gradient algorithm, Numer. Math. 33 (1979), no. 2, 181–193. MR 549448, DOI 10.1007/BF01399553
- Anne Greenbaum, Iterative methods for solving linear systems, Frontiers in Applied Mathematics, vol. 17, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1997. MR 1474725, DOI 10.1137/1.9781611970937
- Magnus R. Hestenes and Eduard Stiefel, Methods of conjugate gradients for solving linear systems, J. Research Nat. Bur. Standards 49 (1952), 409–436 (1953). MR 0060307
- I. C. F. Ipsen, Expressions and bounds for the GMRES residual, BIT 40 (2000), no. 3, 524–535. MR 1780406, DOI 10.1023/A:1022371814205
- Shmuel Kaniel, Estimates for some computational techniques in linear algebra, Math. Comp. 20 (1966), 369–378. MR 234618, DOI 10.1090/S0025-5718-1966-0234618-4
- 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/.
- —, Vandermonde matrices with Chebyshev nodes, Technical Report 2005-02, Department of Mathematics, University of Kentucky, 2005, Available athttp://www.ms.uky.edu/~math/MAreport/, Lin. Alg. Appl., to appear.
- J. Liesen, M. Rozložník, and Z. Strakoš, Least squares residuals and minimal residual methods, SIAM J. Sci. Comput. 23 (2002), no. 5, 1503–1525. MR 1885072, DOI 10.1137/S1064827500377988
- Jörg Liesen and Petr Tichý, The worst-case GMRES for normal matrices, BIT 44 (2004), no. 1, 79–98. MR 2057363, DOI 10.1023/B:BITN.0000025083.59864.bd
- Günter Meinardus, Über eine Verallgemeinerung einer Ungleichung von L. V. Kantorowitsch, Numer. Math. 5 (1963), 14–23 (German). MR 160311, DOI 10.1007/BF01385875
- Yousef Saad, Iterative methods for sparse linear systems, 2nd ed., Society for Industrial and Applied Mathematics, Philadelphia, PA, 2003. MR 1990645, DOI 10.1137/1.9780898718003
- 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–278. MR 1407670, DOI 10.1016/0024-3795(94)00360-2
- G. W. Stewart and Ji Guang Sun, Matrix perturbation theory, Computer Science and Scientific Computing, Academic Press, Inc., Boston, MA, 1990. MR 1061154
- Lloyd N. Trefethen and David Bau III, Numerical linear algebra, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1997. MR 1444820, DOI 10.1137/1.9780898719574
- K. Zhou, J. C. Doyle, and K. Glover, Robust and optimal control, Prentice Hall, 1995.
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
- 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.
- © Copyright 2007
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication. - Journal: Math. Comp. 77 (2008), 335-352
- MSC (2000): Primary 65F10
- DOI: https://doi.org/10.1090/S0025-5718-07-01922-9
- MathSciNet review: 2353956