WikiDer > FEE метод

В математике FEE метод - метод быстрого суммирования рядов специального вида. Он был построен в 1990 г. Екатерина Александровна Карацуба^[1][2] и был назван ПЛАТЕЖ – быстрая оценка E-функции - потому что он выполняет быстрые вычисления Зигеля ${displaystyle E}$ -функции возможно, и в частности ${displaystyle e ^ {x}.}$

Класс функций, которые «похожи на экспоненциальную функцию» получил название «E-функции». Сигель.^[3] Среди этих функций есть такие специальные функции как гипергеометрическая функция, цилиндр, сферический функции и так далее.

Используя FEE, можно доказать следующую теорему:

Теорема: Позволять ${displaystyle y = f (x)}$ быть элементарный трансцендентная функция, это экспоненциальная функция, или тригонометрическая функция, или элементарная алгебраическая функция, или их суперпозиция, или их обратный, или суперпозиция обратных. потом

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

Здесь ${displaystyle s_ {f} (n)}$ это сложность вычисления (бит) функции ${displaystyle f (x)}$ с точностью до ${displaystyle n}$ цифры ${displaystyle M (n)}$ сложность умножения двух ${displaystyle n}$-значные целые числа.

Алгоритмы, основанные на методе FEE, включают в себя алгоритмы для быстрого вычисления любых элементарных трансцендентная функция для любого значения аргумента классические константы е, ${displaystyle pi,}$ то Постоянная Эйлера ${displaystyle gamma,}$ то Каталонский и Константы Апери,^[4] такие высшие трансцендентные функции, как Гамма-функция Эйлера и его производные, гипергеометрический,^[5] сферический, цилиндр (включая Бессель)^[6] функции и некоторые другие функции дляалгебраический значения аргумента и параметров, Дзета-функция Римана для целых значений аргумента^[7][8] и Дзета-функция Гурвица для целочисленного аргумента и алгебраических значений параметра,^[9] а также такие специальные интегралы, как интеграл вероятности, то Интегралы Френеля, то интегральная экспоненциальная функция, то тригонометрические интегралы, и некоторые другие интегралы^[10] для алгебраических значений аргумента с оценкой сложности, близкой к оптимальной, а именно

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

В настоящий момент,^{[когда?]} только FEE позволяет быстро вычислить значения функций из класса высших трансцендентных функций,^[11] некоторые специальные интегралы математической физики и такие классические константы, как константы Эйлера, Каталонии^[12] и константы Апери. Дополнительным преимуществом метода FEE является возможность распараллеливания алгоритмов на основе FEE.

FEE-вычисление классических констант

Для быстрой оценки постоянной ${displaystyle pi,}$ можно использовать формулу Эйлера${displaystyle {frac {pi} {4}} = arctan {frac {1} {2}} + arctan {frac {1} {3}},}$и применить FEE для суммирования ряда Тейлора для

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

с остальными условиями ${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}}};}$

и для

${displaystyle r = n ,,}$

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

Вычислять ${displaystyle pi}$ по БЕСПЛАТНОМУ можно использовать и другие приближения^[13] Во всех случаях сложность

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

Для вычисления постоянной гаммы Эйлера с точностью до ${displaystyle n}$цифр, следует суммировать ПКО две серии. А именно для

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

${displaystyle gamma = -log nsum _ {r = 0} ^ {12n} {frac {(-1) ^ {r} n ^ {r + 1}} {(r + 1)!}} + sum _ {r = 0} ^ {12n} {гидроразрыв {(-1) ^ {r} n ^ {r + 1}} {(r + 1)! (R + 1)}} + O (2 ^ {- n}) .}$

Сложность

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

Чтобы быстро оценить константу ${displaystyle gamma}$ можно применить FEE к другим приближениям.^[14]

FEE-расчет определенного степенного ряда

По FEE быстро рассчитываются две следующие серии:

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

в предположении, что ${displaystyle a (j), quad b (j)}$ целые числа,

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

и ${displaystyle C}$ - константы, а ${displaystyle z}$ - алгебраическое число. Сложность оценки серии составляет

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

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

Детали FEE на примере быстрого вычисления классической постоянной е

Для оценки постоянной ${displaystyle e}$ взять ${displaystyle m = 2 ^ {k}, quad kgeq 1}$, члены ряда Тейлора для ${displaystyle e,}$

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

Здесь мы выбираем ${displaystyle m}$, требуя, чтобы для оставшейся части ${displaystyle R_ {m}}$ неравенство ${displaystyle R_ {m} leq 2 ^ {- n-1}}$ выполняется. Так обстоит дело, например, когда ${displaystyle mgeq {frac {4n} {log n}}.}$ Таким образом, мы берем ${displaystyle m = 2 ^ {k}}$такое, что натуральное число ${displaystyle k}$ определяется неравенствами:

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

Рассчитываем сумму

${displaystyle S = 1 + {frac {1} {1!}} + {frac {1} {2!}} + cdots + {frac {1} {(m-1)!}} = сумма _ {j = 0} ^ {m-1} {frac {1} {(m-1-j)!}},}$

в ${displaystyle k}$ шаги следующего процесса.

Шаг 1. Объединение в ${displaystyle S}$ слагаемые последовательно попарно выносим за скобки «очевидный» общий множитель и получаем

${displaystyle {egin {align} 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 {выровнено}}}$

Мы будем вычислять только целые значения выражений в скобках, то есть значения

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

Таким образом, на первом этапе сумма ${displaystyle S}$ в

${displaystyle S = S (1) = sum _ {j = 0} ^ {m_ {1} -1} {frac {1} {(m-1-2j)!}} альфа _ {m_ {1} -j } (1),}$

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

На первом этапе ${displaystyle {frac {m} {2}}}$ целые числа формы

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

рассчитаны. После этого действуем аналогично: на каждом шаге объединяем слагаемые суммы ${displaystyle S}$ последовательно попарно вынимаем из скобок «очевидный» общий множитель и вычисляем только целые значения выражений в скобках. Предположим, что первый ${displaystyle i}$ шаги этого процесса завершены.

Шаг ${displaystyle i + 1}$ (${displaystyle i + 1leq k}$).

${displaystyle S = S (i + 1) = sum _ {j = 0} ^ {m_ {i + 1} -1} {frac {1} {(m-1-2 ^ {i + 1} j)! }} альфа _ {m_ {i + 1} -j} (i + 1),}$

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

мы вычисляем только ${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 ) {гидроразрыв {(m-1-2 ^ {i + 1} j)!} {(m-1-2 ^ {i} -2 ^ {i + 1} j)!}},}$

${displaystyle j = 0,1, точки, quad m_ {i + 1} -1, quad m = 2 ^ {k}, quad kgeq i + 1.}$

Здесь

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

это продукт ${displaystyle 2 ^ {i}}$ целые числа.

И т.п.

Шаг ${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 Oleft (M (m) log ^ {2} might) = Oleft (M (n) log night).,}$

Смотрите также

• Быстрые алгоритмы
• Метод AGM
• Вычислительная сложность

Рекомендации

внешняя ссылка

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