ERROR IN LINEAR INTERPOLATION

1 ERROR IN LINEAR INTERPOLATIONLetP1(x) be the LINEAR polynomial interpolatingf(x) (x) is twice continuously differentiable on an interval[a,b] which contains the pointsx0<x1. Then fora x b,f(x) P1(x) =(x x0) (x x1)2f (cx)for somecxbetween the minimum and maximum ofx0,x1, usually useP1(x) as an approximation off(x) forx [x0,x1].Then for an ERROR bound,|f(x) P1(x)| (x x0) (x1 x)2maxx0 x x1|f (x)|,x [x0,x1].Easily, withh=x1 x0,maxx0 x x1(x x0) (x1 x) =h2 ,|f(x) P1(x)| h28maxx0 x x1|f (x)|,x [x0,x1].EXAMPLELetf(x) = log10x; and in line with typical tables of log10x, wetake 1 x0 x x1 10, and again leth=x1 x0. Thenf (x) = log10ex2maxx0 x x1|f (x)|= ,|log10x P1(x)| h28log10ex20,x [x0,x1].Typical high school algebra textbooks contain tables of log10xwith a spacing ofh=.

2 01. What is the ERROR in this case?|log10x P1(x)| 10 most tables, a typical entry is given to only four decimal placesto the right of the decimal point, the entries are in ERROR by as much as .00005. Comparingthis with the INTERPOLATION ERROR , we see the latter (withh=.01) isless important than the rounding errors in the table the bound,|log10x P1(x)| see the ERROR decreases asx0increases, and it is about 100times smaller for points near 10 than for points near QUADRATIC CASEForn= 2, we havef(x) P2(x) =(x x0) (x x1) (x x2)3!f(3)(cx)(*)withcxsome point between the minimum and maximum of thepoints in{x,x0,x1,x2}.To illustrate the use of this formula, consider the case of evenlyspaced nodes:x1=x0+h,x2=x1+hFurther suppose we havex0 x x2, as we would usually havewhen interpolating in a table of given function values ( ).

3 The quantity 2(x) = (x x0) (x x1) (x x2)can be evaluated directly for a of 2(x) = (x+h)x(x h)using (x0,x1,x2) = ( h,0,h):xyh hIn the formula ( ), however, we do not knowcx, and therefore wereplace f(3)(cx) with a maximum of f(3)(x) asxvaries overx0 x x2. This yields|f(x) P2(x)| | 2(x)|3!maxx0 x x2 f(3)(x) (**)If we want a uniform bound forx0 x x2, we must computemaxx0 x x2| 2(x)|= maxx0 x x2|(x x0) (x x1) (x x2)|With a change of variablesx=x1+t h,x x0= (1 +t)h,x x1=t h,x x2= (t 1)hmaxx0 x x2| 2(x)|=h3max 1 t 1 t t3 =2h33 3 Combined with ( ), this yields|f(x) P2(x)| h39 3maxx0 x x2 f(3)(x) forx0 x (x) = log10x, with 1 x0 x x2 10,this leads to|log10x P2(x)| h39 3 maxx0 x x22 log10ex3=.05572h3x30 For the case ofh=.

4 01, we have|log10x P2(x)| 10 8x30 10 8 For comparison,|log10x P1(x)| 10 6 Question: How much larger could we makehso that quadraticinterpolation would have an ERROR comparable to that of linearinterpolation of log10xwithh=.01? The ERROR bound for thelinear INTERPOLATION was 10 6, and therefore we want thesame to be true of quadratic INTERPOLATION . Using a simpler bound,we want to findhso that|log10x P2(x)| .05572h3 5 10 6 This is true ifh=.04477. Therefore a spacing ofh=.04 wouldbe sufficient. A table with this spacing and quadratic interpolationwould have an ERROR comparable to a table withh=.01 and ERROR FORMULA: THE GENERAL CASER ecall the general INTERPOLATION problem: find a polynomialPn(x)for which deg(Pn) nPn(xi) =f(xi),i= 0,1, ,nwith distinct node points{x0.}

5 ,xn}and a given functionf(x).Let [a,b] be a given interval on whichf(x) is (n+ 1)-timescontinuously differentiable; and assume the pointsx0,..,xn, andxare contained in [a,b]. Thenf(x) Pn(x) =(x x0) (x x1) (x xn)(n+ 1)!f(n+1)(cx)withcxsome point between the minimum and maximum of thepoints in{x,x0,..,xn}.As shorthand, introduce n(x) = (x x0) (x x1) (x xn)a polynomial of degreen+ 1 with roots{x0,..,xn}. Thenf(x) Pn(x) = n(x)(n+ 1)!f(n+1)(cx)When bounding the ERROR we replacef(n+1)(cx) with its maximumover the interval containing{x,x0,..,xn}, as we have illustratedearlier in the LINEAR and quadratic concentrate on understanding the size of n(x)or n(x)(n+ 1)! ERROR FOR EVENLY SPACED NODESWe consider first the case in which the node points are evenlyspaced, as this seems the natural way to define the points atwhich INTERPOLATION is carried out.

