Computing the strict Chebyshev solution of overdetermined linear equations
Author:
Nabih N. Abdelmalek
Journal:
Math. Comp. 31 (1977), 974983
MSC:
Primary 65F20
MathSciNet review:
0445803
Fulltext 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
(58 #3368)
 [2]
Jean
Descloux, Approximations in 𝐿^{𝑝} and Chebyshev
approximations, J. Soc. Indust. Appl. Math. 11
(1963), 1017–1026. MR 0159172
(28 #2389)
 [3]
C. S. DURIS, "An exchange method for solving Haar and nonHaar overdetermined linear equations in the sense of Chebyshev," Proc. ACM Nat. Conf., 1968, pp. 6166.
 [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
(48 #7574)
 [5]
G.
Hadley, Linear programming, AddisonWesley Series in
Industrial Management, AddisonWesley Publishing Co., Inc., Reading,
Mass.London, 1962. MR 0135622
(24 #B1669)
 [6]
M.
R. Osborne and G.
A. Watson, On the best linear Chebyshev approximation, Comput.
J. 10 (1967), 172–177. MR 0218808
(36 #1892)
 [7]
John
R. Rice, Tchebycheff approximation in a compact
metric space, Bull. Amer. Math. Soc. 68 (1962), 405–410.
MR
0139886 (25 #3313), http://dx.doi.org/10.1090/S000299041962108222
 [8]
John
R. Rice, The approximation of functions. Vol. 2: Nonlinear and
multivariate theory, AddisonWesley Publishing Co., Reading,
Mass.LondonDon Mills, Ont., 1969. MR 0244675
(39 #5989)
 [9]
G.
A. Watson, A multiple exchange algorithm for multivariate Chebyshev
approximation, SIAM J. Numer. Anal. 12 (1975),
46–52. MR
0373229 (51 #9430)
 [1]
 N. N. ABDELMALEK, "Chebyshev solution of overdetermined systems of linear equations," BIT, v. 15, 1975, pp. 117129. MR 0483357 (58:3368)
 [2]
 J. DESCLOUX, "Approximations in and Chebyshev approximations," J. Soc. Indust. Appl. Math., v. 11, 1963, pp. 10171026. MR 28 #2389. MR 0159172 (28:2389)
 [3]
 C. S. DURIS, "An exchange method for solving Haar and nonHaar overdetermined linear equations in the sense of Chebyshev," Proc. ACM Nat. Conf., 1968, pp. 6166.
 [4]
 C. S. DURIS & M. G. TEMPLE, "A finite step algorithm for determining the "strict" Chebyshev solution to ," SIAM J. Numer. Anal., v. 10, 1973, pp. 690699. MR 48 #7574. MR 0329232 (48:7574)
 [5]
 G. HADLEY, Linear Programming, AddisonWesley, Reading, Mass., 1962. MR 24 #B1669. MR 0135622 (24:B1669)
 [6]
 M. R. OSBORNE & G. A. WATSON, "On the best linear Chebyshev approximation," Comput. J., v. 10, 1967, pp. 172177. MR 36 #1892. MR 0218808 (36:1892)
 [7]
 J. R. RICE, "Tchebycheff approximation in a compact metric space," Bull. Amer. Math. Soc., v. 68, 1962, pp. 405410. MR 25 #3313. MR 0139886 (25:3313)
 [8]
 J. R. RICE, The Approximation of Functions. Vol. 2, AddisonWesley, Reading Mass., 1969. MR 39 #5989. MR 0244675 (39:5989)
 [9]
 G. A. WATSON, "A multiple exchange algorithm for multivariate Chebyshev approximation," SIAM J. Numer. Anal., v. 12, 1975, pp. 4652. MR 51 #9430. MR 0373229 (51:9430)
Similar Articles
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/S00255718197704458038
PII:
S 00255718(1977)04458038
Keywords:
Discrete linear Chebyshev approximation,
strict Chebyshev approximation,
overdetermined linear equations,
linear programming
Article copyright:
© Copyright 1977
American Mathematical Society
