FEE方式
数学における高速合計法

数学において、FEE法（高速E関数評価法）は、特殊な形式の級数の高速和を求める手法である。この手法は1990年にエカテリーナ・カラツバ[1] [2]によって考案され、ジーゲルE関数、特に の高速計算を可能にすることからその名が付けられた。 e × {\displaystyle e^{x}}

「指数関数に似た」関数のクラスは、カール・ルートヴィヒ・ジーゲルによって「E関数」と名付けられました。[3]これらの関数には、超幾何関数、円筒関数、球面関数などの特殊関数が含まれます。

FEE を使用すると、次の定理を証明することができます。

定理：を初等超越関数、すなわち指数関数、 三角関数、初等代数関数、それらの重ね合わせ、それらの逆関数、あるいはそれらの逆関数の重ね合わせとします。すると、 y ＝ f （ × ） {\displaystyle y=f(x)}

s f （ n ） ＝ お （ M （ n ） ログ 2 ⁡ n ） 。 {\displaystyle s_{f}(n)=O(M(n)\log ^{2}n).\,}

ここで、桁までの精度を持つ関数の計算の複雑さ(ビット)は、2 桁の整数の乗算の複雑さです。 s f （ n ） {\displaystyle s_{f}(n)} f （ × ） {\displaystyle f(x)} n {\displaystyle n} M （ n ） {\displaystyle M(n)} n {\displaystyle n}

FEE法に基づくアルゴリズムには、引数の任意の値に対するあらゆる基本超越関数の高速計算アルゴリズム、古典定数e、 オイラー定数、カタラン定数、アペリー定数[4]、オイラーガンマ関数とその導関数、超幾何関数[ 5]、球面関数、円筒関数（ベッセル関数を含む）[6] 、引数の代数値とパラメータに対するその他の関数 、引数の整数値に対するリーマンゼータ関数[7] [8]、整数引数とパラメータの代数値に対するフルビッツゼータ関数[9]、および確率の積分、フレネル積分、積分指数関数、三角積分、および引数の代数値に対するその他の積分[10]などの特殊積分があり、これらの積分は計算量が最適値に近い。 π 、 {\displaystyle \pi,} γ 、 {\displaystyle \gamma ,}

s f （ n ） ＝ お （ M （ n ） ログ 2 ⁡ n ） 。 {\displaystyle s_{f}(n)=O(M(n)\log ^{2}n).\,}

FEEは、高次超越関数[11]のクラスに属する関数、数理物理学における特定の特殊積分、そしてオイラー定数、カタラン定数[12]、アペリー定数といった古典定数の値を高速に計算することを可能にする。FEE法の更なる利点は、FEEに基づくアルゴリズムを並列化できることである。

古典定数のFEE計算

定数を素早く評価するには、マチンのような公式を使用し 、FEEを適用してテイラー級数を合計します。 π 、 {\displaystyle \pi,} π 4 ＝ アークタンジェント ⁡ 1 2 + アークタンジェント ⁡ 1 3 、 {\displaystyle {\frac {\pi }{4}}=\arctan {\frac {1}{2}}+\arctan {\frac {1}{3}},}

アークタンジェント ⁡ 1 2 ＝ 1 1 ⋅ 2 − 1 3 ⋅ 2 3 + ⋯ + （ − 1 ） r − 1 （ 2 r − 1 ） 2 2 r − 1 + R 1 、 {\displaystyle \arctan {\frac {1}{2}}={\frac {1}{1\cdot 2}}-{\frac {1}{3\cdot 2^{3}}}+\cdots +{\frac {(-1)^{r-1}}{(2r-1)2^{2r-1}}}+R_{1},}
arctan ⁡ 1 3 = 1 1 ⋅ 3 − 1 3 ⋅ 3 3 + ⋯ + ( − 1 ) r − 1 ( 2 r − 1 ) 3 2 r − 1 + R 2 , {\displaystyle \arctan {\frac {1}{3}}={\frac {1}{1\cdot 3}}-{\frac {1}{3\cdot 3^{3}}}+\cdots +{\frac {(-1)^{r-1}}{(2r-1)3^{2r-1}}}+R_{2},}

境界を満たす 残りの項 R 1 , {\displaystyle R_{1},} R 2 , {\displaystyle R_{2},}

