FEE metoda - FEE method

V matematice je FEE metoda je metoda rychlého sčítání řad zvláštního tvaru. Byl postaven v roce 1990 společností Ekaterina A. Karatsuba^[1]^[2] a byl volán POPLATEK – rychlé vyhodnocení E-funkce - protože umožňuje rychlé výpočty Siegelu ${displaystyle E}$ -funkce možné, a zejména z ${displaystyle e ^ {x}.}$

Třída funkcí, které jsou „podobné exponenciální funkci“, dostala název „E-funkce“ Siegel.^[3] Mezi tyto funkce patří speciální funkce jako hypergeometrická funkce, válec, sférický funkce atd.

Pomocí FEL je možné dokázat následující větu:

Teorém: Nechte ${displaystyle y = f (x)}$ být základní transcendentální funkce, toto je exponenciální funkce nebo trigonometrická funkce, nebo elementární algebraická funkce, nebo jejich superpozice, nebo jejich inverzní nebo superpozice inverzí. Pak

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

Tady ${displaystyle s_ {f} (n)}$ je složitost výpočtu (bit) funkce ${displaystyle f (x)}$ s přesností až ${displaystyle n}$ číslice, ${displaystyle M (n)}$ je složitost násobení dvou ${displaystyle n}$ -číselná celá čísla.

Algoritmy založené na metodě FEL zahrnují algoritmy pro rychlý výpočet libovolného elementárního prvku transcendentální funkce pro jakoukoli hodnotu argumentu klasické konstanty E, ${displaystyle pi,}$ the Eulerova konstanta ${displaystyle gamma,}$ the Katalánština a Apéryho konstanty,^[4] takové vyšší transcendentální funkce jako Eulerova gama funkce a jeho deriváty, hypergeometrický,^[5] sférický, válec (včetně Bessel )^[6] funkce a některé další funkce proalgebraický hodnoty argumentu a parametrů, Funkce Riemann zeta pro celočíselné hodnoty argumentu^[7]^[8] a Funkce Hurwitz zeta pro celočíselný argument a algebraické hodnoty parametru,^[9] a také takové speciální integrály jako integrál pravděpodobnosti, Fresnelovy integrály, integrální exponenciální funkce, trigonometrické integrály a některé další integrály^[10] pro algebraické hodnoty argumentu s vázanou složitostí, která je blízká optimální, a to

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

V současnosti,^{[když? ]} pouze FEE umožňuje rychle vypočítat hodnoty funkcí z třídy vyšších transcendentních funkcí,^[11] určité speciální integrály matematické fyziky a takové klasické konstanty jako Eulerova, Katalánština^[12] a Apéryho konstanty. Další výhodou metody FEE je možnost paralelizace algoritmů založených na FEE.

Výpočet FEE klasických konstant

Pro rychlé vyhodnocení konstant ${displaystyle pi,}$ lze použít Eulerův vzorec ${displaystyle {frac {pi} {4}} = arctan {frac {1} {2}} + arctan {frac {1} {3}},}$ a použít FEE na součet Taylorovy řady

{displaystyle arctan {frac {1} {2}} = {frac {1} {1cdot 2}} - {frac {1} {3cdot 2 ^ {3}}} + cdots + {frac {(-1) ^ { r-1}} {(2r-1) 2 ^ {2r-1}}} + R_ {1},}

{displaystyle arctan {frac {1} {3}} = {frac {1} {1cdot 3}} - {frac {1} {3cdot 3 ^ {3}}} + cdots + {frac {(-1) ^ { r-1}} {(2r-1) 3 ^ {2r-1}}} + R_ {2},}

se zbývajícími podmínkami ${displaystyle R_ {1},}$ ${displaystyle R_ {2},}$ které uspokojují hranice

{displaystyle | R_ {1} | leq {frac {4} {5}} {frac {1} {2r + 1}} {frac {1} {2 ^ {2r + 1}}};}

