C++ Program: Lagrange Interpolation

 

C++ Program For Lagrange Interpolation

Here’s a C++ program for finding the value of a function at a given point using the Lagrange Interpolation Method, followed by a detailed step-by-step explanation.

C++ Program: Lagrange Interpolation

cpp
#include <iostream>
#include <vector>

using namespace std;

// Function to perform Lagrange Interpolation
double lagrangeInterpolation(const vector<double>& x_points, const vector<double>& y_points, double x) {
    int n = x_points.size(); // Number of points
    double result = 0.0;

    for (int i = 0; i < n; i++) {
        // Calculate L_i(x)
        double L_i = 1.0;
        for (int j = 0; j < n; j++) {
            if (i != j) {
                L_i *= (x - x_points[j]) / (x_points[i] - x_points[j]);
            }
        }
        // Add the contribution of L_i(x) to the final result
        result += L_i * y_points[i];
    }

    return result;
}

int main() {
    // Input data points
    vector<double> x_points = {1, 2, 3}; // x-coordinates
    vector<double> y_points = {2, 3, 5}; // y-coordinates

    double x; // Point to interpolate
    cout << "Enter the value of x to interpolate: ";
    cin >> x;

    // Perform interpolation
    double interpolatedValue = lagrangeInterpolation(x_points, y_points, x);
    cout << "The interpolated value at x = " << x << " is " << interpolatedValue << endl;

    return 0;
}

---

Step-by-Step Guide

1. Understand Lagrange Interpolation Formula:

The Lagrange interpolation formula is:

$$P(x) = \sum_{i=0}^{n-1} y_i \cdot L_i(x)$$

where:

$$L_i(x) = \prod_{j=0, j \neq i}^{n-1} \frac{x - x_j}{x_i - x_j}$$

2. Input Data Points:

• The program uses two vectors: x_points and y_points to store the known data points $(x_i,y_i).$
• These vectors are used to represent the known values of the function.

3. Iterate Over Data Points:

• For each point $i$, calculate the Lagrange basis polynomial $L_i(x)$.
• This involves multiplying terms $(x-x_j)\mathrm{/}(x_i-x_j)\; for\; all$$j \neq i$.

4. Accumulate the Result:

• Multiply $L_i(x)$ by the corresponding $y_i$, and add it to the final result.

5. Output the Interpolated Value:

• Once all terms have been summed, the program prints the interpolated value of the function at $x$.

---

Example Execution:

Suppose you input the following:

• Known points: $(1, 2), (2, 3), (3, 5)$
  
• Enter $x = 2.5$
  

The program computes:

1. $L_0(2.5) = \frac{(2.5 - 2)(2.5 - 3)}{(1 - 2)(1 - 3)}$,
2. $L_1(2.5) = \frac{(2.5 - 1)(2.5 - 3)}{(2 - 1)(2 - 3)}$,
3. $L_2(2.5) = \frac{(2.5 - 1)(2.5 - 2)}{(3 - 1)(3 - 2)}$.

The final interpolated value is:

$$P(2.5) = y_0 \cdot L_0(2.5) + y_1 \cdot L_1(2.5) + y_2 \cdot L_2(2.5)$$

The output will be the interpolated value at $x = 2.5$