08-07-2023
Метод БВЕ — это метод быстрого суммирования специального вида рядов. Он был построен в 1990 Е.А. Карацубой[1] [2] и назван БВЕ — Быстрого Вычисления Е-функций — потому, что позволяет вычислять быстро Зигелевские -функции, и в частности, .
Зигель назвал "E -функциями" класс функций,"похожих на экспоненциальную". К ним принадлежат такие высшие трансцендентные функции как гипергеометрические, сферические, цилиндрические функции и т.д.
С помощью БВЕ можно доказать следующую теорему
Теорема. Пусть --- простейшая трансцендентная функция, т.е. экспоненциальная функция или тригонометрическая функция, или элементарная алгебраическая функция, или их суперпозиция, или обратная им функция или суперпозиция обратных функций. Тогда
Здесь есть сложность вычисления (битовая) функции с точностью до знаков, --- сложность умножения двух -значных чисел.
Алгоритмы, основанные на БВЕ включают алгоритмы быстрого вычисления любой элементарной трансцендентной функции для любого аргумента, классических констант , , постоянной Эйлера , постоянных Апери[3] и Каталана, таких высших трансцендентных функций, как гамма-функции Эйлера и её производных, гипергеометрических функций [4], сферических функций, цилиндрических функций[5] и т.д. для алгебраических значений аргумента и параметров, дзета-функции Римана для целых значений аргумента[6] [7], дзета-функции Гурвица для целого аргумента и алгебраических значений параметра[8], а также таких специальных интегралов[9], как интеграл вероятности, интегралы Френеля, интегральная экспоненциальная функция, интегральные синус и косинус и т.д. при алгебраических значениях аргумента с оценкой сложности вычисления, близкой к оптимальной, а именно
В настоящее время только метод БВЕ даёт возможность быстро вычислять значения функций из класса высших трансцендентных функций[10], некоторые специальные интегралы математической физики и такие классические константы, как константы Эйлера, Каталана[11] и Апери. Дополнительным преимуществом метода БВЕ является возможность распараллеливания основанных на БВЕ алгоритмов.
Содержание |
Для быстрого вычисления константы можно воспользоваться формулой Эйлера
и применить БВЕ к суммированию рядов Тейлора для
с остаточными членами для которых справедливы оценки
и при
Чтобы вычислить посредством БВЕ, можно использовать также другие приближения[12] Во всех случаях сложность
Чтобы вычислить постоянную Эйлера гамма с точностью до знаков, нужно просуммировать с помощью БВЕ два ряда. А именно, при
При этом
Для быстрого вычисления константы можно также применить метод БВЕ к другому приближению [13]
С помощью БВЕ можно вычислить быстро следующие два вида рядов:
при условии, что --- целые числа, и есть константы, и есть алгебраическое число.
Сложность вычисления этих рядов
Для вычисления константы возьмём , членов ряда Тейлора для
При этом выбираем так, чтобы для остатка выполнялось неравенство . Это будет, например, когда . Таким образом, возьмем таким, что натуральное число определяется неравенствами:
Будем вычислять сумму
за шагов следующего процесса.
Шаг 1. Объединяя слагаемые последовательно попарно и вынося за скобки "очевидный" общий множитель, получаем
Будем вычислять только целые значения выражений, стоящих в скобках, т.е. значения
Таким образом, на первом шаге сумма преобразуется к виду
На первом шаге вычисляется только целых чисел вида
Далее мы действуем аналогично: объединяя на каждом шаге слагаемые суммы последовательно попарно, мы выносим за скобки "очевидный" общий множитель и вычисляем только целые значения выражений в скобках. Пусть сделано шагов такого процесса.
Шаг ().
мы вычисляем только целых чисел вида
Здесь есть произведение целых чисел.
И т.д.
Последний, -й шаг. Вычисляем одно целое значение , вычисляем, пользуясь вышеописанным быстрым алгоритмом, значение , и производим одно деление целого числа на число с точностью до знаков. Получившийся результат и есть сумма , или константа с точностью до . Сложность всех вычислений есть
http://www.ccas.ru/personal/karatsuba/alg.htm
Метод БВЕ.