ラグランジュ補間

四点テンプレート:Math に対する三次補間多項式 テンプレート:Math (黒破線) は基底多項式 テンプレート:Math のスケールを変えたものの和である。この補間多項式は与えられた四つの制御点を通り、各スケールされた基底多項式は対応する制御点を通り、それ以外の三つの制御点に対応する テンプレート:Mvar のところでは テンプレート:Math になっている。

数値解析におけるラグランジュ補間（ラグランジュほかん、テンプレート:Lang-en-short）は、多項式補間に用いられる。相異なる点の集合 テンプレート:Mvar および数値 テンプレート:Mvar に対し、そのラグランジュ補間多項式は、各 テンプレート:Mvar において対応する値として テンプレート:Mvar をとるような次数最小の多項式である。このように次数最小の多項式は一意に決まるが、決定する方法は複数存在するため、「ラグランジュ補間多項式」という名称をその一意な多項式の「ラグランジュ形」というふうに言及するのは正確でない。

名称はジョゼフ＝ルイ・ラグランジュに因んだものだが、ラグランジュの発表する1795年よりも以前に、この方法を初めて発見したのは1779年のエドワード・ワーリングである。ラグランジュの結果はレオンハルト・オイラーが1783年に発表したより複雑な形の公式の簡単な帰結となるものであった。

ラグランジュ補間多項式は数値積分法の一種ニュートン–コーツ法でも用いられ、また有限体上で計算されたラグランジュ補間多項式は暗号理論におけるテンプレート:Ill2でも用いられる。

ラグランジュ補間は巨大振幅に関するルンゲ現象の影響を受けやすい。また評価点 テンプレート:Mvar の変更に関して補間の計算を全くやり直す必要があるから、そのような目的では変更が容易にできるニュートン補間がしばしば用いられる。

定義

テンプレート:Math 個のデータ点集合 $(x_0,y_0),\dots ,(x_j,y_j),\dots ,(x_k,y_k)$ はどの二つの テンプレート:Mvar も同じでないとする。これらのデータのラグランジュ型の補間多項式とは、ラグランジュ基底多項式 $${\ell }_j(x):=\prod _{\genfrac{}{}{0ex}{}{0\le m\le k}{m\ne j}}\frac{x-x_m}{x_j-x_m}=\frac{(x-x_0)}{(x_j-x_0)}\cdots \frac{(x-x_{j-1})}{(x_j-x_{j-1})}\frac{(x-x_{j+1})}{(x_j-x_{j+1})}\cdots \frac{(x-x_k)}{(x_j-x_k)}$$ の線型結合 $$L(x):=\sum _{j=0}^k{y}_j{\ell }_j(x)$$ を言う。

まず最初の仮定により $x_j-x_m\ne 0$ であるから、この式は常に矛盾なく定まる。$x_i=x_j$ かつ $y_i\ne y_j$ となるような対を許さない理由は、必要な補間多項式 テンプレート:Mvar ($y_i=L(x_i)$) が存在しないからである（各引数 テンプレート:Mvar に対する値は一つでなければならない）。他方、$y_i=y_j$ もそれら二点が実際には単一の点となる。

任意の テンプレート:Math に対して、基底多項式 テンプレート:Math は分子に テンプレート:Math を因子として持つから、テンプレート:Math のとき積全体も零となる。他方、テンプレート:Math のときは明らかに テンプレート:Math が成り立つ。すなわち、 ${\ell }_j(x_i)={\delta }_{ij}$ である。ここに右辺はクロネッカーのデルタ。したがって各点 テンプレート:Mvar において $L(x_i)=y_i+0+0+\cdots +0=y_i$ となり テンプレート:Mvar は所期の函数の補間を与えるものとなる。

注意

ラグランジュ多項式の集合に対する補間の発散の例

ラグランジュ型の補間では、多項式補間の線型性と補間多項式の一意性があるため、証明や理論的な議論では都合がよい。この一意性はヴァンデルモンド行列の可逆性（同じことだがヴァンデルモンド行列式が至る所消えないこと）からも導けることである。

しかしながら、構成からわかる通り、節点 テンプレート:Mvar を変更するごとに、ラグランジュ基底多項式をすべて計算し直さなければならない。そこで実用上（あるいは計算上）の目的では、重心形のラグランジュ補間（後述）やニュートン補間を用いるほうが良い。

等間隔に取った節点に関するラグランジュ補間やその他の補間は、真の函数の上下に振動する多項式を生じるものである。この振る舞いは節点の数を多くするにつれてルンゲ現象と呼ばれる発散に逢着しやすくなっていく。この問題は、補間に用いる点をテンプレート:Ill2に選ぶことで解消できる。

線型代数学的説明

補間問題を解くことは、逆行列を計算する線型代数学の問題につながる。標準的な単項式基底を用いた補間多項式 $L(x)=\sum _{j=0}^k{x}^j{m}_j$ では、テンプレート:Math を テンプレート:Mvar の係数 テンプレート:Mvar に関してヴァンデルモンド行列 $((x_i{)}^j)$ を逆に解かなければならない。対して、ラグランジュ基底を用いて $L(x)=\sum _{j=0}^k{l}_j(x)y_j$ を作れば、この場合先ほどはヴァンデルモンド行列が現れた部分には単位行列 $({\delta }_{ij})$ が現れ、逆行列は単位行列自身であるから、ラグランジュ基底は自動的に逆に解かれていることになる。

