On Cline’s Direct Method for Solving Overdetermined Linear Systems in the L_∞ Sense

An algorithm is presented for computing a vector x which satisfies a given m × n(m > n 2) linear system in the sense that the L_∞ norm of the residual vector is minimized. That is, letting a₁ , ⋯ ,aₘ be the columns of a matrix A, each column being of length n, and letting β ₁ , ⋯ ,β ₘ be the components of a vector b, we wish to find a vector x which minimizes \[φ (x) = ||A^T x - b||_∞ = {max }_i |a_i^T x - β _i |.\] The proposed algorithm is a direct (i.e. descent) method which minimizes the function φ in a finite number of steps. It is closely related to Cline’s algorithm for the above problem: The algorithm represents an improvement over others which proceed by directly minimizing the function φ in that it employs recent advances in the use of fast Givens transformations to update orthogonal matrix factorizations. This permits the work per cycle in the algorithm to be reduced without sacrificing numerical stability. Further, the method does not require the Haar condition, and it permits the easy accommodation of linear equality and inequality constraints. The method has the disadvantage, which appears characteristic of direct methods for the L_∞ problem, that if often requires many more steps to arrive at a solution for data-fitting problems than do indirect (i.e. ascent) methods. This is indicated by some comparisons with Stiefel’s method and with the method due to Barrodale and Phillips.