Lagrange interpolation

For one interpolation point (x_p, y_p) Lagrange builds one enumerator polynomial and one denominator polynomial per supporting point including the xp value for the interpolation and the x values of the n supporting points. The enumerator divided by the denominator gives a factor Lk. For n supporting points that makes n polynomials L₁..L_n.

Please note: In the denominator the term (x_i – x_k) is allways missing where i = k and in the enumerator (x_p – x_k) is missing for the same k. That’s an essential detail :-)

Where k runs from 1 to n and x_p is the interpolation variable to which the value y_p shall be calculated later on.

The interpolation value y_p becomes now the sum of all the L_k* y_k terms whereas y_k is the y value of one supporting point.

Now, if xp becomes x₀, x₁, x₂, x₃… one of the (x_i - x_k) becomes 0 in most of the Lk’s. Except where x_p = x_k. There L_k becomes 1 and therefore y_p becomes y_k in this case. That means the interpolation function exactly meets each supporting point.

The interpolation for one interpolation point is made in one loop including the calculation of all the L_k elements and adding the multiplication of L_k * y_k together:

for (i = 0; i < order; i++)
{
                enumerator = 1.0;
                denominator = 1.0;
                /* calculate the Lk elements */
                for (k = 0; k < order; k++)
                {

if (k != i)
{

                        /* enumerator and denominator for one L element */
                        enumerator = enumerator * (xp - x_k[k]);
                        denominator = denominator * (x_k[i] - x_k[k]);

}

                }
                /* put every thing thogether to yp*/
               if (denominator != 0.0)
                    yp = yp + y_k[i] * enumerator / denominator;
                else
                   yp = 0.0;
}

This loop calculates one yp interpolation value.

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

C# Demo Project Lagrange interpolation

Lagrange.zip

Java Demo Project Lagrange interpolation

LagrangePoly.zip