On Cline’s Direct Method for Solving Overdetermined Linear Systems in the $L_\infty $ Sense
Authors:
- Richard H. BartelsRBRichard H. Bartels
- Andrew R. ConnACAndrew R. Conn
- Christakis CharalambousCCChristakis Charalambous
- 1 April 1978
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Numerical Analysis
- Vol. 15 (2) , 255-270
Abstract
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.
Keywords
This publication has 10 references indexed in Scilit:
- Linearly Constrained Discrete I 1 ProblemsACM Transactions on Mathematical Software, 1980
- Minimization Techniques for Piecewise Differentiable Functions: The $l_1$ Solution to an Overdetermined Linear SystemSIAM Journal on Numerical Analysis, 1978
- An Efficient Method to Solve the Minimax Problem DirectlySIAM Journal on Numerical Analysis, 1978
- A Penalty Function Method Converging Directly to a Constrained OptimumSIAM Journal on Numerical Analysis, 1977
- A Descent Method for the Uniform Solution to Over-Determined Systems of Linear EquationsSIAM Journal on Numerical Analysis, 1976
- Algorithm 495: Solution of an Overdetermined System of Linear Equations in the Chebychev Norm [F4]ACM Transactions on Mathematical Software, 1975
- Methods for modifying matrix factorizationsMathematics of Computation, 1974
- Numerical Analysis: Stable numerical methods for obtaining the Chebyshev solution to an overdetermined system of equationsCommunications of the ACM, 1968
- An Algorithm for the Chebyshev Problem—With an Application to Concave ProgrammingManagement Science, 1967
- Note on Jordan elimination, linear programming and Tchebycheff approximationNumerische Mathematik, 1960