STEP 20

FINITE DIFFERENCES 3

Polynomials

Since polynomial approximations are used in many areas of Numerical Analysis, it is important to investigate the phenomena of differencing polynomials.

1. Finite differences of a polynomial

Consider the finite differences of an n-th degree polynomial

,

tabulated for equidistant points at the tabular interval h.

Theorem: The n-th difference of a polynomial of degree n is a constant proportional to n
_{and higher order differences are zero.}

_{Proof: For any positive integer k, the binomial expansion}

_,

_yields

_.

_{Omitting the subscript of x, we find}

_.

_{In passing, the student may recall that in the Differential Calculus the increment is related to the derivative of f (x) at the point x.}

_{2. Example}

_{Construct for f (x) = x}³ _{with x = 5.0(0.1)5.5 the difference table:}

_{Since in this case n = 3, an =1, h = 0.1, we find}

_{Note that round-off error noise may occur; for example, consider the tabulation of f(x) = x}3 _{for 5.0(0.1)5.5, rounded to two decimal places:}

_{3. Approximation of a function by a polynomial}

_{Whenever the higher differences of a table become small (allowing for round-off noise), the function represented may be approximated well by a polynomial. For example, reconsider the difference table of 6D for f (x ) = e}x _{with x = 0.1(0.05)0.5:}

_{Since the estimate for round-off error at (cf. the table in STEP 12), we say that third differences are constant within round-off error, and deduce that a cubic approximation is appropriate for e}x _{over the range 0.1 < x < 0.5. An example in which polynomial approximation is inappropriate occurs when f(x) = 10}x _{for x = 0(1)4, as is shown by the next table:}

_{Although the function f(x) = 10}x _{is `smooth', the large tabular interval (h = 1) produces large higher order finite differences. It should also be understood that there exist functions that cannot usefully be tabulated at all, at least in certain neighbourhoods; for example, f(x) = sin(1/x) near the origin x = 0. Nevertheless, these are fairly exceptional cases.}

_{Finally, we remark that the approximation of a function by a polynomial is fundamental to the widespread use of finite difference methods.}

_Checkpoint

1. _{What may be said about the higher order (exact) differences of a polynomial?}
   
2. _{What is the effect of round-off error on the higher order differences of a polynomial?}
   
3. _{When may a function be approximated by a polynomial?}

_EXERCISES

1. _{Construct a difference table for the polynomial f(x) = x}4 _{for x = 0(0.1)1 when}
   1. _{the values of f are exact;}
   2. _{the values of f have been rounded to 3D.}
   3. _{Compare the fourth difference round-off errors with the estimate +/-6.}
   4.  
2. _{Find the degree of the polynomial which fits the data in the table:}

   

Answers

last next