ラグランジュ多項式

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

座標ペアのデータセットが与えられた場合${\displaystyle \textstyle (x_{j},y_{j})}$⁠、その⁠${\displaystyle \textstyle x_{j}}$⁠はノードと呼ばれ、 ⁠${\displaystyle \textstyle y_{j}}$は値と呼ばれます。ラグランジュ多項式${\displaystyle L(x)}$データを補間する各ノードの値は、${\displaystyle \textstyle L(x_{j})=y_{j}}$⁠ . もしあるなら⁠${\displaystyle k+1}$データペアの場合、ラグランジュ多項式の次数は です。${\displaystyle \leq k}$⁠ .

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

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

等間隔の節点の場合、ラグランジュ補間はルンゲ現象による大きな振動の影響を受けやすい。

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

$${\displaystyle {\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}}}$$

分子に注目してください${\displaystyle \textstyle \prod _{m\neq j}(x-x_{m})}$⁠持っている⁠${\displaystyle k}$ノードの根${\displaystyle \textstyle \{x_{m}\}_{m\neq j}}$分母は${\displaystyle \textstyle \prod _{m\neq j}(x_{j}-x_{m})}$結果として得られる多項式を次のようにスケーリングします。${\displaystyle \textstyle \ell _{j}(x_{j})=1}$⁠ .

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

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

各基底多項式の次数は⁠${\displaystyle k}$⁠、したがって合計は⁠${\displaystyle L(x)}$学位を持っている${\displaystyle \leq k}$⁠、そしてデータを補間するのは、${\displaystyle \textstyle L(x_{m})=\sum _{j=0}^{k}y_{j}\ell _{j}(x_{m})=\sum _{j=0}^{k}y_{j}\delta _{mj}=y_{m}}$⁠ .

補間多項式は一意である。証明：ある多項式を仮定する。${\displaystyle M(x)}$程度の​${\displaystyle \leq k}$データを補間します。次に差分${\displaystyle M(x)-L(x)}$はゼロです${\displaystyle k+1}$異なるノード${\textstyle \{x_{0},x_{1},\ldots ,x_{k}\}}$しかし、次数 の唯一の多項式は${\displaystyle \leq k}$⁠より多く⁠${\displaystyle k}$⁠根は定数ゼロ関数なので、${\displaystyle M(x)-L(x)=0}$⁠、または⁠${\displaystyle M(x)=L(x)}$⁠ .

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

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

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

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

重みが${\displaystyle \textstyle w_{j}}$は事前に計算されているため、必要なのは だけです。${\displaystyle {\mathcal {O}}(k)}$操作と比較して${\displaystyle \textstyle {\mathcal {O}}(k^{2})}$各ラグランジュ基底多項式を評価するために${\displaystyle \textstyle \ell _{j}(x)}$個別に。（ビッグオー記法を参照。）

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

任意のxに対して、${\textstyle \sum _{j=0}^{k}\ell _{j}(x)=1}$定数関数${\textstyle g(x)=1}$次数が一意な多項式です${\displaystyle \leq k}$データの補間${\textstyle \{(x_{0},1),(x_{1},1),\ldots ,(x_{k},1)\}}$。したがって、{ を割ることによって、重心公式をさらに簡略化できます。${\displaystyle L(x)=L(x)/g(x)}$:

$${\displaystyle {\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番目の形式は、計算コストと精度において利点があります。${\displaystyle \ell (x)}$;分母の各項を計算する作業${\displaystyle w_{j}/(x-x_{j})}$コンピューティング分野では既に実施されている${\displaystyle {\bigl (}w_{j}/(x-x_{j}){\bigr )}y_{j}}$そのため、分母の合計を計算するコストは${\textstyle k}$加算演算;評価ポイントの場合${\textstyle x}$ノードの1つに近い${\textstyle x_{j}}$壊滅的なキャンセルは通常、価値にとって問題となるだろう${\textstyle (x-x_{j})}$しかし、この量は分子と分母の両方に現れるが、両者が相殺されるため、最終結果の相対的な精度は良好となる。

この式を用いて評価する${\displaystyle L(x)}$ノードの1つで${\displaystyle x_{j}}$不確定な結果になる${\displaystyle \infty y_{j}/\infty }$; コンピュータ実装では、このような結果を${\displaystyle L(x_{j})=y_{j}.}$

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

$${\displaystyle \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}}$ヴァンデルモンド行列を逆行列にする必要があります${\displaystyle (x_{i})^{j}}$解決する${\displaystyle L(x_{i})=y_{i}}$係数について${\displaystyle m_{j}}$の${\displaystyle L(x)}$より良い基底であるラグランジュ基底を選択することにより、${\textstyle L(x)=\sum _{j=0}^{k}l_{j}(x)y_{j}}$すると、単に単位行列が得られるだけです。${\displaystyle \delta _{ij}}$これは自身の逆行列です。ラグランジュ基底は、ヴァンデルモンド行列の類似行列を自動的に逆行列化します。

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

さらに、次数が大きい場合は、高速フーリエ変換を用いて補間された多項式の係数を求めることができる。

補間したい${\displaystyle f(x)=x^{2}}$ドメイン全体にわたって${\displaystyle 1\leq x\leq 3}$3つのノードにおいて${\displaystyle \{1,\,2,\,3\}}$:

$${\displaystyle {\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}}}$$

節点多項式${\displaystyle \ell }$は $${\displaystyle \ell (x)=(x-1)(x-2)(x-3)=x^{3}-6x^{2}+11x-6.}$$

重心重みは $${\displaystyle {\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}}}$$

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

$${\displaystyle {\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}}}$$

ラグランジュ補間多項式は次のとおりです。 $${\displaystyle {\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}}}$$

（第二の）重心形式では、

$${\displaystyle 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の多項式でノードで補間する場合${\displaystyle x_{0},\dots ,x_{k}}$残りは${\displaystyle R(x)=f(x)-L(x)}$これは次のように表現できます^{[ 6 ]}

$${\displaystyle {\begin{aligned}R(x)&=f[x_{0},\ldots ,x_{k},x]\ell (x)\\[1ex]&=\ell (x){\frac {f^{(k+1)}(\xi )}{(k+1)!}},&x_{0}<\xi <x_{k},\end{aligned}}}$$

どこ${\displaystyle f[x_{0},\ldots ,x_{k},x]}$は分割差分を表す表記です。あるいは、剰余は複素領域における経路積分として次のように表すことができます。

$${\displaystyle {\begin{aligned}R(x)&={\frac {\ell (x)}{2\pi i}}\int _{C}{\frac {f(t)}{(t-x)(t-x_{0})\cdots (t-x_{k})}}dt\\[1ex]&={\frac {\ell (x)}{2\pi i}}\int _{C}{\frac {f(t)}{(t-x)\ell (t)}}dt.\end{aligned}}}$$

残りは次のように束ねることができます

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

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

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

（上記の§ 定義を参照）各ラグランジュ基底多項式は

$${\displaystyle {\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}}}$$

一次導関数は積の法則を用いて求めることができる。

$${\displaystyle {\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階微分は

$${\displaystyle {\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階微分は

$${\displaystyle {\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}}}$$

そして、高階微分についても同様である。

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

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

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