NEWTON DIVIDED DIFFERENCE FORMULA
In our previous lectures, we explored the applications of Lagrange
interpolation and examined various software, such as Autodesk Maya,
Gazebo, and ROS, that utilize this method for smooth transitions and
path planning. However, it's important to note that Newton's divided
differences can also serve as an effective interpolation technique in
similar contexts.
Rendering – Science behind PIXAR
In animated movie rendering, both Lagrange interpolation and
Newton's divided differences can be used to generate smooth
transitions and curves essential for realistic motion and surface
design. For instance, when animators need to create smooth
movements of characters or objects, interpolation is applied to
generate frames between key positions. Lagrange interpolation
helps create smooth motion paths by passing through these
keyframes exactly, ensuring fluid transitions. Similarly, Newton's
divided differences can be used to generate curves for lighting
effects, camera motion, or the shape of surfaces, allowing efficient
computation of smooth, continuous changes. These interpolation
methods help in rendering realistic animations, blending
movements and surfaces seamlessly without sharp, abrupt
transitions, thus improving the visual quality of the film.
Why NDD if Lagrange is there?
At first glance, Lagrange interpolation looks sufficient, but Newton’s Divided
Difference (NDD) is preferred in many scenarios:
1. Efficiency with Additional Points:
• Lagrange requires rebuilding the whole polynomial if a new data point is
added.
• NDD allows extending the table without recomputing everything.
2. Numerical Stability:
• It minimizes redundant calculations and reduces round-off errors.
3. Step-by-Step Construction:
• NDD builds the polynomial incrementally, which is computationally
cheaper.
• This is crucial in CS where large datasets are handled.
MATHEMATICAL REPRESENTATION
x f(x) First divided Second divided Third divided Fourth divided
differences differences differences difference
𝑥0 𝑓[𝑥0 ]
𝑓[𝑥0 , 𝑥1 ] = 𝐴
𝑓(𝑥1 ) − 𝑓(𝑥0 )
=
𝑥1 − 𝑥0
𝑥1 𝑓[𝑥1 ] 𝑓[𝑥0 , 𝑥1 , 𝑥2 ]
𝐵 −𝐴
= =𝐸
𝑥2 − 𝑥0
𝑓[𝑥1 , 𝑥2 ] = 𝐵 𝑓[𝑥0 , 𝑥1 , 𝑥2 , 𝑥3 ]
𝑓(𝑥2 ) − 𝑓(𝑥1 ) 𝐹−𝐸
= = =𝐻
𝑥2 − 𝑥1 𝑥3 − 𝑥0
𝑥2 𝑓[𝑥2 ] 𝑓[𝑥1 , 𝑥2 , 𝑥3 ] 𝑓[𝑥0 , 𝑥1 , … , 𝑥4 ]
𝐶 −𝐵 𝐼 −𝐻
= =𝐹 = =𝐽
𝑥3 − 𝑥1 𝑥4 − 𝑥0
𝑓[𝑥2 , 𝑥3 ] = 𝐶 𝑓[𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 ]
𝑓(𝑥3 ) − 𝑓(𝑥2 ) 𝐺−𝐹
= = =𝐼
𝑥3 − 𝑥2 𝑥4 − 𝑥1
𝑥3 𝑓[𝑥3 ] 𝑓[𝑥2 , 𝑥3 , 𝑥4 ]
𝐷 −𝐶
= =𝐺
𝑥4 − 𝑥2
𝑓[𝑥3 , 𝑥4 ] = 𝐷
𝑓(𝑥4 ) − 𝑓(𝑥3 )
=
𝑥4 − 𝑥3
𝑥4 𝑓[𝑥4 ]
Newton interpolating polynomials
𝑃1 (𝑥) = 𝑓(𝑥0 ) + (𝑥 − 𝑥0 )𝐴,
𝑃2 (𝑥) = 𝑓(𝑥0 ) + (𝑥 − 𝑥0 )𝐴 + (𝑥 − 𝑥0 )(𝑥 − 𝑥1 )𝐸
And 𝑃3 (𝑥) = 𝑓(𝑥0 ) + (𝑥 − 𝑥0 )𝐴 + (𝑥 − 𝑥0 )(𝑥 − 𝑥1 )𝐸 +(𝑥 − 𝑥0 )(𝑥 − 𝑥1 )(𝑥 − 𝑥2 )𝐻
Next, Newton interpolating polynomial of degree four is?
𝑃4 (𝑥) = 𝑓 (𝑥0 ) + (𝑥 − 𝑥0 )𝐴 + (𝑥 − 𝑥0 )(𝑥 − 𝑥1 )𝐸 +(𝑥 − 𝑥0 )(𝑥 − 𝑥1 )(𝑥 − 𝑥2 )𝐻
+(𝑥 − 𝑥0 )(𝑥 − 𝑥1 )(𝑥 − 𝑥2 )(𝑥 − 𝑥3 )𝐽
GRAPHICAL REPRESENTATION
EXAMPLES
Example
For the given functions 𝑓(𝑥) = √1 + 𝑥 and 𝑥0 = 0, 𝑥1 = 0.6 and 𝑥2 = 0.9. Construct
interpolation polynomials of degree one and two to approximate 𝑓(0.45), and find the
absolute error.
x f(x) First divided differences
𝑥0 = 0 𝑓[𝑥0 ] = 1
√1.6 − 1
𝑓[𝑥0 , 𝑥1 ] = = 0.44152
0.6 − 0
𝑥1 = 0.6 𝑓[𝑥1 ] =√1.6
𝑃1 (𝑥) = 𝑓(𝑥0 ) + (𝑥 − 𝑥0 )𝑓[𝑥0 , 𝑥1 ] = 1 + 0.44152 𝑥
𝑃1 (0.45) = 1.198684
x f(x) First divided differences Second divided differences
𝑥0 = 0 𝑓[𝑥0 ] = 1
√1.6 − 1
𝑓[𝑥0 , 𝑥1 ] = = 0.44152
0.6 − 0
𝑥1 = 0.6 𝑓[𝑥1 ] =√1.6 𝑓[𝑥0 , 𝑥1 , 𝑥2 ] =
𝑓[𝑥1 , 𝑥2 ] − 𝑓[𝑥0 , 𝑥1 ]
= −0.07023
𝑥2 − 𝑥0
√1.9 − √1.6
𝑓[𝑥1 , 𝑥2 ] = = 0.37831
0.9 − 0.6
𝑥2 = 0.9 𝑓[𝑥2 ] =√1.9
𝑃2 (𝑥) = 𝑓(𝑥0 ) + (𝑥 − 𝑥0 )𝑓[𝑥0 , 𝑥1 ] + (𝑥 − 𝑥0 )(𝑥 − 𝑥1 )𝑓[𝑥0 , 𝑥1 , 𝑥2 ]
= 1 + 0.44152 𝑥 − 0.07023𝑥(𝑥 − 0.6)
𝑃2 (0.45) = 1.203425
We can also use Newton backward divided difference formula as
𝑃2 (𝑥) = 𝑓(𝑥2 ) + (𝑥 − 𝑥2 )𝑓[𝑥1 , 𝑥2 ] + (𝑥 − 𝑥2 )(𝑥 − 𝑥1 )𝑓[𝑥0 , 𝑥1 , 𝑥2 ]
= √1.9 + 0.37831 (𝑥 − 0.9) − 0.07023(𝑥 − 0.9)(𝑥 − 0.6)
𝑃2 (0.45) = 1.203425
Example
Use Newton divided difference interpolating polynomials of degrees 1, 2, and 3 to
approximate f(8.4), if f (8.1) =16.94410, f (8.3) =17.56492, f (8.6) =18.50515,
f(8.7) =18.82091.
Solution: First, let us make divided difference table:
x f(x) First divided Second divided differences Third divided differences
differences
𝑥0 = 8.1 𝑓[𝑥0 ] = 16.94410
𝑓[𝑥0 , 𝑥1 ] = 3.1041
𝑥1 = 8.3 𝑓[𝑥1 ] =17.56492 𝑓[𝑥1 , 𝑥2 ] − 𝑓[𝑥0 , 𝑥1 ]
𝑥2 − 𝑥0
= 0.06
𝑓[𝑥1 , 𝑥2 ] = 3.1341 𝑓[𝑥1 , 𝑥2 , 𝑥3 ] − 𝑓[𝑥0 , 𝑥1 , 𝑥2 ]
𝑥3 − 𝑥0
= −0.002083
𝑥2 = 8.6 𝑓[𝑥2 ] =18.50515 𝑓[𝑥2 , 𝑥3 ] − 𝑓[𝑥1 , 𝑥2 ]
𝑥3 − 𝑥1
= 0.05875
𝑓[𝑥2 , 𝑥3 ] = 3.1576
𝑥3 = 8.7 𝑓[𝑥3 ] =18.82091
𝑃1 (𝑥) = 𝑓(𝑥0 ) + (𝑥 − 𝑥0 )𝑓[𝑥0 , 𝑥1 ] = 16.94410 + 3.1041 (𝑥 − 8.1)
𝑃1 (8.4) = 17.87533
𝑃2 (𝑥) = 𝑓(𝑥0 ) + (𝑥 − 𝑥0 )𝑓[𝑥0 , 𝑥1 ] + (𝑥 − 𝑥0 )(𝑥 − 𝑥1 )𝑓[𝑥0 , 𝑥1 , 𝑥2 ]
= 16.94410 + 3.1041 (𝑥 − 8.1) + 0.06(𝑥 − 8.1)(𝑥 − 8.3)
𝑃2 (8.4) = 17.87713
𝑃3 (𝑥) = 𝑓(𝑥0 ) + (𝑥 − 𝑥0 )𝑓[𝑥0 , 𝑥1 ] + (𝑥 − 𝑥0 )(𝑥 − 𝑥1 )𝑓[𝑥0 , 𝑥1 , 𝑥2 ]
+(𝑥 − 𝑥0 )(𝑥 − 𝑥1 )(𝑥 − 𝑥2 )𝑓[𝑥0 , 𝑥1 , 𝑥2 , 𝑥3 ]
= 16.94410 + 3.1041 (𝑥 − 8.1) + 0.06(𝑥 − 8.1)(𝑥 − 8.3) − 0.002083(𝑥 − 8.1)(𝑥
− 8.3)(𝑥 − 8.6)
𝑃3 (8.4) = 17.87714
ADVANTAGE/DISADVANTAGE
Advantages
• Efficient incremental updates (add a point → compute new divided
differences).
• Numerically stable when evaluated with nested form.
• Equivalent to Lagrange but better computational workflow.
Disadvantages
• If nodes are badly spaced or high degree is used, polynomial oscillation can
appear.
• For large datasets, use splines instead of high-degree polynomials.
SHORT QUESTIONS
Question 1.
Two different sets of points are given:
• Equally spaced: 𝑥 = 0, 1, 2, 3.
• Unequally spaced: 𝑥 = 0, 0.5, 2, 5.
a. For both, construct the 2nd degree NDD polynomial.
b. Which gives more accurate approximation of 𝑓(𝑥) = 𝑒 𝑥 at 𝑥 = 1.2? (Compute
actual error.)
Question 2.
Four points from a function 𝑓(𝑥) are given as follows:
(0,4), (1,9), (2,15), (3,18)
a. Construct the Newton Divided Difference (NDD) table and the 3rd degree
interpolating polynomial.
b. Using the same NDD table, evaluate the interpolating polynomial at 𝑥 = 2.5.
c. Suppose one more point (4,23) is added to end of the dataset. Update the NDD
table without recomputing everything. Write the new polynomial.
Question 3.
Consider the following dataset:
𝑥 0 1 2
𝑓(𝑥) 2 -1 4
2
Determine the coefficient of 𝑥 in 𝑃2 (𝑥) obtained via NDD.
PRACTICE
Problem 1
A software engineer is developing an application to approximate sensor readings
based on given data points. The sensor collects values of a function 𝑓(𝑥) at several
positions: at 𝑥 = 0.6 , 𝑓(𝑥) = −0.17694460 ; at 𝑥 = 0.7 , 𝑓(𝑥) = 0.01375227;
at 𝑥 = 0.8, 𝑓(𝑥) = 0.22363362 ; and at 𝑥 = 1.0 , 𝑓(𝑥) = 0.65809197 .
To predict the sensor value at 𝑥 = 0.9, the engineer decides to use Newton's divided
difference interpolation.
a. Use Newton's divided difference interpolating polynomials of degrees 1, 2, and 3
to approximate 𝑓(0.9).
b. Calculate the actual value of 𝑓(0.9) using the function 𝑓(𝑥) = 𝑠𝑖𝑛(𝑒 𝑥 − 2).
c. Compare the values obtained from the interpolating polynomials with the actual
value.
Problem 2
For a function 𝑓, the forward divided differences are given by
Determine the missing entries.
PROBLEM STATEMENT
In robotics, effective path planning is essential for guiding a robot's movement
through various points in its environment. For instance, in autonomous navigation
systems, a robot may need to travel through several target positions, such as specific
locations in a warehouse or along a route in a complex space. To ensure smooth and
precise movement, it is crucial to create a continuous trajectory that minimizes abrupt
changes in direction, which can be important for maintaining speed, conserving
energy, and performing delicate operations efficiently.
Consider designing a path-planning algorithm for a robot that must follow four target
coordinates:
Target 1: (2, 4)
Target 2: (5, 1)
Target 3: (6, 4)
Target 4: (7, 10)
Using Lagrange interpolation, determine the cubic polynomial (degree 3) that
interpolates through these points. Also, solve the same interpolation problem using
Newton's divided difference formula and compare the results of both methods. Pay
particular attention to their accuracy and error analysis to assess which method
provides a more reliable trajectory for the robot.
PYTHON CODE AND RESULTS