Abstract
This paper presents a special purpose dual algorithm for obtaining a Chebychev approximation to an overdetermined system of linear equations. The method is founded on the principles of linear programming and is designed to take advantage of the problem's special structure. It is shown that, while maintaining a reduced basis, certain iterations of the standard dual algorithm may be combined into one. Two computer code implementations of the method are discussed and a computational comparison with another algorithm for Chebychev approximation is given.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
R.D. Armstrong and D.S. Kung, “Min—max estimates for a linear multiple regression problem”,Applied Statistics 1 (1979) 93–100.
I. Barrodale and C. Phillips, “Solution of an overdetermined system of linear equations in the Chebyshev norm”,ACM Transactions on Mathematical Software 1(3) (1975) 264–270.
R.H. Bartels and G.H. Golub, “The simplex method of linear programming using LU decomposition”,Communications of the ACM 12 (1969) 266–268.
A. Ben-Israel and A. Charnes, “An explicit solution of a special class of linear programming problems”,Operations Research 16 (1968) 1166–1175.
P.T. Boggs, “A new algorithm for the Chebyshev solution of over-determined linear systems”,Mathematics of Computation 28 (1974) 203–217.
A. Charnes, “Optimality and degeneracy in linear programming”,Econometrica 20 (1952) 160–170.
A.K. Cline, “A descent method for the uniform solution to over-determined systems of linear equations”,SIAM Journal on Numerical Analysis 13 (1976) 293–309.
S. Forsythe and C.B. Moler,Computer solution of linear algebraic systems (Prentice-Hall, Englewood Cliffs, NJ, 1967).
J. Gilsinn, K. Hoffman, R.H.F. Jackson, E. Leyendecker, P. Saunders and D. Shier, “Computational comparisons ofL 1 approximation codes: A test case”, paper presented at ORSATIMS conference (Atlanta, GA, November 1977).
L.S. Lasdon,Optimization theory for large systems (Macmillan Company, New York, 1970).
D. Moursund, “Chebyshev solution ofn + 1 linear equations inn unknowns”,Journal of the Association for Computing Machinery 12 (1965) 383–387.
P. Rabinowitz, “Applications of linear programming to numerical analysis”,SIAM Review 10 (1968) 121–159.
E. Stiefel, “Methods—old and new—for solving the Tschebyscheff approximation problem”,SIAM Journal on Numerical Analysis 1 (1964) 164–176.
E. Stiefel, “Note on Jordan elimination, linear programming and Tschebyscheff approximation”,Numerische Mathematik 2 (1960) 1–17.
E. Stiefel, “Uber diskrete und lineare Tschebyscheff Approximationen”,Numerische Mathematik 1 (1959) 1–28.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Armstrong, R.D., Kung, D.S. A dual method for discrete Chebychev curve fitting. Mathematical Programming 19, 186–199 (1980). https://doi.org/10.1007/BF01581640
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01581640