Updating Techniques for Solving Linear Least Squares Problems with Equality Constraints

Abstract

Linear least squares (LLS) problem is a computational problem of wide scale importance in the field of numerical linear algebra. Such problem often arises in real world applications subject to some equality constraints and is known as linear least squares problem with equality constraints (LSE). In this work, updating techniques based on QR factorization are considered as a solution tool for LSE problem. The LSE problem is first transformed into the weighted LLS problem using a suitable weighted factor w and then its solution is ap proximated by the updating techniques. The proposed updating algorithms are mainly based on Householder QR factorization. The original problem is partition into a small subproblem and then its QR factorization is com puted. The removed block of columns and rows are appended respectively and then updated the QR factorization to get the solution of the original problem. The proposed algorithms contain repeatedly updating of the QR factorization to approximate the solution of LSE problem. Moreover, the solution of an equivalent formulation of LSE problem possessing the saddle point structure is computed using updating of the QR factorization. The proposed algorithms are implemented in MATLAB and the error analysis has been carried out to study their accuracy and stability