Computing the strict Chebyshev solution of overdetermined linear equations

Abdelmalek, Nabih N.

doi:10.1090/S0025-5718-1977-0445803-8

Computing the strict Chebyshev solution of overdetermined linear equations
HTML articles powered by AMS MathViewer

by Nabih N. Abdelmalek PDF

Math. Comp. 31 (1977), 974-983 Request permission

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.

References

Nabih N. Abdelmalek, Chebyshev solution of overdetermined systems of linear equations, Nordisk Tidskr. Informationsbehandling (BIT) 15 (1975), no. 2, 117–129. MR 483357, DOI 10.1007/bf01932684
Jean Descloux, Approximations in $L^{p}$ and Chebyshev approximations, J. Soc. Indust. Appl. Math. 11 (1963), 1017–1026. MR 159172

Proc. ACM Nat. Conf.

C. S. Duris and M. G. Temple, A finite step algorithm for determining the “strict” Chebyshev solution to $Ax=b$, SIAM J. Numer. Anal. 10 (1973), 690–699. MR 329232, DOI 10.1137/0710060
G. Hadley, Linear programming, Addison-Wesley Series in Industrial Management, Addison-Wesley Publishing Co., Inc., Reading, Mass.-London, 1962. MR 0135622
M. R. Osborne and G. A. Watson, On the best linear Chebyshev approximation, Comput. J. 10 (1967), 172–177. MR 218808, DOI 10.1093/comjnl/10.2.172
John R. Rice, Tchebycheff approximation in a compact metric space, Bull. Amer. Math. Soc. 68 (1962), 405–410. MR 139886, DOI 10.1090/S0002-9904-1962-10822-2
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
G. A. Watson, A multiple exchange algorithm for multivariate Chebyshev approximation, SIAM J. Numer. Anal. 12 (1975), 46–52. MR 373229, DOI 10.1137/0712004