The calculation of best linear one-sided approximations

Author:
G. A. Watson

Journal:
Math. Comp. **27** (1973), 607-620

MSC:
Primary 65D15

DOI:
https://doi.org/10.1090/S0025-5718-1973-0343537-8

MathSciNet review:
0343537

Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: The calculation of linear one-sided approximations is considered, using the discrete norm. For and , this gives rise to a linear programming problem, and for , to a convex programming problem. Numerical results are presented, including some applications to the approximate numerical solution of ordinary differential equations, with error bounds.

**[1]**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**[2]**I. Barrodale and F. D. K. Roberts,*Applications of mathematical programming to 𝑙_{𝑝} approximation*, Nonlinear Programming (Proc. Sympos., Univ. of Wisconsin, Madison, Wis., 1970) Academic Press, New York, 1970, pp. 447–464. MR**0271594****[3]**R. Bojanić and R. DeVore,*On polynomials of best one sided approximation*, Enseignement Math. (2)**12**(1966), 139–164. MR**0213790****[4]**Lothar Collatz,*Approximation in partial differential equations*, On numerical approximation. Proceedings of a Symposium, Madison, April 21-23, 1958, Edited by R. E. Langer. Publication no. 1 of the Mathematics Research Center, U.S. Army, the University of Wisconsin, The University of Wisconsin Press, Madison, 1959, pp. 413–422. MR**0103593****[5]**L. Collatz,*Monotonicity and related methods in non-linear differential equations problems*, Numerical Solutions of Nonlinear Differential Equations (Proc. Adv. Sympos., Madison, Wis., 1966) John Wiley & Sons, Inc., New York, 1966, pp. 65–87. MR**0210330****[6]**Ronald DeVore,*One-sided approximation of functions*, J. Approximation Theory**1**(1968), no. 1, 11–25. MR**0230018****[7]**Anthony V. Fiacco and Garth P. McCormick,*Nonlinear programming: Sequential unconstrained minimization techniques*, John Wiley and Sons, Inc., New York-London-Sydney, 1968. MR**0243831****[8]**R. Fletcher, J. A. Grant, and M. D. Hebden,*The calculation of linear best 𝐿_{𝑝} approximations*, Comput. J.**14**(1971), 276–279. MR**0303948**, https://doi.org/10.1093/comjnl/14.3.276**[9]**R. Fletcher,*Minimizing general functions subject to linear constraints*, Numerical methods for non-linear optimization (Conf., Dundee, 1971), Academic Press, London, 1972, pp. 279–296. MR**0408244****[10]**G. Hadley,*Linear programming*, Addison-Wesley Series in Industrial Management, Addison-Wesley Publishing Co., Inc., Reading, Mass.-London, 1962. MR**0135622****[11]**James T. Lewis,*Computation of best one-sided 𝐿₁ approximation*, Math. Comp.**24**(1970), 529–536. MR**0273780**, https://doi.org/10.1090/S0025-5718-1970-0273780-5**[12]**G. Marsaglia,*One-sided approximations by linear combinations of functions*, Approximation Theory (Proc. Sympos., Lancaster, 1969) Academic Press, London, 1970, pp. 233–242. MR**0266401****[13]**B. A. Murtagh and R. W. H. Sargent,*A constrained minimization method with quadratic convergence*, Optimization (Sympos., Univ. Keele, Keele, 1968) Academic Press, London, 1969, pp. 215–245. MR**0284213****[14]**M. R. Osborne and G. A. Watson,*On the best linear Chebyshev approximation*, Comput. J.**10**(1967), 172–177. MR**0218808**, https://doi.org/10.1093/comjnl/10.2.172**[15]**David L. Phillips,*A note on best one-sided approximations*, Comm. ACM**14**(1971), 598–600. MR**0297100**, https://doi.org/10.1145/362663.362743**[16]**Murray H. Protter and Hans F. Weinberger,*Maximum principles in differential equations*, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1967. MR**0219861****[17]**J. B. Rosen,*The gradient projection method for nonlinear programming. I. Linear constraints*, J. Soc. Indust. Appl. Math.**8**(1960), 181–217. MR**0112750****[18]**J. B. Rosen,*Approximate computational solution of non-linear parabolic partial differential equations by linear programming*, Numerical Solutions of Nonlinear Differential Equations (Proc. Adv. Sympos., Madison, Wis., 1966) John Wiley & Sons, Inc., New York, 1966, pp. 265–296. MR**0207232****[19]**J. B. Rosen,*Approximate solution and error bounds for quasi-linear elliptic boundary value problems*, SIAM J. Numer. Anal.**7**(1970), 80–103. MR**0264861**, https://doi.org/10.1137/0707004**[20]**G. A. Watson,*On the best linear one-sided Chebyshev approximation*, J. Approximation Theory**7**(1973), 48–58. MR**0342929****[21]**Philip Wolfe,*Methods of nonlinear programming*, Recent advances in mathematical programming, McGraw-Hill, New York, 1963, pp. 67–86. MR**0155683****[22]**P. Wolfe,*Methods of nonlinear programming*, Nonlinear Programming (NATO Summer School, Menton, 1964) North-Holland, Amsterdam, 1967, pp. 97–131. MR**0216868****[23]**Richard H. Bartels and Gene H. Golub,*Stable numerical methods for obtaining the Chebyshev solution to an overdetermined system of equations*, Comm. ACM**11**(1968), 401–406. MR**0240957**, https://doi.org/10.1145/363347.363364**[24]**I. Barrodale & F. D. K. Roberts,*An Improved Algorithm for Discrete**Linear Approximation*, MRC Technical Summary Report #1172, January 1972.

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

Retrieve articles in all journals with MSC: 65D15

Additional Information

DOI:
https://doi.org/10.1090/S0025-5718-1973-0343537-8

Keywords:
One-sided approximation,
approximation,
linear programming,
convex programming

Article copyright:
© Copyright 1973
American Mathematical Society