编写拉格朗日插值和牛顿插值函数

拉格朗日插值和牛顿插值都是数值分析中的两个重要技术，用于估计给定数据点上未知函数值。下面是简短的解释：

**拉格朗日插值法**：
这是一种基于多项式的方法，通过构造一个特定次数的多项式，使得这个多项式的值在已知数据点上等于对应的函数值。公式可以表示为：
\[ P(x) = \sum_{i=0}^{n} f(x_i)\frac{(x-x_0)(x-x_1)...(x-x_{i-1})(x-x_{i+1})...(x-x_n)}{(x_i-x_0)(x_i-x_1)...(x_i-x_{i-1})(x_i-x_{i+1})...(x_i-x_n)} \]
其中 \( x_0, x_1, ..., x_n \) 是数据点的坐标，\( f(x_i) \) 是对应的数据。

**牛顿插值法**：
也称为 Neville's 法，是一种迭代过程，它是拉格朗日插值的一种推广，特别是对于分段线性插值特别有效。它通过将区间分割成若干小部分，然后对每个部分应用拉格朗日插值，逐步构建出整个区域的插值函数。

为了编写这样的函数，你可能会需要以下步骤：
1. 定义两个函数：`lagrange_interpolate` 和 `newton_interpolate`。
2. 对于拉格朗日插值，计算每个节点的系数，并将它们组合成插值多项式。
3. 牛顿插值则涉及到递归地应用拉格朗日插值到子区间。

以下是简单的Python代码示例：

def lagrange_interpolate(x_data, y_data, x):
    n = len(x_data)
    result = 0
    for i in range(n):
        prod = 1
        for j in range(n):
            if j != i:
                prod *= (x - x_data[j]) / (x_data[i] - x_data[j])
        result += y_data[i] * prod
    return result

def newton_interpolate(data, x):
    # ... 实现牛顿插值递归逻辑 ...