Numerical Methods

  2. Home
  4. Docs
  6. Numerical Methods
  8. Interpolation and Regression
  10. Lagrange Interpolation

Lagrange Interpolation

Table of Contents
  1. Introduction
  2. Algorithm
  3. Codes
  4. Examples

Introduction

We can write the second order polynomial in the form

    \[ P_2(x)=b_1(x-x_0)(x-x_1)+b_2(x-x_1)(x-x_2)+b_3(x-x_2)(x-x_0) \]

Let us assume (x_0,f_0), (x_1, f_1) and (x_2, f_2) are the three interpolating points then,

    \[ P_2(x_0)=f_0=b_2(x_0-x_1)(x_0-x_2), \]

    \[ P_2(x_1)=f_1=b_3(x_1-x_2)(x_1-x_0) and \]

    \[ P_2(x_2)=f_2=b_1(x_2-x_0)(x_2-x_1) \]

Using above we have

    \[ b_2 = {{f_0} \over {(x_0-x_1)(x_0-x_2)} } , \]

    \[ b_3 = {{f_1} \over {(x_1-x_2)(x_1-x_0)}} and \]

    \[ b_1 = {{f_2} \over {(x_2-x_0)(x_2-x_1)}} \]

Putting the values together we have,

    \[ P_2(x)= {{f_2(x-x_0)(x-x_1)} \over {(x_2-x_0)(x_2-x_1)}}+{{f_0(x-x_1)(x-x_2)} \over {(x_0-x_1)(x_0-x_2)}}+{{f_1(x-x_2)(x-x_0)} \over {(x_1-x_2)(x_1-x_0)}} \]

This form can be written as

    \[ \begin{split} P_2(x) & = {f_0l_0+f_1l_1+f_2l_2} \\ & = \sum_{i=0}^{2} {f_il_i(x)} \end{split} \]

where l_i(x) = \prod_{j=0,j \neq i}^{2} \frac{x-x_j}{x_i-x_j}

Generalizing we have

    \[ P_n(x)= \sum_{i=0}^{n} {f_il_i(x)} \]

Algorithm

1. Start 
2. Read number of points, let us assume (n)
3. Read the value at which the value is needed, let us assume (x)
4. Read given data points
5. Calculate the value of Li 
     for I = 1 to n 
        for j = 1 to n
           if (j!=i)
              L[i] = L[i]*((x-x[i])/(x[i]-x[j]))
           Endif
        endfor 
     endfor
6. Calculate the interpolated point at x
   For i= 1 to n 
      t=t+fx[i]*lx[i]
   Endfor
7. Print the interpolated value v at x
8. End

Codes

C ProgramJS
#include <stdio.h>
#include <conio.h>

void main()
{
    float x[100], y[100], xp, yp = 0, p;
    int i, j, n;
    clrscr();
    /* Input Section */
    printf("Enter number of data: ");
    scanf("%d", &n);
    printf("Enter data:\n");
    for (i = 1; i <= n; i++)
    {
        printf("x[%d] = ", i);
        scanf("%f", &x[i]);
        printf("y[%d] = ", i);
        scanf("%f", &y[i]);
    }
    printf("Enter interpolation point: ");
    scanf("%f", &xp);
    /* Implementing Lagrange Interpolation */
    for (i = 1; i <= n; i++)
    {
        p = 1;
        for (j = 1; j <= n; j++)
        {
            if (i != j)
            {
                p = p * (xp - x[j]) / (x[i] - x[j]);
            }
        }
        yp = yp + p * y[i];
    }
    printf("Interpolated value at %.3f is %.3f.", xp, yp);
    getch();
}

Examples

Was this article helpful to you? Yes No

How can we help?

Leave a Reply

Your email address will not be published. Required fields are marked *