The calculation of best linear one-sided $L_{p}$ 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 ${L_p}$ norm. For $p = 1$ and $p = \infty$, this gives rise to a linear programming problem, and for $1 < p < \infty$, to a convex programming problem. Numerical results are presented, including some applications to the approximate numerical solution of ordinary differential equations, with error bounds.

- Ian Barrodale and Andrew Young,
*Algorithms for best $L_{1}$ and $L_{\infty }$ linear approximations on a discrete set*, Numer. Math.**8**(1966), 295β306. MR**196912**, DOI https://doi.org/10.1007/BF02162565 - I. Barrodale and F. D. K. Roberts,
*Applications of mathematical programming to $l_{p}$ approximation*, Nonlinear Programming (Proc. Sympos., Univ. of Wisconsin, Madison, Wis., 1970) Academic Press, New York, 1970, pp. 447β464. MR**0271594** - R. BojaniΔ and R. DeVore,
*On polynomials of best one sided approximation*, Enseign. Math. (2)**12**(1966), 139β164. MR**213790** - 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** - 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** - Ronald DeVore,
*One-sided approximation of functions*, J. Approximation Theory**1**(1968), no. 1, 11β25. MR**230018**, DOI https://doi.org/10.1016/0021-9045%2868%2990054-3 - 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** - R. Fletcher, J. A. Grant, and M. D. Hebden,
*The calculation of linear best $L_{p}$ approximations*, Comput. J.**14**(1971), 276β279. MR**303948**, DOI https://doi.org/10.1093/comjnl/14.3.276 - 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** - G. Hadley,
*Linear programming*, Addison-Wesley Series in Industrial Management, Addison-Wesley Publishing Co., Inc., Reading, Mass.-London, 1962. MR**0135622** - James T. Lewis,
*Computation of best one-sided $L_{1}$ approximation*, Math. Comp.**24**(1970), 529β536. MR**273780**, DOI https://doi.org/10.1090/S0025-5718-1970-0273780-5 - 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** - 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** - M. R. Osborne and G. A. Watson,
*On the best linear Chebyshev approximation*, Comput. J.**10**(1967), 172β177. MR**218808**, DOI https://doi.org/10.1093/comjnl/10.2.172 - David L. Phillips,
*A note on best one-sided approximations*, Comm. ACM**14**(1971), 598β600. MR**0297100**, DOI https://doi.org/10.1145/362663.362743 - Murray H. Protter and Hans F. Weinberger,
*Maximum principles in differential equations*, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1967. MR**0219861** - J. B. Rosen,
*The gradient projection method for nonlinear programming. I. Linear constraints*, J. Soc. Indust. Appl. Math.**8**(1960), 181β217. MR**112750** - 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** - J. B. Rosen,
*Approximate solution and error bounds for quasi-linear elliptic boundary value problems*, SIAM J. Numer. Anal.**7**(1970), 80β103. MR**264861**, DOI https://doi.org/10.1137/0707004 - G. A. Watson,
*On the best linear one-sided Chebyshev approximation*, J. Approximation Theory**7**(1973), 48β58. MR**342929**, DOI https://doi.org/10.1016/0021-9045%2873%2990051-8 - Philip Wolfe,
*Methods of nonlinear programming*, Recent advances in mathematical programming, McGraw-Hill, New York, 1963, pp. 67β86. MR**0155683** - P. Wolfe,
*Methods of nonlinear programming*, Nonlinear Programming (NATO Summer School, Menton, 1964) North-Holland, Amsterdam, 1967, pp. 97β131. MR**0216868** - 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**, DOI https://doi.org/10.1145/363347.363364
I. Barrodale & F. D. K. Roberts,

*An Improved Algorithm for Discrete*${l_1}$

*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

Keywords:
One-sided approximation,
<IMG WIDTH="29" HEIGHT="38" ALIGN="MIDDLE" BORDER="0" SRC="images/img1.gif" ALT="${L_p}$"> approximation,
linear programming,
convex programming

Article copyright:
© Copyright 1973
American Mathematical Society