拉格朗日插值误差与节点数n的关系及误差估计正确性咨询

核心方法正确性 #

你采用足够密的离散采样点最大误差模估计区间上插值误差的∞范数，这个思路是正确的：当M取值足够大时，采样点可以覆盖区间内几乎所有误差极值点，得到的最大误差值可以作为误差范数的可靠估计，你设置M=100000对于[0,1]区间来说密度完全满足要求。

代码存在的错误 #

你当前的代码存在几处逻辑错误，会导致误差估计结果不准：

• 端点函数值未赋值：你仅对k=1到k=n-2的节点赋值了f[k]，端点x[0]、x[n-1]对应的f[0]和f[n-1]未初始化，插值计算时会引用随机值。
• 等距节点生成逻辑错误：你硬编码x[n-1]=b，而中间节点用x[k]=a+((b-a)*k)/n计算，会导致最后两个节点的间距小于其他节点，不是标准等距节点。正确的n个等距节点生成逻辑应该是步长为(b-a)/(n-1)，覆盖[a,b]全区间。
• 采样点和插值区间绑定：当前你把插值区间固定为[0,1]，采样t直接用k/M计算，如果后续放开a、b的输入自定义区间，需要同步把采样t改为a + (b-a)*k/M，否则采样区间和插值区间不匹配。

修正后的参考代码 #

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

double func(double x) 
{
    return sin(x); 
}

double lagr(double *x, double *f, double t, int n); 

int main(void)
{
    int n, k, M = 100000; 
    double *x, *f, t, maxr = 0, L, a = 0, b = 1; 
    printf("n="); 
    scanf("%d", &n); 
    x = (double*)malloc(n * sizeof(double));
    f = (double*)malloc(n * sizeof(double));

    // 生成n个等距插值节点，包含两端点
    for(k = 0; k < n; k++)
    {
        x[k] = a + (b - a) * k / (n - 1); 
        f[k] = func(x[k]); 
    }  

    // 密集采样计算最大误差
    for(k = 0; k < M; k++) 
    {
        t = a + (b - a) * k / M;
        L = lagr(x, f, t, n); 
        double err = fabs(L - func(t));
        if(err > maxr) maxr = err; 
    }  
    printf("Error estimation=%le", maxr); 

    free(x);
    free(f);
    return 0;
}

double lagr(double *x, double *f, double t, int n)
{
    int k, j;
    double sum = 0, p;
    for(k = 0; k < n; k++)
    {
        p = 1;
        for(j = 0; j < n; j++)
        {
            if(j != k)
            {
                p *= (t - x[j]) / (x[k] - x[j]); 
            }    
        }
        sum += p * f[k]; 
    }
    return sum; 
}

额外注意事项 #

• 等距拉格朗日插值存在龙格现象：如果替换为非光滑函数（例如Runge函数f(x)=1/(1+25x²)），会出现节点数n越大误差反而越高的情况，这是等距拉格朗日插值本身的特性，不是误差估计方法的问题。
• 你可以用理论误差上界验证结果：sin(x)的任意阶导数绝对值不超过1，等距节点插值的理论误差上界为1/(n!) * ((b-a)/4)^n，你计算得到的估计误差应该小于该上界，可用于验证结果正确性。
• 当前拉格朗日插值的实现时间复杂度为O(n²)，如果n取值较大（>50）会很慢，仅适合小规模节点的误差分析。

内容的提问来源于stack exchange，提问作者Nickie