C++ Code for Newton's Interpolating Polynomials

            
#include <iostream>
#include <vector>

using namespace std;

// Function to calculate coefficients of Newton's divided difference table
void calculateCoefficients(vector<double>& x, vector<double>& y, vector<vector<double>>& f) {
    int n = x.size();
    for (int i = 0; i < n; i++) {
        f[i][0] = y[i];
    }
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < n - i; j++) {
            f[j][i] = (f[j + 1][i - 1] - f[j][i - 1]) / (x[i + j] - x[j]);
        }
    }
}

// Function to apply Newton's interpolating polynomial
double newtonInterpolation(double value, vector<double>& x, vector<double>& y, vector<vector<double>>& f) {
    int n = x.size();
    double result = f[0][0];
    double term = 1;
    for (int i = 1; i < n; i++) {
        term *= (value - x[i - 1]);
        result += f[0][i] * term;
    }
    return result;
}

int main() {
    // Sample data
    vector<double> x = {1, 2, 3, 4, 5}; // Sample x values
    vector<double> y = {10, 20, 30, 40, 50}; // Sample y values
    int n = x.size();

    // Initialize the divided difference table
    vector<vector<double>> f(n, vector<double>(n));

    // Calculate coefficients of Newton's divided difference table
    calculateCoefficients(x, y, f);

    // Sample value for interpolation
    double sampleValue = 2.5;

    // Calculate interpolated value
    double interpolatedValue = newtonInterpolation(sampleValue, x, y, f);

    // Output the results
    cout << "Sample x values: ";
    for (double val : x) {
        cout << val << " ";
    }
    cout << endl;
    cout << "Sample y values: ";
    for (double val : y) {
        cout << val << " ";
    }
    cout << endl;
    cout << "Interpolated value at x = " << sampleValue << ": " << interpolatedValue << endl;

    return 0;
}