ラグランジュ補間

数値解析におけるラグランジュ補間（ラグランジュほかん、）は、多項式補間に用いられる。相異なる点の集合 および数値 に対し、そのラグランジュ補間多項式は、各 において対応する値として をとるような次数最小の多項式である。このように次数最小の多項式は一意に決まるが、決定する方法は複数存在するため、「ラグランジュ補間多項式」という名称をその一意な多項式の「ラグランジュ形」というふうに言及するのは正確でない。
名称はジョゼフ＝ルイ・ラグランジュに因んだものだが、ラグランジュの発表する1795年よりも以前に、この方法を初めて発見したのは1779年のエドワード・ワーリングである。ラグランジュの結果はレオンハルト・オイラーが1783年に発表したより複雑な形の公式の簡単な帰結となるものであった
ラグランジュ補間多項式は数値積分法の一種ニュートン–コーツ法でも用いられ、また有限体上で計算されたラグランジュ補間多項式は暗号理論におけるでも用いられる。
ラグランジュ補間は巨大振幅に関するルンゲ現象の影響を受けやすい。また評価点 の変更に関して補間の計算を全くやり直す必要があるから、そのような目的では変更が容易にできるニュートン補間がしばしば用いられる。
定義.
 個のデータ点集合 formula_1 はどの二つの も同じでないとする。これらのデータのラグランジュ型の補間多項式とは、ラグランジュ基底多項式 formula_2 の線型結合 formula_3 を言う。
まず最初の仮定により formula_4 であるから、この式は常に矛盾なく定まる。formula_5 かつ formula_6 となるような対を許さない理由は、必要な補間多項式 (formula_7) が存在しないからである（各引数 に対する値は一つでなければならない）。他方、formula_8 もそれら二点が実際には単一の点となる。
任意の に対して、基底多項式 は分子に を因子として持つから、 のとき積全体も零となる。他方、 のときは明らかに が成り立つ。すなわち、 formula_9 である。ここに右辺はクロネッカーのデルタ。したがって各点 において formula_10 となり は所期の函数の補間を与えるものとなる。
注意.
ラグランジュ型の補間では、多項式補間の線型性と補間多項式の一意性があるため、証明や理論的な議論では都合がよい。この一意性はヴァンデルモンド行列の可逆性（同じことだがヴァンデルモンド行列式が至る所消えないこと）からも導けることである。
しかしながら、構成からわかる通り、節点 を変更するごとに、ラグランジュ基底多項式をすべて計算し直さなければならない。そこで実用上（あるいは計算上）の目的では、重心形のラグランジュ補間（後述）やニュートン補間を用いるほうが良い。
等間隔に取った節点に関するラグランジュ補間やその他の補間は、真の函数の上下に振動する多項式を生じるものである。この振る舞いは節点の数を多くするにつれてルンゲ現象と呼ばれる発散に逢着しやすくなっていく。この問題は、補間に用いる点をに選ぶことで解消できる。
線型代数学的説明.
補間問題を解くことは、逆行列を計算する線型代数学の問題につながる。標準的な単項式基底を用いた補間多項式 formula_11 では、 を の係数 に関してヴァンデルモンド行列 formula_12 を逆に解かなければならない。対して、ラグランジュ基底を用いて formula_13 を作れば、この場合先ほどはヴァンデルモンド行列が現れた部分には単位行列 formula_14 が現れ、逆行列は単位行列自身であるから、ラグランジュ基底は自動的に逆に解かれていることになる。
この構成は中国の剰余定理と類似対応している（つまり、素数を法とする整数の剰余を調べる代わりに、一次式を法とする多項式の剰余を見ている）。
重心形.
ラグランジュ基底多項式を formula_15 を用いて、formula_16と書き直す。これは重心重み付け ("barycentric weight")を formula_17 と定めれば簡潔に formula_18 と書くことができる、これを重心ラグランジュ補間の「第一形」と呼ぶ。
この形の多項式補間を考えることの利点は、補間多項式 formula_19 を評価するときに、重み が事前に分かっていれば、 で計算できることである（ラグランジュ基底 を個別に計算するのは 掛かる）。もうひとつ重心形補間の利点として、新しい節点 の追加も各 を formula_20 で割って、新しい を計算するだけで容易にできる点が挙げられる。
さらに第一形を単純化することもできて、まず定数函数 の重心補間 formula_21 を計算してから を で割れば、得られる
誤差項.
与えられた函数 を、節点 において次数 の多項式で補完するとき、誤差 formula_23 は formula_24 と表せる。ただし、formula_25 は差商である. またこの誤差項を複素領域における周回積分 formula_26 と書くこともできる。
この誤差項によって、誤差の範囲を formula_27 と見積もることができる。