Algorithm to approximate functions
1934年に エフゲニー・ヤコブレヴィチ・レメズ によって発表された レメ ズアルゴリズム または レメズ交換アルゴリズムは、関数の単純な近似、具体的には、 チェビシェフ空間における関数による、 一様ノルム L∞ の 意味で最適な近似を求めるために使用される反復アルゴリズムです 。 [1] レメスアルゴリズム または レメアルゴリズム と呼ばれることもあります 。 [2]
チェビシェフ空間の典型的な例は、 区間 C [ a , b ]上の 実 連続関数の 空間 における n 位 チェビシェフ多項式 の部分空間である。与えられた部分空間内で最良近似多項式とは、多項式と関数の 差の絶対値の 最大値を最小化する多項式と定義される。この場合、解の形は 等振動定理 によって厳密に規定される 。
手順 Remezアルゴリズムは 、近似する関数と近似区間内の サンプル点 の集合 （通常はチェビシェフ多項式の極値を区間に線形写像したもの）から始まります。手順は以下のとおりです f {\displaystyle f} X {\displaystyle X} n + 2 {\displaystyle n+2} x 1 , x 2 , . . . , x n + 2 {\displaystyle x_{1},x_{2},...,x_{n+2}}
b 0 + b 1 x i + . . . + b n x i n + ( − 1 ) i E = f ( x i ) {\displaystyle b_{0}+b_{1}x_{i}+...+b_{n}x_{i}^{n}+(-1)^{i}E=f(x_{i})} （どこ ）、 i = 1 , 2 , . . . n + 2 {\displaystyle i=1,2,...n+2} 未知数 および E については、 b 0 , b 1 . . . b n {\displaystyle b_{0},b_{1}...b_{n}} を係数として使用して 、多項式を形成します 。 b i {\displaystyle b_{i}} P n {\displaystyle P_{n}} 局所最大誤差の点の 集合を見つけます 。 M {\displaystyle M} | P n ( x ) − f ( x ) | {\displaystyle |P_{n}(x)-f(x)|} 各 における誤差 の大きさが等しく、符号が交互に変わる場合、 は ミニマックス近似多項式です。そうでない場合は、 を に置き換え 、上記の手順を繰り返します。 m ∈ M {\displaystyle m\in M} P n {\displaystyle P_{n}} X {\displaystyle X} M {\displaystyle M} 結果は、最良近似多項式または ミニマックス近似アルゴリズム と呼ばれます。
Remezアルゴリズムの実装に関する技術的なレビューはW. Fraserによって行われています。 [3]
初期化の選択 チェビシェフ ノードは、 多項式補間 理論における役割から、初期近似としてよく選ばれます。関数 f の最適化問題を ラグランジュ補間 L n ( f )で初期化する場合、この初期近似は次の式で有界であることが示されます
‖ f − L n ( f ) ‖ ∞ ≤ ( 1 + ‖ L n ‖ ∞ ) inf p ∈ P n ‖ f − p ‖ {\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 1 、…、 t n + 1 ）
の ラグランジュ補間演算子 L n のノルムまたは ルベーグ定数は
‖ L n ‖ ∞ = Λ ¯ n ( T ) = max − 1 ≤ x ≤ 1 λ n ( T ; x ) , {\displaystyle \lVert L_{n}\rVert _{\infty }={\overline {\Lambda }}_{n}(T)=\max _{-1\leq x\leq 1}\lambda _{n}(T;x),} T はチェビシェフ多項式の零点であり、ルベーグ関数は
λ n ( T ; x ) = ∑ j = 1 n + 1 | l j ( x ) | , l j ( x ) = ∏ i ≠ j i = 1 n + 1 ( x − t i ) ( t j − t i ) . {\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・キルゴア [4] 、カール・デ・ブール、アラン・ピンカス [5] は、（通常の）多項式では明示的には知られていないものの、各 L n に対して一意の t i が存在することを証明した。同様に、、 およびノード選択の最適性は次のように表される。 Λ _ n ( T ) = min − 1 ≤ x ≤ 1 λ n ( T ; x ) {\displaystyle {\underline {\Lambda }}_{n}(T)=\min _{-1\leq x\leq 1}\lambda _{n}(T;x)} Λ ¯ n − Λ _ n ≥ 0. {\displaystyle {\overline {\Lambda }}_{n}-{\underline {\Lambda }}_{n}\geq 0.}
チェビシェフノードの場合、最適ではないが解析的に明示的な選択が提供され、漸近的な挙動は [6]として知られている。
Λ ¯ n ( T ) = 2 π log ( n + 1 ) + 2 π ( γ + log 8 π ) + α n + 1 {\displaystyle {\overline {\Lambda }}_{n}(T)={\frac {2}{\pi }}\log(n+1)+{\frac {2}{\pi }}\left(\gamma +\log {\frac {8}{\pi }}\right)+\alpha _{n+1}} （ γ は オイラー・マスケロニ定数 ）
0 < α n < π 72 n 2 {\displaystyle 0<\alpha _{n}<{\frac {\pi }{72n^{2}}}} について n ≥ 1 , {\displaystyle n\geq 1,} および上限 [7]
Λ ¯ n ( T ) ≤ 2 π log ( n + 1 ) + 1 {\displaystyle {\overline {\Lambda }}_{n}(T)\leq {\frac {2}{\pi }}\log(n+1)+1} レフ・ブルトマン [8] は 、 および が展開チェビシェフ多項式の零点であるとして 、 の境界を得ました n ≥ 3 {\displaystyle n\geq 3} T ^ {\displaystyle {\hat {T}}}
Λ ¯ n ( T ^ ) − Λ _ n ( T ^ ) < Λ ¯ 3 − 1 6 cot π 8 + π 64 1 sin 2 ( 3 π / 16 ) − 2 π ( γ − log π ) ≈ 0.201. {\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.} リュディガー・ギュントナー [9] は、より正確な推定値から n ≥ 40 {\displaystyle n\geq 40}
Λ ¯ n ( T ^ ) − Λ _ n ( T ^ ) < 0.0196. {\displaystyle {\overline {\Lambda }}_{n}({\hat {T}})-{\underline {\Lambda }}_{n}({\hat {T}})<0.0196.}
詳細な議論 このセクションでは、上記で概説した手順についてさらに詳しく説明します。このセクションでは、インデックス i は 0 から n +1
までです
ステップ1: が与えられて、 n +2方程式 の線形連立方程式を解く x 0 , x 1 , . . . x n + 1 {\displaystyle x_{0},x_{1},...x_{n+1}}
b 0 + b 1 x i + . . . + b n x i n + ( − 1 ) i E = f ( x i ) {\displaystyle b_{0}+b_{1}x_{i}+...+b_{n}x_{i}^{n}+(-1)^{i}E=f(x_{i})} （どこ ）、 i = 0 , 1 , . . . n + 1 {\displaystyle i=0,1,...n+1} 未知数 および E については、 b 0 , b 1 , . . . b n {\displaystyle b_{0},b_{1},...b_{n}} この式は、ノードが厳密に増加または減少する順序で 並んで いる場合にのみ意味を成す ことは明らかです 。この場合、この線形方程式は唯一の解を持ちます。（よく知られているように、すべての線形方程式が解を持つわけではありません。）また、この解は算術演算のみで得られます が、ライブラリの標準的なソルバーでは 演算が必要になります。簡単な証明を以下に示します。 ( − 1 ) i E {\displaystyle (-1)^{i}E} x 0 , . . . , x n + 1 {\displaystyle x_{0},...,x_{n+1}} O ( n 2 ) {\displaystyle O(n^{2})} O ( n 3 ) {\displaystyle O(n^{3})}
最初の n +1個のノードにおける n 次標準 補間関数 と、 縦座標における n 次標準補間関数
を計算する。 p 1 ( x ) {\displaystyle p_{1}(x)} f ( x ) {\displaystyle f(x)} p 2 ( x ) {\displaystyle p_{2}(x)} ( − 1 ) i {\displaystyle (-1)^{i}}
p 1 ( x i ) = f ( x i ) , p 2 ( x i ) = ( − 1 ) i , i = 0 , . . . , n . {\displaystyle p_{1}(x_{i})=f(x_{i}),p_{2}(x_{i})=(-1)^{i},i=0,...,n.} この目的のために、ニュートンの補間式を、 順序 と算術演算の 差商 とともに 毎回使用します 。 0 , . . . , n {\displaystyle 0,...,n} O ( n 2 ) {\displaystyle O(n^{2})}
多項式の i 番目の零点は との間に ある ため、 との間には他に零点は存在しません 。 と は 同じ符号 を持ちます 。 p 2 ( x ) {\displaystyle p_{2}(x)} x i − 1 {\displaystyle x_{i-1}} x i , i = 1 , . . . , n {\displaystyle x_{i},\ i=1,...,n} x n {\displaystyle x_{n}} x n + 1 {\displaystyle x_{n+1}} p 2 ( x n ) {\displaystyle p_{2}(x_{n})} p 2 ( x n + 1 ) {\displaystyle p_{2}(x_{n+1})} ( − 1 ) n {\displaystyle (-1)^{n}}
線形結合
も n 次の多項式であり 、 p ( x ) := p 1 ( x ) − p 2 ( x ) ⋅ E {\displaystyle p(x):=p_{1}(x)-p_{2}(x)\!\cdot \!E}
p ( x i ) = p 1 ( x i ) − p 2 ( x i ) ⋅ E = f ( x i ) − ( − 1 ) i E , i = 0 , … , 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.} これは、 E の任意の選択 に対して、およびに対して上記の式と同じである。i = n +1 に対して同じ式は次のようになる。 i = 0 , . . . , n {\displaystyle i=0,...,n}
p ( x n + 1 ) = p 1 ( x n + 1 ) − p 2 ( x n + 1 ) ⋅ E = f ( x n + 1 ) − ( − 1 ) n + 1 E {\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 の 定義 は次のようになります。 E := p 1 ( x n + 1 ) − f ( x n + 1 ) p 2 ( x n + 1 ) + ( − 1 ) n . {\displaystyle E\ :=\ {\frac {p_{1}(x_{n+1})-f(x_{n+1})}{p_{2}(x_{n+1})+(-1)^{n}}}.} 前述のように、分母の 2 つの項は同じ符号 ( E) を持ち、 常に明確に定義されます。 p ( x ) ≡ b 0 + b 1 x + … + b n x n {\displaystyle p(x)\equiv b_{0}+b_{1}x+\ldots +b_{n}x^{n}}
与えられたn +2個のノードにおける誤差は 、正と負の順になる。
p ( x i ) − f ( x i ) = − ( − 1 ) i E , i = 0 , . . . , n + 1. {\displaystyle p(x_{i})-f(x_{i})\ =\ -(-1)^{i}E,\ \ i=0,...,n\!+\!1.} 等 振動定理は 、この条件下では誤差が E 未満の n 次多項式は存在しないことを述べています。実際、そのような多項式（ と呼ぶ）が存在するとすれば、 n +2 個のノードにおける 差は 依然として正または負となり 、したがって少なくとも n +1 個の零点を持つことになりますが、これは n 次多項式ではあり得ません 。したがって、この Eは n 次 多項式で達成可能な最小誤差の下限値となります 。 p ~ ( x ) {\displaystyle {\tilde {p}}(x)} p ( x ) − p ~ ( x ) = ( p ( x ) − f ( x ) ) − ( p ~ ( x ) − f ( x ) ) {\displaystyle p(x)-{\tilde {p}}(x)=(p(x)-f(x))-({\tilde {p}}(x)-f(x))} x i {\displaystyle x_{i}}
ステップ 2 では 、表記が から に変更され ます 。 b 0 + b 1 x + . . . + b n x n {\displaystyle b_{0}+b_{1}x+...+b_{n}x^{n}} p ( x ) {\displaystyle p(x)}
ステップ 3 では、入力ノード とそのエラーが 次のように改善されます。 x 0 , . . . , x n + 1 {\displaystyle x_{0},...,x_{n+1}} ± E {\displaystyle \pm E}
各P領域では、現在のノードが 局所最大化に置き換えられ 、各N領域では 局所最小化に置き換えられます。（A、近傍、Bを除く ） ここ で は 高い 精度 は 必要ないため、標準的な 直線探索 と2次 曲線の近似 で 十分です。（ [10] を参照） x i {\displaystyle x_{i}} x ¯ i {\displaystyle {\bar {x}}_{i}} x i {\displaystyle x_{i}} x ¯ 0 {\displaystyle {\bar {x}}_{0}} x ¯ i {\displaystyle {\bar {x}}_{i}} x i {\displaystyle x_{i}} x ¯ n + 1 {\displaystyle {\bar {x}}_{n+1}}
とする 。各振幅は E 以上である。 ラ・ヴァレー＝プーサン の定理とその証明は、 n 次多項式で可能な最良の誤差の新しい下限として に も 適用される 。 z i := p ( x ¯ i ) − f ( x ¯ i ) {\displaystyle z_{i}:=p({\bar {x}}_{i})-f({\bar {x}}_{i})} | z i | {\displaystyle |z_{i}|} z 0 , . . . , z n + 1 {\displaystyle z_{0},...,z_{n+1}} min { | z i | } ≥ E {\displaystyle \min\{|z_{i}|\}\geq E}
さらに、 可能な限り最良のエラーの上限値として役立ちます。 max { | z i | } {\displaystyle \max\{|z_{i}|\}}
ステップ4： および を 最良の 近似誤差 の 下限および上限とすることで 、信頼性の高い停止基準が得られます。 が十分に小さくなるか、減少しなくなるまで、ステップを繰り返します 。これらの境界は、進行状況を示します。 min { | z i | } {\displaystyle \min \,\{|z_{i}|\}} max { | z i | } {\displaystyle \max \,\{|z_{i}|\}} max { | z i | } − min { | z i | } {\displaystyle \max\{|z_{i}|\}-\min\{|z_{i}|\}}
バリエーション アルゴリズムのいくつかの修正が文献に示されています。 [11] これらには以下が含まれます
複数のサンプルポイントを、近くにある最大絶対差の位置に置き換えます。 [ 引用が必要 ] 1回の反復で、すべてのサンプルポイントを、符号が交互に変わる最大差の位置に置き換えます。 [12] 相対誤差を使用して近似値と関数の差を測定します。特に、近似値が浮動小数点 演算 を使用するコンピュータ上で関数を計算するために使用される場合。 ゼロ誤差点制約を含む。 [12] フレイザー・ハート変種は、最良の有理チェビシェフ近似を決定するために使用される。 [13]
参照 アダマールの補題 – 定理 Pages displaying short descriptions with no spaces ローラン級数 – 負のべき乗を持つべき級数 パデ近似 – 与えられた次数の有理関数による関数の「最良の」近似 ニュートン級数 – 微分の離散的類似 Pages displaying short descriptions of redirect targets 近似理論 – 不正確な数学的計算を許容できる程度に近づける理論 関数近似 – 任意の関数を振る舞いの良い関数で近似する
参考文献 ^ レメス、E. Ya. （1934年）。 「高度な近似のポリノームの決定」。 通信社会数学。ハリコフ 。 10：41 — (1934)。 「近似を収束させる一連の手順を決定し、近似のポリノームを作成する」。 完了レンド。アカド。科学。 （フランス語で）。 198 : 2063-5 . — (1934)。 「チェビシェフの近似多ノームの効果を計算する」。 完了レンド。アカド。科学。 （フランス語で）。 199 : 337–340 . ^ Chiang, Yi-Ling F. (1988年11月). 「改良Remesアルゴリズム」 . SIAM Journal on Scientific and Statistical Computing . 9 (6): 1058– 1072. doi :10.1137/0909072. ISSN 0196-5204. ^ Fraser, W. (1965). 「単一独立変数関数のミニマックスおよび準ミニマックス多項式近似値の計算方法の概説」 J. ACM . 12 (3): 295– 314. doi : 10.1145/321281.321282 . S2CID 2736060. ^ キルゴア, TA (1978). 「最小チェビシェフノルムによるラグランジュ補間投影の特徴づけ」. 近似理論誌 . 24 (4): 273– 288. doi :10.1016/0021-9045(78)90013-8. ^ de Boor, C.; Pinkus, A. (1978). 「多項式補間における最適ノードに関するベルンシュタインとエルデシュの予想の証明」 近似理論ジャーナル . 24 (4): 289– 303. doi : 10.1016/0021-9045(78)90014-X . ^ Luttmann, FW; Rivlin, TJ (1965). 「多項式補間理論におけるいくつかの数値実験」. IBM J. Res. Dev . 9 (3): 187– 191. doi :10.1147/rd.93.0187. ^ Rivlin, TJ (1974). 「多項式補間におけるルベーグ定数」. Garnir, HG; Unni, KR; Williamson, JH (編). 関数解析とその応用 . 数学講義ノート. 第399巻. Springer. pp. 422– 437. doi :10.1007/BFb0063594. ISBN 978-3-540-37827-3 。 ^ Brutman, L. (1978). 「多項式補間のためのルベーグ関数について」. SIAM J. Numer. Anal . 15 (4): 694– 704. Bibcode :1978SJNA...15..694B. doi :10.1137/0715046 ^ Günttner, R. (1980). 「ルベーグ定数の評価」. SIAM J. Numer. Anal . 17 (4): 512– 520. Bibcode :1980SJNA...17..512G. doi :10.1137/0717043. ^ Luenberger, DG; Ye, Y. (2008). 「基本降下法」. 線形計画法と非線形計画法 . 国際オペレーションズ・リサーチ＆マネジメント・サイエンスシリーズ. 第116巻（第3版）. Springer. pp. 215– 262. doi :10.1007/978-0-387-74503-9_8. ISBN 978-0-387-74503-9 。 ^ エギディ、ナダニエラ；ファトーネ、ロレッラ；ミシチ、ルチアーノ（2020年）、セルゲイエフ、ヤロスラフ・D；クヴァソフ、ドミトリ・E（編）、 「最良多項式近似のための新しいレメズ型アルゴリズム」 、 数値計算：理論とアルゴリズム 、第11973巻、Cham：Springer、pp. 56– 69、 doi ：10.1007/978-3-030-39081-5_7、 ISBN 978-3-030-39080-8 , S2CID 211159177 ^ ab Temes, GC; Barcilon, V.; Marshall, FC (1973). 「帯域制限システムの最適化」 Proceedings of the IEEE . 61 (2): 196– 234. Bibcode :1973IEEEP..61..196T. doi :10.1109/PROC.1973.9004. ISSN 0018-9219 ^ Dunham, Charles B. (1975). 「有理チェビシェフ近似に対するフレイザー・ハート法の収束」 . 計算数学 . 29 (132): 1078– 1082. doi : 10.1090/S0025-5718-1975-0388732-9 . ISSN 0025-5718.
外部リンク 