| R 1 | ≤ 4 5 1 2 r + 1 1 2 2 r + 1 ; {\displaystyle |R_{1}|\leq {\frac {4}{5}}{\frac {1}{2r+1}}{\frac {1}{2^{2r+1}}};}
| R 2 | ≤ 9 10 1 2 r + 1 1 3 2 r + 1 ; {\displaystyle |R_{2}|\leq {\frac {9}{10}}{\frac {1}{2r+1}}{\frac {1}{3^{2r+1}}};}

そして

r = n , {\displaystyle r=n,\,}
4 ( | R 1 | + | R 2 | )   <   2 − n . {\displaystyle 4(|R_{1}|+|R_{2}|)\ <\ 2^{-n}.}

FEEで計算するには、 他の近似値も使用できる[13]。いずれの場合も、計算の複雑さは π {\displaystyle \pi }

s π = O ( M ( n ) log 2 ⁡ n ) . {\displaystyle s_{\pi }=O(M(n)\log ^{2}n).\,}

オイラー定数ガンマを 桁精度で計算するには、2つの級数をFEEで足し合わせる必要があります。つまり、 n {\displaystyle n}

m = 6 n , k = n , k ≥ 1 , {\displaystyle m=6n,\quad k=n,\quad k\geq 1,\,}
γ = − log ⁡ n ∑ r = 0 12 n ( − 1 ) r n r + 1 ( r + 1 ) ! + ∑ r = 0 12 n ( − 1 ) r n r + 1 ( r + 1 ) ! ( r + 1 ) + O ( 2 − n ) . {\displaystyle \gamma =-\log n\sum _{r=0}^{12n}{\frac {(-1)^{r}n^{r+1}}{(r+1)!}}+\sum _{r=0}^{12n}{\frac {(-1)^{r}n^{r+1}}{(r+1)!(r+1)}}+O(2^{-n}).}

複雑さは

s γ = O ( M ( n ) log 2 ⁡ n ) . {\displaystyle s_{\gamma }=O(M(n)\log ^{2}n).\,}

定数を素早く評価するために、 FEEを他の近似値に適用することが可能です。[14] γ {\displaystyle \gamma }

特定の冪級数のFEE計算

FEE によって、次の 2 つのシリーズが高速に計算されます。

f 1 = f 1 ( z ) = ∑ j = 0 ∞ a ( j ) b ( j ) z j , {\displaystyle f_{1}=f_{1}(z)=\sum _{j=0}^{\infty }{\frac {a(j)}{b(j)}}z^{j},}
f 2 = f 2 ( z ) = ∑ j = 0 ∞ a ( j ) b ( j ) z j j ! , {\displaystyle f_{2}=f_{2}(z)=\sum _{j=0}^{\infty }{\frac {a(j)}{b(j)}}{\frac {z^{j}}{j!}},}

が整数であるという仮定のもと、 a ( j ) , b ( j ) {\displaystyle a(j),\quad b(j)}

| a ( j ) | + | b ( j ) | ≤ ( C j ) K ; | z |   <   1 ; K {\displaystyle |a(j)|+|b(j)|\leq (Cj)^{K};\quad |z|\ <\ 1;\quad K}

と は定数であり、 は代数的数である。この級数の評価の複雑さは C {\displaystyle C} z {\displaystyle z}

s f 1 ( n ) = O ( M ( n ) log 2 ⁡ n ) , {\displaystyle s_{f_{1}}(n)=O\left(M(n)\log ^{2}n\right),\,}
s f 2 ( n ) = O ( M ( n ) log ⁡ n ) . {\displaystyle s_{f_{2}}(n)=O\left(M(n)\log n\right).}

古典定数のFEE計算e

定数テイクの評価については、テイラー級数の項 e {\displaystyle e} m = 2 k , k ≥ 1 {\displaystyle m=2^{k},\quad k\geq 1} e , {\displaystyle e,}

e = 1 + 1 1 ! + 1 2 ! + ⋯ + 1 ( m − 1 ) ! + R m . {\displaystyle e=1+{\frac {1}{1!}}+{\frac {1}{2!}}+\cdots +{\frac {1}{(m-1)!}}+R_{m}.}

ここで を選択し、残りの部分について不等式が満たされることを要求します。これは例えば のときです。したがって、をとると、 自然数は不等式によって決定されます。 m {\displaystyle m} R m {\displaystyle R_{m}} R m ≤ 2 − n − 1 {\displaystyle R_{m}\leq 2^{-n-1}} m ≥ 4 n log ⁡ n . {\displaystyle m\geq {\frac {4n}{\log n}}.} m = 2 k {\displaystyle m=2^{k}} k {\displaystyle k}

