Browse Prior Art Database

Convergence of a Two-Stage Richardson Iterative Procedure for Solving Systems of Linear Equations

IP.com Disclosure Number: IPCOM000128208D
Original Publication Date: 1981-Dec-31
Included in the Prior Art Database: 2005-Sep-15
Document File: 11 page(s) / 32K

Publishing Venue

Software Patent Institute

Related People

Gene H. Golub: AUTHOR [+4]

Abstract

Consider the problem of solving a system of linear equations [Equation ommitted] by an iterative method, i.e. generating a sequence of approximations [Equation ommitted] such [Equation ommitted] Frequently it is useful to introduce a splitting k--co [Equation ommitted] where systems of the form (0.2) may be solved much more easily than the original system (0.1). When (0.1) arises from the discretization of a partial differential equation, such a splitting is often natural, with M and D1 corresponding to sepa-rate terms in the differential equation. The iterative method used to solve (0.1) can then be "preconditioned" by M, i.e. designed so that each step of this "outer" iteration involves solving a system of the form (0.2). Sometimes it is desirable to solve these systems (0.2) by "inner" iterative procedures. In this paper we consider using the second-order Richardson method for the outer iteration, and show how the rate of convergence of this iteration depends on the accuracy re-

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

Page 1 of 11

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

Convergence of a Two-Stage Richardson Iterative Procedure for Solving Systems of Linear Equations

Gene H. Golub and Michael. L. Overton

"_ September 1981 REPORT NO. 38 Presented at the Dundee Biennial Conference on Numerical Analysis, University of Dundee, Scotland, June 23-26, 1981. To appear in the Proceedings of the Conference, published by Springer-Verlag.

Computer Science Department, Stanford University, Stanford, California 94305, U.S.A. Supported in part by the United States Department of Energy contract DE-AT03-ER71030 and in part by the National Science Foundation grant MCS-78-11985.

Computer Science Department, Courant Institute of Mathematical Sciences.LJew York University, 251 Mercer St., New York, NY

10012, U.S.A. Supported in part by the United States Department of Energy contract DE-AC02- 76ER03077 and in part by the National Science Foundation grant MCS-81-01924. Convergence of a Two-Stage Richardson Iterative Procedure

for Solving Systems of Linear Equations. Gene H. Golub and Michael L. Overton'

0. Introduction

Consider the problem of solving a system of linear equations

(Equation Omitted)

by an iterative method, i.e. generating a sequence of approximations

(Equation Omitted)

such

(Equation Omitted)

Frequently it is useful to introduce a splitting k--co

(Equation Omitted)

where systems of the form (0.2) may be solved much more easily than the original system (0.1). When (0.1) arises from the discretization of a partial differential equation, such a splitting is often natural, with M and D1 corresponding to sepa-rate terms in the differential equation. The iterative method used to solve (0.1) can then be "preconditioned" by M, i.e. designed so that each step of this "outer" iteration involves solving a system of the form (0.2). Sometimes it is desirable to solve these systems (0.2) by "inner" iterative procedures. In this paper we consider using the second-order Richardson method for the outer iteration, and show how the rate of convergence of this iteration depends on the accuracy re-

New York University Page 1 Dec 31, 1981

Page 2 of 11

Convergence of a Two-Stage Richardson Iterative Procedure for Solving Systems of Linear Equations

Computer Science Department, Stanford University, Stanford, California 94305, U.S.A. Supported in part by the United States Department of Energy contract DE-AT03-ER71030 and in part by the National Science Foundation grant MCS-78-11985.

'Computer Science Department, Courant Institute of Mathematical Sciences New York University, 251 Mercer St., New York, NY 10012, U.S.A. Sup-ported in part by the United States Department of Energy contract DE-AC02-76ER03077 and in part by the National Science Foundation grant MCS-81-01924. - 2 -

quired for the inner iterations. To our knowledge analysis of this particular method has not been attempted previously. See Nichols (1973) for an analysis of more general schemes using inner and...