A new approach for the analysis of the propagation of round-off errors in recursive algorithms is presented. This approach is based on the concept of backward consistency. In general, this concept leads to a decomposition of the state space of the algorithm, and in fact, to a manifold. This manifold is the set of state values that are backward consistent. Perturbations within the manifold can be interpreted as resulting from perturbations on the input data. Hence, the error propagation on the manifold corresponds exactly (without averaging or even linearization) to the propagation of the effect of a perturbation of the input data at some point in time on the state of the algorithm at future times. These ideas are applied to the Kalman filter and its various derivatives. The Chandrasekhar equations, which apply to time-invariant state-space models are then considered. The author also considers in detail two groups of fast RLS algorithms: the fast transversal filter algorithms and the fast lattice/fast QR RLS algorithms.
This paper is published in Optical engineering, Volume 31, N° 6, June 1992 and is made available as an electronic preprint with permission of SPIE. One print or electronic copy may be made for personal use only. Systematic or multiple reproduction, distribution to multiple locations via electronic or other means, duplication of any material in this paper for a fee or for commercial purposes, or modification of the content of the paper are prohibited.
