## 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  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]
for i = 0 to n - 1 repeat
[End of ‘for’ loop]
for i = 0 to n - 1 repeat
[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

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

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