Metoda OPŁATY

W matematyce metoda FEE lub metoda oceny szybkiej funkcji E jest metodą szybkiego sumowania szeregów o specjalnej postaci. Został skonstruowany w 1990 roku przez Ekaterinę Karatsubę i nosi taką nazwę, ponieważ umożliwia szybkie obliczenia funkcji E $Siegela$ , w szczególności funkcji mi $\ displaystyle e ^ {x}}$ .

Klasa funkcji, które są „podobne do funkcji wykładniczej”, została nazwana „E-funkcjami” przez Carla Ludwiga Siegela . Wśród tych funkcji znajdują się takie funkcje specjalne , jak funkcja hipergeometryczna , cylindryczna , sferyczna i tak dalej.

Za pomocą FEE można udowodnić następujące twierdzenie:

Twierdzenie : Niech będzie $funkcją$ odwrotnością funkcją transcendentalną , czyli funkcją wykładniczą funkcją trygonometryczną , elementarną superpozycją lub lub superpozycja odwrotności. Następnie

{\ Displaystyle s_ {f} (n) = O (M (n) \ log ^ {2} n). \,}

Tutaj ${\ Displaystyle s_ {f} (n)}$ jest złożonością obliczeń (bitowych) funkcji ${\ Displaystyle f (x)}$ z dokładnością do ${\ displaystyle n}$ cyfry $,$ dwóch $.$ liczb

Algorytmy oparte na metodzie FEE obejmują algorytmy szybkiego obliczania dowolnej elementarnej funkcji przestępnej dla dowolnej wartości argumentu, klasyczne stałe stałe Eulera mi , ${\ displaystyle \ pi,}$ stała Eulera ${\ displaystyle \ gamma, }$ stałe katalońskie i Apéry'ego , takie wyższe funkcje przestępne, jak funkcja gamma Eulera i jej pochodne, funkcje hipergeometryczne , sferyczne , cylindryczne (w tym Bessela ) i niektóre inne funkcje dla algebraicznych wartości argumentu i parametrów, funkcja zeta Riemanna dla całkowitych wartości argumentu i funkcji zeta Hurwitza dla argumentu całkowitego i algebraicznych wartości parametru, a także całek specjalnych, takich jak całka prawdopodobieństwa , całki Fresnela , całkowa funkcja wykładnicza , całki trygonometryczne i niektóre inne całki dla wartości algebraiczne argumentu o granicy złożoności zbliżonej do optymalnej, tj

{\ Displaystyle s_ {f} (n) = O (M (n) \ log ^ {2} n). \,}

Obecnie ^{[ kiedy? ]} dopiero FEE umożliwia szybkie obliczenie wartości funkcji z klasy wyższych funkcji przestępnych, niektórych całek specjalnych fizyki matematycznej oraz takich klasycznych stałych jak stała Eulera, Catalana i Apéry'ego. Dodatkową zaletą metody FEE jest możliwość zrównoleglenia algorytmów opartych na metodzie FEE.

Obliczanie FEE stałych klasycznych

Do szybkiego oszacowania stałej można użyć wzoru Eulera $arctan {\frac {1}{2}}+\arctan {\frac {1}{3}},}$ $,$ $\ Displaystyle {\ Frac {\ pi}}}$ i zastosuj OPŁATĘ, aby zsumować szereg Taylora dla

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

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

z pozostałymi terminami, które spełniają granice ${\ Displaystyle R_ {1},}$ ${\ Displaystyle R_ {2}}$

{\ Displaystyle | R_ {1} | \ równoważnik {\ Frac {4} {5}}} {\ Frac {1} {2r + 1}}} {\ Frac {1} {2 ^ {2r + 1}}}; }

{\ Displaystyle | R_ {2} | \ równoważnik {\ Frac {9} {10}} {\ Frac {1} {2r + 1}}} {\ Frac {1} {3 ^ {2r + 1}}}; }

i dla

{\ Displaystyle r = n, \,}

{\ Displaystyle 4 (| R_ {1} | + | R_ {2} |) \ <\ 2 ^ {- n}.}

Aby obliczyć za pomocą OPŁATY, można zastosować również inne przybliżenia. We wszystkich przypadkach złożoność wynosi ${\ displaystyle \ pi}$

{\ Displaystyle s_ {\ pi} = O (M (n) \ log ^ {2} n). \,}

Aby obliczyć stałą gamma Eulera z dokładnością do $.$ , konieczne jest zsumowanie przez FEE dwóch serii Mianowicie dla

{\ Displaystyle m = 6n, \ quad k = n, \ quad k \ geq 1, \,}

{\ Displaystyle \ gamma = - \ log n \ suma _ {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}).}

Złożoność jest

{\ Displaystyle s _ {\ gamma} = O (M (n) \ log ^ {2} n). \,}

Aby szybko oszacować stałą $możliwe$ jest zastosowanie OPŁATY do innych przybliżeń.

Obliczanie FEE pewnych szeregów potęgowych

Przez FEE szybko obliczane są dwie następujące serie:

{\ Displaystyle f_ {1} = f_ {1} (z) = \ suma _ {j = 0} ^ { \infty }{\frac {a(j)}{b(j)}}z^{j},

\ Displaystyle f_ {2} = f_ {2} (z) = \ suma _ {j = 0} ^ {\ infty} {\ Frac {a (j)}} {b (j)}} {\ Frac { z^{j}}{j!}},}

