C 语言牛顿前向插值

2024 年 8 月 28 日 | 阅读 10 分钟

牛顿前插法 是一种数值方法，用于逼近给定数据点之间的函数值。当数据点等距分布时，这种技术特别有用。它是一种多项式插值，通过给定的数据点构建一个特定次数的多项式。然后，该多项式用于估计中间点处的函数值。

该插值方法以艾萨克·牛顿爵士的名字命名，他为微积分和插值技术做出了重要贡献。

牛顿前插法的过程

给定数据

你从数据点 (x_i, y_i) 开始，其中 x_i 是自变量值，y_i 是相应的函数值。这些数据点通常按 x 的升序排列。

差商

差商是牛顿前插法的基础。它们是根据给定的数据点递归计算的。差商定义如下：

对于 j = 0, f[i][0] = y_i （即原始的 y 值）。

对于 j > 0, f[i][j] = (f[i+1][j-1] - f[i][j-1]) / (x_i+j - x_i)。

这里，i 表示数据点的索引，j 表示差商的阶数。

插值多项式

使用计算出的差商，你可以构建一个形式为

P(x) = f[0][0] + (x - x_0)f[0][1] + (x - x_0)(x - x_1)f[0][2] + ...

的插值多项式。之后，该多项式用于逼近给定数据点之间点的函数值。

估计函数值

一旦有了插值多项式，你就可以将所需的x 值代入多项式，以估计该点处的相应函数值。

好处

牛顿前插法有几个优点。牛顿前插法的一些优点如下：

简单易于实现

牛顿前插法简单易懂且易于实现。该方法涉及一个逐步计算差商和构建插值多项式的过程。这种简单性使其对于插值技术和数值分析的初学者来说都很容易上手。

阶数灵活

它在选择插值多项式的阶数方面提供了灵活性。这意味着你可以根据要逼近函数的复杂性和所需的精度来修改阶数。高次多项式可以捕捉更复杂的行为，而低次多项式则产生更简单的逼近。

应用于平滑曲线

牛顿前插法的另一个优点是它适合函数在数据点之间具有相对平滑的行为。当底层函数表现出渐变或平滑过渡时，该方法可提供准确的逼近，紧密遵循函数的行为。在处理表现出渐变变化的实际数据时，此特性尤其有利。

局限性

牛顿前插法有几个局限性。牛顿前插法的一些局限性如下：

对数据变化的敏感性

虽然该算法可以处理数据集的变化，但它可能对剧烈变化或异常值很敏感。数据中的快速波动或不规则行为可能导致插值多项式出现振荡。这些振荡可能导致不准确的逼近和可靠性损失。

外插不准确

牛顿前插法更适合外插超出提供的数据点范围。尝试估计范围之外的值可能无法产生可靠且准确的结果。外插使用插值方法可能会引入显著的错误，应避免使用。

距离越远，精度越低

随着你离两个数据点之间的中点越来越远，插值值的精度会趋于下降。对于具有快速变化、急剧不连续或高频振荡的函数，此限制尤为明显。当远离数据区间中心时，该方法的精度会降低。

算法

步骤 1： 读取数据点的数量 n。将 n 个等距的 x 值及其相应的 y 值读入数组 x 和 y。

步骤 2： 计算连续 x 值之间的公差 h：h = x[1] - x[0]。初始化一个二维数组 f 来存储差商。

步骤 3

对于从 0 到 n - 1 的每个数据点 i，设置 f[i][0] = y[i]。
对于从 1 到 n - 1 的每个差商阶数 j：
对于从 0 到 n - j - 1 的每个数据点 i，计算
f[i][j] = (f[i+1][j-1] - f[i][j-1]) / (x[i+j] - x[i])。

步骤 4： 读取要进行插值的点 x_interp 的值。将结果初始化为 f[0][0]（第一个差商）。然后，将项初始化为 1.0。

步骤 5： 对于从 0 到 n - 1 的每个数据点 i。将项乘以 (x_interp - x[i])。

