Newton Divide Difference

Back to Programming


It is an interpolation technique which is used if the interval difference is not same for all sequence of values. These differences are symmetric with respect to the arguments which is independent of the order of arguments.



Let y = f(x) is known for (n + 1) distinct arguments xj (j = 0,1,..., n), it may not be equispaced, and yj = f(xj) (j = 0,1,..., n) be the corresponding entries. 


Now we have to construct a polynomial φ(x) of degree less than or equal to n, such that φ(x) replaces f(x) on the set of arguments xj i.e. 


Where Rn+1(x) is the remainder or error in interpolating f(x) for a given x, 

Let us choose φ(x) as a polynomial of degree ≤ n as


Similarly, we get 

And we get 






The value of x and f(x)



An interpolating point for a given value of x.



Step 1: [taking inputs from the user]

	Read n [the number of values]
		for i = 0 to n - 1 repeat
			Read x1[i], y[i]
		[End of ‘for’ loop]
	Read x [the value for which f(x) is to be calculated]

Step 2: [Newton’s divide difference interpolation]
	Step 2.1: Set s ← y[0]
		Step 2.2: for i = 0 to n - 2 repeat
					Set d[i] ← ((y[i+1]-y[i])/(x1[i+j] - x1[i]))
					Set y[i] ← d[i]
				[End of ‘for’ loop]
				Set c1 ← 1
				for i = 0 to j - 1 repeat
					Set  c1 ← c1 × (x - x1[i])
			[End of ‘for’ loop]
				Set  c2 ← c2 + (y[0] × c1)
				Set  n ← n - 1
				Set  j ← j + 1
				While n != 1 repeat step 2.2
		Step 2.3: Set s ← s + c2
		Step 2.4: print s

Step 3: Stop



1. This can be used for any interval.


2. The value of the function can be found at any point in the interval.


3. For different points also the same table can be used.


4. For new data, we can use this method by slightly changing the divide difference table. 


5. The value of y can be found regardless of the nature of x and of units in which x is expressed.



1. It is less efficient than Lagrange’s interpolation when several data sets are interpolated on the same data points.



1. It is used when the points are not equispaced.


2. When the new data points are added to create a new interpolation polynomial, it can be done without recalculating the old co-efficient.