za ${\ Displaystyle a (j), \ quad b (j)}$ liczbami całkowitymi,

{\ Displaystyle | a (j) | + | b (j) | \ równoważnik (Cj) ^ {K}; \ quad | z |\ <\ 1; \ quad K}

i $są$ $stałymi$ , a algebraiczną. Złożoność oceny serii jest

{\ Displaystyle s_ {f_ {1}} (n) = O \ lewo (M (n) \ log ^ {2} n \ prawo ),\,}

{\ Displaystyle s_ {f_ {2}} (n) = O \ lewo (M (n) \ log n \ prawo).}

Obliczenie FEE stałej klasycznej e

Aby obliczyć stałą, $\$ m $Displaystyle m = 2 ^ {k}, \ quad k \ geq 1}$ , wyrazy z szeregu Taylora dla ${\ styl wyświetlania e,}$

{\ Displaystyle e = 1 + {\ Frac {1} {1!}} + {\ Frac {1} {2!}} + \ cdots + {\ Frac {1} {(m-1)!}} + R_{m}.}

$,$ wybieramy $m} \ równoważnik 2 ^ {-n- 1}}$ , aby dla reszty była nierówność $Displaystyle R_$ jest spełnione. Dzieje się tak na przykład, gdy ${\ Displaystyle m \ geq {\ Frac {4n} {\ log n}}.}$ $displaystyle k$ $k$ takie , że liczba naturalna jest określona przez nierówności:

{\ Displaystyle 2 ^ {k} \ geq {\ Frac {4n} {\ log n}}> 2 ^ {k-1}.}

Obliczamy sumę

{\ Displaystyle S = 1 + {\ Frac {1} {1}}} + {\ Frac {1} {2!}} + \ cdots + {\ Frac {1} {(m-1)!}

w $krokach$ następującego procesu

Krok 1. Łącząc sumy kolejno w parach, wyprowadzamy z nawiasów „oczywisty” wspólny czynnik i otrzymujemy S {\ $S}$

{\ Displaystyle {\ rozpocząć {wyrównane} S & = \ lewo ({\ Frac {1} {(m-1)!}} + {\ Frac {1} {(m-2)!}} \ prawej) + \ 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{wyrównane}}}

Obliczymy tylko wartości całkowite wyrażeń w nawiasach, czyli wartości

{\ Displaystyle m, m-2, m-4, \ kropki. \,}

na pierwszym etapie $jest$

{\ Displaystyle S = S (1) = \ suma _ {j = 0} ^ {m_ {1} -1} {\ Frac {1} {(m-1-2j) !}} \ alfa _ {m_ {1} -j} (1),}

{\ Displaystyle m_ {1} = {\ Frac {m} {2} }},m=2^{k},k\geq 1.}

W pierwszym kroku liczby całkowite postaci ${\ Displaystyle {\ Frac {m} {2}}}$

{\ Displaystyle \ alfa _ {m_ {1} -j} (1) = m-2j \ quad j=0,1,\kropki,m_{1}-1,}

są obliczane. Następnie postępujemy w podobny sposób: łącząc na każdym kroku sumy sumy $parami$ , usuwamy z nawiasów „oczywisty” wspólny czynnik i obliczamy tylko wartości całkowite wyrażeń w wsporniki. Załóżmy $,$ że pierwsze tego procesu zostały zakończone.

Krok ${\ Displaystyle i + 1}$ ( ${\ Displaystyle i + 1 \ równoważnik k}$ ).

{\ Displaystyle S = S (i + 1) = \ suma _ {j = 0} ^ {m_ {i + 1} -1} {\ Frac {1} {(m-1-2^{i+1}j)!}}\alpha _{m_{i+1}-j}(i+1),}

{\ Displaystyle m_ {i + 1} = {\ Frac {m_ {i}} {2}} = {\ Frac {m} {2 ^ {i + 1}}},}

obliczamy tylko liczby całkowite postaci ${\ Displaystyle {\ Frac {m} {2 ^ {i + 1}}}}$

\ Displaystyle \ alfa _ {m_ {i + 1} -j} (i + 1) = \ alfa _ {m_ {i} -2j} (i) + \ alfa _ {m_ {i} - (2j + 1)}(i){\frac {(m-1-2^{i+1}j)!}{(m-1-2^{i}-2^{i+1}j)!}} ,}

{\ Displaystyle j = 0,1, \ kropki, \ quad m_ {i + 1} -1, \quad m=2^{k},\quad k\geq i+1.}

Tutaj

{\ Displaystyle {\ Frac {(m-1-2 ^ {i + 1} j)!} {(m-1-2 ^ {i} -2 ^ {i + 1} j)!}}}

$jest$ iloczynem .

Itp.

Krok $ostatni$ _ Obliczamy jedną wartość całkowitą ${\ Displaystyle \ alpha _ {1} (k)}$ obliczamy, używając szybkiego algorytmu opisanego powyżej wartości $\ Displaystyle (m-1) !,}$ $dokonaj$ ${\ Displaystyle (m-1) !,}$ liczby całkowitej liczbę całkowitą z dokładnością do cyfr ${\ displaystyle n}$ . Otrzymany $wynik$ $to$ $.$ stała do _ Złożoność wszystkich obliczeń jest

{\ Displaystyle O \ lewo (M (m) \ log ^ {2} m \ prawo) = O \ lewo (M (n) \ log n \ prawo). \,}

Zobacz też

Linki zewnętrzne