On the Stability of Sequential Updates and Downdates
On the Stability of Sequential Updates and Downdates
Files
Publication or External Link
Date
1998-10-15
Authors
Stewart, G. W.
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)