ラグランジュ多項式

数値解析において、ラグランジュ補間多項式は、与えられたデータセットを補間する唯一の最低次多項式です。

座標ペアのデータセットが与えられ、はノード、は値と呼ばれます。ラグランジュ多項式は次数を持ち、対応するノードの各値は、 $(x_{j},y_{j})$ $0\leq j\leq k,$ $x_{j}$ $y_{j}$ $L(x)$ ${\textstyle \leq k}$ $L(x_{j})=y_{j}.$

この方法は1795年に発表したジョゼフ＝ルイ・ラグランジュにちなんで名付けられましたが、^{[1] 、 1779年に}エドワード・ウェアリングによって初めて発見されました。^{[2]また、これは}レオンハルト・オイラーが1783年に発表した公式から容易に導かれる結果でもあります。^[3]

ラグランジュ多項式の用途としては、数値積分のニュートン・コーツ法、暗号におけるシャミアの秘密分散法、符号理論におけるリード・ソロモン誤り訂正法などがあります。

等間隔のノードの場合、ラグランジュ補間はルンゲの大振動現象の影響を受けやすくなります。

意味

インデックスについて、すべて異なるノードの集合が与えられた場合、それらのノードの次数の多項式のラグランジュ基底は、およびのときに値を取る、それぞれ次数の多項式の集合です。クロネッカーのデルタを用いると、これは次のように書けます。各基底多項式は、次の積で明示的に記述できます。 ${\textstyle k+1}$ $\{x_{0},x_{1},\ldots ,x_{k}\}$ $x_{j}\neq x_{m}$ $j\neq m$ ${\textstyle \leq k}$ ${\textstyle \{\ell _{0}(x),\ell _{1}(x),\ldots ,\ell _{k}(x)\}}$ ${\textstyle k}$ ${\textstyle \ell _{j}(x_{m})=0}$ ${\textstyle m\neq j}$ ${\textstyle \ell _{j}(x_{j})=1}$ ${\textstyle \ell _{j}(x_{m})=\delta _{jm}.}$

${\begin{aligned}\ell _{j}(x)&={\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})}}\\[8mu]&=\prod _{\begin{smallmatrix}0\leq m\leq k\\m\neq j\end{smallmatrix}}{\frac {x-x_{m}}{x_{j}-x_{m}}}{\vphantom {\Bigg |}}.\end{aligned}}$

分子は節点に根を持ち、分母は結果として得られる多項式をスケールするので、 ${\textstyle \prod _{m\neq j}(x-x_{m})}$ ${\textstyle k}$ ${\textstyle \{x_{m}\}_{m\neq j}}$ ${\textstyle \prod _{m\neq j}(x_{j}-x_{m})}$ ${\textstyle \ell _{j}(x_{j})=1.}$

対応する値 を通るこれらのノードのラグランジュ補間多項式は線形結合です。 $\{y_{0},y_{1},\ldots ,y_{k}\}$

$L(x)=\sum _{j=0}^{k}y_{j}\ell _{j}(x).$

各基底多項式は次数なので、和は次数となり、データの補間は次のように行われます。 ${\textstyle k}$ ${\textstyle L(x)}$ ${\textstyle \leq k}$ ${\textstyle L(x_{m})=\sum _{j=0}^{k}y_{j}\ell _{j}(x_{m})=\sum _{j=0}^{k}y_{j}\delta _{mj}=y_{m}.}$

補間多項式は一意である。証明：次数の多項式がデータを補間すると仮定する。すると、異なるノードにおける差はゼロとなる。しかし、次数以上の根を持つ多項式は定数ゼロ関数のみであるため、または ${\textstyle M(x)}$ ${\textstyle \leq k}$ ${\textstyle M(x)-L(x)}$ ${\textstyle k+1}$ ${\textstyle \{x_{0},x_{1},\ldots ,x_{k}\}.}$ ${\textstyle \leq k}$ ${\textstyle k}$ ${\textstyle M(x)-L(x)=0,}$ ${\textstyle M(x)=L(x).}$

