Question

Write an algorithm to compute the value of a function using Lagrange’s interpolation.

Answer 1

The interpolating polynomial is:

$$L(x)=\dfrac{(x-x_1)(x-x_2)...(x-x_n)}{(x_0-x_1)(x_0-x_2)...(x_0-x_n)}\times y_0$$

$$+\dfrac{(x-x_0)(x-x_2)...(x-x_n)}{(x_1-x_0)(x_1-x_2)...(x_1-x_n)}\times y_1$$

$$+...$$

$$+\dfrac{(x-x_0)(x-x_1)...(x-x_{n-1})}{(x_n-x_0)(x_n-x_1)...(x_n-x_{n-1})}\times y_n$$

1. Start

2. Read number of data (n)

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

4. Read value of independent variables say xp
   whose corresponding value of dependent variables 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