Numerical stability properties of a QR-based fast least squares algorithm

Abstract

The numerical stability of a recent QR-based fast least-squares algorithm is established from a backward stability perspective. A stability domain approach applicable to any least-squares algorithm, constructed from the set of reachable states in exact arithmetic, is presented. The error propagation question is shown to be subordinate to a backward consistency constraint, which requires that the set of numerically reachable variables be contained within the stability domain associated to the algorithm. This leads to a conceptually lucid approach to the numerical stability question which frees the analysis of stationary assumptions on the filtered sequences and obviates the tedious linearization methods of previous approaches. Moreover, initialization phenomena and considerations related to poorly exciting inputs admit clear interpretations from this perspective. The algorithm under study is proved, in contrast to many fast algorithms, to be minimal.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>