重心形式

各ラグランジュ基底多項式は、すべての基底多項式に共通する関数、ノード固有の定数（重心重みと呼ばれる）、およびからへの変位を表す部分の3つの部分の積として書き直すことができる。^[4] ${\textstyle \ell _{j}(x)}$ ${\textstyle \ell (x)=\prod _{m}(x-x_{m})}$ ${\textstyle w_{j}=\prod _{m\neq j}(x_{j}-x_{m})^{-1}}$ ${\textstyle x_{j}}$ ${\textstyle x}$

$\ell _{j}(x)=\ell (x){\dfrac {w_{j}}{x-x_{j}}}$

和から因数分解することで、ラグランジュ多項式をいわゆる第一重心形式で書くことができます。 ${\textstyle \ell (x)}$

L(x)=\ell (x)\sum _{j=0}^{k}{\frac {w_{j}}{x-x_{j}}}y_{j}.

重みが事前に計算されている場合は、各ラグランジュ基底多項式を個別に評価する場合と比較した操作のみが必要です。 $w_{j}$ ${\mathcal {O}}(k)$ ${\mathcal {O}}(k^{2})$ $\ell _{j}(x)$

重心補間式は、、をそれぞれで割り、上記のように新しいを構築することで、新しいノードを組み込むように簡単に更新できます。 $x_{k+1}$ $w_{j}$ $j=0\dots k$ $(x_{j}-x_{k+1})$ $w_{k+1}$

任意の定数関数はデータを補間する次数の唯一の多項式であるため、重心式をさらに簡略化して、 ${\textstyle x,}$ ${\textstyle \sum _{j=0}^{k}\ell _{j}(x)=1}$ ${\textstyle g(x)=1}$ $\leq k$ ${\textstyle \{(x_{0},1),(x_{1},1),\ldots ,(x_{k},1)\}.}$ $L(x)=L(x)/g(x)\colon$

{\begin{aligned}L(x)&=\ell (x)\sum _{j=0}^{k}{\frac {w_{j}}{x-x_{j}}}y_{j}{\Bigg /}\ell (x)\sum _{j=0}^{k}{\frac {w_{j}}{x-x_{j}}}\\[10mu]&=\sum _{j=0}^{k}{\frac {w_{j}}{x-x_{j}}}y_{j}{\Bigg /}\sum _{j=0}^{k}{\frac {w_{j}}{x-x_{j}}}.\end{aligned}}

これは、重心補間式の2 番目の形式または真の形式と呼ばれます。

この 2 番目の形式には、計算コストと精度の面で利点があります。の評価を回避できます。分母の各項を計算する作業は計算で既に行われているため、分母の合計を計算するには加算演算のみが必要です。評価ポイントがノードの 1 つに近い場合、通常は値の壊滅的なキャンセルが問題になりますが、この量は分子と分母の両方に表示され、2 つがキャンセルされるため、最終結果の相対精度は良好になります。 $\ell (x)$ $w_{j}/(x-x_{j})$ ${\bigl (}w_{j}/(x-x_{j}){\bigr )}y_{j}$ ${\textstyle k}$ ${\textstyle x}$ ${\textstyle x_{j}}$ ${\textstyle (x-x_{j})}$

この式をノードの1つで評価すると不確定な結果となる。コンピュータ実装では、このような結果を次のように置き換える必要がある。 $L(x)$ $x_{j}$ $\infty y_{j}/\infty$ $L(x_{j})=y_{j}.$

各ラグランジュ基底多項式は重心形式でも表すことができます。

\ell _{j}(x)={\frac {w_{j}}{x-x_{j}}}{\Bigg /}\sum _{m=0}^{k}{\frac {w_{m}}{x-x_{m}}}.

線形代数からの視点

