The convergence of inexact Chebyshev and Richardson iterative methods for solving linear systems

Gene H. Golub, Michael L. Overton

Research output: Contribution to journalArticle

Abstract

The Chebyshev and second-order Richardson methods are classical iterative schemes for solving linear systems. We consider the convergence analysis of these methods when each step of the iteration is carried out inexactly. This has many applications, since a preconditioned iteration requires, at each step, the solution of a linear system which may be solved inexactly using an "inner" iteration. We derive an error bound which applies to the general nonsymmetric inexact Chebyshev iteration. We show how this simplifies slightly in the case of a symmetric or skew-symmetric iteration, and we consider both the cases of underestimating and overestimating the spectrum. We show that in the symmetric case, it is actually advantageous to underestimate the spectrum when the spectral radius and the degree of inexactness are both large. This is not true in the case of the skew-symmetric iteration. We show how similar results apply to the Richardson iteration. Finally, we describe numerical experiments which illustrate the results and suggest that the Chebyshev and Richardson methods, with reasonable parameter choices, may be more effective than the conjugate gradient method in the presence of inexactness.

Original languageEnglish (US)
Pages (from-to)571-593
Number of pages23
JournalNumerische Mathematik
Volume53
Issue number5
DOIs
StatePublished - Aug 1988

Keywords

  • Subject Classifications: AMS(MOS): 65F10, CR: G1.3

ASJC Scopus subject areas

  • Computational Mathematics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'The convergence of inexact Chebyshev and Richardson iterative methods for solving linear systems'. Together they form a unique fingerprint.

  • Cite this