Linear programming and best approximation

Thesis (M.A.)--Boston UniversityPLEASE NOTE: Boston University Libraries did not receive an Authorization To Manage form for this thesis or dissertation. It is therefore not openly accessible, though it may be available by request. If you are the author or principal advisor of this work and would like to request open access for it, please contact us at open-help@bu.edu. Thank you.The problem discussed in this paper is that of finding a best approximation to a given real-valued function f(x) over a continuum by means of finding a best approximation over a discrete set of points. We are also seeking to find a numerical method of finding a best approximation over our discrete set of points. A best approximation is one which minimizes the maximum deviation of our approximation from our given function f(x). We first discuss the concept of linear programming. In this paper we are not so much concerned with the theory behind linear programming as we are with the method to solve a linear programming problem, namely the simplex method. We discuss the simplex method from the point of view of a programmer, noting how results are continually updated until an optimal solution to t he problem is found. The only theoretical aspect of linear programming which we discuss is the notion of duals and the relationship between the solution of a primal and a dual problem. This becomes very important later in the paper when we try to formulate a best a proximat ion problem as a linear programming problem. Next we discuss the theoretical aspects of best approximation over a continuum. We prove existence, uniqueness, and, most important for our purposes, characterization. Our approximating functions are assumed to form a Chebyschev set throughout this paper. Finally we discuss best approximation over a discrete set of points. We first prove that the characterization theorem holds for problems of this type. Now that we have a way to tell whether our approximation is the best that can be obtained, we turn our attention to the relationship between the best approximation problem over a continuum and a discrete set of points. We prove in a quite general context that the best approximation over a discrete set of points converges uniformly to the solution to the problem over the continuum. We then retrace our steps and establish similar results for the particular case of polynomial approximation. After this we try to find out about the rate at which this convergence takes place. In general this question has no answer for its depends on the smoothness of the functions involved; if, however, we assume the fun ctions satisfy a Holder condition we may obtain some bounds on the rate of convergence. Finally, we reformulate the best approximation problem, showing how it can be considered as a linear programming problem which we already have a means of solving.2031-01-0