補間問題を解くことは、線形代数における行列の逆行列を求める問題につながります。補間多項式の標準的な単項式基底を用いると、の係数を求めるにはヴァンデルモンド行列を逆行列化する必要があります。より適切な基底であるラグランジュ基底を選択すれば、単に単位行列が得られます。これはそれ自体の逆行列です。ラグランジュ基底は、ヴァンデルモンド行列の類似物を自動的に逆行列化します。 ${\textstyle L(x)=\sum _{j=0}^{k}x^{j}m_{j}}$ $(x_{i})^{j}$ $L(x_{i})=y_{i}$ $m_{j}$ $L(x)$ ${\textstyle L(x)=\sum _{j=0}^{k}l_{j}(x)y_{j}}$ $\delta _{ij}$

この構成は中国式剰余定理に類似しています。素数を法とする整数の剰余を調べるのではなく、多項式を線型で割ったときの剰余を調べます。

さらに、次数が大きい場合は、高速フーリエ変換を使用して補間多項式の係数を解くことができます。

例

3つのノードでドメインを補間したいとします。 $f(x)=x^{2}$ $1\leq x\leq 3$ $\{1,\,2,\,3\}$

{\begin{aligned}x_{0}&=1,&&&y_{0}=f(x_{0})&=1,\\[3mu]x_{1}&=2,&&&y_{1}=f(x_{1})&=4,\\[3mu]x_{2}&=3,&&&y_{2}=f(x_{2})&=9.\end{aligned}}

ノード多項式は $\ell$

\ell (x)=(x-1)(x-2)(x-3)=x^{3}-6x^{2}+11x-6.

重心重みは

{\begin{aligned}w_{0}&=(1-2)^{-1}(1-3)^{-1}={\tfrac {1}{2}},\\[3mu]w_{1}&=(2-1)^{-1}(2-3)^{-1}=-1,\\[3mu]w_{2}&=(3-1)^{-1}(3-2)^{-1}={\tfrac {1}{2}}.\end{aligned}}

ラグランジュ基底多項式は

{\begin{aligned}\ell _{0}(x)&={\frac {x-2}{1-2}}\cdot {\frac {x-3}{1-3}}={\tfrac {1}{2}}x^{2}-{\tfrac {5}{2}}x+3,\\[5mu]\ell _{1}(x)&={\frac {x-1}{2-1}}\cdot {\frac {x-3}{2-3}}=-x^{2}+4x-3,\\[5mu]\ell _{2}(x)&={\frac {x-1}{3-1}}\cdot {\frac {x-2}{3-2}}={\tfrac {1}{2}}x^{2}-{\tfrac {3}{2}}x+1.\end{aligned}}

ラグランジュ補間多項式は次のとおりです。

{\begin{aligned}L(x)&=y_{0}\cdot \ell _{0}(x)+y_{1}\cdot \ell _{1}(x)+y_{2}\cdot \ell _{2}(x)=x^{2}.\end{aligned}}

（第2）重心形式では、

L(x)={\frac {\displaystyle \sum _{j=0}^{2}{\frac {w_{j}}{x-x_{j}}}y_{j}}{\displaystyle \sum _{j=0}^{2}{\frac {w_{j}}{x-x_{j}}}}}={\frac {\displaystyle {\frac {\tfrac {1}{2}}{x-1}}+{\frac {-4}{x-2}}+{\frac {\tfrac {9}{2}}{x-3}}}{\displaystyle {\frac {\tfrac {1}{2}}{x-1}}+{\frac {-1}{x-2}}+{\frac {\tfrac {1}{2}}{x-3}}}}.

注記

補間多項式のラグランジュ形は、多項式補間の線形性と補間多項式の一意性を示す。そのため、証明や理論的議論において好んで用いられる。また、ヴァンデルモンド行列の逆行列式が零でないことによる、ヴァンデルモンド行列の一意性からも、この一意性が分かる。

しかし、構築からわかるように、ノードx _{k が}変化するたびに、すべてのラグランジュ基底多項式を再計算する必要があります。実用的（または計算的）な補間多項式のより適切な形式は、ラグランジュ補間の重心形式（下記参照）またはニュートン多項式です。

上記の例のように、等間隔の点におけるラグランジュ補間やその他の補間法では、真の関数の上下に振動する多項式が得られます。この挙動は点の数が増えるにつれて大きくなり、ルンゲ現象として知られる発散を引き起こします。この問題は、チェビシェフノードに補間点を選択することで解消できます。^[5]

ラグランジュ基底多項式は数値積分においてニュートン・コーツの公式を導くために使用することができます。

ラグランジュ補間式の剰余

与えられた関数fを $k$ 次の多項式でノードに補間すると、次のように表される剰余が得られる^[6]。 $x_{0},...,x_{k}$ $R(x)=f(x)-L(x)$

R(x)=f[x_{0},\ldots ,x_{k},x]\ell (x)=\ell (x){\frac {f^{(k+1)}(\xi )}{(k+1)!}},\quad \quad x_{0}<\xi <x_{k},

ここでは差分商の表記である。あるいは、剰余は複素領域における周回積分として次のように表すこともできる。 $f[x_{0},\ldots ,x_{k},x]$

R(x)={\frac {\ell (x)}{2\pi i}}\int _{C}{\frac {f(t)}{(t-x)(t-x_{0})\cdots (t-x_{k})}}dt={\frac {\ell (x)}{2\pi i}}\int _{C}{\frac {f(t)}{(t-x)\ell (t)}}dt.

残りは次のように制限される。

|R(x)|\leq {\frac {(x_{k}-x_{0})^{k+1}}{(k+1)!}}\max _{x_{0}\leq \xi \leq x_{k}}|f^{(k+1)}(\xi )|.

導出

明らかに、はノードで零です。点を求めるには、新しい関数を定義し、を選びます。は、与えられたに対して決定する必要がある定数です。が（すべてのノードとで）零点を持つように選びます（端点を含む）。が回微分可能であると仮定すると、とは多項式であり、したがっては無限微分可能であるため、は回微分可能です。ロールの定理により、は零点を持ち、は零点を持ち…は1つの零点を持ちます（とします）。を明示的に書き表すと： $R(x)$ $R(x)$ $x_{p}$ $F(x)=R(x)-{\tilde {R}}(x)=f(x)-L(x)-{\tilde {R}}(x)$ ${\textstyle {\tilde {R}}(x)=C\cdot \prod _{i=0}^{k}(x-x_{i})}$ $C$ $x_{p}$ $C$ $F(x)$ $k+2$ $x_{p}$ $x_{0}$ $x_{k}$ $f(x)$ $k+1$ $L(x)$ ${\tilde {R}}(x)$ $F(x)$ $k+1$ $F^{(1)}(x)$ $k+1$ $F^{(2)}(x)$ $k$ $F^{(k+1)}$ $\xi ,\,x_{0}<\xi <x_{k}$ $F^{(k+1)}(\xi )$

F^{(k+1)}(\xi )=f^{(k+1)}(\xi )-L^{(k+1)}(\xi )-{\tilde {R}}^{(k+1)}(\xi )

L^{(k+1)}=0,{\tilde {R}}^{(k+1)}=C\cdot (k+1)!

（の最高べき乗はであるため）

x

{\tilde {R}}(x)

k+1

0=f^{(k+1)}(\xi )-C\cdot (k+1)!

この式は次のように変形できる^[7]

C={\frac {f^{(k+1)}(\xi )}{(k+1)!}}

私たちは $F(x_{p})=0$ $R(x_{p})={\tilde {R}}(x_{p})={\frac {f^{k+1}(\xi )}{(k+1)!}}\prod _{i=0}^{k}(x_{p}-x_{i})$

デリバティブ

ラグランジュ補間多項式のd次導関数は $、$ 基底多項式の導関数を使って次のように表すことができます。

L^{(d)}(x):=\sum _{j=0}^{k}y_{j}\ell _{j}^{(d)}(x).

それぞれのラグランジュ基底多項式は、

