TY - JOUR
T1 - On the stability of sequential updates and downdates
JF - Signal Processing, IEEE Transactions on
Y1 - 1995
A1 - Stewart, G.W.
KW - algorithm;Cholesky
KW - algorithm;downdating
KW - algorithm;error
KW - algorithm;URV
KW - algorithms;hyperbolic
KW - analysis;matrix
KW - analysis;sequential
KW - Chambers'
KW - condition;rounding
KW - decomposition;backward
KW - decomposition;numerical
KW - decomposition;plane
KW - decompositions;LINPACK
KW - decompositions;updating
KW - downdates;sequential
KW - error
KW - errors;sequences;
KW - orthogonal
KW - rotations;relational
KW - stability
KW - stability;roundoff
KW - stable
KW - transformations;matrix
KW - updates;stability;two-sided
AB - 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
VL - 43
SN - 1053-587X
CP - 11
M3 - 10.1109/78.482114
ER -