# CREATE OWN LIBRARY

## Newton Divide Difference

Back to Programming

### Description

It is an interpolation technique which is used if the interval difference is not same for all sequence of values. These differences are symmetric with respect to the arguments which is independent of the order of arguments.

DERIVATION

Let y = f(x) is known for (n + 1) distinct arguments ${\mathrm{x}}_{\mathrm{j}}$ (j = 0,1,..., n), it may not be equispaced, and ${\mathrm{y}}_{\mathrm{j}}$ = f(${\mathrm{x}}_{\mathrm{j}}$) (j = 0,1,..., n) be the corresponding entries.

Now we have to construct a polynomial φ(x) of degree less than or equal to n, such that φ(x) replaces f(x) on the set of arguments ${\mathrm{x}}_{\mathrm{j}}$ i.e.

Where ${\mathrm{R}}_{\mathrm{n}+1}\left(\mathrm{x}\right)$ is the remainder or error in interpolating f(x) for a given x,

Let us choose φ(x) as a polynomial of degree ≤ n as

Similarly, we get

And we get

And

GRAPHICAL REPRESENTATION

### Algorithm

INPUT:

The value of x and f(x)

OUTPUT:

An interpolating point for a given value of x.

PROCESS:

``````Step 1: [taking inputs from the user]

Read n [the number of values]
for i = 0 to n - 1 repeat
[End of ‘for’ loop]
Read x [the value for which f(x) is to be calculated]

Step 2: [Newton’s divide difference interpolation]
Step 2.1: Set s ← y
Step 2.2: for i = 0 to n - 2 repeat
Set d[i] ← ((y[i+1]-y[i])/(x1[i+j] - x1[i]))
Set y[i] ← d[i]
[End of ‘for’ loop]
Set c1 ← 1
for i = 0 to j - 1 repeat
Set  c1 ← c1 × (x - x1[i])
[End of ‘for’ loop]
Set  c2 ← c2 + (y × c1)
Set  n ← n - 1
Set  j ← j + 1
While n != 1 repeat step 2.2
Step 2.3: Set s ← s + c2
Step 2.4: print s

Step 3: Stop``````

### Code

1. This can be used for any interval.

2. The value of the function can be found at any point in the interval.

3. For different points also the same table can be used.

4. For new data, we can use this method by slightly changing the divide difference table.

5. The value of y can be found regardless of the nature of x and of units in which x is expressed.