閑古鳥

オールドプログラマの日記。プログラミングとか病気(透析)の話とか。

ラグランジュ補間

突然ですがラグランジュ補間をします。式は以下。

Pn(x)=\Bigsum_{i=0}^{n}y_i{Li(x)}

Li(x)=\Bigprod_{j=0}^{N(i\neq j)}\frac{x-x_j}{x_i-x_j}

\prod が今日はじめて見たので読み方も意味もよくわからないんですが、とりあえず積和すればいいらしいです。

式はなんとなくわかったので早速 C++ で実装。手元の本には C での実装も書いてあったんですが、自分でも書いてみた方がいいかと思って書いてみました。

#include <vector>

class Lagrange
{
public:
    void Input(const double* x, const double* y, const int N);
    double Calculate(const double x);

private:
    std::vector<double> m_vX, m_vY;
};

void Lagrange::Input(const double* x, const double* y, const int N)
{
    m_vX.assign(x, x + N);
    m_vY.assign(y, y + N);
}

double Lagrange::Calculate(const double x)
{
    double result = 0.0;

    const int N = m_vX.size();
    for(int i = 0; i < N; ++i) {
        double li = 1.0;
        for(int j = 0; j < N; ++j) {
            if(j != i) {
                li *= (x - m_vX[j]) / (m_vX[i] - m_vX[j]);
            }
        }
        result += li * m_vY[i];
    }
    return result;
}

クラスにしたせいで無駄に長くなってしまったけれどまあ良し。意外と簡単です。

で、これに値を入れて結果を見てもよくわからないので、このクラスを使って適当に曲線を描いてみました。 .Net Framework の Graphics クラスには DrawCurve というメソッドがあって、これを使うと簡単に C スプラインで補間して線を出してくれるらしいので、一緒に出してみました。

f:id:wata_d:20060501021238p:image

黒い線が C スプラインで補間して書いた線で、赤い線がラグランジュ補間です。ラグランジュ補間だと振動が激しいのでスプラインの方が良いらしいのですが、重ねてみるとよくわかりますね。

追記

ソース中の式が間違っていたので修正。古い方のバグありコードを載せてしまいました……。