2 k ≥ 4 n log ⁡ n > 2 k − 1 . {\displaystyle 2^{k}\geq {\frac {4n}{\log n}}>2^{k-1}.}

合計を計算します

S = 1 + 1 1 ! + 1 2 ! + ⋯ + 1 ( m − 1 ) ! = ∑ j = 0 m − 1 1 ( m − 1 − j ) ! , {\displaystyle S=1+{\frac {1}{1!}}+{\frac {1}{2!}}+\cdots +{\frac {1}{(m-1)!}}=\sum _{j=0}^{m-1}{\frac {1}{(m-1-j)!}},}

以下のプロセスの手順 で行います。 k {\displaystyle k}

ステップ1.被加数をペアで順に組み合わせて、括弧内の「明らかな」共通因数を取り、 S {\displaystyle S}

S = ( 1 ( m − 1 ) ! + 1 ( m − 2 ) ! ) + ( 1 ( m − 3 ) ! + 1 ( m − 4 ) ! ) + ⋯ = 1 ( m − 1 ) ! ( 1 + m − 1 ) + 1 ( m − 3 ) ! ( 1 + m − 3 ) + ⋯ . {\displaystyle {\begin{aligned}S&=\left({\frac {1}{(m-1)!}}+{\frac {1}{(m-2)!}}\right)+\left({\frac {1}{(m-3)!}}+{\frac {1}{(m-4)!}}\right)+\cdots \\&={\frac {1}{(m-1)!}}(1+m-1)+{\frac {1}{(m-3)!}}(1+m-3)+\cdots .\end{aligned}}}

括弧内の式の整数値のみを計算します。つまり、

m , m − 2 , m − 4 , … . {\displaystyle m,m-2,m-4,\dots .\,}

したがって、最初のステップでは、合計は S {\displaystyle S}

S = S ( 1 ) = ∑ j = 0 m 1 − 1 1 ( m − 1 − 2 j ) ! α m 1 − j ( 1 ) , {\displaystyle S=S(1)=\sum _{j=0}^{m_{1}-1}{\frac {1}{(m-1-2j)!}}\alpha _{m_{1}-j}(1),}
m 1 = m 2 , m = 2 k , k ≥ 1. {\displaystyle m_{1}={\frac {m}{2}},m=2^{k},k\geq 1.}

最初のステップでは、次の形式の整数 m 2 {\displaystyle {\frac {m}{2}}}

α m 1 − j ( 1 ) = m − 2 j , j = 0 , 1 , … , m 1 − 1 , {\displaystyle \alpha _{m_{1}-j}(1)=m-2j,\quad j=0,1,\dots ,m_{1}-1,}

が計算されます。その後は同様の手順で行います。各ステップで、和の被加数をペアで順番に組み合わせ、括弧内から「明らかな」共通因数を取り出し、括弧内の式の整数値のみを計算します。このプロセスの最初のステップは完了していると仮定します。 S {\displaystyle S} i {\displaystyle i}

ステップ（）。 i + 1 {\displaystyle i+1} i + 1 ≤ k {\displaystyle i+1\leq k}

S = S ( i + 1 ) = ∑ j = 0 m i + 1 − 1 1 ( m − 1 − 2 i + 1 j ) ! α m i + 1 − j ( i + 1 ) , {\displaystyle S=S(i+1)=\sum _{j=0}^{m_{i+1}-1}{\frac {1}{(m-1-2^{i+1}j)!}}\alpha _{m_{i+1}-j}(i+1),}
m i + 1 = m i 2 = m 2 i + 1 , {\displaystyle m_{i+1}={\frac {m_{i}}{2}}={\frac {m}{2^{i+1}}},}

我々は次の形式の整数 のみを計算する。 m 2 i + 1 {\displaystyle {\frac {m}{2^{i+1}}}}

α m i + 1 − j ( i + 1 ) = α m i − 2 j ( i ) + α m i − ( 2 j + 1 ) ( i ) ( m − 1 − 2 i + 1 j ) ! ( m − 1 − 2 i − 2 i + 1 j ) ! , {\displaystyle \alpha _{m_{i+1}-j}(i+1)=\alpha _{m_{i}-2j}(i)+\alpha _{m_{i}-(2j+1)}(i){\frac {(m-1-2^{i+1}j)!}{(m-1-2^{i}-2^{i+1}j)!}},}
j = 0 , 1 , … , m i + 1 − 1 , m = 2 k , k ≥ i + 1. {\displaystyle j=0,1,\dots ,\quad m_{i+1}-1,\quad m=2^{k},\quad k\geq i+1.}