{displaystyle | R_ {2} | leq {frac {9} {10}} {frac {1} {2r + 1}} {frac {1} {3 ^ {2r + 1}}};}

a pro

{displaystyle r = n ,,}

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

Vypočítat ${displaystyle pi}$ theFEE je možné použít i jiné aproximace^[13] Ve všech případech je složitost

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

Vypočítat Eulerovo konstantní gama s přesností až ${displaystyle n}$ číslic, je nutné sečíst podle FEL dvě řady. Jmenovitě pro

{displaystyle m = 6n, quad k = n, quad kgeq 1 ,,}

{displaystyle gamma = -log nsum _ {r = 0} ^ {12n} {frac {(-1) ^ {r} n ^ {r + 1}} {(r + 1)!}} + součet _ {r = 0} ^ {12n} {frac {(-1) ^ {r} n ^ {r + 1}} {(r + 1)! (R + 1)}} + O (2 ^ {- n}) .}

Složitost je

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

Rychle vyhodnotit konstantu ${displaystyle gamma}$ je možné použít FEE na jiné aproximace.^[14]

Výpočet FEE určitých výkonových řad

Podle FEE se rychle počítají dvě následující řady:

{displaystyle f_ {1} = f_ {1} (z) = součet _ {j = 0} ^ {infty} {frac {a (j)} {b (j)}} z ^ {j},}

{displaystyle f_ {2} = f_ {2} (z) = součet _ {j = 0} ^ {infty} {frac {a (j)} {b (j)}} {frac {z ^ {j}} {j!}},}

za předpokladu, že ${displaystyle a (j), quad b (j)}$ jsou celá čísla,

{displaystyle | a (j) | + | b (j) | leq (Cj) ^ {K}; quad | z | <1; čtyřkolka K}

a ${displaystyle C}$ jsou konstanty a ${displaystyle z}$ je algebraické číslo. Složitost hodnocení série je

{displaystyle s_ {f_ {1}} (n) = Oleft (M (n) log ^ {2} noc) ,,}

{displaystyle s_ {f_ {2}} (n) = Oleft (M (n) log noc).}

Podrobnosti o FEE na příkladu rychlého výpočtu klasické konstanty E

Pro vyhodnocení konstanty ${displaystyle e}$ vzít ${displaystyle m = 2 ^ {k}, quad kgeq 1}$ , podmínky Taylorovy řady pro ${displaystyle e,}$

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

Tady jsme si vybrali ${displaystyle m}$ , požadující to pro zbytek ${displaystyle R_ {m}}$ nerovnost ${displaystyle R_ {m} leq 2 ^ {- n-1}}$ je splněn. To je například případ, kdy ${displaystyle mgeq {frac {4n} {log n}}.}$ Bereme tedy ${displaystyle m = 2 ^ {k}}$ takové, že přirozené číslo ${displaystyle k}$ je dáno nerovnostmi:

{displaystyle 2 ^ {k} geq {frac {4n} {log n}}> 2 ^ {k-1}.}

Vypočítáme součet

{displaystyle S = 1 + {frac {1} {1!}} + {frac {1} {2!}} + cdots + {frac {1} {(m-1)!}} = součet _ {j = 0} ^ {m-1} {frac {1} {(m-1-j)!}},}

v ${displaystyle k}$ kroky následujícího procesu.

Krok 1. Kombinace ${displaystyle S}$ summandy postupně v párech vynášejí z závorek „zřejmý“ společný faktor a získají

{displaystyle {egin {aligned} S & = left ({frac {1} {(m-1)!}} + {frac {1} {(m-2)!}} ight) + left ({frac {1} {(m-3)!}} + {frac {1} {(m-4)!}} ight) + cdots & = {frac {1} {(m-1)!}} (1 + m- 1) + {frac {1} {(m-3)!}} (1 + m-3) + cdots .end {zarovnáno}}}

Budeme počítat pouze celočíselné hodnoty výrazů v závorkách, tedy hodnoty

{displaystyle m, m-2, m-4, tečky.,}

V prvním kroku tedy součet ${displaystyle S}$ je do

