método de tarifa

Método de suma rápida en matemáticas.

En matemáticas, el método FEE , o método rápido de evaluación de funciones E , es el método de suma rápida de series de una forma especial. Fue construido en 1990 por Ekaterina Karatsuba ^{[1] [2]} y se llama así porque hace posibles cálculos rápidos de las funciones E de Siegel , en particular de . ${\displaystyle e^{x}}$

Una clase de funciones que son "similares a la función exponencial" recibió el nombre de "funciones E" de Carl Ludwig Siegel . ^[3] Entre estas funciones se encuentran funciones especiales como la función hipergeométrica , el cilindro , las funciones esféricas , etc.

Utilizando la FEE, es posible demostrar el siguiente teorema:

Teorema : Sea una función trascendental elemental , o sea la función exponencial , o una función trigonométrica , o una función algebraica elemental , o su superposición, o su inversa , o una superposición de las inversas. Entonces ${\displaystyle y=f(x)}$

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

Aquí está la complejidad del cálculo (bits) de la función con precisión de hasta dígitos, es la complejidad de la multiplicación de números enteros de dos dígitos. ${\displaystyle s_{f}(n)}$ ${\displaystyle f(x)}$ ${\displaystyle n}$ ${\displaystyle M(n)}$ ${\displaystyle n}$

Los algoritmos basados ​​en el método FEE incluyen los algoritmos para el cálculo rápido de cualquier función trascendental elemental para cualquier valor del argumento, las constantes clásicas e , la constante de Euler, la catalana y las constantes de Apéry , ^[4] funciones trascendentales superiores como la de Euler. función gamma y sus derivadas, las funciones hipergeométricas , ^[5] esféricas , cilíndricas (incluida la de Bessel ) ^[6] y algunas otras funciones para valores algebraicos del argumento y parámetros, la función zeta de Riemann para valores enteros del argumento ^{[7] [8]} y la función zeta de Hurwitz para argumentos enteros y valores algebraicos del parámetro, ^[9] y también integrales especiales como la integral de probabilidad , las integrales de Fresnel , la función exponencial integral , las integrales trigonométricas y algunas otras integrales ^{[ 10]} para valores algebraicos del argumento con un límite de complejidad cercano al óptimo, es decir ${\displaystyle \pi ,}$ ${\displaystyle \gamma ,}$

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

La FEE permite calcular rápidamente los valores de funciones de la clase de funciones trascendentales superiores ^[11] , ciertas integrales especiales de la física matemática y constantes clásicas como las de Euler, Catalan ^[12] y Apéry. Una ventaja adicional del método FEE es la posibilidad de paralelizar los algoritmos basados ​​en el FEE.

Cálculo FEE de constantes clásicas.

Para una evaluación rápida de la constante, se puede utilizar la fórmula de Euler y aplicar la FEE para sumar la serie de Taylor para ${\displaystyle \pi ,}$ ${\displaystyle {\frac {\pi }{4}}=\arctan {\frac {1}{2}}+\arctan {\frac {1}{3}},}$

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

con los términos restantes que satisfacen los límites ${\displaystyle R_{1},}$ ${\displaystyle R_{2},}$

${\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}}};}$

y para

${\displaystyle r=n,\,}$

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

Para calcular la FEE es posible utilizar también otras aproximaciones ^[13] En todos los casos la complejidad es ${\displaystyle \pi }$

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

Para calcular la constante gamma de Euler con una precisión de hasta dígitos, es necesario sumar dos series de FEE. Es decir, para ${\displaystyle n}$

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

${\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}).}$

La complejidad es

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

Para evaluar rápidamente la constante es posible aplicar la FEE a otras aproximaciones. ^[14] ${\displaystyle \gamma }$

Cálculo de FEE de determinadas series de potencias.

Por la FEE se calculan rápidamente las dos series siguientes:

${\displaystyle f_{1}=f_{1}(z)=\sum _{j=0}^{\infty }{\frac {a(j)}{b(j)}}z^{j},}$

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

bajo el supuesto de que son números enteros, ${\displaystyle a(j),\quad b(j)}$

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

y son constantes y es un número algebraico. La complejidad de la evaluación de la serie es ${\displaystyle C}$ ${\displaystyle z}$

${\displaystyle s_{f_{1}}(n)=O\left(M(n)\log ^{2}n\right),\,}$

${\displaystyle s_{f_{2}}(n)=O\left(M(n)\log n\right).}$

Cálculo de FEE de la constante clásica e.

Para la evaluación de la toma constante se utilizan términos de la serie de Taylor para ${\displaystyle e}$ ${\displaystyle m=2^{k},\quad k\geq 1}$ ${\displaystyle e,}$

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

Aquí elegimos , exigiendo que para el resto se cumpla la desigualdad . Este es el caso, por ejemplo, cuando tomamos un número tal que el número natural está determinado por las desigualdades: ${\displaystyle m}$ ${\displaystyle R_{m}}$ ${\displaystyle R_{m}\leq 2^{-n-1}}$ ${\displaystyle m\geq {\frac {4n}{\log n}}.}$ ${\displaystyle m=2^{k}}$ ${\displaystyle k}$

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

calculamos la suma

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

en pasos del siguiente proceso. ${\displaystyle k}$

