Computing projections via Householder transformations and Gram–Schmidt orthogonalizations

Let x * denote the solution of a linear least‐squares problem of the form$$ {\rm minimize} \quad \|A{\bf x}-{\bf b}\|^{2}_{2}$$where A is a full rank m × n matrix, m > n . Let r *= b ‐ A x * denote the corresponding residual vector. In most problems one is satisfied with accurate computation of x *. Yet in some applications, such as affine scaling methods, one is also interested in accurate computation of the unit residual vector r */∥ r *∥ 2 . The difficulties arise when ∥ r *∥ 2 is much smaller than ∥ b ∥ 2 . Let x̂ and r̂ denote the computed values of x * and r *, respectively. Let εdenote the machine precision in our computations, and assume that r̂ is computed from the equality r̂ = b ‐ A x̂ . Then, no matter how accurate x̂ is, the unit residual vector û = r̂ /∥ r̂ ∥ 2 contains an error vector whose size is likely to exceed ε∥ b ∥ 2 /∥ r* ∥ 2 . That is, the smaller ∥ r* ∥ 2 the larger the error. Thus although the computed unit residual should satisfy A T û = 0 , in practice the size of ∥A T û ∥ 2 is about ε∥A∥ 2 ∥ b ∥ 2 /∥ r* ∥ 2 . The methods discussed in this paper compute a residual vector, r̂ , for which ∥A T r̂ ∥ 2 is not much larger than ε∥A∥ 2 ∥ r̂ ∥ 2 . Numerical experiments illustrate the difficulties in computing small residuals and the usefulness of the proposed safeguards. Copyright © 2004 John Wiley & Sons, Ltd.