FOR FREE YEAR SOLVED

Newton's Backword Method

Back to Programming

Description

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 $x_{0}, x_{1}, . . ., x_{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.

Algorithm

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

Code

ADVANTAGES

1. The data sets can fit exactly for higher-order polynomials.

2. These are simpler to evaluate than the approximations of non-polynomials.

DISADVANTAGES

1. Sometimes they tend to overfit the data.

2. It is only applicable for the equidistant values of a function.

APPLICATIONS

1. This method is used to interpolate the values of y which is near the end of the difference table.

Contributed by

Debashis Roy Faculty of Computer Science Department, JCC College, University of Calcutta

Please Login to Bookmark