ラグランジュ補間法
ラグランジュ補間法（Lagrange Interpolation）とは、与えられたいくつかの点をすべて通るような多項式（補間多項式）を求める手法です。ラグランジュ補間法を用いると、連立方程式を解くことなく、基底多項式を組み合わせて補間多項式を求めることができます。
$n+1$ 個の異なるデータ点 $(x_0, y_0), (x_1, y_1), \dots, (x_n, y_n)$ が与えられたとき、これらの点すべてを通る高々 $n$ 次の多項式 $P(x)$ を求めることを目指します。
$$y_i=P(x_i) \quad (i = 0, 1, \dots, n) -①$$
ラグランジュ補間法の特徴は以下になります。
- 解の一意性：
$n+1$ 個の点を通る $n$ 次以下の多項式はただ１つ存在します。 - 計算コスト：
点が追加された際、すべての基底多項式を再計算する必要があるため、動的にデータが増える場合は重心ラグランジュ補間法やニュートン補間法が用いられます。 - ルンゲ現象：
点の数が多くなると、区間の端付近で多項式が振動する現象が生じることがあります。
基底多項式
基底多項式（ラグランジュ基底）$\ell_k(x)$ は、各点 $x_k$ に対して、次のような特性を持つ高々 $n$ 次の多項式として定義されます。
$$\ell_k(x_i) = \begin{cases} 1 & (i = k) \\ 0 & (i \neq k) \end{cases} -②$$
この条件を満たす多項式 $\ell_k(x)$ は、以下のように構成されます。
$$\ell_k(x) = \prod_{\substack{0 \le j \le n \\ j \neq k}} \frac{x-x_j}{x_k-x_j} -③$$$$=\frac{(x-x_0)(x-x_1) \cdots (x-x_{k-1})(x-x_{k+1}) \cdots (x-x_n)}{(x_k-x_0)(x_k-x_1) \cdots (x_k-x_{k-1})(x_k-x_{k+1}) \cdots (x_k-x_n)}$$
$x = x_i$ を代入すると、$\ell_i(x_i) = 1$ 、かつ、$\ell_k(x_i) = 0 \, (k \neq i)$ となるため、②が成り立ちます。
補間多項式
各基底多項式 $\ell_k(x)$ にそれぞれの $y_k$ を掛けて足し合わせることで、目的の補間多項式 $P(x)$ が得られます。
$$P(x) = \sum_{k=0}^{n} y_k \ell_k(x) = y_0 \ell_0(x) + y_1 \ell_1(x) + \dots + y_n \ell_n(x) -④$$
具体例
3つの点 $(1, 2), (2, 3), (3, 6)$ を通る２次多項式を求めます。
-
- $x_0 = 1, y_0 = 2$
- $x_1 = 2, y_1 = 3$
- $x_2 = 3, y_2 = 6$
③の基底多項式を計算すると、
$$\ell_0(x)=\frac{(x-2)(x-3)}{(1-2)(1-3)}=\frac{(x-2)(x-3)}{2}$$$$\ell_1(x)=\frac{(x-1)(x-3)}{(2-1)(2-3)}= -(x-1)(x-3)$$$$\ell_2(x) = \frac{(x-1)(x-2)}{(3-1)(3-2)} = \frac{(x-1)(x-2)}{2}$$
④の補間多項式は以下で得られます。
$$P(x) = 2 \cdot \ell_0(x)+3 \cdot \ell_1(x) + 6 \cdot \ell_2(x)=x^2-2x+3$$
重心ラグランジュ補間
重心ラグランジュ補間（Barycentric Lagrange Interpolation）は、従来のラグランジュ補間法の計算コストの高さなどの欠点を克服し、高速かつ数値的に安定して評価できるように修正した補間手法です。
重心ラグランジュ補間の特徴は以下になります。
- 高速な計算速度：
事前に重心重み $w_j$ を $O(n^2)$ で一度計算しておけば、任意の点 $x$ に対する $P(x)$ の評価は $O(n)$ の加減乗除で行えます。 - 数値的安定性：
第二種重心形式は分母と分子の項がバランスするため、丸め誤差の影響を受けにくく、ルンゲ現象を抑える節点と組み合わせることで、高次の補間多項式を桁落ちせず安定に求められます。 - 節点の追加が容：
新しい節点 $x_{n+1}$ が追加された場合、$O(n)$ の計算量で対応可能です。
基底多項式
基底多項式 $\ell_k(x)$ は、以下で定義されます。
$$\ell_j(x) = l(x) \frac{w_j}{x-x_j} -⑤$$
ここで、積多項式 $l(x)$ と重心重み $w_j$ は以下で定義します。
$$l(x) = \prod_{k=0}^{n} (x-x_k) -⑥$$$$\frac{1}{w_j}=\prod_{\substack{k=0 \\ k \neq j}}^{n} (x_j-x_k) -⑦$$
第一種重心形式
これを $P(x)$ の式に代入したものが第一種重心形式（First form of the barycentric formula）です。
$$P(x)=l(x) \sum_{j=0}^{n} \frac{w_j}{x-x_j} y_j -⑧$$
第二種重心形式
定数関数 $P(x) = 1$ （すべての $y_j = 1$）に対して第一種形式を適用すると、次の等式が得られます。
$$1=l(x)\sum_{j=0}^{n}\frac{w_j}{x-x_j}$$
この等式で⑧を割ることで、$l(x)$ の項を消去できます。これが第二種重心形式（Second form / True barycentric formula）です。なお、 $x = x_j$ のときはゼロ除算を防ぐため、$P(x_j) = y_j$ とします。
$$P(x) = \frac{\sum_{j=0}^{n} \dfrac{w_j}{x-x_j} y_j}{\sum_{j=0}^{n} \dfrac{w_j}{x-x_j}} -⑨$$
補間法の比較
両者の使い分けとして、高次多項式を数値的に安定して評価したい場合、重心ラグランジュ補間が標準的です。
| 項目 | ラグランジュ補間 | 重心ラグランジュ補間（第二種） |
| 補間式の構造 | 直感的・明示的 | 分数形式（重心重みによる正規化） |
| 点追加のコスト | $O(n^2)$（全再計算） | $O(n)$（重みの更新） |
| 任意点 $x$ での評価コスト | $O(n^2)$ | $O(n)$ |
| 数値的安定性 | 桁落ちに弱い | 高い（高次でも桁落ちしない） |
