Chapter 2: Polynomial Interpolation
1. INTRODUCTION:
You will frequently have occasion to estimate intermediate values between
precise data points. The most common method used for this purpose is
polynomial interpolation. The general formula for an nth-order polynomial is:
f(x) = a 0 +a1x +a 2x2 +···+a nxn
For n+1 data points, there is one and only one polynomial of order n that
passes through all the points. For example, there is only one straight line (that
is, a first-order polynomial) that connects two points (Fig 1a). Similarly, only
one parabola connects a set of three points (Fig. 1b). Polynomial interpolation
consists of determining the unique nth-order polynomial that fits n+1 data
points. This polynomial then provides a formula to compute intermediate
values. Although there is one and only one nth-order polynomial that fits n+1
point, there are a variety of mathematical formats in which this polynomial can
be expressed. In this chapter, we will describe two alternatives that are well-
suited for computer implementation: the Newton and the Lagrange
polynomials.
Figure 1
1
2. NEWTON’S DIVIDED-DIFFERENCE INTERPOLATING POLYNOMIAL
As stated above, there are a variety of alternative forms for expressing an
interpolating polynomial. Newton’s divided-difference interpolating
polynomial is among the most popular and useful forms. Before presenting the
general equation, we will introduce the first and second-order versions
because of their simple visual interpretation.
2.1 Linear Interpolation
The simplest form of interpolation is to connect two data points with a straight
line. This technique, called linear interpolation, is depicted graphically in Fig.2.
Using similar triangles:
( ) ( ) ( ) ( )
Which can be rearranged to yield
( ) ( )
( ) ( ) ( )
Which is the linear-interpolation formula. The notation f 1(x) designates that
this is a first order interpolating polynomial. Notice that besides representing
the slope of the line connecting the points, the term
( ) ( )
is a finite-divided-difference approximation of the first derivative . In general,
the smaller the interval between the data points, the better the
approximation. This is due to the fact that, as the interval decreases, a
continuous function will be better approximated by a straight line. This
characteristic is demonstrated in the following example.
2
Figure 2
Example 2.1.1
Estimate the natural logarithm of 2 using linear interpolation. First, perform
the computation by interpolating between ln 1=0 and ln 6=1.791759. Then,
repeat the procedure, but use a smaller interval from ln 1 to ln 4 (1.386294).
Note that the true value of ln 2 is 0.6931472.
We use a linear interpolation for ln(2)
from x0 =1 to x1 =6 to give:
( ) ( )
ε=(0.6931472-
)/0.6931472=0.483=48.3%
Using the smaller interval from x0 =1 to x1 =4 yields:
( ) ( )
ε=(0.6931472- )/0.6931472=0.333=33.3%
Thus, using the shorter interval reduces the percent relative error to ε =33.3%
3
2.2 Quadratic Interpolation
The error in Example 2.1.1 resulted from our approximating a curve with a
straight line. Consequently, a strategy for improving the estimate is to
introduce some curvature into the line connecting the points. If three data
points are available, this can be accomplished with a second-order polynomial
(also called a quadratic polynomial or a parabola). A particularly convenient
form for this purpose is
( ) ( ) ( )( )
A simple procedure can be used to determine the values of the coefficients.
For b0 with x=x0 can be used to compute:
b0=f(x0).
b1 at x=x1 for
( ) ( )
b2
( ) ( ) ( ) ( )
Example 2.2.1
Estimate the natural logarithm of 2 using a quadratic interpolation (second-
order polynomial)
x x0 = 1 x1 = 4 x2 = 6 x=2
f(x)=ln(x) f(x0)=0 f(x1)=1.386294 f(x2)=1.791759 ?
b0=0;
4
( ) ( )
=0.4620981
( ) ( ) ( ) ( )
=-0.518731
( ) ( ) ( )( )=0.5658444
So ; ε=18.4%
Thus, the curvature introduced by the quadratic formula improves the
interpolation compared with the result obtained using straight lines.
2.3 General Form of Newton’s Interpolating Polynomials
The preceding analysis can be generalized to fit an nth-order polynomial to n+1
data points. The nth-order polynomial is:
( ) ( ) ( )( ) ( )
As was done previously with the linear and quadratic interpolations, data
points can be used to evaluate the coefficients b 0, b1, . . . , bn . For an nth-order
polynomial, n+1 data points are required: [x0, f(x0)], [x1, f(x1)], . . . , [xn , f(xn )].
We use these data points and the following equations to evaluate the
coefficients:
b0=f(x 0).
b1=f[x1,x0]
b2=f[x2, x1,x0]
.
.
bn=f[x n, xn-1,…..,x1, x0]
5
Where the bracketed function evaluations are finite divided differences. For
example, the first finite divided difference is represented generally as:
( ) ( )
[ ]
( )
The second finite divided difference, which represents the difference of two
first divided differences, is expressed generally as:
[ ]
Similarly, the nth finite divided difference is:
These divided differences can be used to evaluate the coefficients of the
Newton interpolating polynomial.
6
2.3.1 Example
Estimate the natural logarithm of 2 using a third order interpolation Newton
polynomial .
x x0 = 1 x1 = 4 x2 = 6 x3=5
f(x)=ln(x) f(x0)=0 f(x1)=1.386294 f(x2)=1.791759 f(x3)=1.609438
The third-order interpolation polynomial with n=3, is:
( ) ( ) ( )( ) ( )( )( )
With:
f[x1,x0]=(1.38624-0)/(4-1)=0.4620981
f[x2,x1]=(1.791759-1.386294)/(6-4)=0.2027326
f[x3,x2]=(1.609438-1.791759)/(5-6)=0.1823216
f[x2,x1,x0]=(0.2027326-0.4620981)/(6-1)=-0.05187311
f[x3,x2,x1]=(0.1823216-0.2027326)/(5-4)=-0.02041100
f[x3,x2,x1,x0]=(-0.02041100-(-0.05187311))/(5-1)=0.007865529
So;
( ) ( ) ( )( )
( )( )( )
We obtain then;
f3(2)=0.6287686.
So the relative error for a third order interpolation polynomial is only 9.3%.
3 Lagrange Interpolating Polynomials
The Lagrange interpolating polynomial is simply a reformulation of the Newton
polynomial that avoids the computation of divided differences. It can be
represented concisely as:
7
( ) ∑ ( ) ( )
Where;
( )
( ) ∏
( )
Where Π designates the “product of.”
For example, the linear version (n=1) is:
( ) ( ) ( )
For n=2;
( )( ) ( )( )
( ) ( ) ( )
( )( ) ( )( )
( )( )
( )
( )( )
3.1 Example
Use a Lagrange interpolating polynomial of the first and second order to
evaluate ln 2 on the basis of the following data:
x x0 = 1 x1 = 4 x2 = 6 x=2
f(x)=ln(x) f(x0)=0 f(x1)=1.386294 f(x2)=1.791759 ?
a-For n=1:
( )
b-For n=2
( )( ) ( )( ) ( )( )
( ) 791760
( )( ) ( )( ) ( )( )
As expected, both these results agree with those previously obtained using
Newton’s interpolating polynomial