ラグランジュ補間

HOME>>メモ>>アルゴリズム>>ラグランジュ補間

ラグランジュ補間

ある関数$f(x)$上の$n+1$個の点$(x_0, y_0), (x_1, y_1), \cdots, (x_n, y_n)$が分かっているとします。 このとき、与えられたすべての点を通る多項式関数を求める方法がラグランジュ補間です。

3点を補間してみる

例として3点を通る補間関数を考えてみます。 下の図で、$(x_0, y_0), (x_1, y_1), (x_2, y_2)$の3点を通る関数$P(x)$を求めるのがここでの目的です。

3点を通る補間関数

しかし、このような関数を直接求めるのは困難です。 そこで、補間関数を次の図のように3つの関数に分解します。

補間関数を分解
$y_0L_0(x)$(赤の曲線)は点$(x_0, y_0)$を通りますが、それ以外の点$x=x_1, x_2$では0になるような関数です。 同様に、$y_1L_1$(x)(緑の曲線)は点$(x_1, y_1)$を通りそれ以外の点$x=x_0, x_2$では0、 $y_2L_2(x)$(青の曲線)は点$(x_2, y_2)$を通りそれ以外の点$x=x_0, x_1$では0となるような関数です。 これらの関数を用いると、$P(x)$は次のように表すことができます。 \[P(x)=y_0L_0(x) + y_1L_1(x) + y_2L_2(x)\]

分解したあとの関数を求めるのは簡単です。 $L_0(x)$は$x=x_1, x_2$で0となるので、因数として$(x-x_1)(x-x_2)$を持つはずです。 $L_0(x_0)=1$となるように係数を調節してやれば \[L_0(x)=\frac{(x-x_1)(x-x_2)}{(x_0-x_1)(x_0-x_2)}\] となります。$L_1(x), L_2$(x)についても同様に考えると次のようになります。 \begin{eqnarray*} L_1(x) &=& \frac{(x-x_0)(x-x_2)}{(x_1-x_0)(x_1-x_2)}\\ L_2(x) &=& \frac{(x-x_0)(x-x_1)}{(x_2-x_0)(x_2-x_1)} \end{eqnarray*}

一般的な場合

以上のことを一般的な場合に拡張すると \begin{eqnarray*} P(x) &=& \sum_{i=0}^{n}y_iL_i(x)\\ L_i(x) &=& \frac{(x-x_0)\cdots(x-x_{i-1})(x-x_{i+1})\cdots(x-x_n)}{(x_i-x_0)\cdots(x_i-x_{i-1})(x_i-x_{i+1})\cdots(x_i-x_n)}\\ &=&\prod_{\footnotesize\begin{array}{c}j=0\\j\not = i\end{array}}^{n}\frac{x-x_j}{x_i-x_j} \end{eqnarray*} が得られます。これがラグランジュ補間の補間関数です。

実際にやってみよう

一変数の場合について、実際にやってみました。 例によって、SVGにJavascriptを埋め込んだ簡単なアニメーションです。 すべての赤い点を通るように、黒い曲線を引きます。ドラッグ＆ドロップで点を移動できます。

残念ながら現在使用しているブラウザでは表示できません。 IE以外のブラウザの最新版をダウンロードしてください。

ラグランジュ補間のような多項式補間では、補間する点の数が増えると下のように振動してしまいます。 このような現象をルンゲ現象と言います。これを回避するには、いくつかの区間に分割する、区間の端の点を多くする、などの対処方法をとる必要があります。

残念ながら現在使用しているブラウザでは表示できません。 IE以外のブラウザの最新版をダウンロードしてください。