FEE метод - FEE method

В математике 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).,}

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

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

[1] Е. А. Карацуба, Быстрые вычисления трансцендентных функций. Пробл. Передачи информ., Т. 27, № 4, (1991)

[2] Д. В. Лозье, Ф. В. Дж. Олвер, Численное вычисление специальных функций. Математика вычислений 1943–1993: полвека вычислительной математики, W. Gautschi, eds., Proc. Симпози. Прикладная математика, AMS, Vol. 48 (1994).

[3] К. Л. Сигель,Трансцендентные числа. Издательство Принстонского университета, Принстон (1949).

[4] Карацуба Э.А., Быстрая оценка ${displaystyle zeta (3)}$ , Пробл. Передачи информ., Т. 29, № 1 (1993)

[5] Ekatharine A. Karatsuba, Быстрое вычисление гипергеометрической функции методом FEE. Вычислительные методы и теория функций (CMFT'97), N. Papamichael, St. Ruscheweyh, E. B. Saff, eds., World Sc. Паб. (1999)

[6] Екатерина А. Карацуба, Быстрое вычисление функций Бесселя. Интегральные преобразования и специальные функции, Vol. 1, № 4 (1993)

[7] Э. А. Карацуба, Быстрое вычисление дзета-функции Римана ${displaystyle zeta (s)}$ для целых значений аргумента ${displaystyle s}$ . Пробл. Передачи информ., Т. 31, № 4 (1995).

[8] Дж. М. Борвейн, Д. М. Брэдли и Р. Э. Крэндалл, Вычислительные стратегии для дзета-функции Римана. J. of Comput. Appl. Math., Vol. 121, №1–2 (2000).

[9] Э. А. Карацуба, Быстрое вычисление дзета-функции Гурвица и Дирихле ${displaystyle L}$ -серия, Проблема. Передачи информ., Т. 34, No. 4, pp. 342–353, (1998).

[10] Е. А. Карацуба, Быстрое вычисление некоторых специальных интегралов математической физики. Научные вычисления, подтвержденные числа, интервальные методы, В. Крамер, Дж. В. фон Гуденберг, редакторы (2001).

[11] Э. Бах, Сложность теоретико-числовых констант. Информация. Proc. Письма, № 62 (1997).

[12] Е. А. Карацуба, Быстрое вычисление $ zeta (3) $ и некоторых специальных интегралов с использованием полилогарифмов, формулы Рамануджана и ее обобщений.J. вычислительной математики BIT, Vol. 41, № 4 (2001).

[13] Д. Х. Бейли, П. Б. Борвейн и С. Плафф, О быстром вычислении различных полилогарифмических констант. Math.Comp., Vol. 66 (1997).

[14] Р. П. Брент и Э. М. Макмиллан, Некоторые новые алгоритмы для высокоточного вычисления постоянной Эйлера. Математика. Comp., Vol. 34 (1980).

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]