SOFTIST 编程方法筆記 →目録　

拉格朗日插值法(算法)

Lagrange Interpolation

拉格朗日插值法是根据 n + 1个点x0, x1, ... xn(x0 < x1 < ... xn)的函数值f(x0), f(x1) , ... , f(xn)推出n次多項式p(x)，然后n次多項式p(x)求出任意的点x对应的函数值f(x)的算法。

１．拉格朗日插值法。求p(xn)的程序。

#define N 20
typedef struct TagXYVALUE
{
    double x;
    double y;
} XYVALUE;

XYVALUE val[N+1];

double LagrangeInterpolation(double x)
{
    double y = 0.0;
    for (int i = 0; i <= N; i ++)
    {
        double p = 1.0;
        for(int j = 0; j <= N; j++)
        {
            if (i == j)
                continue;
            p = p * (x-val[j].x) / (val[i].x - val[j].x);
        }
        y = y + p * val[i].y;
    }
    return y;
}

３．测试。用正弦波的20个采样点，还原出正弦波曲线。

void CNewtonInterpolationTestView::OnDraw(CDC* pDC)
{
    for (int i = 0; i <= N; i ++)
    {
        val[i].x = i * 15 * atan(1.0) / 45.0 * 2;
        val[i].y = sin(val[i].x);
        pDC->Rectangle((int)(val[i].x * 20) - 2, 150 - (int)(val[i].y * 50) - 2,
                                 (int)(val[i].x * 20) + 2, 150 - (int)(val[i].y * 50) + 2);
    }
    for (int j = 0; j <= N*15; j += 5)
    {
        double x = j * atan(1.0) / 45.0 * 2;
        double y = LagrangeInterpolation(x);
        pDC->SetPixel((int)(x * 20) - 2, 150 - (int)(y * 50) - 2, 0x000000ff);
    }
}