Row-wise backward stable elimination methods for the equality constrained least squares problem

It is well known that the solution of the equality constrained least square s (LSE) problem min(Bx=d) parallel to b - Ax parallel to(2) is the limit of the solution of the unconstrained weighted least squares problem [GRAPHICS] as the weight mu tends to infinity, assuming that [B-T A(T)](T) has full ra nk. We derive a method for the LSE problem by applying Householder QR facto rization with column pivoting to this weighted problem and taking the limit analytically, with an appropriate rescaling of rows. The method obtained i s a type of direct elimination method. We adapt existing error analysis for the unconstrained problem to obtain a row-wise backward error bound for th e method. The bound shows that, provided row pivoting or row sorting is use d, the method is well-suited to problems in which the rows of A and B vary widely in norm. As a by-product of our analysis, we derive a row-wise backw ard error bound of precisely the same form for the standard elimination met hod for solving the LSE problem. We illustrate our results with numerical t ests.