An efficient method for the discrete linear approximation problem

Author:
Nabih N. Abdelmalek

Journal:
Math. Comp. **29** (1975), 844-850

MSC:
Primary 65D15; Secondary 90C10

DOI:
https://doi.org/10.1090/S0025-5718-1975-0378354-8

MathSciNet review:
0378354

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: An improved dual simplex algorithm for the solution of the discrete linear approximation problem is described. In this algorithm certain intermediate iterations are skipped. This method is comparable with an improved simplex method due to Barrodale and Roberts, in both speed and number of iterations. It also has the advantage that in case of ill-conditioned problems, the basis matrix can lend itself to triangular factorization and can thus ensure a stable solution. Numerical results are given.

**[1]**Nabih N. Abdelmalek,*On the discrete linear 𝐿₁ approximation and 𝐿₁ solutions of overdetermined linear equations*, J. Approximation Theory**11**(1974), 38–53. MR**0388750****[2]**N. N. ABDELMALEK, " solution of overdetermined system of linear equations by a dual simplex method,"*Comm. ACM*(Submitted.)**[3]**N. N. ABDELMALEK, " solution of overdetermined system of linear equations by a dual simplex method and*LU*decomposition,"*Comm. ACM*(Submitted.)**[4]**Ian Barrodale and Andrew Young,*Algorithms for best 𝐿₁ and 𝐿_{∞} linear approximations on a discrete set*, Numer. Math.**8**(1966), 295–306. MR**0196912**, https://doi.org/10.1007/BF02162565**[5]**I. BARRODALE & F. D. K. ROBERTS,*An Improved Algorithm For Discrete*.*Approximation*, The University of Wisconsin, MRC Tech. Report no. 1172, 1972.**[6]**I. Barrodale and F. D. K. Roberts,*An improved algorithm for discrete 𝑙₁ linear approximation*, SIAM J. Numer. Anal.**10**(1973), 839–848. MR**0339449**, https://doi.org/10.1137/0710069**[7]**I. BARRODALE & F. D. K. ROBERTS, "Solution of an overdetermined system of equations in the norm,"*Comm. ACM*, v. 17, 1974, pp. 319-920.**[8]**R. H. BARTELS & G. H. GOLUB, "The simplex method of linear programming using*LU*decomposition,"*Comm. ACM*, v. 12, 1969, pp. 266-268. MR**39**#2302.**[9]**Karl H. Usow,*On 𝐿₁ approximation. II. Computation for discrete functions and discretization effects*, SIAM J. Numer. Anal.**4**(1967), 233–244. MR**0217499**, https://doi.org/10.1137/0704022**[10]**Harvey M. Wagner,*Linear programming techniques for regression analysis*, J. Amer. Statist. Assoc.**54**(1959), 206–212. MR**0130753**

Retrieve articles in *Mathematics of Computation*
with MSC:
65D15,
90C10

Retrieve articles in all journals with MSC: 65D15, 90C10

Additional Information

DOI:
https://doi.org/10.1090/S0025-5718-1975-0378354-8

Keywords:
Discrete linear approximation,
overdetermined system of linear equations,
linear programming,
dual simplex algorithm

Article copyright:
© Copyright 1975
American Mathematical Society