Интернет магазин китайских планшетных компьютеров



Компьютеры - Метод БВЕ

23 января 2011


Оглавление:
1. Метод БВЕ
2. БВЕ-вычисление классических констант
3. Детали БВЕ на примере быстрого вычисления константы e



Метод БВЕ — это метод быстрого суммирования специального вида рядов. Он был построен в 1990 Е.А. Карацубой и назван БВЕ — Быстрого Вычисления Е-функций — потому, что позволяет вычислять быстро Зигелевские E-функции, и в частности, e.


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


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

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

sf = Ologn).

Здесь sf есть сложность вычисления функции f с точностью до n знаков, M --- сложность умножения двух n-значных чисел.

Алгоритмы, основанные на БВЕ включают алгоритмы быстрого вычисления любой элементарной трансцендентной функции для любого аргумента, классических констант e, π, постоянной Эйлера γ, постоянных Апери и Каталана, таких высших трансцендентных функций, как гамма-функции Эйлера и её производных, гипергеометрических функций , сферических функций, цилиндрических функций и т.д. для алгебраических значений аргумента и параметров, дзета-функции Римана для целых значений аргумента , дзета-функции Гурвица для целого аргумента и алгебраических значений параметра, а также таких специальных интегралов, как интеграл вероятности, интегралы Френеля, интегральная экспоненциальная функция, интегральные синус и косинус и т.д. при алгебраических значениях аргумента с оценкой сложности вычисления, близкой к оптимальной, а именно


sf = Ologn).

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



Просмотров: 1456


<<< Быстрые алгоритмы
Метод умножения Шёнхаге Штрассена >>>