FOR FREE MATERIALS

In the case of Newton’s forward interpolation, the value of y at the beginning of the table can be determined, but the value at the end of the table cannot be determined by this method. 

So, when y = f(x) has equidistant values are given at nodes ${\mathbf{x}}_{\mathbf{0}}\mathbf{,}\mathbf{ }{\mathbf{x}}_{\mathbf{1}}\mathbf{,}\mathbf{ }\mathbf{.}\mathbf{.}\mathbf{.}\mathbf{,}\mathbf{ }{\mathbf{x}}_{\mathbf{n}}$ and the value of y is to be computed at the end of the table, then newton’s backward difference interpolation formula is used.

DERIVATION

Let Ø(x) be a polynomial of the nth degree in x as

And

Therefore,

Proceeding this way we get,

Hence, 

This formula is known as Newton’s backward interpolation formula.

INPUT: 

The values of x and f(x)

OUTPUT: 

The value after calculating f(x) for a given x.

PROCESS:

Step 1: [taking the value from the user]
Read n [number of values]
	for i = 0 to n - 1 repeat
		Read x[i]
	[End of ‘for’ loop]
	for i = 0 to n - 1 repeat
		Read y[i][0])
	[End of ‘for’ loop]
	Read v [the value for which the interpolation is to be calculated]

Step 2: [Newton’s Backward Interpolation]
for i = 1 to n - 1 repeat
		for j = n - 1 to i repeat 
			Set y[j][i] ← y[j][i - 1] - y[j - 1][i - 1];
[End of ‘for’ loop]
	[End of ‘for’ loop]
	
for i = 0 to n - 1 repeat
		for j = 0 to i repeat 
			Print y[i][j]	
[End of ‘for’ loop]
		Move to the next line
	[End of ‘for’ loop]
	Set sum ← y[n - 1][0] 
	Set u ← (v - x[n - 1]) / (x[1] - x[0])
	for i = 1 to n - 1 repeat 
		Set sum ← sum + (calculate(u, i) * y[n - 1][i]) / factorial(i) 
[‘calculate’ and ‘factorial’ are two functions defined below in step 3 and 4 respectively]
	[End of ‘for’ loop]
	Print sum

Step 3: [function ‘calculate’]
Set tmp ← u 
	for i = 1 to n - 1 repeat 
		Set tmp ← tmp × (u + i) 
[End of ‘for’ loop]
	return tmp
[End of function ‘calculate’]

Step 4: [Function ‘factorial’]
Set fact ← 1 
	for i = 2 to n repeat 
		Set fact ← fact × i
[End of ‘for’ loop]
	return fact
[End of function ‘factorial’]

Step 5: Stop