Computing the strict Chebyshev solution of overdetermined linear equations

Author:
Nabih N. Abdelmalek

Journal:
Math. Comp. **31** (1977), 974-983

MSC:
Primary 65F20

MathSciNet review:
0445803

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: A method for calculating the strict Chebyshev solution of overdetermined systems of linear equations using linear programming techniques is described. This method provides: (1) a way to determine, for the majority of cases, all the equations belonging to the characteristic set, (2) an efficient method to obtain the inverse of the matrix needed to calculate the strict Chebyshev solution, and (3) a way of recognizing when an element of the Chebyshev solution equals a corresponding element of the strict Chebyshev solution. As a result, in general, the computational effort is considerably reduced. Also the present method deals with full rank as well as rank deficient cases. Numerical results are given.

**[1]**Nabih N. Abdelmalek,*Chebyshev solution of overdetermined systems of linear equations*, Nordisk Tidskr. Informationsbehandling (BIT)**15**(1975), no. 2, 117–129. MR**0483357****[2]**Jean Descloux,*Approximations in 𝐿^{𝑝} and Chebyshev approximations*, J. Soc. Indust. Appl. Math.**11**(1963), 1017–1026. MR**0159172****[3]**C. S. DURIS, "An exchange method for solving Haar and non-Haar overdetermined linear equations in the sense of Chebyshev,"*Proc. ACM Nat. Conf.*, 1968, pp. 61-66.**[4]**C. S. Duris and M. G. Temple,*A finite step algorithm for determining the “strict” Chebyshev solution to 𝐴𝑥=𝑏*, SIAM J. Numer. Anal.**10**(1973), 690–699. MR**0329232****[5]**G. Hadley,*Linear programming*, Addison-Wesley Series in Industrial Management, Addison-Wesley Publishing Co., Inc., Reading, Mass.-London, 1962. MR**0135622****[6]**M. R. Osborne and G. A. Watson,*On the best linear Chebyshev approximation*, Comput. J.**10**(1967), 172–177. MR**0218808****[7]**John R. Rice,*Tchebycheff approximation in a compact metric space*, Bull. Amer. Math. Soc.**68**(1962), 405–410. MR**0139886**, 10.1090/S0002-9904-1962-10822-2**[8]**John R. Rice,*The approximation of functions. Vol. 2: Nonlinear and multivariate theory*, Addison-Wesley Publishing Co., Reading, Mass.-London-Don Mills, Ont., 1969. MR**0244675****[9]**G. A. Watson,*A multiple exchange algorithm for multivariate Chebyshev approximation*, SIAM J. Numer. Anal.**12**(1975), 46–52. MR**0373229**

Retrieve articles in *Mathematics of Computation*
with MSC:
65F20

Retrieve articles in all journals with MSC: 65F20

Additional Information

DOI:
http://dx.doi.org/10.1090/S0025-5718-1977-0445803-8

Keywords:
Discrete linear Chebyshev approximation,
strict Chebyshev approximation,
overdetermined linear equations,
linear programming

Article copyright:
© Copyright 1977
American Mathematical Society