レメズアルゴリズム

1934年にエフゲニー・ヤコブレヴィッチ・レメズによって発表されたレメズアルゴリズムまたはレメズ交換アルゴリズムは、関数の単純な近似値、具体的にはチェビシェフ空間内の関数による近似値のうち、均一ノルムL∞_の意味で最適なものを見つけるために使用される反復アルゴリズムです。^[1]レメスアルゴリズムまたはレメアルゴリズムと呼ばれることもあります。^[要出典]

チェビシェフ空間の典型的な例は、区間C [ a , b ]上の実連続関数の空間におけるn次チェビシェフ多項式の部分空間です。与えられた部分空間内で最も近似度の高い多項式は、多項式と関数の最大絶対差を最小化するものとして定義されます。この場合、解の形は等振動定理によって明確に定義されます。

Remez アルゴリズムは、近似する関数と近似区間内のサンプル ポイントのセット(通常は、区間に線形にマッピングされたチェビシェフ多項式の極値) から始まります。手順は次のとおりです。 ${\displaystyle f}$${\displaystyle X}$${\displaystyle n+2}$${\displaystyle x_{1},x_{2},...,x_{n+2}}$

• 線形方程式を解く

${\displaystyle b_{0}+b_{1}x_{i}+...+b_{n}x_{i}^{n}+(-1)^{i}E=f(x_{i})}$（どこ）、${\displaystyle i=1,2,...n+2}$

未知数およびEの場合。${\displaystyle b_{0},b_{1}...b_{n}}$

• を係数として使用して多項式を形成します。${\displaystyle b_{i}}$${\displaystyle P_{n}}$
• 局所最大誤差の点の集合を見つけます。${\displaystyle M}$${\displaystyle |P_{n}(x)-f(x)|}$
• 各 における誤差の大きさが等しく、符号が交互になっている場合、 はミニマックス近似多項式です。 そうでない場合は、を に置き換えて、上記の手順を繰り返します。${\displaystyle m\in M}$${\displaystyle P_{n}}$${\displaystyle X}$${\displaystyle M}$

結果は、最良近似多項式またはミニマックス近似アルゴリズムと呼ばれます。

Remezアルゴリズムの実装に関する技術的なレビューはW. Fraserによって提供されています。^[2]

チェビシェフノードは、多項式補間理論における役割のため、初期近似値としてよく選ばれる。関数fの最適化問題をラグランジュ補間関数L _n ( f )で初期化する場合、この初期近似値は次の式で制限されることがわかる。

${\displaystyle \lVert f-L_{n}(f)\rVert _{\infty }\leq (1+\lVert L_{n}\rVert _{\infty })\inf _{p\in P_{n}}\lVert f-p\rVert }$

ノード（t ₁、...、t _{n  + 1}） のラグランジュ補間演算子L _nのノルムまたはルベーグ定数は

${\displaystyle \lVert L_{n}\rVert _{\infty }={\overline {\Lambda }}_{n}(T)=\max _{-1\leq x\leq 1}\lambda _{n}(T;x),}$

Tはチェビシェフ多項式の零点であり、ルベーグ関数は

${\displaystyle \lambda _{n}(T;x)=\sum _{j=1}^{n+1}\left|l_{j}(x)\right|,\quad l_{j}(x)=\prod _{\stackrel {i=1}{i\neq j}}^{n+1}{\frac {(x-t_{i})}{(t_{j}-t_{i})}}.}$

セオドア・A・キルゴア^[3]、カール・デ・ブール、アラン・ピンカス^[4]は、（通常の）多項式では明示的には知られていないが、各L _nに対して一意のt _iが存在することを証明した。同様に、、およびノー​​ドの選択の最適性は次のように表される。${\displaystyle {\underline {\Lambda }}_{n}(T)=\min _{-1\leq x\leq 1}\lambda _{n}(T;x)}$${\displaystyle {\overline {\Lambda }}_{n}-{\underline {\Lambda }}_{n}\geq 0.}$

チェビシェフノードは、最適ではないが解析的に明示的な選択を提供し、漸近的な振る舞いは次のように知られている^[5]

${\displaystyle {\overline {\Lambda }}_{n}(T)={\frac {2}{\pi }}\log(n+1)+{\frac {2}{\pi }}\left(\gamma +\log {\frac {8}{\pi }}\right)+\alpha _{n+1}}$

（γはオイラー・マスケロニ定数）

${\displaystyle 0<\alpha _{n}<{\frac {\pi }{72n^{2}}}}$のために${\displaystyle n\geq 1,}$

上限^[6]

${\displaystyle {\overline {\Lambda }}_{n}(T)\leq {\frac {2}{\pi }}\log(n+1)+1}$

レフ・ブルトマン^[7]は、およびが展開されたチェビシェフ多項式の零点であるとして 、の境界を得た。${\displaystyle n\geq 3}$${\displaystyle {\hat {T}}}$

${\displaystyle {\overline {\Lambda }}_{n}({\hat {T}})-{\underline {\Lambda }}_{n}({\hat {T}})<{\overline {\Lambda }}_{3}-{\frac {1}{6}}\cot {\frac {\pi }{8}}+{\frac {\pi }{64}}{\frac {1}{\sin ^{2}(3\pi /16)}}-{\frac {2}{\pi }}(\gamma -\log \pi )\approx 0.201.}$

リュディガー・ギュントナー^[8]は、より正確な推定値から${\displaystyle n\geq 40}$

${\displaystyle {\overline {\Lambda }}_{n}({\hat {T}})-{\underline {\Lambda }}_{n}({\hat {T}})<0.0196.}$

このセクションでは、上で概説した手順についてさらに詳しく説明します。このセクションでは、インデックスi は0 からn +1 までです。

ステップ1:が与えられたとき、 n +2方程式 の線形連立方程式を解く${\displaystyle x_{0},x_{1},...x_{n+1}}$

${\displaystyle b_{0}+b_{1}x_{i}+...+b_{n}x_{i}^{n}+(-1)^{i}E=f(x_{i})}$（どこ）、${\displaystyle i=0,1,...n+1}$

未知数およびEの場合。${\displaystyle b_{0},b_{1},...b_{n}}$

この方程式が意味をなすのは、ノードが厳密に増加または厳密に減少する順序になっている場合のみであることは明らかです。この場合、この線形システムには一意の解があります。(よく知られているように、すべての線形システムに解があるわけではありません。) また、ライブラリの標準ソルバーでは演算が必要になりますが、この解は算術演算だけで取得できます。簡単な証明は次のとおりです。 ${\displaystyle (-1)^{i}E}$${\displaystyle x_{0},...,x_{n+1}}$${\displaystyle O(n^{2})}$${\displaystyle O(n^{3})}$

最初のn +1個のノードにおける標準n次補間値と、縦座標における標準n次補間値 を計算する。${\displaystyle p_{1}(x)}$${\displaystyle f(x)}$${\displaystyle p_{2}(x)}$${\displaystyle (-1)^{i}}$

${\displaystyle p_{1}(x_{i})=f(x_{i}),p_{2}(x_{i})=(-1)^{i},i=0,...,n.}$

このため、ニュートンの補間公式を、順序の差商と算術演算 とともに毎回使用します。${\displaystyle 0,...,n}$${\displaystyle O(n^{2})}$

多項式のi番目の零点はと の間にあり、したがって との間にはそれ以上零点は存在しません。と は同じ符号 を持ちます。 ${\displaystyle p_{2}(x)}$${\displaystyle x_{i-1}}$${\displaystyle x_{i},\ i=1,...,n}$${\displaystyle x_{n}}$${\displaystyle x_{n+1}}$${\displaystyle p_{2}(x_{n})}$${\displaystyle p_{2}(x_{n+1})}$${\displaystyle (-1)^{n}}$

線形結合 もn次の多項式であり、 ${\displaystyle p(x):=p_{1}(x)-p_{2}(x)\!\cdot \!E}$

${\displaystyle p(x_{i})=p_{1}(x_{i})-p_{2}(x_{i})\!\cdot \!E\ =\ f(x_{i})-(-1)^{i}E,\ \ \ \ i=0,\ldots ,n.}$

これは、 Eの任意の選択に対して、および に対して上記の式と同じです。 i = n +1 に対して同じ式は次のようになります。${\displaystyle i=0,...,n}$

${\displaystyle p(x_{n+1})\ =\ p_{1}(x_{n+1})-p_{2}(x_{n+1})\!\cdot \!E\ =\ f(x_{n+1})-(-1)^{n+1}E}$特別な推論が必要です。変数Eについて解くと、 Eの定義は次のようになります。

${\displaystyle E\ :=\ {\frac {p_{1}(x_{n+1})-f(x_{n+1})}{p_{2}(x_{n+1})+(-1)^{n}}}.}$

前述のように、分母の 2 つの項は同じ符号 (E)を持ち、常に明確に定義されます。 ${\displaystyle p(x)\equiv b_{0}+b_{1}x+\ldots +b_{n}x^{n}}$

与えられたn +2個のノードにおける誤差は、正と負の順になる。

${\displaystyle p(x_{i})-f(x_{i})\ =\ -(-1)^{i}E,\ \ i=0,...,n\!+\!1.}$

ラ・ヴァレー・プーサンの定理によれば、この条件下では誤差がE未満のn 次多項式は存在しません。実際、そのような多項式が存在する場合、これを と呼ぶことにします。その場合、 n +2 個のノードで差は 依然として正/負になり、したがって少なくともn +1 個のゼロが存在しますが、これはn次多項式では不可能です。したがって、このE はn次多項式で達成できる最小誤差の下限です。 ${\displaystyle {\tilde {p}}(x)}$${\displaystyle p(x)-{\tilde {p}}(x)=(p(x)-f(x))-({\tilde {p}}(x)-f(x))}$${\displaystyle x_{i}}$

ステップ 2 では、表記が から に変更され ます。 ${\displaystyle b_{0}+b_{1}x+...+b_{n}x^{n}}$${\displaystyle p(x)}$

ステップ 3では、入力ノードとそのエラーが次のように改善されます。 ${\displaystyle x_{0},...,x_{n+1}}$${\displaystyle \pm E}$

各P領域では、現在のノードが局所最大化に置き換えられ、各N領域では局所最小化に置き換えられます。（A、近傍、Bを除く）ここでは高い精度は必要ないため、標準的な直線探索と2、3の二次曲線 近似で十分です。（^[9]を参照） ${\displaystyle x_{i}}$${\displaystyle {\bar {x}}_{i}}$${\displaystyle x_{i}}$${\displaystyle {\bar {x}}_{0}}$${\displaystyle {\bar {x}}_{i}}$${\displaystyle x_{i}}$${\displaystyle {\bar {x}}_{n+1}}$

とします。各振幅はE以上です。ラ・ヴァレー・プッサンの定理とその証明は にも適用され、はn次多項式で可能な最良の誤差の新しい下限値となります。 ${\displaystyle z_{i}:=p({\bar {x}}_{i})-f({\bar {x}}_{i})}$${\displaystyle |z_{i}|}$${\displaystyle z_{0},...,z_{n+1}}$${\displaystyle \min\{|z_{i}|\}\geq E}$

さらに、最良の可能性のあるエラーの明らかな上限として役立ちます。 ${\displaystyle \max\{|z_{i}|\}}$

ステップ 4:およびを最良の近似誤差の下限と上限とすると、信頼できる停止基準が得られます。つまり、が十分に小さくなるか、減少しなくなるまで、ステップを繰り返します。これらの境界は進行状況を示します。 ${\displaystyle \min \,\{|z_{i}|\}}$${\displaystyle \max \,\{|z_{i}|\}}$${\displaystyle \max\{|z_{i}|\}-\min\{|z_{i}|\}}$

アルゴリズムのいくつかの修正が文献に記載されている。^[10]これらには以下が含まれる。

• 複数のサンプルポイントを、近くの最大絶対差の位置に置き換えます。^{[引用が必要]}
• 1回の反復で全てのサンプルポイントを、符号が交互に変わる最大差の位置に置き換えます。^[11]
• 近似値と関数の差を測定するために相対誤差を使用する。特に、近似値が浮動小数点演算を使用するコンピュータ上で関数を計算するために使用される場合。
• ゼロ誤差点制約を含む。^[11]
• フレイザーハート変種は、最良の有理チェビシェフ近似を決定するために使用される。^[12]

• アダマールの補題
• ローラン級数 – 負のべき乗を持つべき級数
• パデ近似 – 与えられた次数の有理関数による関数の「最良の」近似
• ニュートン級数 – 微分の離散的類似Pages displaying short descriptions of redirect targets
• 近似理論 – 不正確な数学的計算を許容できる程度に近づける理論
• 関数近似 – 任意の関数を適切な関数で近似する

• ミニマックス近似と Remez アルゴリズム、Boost Math Tools ドキュメントの背景の章、C++ での実装へのリンク付き
• DSP入門
• ロナルド・M・アーツ;ボンド、チャールズ。メンデルソーン、フィル＆ワイスタイン、エリック・W.「レメズ・アルゴリズム」。マスワールド。