On the Stability of Sequential Updates and Downdates

Loading...
Thumbnail Image

Files

CS-TR-3238.ps (176.03 KB)
No. of downloads: 175
CS-TR-3238.pdf (185.67 KB)
No. of downloads: 721

Publication or External Link

Date

1998-10-15

Advisor

Citation

DRUM DOI

Abstract

The updating and downdating of QR decompositions has important applications in a number of areas. There is essentially one standard updating algorithm, based on plane rotations, which is backwards stable. Three downdating algorithms have been treated in the literature: the LINPACK algorithm, the method of hyperbolic transformations, and Chambers' algorithm. Although none of these algorithms is backwards stable, the first and third satisfy a relational stability condition. In this paper, 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. (Also cross-referenced as UMIACS-TR-94-30)

Notes

Rights