Newton’s Backward Interpolation
The working formula for Newton’s Backward Interpolation is
To Compute the value, we need to construct a backward difference table and thereafter, to implement Newton’s backward interpolation by generating the formula.
Algorithm:
Step 1: Start the program
Step 2: Read n (No. of arguments)
Step 3: For i = 0 to n − 1
Read x i &y i [0]
End i
Step 4: Construct the Backward Difference Table
For j = 1 to n − 1
For i = j to n − 1
y i [j] = y[i][j − 1] − y[i − 1][j − 1]
End i
End j
Step 5: Print the Backward Difference Table
For i = 0 to n − 1
For j = 0 to i
Print y i [j]
End j
End i
Step 6: Read a (Point of Interpolation)
Step 7: Assign h = x[1] − x[0] (Step Length)
Step 8: Assign u = (a − x[n − 1])/h
Step 9: Assign sum = y n − 1 [0] & p = 1.0
Step 10: For j = 1 to n − 1
p = p ∗ (u + j − 1)/j
sum = sum + p ∗ y n − 1 [j]
End j
Step 11: Display a & sum
Step 12: Stop
Example:
C
// C program to demonstrate // both Forward and Backward // Newton's Interpolation #include <stdio.h> void forward( float x[4], float y[4][4], int n); void BackWard( float x[4], float y[4][4], int n); int main() { int i, j; int n = 4; // number of arguments float x[4] = { 0, 1, 2, 3 }; float y[4][4] = { { 1, 0, 0, 0 }, { 0, 0, 0, 0 }, { 1, 0, 0, 0 }, { 10, 0, 0, 0 }, }; forward(x, y, n); BackWard(x, y, n); return 0; } void forward( float x[4], float y[4][4], int n) { int i, j; float a = 0.5; // interpolation point float h, u, sum, p; for (j = 1; j < n; j++) { for (i = 0; i < n - j; i++) { y[i][j] = y[i + 1][j - 1] - y[i][j - 1]; } } printf ( "\n The forward difference table is:\n" ); for (i = 0; i < n; i++) { printf ( "\n" ); for (j = 0; j < n - i; j++) { printf ( "%f\t" , y[i][j]); } } p = 1.0; sum = y[0][0]; h = x[1] - x[0]; u = (a - x[0]) / h; for (j = 1; j < n; j++) { p = p * (u - j + 1) / j; sum = sum + p * y[0][j]; } printf ( "\nThe value of y at x=%0.1f is %0.3f" , a, sum); } void BackWard( float x[4], float y[4][4], int n) { int i, j; float a = 0.5; // interpolation point float h, u, sum, p; for (j = 1; j < n; j++) { for (i = j; i < n; i++) { y[i][j] = y[i][j - 1] - y[i - 1][j - 1]; } } printf ( "\nThe backward difference table is:\n" ); for (i = 0; i < n; i++) { printf ( "\n" ); for (j = 0; j <= i; j++) { printf ( "%f\t" , y[i][j]); } } p = 1.0; sum = y[n - 1][0]; h = x[1] - x[0]; u = (a - x[n - 1]) / h; for (j = 1; j < n; j++) { p = p * (u + j - 1) / j; sum = sum + p * y[n - 1][j]; } printf ( "\nThe value of y at x=%0.1f is %0.3f" , a, sum); } |
Output
The forward difference table is: 1.000000 -1.000000 2.000000 6.000000 0.000000 1.000000 8.000000 1.000000 9.000000 10.000000 The value of y at x=0.5 is 0.625 The backward difference table is: 1.000000 0.000000 -1.000000 1.000000 1.000000 2.000000 10.000000 9.000000 8.000000 6.000000 The value of y at x=0.5 is 0.625
Time Complexity: O(N*N)
Space Complexity: O(N*N)
Program For Newton’s Forward Interpolation
Here we will construct a C program for Newton’s Forward interpolation formula to calculate y(0.5), Correct to 3 decimal places from the following table:
x | 0 | 1 | 2 | 3 |
---|---|---|---|---|
y | 1 | 0 | 1 | 10 |
Also, To compute the value, we need to construct forward difference table and thereafter, to implement Newton’s Forward Interpolation by generating the formula.