FOR FREE CONTENT

Interpolation is a technique by which the value of a function is estimated for any intermediate value of the independent variable. 

The differences ${\mathrm{y}}_1 - {\mathrm{y}}_0, {\mathrm{y}}_2 - {\mathrm{y}}_1, {\mathrm{y}}_3 - {\mathrm{y}}_2, ..., {\mathrm{y}}_{\mathrm{n}} - {\mathrm{y}}_{\mathrm{n}-1}$ are denoted by ${\mathrm{dy}}_0, {\mathrm{dy}}_1, ... , {\mathrm{dy}}_{\mathrm{n}-1}$ respectively. 

These are called first forward differences.

DERIVATION

Let y = f(x) denote a function which takes the values ${\mathrm{y}}_0, {\mathrm{y}}_1, {\mathrm{y}}_2, ..., {\mathrm{y}}_{\mathrm{n}}$ for the equidistant values ${\mathrm{x}}_0, {\mathrm{x}}_1, {\mathrm{x}}_2, ..., {\mathrm{x}}_{\mathrm{n}}$ 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.

INPUT: 

The value of x and f(x)

OUTPUT: 

The value of f(x) for a given x

PROCESS:

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][0]
	[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[0][0] 
	Set u ← (v - x[0]) / (x[1] - x[0]) 
	for i = 1 to n - 1 repeat
		Set sum ← sum + (calculate(u, i) * y[0][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’]