Abstract: A new approach to error analysis is introduced, based on the observation that many numerical procedures can be interpreted as computations of products in a suitable Lie group. The absence of an additive error law for such procedures is intimately related to the nonexistence of bi-invariant metrics on the relevant groups. Introducing the notion of an almost Inn$(G)$ invariant metric (a left invariant, almost Inn$(G)$ invariant metric can be constructed on an arbitrary matrix Lie group), we show how error analysis can nevertheless be done for such procedures. We illustrate for what we call "scalar calculations without writing to memory"; the Horner algorithm for evaluation of a polynomial is such a calculation, and we give explicit error bounds for a floating point implementation of the Horner algorithm, and demonstrate their usefulness numerically. A left invariant, almost Inn$(G)$ invariant metric on a group induces a metric on a homogeneous space of the group with useful properties for error analysis; treating $ R$ as a homogeneous space of the group of affine transformations of $ R$ we compute a new metric that unifies absolute and relative error.
Classification (MSC2000): 65G99
Full text of the article: