用Python实现Newton插值法

一、方法介绍

牛顿插值法（Newton Interpolation）是一种通过将数据点连接一个多项式来逼近数据的方法。它使用一个递推公式来得出对应的插值多项式，因此也叫做Newton递推公式。它的主要思想是将插值多项式表示为一个递推公式，每次插入一个数据点时，就可以更新多项式的系数。

二、代码实现

下面是用Python实现Newton插值法的代码。其中，x、y分别为已知的数据点的横、纵坐标，n为数据点的个数，t为插值时需要用到的值。

def Newton(x, y, n, t):
    # 初始化数组
    f = [0] * n
    for i in range(n):
        f[i] = y[i]

    # 递推计算
    for i in range(1, n):
        for j in range(n - i):
            f[j] = (f[j] - f[j + 1]) / (x[j] - x[j + i])

    # 计算插值多项式的值
    result = f[0]
    for i in range(1, n):
        temp = f[i]
        for j in range(i):
            temp *= (t - x[j])
        result += temp

    return result

三、示例说明

下面是两个使用Newton插值法进行插值的例子。

例子1：利用牛顿插值法进行某函数的插值

假设我们需要插值的函数是$f(x) = x^2 + 3x - 2$，已知数据点如下：

x	-1	0	2
y	0	-2	12

我们要求在$x = 1$处进行插值。可以使用上述代码实现，具体代码如下：

x = [-1, 0, 2]
y = [0, -2, 12]
n = len(x)
t = 1

result = Newton(x, y, n, t)
print("f(1) = ", result)

运行结果如下：

f(1) =  2.0

例子2：利用牛顿插值法进行三次函数的插值

假设我们需要插值的函数是$f(x) = 2x^3 - 3x^2 + 4x - 1$，已知数据点如下：

x	0	1	2	3
y	-1	2	17	46

我们要求在$x = 1.5$处进行插值。同样，可以使用上述代码实现，具体代码如下：

x = [0, 1, 2, 3]
y = [-1, 2, 17, 46]
n = len(x)
t = 1.5

result = Newton(x, y, n, t)
print("f(1.5) = ", result)

运行结果如下：

f(1.5) =  6.125

通过这两个例子，我们可以看到，Newton插值法可以通过已知的数据点来精确地估计函数在指定点的值。