On the stability of sequential updates and downdates

Author

Stewart, G.W.

Author_Institution

Dept. of Comput. Sci., Maryland Univ., College Park, MD, USA

Volume

43

Issue

11

fYear

1995

fDate

11/1/1995 12:00:00 AM

Firstpage

2642

Lastpage

2648

Abstract

The updating and downdating of Cholesky decompositions has important applications in a number of areas. There is essentially one standard updating algorithm, based on plane rotations, which is backward stable. Three downdating algorithms have been treated in the literature: the LINPACK algorithm, the method of hyperbolic transformations, and Chambers´ (1971) algorithm. Although none of these algorithms is backward stable, the first and third satisfy a relational stability condition. It is shown that relational stability extends to a sequence of updates and downdates. In consequence, other things being equal, if the final decomposition in the sequence is well conditioned, it will be accurately computed, even though intermediate decompositions may be almost completely inaccurate. These results are also applied to the two-sided orthogonal decompositions, such as the URV decomposition

Keywords

error analysis; matrix decomposition; numerical stability; roundoff errors; sequences; Chambers´ algorithm; Cholesky decompositions; LINPACK algorithm; URV decomposition; backward stable algorithm; downdating algorithms; hyperbolic transformations; matrix decomposition; plane rotations; relational stability condition; rounding error analysis; sequential downdates; sequential updates; stability; two-sided orthogonal decompositions; updating algorithm; Algorithm design and analysis; Arithmetic; Error analysis; Error correction; Least squares methods; Matrix decomposition; Null space; Roundoff errors; Sociotechnical systems; Stability;

fLanguage

English

Journal_Title

Signal Processing, IEEE Transactions on

Publisher

ieee

ISSN

1053-587X

Type

jour

DOI

10.1109/78.482114

Filename

482114