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 Free Access

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]**I. Barrodale & A. Young, "Algorithms for best and linear approximations on a discrete set,"*Numer. Math.*, v. 8, 1966, pp. 295-306. MR**33**#5096. MR**0196912 (33:5096)****[2]**I. Barrodale & F. D. K. Roberts,*Applications of Mathematical Programming to**Approximation*, Dept. of Mathematics Report #32, May 1970;*Nonlinear Programming*, Academic Press, New York, 1970, pp. 447-464. MR**0271594 (42:6477)****[3]**R. Bojanic & R. De Vore, "On polynomials of best one-sided approximation,"*Enseignment Math.*, (2) v. 12, 1966, pp. 139-164. MR**35**#4647. MR**0213790 (35:4647)****[4]**L. Collatz, "Approximation in partial differential equations," in*On Numerical Approximation*(Proc. Sympos., Madison, 1958), Publ. no. 1, Math. Res. Center, U.S. Army, University of Wisconsin, Univ. of Wisconsin Press, Madison, Wis., 1959, pp. 413-422. MR**21**#2361. MR**0103593 (21:2361)****[5]**L. Collatz, "Monotonicity and related methods in nonlinear differential equations problems," in*Numerical Solutions of Nonlinear Differential Equations*, Wiley, New York, 1966, pp. 65-87. MR**35**# 1223. MR**0210330 (35:1223)****[6]**R. De Vore, "One-sided approximation of functions,"*J. Approximation Theory*, v. 1, 1968, pp. 11-25. MR**37**#5584. MR**0230018 (37:5584)****[7]**A. V. Fiacco & G. P. McCormick,*Nonlinear Programming*:*Sequential Unconstrained Minimization Techniques*, Wiley, New York, 1968. MR**39**#5152. MR**0243831 (39:5152)****[8]**R. Fletcher, J. A. Grant & M. D. Hebden, "The calculation of linear best approximations,"*Comput. J.*, v. 14, 1971, pp. 276-279. MR**0303948 (46:3084)****[9]**R. Fletcher, "Minimizing general functions subject to linear constraints," in*Numercial Methods for Non-linear Optimisation*, F. A. Lootsma (Editor), Academic Press, London, New York, 1972, pp. 279-296. MR**0408244 (53:12009)****[10]**G. Hadley,*Linear Programming*, Addison-Wesley Ser. in Indust. Management., Addison-Wesley, Reading, Mass., 1962. MR**24**#B1669. MR**0135622 (24:B1669)****[11]**J. T. Lewis, "Computation of best one-sided approximation,"*Math Comp.*, v. 24, 1970, pp. 529-536. MR**42**#8656. MR**0273780 (42:8656)****[12]**G. Marsaglia, "One-sided approximations by linear combinations of functions," in*Approximation Theory*, Academic Press, London, 1970, pp. 233-242. MR**42**#1307. MR**0266401 (42:1307)****[13]**B. A. Murtagh & R. W. H. Sargent, "A constrained minimisation method with quadratic convergence," in*Optimization*(Sympos., Univ. of Keele, Keele, 1968), Academic Press, London, 1969, pp. 215-245, MR**44**#1442. MR**0284213 (44:1442)****[14]**M. R. Osborne & G. A. Watson, "On the best linear Chebyshev approximation,"*Comput. J.*, v. 10, 1967, pp. 172-177. MR**36**#1892. MR**0218808 (36:1892)****[15]**D. L. Phillips, "A note on best one-sided approximations,"*Comm. ACM*, v. 14, 1971, pp. 598-600. MR**0297100 (45:6158)****[16]**M. H. Protter & H. F. Weinberger,*Maximum Principles in Differential Equations*, Prentice-Hall, Englewood Cliffs, N.J., 1967. MR**36**#2935. MR**0219861 (36:2935)****[17]**J. B. Rosen, "The gradient projection method for nonlinear programming, I: Linear constraints,"*J. Soc. Indust. Appl. Math.*, v. 8, 1960, pp. 181-217. MR**22**#3601. MR**0112750 (22:3601)****[18]**J. B. Rosen, "Approximate computational solution of nonlinear parabolic partial differential equations by linear programming," in*Numerical Solutions of Nonlinear Differential Equations*(Proc. Adv. Sympos., Madison, Wis., 1966), Wiley, New York, 1966, pp. 265-296. MR**34**#7048. MR**0207232 (34:7048)****[19]**J. B. Rosen, "Approximate solution and error bounds for quasi-linear elliptic boundary value problems,"*SIAM J. Numer. Anal.*, v. 7, 1970, pp. 80-103. MR**41**#9452. MR**0264861 (41:9452)****[20]**G. A. Watson, "On the best linear one-sided Chebyshev approximation,"*J. Approximation Theory*, v. 7, 1973, pp. 48-58. MR**0342929 (49:7673)****[21]**P. Wolfe, "Methods of nonlinear programming," in*Recent Advances in Mathematical Programming*, McGraw-Hill, New York, 1963, pp. 67-86. MR**27**#5617. MR**0155683 (27:5617)****[22]**P. Wolfe, "Methods of nonlinear programming," in*Nonlinear Programming*(NATO Summer School, Menton, 1964), North-Holland, Amsterdam, 1967, pp. 97-131. MR**35**#7697. MR**0216868 (35:7697)****[23]**R. H. Bartels & G. H. Golub, "Stable numerical methods for obtaining the Chebyshev solution to an overdetermined system of equations,"*Comm. ACM*, v. 11, 1968, pp. 401-406. MR**0240957 (39:2302)****[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