Interpolation is a technique by which the value of a function is estimated for any intermediate value of the independent variable.
The differences are denoted by respectively.
These are called first forward differences.
Let y = f(x) denote a function which takes the values for the equidistant values respectively of the independent variable x, and let φ(x) denote a polynomial of the nth degree written as:
Where h is the interval length between these equidistant points.
Continuing this way we can get,
This formula is known as Newton’s forward interpolation formula.
The value of x and f(x)
The value of f(x) for a given x
Step 1: [Taking the inputs from the user] Read n [the number of elements] 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 of interpolation] Step 2: [Newton’s forward interpolation] for i = 1 to n - 1 repeat for j = 0 to n – i - 1 repeat Set y[j][i] ← y[j + 1][i - 1] - y[j][i - 1] [End of ‘for’ loop] [End of ‘for’ loop] for i = 0 to n - 1 repeat Print x[i] for j = 0 to n – i - 1 repeat Printf y[i][j] [End of ‘for’ loop] Move to the next line [End of ‘for’ loop] Set sum ← y Set u ← (v - x) / (x - x) for i = 1 to n - 1 repeat Set sum ← sum + (calculate(u, i) * y[i]) / factorial(i) [here calculate and factorial are two functions described in step 3 and 4 respectively] [End of ‘for’ loop] Print sum [End of ‘newton’s forward interpolation’] 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’]
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. It is used for estimating the value of a function for any intermediate data points.