On Cline’s Direct Method for Solving Overdetermined Linear Systems in the $L_\infty $ Sense
Richard H. Bartels, Andrew R. Conn, Christakis Charalambous · SIAM Journal on Numerical Analysis · 1978
An algorithm is presented for computing a vector x which satisfies a given $m \times n(m > n \geqq 2)$ linear system in the sense that the $L_\infty $ norm of the residual vector is minimized. That is, letting $a_1 , \cdots ,a_m $ be the columns of a matrix A, each column being of length n, and letting $\beta _1 , \cdots ,\beta _m $ be the components of a vector b, we wish to find a vector x which minimizes \[\phi (x) = ||A^T x - b||_\infty = \mathop {\max }\limits_i |a_i^T x - \beta _i |.\] The proposed algorithm is a direct (i.e. descent) method which minimizes the function $\phi $ 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 $\phi $ 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_\infty $ 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.