Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Numerical Algorithms
Published in: Numerical Algorithms 4/2020

16-12-2019 | Original Paper

On prescribing the convergence behavior of the conjugate gradient algorithm

Author: Gérard Meurant

Published in: Numerical Algorithms | Issue 4/2020

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

The conjugate gradient (CG) algorithm is the most frequently used iterative method for solving linear systems Ax = b with a symmetric positive definite (SPD) matrix. In this paper we construct real symmetric positive definite matrices A of order n and real right-hand sides b for which the CG algorithm has a prescribed residual norm convergence curve. We also consider prescribing as well the A-norms of the error. We completely characterize the tridiagonal matrices constructed by the Lanczos algorithm and their inverses in terms of the CG residual norms and A-norms of the error. This also gives expressions and lower bounds for the ℓ2 norm of the error. Finally, we study the problem of prescribing both the CG residual norms and the eigenvalues of A. We show that this is not always possible. Our constructions are illustrated by numerical examples.
previous article On the residual norms, the Ritz values and the harmonic Ritz values that can be generated by restarted GMRES
next article Simple stopping criteria for the LSQR method applied to discrete ill-posed problems

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now
Literature
1.
Arioli, M., Pták, V., Strakoš, Z.: Krylov sequences of maximal length and convergence of GMRES. BIT Numer. Math. 38(4), 636–643 (1998)MathSciNetMATH
2.
Arnoldi, W.E.: The principle of minimized iterations in the solution of the matrix eigenvalue problem. Quart. Appl. Math. 9, 17–29 (1951)MathSciNetMATH
3.
Baranger, J., Duc-Jacquet, M.: Matrices tridiagonales symétriques et matrices factorisables. RIRO 3, 61–66 (1971)MATH
4.
Duintjer Tebbens, J., Meurant, G.: Any Ritz value behavior is possible for Arnoldi and for GMRES. SIAM J. Matrix Anal. Appl. 33(3), 958–978 (2012)MathSciNetMATH
5.
Duintjer Tebbens, J., Meurant, G.: Prescribing the behavior of early terminating GMRES and Arnoldi iterations. Numer. Algorithms 65(1), 69–90 (2014)MathSciNetMATH
6.
Duintjer Tebbens, J., Meurant, G.: On the convergence of Q-OR and Q-MR Krylov methods for solving linear systems. BIT Numer. Math. 56(1), 77–97 (2016)MathSciNetMATH
7.
8.
Golub, G.H., Meurant, G: Matrices, Moments and Quadrature with Applications. Princeton University Press (2010)
9.
Greenbaum, A., Strakoš, Z.: Matrices that generate the same Krylov residual spaces. In: Golub, G.H., Greenbaum, A., Luskin, M. (eds.) Recent Advances in Iterative Methods, pp 95–118. Springer (1994)
10.
Greenbaum, A., Pták, V., Strakoš, Z.: Any convergence curve is possible for GMRES. SIAM J. Matrix Anal. Appl. 17(3), 465–470 (1996)MathSciNetMATH
11.
Hestenes, M.R., Stiefel, E.: Methods of conjugate gradients for solving linear systems. J. Nat. Bur. Standards 49(6), 409–436 (1952)MathSciNetMATH
12.
13.
Juárez-Ruiz, E., Cortés-Maldonado, R., Pérez-Rodríguez, F.: Relationship between the inverses of a matrix and a submatrix. Computación y Sistemas 20(2), 251–262 (2016)
14.
Lanczos, C.: Solution of systems of linear equations by minimized iterations. J. Res. Nat. Bur. Standards 49, 33–53 (1952)MathSciNet
15.
Liesen, J., Strakoš, Z: Krylov Subspace Methods, Principles and Analysis. Oxford University Press (2013)
16.
Meurant, G.: A review on the inverse of tridiagonal and block tridiagonal symmetric matrices. SIAM J. Matrix Anal. Appl. 13(3), 707–728 (1992)MathSciNetMATH
17.
Meurant, G.: Numerical experiments in computing bounds for the norm of the error in the preconditioned conjugate gradient algorithm. Numer. Algorithms 22, 353–365 (1999)MathSciNetMATH
18.
Meurant, G.: The Lanczos and Conjugate Gradient Algorithms from Theory to Finite Precision Computations. SIAM, Philadelphia (2006)MATH
19.
Meurant, G., Strakoš, Z.: The Lanczos and conjugate gradient algorithms in finite precision arithmetic. Acta Numerica 15, 471–542 (2006)MathSciNetMATH
20.
Paige, C.C.: The Computation of Eigenvalues and Eigenvectors of Very Large Sparse Matrices. University of London, Ph.D. thesis (1971)
21.
Paige, C.C., Saunders, M.A.: Solution of sparse indefinite systems of linear equations. SIAM J. Numer. Anal. 12(4), 617–629 (1975)MathSciNetMATH
22.
Saad, Y.: Krylov subspace methods for solving large nonsymmetric linear systems. Math. Comp. 37, 105–126 (1981)MathSciNetMATH
23.
Saad, Y.: Practical use of some Krylov subspace methods for solving indefinite and nonsymmetric linear systems. SIAM J. Sci. Statist. Comput. 5(1), 203–228 (1984)MathSciNetMATH
24.
Schweitzer, M.: Any finite convergence curve is possible in the initial iterations of restarted FOM. Electron. Trans. Numer. Anal. 45, 133–145 (2016)MathSciNetMATH
25.
Strakoš, Z., Tichý, P.: On error estimates in the conjugate gradient method and why it works in finite precision computations. Electron. Trans. Numer. Anal. 13, 56–80 (2002)MathSciNetMATH
Metadata
Title
On prescribing the convergence behavior of the conjugate gradient algorithm
Author
Gérard Meurant
Publication date
16-12-2019
Publisher
Springer US
Published in
Numerical Algorithms / Issue 4/2020
Print ISSN: 1017-1398
Electronic ISSN: 1572-9265
DOI
https://doi.org/10.1007/s11075-019-00851-2

Other articles of this Issue 4/2020

Numerical Algorithms 4/2020 Go to the issue

Original Paper

Golub–Kahan bidiagonalization for ill-conditioned tensor equations with applications

Original Paper

Mixed finite element methods for the Oseen problem

Original Paper

Extended nonsymmetric global Lanczos method for matrix function approximation

Original Paper

Some unusual results on extrapolation methods

Original Paper

FDEMtools: a MATLAB package for FDEM data inversion

Original Paper

Krylov subspace projection method for Sylvester tensor equation with low rank right-hand side

Premium Partner

    Image Credits