{displaystyle S = S (1) = součet _ {j = 0} ^ {m_ {1} -1} {frac {1} {(m-1-2j)!}} alfa _ {m_ {1} -j } (1),}

{displaystyle m_ {1} = {frac {m} {2}}, m = 2 ^ {k}, kgeq 1.}

V prvním kroku ${displaystyle {frac {m} {2}}}$ celá čísla formuláře

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

jsou vypočteny. Poté postupujeme podobným způsobem: kombinací každého kroku se sčítají součty ${displaystyle S}$ postupně v párech vymáčkněte z závorek „zřejmý“ společný faktor a vypočítejte pouze celočíselné hodnoty výrazů v závorkách. Předpokládejme, že první ${displaystyle i}$ kroky tohoto procesu jsou dokončeny.

Krok ${displaystyle i + 1}$ ( ${displaystyle i + 1leq k}$ ).

{displaystyle S = S (i + 1) = součet _ {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}}},}

počítáme pouze ${displaystyle {frac {m} {2 ^ {i + 1}}}}$ celá čísla formuláře

{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)!}},}

{displaystyle j = 0,1, tečky, quad m_ {i + 1} -1, quad m = 2 ^ {k}, quad kgeq i + 1.}

Tady

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

je produktem ${displaystyle 2 ^ {i}}$ celá čísla.

Atd.

Krok ${displaystyle k}$ , poslední. Vypočítáme jednu celočíselnou hodnotu ${displaystyle alpha _ {1} (k),}$ vypočítáme pomocí rychlého algoritmu popsaného výše ${displaystyle (m-1) !,}$ a udělejte jedno dělení celého čísla ${displaystyle alpha _ {1} (k)}$ celým číslem ${displaystyle (m-1) !,}$ s přesností až ${displaystyle n}$ číslice. Získaným výsledkem je součet ${displaystyle S,}$ nebo konstanta ${displaystyle e}$ až do ${displaystyle n}$ číslice. Složitost všech výpočtů je

{displaystyle Oleft (M (m) log ^ {2} může) = Oleft (M (n) log noc).,}

Viz také

Reference

