algorithm - 符号计算来自 Neville 算法的多项式

Question

我正在研究 Neville 的算法，该算法依赖于计算多项式插值。关于它的更多信息，您可以在 http://en.wikipedia.org/wiki/Neville%27s_algorithm 找到.在某个时候计算多项式对我来说不是问题。有很多关于它的资料。我的问题依赖于我不想在某个时候计算多项式，我想获得这种形式的多项式:a_0 + a_1x + ... + a_nx^n。我不知道如何开始。你能给我一些提示吗？

Answer 1

Neville 算法的一个变体允许计算一些常量(不是多项式系数)以与另一个函数一起使用，该函数可以在任意点计算插值多项式。后一个函数很容易区分。下面的 C 代码是我使用的，我相信它工作正常。但是我怀疑您可能会对多项式插值的效果感到失望，除非您提供的数据确实来自多项式。如果您可以轻松地在多个点对数据进行采样，那么最好通过对数据进行最小二乘法拟合来找到多项式(表示为切比雪夫多项式之和)。

// fill C (allocated if null) with params for interpolating polynomial
// use params with interp_poly_eval
// !! these are NOT polynomial coefficients. 

double* interp_poly( Int deg, const double* x, const double* y, double* restrict C)
{
double* c = C ?: calloc( deg+1, sizeof *c);
Int i, j;
    memcpy( c, y, (deg+1)*sizeof *y);
    for (i=1; i<=deg; i++) 
    {   for (j=deg; j>=i; j--)
        {   c[j] = (c[j]-c[j-1]) / (x[j]-x[j-i]);
        }
    }
    return c;
}


double  interp_poly_eval( Int deg, const double* c, const double* x, double X)
{
double  p = c[deg];
Int i = deg;
    while( --i >= 0)
    {   p = c[i] + (X-x[i])*p;
    }
    return p;
}

// as above but also returns derivative of the polynomial through pdp
double  interp_poly_eval_d( Int deg, const double* c, const double* x, double X, double* pdp)
{
double  p = c[deg];
double  dp = 0.0;
Int i = deg;
    while( --i >= 0)
    {   dp = (X-x[i])*dp + p;
        p = c[i] + (X-x[i])*p;
    }   
    *pdp = dp;
    return p;
}