5 Numerical Differentiation

1 D. Levy5 Numerical Basic ConceptsThis chapter deals with Numerical approximations of derivatives . The first questionsthat comes up to mind is: why do we need to approximate derivatives at all? Afterall, we do know how to analytically differentiate every function. Nevertheless, there areseveral reasons as of why we still need to approximate derivatives : Even if there exists an underlying function that we need to differentiate, we mightknow its values only at a sampled data set without knowing the function itself. There are some cases where it may not be obvious that an underlying functionexists and all that we have is a discrete data set.

2 We may still be interested instudying changes in the data, which are related, of course, to derivatives . There are times in which exact formulas are available but they are very complicatedto the point that an exact computation of the derivative requires a lot of functionevaluations. It might be significantly simpler to approximate the derivative insteadof computing its exact value. When approximating solutions to ordinary (or partial) differential equations, wetypically represent the solution as a discrete approximation that is defined on agrid. Since we then have to evaluate derivatives at the grid points, we need to beable to come up with methods for approximating the derivatives at these points,and again, this will typically be done using only values that are defined on a underlying function itself (which in this cased is the solution of the equation)is simple approximation of the first derivative isf (x) f(x+h) f(x)h,( )where we assume thath >0.

3 What do we mean when we say that the expression onthe right-hand-side of ( ) is an approximation of the derivative? For linear functions( ) is actually an exact expression for the derivative. For almost all other functions,( ) is not the exact s compute the approximation error. We write a Taylor expansion off(x+h)aboutx, ,f(x+h) =f(x) +hf (x) +h22f ( ), (x, x+h).( )For such an expansion to be valid, we assume thatf(x) has two continuous Taylor expansion ( ) means that we can now replace the approximation ( ) Basic ConceptsD. Levyan exact formula of the formf (x) =f(x+h) f(x)h h2f ( ), (x, x+h).

4 ( )Since this approximation of the derivative atxis based on the values of the function atxandx+h, the approximation ( ) is called aforward differencingorone-sideddifferencing. The approximation of the derivative atxthat is based on the values ofthe function atx handx, ,f (x) f(x) f(x h)h,is called abackward differencing(which is obviously also a one-sided differencingformula).The second term on the right-hand-side of ( ) is theerror term. Since the ap-proximation ( ) can be thought of as being obtained by truncating this term from theexact formula ( ), this error is called thetruncation error.

5 The small parameterhdenotes the distance between the two pointsxandx+h. As this distance tends to zero, ,h 0, the two points approach each other and we expect the approximation ( )to improve. This is indeed the case if the truncation error goes to zero, which in turn isthe case iff ( ) is well defined in the interval (x, x+h). The speed in which the errorgoes to zero ash 0 is called therate of convergence. When the truncation error isof the order ofO(h), we say that the method isa first order method. We refer to amethods asapth-order methodif the truncation error is of the order ofO(hp).

6 It is possible to write more accurate formulas than ( ) for the first derivative. Forexample, a more accurate approximation for the first derivative that is based on thevalues of the function at the pointsf(x h) andf(x+h) is thecentered differencingformulaf (x) f(x+h) f(x h)2h.( )Let s verify that this is indeed a more accurate formula than ( ). Taylor expansionsof the terms on the right-hand-side of ( ) aref(x+h) =f(x) +hf (x) +h22f (x) +h36f ( 1),f(x h) =f(x) hf (x) +h22f (x) h36f ( 2).Here 1 (x, x+h) and 2 (x h, x). Hencef (x) =f(x+h) f(x h)2h h212[f ( 1) +f ( 2)],2D.

7 Differentiation Via Interpolationwhich means that the truncation error in the approximation ( ) is h212[f ( 1) +f ( 2)].If the third-order derivativef (x) is a continuous function in the interval [x h, x+h],then the intermediate value theorem implies that there exists a point (x h, x+h)such thatf ( ) =12[f ( 1) +f ( 2)].Hencef (x) =f(x+h) f(x h)2h h26f ( ),( )which means that the expression ( ) is a second-order approximation of the first a similar way we can approximate the values of higher-order derivatives . Forexample, it is easy to verify that the following is a second-order approximation of thesecond derivativef (x) f(x+h) 2f(x) +f(x h)h2.

8 ( )To verify the consistency and the order of approximation of ( ) we expandf(x h) =f(x) hf (x) +h22f (x) h36f (x) +h424f(4)( ).Here, (x h, x) and + (x, x+h). Hencef(x+h) 2f(x) +f(x h)h2=f (x)+h224(f(4)( ) +f(4)( +))=f (x)+h212f(4)( ),where we assume that (x h, x+h) and thatf(x) has four continuous derivativesin the interval. Hence, the approximation ( ) is indeed a second-order approximationof the derivative, with a truncation error that is given by h212f(4)( ), (x h, x+h). Differentiation Via InterpolationIn this section we demonstrate how to generate differentiation formulas by differentiatingan interpolant.

9 The idea is straightforward: the first stage is to construct an interpo-lating polynomial from the data. An approximation of the derivative at any point canbe then obtained by a direct differentiation of the Differentiation Via InterpolationD. LevyWe follow this procedure and assume thatf(x0), .. , f(xn) are given. The Lagrangeform of the interpolation polynomial through these points isQn(x) =n j=0f(xj)lj(x).Here we simplify the notation and replacelni(x) which is the notation we used in Sec-tion??byli(x). According to the error analysis of Section??we know that the inter-polation error isf(x) Qn(x) =1(n+ 1)!

10 F(n+1)( n)n j=0(x xj),where n (min(x, x0, .. , xn),max(x, x0, .. , xn)). Since here we are assuming that thepointsx0, .. , xnare fixed, we would like to emphasize the dependence of nonxandhence replace the nnotation by x. We that have:f(x) =n j=0f(xj)lj(x) +1(n+ 1)!f(n+1)( x)w(x),( )wherew(x) =n i=0(x xi).Differentiating the interpolant ( ):f (x) =n j=0f(xj)l j(x) +1(n+ 1)!f(n+1)( x)w (x) +1(n+ 1)!w(x)ddxf(n+1)( x).( )We now assume thatxis one of the interpolation points, ,x {x0, .. , xn}, sayxk,so thatf (xk) =n j=0f(xj)l j(xk) +1(n+ 1)!f(n+1)( xk)w (xk).( )Now,w (x) =n i=0n j=0j6=i(x xj) =n i=0[(x x0).]