Polynomial Approximation and Interpolation Chapter 4

Polynomial Approximation and Interpolation Chapter 4

Nizar Salim 2 lecture 2

Consider two points, [a,f(a)] and [b,f(b)]. The linear Lagrange polynomial

P1(x) which passes through these two points is given by

The Lagrange polynomial can be used for both unequally spaced data

and equally spaced data. No system of equations must be solved to evaluate

the polynomial. However, a considerable amount of computational effort is

involved, especially for higher-degree polynomials.

The form of the Lagrange polynomial is quite different in appearance

from the form of the direct fit polynomial, Eq. (4.34). However, by the

Polynomial Approximation and Interpolation Chapter 4

Nizar Salim 3 lecture 2

uniqueness theorem, the two forms both represent the unique polynomial

that passes exactly through a set of points.

Polynomial Approximation and Interpolation Chapter 4

Nizar Salim 4 lecture 2

The results are summarized below, where the results of linear, quadratic, and

cubic interpolation, and the errors, Error(3.44) = P(3.44) = 0.290698, are

tabulated. The advantages of higher-degree interpolation are obvious.

P(3.44) = 0.290756 linear interpolation Error = 0.000058

= 0.290697 quadratic interpolation = -0.000001

= 0.290698 cubic interpolation = 0.000000

These results are identical to the results obtained in Example 4.2 by

direct fit polynomials, as they should be, since the same data points are used

in both examples.

The main advantage of the Lagrange polynomial is that the data may be

unequally spaced. There are several disadvantages. All of the work must be

redone for each degree polynomial. All the work must be redone for each

value of x. The first disadvantage is eliminated by Neville s algorithm,

which is presented in the next subsection. Both disadvantages are eliminated

by using divided differences, which are presented in Section 4.5.

Polynomial Approximation and Interpolation Chapter 4

Nizar Salim 5 lecture 2

where the subscript i denotes the base point of the value (e.g., i,i+ 1, etc.)

and the superscript (n) denotes the degree of the interpolation (e.g., zeroth,

first, second, etc.).

A table of linearly interpolated values is constructed for the original

data, which are denoted as fi

(0). For the first interpolation of the data,

Polynomial Approximation and Interpolation Chapter 4

Nizar Salim 6 lecture 2

as illustrated in Figure 4.6a. This creates a column of n - 1 values of fi

(1) . A

second column of n - 2 values of fi

(2) is obtained by linearly interpolating

the column of fi

(1) values. Thus,

which is illustrated in Figure 4.6b. This process is repeated to create a third

column of fi

(3) values, as illustrated in Figure 4.6c, and so on. The form of

the resulting table is illustrated in Table 4.1.

Polynomial Approximation and Interpolation Chapter 4

Nizar Salim 7 lecture 2

It can be shown by direct substitution that each specific value in Table

4.1 is identical to a Lagrange polynomial based on the data points used to

calculate the specific value. For example,f1

Consider the four data points given in Example 4.3. Let s interpolate for

Polynomial Approximation and Interpolation Chapter 4

Nizar Salim 8 lecture 2

Polynomial Approximation and Interpolation Chapter 4

Nizar Salim 9 lecture 2

Thus, the result of quadratic interpolation is f(3.44) =f1

(2) = 0.290696. To

evaluate ,f1

A divided difference is defined as the ratio of the difference in the

function values at two points divided by the difference in the values of the

corresponding independent variable. Thus, the first divided difference at

point i is defined as

Polynomial Approximation and Interpolation Chapter 4

Nizar Salim 10 lecture 2

Similar expressions can be obtained for divided differences of any order.

Approximating polynomials for no equally spaced data can be constructed

using divided differences.

Consider a table of data:

By definition, f[xi] =fi .

The notation presented above is a bit clumsy. A more compact notation

is defined in the same manner as the notation used in Neville s method,

which is presented in Section 4.4.2. Thus,

Polynomial Approximation and Interpolation Chapter 4

Nizar Salim 11 lecture 2

Table 4.3 illustrates the formation of a divided difference table. The

first column contains the values of xi and the second column contains the

values of f(xi) =fi , which are denoted by fi

(0). The remaining columns

contain the values of the divided differences, fi

(n) where the subscript i

denotes the base point of the value and the superscript (n) denotes the degree

of the divided difference.

The data points do not have to be in any specific order to apply the

divided difference concept. However, just as for the direct fit polynomial,

the Lagrange polynomial, and Neville s method, more accurate results are

obtained if the data are arranged in order of closeness to the interpolated

point.

Let s construct a six-place divided difference table for the data presented in

Section 4.1.

The results are presented in Table 4.4.

Polynomial Approximation and Interpolation Chapter 4

Nizar Salim 12 lecture 2

Let s define a power series for Pn(x) such that the coefficients are identical to

the divided differences, fi

(n) Thus,

Polynomial Approximation and Interpolation Chapter 4

Nizar Salim 13 lecture 2

Since Pn(x) is a polynomial of degree n and passes exactly through the n + 1

data points, it is obviously one form of the unique polynomial passing

through the data points.

.

Consider the divided difference table presented in Example 4.5. Let s

interpolate for f(3.44) using the divided difference polynomial, Eq. (4.65),

using x0 = 3.35 as the base point. The exact solution is

Polynomial Approximation and Interpolation Chapter 4

Nizar Salim 14 lecture 2

The advantage of higher-degree interpolation is obvious.

The above results are not the most accurate possible since the data

points in Table 4.4 are in monotonic order, which make the linear

interpolation result actually linear extrapolation. Rearranging the data in

order of closeness to x = 3.44 yields the results presented in Table 4.5. From

Eq. (4.65):

Polynomial Approximation and Interpolation Chapter 4

Nizar Salim 15 lecture 2

The linear interpolation value is much more accurate due to the centering of

the data. The quadratic and cubic interpolation values are the same as before,

except for round-off errors, because the same points are used in those two

interpolations. These results are the same as the results obtained in the

previous examples.

This document was created with Win2PDF available at http://www.daneprairie.com.

The unregistered version of Win2PDF is for evaluation or non-commercial use only.