Approximation Theory and Methods

Most functions that occur in mathematics cannot be used directly in computer calculations. Instead they are approximated by manageable functions such as polynomials and piecewise polynomials. The general theory of the subject and its application to polynomial approximation are classical, but piecewise polynomials have become far more useful during the last twenty years. Thus many important theoretical properties have been found recently and many new techniques for the automatic calculation of approximations to prescribed accuracy have been developed. This book gives a thorough and coherent introduction to the theory that is the basis of current approximation methods. Professor Powell describes and analyses the main techniques of calculation supplying sufficient motivation throughout the book to make it accessible to scientists and engineers who require approximation methods for practical needs. Because the book is based on a course of lectures to third-year undergraduates in mathematics at Cambridge University, sufficient attention is given to theory to make it highly suitable as a mathematical textbook at undergraduate or postgraduate level. TITLE CONTENTS PREFACE 1 The approximation problem and existence of best approximations 1.1 Examples of approximation problems 1.2 Approximation in a metric space 1.3 Approximation in a normed linear space 1.4 The Lp·norms 1.5 A geometric view of best approximations 1 Exercises 2 The uniqueness of best approximations 2.1 Convexity conditions 2.2 Conditions for uniqueness of the best approximation 2.3 The continuity of best approximation operators 2.4 The 1-, 2- and oo-norms 2 Exercises 3 Approximation operators and some approximating functions 3.1 Approximation operators 3.2 Lebesgue constants 3.3 Polynomial approximations to differentiable functions 3.4 Piecewise polynomial approximations 3 Exercises 4 Polynomial interpolation 4.1 The Lagrange interpolation formula 4.2 The error in polynomial interpolation 4.3 The Chebyshev interpolation points 4.4 The norm of the Lagrange interpolation operator 4 Exercises 5 IJivided differences 5.1 Basic properties of divided differences 5.2 Newton's interpolation method 5.3 The recurrence relation for divided differences 5.4 Discussion of formulae for polynomial interpolation 5.5 Hermite interpolation 5 Exercises 6 The uniform convergence of polynomial approximations 6.1 The Weierstrass theorem 6.2 Monotone operators 6.3 The Bernstein operator 6.4 The derivatives of the Bernstein approximations 6 Exercises 7 The theory of minimax approximation 7 .1 Introduction to minimax approximation 7 .2 The reduction of the error of a trial approximation 7 .3 The characterization theorem and the Haar condition 7 .4 Uniqueness and bounds on the minimax error 7 Exercises 8 The exchange algorithm 8.1 Summary of the exchange algorithm 8.2 Adjustment of the reference 8.3 An example of the iterations of the exchange algorithm 8.4 Applications of Chebyshev polynomials to minimax approximation 8.5 Minimax approximation on a discrete point set 8 Exercises 9 The convergence of the exchange algorithm 9.1 The increase in the levelled reference error 9 .2 Proof of convergence 9.3 Properties of the point that is brought into the reference 9.4 Second-order convergence 9 Exercises 10 Rational approximation by the exchange algorithm 10.1 Best minimax rational approximation 10.2 The best approximation on a reference 10.3 Some convergence properties of the exchange algorithm 10.4 Methods based on linear programming 10 Exercises 11 Least squares approximation 11.1 The general form of a linear least squares calculation 11.2 The least squares characterization theorem 11.3 Methods of calculation 11.4 The recurrence relation for orthogonal polynomials 11 Exercises 12 Properties of orthogonal polynomials 12.1 Elementary properties 12.2 Gaussian quadrature 12.3 The characterization of orthogonal polynomials 12.4 The operator Rn 12 Exercises 13 Approximation to periodic functions 13.1 Trigonometric polynomials 13.2 The Fourier series operator Sn 13.3 The discrete Fourier series operator 13.4 Fast Fourier transforms 13 Exercises 14 The theory of best L1 approximation 14.1 Introduction to best L1 approximation 14.2 The characterization theorem 14.3 Consequences of the Haar condition 14.4 The L1 interpolation points for algebraic polynomials 14 Exercises 15 An application of L1 approximation and the discrete case 15.1 A useful example of L1 approximation 15.2 Jackson's first theorem 15.3 Discrete L1 approximation 15.4 Linear programming methods 15 Exercises 16 The order of convergence of polynomial approximations 16.1 Approximations to non-differentiable functions 16.2 The Dini-Lipschitz theorem 16.3 Some bounds that depend on higher derivatives 16.4 Extensions to algebraic polynomials 16 Exercises 17 The uniform boundedness theorem 17 .1 Preliminary results 17 .2 Tests for uniform convergence 17 .3 Application to trigonometric polynomials 17 .4 Application to algebraic polynomials 17 Exercises 18 Interpolation by piecewise polynomials 18.1 Local interpolation methods 18.2 Cubic spline interpolation 18.3 End conditions for cubic spline interpolation 18.4 Interpolating splines of other degrees 18 Exercises 19 B-splines 19.1 The parameters of a spline function 19.2 The form of B-splines 19.3 B-splines as basis functions 19.4 A recurrence relation for B-splines 19 Exercises 20 Convergence properties of spline approximations 20.l Uniform convergence 20.2 The order of convergence when f is differentiable 20.3 Local spline interpolation 20.4 Cubic splines with constant knot spacing 20 Exercises 21 Knot positions and the calculation of spline approximations 21.1 The distribution of knots at a singularity 21.2 Interpolation for general knots 21.3 The approximation of functions to prescribed accuracy 21 Exercises 22 The Peano kernel theorem 22.1 The error of a formula for the solution of differential equations 22.2 The Peano kernel theorem 22.3 Application to divided differences and to polynomial interpolation 22.4 Application to cubic spline interpolation 22 Exercises 23 Natural and perfect splines 23.1 A variational problem 23.2 Properties of natural splines 23.3 Perfect splines 23 Exercises 24 Optimal interpolation 24.1 The optimal interpolation problem 24.2 L1 approximation by B-splines 24.3 Properties of optimal interpolation 24 Exercises APPENDIX A The Haar condition APPENDIX B Related work and references References INDEX