6 Moreover, using evenly spacednodes is the case to consider for table evenly spaced node points on [0,1],h=1n,x0= 0,x1=h,x2= 2h,..,xn=nh= 1 For this case, n(x) =x(x h) (x 2h) (x 1)Using the following 12we can observe that the maximumMn maxx0 x xn| n(x)|(n+ 1)!becomes smaller with of n(x) are shown next for the cases ofn= 2,.., = 21xyn = 31xyn = 41xyn = 51 Figure: Graphs of n(x) on [0,1] forn= 2,3,4,5xyn = 61xyn = 71xyn = 81xyn = 91 Figure: Graphs of n(x) on [0,1] forn= 6,7,8,9 More detailed view of the graph of 6(x) = (x x0) (x x1) (x x6)with evenly spaced nodes:xx0x1x2x3x4x5x6 What can we learn from the given graphs? Observe that there isenormous variation in the size of n(x) asxvaries over [0,1]; andthus there is also enormous variation in the ERROR asxso example, in then= 9 case,maxx0 x x1| n(x)|(n+ 1)!

7 = 10 11maxx4 x x5| n(x)|(n+ 1)!= 10 13and the ratio of these two errors is approximately 49. Thus theinterpolation ERROR is likely to be around 49 times larger whenx0 x x1as compared to the case whenx4 x x5. Whendoing table INTERPOLATION , the pointxat which we interpolateshould be centrally located with respect to the INTERPOLATION nodes{x0,..,xn}being used to define the INTERPOLATION , if on ConvergenceConsider now the problem of using an INTERPOLATION polynomial toapproximate a given functionf(x) on a given interval [a,b]. Inparticular, take INTERPOLATION nodesa x0<x1< <xn 1<xn band produce the INTERPOLATION polynomialPn(x) that interpolatesf(x) at the given node points. We would like to havemaxa x b|f(x) Pn(x)| 0asn Does it happen?

8 Recall the ERROR boundmaxa x b|f(x) Pn(x)| maxa x b| n(x)|(n+ 1)! maxa x b f(n+1)(x) We begin with an example using evenly spaced node S EXAMPLEUse evenly spaced node points:h=b an,xi=a+ihfori= 0,..,nFor some functions, such asf(x) =ex, the maximum ERROR goes tozero quite rapidly. But the size of the derivative termf(n+1)(x) inmaxa x b|f(x) Pn(x)| maxa x b| n(x)|(n+ 1)! maxa x b f(n+1)(x) can badly hurt or destroy the convergence of other particular, we show the graph off(x) = 1/(1 +x2)andPn(x)on [ 5,5] for the casesn= 8 andn= 12. The casen= 10 is inthe text on page 127. It can be proven that for this function, themaximum ERROR on [ 5,5] does not converge to zero. Thus the useof evenly spaced nodes is not necessarily a good approach toapproximating a functionf(x) by (x)y=1/(1+x2)Figure: Runge s example withn= 10 OTHER CHOICES OF NODESR ecall the general ERROR boundmaxa x b|f(x) Pn(x)| maxa x b| n(x)|(n+ 1)!

9 Maxa x b f(n+1)(x) There is nothing we really do with the derivative term forf; butwe can examine the way of defining the nodes{x0,..,xn}withinthe interval [a,b]. We ask how these nodes can be chosen so thatthe maximum of| n(x)|over [a,b] is made as small as is an elegant solution to this problem, and it is taken up in The node points{x0,..,xn}turn out to be the zeros of aparticular polynomialTn+1(x) of degreen+ 1, called aChebyshevpolynomial. These zeros are known explicitly, and with themmaxa x b| n(x)|=(b a2)n+12 nThis turns out to be smaller than for evenly spaced cases; andalthough this polynomial INTERPOLATION does not work for allfunctionsf(x), it works for all differentiable functions and ERROR FORMULAR ecall the ERROR formulaf(x) Pn(x) = n(x)(n+ 1)!

10 F(n+1)(c) n(x) = (x x0) (x x1) (x xn)withcbetween the minimum and maximum of{x0,..,xn,x}. A second formula is given byf(x) Pn(x) = n(x)f[x0,..,xn,x]To show this is a simple, but somewhat subtle +1(x) denote the polynomial of degree n+ 1 whichinterpolatesf(x) at the points{x0,..,xn,xn+1}. ThenPn+1(x) =Pn(x) +f[x0,..,xn,xn+1] (x x0) (x xn)Substitutingx=xn+1, and using the fact thatPn+1(x)interpolatesf(x) atxn+1, we havef(xn+1) =Pn(xn+1) +f[x0,..,xn,xn+1] (xn+1 x0) (xn+1 xn)In this formula, the numberxn+1is completely arbitrary, otherthan being distinct from the points in{x0,..,xn}. To emphasizethis fact, replacexn+1byxthroughout the formula, obtainingf(x) =Pn(x) +f[x0,..,xn,x] (x x0) (x xn)=Pn(x) + n(x)f[x0,..,xn,x]providedx6=x0.