この構成は中国の剰余定理と類似対応している（つまり、素数を法とする整数の剰余を調べる代わりに、一次式を法とする多項式の剰余を見ている）。

重心形

ラグランジュ基底多項式を $$\begin{array}{cc}\ell (x)& =(x-x_0)(x-x_1)\cdots (x-x_k)\\ {\ell }^{\prime }(x_j)& =\frac{d\ell (x)}{dx}{|}_{x=x_j}=\prod _{i=0,i\ne j}^k(x_j-x_i)\end{array}$$ を用いて、${\ell }_j(x)=\frac{\ell (x)}{{\ell }^{\prime }(x_j)(x-x_j)}$と書き直す。これは重心重み付け (barycentric weight)を $w_j=\frac{1}{{\ell }^{\prime }(x_j)}$ と定めれば簡潔に $${\ell }_j(x)=\ell (x)\frac{w_j}{x-x_j}$$ と書くことができる、これを重心ラグランジュ補間の「第一形」と呼ぶ。

この形の多項式補間を考えることの利点は、補間多項式 $L(x)=\ell (x)\sum _{j=0}^k\frac{w_j}{x-x_j}{y}_j$ を評価するときに、重み テンプレート:Mvar が事前に分かっていれば、テンプレート:Math で計算できることである（ラグランジュ基底 テンプレート:Math を個別に計算するのは テンプレート:Math 掛かる）。もうひとつ重心形補間の利点として、新しい節点 テンプレート:Math の追加も各 テンプレート:Mvar を $(x_j-x_{k+1})$ で割って、新しい テンプレート:Math を計算するだけで容易にできる点が挙げられる。

さらに第一形を単純化することもできて、まず定数函数 テンプレート:Math の重心補間 $g(x)=\ell (x)\sum _{j=0}^k\frac{w_j}{x-x_j}$ を計算してから テンプレート:Mvar を テンプレート:Mvar で割れば、得られる

$L(x)=\frac{\sum _{j=0}^k\frac{w_j}{x-x_j}{y}_j}{\sum _{j=0}^k\frac{w_j}{x-x_j}}$ は与えられた節点における補間性を失わない。この補間多項式を重心補間多項式の「第二形」あるいは「真の形」という。真の重心補間多項式は、テンプレート:Mvar の各節点における評価に際してラグランジュ基底 テンプレート:Mvar を評価しなくてよいという点で有利である。

誤差項

与えられた函数 テンプレート:Mvar を、節点 テンプレート:Math において次数 テンプレート:Mvar の多項式で補完するとき、誤差 $R(x)=f(x)-L(x)$ は $$R(x)=f[x_0,\dots ,x_n,x]\ell (x)=\ell (x)\frac{f^{(n+1)}(\xi )}{(n+1)!},x_0<\xi <x_n,$$ と表せる。ただし、$f[x_0,\dots ,x_n,x]$ は差商であるテンプレート:Efn. またこの誤差項を複素領域における周回積分 $$R(z)=\frac{\ell (z)}{2\pi i}\underset{C}{\int }\frac{f(t)}{(t-z)(t-z_0)\cdots (t-z_n)}dt=\frac{\ell (z)}{2\pi i}\underset{C}{\int }\frac{f(t)}{(t-z)\ell (t)}dt$$ と書くこともできる。

この誤差項によって、誤差の範囲を $$|R(x)|\le \frac{(x_n-x_0{)}^{n+1}}{(n+1)!}\underset{x_0\le \xi \le x_n}{\max }|f^{(n+1)}(\xi )|$$ と見積もることができる。

参考文献

• 高橋大輔 『数値計算』 岩波書店、1996年。

関連項目

• ネヴィルのアルゴリズム
• ニュートン補間: ニュートン形の補間多項式
• バーンスタイン多項式: バーンスタイン形の補間多項式
• テンプレート:Ill2
• テンプレート:Ill2
• テンプレート:Ill2
• テンプレート:Ill2
• テンプレート:Ill2
• テンプレート:Ill2: ラグランジュ–シルベスター補間

外部リンク

• テンプレート:高校数学の美しい物語
• テンプレート:SpringerEOM
• テンプレート:MathWorld
• テンプレート:ProofWiki
• テンプレート:ProofWiki

• ALGLIB has an implementations in C++ / C# / VBA / Pascal.
• GSL has a polynomial interpolation code in C
• SO has a MATLAB example that demonstrates the algorithm and recreates the first image in this article
• Lagrange Method of Interpolation — Notes, PPT, Mathcad, Mathematica, MATLAB, Maple at Holistic Numerical Methods Institute
• Lagrange interpolation polynomial on www.math-linux.com
• Dynamic Lagrange interpolation with JSXGraph
• Numerical computing with functions: The Chebfun Project
• Worksheet Function for Bicubic Lagrange Interpolation
• Lagrange polynomials in Python