Chapter 05.03 Newton’s Divided Difference Interpolation
[Pages:12]Chapter 05.03 Newton's Divided Difference Interpolation
After reading this chapter, you should be able to: 1. derive Newton's divided difference method of interpolation, 2. apply Newton's divided difference method of interpolation, and 3. apply Newton's divided difference method interpolants to find derivatives and integrals.
What is interpolation?
Many times, data is given only at discrete points such as x0, y0 , x1, y1, ......, xn1, yn1 , xn, yn . So, how then does one find the value of y at any other value of x ? Well, a continuous function f x may be used to represent the n 1 data values with f x passing
through the n 1 points (Figure 1). Then one can find the value of y at any other value of x . This is called interpolation.
Of course, if x falls outside the range of x for which the data is given, it is no longer interpolation but instead is called extrapolation.
So what kind of function f x should one choose? A polynomial is a common
choice for an interpolating function because polynomials are easy to (A) evaluate, (B) differentiate, and (C) integrate,
relative to other choices such as a trigonometric and exponential series. Polynomial interpolation involves finding a polynomial of order n that passes
through the n 1 points. One of the methods of interpolation is called Newton's divided difference polynomial method. Other methods include the direct method and the Lagrangian interpolation method. We will discuss Newton's divided difference polynomial method in this chapter.
Newton's Divided Difference Polynomial Method To illustrate this method, linear and quadratic interpolation is presented first. Then, the general form of Newton's divided difference polynomial method is presented. To illustrate the general form, cubic interpolation is shown in Figure 1.
05.02.1
05.03.2
Chapter 05.03
y
x1, y1
x3, y3
x2, y2
f x
x0, y0
x Figure 1 Interpolation of discrete data.
Linear Interpolation
Given (x0, y0 ) and (x1, y1 ), fit a linear interpolant through the data. Noting y f (x) and
y1 f (x1 ) , assume the linear interpolant f1 (x) is given by (Figure 2)
f1 (x) b0 b1 (x x0 )
Since at x x0 ,
f1 (x0 ) f (x0 ) b0 b1 (x0 x0 ) b0
and at x x1 ,
f1 (x1 ) f (x1 ) b0 b1 (x1 x0 )
f (x0 ) b1 (x1 x0 )
giving
b1
f (x1 ) f (x0 ) x1 x0
So
b0 f (x0 )
b1
f (x1 ) f (x0 ) x1 x0
giving the linear interpolant as
f1 (x) b0 b1 (x x0 )
f1(x)
f (x0 )
f
(
x1 ) x1
f (x0 x0
)
(x
x0
)
Newton's Divided Difference Interpolation y
x1, y1
05.03.3
f1x
x0, y0
x
Figure 2 Linear interpolation.
Example 1 The upward velocity of a rocket is given as a function of time in Table 1 (Figure 3).
Table 1 Velocity as a function of time. t (s) v(t) (m/s)
0
0
10 227.04
15 362.78
20 517.35
22.5 602.97
30 901.67
Determine the value of the velocity at t 16 seconds using first order polynomial interpolation by Newton's divided difference polynomial method. Solution
For linear interpolation, the velocity is given by v(t) b0 b1(t t0 )
Since we want to find the velocity at t 16 , and we are using a first order polynomial, we need to choose the two data points that are closest to t 16 that also bracket t 16 to evaluate it. The two points are t 15 and t 20 . Then
t0 15, v(t0 ) 362.78
t1 20, v(t1 ) 517.35 gives
b0 v(t0 )
05.03.4
362.78
b1
v(t1 ) v(t0 ) t1 t0
517.35 362.78 20 15
30.914
Chapter 05.03
Figure 3 Graph of velocity vs. time data for the rocket example.
Hence
v(t) b0 b1 (t t0 ) 362.78 30.914(t 15),
15 t 20
At t 16,
v(16) 362.78 30.914(16 15)
393.69 m/s
If we expand
v(t) 362.78 30.914(t 15),
15 t 20
we get
v(t) 100.93 30.914t,
15 t 20
and this is the same expression as obtained in the direct method.
Quadratic Interpolation Given (x0 , y0 ), (x1, y1 ), and (x2 , y2 ), fit a quadratic interpolant through the data. Noting
y f (x), y0 f (x0 ), y1 f (x1 ), and y2 f (x2 ), assume the quadratic interpolant f2 (x) is given by
f 2 (x) b0 b1 (x x0 ) b2 (x x0 )(x x1 )
Newton's Divided Difference Interpolation
05.03.5
At x x0 ,
f2 (x0 ) f (x0 ) b0 b1(x0 x0 ) b2 (x0 x0 )(x0 x1)
b0
b0 f (x0 )
At x x1
f2 (x1) f (x1) b0 b1(x1 x0 ) b2 (x1 x0 )(x1 x1)
f (x1 ) f (x0 ) b1 (x1 x0 )
giving
b1
f (x1 ) f (x0 ) x1 x0
At x x2
f2 (x2 ) f (x2 ) b0 b1(x2 x0 ) b2 (x2 x0 )(x2 x1)
f (x2 )
f (x0 )
f
(x1 ) x1
f (x0 x0
)
(
x2
x0 ) b2 (x2
x0 )(x2
x1 )
Giving
b2
f
(x2 ) x2
f (x1 x1
)
f (x1 ) f (x0 ) x1 x0
x2 x0
Hence the quadratic interpolant is given by
f 2 (x) b0 b1 (x x0 ) b2 (x x0 )(x x1 )
f (x0 )
f
( x1 ) x1
f (x0 x0
)
(
x
x0
)
f
(
x2 ) x2
f( x1
x1) x2
f( x0
x1) x1
f( x0
x0
)
(x
x0
)(
x
x1)
y
x1, y1
x2, y2
f2 x
x0 , y0
x Figure 4 Quadratic interpolation.
05.03.6
Chapter 05.03
Example 2 The upward velocity of a rocket is given as a function of time in Table 2.
Table 2 Velocity as a function of time.
t (s) v(t) (m/s)
0
0
10 227.04
15 362.78
20 517.35
22.5 602.97
30 901.67
Determine the value of the velocity at t 16 seconds using second order polynomial interpolation using Newton's divided difference polynomial method. Solution
For quadratic interpolation, the velocity is given by
v(t) b0 b1 (t t0 ) b2 (t t0 )(t t1 )
Since we want to find the velocity at t 16, and we are using a second order polynomial, we
need to choose the three data points that are closest to t 16 that also bracket t 16 to
evaluate it. The three points are t0 10, t1 15, and t2 20 . Then
t0 10, v(t0 ) 227.04
gives
t1 15, v(t1 ) 362.78 t2 20, v(t2 ) 517.35
b0 v(t0 ) 227.04
b1
v(t1 ) t1
v(t0 ) t0
362.78 15
227.04 10
27.148
b2
v(t2 ) v(t1 ) t2 t1 t2
v(t1 ) t1
v(t0 t0
)
t0
517.35 20
362.78 15
362.78 15
227.04 10
20 10
30.914 27.148 10
Newton's Divided Difference Interpolation
05.03.7
0.37660
Hence
v(t) b0 b1 (t t0 ) b2 (t t0 )(t t1 ) 227.04 27.148(t 10) 0.37660(t 10)(t 15),
10 t 20
At t 16,
v(16) 227.04 27.148(16 10) 0.37660(16 10)(16 15)
392.19 m/s If we expand
v(t) 227.04 27.148(t 10) 0.37660(t 10)(t 15), 10 t 20
we get
v(t) 12.05 17.733t 0.37660t 2 , 10 t 20
This is the same expression obtained by the direct method.
General Form of Newton's Divided Difference Polynomial
In the two previous cases, we found linear and quadratic interpolants for Newton's divided
difference method. Let us revisit the quadratic polynomial interpolant formula
f 2 (x) b0 b1 (x x0 ) b2 (x x0 )(x x1 )
where
b0 f (x0 )
b1
f (x1 ) f (x0 ) x1 x0
b2
f (x2 ) f (x1 ) x2 x1
f (x1 ) f (x0 ) x1 x0
x2 x0
Note that b0 , b1, and b2 are finite divided differences. b0 , b1, and b2 are the first, second,
and third finite divided differences, respectively. We denote the first divided difference by
f [x0 ] f (x0 )
the second divided difference by
f [x1, x0 ]
f (x1 ) f (x0 ) x1 x0
and the third divided difference by
f [x2 , x1, x0 ]
f [x2 , x1 ] f [x1, x0 ] x2 x0
f
(x2 ) x2
f (x1 x1
)
f (x1 ) f (x0 ) x1 x0
x2 x0
where f [x0 ], f [x1, x0 ], and f [x2 , x1, x0 ] are called bracketed functions of their variables
enclosed in square brackets.
Rewriting,
f 2 (x) f [x0 ] f [x1, x0 ](x x0 ) f [x2 , x1, x0 ](x x0 )(x x1 )
05.03.8
Chapter 05.03
This leads us to writing the general form of the Newton's divided difference polynomial for
n 1 data points, x0 , y0 , x1, y1 ,......, xn1, yn1 , xn , yn , as
f n (x) b0 b1 (x x0 ) .... bn (x x0 )(x x1 )...(x xn1 ) where
b0 f [x0 ]
b1 f [x1, x0 ]
b2 f [x2 , x1, x0 ]
bn1 f [xn1, xn2 ,...., x0 ]
bn f [xn , xn1,...., x0 ]
where the definition of the mth divided difference is
bm f [xm ,........, x0 ]
f [xm,........, x1] f [xm1,........, x0] xm x0
From the above definition, it can be seen that the divided differences are calculated
recursively.
For an example of a third order polynomial, given (x0 , y0 ), (x1, y1 ), (x2 , y2 ), and (x3 , y3 ),
f3 (x) f [x0 ] f [x1, x0 ](x x0 ) f [x2 , x1, x0 ](x x0 )(x x1 )
f [x3 , x2 , x1, x0 ](x x0 )(x x1 )(x x2 )
x0 f x0
x1 f x1
x 2
f x2
x3 f x3
b 0
f x1, x0 f x2 , x1 f x3, x2
b1
f x2 , x1, x0 f x3, x2 , x1
b2 b3
f x3, x2, x1, x0
Figure 5 Table of divided differences for a cubic polynomial.
Example 3 The upward velocity of a rocket is given as a function of time in Table 3.
................
................
In order to avoid copyright disputes, this page is only a partial summary.
To fulfill the demand for quickly locating and searching documents.
It is intelligent file search solution for home and business.
Related download
- chapter 05 03 newton s divided difference interpolation
- translating words into algebra leeward community college
- translating words into algebraic expressions
- center frequencies and high low frequency limits for
- eas iesacy chart rea property ony
- 1 3 division of polynomials remainder and factor theorems
- solutions to assignment 1
- divisibility
- unit 6 lesson 1 tape diagrams and equations
- dividing a fraction by a whole number texas instruments
Related searches
- newton s laws of motion pdf
- newton s laws examples
- newton s laws of motion printables
- newton s second law of motion example
- newton s second law of motion state
- newton s law of motion examples
- newton s first law illustration
- newton s first law of motion formula
- newton s equations of motion
- newton s laws of motion examples
- newton s laws of motion formulas
- newton s first law formula