如何用C++实现牛顿插值法？

在C++中，你可以使用牛顿插值法（也称为拉格朗日插值法的一种）来近似数据点之间的函数。牛顿插值的基本思想是构建多项式通过给定的数据点，每个数据点对应多项式的根。以下是简单的步骤：

#include <iostream>
#include <vector>

// 计算拉格朗日基础多项式
double lagrange_interpolation(const std::vector<double>& x_data, const std::vector<double>& y_data, double x) {
    int n = x_data.size();
    double result = y_data[0];

    for (int i = 1; i < n; ++i) {
        double l_i = 1;
        for (int j = 0; j < n; ++j) {
            if (j != i) {
                l_i *= (x - x_data[j]) / (x_data[i] - x_data[j]);
            }
        }
        result += l_i * y_data[i];
    }

    return result;
}

int main() {
    std::vector<double> x = {0, 1, 2, 3};
    std::vector<double> y = {1, 4, 9, 16}; // f(x) = x^2

    double interpolated_value = lagrange_interpolation(x, y, 2); // 插值点 x=2

    std::cout << "Interpolated value at x=2 is: " << interpolated_value << std::endl;

    return 0;
}

在这个例子中，我们首先计算了一个n次多项式，其中`x_data`是一个包含数据点x值的向量，`y_data`则包含对应的y值。然后对于每个数据点，我们构造了一个拉格朗日基础多项式，并将其乘以该点的y值。最后，我们将所有这样的项相加，得到在给定x值处的插值结果。