通过添加 f[0][i+1] * term 来更新结果。

步骤 6： 打印函数在 x_interp 处的插值结果，以及提供的 x 和 y 值。

注意：此算法假定数据点是等距的，并且特定于牛顿前插法。

程序

让我们举一个例子来理解 C 语言中牛顿前插法的用法。

#include <stdio.h>
int main() {
    int n; // Number of data points
printf("Enter the number of data points: ");
scanf("%d", &n);
    double x[n], y[n]; // Arrays to store x and y values
printf("Enter the equidistant x values:\n");
    for (int i = 0; i< n; i++) {
scanf("%lf", &x[i]);
    }
printf("Enter the corresponding y values:\n");
    for (int i = 0; i< n; i++) {
scanf("%lf", &y[i]);
    }
    double h = x[1] - x[0]; // Common difference
    double f[n][n]; // Divided differences
    // Initialize the divided differences with y values
    for (int i = 0; i< n; i++) {
        f[i][0] = y[i];
    }
    // Compute divided differences
    for (int j = 1; j < n; j++) {
        for (int i = 0; i< n - j; i++) {
            f[i][j] = (f[i+1][j-1] - f[i][j-1]) / (x[i+j] - x[i]);
        }
    }
    // Interpolating polynomial evaluation
    double x_interp; // The point where you want to interpolate
printf("Enter the value of x for interpolation: ");
scanf("%lf", &x_interp);
    double result = f[0][0];
    double term = 1.0;
    for (int i = 0; i< n; i++) {
        term *= (x_interp - x[i]);
        result += f[0][i+1] * term;
    }
printf("Interpolated value at x = %.2lf is %.6lf\n", x_interp, result);
    return 0;
}

输出

Enter the number of data points: 4
Enter the central x values:
1.0 2.0 3.0 4.0
Enter the corresponding y values:
2.0 4.0 8.0 16.0
Enter the value of x for interpolation: 2.5
Interpolated value at x = 2.50 is 7.875000

说明

首先，程序通过包含必要的头文件 stdio.h 来开始，该文件提供了输入和输出的函数。main 函数是程序的入口点。
程序要求用户输入数据点数 (n)。它确定用户将提供的x 和 y 值的数量。
声明两个数组 x 和 y，用于存储中心x 值及其相应的y 值。
程序使用循环从用户读取中心x 值并将它们存储在x 数组中。
之后，另一个循环用于从用户读取相应的y 值并将它们存储在y 数组中。
连续x 值之间的公差 h 计算为 h = x[1] - x[0]。此差值稍后用于差商计算。声明一个二维数组 (f) 来存储差商。
通过将y 值复制到f 数组的第一列来初始化差商。
两个嵌套循环计算每个阶数 j 的差商。用于计算的公式是(f[i+1][j-1] - f[i][j-1]) / (x[i+j] - x[i])。
程序提示用户输入要进行插值的 x 值。
一个循环使用牛顿前插法公式计算插值结果。在循环的每次迭代中更新结果。
之后，使用printf 函数打印插值结果，显示提供的x 值和插值结果。
程序返回 0，表示成功执行，然后是main 函数。
此代码实现了牛顿前插法，通过提供的中心数据点来逼近给定点处的函数值。提供的输入值将影响结果，程序将根据输入数据计算并显示插值结果。

复杂度分析

时间复杂度

代码读取数据点数、等距 x 值和相应的y 值。它涉及读取具有 O(n) 线性时间复杂度的 n 个数据点。
代码初始化差商数组，这需要遍历所有 n 个数据点并填充 f 数组的初始列。这以 O(n) 时间复杂度执行。
嵌套循环计算每个阶数 j 的差商。
外循环迭代 n - 1 次，内循环迭代最多 n - j 次，从而得到 O(n^2) 的时间复杂度。
用于评估插值多项式的循环迭代 n 次。它是 O(n)。插值结果的打印需要恒定的时间复杂度 O(1)。
总的来说，占主导地位的时间复杂度来自于差商的计算：O (n^2)。因此，代码的总时间复杂度为 O(n^2)。

