レメズアルゴリズム

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

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

レメズアルゴリズムは関数から始まります${\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}$)

未知のもののために${\displaystyle b_{0},b_{1}...b_{n}}$そしてE。​

• 使用する${\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によるレビューがある。^{[ 3 ]}

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

ステップ1：${\displaystyle x_{0},x_{1},...x_{n+1}}$n + 2 個の線形方程式系を解く

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

未知のもののために${\displaystyle b_{0},b_{1},...b_{n}}$そしてE。​

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

標準n次補間関数を計算する${\displaystyle p_{1}(x)}$に${\displaystyle f(x)}$最初のn + 1 ノードと標準的なn次補間 ${\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})}$算術演算。

多項式${\displaystyle p_{2}(x)}$i番目のゼロは${\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}}$。

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

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

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

${\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の多項式は存在しない。実際、そのような多項式が存在するとすれば、それを と呼ぶ。${\displaystyle {\tilde {p}}(x)}$すると、その差は ${\displaystyle p(x)-{\tilde {p}}(x)=(p(x)-f(x))-({\tilde {p}}(x)-f(x))}$n + 2 ノードでも正負の状態が維持される${\displaystyle x_{i}}$したがって、少なくともn + 1 個の零点を持つことになりますが、これは次数nの多項式では不可能です。したがって、このE は次数nの多項式で達成できる最小誤差の下限となります。

ステップ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領域では、現在のノード${\displaystyle x_{i}}$ローカル最大化器に置き換えられます${\displaystyle {\bar {x}}_{i}}$そして各N領域において${\displaystyle x_{i}}$ローカルミニマイザーに置き換えられます。(${\displaystyle {\bar {x}}_{0}}$Aでは、${\displaystyle {\bar {x}}_{i}}$近く${\displaystyle x_{i}}$、 そして${\displaystyle {\bar {x}}_{n+1}}$Bにおいて。）ここでは高い精度は必要なく、2 つの二次近似を用いた標準的な直線探索で 十分である。（^{[ 10 ]}を参照）

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

さらに、${\displaystyle \max\{|z_{i}|\}}$これは、可能な限り最良の誤差の上限値として非常に役立ちます。

ステップ4：${\displaystyle \min \,\{|z_{i}|\}}$そして${\displaystyle \max \,\{|z_{i}|\}}$最良の近似誤差の下限と上限として、信頼できる停止基準が得られます。${\displaystyle \max\{|z_{i}|\}-\min\{|z_{i}|\}}$十分に小さいか、あるいはそれ以上減少しない。これらの範囲は進捗状況を示している。

文献には、このアルゴリズムのいくつかの修正例が報告されている。^{[ 11 ]}これらには以下が含まれる。

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

• アダマールの補題–スペースなしで短い説明を表示する定理ページ 
• ローランシリーズ– 負のべき乗を持つべき乗シリーズ 
• パデ近似– 与えられた次数を持つ有理関数による関数の「最良」近似 
• ニュートン級数– 微分の離散的類似物リダイレクト先の簡単な説明を表示するページ 
• 近似理論― 不正確な数学的計算で許容範囲内の近似値を得るための理論 
• 関数近似– 任意の関数を性質の良い関数で近似すること 

• ミニマックス近似とレメズアルゴリズム（ Boost Math Toolsドキュメントの背景章、C++での実装へのリンク付き）
• DSP入門（ 2014年4月23日にWayback Machineにアーカイブ済み）
• ロナルド・M・アーツ;ボンド、チャールズ。メンデルソーン、フィル & ワイスタイン、エリック W. 「レメズ アルゴリズム」。マスワールド。