Backward perturbation bounds for linear least squares problems

Recently, Higham, Walden, Karlson, and Sun have provided formulas for computing the best backward perturbation bounds for the linear least squares problem. In this paper we provide several backward perturbation bounds that are easier to compute and optimal up to a factor less than 2. We also show that any least squares algorithm that is stable in the sense of Stewart is necessarily a backward stable algorithm. Our results make it possible to measure numerically the amount of accuracy in any alleged solution of a least squares problem.