A SHORT COURSE ON APPROXIMATION THEORY
TABLE OF CONTENTS PRELIMINARIES 1 PROBLEM SET FUNCTION SPACES 25 APPROXIMATION BY ALGEBRAIC POLYNOMIALS 30 PROBLEM SET UNIFORM APPROXIMATION BY POLYNOMIALS 42 TRIGONOMETRIC POLYNOMIALS 46 PROBLEM SET TRIGONOMETRIC POLYNOMIALS 54 CHARACTERIZATION OF BEST APPROXIMATION 56 PROBLEM SET CHEBYSHEV POLYNOMIALS 72 EXAMPLES CHEBYSHEV POLYNOMIALS IN PRACTICE 74 A BRIEF INTRODUCTION TO INTERPOLATION 76 PROBLEM SET LAGRANGE INTERPOLATION 85 APPROXIMATION ON FINITE SETS 86 A BRIEF INTRODUCTION TO FOURIER SERIES 98 PROBLEM SET FOURIER SERIES 111 JACKSON S THEOREMS 112 ORTHOGONAL POLYNOMIALS 119 PROBLEM SET ORTHOGONAL POLYNOMIALS 122 GAUSSIAN QUADRATURE 124 THE M UNTZ THEOREMS 139 THE STONE WEIERSTRASS THEOREM 145 A SHORT LIST OF REFERENCES 155 PRELIMINARIES INTRODUCTION IN 1853 THE GREAT RUSSIAN MATHEMATICIAN P L CHEBYSHEV CEBY SEV WHILE WORKING ON A PROBLEM OF LINKAGES DEVICES WHICH TRANSLATE THE LINEAR MOTION OF A STEAM ENGINE INTO THE CIRCULAR MOTION OF A WHEEL CONSIDERED THE FOLLOWING PROBLEM GIVEN A CONTINUOUS FUNCTION F DE NED ON A CLOSED INTERVAL A B AND A POSITIVE INTEGER N CAN WE REPRESENT F BY A POLYNOMIAL P X PN K 0 AKXK OF DEGREE AT MOST N IN SUCH A WAY THAT THE MAXIMUM ERROR AT ANY POINT X IN A B IS CONTROLLED IN PARTICULAR IS IT POSSIBLE TO CONSTRUCT P IN SUCH A WAY THAT THE ERROR MAX A X B F X P X IS MINIMIZED THIS PROBLEM RAISES SEVERAL QUESTIONS THE RST OF WHICH CHEBYSHEV HIMSELF IGNORED WHY SHOULD SUCH A POLYNOMIAL EVEN EXIST IF IT DOES CAN WE HOPE TO CONSTRUCT IT IF IT EXISTS IS IT ALSO UNIQUE WHAT HAPPENS IF WE CHANGE THE MEASURE OF THE ERROR TO SAY R B A F X P X 2 DX CHEBYSHEV S PROBLEM IS PERHAPS BEST UNDERSTOOD BY REPHRASING IT IN MODERN TERMS WHAT WE HAVE HERE IS A PROBLEM OF LINEAR APPROXIMATION IN A NORMED LINEAR SPACE RECALL THAT A NORM ON A REAL VECTOR SPACE X IS A NONNEGATIVE FUNCTION ON X SATISFYING X 0 AND X 0 X 0 X X FOR R X Y X Y FOR ANY X Y X ANY NORM ON X INDUCES A METRIC OR DISTANCE FUNCTION BY SETTING DIST X Y X Y THE ABSTRACT VERSION OF OUR PROBLEM S CAN NOW BE RESTATED GIVEN A SUBSET OR EVEN A SUBSPACE Y OF X AND A POINT X X IS THERE AN ELEMENT Y Y WHICH IS NEAREST TO X THAT IS CAN WE ND A VECTOR Y Y SUCH THAT X Y INF Z Y X Z IF THERE IS SUCH A BEST APPROXIMATION TO X FROM ELEMENTS OF Y IS IT UNIQUE PRELIMINARIES 2 EXAMPLES 1 IN X RN WITH ITS USUAL NORM XK N K 1 2 PN K 1 XK 21 2 THE PROBLEM HAS A COMPLETE SOLUTION FOR ANY SUBSPACE OR INDEED ANY CLOSED CONVEX SET Y THIS PROBLEM IS OFTEN CONSIDERED IN CALCULUS OR LINEAR ALGEBRA WHERE IT IS CALLED LEAST SQUARES APPROXIMATION A LARGE PART OF THE CURRENT COURSE WILL BE TAKEN UP WITH LEAST SQUARES APPROXIMATIONS TOO FOR NOW LET S SIMPLY NOTE THAT THE PROBLEM CHANGES CHARACTER DRAMATICALLY IF WE CONSIDER A DI ERENT NORM ON RN CONSIDER X R2 UNDER THE NORM X Y MAX X Y AND CONSIDER THE SUBSPACE Y 0 Y Y R I E THE Y AXIS IT S NOT HARD TO SEE THAT THE POINT X 1 0 R2 HAS IN NITELY MANY NEAREST POINTS IN Y INDEED EVERY POINT 0 Y 1 Y 1 IS NEAREST TO X 2 THERE ARE MANY NORMS WE MIGHT CONSIDER ON RN OF PARTICULAR INTEREST ARE THE P NORMS THAT IS THE SCALE OF NORMS XI N I 1 P N X K 1 XK P 1 P 1 P AND XI N I 1 MAX 1 I N XI IT S EASY TO SEE THAT 1 AND DE NE NORMS THE OTHER CASES TAKE A BIT MORE WORK WE LL SUPPLY FULL DETAILS LATER 3 OUR ORIGINAL PROBLEM CONCERNS X C A B THE SPACE OF ALL CONTINUOUS FUNCTIONS F A B R UNDER THE UNIFORM NORM F MAX A X B F X THE WORD UNIFORM IS USED BECAUSE CONVERGENCE IN THIS NORM IS THE SAME AS UNIFORM CONVERGENCE ON A B FN F 0 FN F ON A B IN THIS CASE WE RE INTERESTED IN APPROXIMATIONS BY ELEMENTS OF Y PN THE SUBSPACE OF ALL POLYNOMIALS OF DEGREE AT MOST N IN C A B IT S NOT HARD TO SEE THAT PN IS A NITE DIMENSIONAL SUBSPACE OF C A B OF DIMENSION EXACTLY N 1 WHY IF WE CONSIDER THE SUBSPACE Y P CONSISTING OF ALL POLYNOMIALS IN X C A B WE READILY SEE THAT THE EXISTENCE OF BEST APPROXIMATIONS CAN BE PROBLEMATIC IT FOLLOWS PRELIMINARIES 3 FROM THE WEIERSTRASS THEOREM FOR EXAMPLE THAT EACH F C A B HAS DISTANCE 0 FROM P BUT SINCE NOT EVERY F C A B IS A POLYNOMIAL WHY WE CAN T HOPE FOR A BEST APPROXIMATING POLYNOMIAL TO EXIST IN EVERY CASE FOR EXAMPLE THE FUNCTION F X X SIN 1 X IS CONTINUOUS ON 0 1 BUT CAN T POSSIBLY AGREE WITH ANY POLYNOMIAL ON 0 1 WHY THE KEY TO THE PROBLEM OF POLYNOMIAL APPROXIMATION IS THE FACT THAT EACH PN IS NITE DIMENSIONAL TO SEE THIS IT WILL BE MOST E CIENT TO CONSIDER THE ABSTRACT SETTING OF NITE DIMENSIONAL SUBSPACES OF ARBITRARY NORMED SPACES SOFT APPROXIMATION LEMMA LET V BE A NITE DIMENSIONAL VECTOR SPACE THEN ALL NORMS ON V ARE EQUIVALENT THAT IS IF AND ARE NORMS ON V THEN THERE EXIST CONSTANTS 0 A B SUCH THAT A X X B X FOR ALL VECTORS X V PROOF SUPPOSE THAT V IS N DIMENSIONAL AND THAT IS A NORM ON V FIX A BASIS E1 EN FOR V AND CONSIDER THE NORM N X I 1 AIEI 1 N X I 1 AI AI N I 1 1 FOR X PN I 1 AIEI V SINCE E1 EN IS A BASIS FOR V IT S NOT HARD TO SEE THAT 1 IS INDEED A NORM ON V IT NOW SU CES TO SHOW THAT AND 1 ARE EQUIVALENT WHY ONE INEQUALITY IS EASY TO SHOW INDEED NOTICE THAT N X I 1 AIEI N X I 1 AI EI MAX 1 I N EI N X I 1 AI B N X I 1 AIEI 1 THE REAL WORK COMES IN ESTABLISHING THE OTHER INEQUALITY TO BEGIN NOTICE THAT WE VE ACTUALLY SET UP A CORRESPONDENCE BETWEEN RN AND V SPECI CALLY THE MAP AI N I 1 7 PN I 1 AIEI IS OBVIOUSLY BOTH ONE TO ONE AND ONTO MOREOVER THIS CORRESPONDENCE IS AN ISOMETRY BETWEEN RN 1 AND V 1