Метод БВЕ (быстрого вычисления E-функций) — метод быстрого суммирования специального вида рядов. Построен в 1990 году Е. А. КарацубойКарацуба Е. А. Быстрое вычисление трансцендентных функций. Проблемы передачи информации, т. 27, № 4 (1991).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).. Позволяет вычислять быстро зигелевские E-функции, и в частности, .

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

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

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

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

Алгоритмы, основанные на БВЕ, включают алгоритмы быстрого вычисления любой элементарной трансцендентной функции для любого аргумента, классических констант , , постоянной Эйлера , постоянных АпериКарацуба Е. А. Быстрое вычисление . Проблемы передачи информации, т. 29, № 1 (1993). и Каталана, таких высших трансцендентных функций, как гамма-функции Эйлера и её производных, гипергеометрических функций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)., сферических функций, цилиндрических функцийKaratsuba Catherine A. Fast evaluation of Bessel functions. Integral Transforms and Special Functions, Vol. 1, № 4 (1993). и так далее для алгебраических значений аргумента и параметров, дзета-функции Римана для целых значений аргументаКарацуба Е. А. Быстрое вычисление дзета-функции Римана для целых значений аргумента . Проблемы передачи информации, т. 31, № 4 (1995).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)., дзета-функции Гурвица для целого аргумента и алгебраических значений параметраКарацуба Е. А. Быстрое вычисление дзета-функции Гурвица и -рядов Дирихле. Проблемы передачи информации, т. 34, № 4 (1998)., а также таких специальных интегралов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)., как интеграл вероятности, интегралы Френеля, интегральная экспоненциальная функция, интегральные синус и косинус и так далее при алгебраических значениях аргумента с оценкой сложности вычисления, близкой к оптимальной, а именно

В настоящее время только метод БВЕ даёт возможность быстро вычислять значения функций из класса высших трансцендентных функцийBach E. The complexity of number-theoretic constants. Info. Proc. Letters, № 62 (1997)., некоторые специальные интегралы математической физики и такие классические константы, как константы Эйлера, Каталана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). и Апери. Дополнительным преимуществом метода БВЕ является возможность распараллеливания основанных на БВЕ алгоритмов.

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

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

и при

Чтобы вычислить посредством БВЕ, можно использовать также другие приближенияBailey D. H., Borwein P. B. and Plouffe S. On the rapid computation of various polylogarithmic constants. Math. Comp., Vol. 66 (1997).. Во всех случаях сложность

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

При этом

Для быстрого вычисления константы можно также применить метод БВЕ к другому приближениюBrent R. P. and McMillan E. M. Some new algorithms for high-precision computation of Euler’s constant. Math. Comp., Vol. 34 (1980).

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

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

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

Детали БВЕ на примере быстрого вычисления константы e Для вычисления константы возьмём , членов ряда Тейлора для

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

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

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

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

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

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

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

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

Шаг ().

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

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

И так далее.

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

Примечания

Ссылки http://www.ccas.ru/personal/karatsuba/alg.htm

Категория:Вычислительная математика Категория:Длинная арифметика Категория:Алгоритмы вычисления числа пи