Interpolation and Approximation by Polynomials George M. Phillips Springer To Rona Elle est a` toi, cette chanson. This page intentionally left blank Preface Thisbookisintendedasacourseinnumericalanalysisandapproximation theory for advanced undergraduate students or graduate students, and as areferenceworkforthosewholectureorresearchinthisarea.Itstitlepays homage to Interpolation and Approximation by Philip J. Davis, published in 1963 by Blaisdell and reprinted by Dover in 1976. My book is less gen- eral than Philip Davis’s much respected classic, as the qualification “by polynomials”initstitlesuggests,anditispitchedatalessadvancedlevel. I believe that no one book can fully cover all the material that could appearinabookentitledInterpolationandApproximationbyPolynomials. Nevertheless, I have tried to cover most of the main topics. I hope that my readers will share my enthusiasm for this exciting and fascinating area of mathematics, and that, by working through this book, some will be encouraged to read more widely and pursue research in the subject. Since my book is concerned with polynomials, it is written in the language of classical analysis and the only prerequisites are introductory courses in analysis and linear algebra. Indecidingwhethertoincludeatopicinanybookorcourseoflectures,I always ask myself, Is the proposed item mathematically interesting? Para- doxically, utility is a useless guide. For instance, why should we discuss interpolation nowadays? Who uses it? Indeed, how many make direct use ofnumericalintegration,orthogonalpolynomials,Bernsteinpolynomials,or techniques for computing various best approximations? Perhaps the most serioususers ofmathematicsaretherelativelysmallnumberwhoconstruct, andtheratherlargernumberwhoapply,specialistmathematicalpackages, includingthoseforevaluatingstandardfunctions,solvingsystemsoflinear viii Preface equations,carryingoutintegrations,solvingdifferentialequations,drawing surfaces with the aid of CAGD (computer-aided geometrical design) tech- niques, and so on. However, it is all too easy to make use of such packages without understanding the mathematics on which they are based, or their limitations, and so obtain poor, or even meaningless, results. Many years ago someone asked my advice on a mathematical calculation that he was findingdifficult.Igentlypointedoutthathisresultwasinvalidbecausethe series he was summing was divergent. He responded honestly that, faced with an infinite series, his strategy was always to compute the sum of the first hundred terms. Therearemanyconnectionsbetweenthevariouschaptersandsectionsin thisbook.Ihavesoughttoemphasizetheseinterconnectionstoencouragea deeper understanding of the subject. The first topic is interpolation, from its precalculus origins to the insights and advances made in the twenti- eth century with the study of Lebesgue constants. Unusually, this account of interpolation also pursues the direct construction of the interpolating polynomialbysolvingthesystemoflinearequationsinvolvingtheVander- monde matrix. How could we dream of despising a study of interpolation, when it is so much at the centre of the development of the calculus? Our understandingoftheinterpolatingpolynomialleadsusnaturallytoastudy ofintegrationrules,andanunderstandingofGaussianintegrationrulesre- quires knowledge of orthogonal polynomials, which are at the very heart of classical approximation theory. The chapter on numerical integration also includes an account of the Euler–Maclaurin formula, in which we can use a series to estimate an integral or vice versa, and the justification of this powerful formula involves some particularly interesting mathematics, with a forward reference to splines. The chapter devoted to orthogonal polynomials is concerned with best approximation, and concentrates on the Legendre polynomials and least squares approximations, and on the Chebyshev polynomials, whose minimax property leads us on to minimax approximations. One chapter is devoted to Peano kernel theory, which was developed in thelatenineteenthcenturyandprovidesaspecialcalculusforcreatingand justifyingerrortermsforvariousapproximations,includingthosegenerated by integration rules. This account of Peano kernel theory is rather more extensive than that usually given in a textbook, and I include a derivation of the error term for the Euler–Maclaurin formula. The following chapter extends the topic of interpolation to several variables, with most atten- tion devoted to interpolation in two variables. It contains a most elegant generalization of Newton’s divided difference formula plus error term to a triangular set of points, and discusses interpolation formulas for various setsofpointsinatriangle.Thelattertopiccontainsmaterialthatwasfirst published in the late twentieth century and is justified by geometry dating fromthefourthcenturyad,towardstheveryendofthegoldenmillennium of Greek mathematics, and by methods belonging to projective geometry, Preface ix using homogeneous coordinates. Mathematics certainly does not have to be new to be relevant. This chapter contains much material that has not appeared before in a textbook at any level. There is a chapter on polynomial splines, where we split the interval on which we wish to approximate a function into subintervals. The ap- proximating function consists of a sequence of polynomials, one on each subinterval,thatconnecttogethersmoothly.Thesimplestandleastsmooth example of this is a polygonal arc. Although we can detect some ideas in earlier times that remind us of splines, this is a topic that truly belongs to the twentieth century. It is a good example of exciting, relatively new mathematics that worthily stands alongside the best mathematics of any age. Bernstein polynomials, the subject of the penultimate chapter, date from the early twentieth century. Their creation was inspired by the fa- mous theorem stated by Weierstrass towards the end of the nineteenth century that a continuous function on a finite interval of the real line can be approximated by a polynomial with any given precision over the whole interval.Polynomialsaresimplemathematicalobjectsthatareeasytoeval- uate, differentiate, and integrate, and Weierstrass’s theorem justifies their importance in approximation theory. Several of the processes discussed in this book have special cases where a function is evaluated at equal intervals, and we can scale the variable so that the function is evaluated at the integers. For example, in finite dif- ference methods for interpolation the interpolated function is evaluated at equal intervals, and the same is true of the integrand in the Newton–Cotes integration rules. Equal intervals occur also in the Bernstein polynomials andtheuniformB-splines.Inourstudyofthesefourtopics,wealsodiscuss processes in which the function is evaluated at intervals whose lengths are ingeometricprogression.Thesecanbescaledsothatthefunctionisevalu- atedontheq-integers.OvertwentyyearsagoIwasaskedtorefereeapaper by the distinguished mathematician I.J. Schoenberg (1903–1990), who is best known for his pioneering work on splines. Subsequently I had a letter from the editor of the journal saying that Professor Schoenberg wished to know the name of the anonymous referee. Over the following few years I had a correspondence with Professor Schoenberg which I still value very much. His wonderful enthusiasm for mathematics continued into his eight- ies. Indeed, of his 174 published papers and books, 56 appeared after his retirementin1973.Theabove-mentionedpaperbyIsoSchoenbergwasthe chiefinfluenceontheworkdonebyS.L.Leeandmeinapplyingq-integers to interpolation on triangular regions. The q-integer motif was continued in joint work with Zeynep Koc¸ak on splines and then in my work on the Bernstein polynomials, in which I was joined by Tim Goodman and Halil Oruc¸. The latter work nicely illustrates variation-diminishing ideas, which take us into the relatively new area of CAGD. The inclusion of a few rather minor topics in whose development I have been directly involved may cause some eyebrows to be raised. But I trust