空间复杂度

x 和 y 数组分别存储 n 个数据点，导致空间复杂度为 O(n)。
存储差商的二维数组 f 的尺寸为 n x n，导致空间复杂度为 O(n^2)。
代码中使用的其他变量（如 h, x_interp, result, term, 循环计数器等）占用恒定空间。
对空间复杂度贡献最大的来自差商数组 O(n^2)。因此，代码的总空间复杂度为 O(n^2)。

应用

牛顿前插法在需要估计已知数据点之间的函数值的各个领域都有应用。在以上每个应用中，牛顿前插法在填充数据点之间的空白和提供对底层现象更全面的理解方面发挥着至关重要的作用。插值方法的选择取决于数据的具体特征、所需的精度以及分析的具体目标。一些常见应用包括：

工程与物理

在工程和物理实验中，由于时间、成本或物理限制，在每个点测量数据通常是不切实际的。例如，在对材料进行应力-应变测试时，数据可能以特定间隔收集。牛顿前插法有助于估计这些数据点之间的应力或应变值，从而提供对材料行为的更完整视图。

计算机图形学

在计算机图形学中，曲线和形状通常由控制点定义。牛顿前插法可以在这些控制点之间生成平滑曲线，从而创建视觉上令人愉悦且逼真的图形。贝塞尔曲线和B 样条曲线是使用插值创建用于图形设计和动画的曲线的流行示例。

地理信息系统 (GIS)

GIS 应用涉及处理空间数据以创建地图和分析地理现象。在GIS中，数据通常在特定位置收集，产生离散的数据点。插值技术，包括牛顿前插法，有助于估计非采样位置的值，生成连续的空间表面，用于高程、温度和人口密度等属性。

金融与经济

在金融领域，像债券和期权这样的金融工具的价值在不断变化。然而，市场数据通常以离散的间隔提供。牛顿前插法有助于估算在任何给定时间点的这些金融工具的价值，从而使投资者和分析师能够做出明智的决策。

科学数据分析

在科学研究中，数据收集可能受到时间限制或测量设备限制等因素的影响。牛顿前插法有助于填补数据中的空白，使研究人员能够更准确地分析趋势和模式。例如，在气候科学中，它用于估计不规则收集的天气数据之间的历史温度值。

特性

牛顿前插法有几个特点。牛顿前插法的一些特点如下：

等距数据点

牛顿前插法在提供的x 轴上的数据点等距分布时最为有效。等距数据点简化了差商的计算，这些差商对于构建插值多项式至关重要。当数据点等距时，计算遵循一致的模式，从而提高计算效率。

多项式插值

该方法涉及创建一个通过提供的数据点的多项式方程。该多项式是底层函数的代理，允许你估计给定数据点之间的函数值。通过多项式插值，你可以获得函数的连续表示，从而有助于分析和可视化。

差商

差商是牛顿前插法的基石。它们量化了数据点之间区间内函数值的增量变化。通过系统地计算这些差值，算法可以导出插值多项式的系数。这些系数对于估计数据点之间的函数值至关重要。

对等距点高效

牛顿前插法的效率在处理中心数据点时尤为明显。等距分布简化了差商的计算，使其遵循可预测的结构。因此，一致的计算模式使整个算法更加高效。

增量构建

该方法的定义特征之一是其增量性质。该算法逐步构建差商和插值多项式。它首先计算低阶差商，然后逐步构建高阶差商。这种增量方法有助于管理计算的复杂性。

渐进精度

插值结果的精度随着你越来越接近两个数据点之间的中点而提高。由于多项式曲线的性质，多项式逼近在该范围内变得更准确。但是，当远离该中点时，精度会降低，可能导致更大的误差。

下一主题汉诺塔

← 上一个下一个 →

C 语言牛顿前向插值

牛顿前插法的过程

好处

局限性