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.
Let Ø(x) be a polynomial of the nth degree in x as
Proceeding this way we get,
This formula is known as Newton’s backward interpolation formula.
The values of x and f(x)
The value after calculating f(x) for a given x.
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]) [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] Set u ← (v - x[n - 1]) / (x - x) 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
1. The data sets can fit exactly for higher-order polynomials.
2. These are simpler to evaluate than the approximations of non-polynomials.
1. Sometimes they tend to overfit the data.
2. It is only applicable for the equidistant values of a function.
1. This method is used to interpolate the values of y which is near the end of the difference table.