STEP 22

INTERPOLATION 2

Newton interpolation formulae

The linear and quadratic interpolation formulae are based on first and second degree polynomial approximations. Newton has derived general forward and backward difference interpolation formulae, corresponding for tables with constant interval h. (For tables with variable interval, we can use an interpolation procedure in Step 24 involving divided differences.)

1. Newton's forward difference formula

   Consider the points x_j, x_j + h, x_j + 2h, . . ., and recall that

   ,

   where q is any real number. Formally, one has (since )

   ,

   which is Newton's forward difference formula. The linear and quadratic (forward) interpolation formulae correspond to first and second order truncation, respectively. If we truncate at n-th order, we obtain

   

   which is an approximation based on the values f_j, f_j+1,. . . , f_j+n. It will be exact if (within round-off errors)

   

   which is the case if f is a polynomial of degree n.

2. Newton's backward difference formula

   Formally, one has (since Newton's backward difference formula. The linear and quadratic (backward) interpolation formulae correspond to truncation at first and second order, respectively. The approximation based on the f_j-n, f_j-1, . . . , f_j-n is

   

3. Use of Newton's interpolation formulae

   Newton's forward and backward difference formulae are wel1 suited for use at the beginning and end of a difference table, respectively. (Other formulae which use central differences may be more convenient elsewhere.)

   As an example, consider the difference table of f (x) = sin x for x = 0°( 10°)50°:

   .

   Since the fourth order differences are constant, we conclude that a quartic approximation is appropriate. (The third-order differences are not quite constant within expected round-offs, and we anticipate that a cubic approximation is not quite good enough.) In order to determine sin 5° from the table, we use Newton's forward difference formula (to fourth order); thus, taking x_j = 0, we find and

   

   Note that we have kept a guard digit (in parentheses) to minimize accumulated round-off error.

   In order to determine sin 45° from the table, we use Newton's backward difference formula (to fourth order); thus, taking x_j = 40, we find and

   

4. Uniqueness of the interpolating polynomial

   Given a set of values f(x₀), f(x₁), . . , f(x_n) with x_j = x₀ + jh, we have two interpolation formulae of order n available:

   

   Clearly, P_n and Q_n are both polynomials of degree n. It can be verified (Exercise 2) that P_n(x_j) = Q_n(x_j) = f(x_j) for j = 0,1, 2, . . . , n, which implies that P_n - Q_n is a polynomial of degree n which vanishes at (n + 1 ) points. In turn, this implies that P_n - Q_n º 0, or P_n º Q_n. In fact, a polynomial of degree n through any given (n + 1) (distinct but not necessarily equidistant) points is unique, and is called the interpolating polynomial.

5. Analogy with Taylor series

   If we define for an integer k

   

   the Taylor series (STEP 5) about x_j becomes

   

   Setting we have formally

   

   A comparison with Newton's interpolation formula

   

   shows that the operator (applied to functions of a continuous variable) is analogous to the operator E (applied to functions of a discrete variable).

   Checkpoint

   1. What is the relationship between the forward and backward linear and quadratic interpolation formulae (for a table of constant interval h) and Newton's interpolation formulae?
      
   2. When do you use Newton's forward difference formula?
      
   3. When do you use Newton's backward difference formula?

   EXERCISES

   1. From a difference table of f (x) = e^x to 5D for x = 0.10(0.05)0.40, estimate:
      1. e^0.14 by means of Newton's forward difference formula;
         
      2. e^0.315 by means of Newton's backward difference formula.
         
   2. Show that for j = 0, 1, 2, . . .,

      

   3. Derivc the equation of the interpolating polynomial for the data.

      

Answers

last next