Finite precision behavior of stationary iteration for solving singular systems

Nicholas J. Higham*, Philip A. Knight

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

19 Citations (Scopus)

Abstract

A stationary iterative method for solving a singular system Ax=b converges for any starting vector if limi→∞Gi exists, where G is the iteration matrix, and the solution to which it converges depends on the starting vector. We examine the behavior of stationary iteration in finite precision arithmetic. A pertubation bound for singular systems is derived and used to define forward stability of a numerical method. A rounding error analysis enables us to deduce conditions under which a stationary iterative method is forward stable or backward stable. The component of the forward error in the null space of A can grow linearly with the number of iterations, but it is innocuous as long as the iteration converges reasonably quickly. As special cases, we show that when A is symmetric positive semidefinite the Richardson iteration with optimal parameter is forward stable, and if A also has unit diagonal and property A, then the Gauss-Seidel method is both forward and backward stable. Two numerical examples are given to illustrate the analysis.

Original languageEnglish
Pages (from-to)165-186
Number of pages22
JournalLinear Algebra and its Applications
Volume192
DOIs
Publication statusPublished - 31 Oct 1993

Keywords

  • stationary iterative method
  • singular systems
  • error analysis

Fingerprint

Dive into the research topics of 'Finite precision behavior of stationary iteration for solving singular systems'. Together they form a unique fingerprint.

Cite this