ここ

( m − 1 − 2 i + 1 j ) ! ( m − 1 − 2 i − 2 i + 1 j ) ! {\displaystyle {\frac {(m-1-2^{i+1}j)!}{(m-1-2^{i}-2^{i+1}j)!}}}

整数の積です。 2 i {\displaystyle 2^{i}}

等。

ステップ、最後のステップです。 上記の高速アルゴリズムを用いて、 1つの整数値を計算し、その整数を 整数で 1回割り算します。その割り算の精度は桁までです。得られた結果は、桁までの 和または定数です。すべての計算の計算量は、 k {\displaystyle k} α 1 ( k ) , {\displaystyle \alpha _{1}(k),} ( m − 1 ) ! , {\displaystyle (m-1)!,} α 1 ( k ) {\displaystyle \alpha _{1}(k)} ( m − 1 ) ! , {\displaystyle (m-1)!,} n {\displaystyle n} S , {\displaystyle S,} e {\displaystyle e} n {\displaystyle n}

O ( M ( m ) log 2 ⁡ m ) = O ( M ( n ) log ⁡ n ) . {\displaystyle O\left(M(m)\log ^{2}m\right)=O\left(M(n)\log n\right).\,}

参照

参考文献

  1. ^ EA Karatsuba, 超越関数の高速評価. Probl. Peredachi Informat., Vol. 27, No. 4, (1991)
  2. ^ DW LozierとFWJ Olver、「特殊関数の数値評価。計算数学1943-1993：計算数学の半世紀」、W. Gautschi編、Proc. Sympos. Applied Mathematics、AMS、Vol. 48 (1994)。
  3. ^ CLシーゲル 「超越数」プリンストン大学出版局、プリンストン（1949年）。
  4. ^ Karatsuba EA, の高速評価, Probl. Peredachi Informat., Vol. 29, No. 1 (1993) ζ ( 3 ) {\displaystyle \zeta (3)}
  5. ^ Ekatharine A. Karatsuba, FEEによる超幾何関数の高速評価. 計算手法と関数理論 (CMFT'97), N. Papamichael, St. Ruscheweyh, EB Saff編, World Sc. Pub. (1999)
  6. ^ キャサリン・A・カラツバ「ベッセル関数の高速評価」積分変換と特殊関数、第1巻、第4号（1993年）
  7. ^ EA Karatsuba,引数の整数値に対するリーマンゼータ関数の高速評価。Probl. Peredachi Informat., Vol. 31, No. 4 (1995). ζ ( s ) {\displaystyle \zeta (s)} s {\displaystyle s}
  8. ^ JM Borwein, DM BradleyおよびRE Crandall、「リーマンゼータ関数の計算戦略」、J. of Comput. Appl. Math.、Vol. 121、No. 1–2 (2000)。
  9. ^ EA Karatsuba、Hurwitz ゼータ関数と Dirichletシリーズの高速評価、問題。ペレダチ情報 Vol. 34、No. 4、342 ～ 353 ページ、(1998)。 L {\displaystyle L}
  10. ^ EA Karatsuba, 数理物理学におけるいくつかの特殊積分の高速計算. Scientific Computing, Validated Numerics, Interval Methods, W. Kramer, JW von Gudenberg編(2001).
  11. ^ E. Bach, 数論定数の複雑さ. Info. Proc. Letters, No. 62 (1997).
  12. ^ EA Karatsuba, 多重対数法、ラマヌジャンの公式とその一般化を用いた$\zeta(3)$といくつかの特殊積分の高速計算。数値数学BIT誌、第41巻、第4号（2001年）。
  13. ^ DH Bailey、PB Borwein、S. Plouffe、「さまざまな多重対数定数の高速計算について」Math. Comp.、Vol. 66 (1997)。
  14. ^ RP BrentとEM McMillan、「オイラー定数の高精度計算のためのいくつかの新しいアルゴリズム」Math. Comp., Vol. 34 (1980)。
  • http://www.ccas.ru/personal/karatsuba/divcen.htm
  • http://www.ccas.ru/personal/karatsuba/algen.htm
Retrieved from "https://en.wikipedia.org/w/index.php?title=FEE_method&oldid=1325466638"