Paso 1. Combinando los sumandos secuencialmente en pares sacamos de los paréntesis el factor común "obvio" y obtenemos ${\displaystyle S}$

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

Calcularemos sólo valores enteros de las expresiones entre paréntesis, es decir, los valores

${\displaystyle m,m-2,m-4,\dots .\,}$

Por lo tanto, en el primer paso la suma es ${\displaystyle S}$

${\displaystyle S=S(1)=\sum _{j=0}^{m_{1}-1}{\frac {1}{(m-1-2j)!}}\alpha _{m_{1}-j}(1),}$

${\displaystyle m_{1}={\frac {m}{2}},m=2^{k},k\geq 1.}$

En el primer paso números enteros de la forma. ${\displaystyle {\frac {m}{2}}}$

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

se calculan. Después actuamos de manera similar: combinando en cada paso los sumandos de la suma secuencialmente en pares, sacamos de los corchetes el factor común "obvio" y calculamos solo los valores enteros de las expresiones entre corchetes. Suponga que se completan los primeros pasos de este proceso. ${\displaystyle S}$ ${\displaystyle i}$

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

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

${\displaystyle m_{i+1}={\frac {m_{i}}{2}}={\frac {m}{2^{i+1}}},}$

calculamos sólo números enteros de la forma ${\displaystyle {\frac {m}{2^{i+1}}}}$

${\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,\dots ,\quad m_{i+1}-1,\quad m=2^{k},\quad k\geq i+1.}$

Aquí

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

es el producto de números enteros. ${\displaystyle 2^{i}}$

Etc.

Paso , el último. Calculamos un valor entero que calculamos, utilizando el algoritmo rápido descrito anteriormente, el valor y hacemos una división del número entero por el número entero con precisión de hasta dígitos. El resultado obtenido es la suma o la constante hasta dígitos. La complejidad de todos los cálculos es ${\displaystyle k}$ ${\displaystyle \alpha _{1}(k),}$ ${\displaystyle (m-1)!,}$ ${\displaystyle \alpha _{1}(k)}$ ${\displaystyle (m-1)!,}$ ${\displaystyle n}$ ${\displaystyle S,}$ ${\displaystyle e}$ ${\displaystyle n}$

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

Ver también

• Algoritmos rápidos
• método AGM
• Complejidad computacional

Referencias

1. EA Karatsuba, Evaluaciones rápidas de funciones trascendentales. Problema. Peredachi Informat., vol. 27, núm. 4, (1991)
2. DW Lozier y FWJ Olver, Evaluación numérica de funciones especiales. Matemáticas de la computación 1943-1993: medio siglo de matemáticas computacionales, W. Gautschi, eds., Proc. Simposios. Matemáticas aplicadas, AMS, vol. 48 (1994).
3. CL Siegel, Números trascendentales . Prensa de la Universidad de Princeton, Princeton (1949).
4. Karatsuba EA, Evaluación rápida de , Probl. Peredachi Informat., vol. 29, núm. 1 (1993) ${\displaystyle \zeta (3)}$
5. Ekatharine A. Karatsuba, Evaluación rápida de la función hipergeométrica mediante FEE. Métodos computacionales y teoría de funciones (CMFT'97), N. Papamichael, St. Ruscheweyh y EB Saff, eds., World Sc. Pub. (1999)
6. Catherine A. Karatsuba, Evaluación rápida de las funciones de Bessel. Transformaciones integrales y funciones especiales, vol. 1, núm. 4 (1993)
7. EA Karatsuba, Evaluación rápida de la función zeta de Riemann para valores enteros de argumento . Problema. Peredachi Informat., vol. 31, núm. 4 (1995). ${\displaystyle \zeta (s)}$ ${\displaystyle s}$
8. JM Borwein, DM Bradley y RE Crandall, Estrategias computacionales para la función zeta de Riemann. J. de Computación. Aplica. Matemáticas, vol. 121, núms. 1 y 2 (2000).
9. EA Karatsuba, Evaluación rápida de la función zeta de Hurwitz y serie Dirichlet, Problema. Peredachi Informat., vol. 34, núm. 4, págs. 342–353, (1998). ${\displaystyle L}$
10. EA Karatsuba, Cálculo rápido de algunas integrales especiales de física matemática. Computación científica, números validados, métodos de intervalo, W. Kramer, JW von Gudenberg, eds. (2001).
11. E. Bach, La complejidad de las constantes de la teoría de números. Información. Proc. Cartas, N° 62 (1997).
12. EA Karatsuba, Cálculo rápido de $\zeta(3)$ y de algunas integrales especiales, utilizando los polilogaritmos, la fórmula de Ramanujan y su generalización. J. de Matemáticas Numéricas BIT, vol. 41, núm. 4 (2001).
13. DH Bailey, PB Borwein y S. Plouffe, Sobre el cálculo rápido de varias constantes polilogarítmicas. Matemáticas. Comp., vol. 66 (1997).
14. RP Brent y EM McMillan, Algunos algoritmos nuevos para el cálculo de alta precisión de la constante de Euler. Matemáticas. Comp., vol. 34 (1980).

enlaces externos

• http://www.ccas.ru/personal/karatsuba/divcen.htm
• http://www.ccas.ru/personal/karatsuba/algen.htm