Метод БВЕ (быстрого вычисления E-функций) — метод быстрого суммирования специального вида рядов. Построен в 1990 году Е. А. Карацубой[1][2]. Позволяет вычислять быстро зигелевские E-функции, и в частности, .

Зигель назвал «E-функциями» класс функций, «похожих на экспоненциальные». Этому классу принадлежат такие высшие трансцендентные функции как гипергеометрические, сферические, цилиндрические функции и так далее.

Теорема

править

С помощью БВЕ можно доказать следующую теорему

Теорема.

Пусть   — простейшая трансцендентная функция, то есть экспоненциальная функция или тригонометрическая функция, или элементарная алгебраическая функция, или их суперпозиция, или обратная им функция или суперпозиция обратных функций. Тогда

 

Здесь   есть сложность вычисления (битовая) функции   с точностью до   знаков,   — сложность умножения двух  -значных чисел.

Алгоритмы, основанные на БВЕ, включают алгоритмы быстрого вычисления любой элементарной трансцендентной функции для любого аргумента, классических констант  ,  , постоянной Эйлера  , постоянных Апери[3] и Каталана, таких высших трансцендентных функций, как гамма-функции Эйлера и её производных, гипергеометрических функций[4], сферических функций, цилиндрических функций[5] и так далее для алгебраических значений аргумента и параметров, дзета-функции Римана для целых значений аргумента[6][7], дзета-функции Гурвица для целого аргумента и алгебраических значений параметра[8], а также таких специальных интегралов[9], как интеграл вероятности, интегралы Френеля, интегральная экспоненциальная функция, интегральные синус и косинус и так далее при алгебраических значениях аргумента с оценкой сложности вычисления, близкой к оптимальной, а именно  

В настоящее время только метод БВЕ даёт возможность быстро вычислять значения функций из класса высших трансцендентных функций[10], некоторые специальные интегралы математической физики и такие классические константы, как константы Эйлера, Каталана[11] и Апери. Дополнительным преимуществом метода БВЕ является возможность распараллеливания основанных на БВЕ алгоритмов.

БВЕ-вычисление классических констант

править

Для быстрого вычисления константы   можно воспользоваться формулой Эйлера   и применить БВЕ к суммированию рядов Тейлора для

 

 

с остаточными членами   для которых справедливы оценки

 

 

и при

 

 

Чтобы вычислить   посредством БВЕ, можно использовать также другие приближения[12]. Во всех случаях сложность

 

Чтобы вычислить постоянную Эйлера   с точностью до   знаков, нужно просуммировать с помощью БВЕ два ряда. А именно, при  

 

При этом

 

Для быстрого вычисления константы   можно также применить метод БВЕ к другому приближению[13]

БВЕ-вычисление некоторых степенных рядов

править

С помощью БВЕ можно вычислить быстро следующие два вида рядов:

 

 

при условии, что   — целые числа,   и   есть константы, и   есть алгебраическое число.

Сложность вычисления этих рядов

 

 

Детали БВЕ на примере быстрого вычисления константы

править

Для вычисления константы   возьмём  , членов ряда Тейлора для  

 

При этом выбираем   так, чтобы для остатка   выполнялось неравенство  . Это будет, например, когда  . Таким образом, возьмем   таким, что натуральное число   определяется неравенствами:

 

Будем вычислять сумму  

за   шагов следующего процесса.

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

 

 

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

Таким образом, на первом шаге сумма   преобразуется к виду

 

 

На первом шаге вычисляется только   целых чисел вида

 

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

Шаг   ( ).

 

 

мы вычисляем только   целых чисел вида

 

 

Здесь   есть произведение   целых чисел.

И так далее.

Последний,  -й шаг. Вычисляем одно целое значение  , вычисляем, пользуясь вышеописанным быстрым алгоритмом, значение  , и производим одно деление целого числа   на число   с точностью до   знаков. Получившийся результат и есть сумма  , или константа   с точностью до  . Сложность всех вычислений есть

 

Примечания

править
  1. Карацуба Е. А. Быстрое вычисление трансцендентных функций. Проблемы передачи информации, т. 27, № 4 (1991).
  2. Lozier D. W. and Olver F. W. J. Numerical Evaluation of Special Functions. Mathematics of Computation 1943—1993: A Half-Century of Computational Mathematics, W. Gautschi, eds., Proc. Sympos. Applied Mathematics, AMS, Vol. 48 (1994).
  3. Карацуба Е. А. Быстрое вычисление  . Проблемы передачи информации, т. 29, № 1 (1993).
  4. Karatsuba Ekatharine A. Fast evaluation of hypergeometric function by FEE. Computational Methods and Function Theory (CMFT’97), N. Papamichael, St. Ruscheweyh and E. B. Saff, eds., World Sc. Pub. (1999).
  5. Karatsuba Catherine A. Fast evaluation of Bessel functions. Integral Transforms and Special Functions, Vol. 1, № 4 (1993).
  6. Карацуба Е. А. Быстрое вычисление дзета-функции Римана   для целых значений аргумента  . Проблемы передачи информации, т. 31, № 4 (1995).
  7. Borwein J. M., Bradley D. M. and Crandall R. E. Computational strategies for the Riemann zeta function. J. of Comput. Appl. Math., Vol. 121, № 1-2 (2000).
  8. Карацуба Е. А. Быстрое вычисление дзета-функции Гурвица и  -рядов Дирихле. Проблемы передачи информации, т. 34, № 4 (1998).
  9. Karatsuba E. A. Fast computation of some special integrals of mathematical physics. Scientific Computing, Validated Numerics, Interval Methods, W. Kramer, J. W. von Gudenberg, eds. (2001).
  10. Bach E. The complexity of number-theoretic constants. Info. Proc. Letters, № 62 (1997).
  11. Karatsuba E. A. Fast computation of   and of some special integrals, using the polylogarithms, the Ramanujan formula and it’s generalization. J. of Numerical Mathematics BIT, Vol. 41, № 4 (2001).
  12. Bailey D. H., Borwein P. B. and Plouffe S. On the rapid computation of various polylogarithmic constants. Math. Comp., Vol. 66 (1997).
  13. Brent R. P. and McMillan E. M. Some new algorithms for high-precision computation of Euler’s constant. Math. Comp., Vol. 34 (1980).

Ссылки

править