Lagrange Interpolation Method Algorithm

In many real world applications of science and engineering, it is required to find the value of dependent variable corresponding to some value of independent variable by analyzing data which are obtained from some observation. For example, suppose we have following sets of data tabulated for x (independent variable) and y (dependent variable) :

----------------------------------------
| x: | x0 | x1 | x2 | x3 | ... | xn |
-----------------------------------
| y: | y0 | y1 | y2 | y3 | ... | yn |
----------------------------------------

Then the method of finding the value of y = f(x) corresponding to any value of x=xi within x0 and xn is called interpolation. Thus interpolation is the process of finding the value of function for any intermediate value of the independent variable. If we need to estimate the value of function f(x) outside the tabular values then the process is called extrapolation. However, in general, extrapolation is also included in interpolation.

There are different methods for interpolation for example: Newtons Forward Interpolation, Netwtons Backward Interpolation, Newtons General Interpolation with divided difference, Lagrange Interpolation etc. In this article we are going to develop an algorithm for Lagrange Interpolation.

Lagrange Interpolation Formula

If y = f(x) takes the value of y0 , y1 , y2 , y3 , ... , yn corresponding to x0 , x1 , x2 , x3 , ... , xn then


 y = f(x) = (x - x1)(x - x2)...(x - xn) * y0/(x0 - x1)(x0 - x2)...(x0 - xn) 
		
				+
	
	(x - x0)(x - x2)...(x - xn) * y1/(x1 - x0)(x1 - x2)...(x1 - xn)
				
				+ .... +
		
	(x - x1)(x - x2)...(x - xn-1) * yn/(xn - x0)(xn - x1)...(xn - xn-1)
		

is known as Lagrange Interpolation Formula for unequal intervals and is very simple to implement on computer.

Algorithm For Lagrange Interpolation Method

1. Start

2. Read number of data (n)

3. Read data Xi and Yi for i=1 ton n

4. Read value of independent variables say xp
   whose corresponding value of dependent say yp is to be determined.
   
5. Initialize: yp = 0

6. For i = 1 to n
     Set p = 1
     For j =1 to n
       If i ≠ j then 
         Calculate p = p * (xp - Xj)/(Xi - Xj)
       End If
     Next j
     Calculate yp = yp + p * Yi
   Next i

6. Display value of yp as interpolated value.

7. Stop

Recommended Readings

  1. Lagrange Interpolation Method Algorithm
  2. Lagrange Interpolation Method Pseudocode
  3. Lagrange Interpolation Method Using C Programming
  4. Lagrange Interpolation Method Using C++