TY - JOUR

T1 - Finite precision behavior of stationary iteration for solving singular systems

AU - Higham, Nicholas J.

AU - Knight, Philip A.

PY - 1993/10/31

Y1 - 1993/10/31

N2 - 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.

AB - 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.

KW - stationary iterative method

KW - singular systems

KW - error analysis

UR - http://www.scopus.com/inward/record.url?scp=21144483536&partnerID=8YFLogxK

U2 - 10.1016/0024-3795(93)90242-G

DO - 10.1016/0024-3795(93)90242-G

M3 - Article

AN - SCOPUS:21144483536

VL - 192

SP - 165

EP - 186

JO - Linear Algebra and its Applications

JF - Linear Algebra and its Applications

SN - 0024-3795

ER -