ラグランジュ多項式

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

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

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

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

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

インデックス について、すべて異なるノードの集合がある場合、それらのノードの次数の多項式のラグランジュ基底は、 および の場合に値を取る、それぞれ 次数の多項式の集合です。クロネッカーのデルタを使用すると、これは次のように記述できます。各基底多項式は、次の積で明示的に記述できます。 ${\textstyle k+1}$${\displaystyle \{x_{0},x_{1},\ldots ,x_{k}\}}$${\displaystyle x_{j}\neq x_{m}}$${\displaystyle 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}.}$

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

分子は節点に根を持ち、分母は結果として得られる多項式をスケーリングするので、${\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.}$

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

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

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

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

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

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

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

任意の定数関数はデータを補間する次数の唯一の多項式であるため、重心式を次のようにさらに簡略化することができます。${\textstyle 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)\colon }$

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

この式をノードの1つで評価すると不確定な結果となる。コンピュータ実装では、このような結果を次のように置き換える必要がある。${\displaystyle L(x)}$${\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}}$

この構成は、中国の剰余定理に似ています。素数を法とする整数の剰余をチェックする代わりに、多項式を線形で割ったときの剰余をチェックします。

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

3つのノードでドメインを補間したいとします。${\displaystyle f(x)=x^{2}}$${\displaystyle 1\leq x\leq 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)&=1\cdot {\frac {x-2}{1-2}}\cdot {\frac {x-3}{1-3}}+4\cdot {\frac {x-1}{2-1}}\cdot {\frac {x-3}{2-3}}+9\cdot {\frac {x-1}{3-1}}\cdot {\frac {x-2}{3-2}}\\[6mu]&=x^{2}.\end{aligned}}}$

（第2）重心形式では、

${\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次の多項式でノードに補間すると、次のように表される剰余が得られる^[6]。${\displaystyle x_{0},...,x_{k}}$${\displaystyle R(x)=f(x)-L(x)}$

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

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

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

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

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

明らかに、はノードでゼロです。点 で を求めるには、新しい関数 を定義して を選択します。は、与えられた に対して決定する必要がある定数です。 が(すべてのノードと で)ゼロになるように選択します(端点を含む)。 が回微分可能であると仮定すると、とは多項式であり、したがって、 は無限に微分可能であるため、は回微分可能です。ロールの定理により、 はゼロを持ち、はゼロを持ちます...には1 つのゼロがあり、 とします。 を明示的に書きます。 ${\displaystyle R(x)}$${\displaystyle R(x)}$${\displaystyle x_{p}}$${\displaystyle 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})}$${\displaystyle C}$${\displaystyle x_{p}}$${\displaystyle C}$${\displaystyle F(x)}$${\displaystyle k+2}$${\displaystyle x_{p}}$${\displaystyle x_{0}}$${\displaystyle x_{k}}$${\displaystyle f(x)}$${\displaystyle k+1}$${\displaystyle L(x)}$${\displaystyle {\tilde {R}}(x)}$${\displaystyle F(x)}$${\displaystyle k+1}$${\displaystyle F^{(1)}(x)}$${\displaystyle k+1}$${\displaystyle F^{(2)}(x)}$${\displaystyle k}$${\displaystyle F^{(k+1)}}$${\displaystyle \xi ,\,x_{0}<\xi <x_{k}}$${\displaystyle F^{(k+1)}(\xi )}$

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

${\displaystyle L^{(k+1)}=0,{\tilde {R}}^{(k+1)}=C\cdot (k+1)!}$（ の最高累乗はであるため）${\displaystyle x}$${\displaystyle {\tilde {R}}(x)}$${\displaystyle k+1}$

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

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

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

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

ラグランジュ補間多項式の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}}}$$

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

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

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

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

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

• ネヴィルのアルゴリズム
• 補間多項式のニュートン形式
• バーンスタイン多項式
• カールソンの定理
• ルベーグ定数
• チェブフンシステム
• ニュートン級数表
• フロベニウス共変
• シルベスターの公式
• 差分係数
• エルミート補間

Wikibookのアルゴリズム実装には、多項式補間に関するページがあります。

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