Lagrange Interpolation Method Algorithm (Step Wise)

Table of Contents

• Introduction
• Formula
• Algorithm
• Recommended Readings

Introduction to Lagrange Method

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=x_i within x₀ and x_n 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.

Formula: Lagrange Interpolation Method

If y = f(x) takes the value of y₀ , y₁ , y₂ , y₃ , ... , y_n corresponding to x₀ , x₁ , x₂ , x₃ , ... , x_n 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: 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