zbMATH — the first resource for mathematics

The rate of convergence of conjugate gradients. (English) Zbl 0596.65015
Authors’ summary: It has been observed that the rate of convergence of conjugate gradients increases when one or more of the extreme Ritz values have sufficiently converged to the corresponding eigenvalues (the ”superlinear convergence” of CG). In this paper this will be proved and made quantitative. It will be shown that a very modest degree of convergence of an extreme Ritz value already suffices for an increased rate of convergence to occur.
Reviewer: W.Niethammer

65F10 Iterative numerical methods for linear systems
Full Text: DOI EuDML
[1] Concus, P., Golub, G.H., O’Leary, D.P.: A generalized Conjugate Gradient method for the numerical solution of elliptic partial differential equations. In: Sparse Matrix Computations (J.R. Bunch and D.J. Rose, eds.), pp. 309-332. New York: Academic Press 1976
[2] Golub, G.H., Van Loan, C.F.: Matrix Computations. Oxford: North Oxford Academic 1983
[3] Hayes, R.M.: Iterative methods of solving linear problems on Hilbert space. National Bureau of Standards, Appl. Math. Ser.,39, 71-103 (1954) · Zbl 0058.10703
[4] Hestenes, M.R., Stiefel, E.: Methods of conjugate gradients for solving linear systems. J. Res. Natl. Bur. Stand.49, 409-436 (1952) · Zbl 0048.09901
[5] Kaniel, S.: Estimates for some computational techniques in linear algebra. Math. Comput.20, 369-378 (1966) · Zbl 0156.16202 · doi:10.1090/S0025-5718-1966-0234618-4
[6] Karush, W.: An iterative method for finding characteristic vectors of a symmetric matrix. Pacific J. Math.1, 233-248 (1950) · Zbl 0043.01602
[7] Karush, W.: Convergence of a method of solving linear problems. Proc. Amer. Math. Soc.3, 839-851 (1952) · Zbl 0048.09504 · doi:10.1090/S0002-9939-1952-0055794-4
[8] Meinardus, G.: Über eine Verallgemeinerung einer Ungleichung von L.V. Kantorovitch. Numer. Math.5, 14-23 (1963) · Zbl 0114.32001 · doi:10.1007/BF01385875
[9] Meyerink, J.A., van der Vorst, H.A.: An iterative solution method for linear systems of which the coefficient matrix is a symmetricM-matrix. Math. Comput.31, 148-162 (1977) · Zbl 0349.65020
[10] Parlett, B.N.: The Symmetric Eigenvalue Problem. Englewood Cliffs: Prentice Hall 1980 · Zbl 0431.65017
[11] Parlett, B.N., Simon, H., Stringer, L.M.: On estimating the largest eigenvalue with the Lanczos Algorithm. Math. Comput.38, 153-165 (1982) · Zbl 0476.65024 · doi:10.1090/S0025-5718-1982-0637293-9
[12] Saad, Y.: On the rates of convergence of the Lanczos and Block Lanczos methods. SIAM J. Numer. Anal.17, 687-706 (1980) · Zbl 0456.65016 · doi:10.1137/0717059
[13] van der Sluis, A., van der Vorst, H.A.: The convergence behaviour of Ritz values in the presence of close eigenvalues. (To be published) · Zbl 0632.65035
[14] Winther, R.: Some superlinear convergence results for the conjugate gradient methods. SIAM J. Numer. Anal.17, 14-17 (1980) · Zbl 0447.65021 · doi:10.1137/0717002
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.