The calculation of best linear one-sided 𝐿_{𝑝} approximations

Watson, G. A.

doi:10.1090/S0025-5718-1973-0343537-8

The calculation of best linear one-sided $L_{p}$ approximations
HTML articles powered by AMS MathViewer

by G. A. Watson PDF

Math. Comp. 27 (1973), 607-620 Request permission

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.

References

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 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, Publication of the Mathematics Research Center, U.S. Army, the University of Wisconsin, no. 1, University of Wisconsin Press, Madison, Wis., 1959, pp. 413–422. Edited by R. E. Langer. 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, N.Y., 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 10.1016/0021-9045(68)90054-3
Anthony V. Fiacco and Garth P. McCormick, Nonlinear programming: Sequential unconstrained minimization techniques, John Wiley & 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 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 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 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 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, DOI 10.1137/0108011
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, N.Y., 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 10.1137/0707004
G. A. Watson, On the best linear one-sided Chebyshev approximation, J. Approximation Theory 7 (1973), 48–58. MR 342929, DOI 10.1016/0021-9045(73)90051-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 10.1145/363347.363364

An Improved Algorithm for Discrete

Linear Approximation