${\begin{aligned}\ell _{j}(x)&=\prod _{\begin{smallmatrix}m=0\\m\neq j\end{smallmatrix}}^{k}{\frac {x-x_{m}}{x_{j}-x_{m}}}.\end{aligned}}$

1次導関数は積の法則を使って求めることができます。

{\begin{aligned}\ell _{j}'(x)&=\sum _{\begin{smallmatrix}i=0\\i\not =j\end{smallmatrix}}^{k}{\Biggl [}{\frac {1}{x_{j}-x_{i}}}\prod _{\begin{smallmatrix}m=0\\m\not =(i,j)\end{smallmatrix}}^{k}{\frac {x-x_{m}}{x_{j}-x_{m}}}{\Biggr ]}\\[5mu]&=\ell _{j}(x)\sum _{\begin{smallmatrix}i=0\\i\not =j\end{smallmatrix}}^{k}{\frac {1}{x-x_{i}}}.\end{aligned}}

2次導関数は

{\begin{aligned}\ell _{j}''(x)&=\sum _{\begin{smallmatrix}i=0\\i\neq j\end{smallmatrix}}^{k}{\frac {1}{x_{j}-x_{i}}}{\Biggl [}\sum _{\begin{smallmatrix}m=0\\m\neq (i,j)\end{smallmatrix}}^{k}{\Biggl (}{\frac {1}{x_{j}-x_{m}}}\prod _{\begin{smallmatrix}n=0\\n\neq (i,j,m)\end{smallmatrix}}^{k}{\frac {x-x_{n}}{x_{j}-x_{n}}}{\Biggr )}{\Biggr ]}\\[10mu]&=\ell _{j}(x)\sum _{0\leq i<m\leq k}{\frac {2}{(x-x_{i})(x-x_{m})}}\\[10mu]&=\ell _{j}(x){\Biggl [}{\Biggl (}\sum _{\begin{smallmatrix}i=0\\i\not =j\end{smallmatrix}}^{k}{\frac {1}{x-x_{i}}}{\Biggr )}^{2}-\sum _{\begin{smallmatrix}i=0\\i\not =j\end{smallmatrix}}^{k}{\frac {1}{(x-x_{i})^{2}}}{\Biggr ]}.\end{aligned}}

3次導関数は

{\begin{aligned}\ell _{j}'''(x)&=\ell _{j}(x)\sum _{0\leq i<m<n\leq k}{\frac {3!}{(x-x_{i})(x-x_{m})(x-x_{n})}}\end{aligned}}

高次の導関数についても同様です。

これらの導関数の公式はすべて、ノードまたはその近傍では無効であることに注意してください。ラグランジュ多項式のすべての次数の導関数を、ノードを含む領域のすべての点で効率的に評価する方法は、ラグランジュ多項式をべき基底形式に変換してから導関数を評価することです。

有限体

ラグランジュ多項式は有限体上でも計算できます。これはシャミールの秘密分散法などの暗号学に応用されています。

参照

参考文献

^ ラグランジュ、ジョゼフ＝ルイ(1795)。「Leçon Cinquième. Sur l'usage des courbes dans la solution des problèmes」。Leçons Elémentaires sur les Mathématiques (フランス語)。パリ。Serret、Joseph-Alfred編に再掲載。（1877年）。ラグランジュ作品集。 Vol. 7. ゴーティエ・ヴィラール。 271–287ページ。「第5講義問題解決における曲線の利用について」として翻訳。初等数学講義。マコーマック、トーマス・J.訳（第2版）。オープンコート。1901年。127 ～ 149頁。
^ ウォーリング、エドワード(1779). 「補間に関する問題」.王立協会哲学論文集. 69 : 59–67 . doi :10.1098/rstl.1779.0008.
^ マイヤーリング、エリック (2002). 「補間の年表：古代天文学から現代の信号・画像処理まで」(PDF) . Proceedings of the IEEE . 90 (3): 319– 342. doi :10.1109/5.993400.
^ Berrut, Jean-Paul ; Trefethen, Lloyd N. (2004). 「重心ラグランジュ補間」(PDF) . SIAM Review . 46 (3): 501– 517. Bibcode :2004SIAMR..46..501B. doi : 10.1137/S0036144502417715 .
^ Quarteroni, Alfio ; Saleri, Fausto (2003). MATLABによる科学計算. 計算科学と工学のテキスト. 第2巻. Springer. p. 66. ISBN 978-3-540-44363-6。。
^ アブラモウィッツ、ミルトン、ステガン、アイリーン・アン編 (1983) [1964年6月]。「第25章式25.2.3」。『数式、グラフ、数表付き数学関数ハンドブック』。応用数学シリーズ。第55巻（1972年12月発行の第10刷に訂正を加えた第9刷、初版）。ワシントンD.C.、ニューヨーク：米国商務省国立標準局、ドーバー出版。878頁。ISBN 978-0-486-61272-0 LCCN 64-60036. MR 0167642. LCCN 65-12253 .
^ 「補間」（PDF） pp. 12– 15。2017年2月15日時点のオリジナル（PDF）からのアーカイブ。

外部リンク

「ラグランジュ補間公式」、数学百科事典、EMSプレス、2001 [1994]
ALGLIB には C++ / C# / VBA / Pascal の実装があります。
GSLにはC言語で多項式補間コードがある
SOには、アルゴリズムを実証し、この記事の最初の画像を再現するMATLABの例があります。
ラグランジュ補間法 — ノート、PPT、Mathcad、Mathematica、MATLAB、Maple
www.math-linux.com のラグランジュ補間多項式
ワイスタイン、エリック・W.「ラグランジュ補間多項式」。MathWorld。
双三次ラグランジュ補間の Excel ワークシート関数
Pythonにおけるラグランジュ多項式

[1] ラグランジュ、ジョゼフ＝ルイ(1795)。「Leçon Cinquième. Sur l'usage des courbes dans la solution des problèmes」。Leçons Elémentaires sur les Mathématiques (フランス語)。パリ。Serret、Joseph-Alfred編に再掲載。（1877年）。ラグランジュ作品集。 Vol. 7. ゴーティエ・ヴィラール。 271–287ページ。「第5講義問題解決における曲線の利用について」として翻訳。初等数学講義。マコーマック、トーマス・J.訳（第2版）。オープンコート。1901年。127 ～ 149頁。

[2] ウォーリング、エドワード(1779). 「補間に関する問題」.王立協会哲学論文集. 69 : 59–67 . doi :10.1098/rstl.1779.0008.

[3] マイヤーリング、エリック (2002). 「補間の年表：古代天文学から現代の信号・画像処理まで」(PDF) . Proceedings of the IEEE . 90 (3): 319– 342. doi :10.1109/5.993400.

[4] Berrut, Jean-Paul ; Trefethen, Lloyd N. (2004). 「重心ラグランジュ補間」(PDF) . SIAM Review . 46 (3): 501– 517. Bibcode :2004SIAMR..46..501B. doi : 10.1137/S0036144502417715 .

[5] Quarteroni, Alfio ; Saleri, Fausto (2003). MATLABによる科学計算. 計算科学と工学のテキスト. 第2巻. Springer. p. 66. ISBN 978-3-540-44363-6。。

[6] アブラモウィッツ、ミルトン、ステガン、アイリーン・アン編 (1983) [1964年6月]。「第25章式25.2.3」。『数式、グラフ、数表付き数学関数ハンドブック』。応用数学シリーズ。第55巻（1972年12月発行の第10刷に訂正を加えた第9刷、初版）。ワシントンD.C.、ニューヨーク：米国商務省国立標準局、ドーバー出版。878頁。ISBN 978-0-486-61272-0 LCCN 64-60036. MR 0167642. LCCN 65-12253 .

[7] 「補間」（PDF） pp. 12– 15。2017年2月15日時点のオリジナル（PDF）からのアーカイブ。