Browse Prior Art Database

STATIONARY ITERATIVE METHODS FOR LINEAR SYSTEMS WITH NON-HERMITIAN SINGULAR MATRICES

IP.com Disclosure Number: IPCOM000128689D
Original Publication Date: 1975-Dec-31
Included in the Prior Art Database: 2005-Sep-16
Document File: 9 page(s) / 26K

Publishing Venue

Software Patent Institute

Related People

R. J. Plemmons: AUTHOR [+3]

Abstract

Iterative methods are considered for approximatinq a (least-squares) solution to a system of linear equations Ax = b, based upon the splitting A = M - N with A in general a singular matrix while M is chosen to be nonsingular. Some necessary and sufficient conditions for convergence of the iteration x(i+l) = M-lNxM + M-lb to some ~', depending on x(o), for every x(o'), are given, that do not require that A be Hem-itian nor positive semidefinite. The discrete Neumann problem in a rectangular region is used as an example to illustrate the applications of these convergence criteria.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 22% of the total text.

Page 1 of 9

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

STATIONARY ITERATIVE METHODS FOR LINEAR SYSTEMS WITH NON- HERMITIAN SINGULAR MATRICES

R. J. Plemmons

CS-75-1 March 1975

STATIONARY ITERATIVE METHODS FOR LINEAR

SYSTEMS WITH NON-HERMITIAN SINGULAR MATRICES

R. J. Plemmons*

Department of Computer Science The University of Tennessee Knoxville, Tennessee 37916

Key Words and Phrases: Consistent linear system, discrete Neumann problem, iterative methods, positive semidefinite matrix, singular matrix.

A. M. S. Subject Classifications (1970): 65FO5, 65GO5

Computing Review Categories: 5.11, 5.14.

This research was supported by the U. S. Army Research Office - Durham, under contract no. DAHC04-74-C-0019.

ABSTRACT

Iterative methods are considered for approximatinq a (least-squares) solution to a system of linear equations Ax = b, based upon the splitting A = M - N with A in general a singular matrix while M is chosen to be nonsingular. Some necessary and sufficient conditions for convergence of the iteration x(i+l) = M-lNxM + M-lb to some ~', depending on x(o), for every x(o'), are given, that do not require that A be Hem-itian nor positive semidefinite. The discrete Neumann problem in a rectangular region is used as an example to illustrate the applications of these convergence criteria.

1. INTRODUCTION

Systems of linear equations with a singular matrix arise in a wide variety of applications. There are many problems, such as the Neumann problem and those for elastic bodies with free surfaces and Poisson's equation on a sphere, whose finite difference formulations lead to singular systems. such problems have been studied in several contexts

in [21, 131, [51, [61, [71, (81, [111 and [121. Consider,the linear system (1.1)

(Equation Omitted)

University of Tennessee Page 1 Dec 31, 1975

Page 2 of 9

STATIONARY ITERATIVE METHODS FOR LINEAR SYSTEMS WITH NON-HERMITIAN SINGULAR MATRICES

where the matrix A is square and singular and where beR(A), the range of A, so that the system is consistent. If one splits the matrix A into

(1.2)

(Equation Omitted)

with M nonsingular, and sets T WIN then there results the natural linear stationary iteration (1.3

(Equation Omitted)

In the case where A is nonsingular a necessary and sufficient condition for the iteration (1.3) to con.verge to the solution to (1.1) for every initial approximation x(o) is that the spectral radius, p(T), of the iteration matrix T be less than one, so that the nowers of T converge to the matrix of all zeroes. However, this is not the case when A is singular. The following results, which are basically from [51 and [131, establish some preliminary convergence criteria. Lemma 1. Consider the splitting (1.2) of A with, M nonsingular and let

(Equation Omitted)

. Then tne following statements are equivalent:

(i) The powers of T converge to a projection matrix onto the null space of

(Equation Omitted)

(ii) There is a complement N7(A) of N(A) such that

(Equation Omitted)

(iii) The ei...