STEP 23

INTERPOLATION 3

Lagrange interpolation formula

The linear and quadratic interpolation formulae of Steps 19 - 21 correspond to first and second degree polynomial approximations, respectively. In Step 22, we have discussed Newton's forward and backward interpolation formulae and noted that higher order interpolation corresponds to higher degree polynomial approximation. In this Step we consider an interpolation formula attributed to Lagrange, which does not require function values at equal intervals. Lagrange's interpolation formula has the disadvantage that the degree of the approximating polynomial must be chosen at the outset; an alternative approach is discussed in the next Step. Thus, Lagrange's formula is mainly of theoretical interest for us here; in passing, we mention that there are some important applications of this formula beyond the scope of this book - for example, the construction of basis functions to solve differential equations using a spectral (discrete ordinate) method.

1. Procedure

   Let the function f be tabulated at (n + 1), not necessarily equidistant points x_j, j = 1, 2,…., n and be approximated by the polynomial

   

   of degree at most n, such that

   

   Since for k = 0,1, 2, . . , n

   

   is a polynomial of degree n which satisfies

   

   then:

   

   is a polynomial of degree n which satisfies

   

   Hence,

   

   is a polynomial of degree (at most) n such that

   ,

   i.e., the (unique) interpolating polynomial. Note that for x = x_j all terms in the sum vanish except the j-th, which is f_j; L_k(x) is called the k-th Lagrange interpolation coefficient, and the identity

   

   (established by setting f(x) º 1) may be used as a check. Note also that with n = 1 we recover the linear interpolation formula:

   

   of Step 21.

2. Example

   We will use Lagrange's interpolation formula to find the interpolating polynomial P₃ through the points (0, 3), (1, 2), (2, 7), and (4, 59), and then find the approximate value P₃(3).

   The Lagrange coefficients are:

   

   (The student should verify that Hence, the required polynomial is

   

   Consequently, However, note that, if the explicit form of the interpolating polynomial were not required, one would proceed to evaluate P₃(x) for some value of x directly from the factored forms of L_k(x). Thus, in order to evaluate P₃(3), one has

   

3. Notes of caution

   In the case of the Newton interpolation formulae, considered in the preceding Step, or the formulae to be discussed in the next Step, the degree of the required approximating polynomial may be determined merely by computing terms until they no longer appear to be significant. In the Lagrange procedure, the polynomial degree must be chosen at the outset! Also, note that

   1. a change of degree involves recomputation of all terms; and
      
   2. for a polynomial of high degree the process involves a large number of multiplications, whence it may be quite slow.

   Lagrange interpolation should be used with considerable caution. For example, let us employ it to obtain an estimate of from the points (0, 0), (1,1), (8, 2), (27, 3), and (64, 4) on . We find

   

   so that which is not very close to the correct value 2.7144! A better result (i.e., 2,6316) can be obtained by linear interpolation between (8, 2) and (27, 3). The problem is that the Lagrange method yields no indication as to how well is represented by a quartic. In practice, therefore, Lagrange interpolation is used only rarely.

Checkpoint

1. When is the Lagrange interpolation formula used in practical computations?
   
2. What distinguishes the Lagrange formula from many other interpolation formulae?
   
3. Why should the Lagrange formula be used in practice only with caution?

EXERCISE

Given that f (-2) = 46, f (-1 ) = 4, f ( 1 ) = 4, f (3) = 156, and f (4) = 484, use Lagrange's interpolation formula to estimate the value of f(0).

Answer

last next