^ E. A. Karatsuba, Rychlé hodnocení transcendentálních funkcí. Probl. Peredachi Informat., Sv. 27, č. 4, (1991)
^ D. W. Lozier a F. W. J. Olver, Numerické hodnocení speciálních funkcí. Mathematics of Computation 1943–1993: A Half-Century of Computational Mathematics, W. Gautschi, eds., Proc. Symposy. Applied Mathematics, AMS, roč. 48 (1994).
^ C. L. Siegel,Transcendentní čísla. Princeton University Press, Princeton (1949).
^ Karatsuba E. A., Rychlé hodnocení ${displaystyle zeta (3)}$ , Probl. Peredachi Informat., Sv. 29, č. 1 (1993)
^ Ekatharine A. Karatsuba, Rychlé vyhodnocení hypergeometrické funkce pomocí FEL. Computational Methods and Function Theory (CMFT'97), N. Papamichael, St. Ruscheweyh a E. B. Saff, eds., World Sc. Hospoda. (1999)
^ Catherine A. Karatsuba, Rychlé vyhodnocení Besselových funkcí. Integral Transforms and Special Functions, sv. 1, č. 4 (1993)
^ E. A. Karatsuba, Rychlé vyhodnocení Riemannovy zeta-funkce ${displaystyle zeta (s)}$ pro celočíselné hodnoty argumentu ${displaystyle s}$ . Probl. Peredachi Informat., Sv. 31, č. 4 (1995).
^ J. M. Borwein, D. M. Bradley a R. E. Crandall, Výpočetní strategie pro funkci Riemann zeta. J. of Comput. Appl. Math., Sv. 121, č. 1–2 (2000).
^ E. A. Karatsuba, Rychlé vyhodnocení funkce Hurwitz zeta a Dirichlet ${displaystyle L}$ -series, Problem. Peredachi Informat., Sv. 34, č. 4, str. 342–353, (1998).
^ E. A. Karatsuba, Rychlý výpočet některých speciálních integrálů matematické fyziky. Scientific Computing, Validated Numerics, Interval Methods, W. Kramer, J. W. von Gudenberg, eds. (2001).
^ E. Bach, Složitost číselně-teoretických konstant. Info. Proc. Letters, No. 62 (1997).
^ E. A. Karatsuba, Rychlý výpočet $ zeta (3) $ a některých speciálních integrálů pomocí polylogaritmů, Ramanujanova vzorce a jeho zobecnění. J. of Numerical Mathematics BIT, sv. 41, č. 4 (2001).
^ D. H. Bailey, P. B. Borwein a S. Plouffe, O rychlém výpočtu různých polylogaritmických konstant. Math.Comp., Sv. 66 (1997).
^ R. P. Brent a E. M. McMillan, Některé nové algoritmy pro vysoce přesný výpočet Eulerovy konstanty. Matematika. Comp., Sv. 34 (1980).

externí odkazy

[1] E. A. Karatsuba, Rychlé hodnocení transcendentálních funkcí. Probl. Peredachi Informat., Sv. 27, č. 4, (1991)

[2] D. W. Lozier a F. W. J. Olver, Numerické hodnocení speciálních funkcí. Mathematics of Computation 1943–1993: A Half-Century of Computational Mathematics, W. Gautschi, eds., Proc. Symposy. Applied Mathematics, AMS, roč. 48 (1994).

[3] C. L. Siegel,Transcendentní čísla. Princeton University Press, Princeton (1949).

[4] Karatsuba E. A., Rychlé hodnocení ${displaystyle zeta (3)}$ , Probl. Peredachi Informat., Sv. 29, č. 1 (1993)

[5] Ekatharine A. Karatsuba, Rychlé vyhodnocení hypergeometrické funkce pomocí FEL. Computational Methods and Function Theory (CMFT'97), N. Papamichael, St. Ruscheweyh a E. B. Saff, eds., World Sc. Hospoda. (1999)

[6] Catherine A. Karatsuba, Rychlé vyhodnocení Besselových funkcí. Integral Transforms and Special Functions, sv. 1, č. 4 (1993)

[7] E. A. Karatsuba, Rychlé vyhodnocení Riemannovy zeta-funkce ${displaystyle zeta (s)}$ pro celočíselné hodnoty argumentu ${displaystyle s}$ . Probl. Peredachi Informat., Sv. 31, č. 4 (1995).

[8] J. M. Borwein, D. M. Bradley a R. E. Crandall, Výpočetní strategie pro funkci Riemann zeta. J. of Comput. Appl. Math., Sv. 121, č. 1–2 (2000).

[9] E. A. Karatsuba, Rychlé vyhodnocení funkce Hurwitz zeta a Dirichlet ${displaystyle L}$ -series, Problem. Peredachi Informat., Sv. 34, č. 4, str. 342–353, (1998).

[10] E. A. Karatsuba, Rychlý výpočet některých speciálních integrálů matematické fyziky. Scientific Computing, Validated Numerics, Interval Methods, W. Kramer, J. W. von Gudenberg, eds. (2001).

[11] E. Bach, Složitost číselně-teoretických konstant. Info. Proc. Letters, No. 62 (1997).

[12] E. A. Karatsuba, Rychlý výpočet $ zeta (3) $ a některých speciálních integrálů pomocí polylogaritmů, Ramanujanova vzorce a jeho zobecnění. J. of Numerical Mathematics BIT, sv. 41, č. 4 (2001).

[13] D. H. Bailey, P. B. Borwein a S. Plouffe, O rychlém výpočtu různých polylogaritmických konstant. Math.Comp., Sv. 66 (1997).

[14] R. P. Brent a E. M. McMillan, Některé nové algoritmy pro vysoce přesný výpočet Eulerovy konstanty. Matematika. Comp., Sv. 34 (1980).

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]