Linear programming and the calculation of maximum norm approximations

Abstract

This thesis examines methods for the solution of a number of approximation problems which include multivariate approximation and the approximate solution of differential equations. After a brief discussion of the literature in Chapter 1, the best linear Chebyshev approximation prob l em is discussed in Chapter 2. A brief introduc ti on to the genera l theory is given, which includes a number of characterization theorems . The di screte linear Chebys hev approximation problem is then discussed and it is shown how this may be solved by linear programm ing techniques. In Chapter 3, the problem of determining, numerically, best linear Chebyshev approximations is considered, and two algorithms are given. Chapter 4 generalizes the methods of Chapters 2 and 3 to enable the numerical calculation of approximate solutions of differential equations to be made. A method is developed which can be used when the approximating family does not satisfy the boundary conditions. In §4 .2 linear elliptic partial differential equations are considered in detail, and an error bound is derived. Use can be made of this to produce an approximation with the best error bound. Non-linear problems are considered in Chapters 5 and 6. In §5 .3, two methods are presented for non-linear continuous approximation which I are analogues of the methods of Chapter 3. The methods depend on an algorithm for the solution of a discrete problem. Two such algorithms are presented in §5.l, §5.2. In Chapter 6, an investigation is made into the question of improving the efficiency of these algorithms. An algorithm is presented which is similar to those of Chapter 5, and which depends on a parameter, k. Conditions are given under which the algorithm has an order of convergence of at least k+l . It is then shown how k may be chosen in an attempt to maximize efficiency. Because many of the algorithms in this thesis require the solution of discrete Chebyshev problems, a set of linear programming routines is included in the appendix.· The code is written to take advantage of the special structure of these problems.