Newton interpolation

Newton uses a polynomial for the interpolation of y_p that can be calculated in a recursive procedure. The basic formulation of this polynomial is:

The coefficients b₀ to b_n he calculates like:

In this form the calculation is not too obvious. But if we put the |X_kX_k-1|… terms into a table (here for n = 4), things become clearer.

We first have to calculate |X_kX_k-1| terms. From this the |X_kX_k-1X_k-2|…terms and so on. Even though we only need the value on the very top of each column for b0 to b4, we have to calculate all the elements. But in a recursive function it becomes quite simple :-)

void CalcElements(double[] x, int order, int step)
{
     int i;
     double[] xx;
     if (order >= 1)
     {
         xx = new double[order];
         for (i = 0; i < order-1; i++)
         {
              xx[i] = (x[i + 1] - x[i]) / (x_k[i + step] - x_k[i]);
         }
         b[step - 1] = x[0];
         CalcElements(xx, order - 1, step + 1);
}

}

This function is called with the array containing the supporting points, the number of supporting points as the order and it starts with the first step.

Now one y_p interpolation value can be calculated like:

for (i = 1; i < order; i++)
{
       tempYp = b[i];
       for (k = 0; k < i; k++)
       {
            tempYp = tempYp * (xp - x_k[k]);
       }
       yp = yp + tempYp;
}

It’s not too clearly visible but the Newton interpolation exactly meets each supporting point. We can check that up to 3 supporting points. For more points it becomes too complicate and we leave that. But let’s start at just 2 supporting points x₀, y₀ and x₁, y₁.

There we have

And that means

Now it’s quite good visible that y_p = y₀ if x_p = x₀ and y_p = y₁ if x_p = x₁.

If we now have a look at 3 supporting points, things become a bit more complicate:

The therm

becomes 0 for x_p = x₀ or x_p = x₁. For this two cases it’s the same as above.

Now if x_p = x₃ we get

that’s

And that can be reduced to y_p = y₂

For other approaches see Polynomial interpolation, Lagrange interpolation, Newton Gregory interpolation, Interpolation by Chebychev polynomials

C# Demo Project Newton interpolation

Newton.zip

Java Demo Project Newton interpolation

NewtonInterpoly.zip