ラグランジュ補間(アルゴリズム)

Lagrange Interpolation

ラグランジュ補間とは、n + 1個の点x₀, x₁, ... x_n(x₀ < x₁ < ... x_n)と、関数値f(x₀), f(x₁) , ... , f(x_n)に基づいて、n次多項式p(x)を、下記の式で求めて、任意のxからf(x)を算出する補間手法です。

１．ラグランジュ補間プログラム。p(x_n)を求めるプログラム。

#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;
}

３．テスト。

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);
    }
}