ラグランジュ補間

提供: miniwiki
2018/8/19/ (日) 17:39時点におけるAdmin (トーク | 投稿記録)による版 (1版 をインポートしました)
(差分) ← 古い版 | 最新版 (差分) | 新しい版 → (差分)
移動先:案内、検索
ファイル:Lagrange polynomial.svg
この図が示すのは、四点 ((−9, 5), (−4, 2), (−1, −2), (7, 9)) に対する三次補間多項式 L(x) (黒破線) が基底多項式 y0ℓ0(x), y1ℓ1(x), y2ℓ2(x), y3ℓ3(x) のスケールを変えたものの和であること。この補間多項式は与えられた四つの制御点を通り、各スケールされた基底多項式は対応する制御点を通り、それ以外の三つの制御点に対応する x のところでは 0 になっている。

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

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

ラグランジュ補間多項式は数値積分法の一種ニュートン–コーツ法でも用いられ、また有限体上で計算されたラグランジュ補間多項式は暗号理論におけるシャミアの秘密分散法（English版）でも用いられる。

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

定義

k + 1 個のデータ点集合 [math](x_0, y_0),\ldots,(x_j, y_j),\ldots,(x_k, y_k)[/math] はどの二つの xj も同じでないとする。これらのデータのラグランジュ型の補間多項式とは、ラグランジュ基底多項式 [math] \ell_j(x) := \prod_{0\le m\le k\atop m\neq 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)} [/math] の線型結合 [math]L(x) := \sum_{j=0}^{k} y_j \ell_j(x)[/math] を言う。

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

任意の i ≠ j に対して、基底多項式 ℓj(x) は分子に (x − xi) を因子として持つから、x = xi のとき積全体も零となる。他方、i = j のときは明らかに ℓi(xi) = 1 が成り立つ。すなわち、 [math]\ell_j(x_i) = \delta_{ij}[/math] である。ここに右辺はクロネッカーのデルタ。したがって各点 xi において [math]L(x_i)=y_i+0+0+\dotsb +0=y_i[/math] となり L は所期の函数の補間を与えるものとなる。

注意

ファイル:Runge's phenomenon in Lagrange polynomials.svg
ラグランジュ多項式の集合に対する補間の発散の例

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

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

等間隔に取った節点に関するラグランジュ補間やその他の補間は、真の函数の上下に振動する多項式を生じるものである。この振る舞いは節点の数を多くするにつれてルンゲ現象と呼ばれる発散に逢着しやすくなっていく。この問題は、補間に用いる点をチェビシェフ節点（English版）に選ぶことで解消できる[2]。

線型代数学的説明

補間問題を解くことは、逆行列を計算する線型代数学の問題につながる。標準的な単項式基底を用いた補間多項式 [math]L(x) = \sum_{j=0}^k x^j m_j[/math] では、L(xi) = yi を L の係数 mj に関してヴァンデルモンド行列 [math]((x_i)^j)[/math] を逆に解かなければならない。対して、ラグランジュ基底を用いて [math]L(x) = \sum_{j=0}^k l_j(x) y_j[/math] を作れば、この場合先ほどはヴァンデルモンド行列が現れた部分には単位行列 [math](\delta_{ij})[/math] が現れ、逆行列は単位行列自身であるから、ラグランジュ基底は自動的に逆に解かれていることになる。

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

重心形

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

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

さらに第一形を単純化することもできて、まず定数函数 g(x) ≡ 1 の重心補間 [math]g(x) = \ell(x) \sum_{j=0}^k \frac{w_j}{x-x_j}[/math] を計算してから L を g で割れば、得られる [math]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}}[/math] は与えられた節点における補間性を失わない。この補間多項式を重心補間多項式の「第二形」あるいは「真の形」という。真の重心補間多項式は、L の各節点における評価に際してラグランジュ基底 ℓ を評価しなくてよいという点で有利である。

誤差項

与えられた函数 f を、節点 x0, …, xn において次数 n の多項式で補完するとき、誤差 [math]R(x) = f(x) - L(x)[/math] は [math] R(x) = f[x_0,\ldots,x_n,x] \ell(x) = \ell(x) \frac{f^{n+1}(\xi)}{(n+1)!}, \quad \quad x_0 \lt \xi \lt x_n,[/math] と表せる[4]。ただし、[math]f[x_0,\ldots,x_n,x][/math] は差商である[注釈 1]. またこの誤差項を複素領域における周回積分 [math] R(z) = \frac{\ell(z)}{2\pi i} \int_C \frac{f(t)}{(t-z)(t-z_0) \cdots (t-z_n)} dt = \frac{\ell(z)}{2\pi i} \int_C \frac{f(t)}{(t-z)\ell(t)} dt [/math] と書くこともできる。

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

脚注

  1. ↑ 差分商とも呼ぶ。近い概念として、有限差分の商 Δy/Δx を差分商あるいは差商と呼ぶ場合もあるので混同してはならない。

参考文献

  1. ↑ Meijering, Erik (2002), “A chronology of interpolation: from ancient astronomy to modern signal and image processing”, Proceedings of the IEEE 90 (3): 319–342, doi:10.1109/5.993400 .
  2. ↑ Quarteroni, Alfio; Saleri, Fausto (2003), Scientific Computing with MATLAB, Texts in computational science and engineering, 2, Springer, p. 66, ISBN 9783540443636, https://books.google.com/books?id=fE1W5jsU4zoC&pg=PA66 .
  3. ↑ Jean-Paul Berrut & Lloyd N. Trefethen (2004). “Barycentric Lagrange Interpolation”. SIAM Review 46 (3): 501–517. doi:10.1137/S0036144502417715. 
  4. ↑ Abramowitz and Stegun, "Handbook of Mathematical Functions," p.878

関連項目

外部リンク



「http:///http:///mymemo.xyz/mymemo.xyz/wiki/index.php?title=ラグランジュ補間&oldid=115256」から取得