Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

ROUND-OFF ERROR ANALYSIS OF ITERATIONS FOR LARGE LINEAR SYSTEMS

IP.com Disclosure Number: IPCOM000147963D
Original Publication Date: 1977-Apr-30
Included in the Prior Art Database: 2007-Mar-28

Publishing Venue

Software Patent Institute

Related People

Wozniakowski, H.: AUTHOR [+2]

Abstract

ROUND-OFF ERROR ANALYSIS OF ITERATIONS FOR M G E LINEAR SYSTEMS H. ~oiniakoweki Department of Computer Science Carnegie-Mellon University Pittsburgh, Pennsylvania 15213 April 1977 This work was partly done during the author's visit at Carnegie-Mellon University and it was supported in part by the Office of Naval Research under Contract N00014-764-0370; NR 044-422 and by the National Science Foundation under Grant MCS75-222-55. ABSTRACT We deal with the rounding error analysis of successive approximation iterations for the solution of large linear systems Ax b. We prove that Jacobi, Richardson, Gauss-Seidel and SOR iterations are numerically stable whenever A A 0 and A has Property A. This means that the computed result xk approximates the exact solutim awith relative error of order 51bll lb'lll where C is the relative computer preci~ion. However with the exception of Gauss-Seidel iteration the residual vector b is of order 6 1blf lb- 11 lbll and hence the remaining three iterations are not well-behaved.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 15% of the total text.

Page 1 of 27

   ROUND-OFF ERROR ANALYSIS OF
ITERATIONS FOR M G E LINEAR SYSTEMS

      H. ~oiniakoweki
Department
of Computer Science
Carnegie-Mellon University
Pittsburgh, Pennsylvania 15213

April 1977

This work was partly done during the author's visit at Carnegie-Mellon
University and it was supported in part by the Office of Naval Research
under Contract
N00014-764-0370; NR 044-422 and by the National Science
Foundation
under Grant MCS75-222-55.

[This page contains 1 picture or other non-text object]

Page 2 of 27

ABSTRACT

    We deal with the rounding error analysis of successive approximation iterations for the solution of large linear systems Ax = b. We prove that Jacobi, Richardson, Gauss-Seidel and SOR iterations are numerically stable

*

whenever A = A > 0 and A has Property A. This means that the computed result xk approximates the exact solutim awith relative error of order

51bll lb'lll where C is the relative computer preci~ion. However with the exception of Gauss-Seidel iteration the residual vector b is of order

6 1blf lb- ' 11 lbll and hence the remaining three iterations are not well-behaved.

[This page contains 1 picture or other non-text object]

Page 3 of 27

   This paper deals with the rounding error analysie in floating point arithmetic of successive approximation iterations for the solution of l~rge
sparse linear systems Ax b.

    We summarize the results of this paper. Basic concepts of numerical stability and good-behavior are recalled in Section 2. We give necessary
and sufficient conditions for numerical stability and good-behavior in Sections 3 and 5. In Section 4 we deal with several examples of eucceesive approximation iterations. We prove that Jacobi, Richardeon, Gauss-Seidel

*

and SOR iterations are numerically stable whenever A A > 0 and A has Property A. In Section 6 we show rhat with the exception of Gauss-Seidel
iteration they are not well-behaved. In the last section we indicate rhat good-behavior of any numerically stable method can be achieved by the use
of iterative refinement even if all computations are performed in single
precis ion.

[This page contains 1 picture or other non-text object]

Page 4 of 27

2. PRELIMINARIES

    In this section we briefly recall what we mean by numerical etability and good-behavior of an iteration for solving a linear system Ax m b where

A
is a n X n
nonsingular complex matrix and b is a n x 1 vector. We shall

assume throughout this paper that I(*I( denotes the spectral norm.

   Let {\] be a computed sequence of successive approxhtions of the solu-
tion rr = ~ ~ l b
by an iteration cp in t digit floating point iarithmetic £1, 8ea

Wilkinson [63].
An iteration C+Y is called numerically stable if

where C 2-t is the relative computer precision, is a conerant which
=I

depends only on the size n of the problem, and cond(b) = (1 A(]

-

the condition number of A.

   An iteration tp is called well-behaved (or...