Метод БВЕ

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

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

Теорема

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

Теорема.

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

$s_f(n)=O(M(n){\log }^{2}n).$

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

Алгоритмы, основанные на БВЕ, включают алгоритмы быстрого вычисления любой элементарной трансцендентной функции для любого аргумента, классических констант $e$, $\pi$, постоянной Эйлера $\gamma$, постоянных Апери и Каталана, таких высших трансцендентных функций, как гамма-функции Эйлера и её производных, гипергеометрических функций, сферических функций, цилиндрических функций и так далее для алгебраических значений аргумента и параметров, дзета-функции Римана для целых значений аргумента, дзета-функции Гурвица для целого аргумента и алгебраических значений параметра, а также таких специальных интегралов, как интеграл вероятности, интегралы Френеля, интегральная экспоненциальная функция, интегральные синус и косинус и так далее при алгебраических значениях аргумента с оценкой сложности вычисления, близкой к оптимальной, а именно $s_f(n)=O(M(n){\log }^{2}n).$

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

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

Для быстрого вычисления константы $\pi$ можно воспользоваться формулой Эйлера $\frac{\pi }{4}=\mathrm{a}\mathrm{r}\mathrm{c}\mathrm{t}\mathrm{g}\frac{1}{2}+\mathrm{a}\mathrm{r}\mathrm{c}\mathrm{t}\mathrm{g}\frac{1}{3},$ и применить БВЕ к суммированию рядов Тейлора для

$\mathrm{a}\mathrm{r}\mathrm{c}\mathrm{t}\mathrm{g}\frac{1}{2}=\frac{1}{1\cdot 2}-\frac{1}{3\cdot 2^3}+\dots +\frac{(-1{)}^{r-1}}{(2r-1)2^{2r-1}}+R_1,$

$\mathrm{a}\mathrm{r}\mathrm{c}\mathrm{t}\mathrm{g}\frac{1}{3}=\frac{1}{1\cdot 3}-\frac{1}{3\cdot 3^3}+\dots +\frac{(-1{)}^{r-1}}{(2r-1)3^{2r-1}}+R_2,$

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

$|R_1|⩽\frac{4}{5}\frac{1}{2r+1}\frac{1}{2^{2r+1}};$

$|R_2|⩽\frac{9}{10}\frac{1}{2r+1}\frac{1}{3^{2r+1}};$

и при

$r=n,$

$4(|R_1|+|R_2|)<2^{-n}.$

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

$s_{\pi }=O(M(n){\log }^{2}n).$

Чтобы вычислить постоянную Эйлера $\gamma$ с точностью до $n$ знаков, нужно просуммировать с помощью БВЕ два ряда. А именно, при $m=6n,k=n,k⩾1,$

$\gamma =-\log n\sum _{r=0}^{12n}\frac{(-1{)}^r{n}^{r+1}}{(r+1)!}+\sum _{r=0}^{12n}\frac{(-1{)}^r{n}^{r+1}}{(r+1)!(r+1)}+O(2^{-n}).$

При этом

$s_{\gamma }=O(M(n){\log }^{2}n).$

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

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

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

$f_1=f_1(z)=\sum _{j=0}^{\mathrm{\infty }}\frac{a(j)}{b(j)}{z}^j,$

$f_2=f_2(z)=\sum _{j=0}^{\mathrm{\infty }}\frac{a(j)}{b(j)}\frac{z^j}{j!},$

при условии, что $a(j),b(j)$ — целые числа, $|a(j)|+|b(j)|⩽(Cj{)}^K;|z|<1;K$ и $C$ есть константы, и $z$ есть алгебраическое число.

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

$s_{f_1}(n)=O(M(n){\log }^{2}n),$

$s_{f_2}(n)=O(M(n)\log n).$

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

Для вычисления константы $e$ возьмём $m=2^k,k⩾1$, членов ряда Тейлора для $e,$

$e=1+\frac{1}{1!}+\frac{1}{2!}+\dots +\frac{1}{(m-1)!}+R_m.$

При этом выбираем $m$ так, чтобы для остатка $R_m$ выполнялось неравенство $R_m⩽2^{-n-1}$. Это будет, например, когда $m⩾\frac{4n}{\log n}$. Таким образом, возьмем $m=2^k$ таким, что натуральное число $k$ определяется неравенствами:

$2^k⩾\frac{4n}{\log n}>2^{k-1}.$

Будем вычислять сумму $S=1+\frac{1}{1!}+\frac{1}{2!}+\dots +\frac{1}{(m-1)!}=\sum _{j=0}^{m-1}\frac{1}{(m-1-j)!},$

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

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

$S=(\frac{1}{(m-1)!}+\frac{1}{(m-2)!})+(\frac{1}{(m-3)!}+\frac{1}{(m-4)!})+\dots =$

$=\frac{1}{(m-1)!}(1+m-1)+\frac{1}{(m-3)!}(1+m-3)+\dots$

Будем вычислять только целые значения выражений, стоящих в скобках, то есть значения $m,m-2,m-4,\dots$

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

$S=S(1)=\sum _{j=0}^{m_1-1}\frac{1}{(m-1-2j)!}{\alpha }_{m_1-j}(1),$

$m_1=\frac{m}{2},m=2^k,k⩾1.$

На первом шаге вычисляется только $\frac{m}{2}$ целых чисел вида

${\alpha }_{m_1-j}(1)=m-2j,j=0,1,\dots ,m_1-1,$

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

Шаг $i+1$ ($i+1⩽k$).

$S=S(i+1)=\sum _{j=0}^{m_{i+1}-1}\frac{1}{(m-1-2^{i+1}j)!}{\alpha }_{m_{i+1}-j}(i+1),$

$m_{i+1}=\frac{m_i}{2}=\frac{m}{2^{i+1}},$

мы вычисляем только $\frac{m}{2^{i+1}}$ целых чисел вида

${\alpha }_{m_{i+1}-j}(i+1)={\alpha }_{m_i-2j}(i)+{\alpha }_{m_i-(2j+1)}(i)\frac{(m-1-2^{i+1}j)!}{(m-1-2^i-2^{i+1}j)!},$

$j=0,1,\dots ,m_{i+1}-1,m=2^k,k⩾i+1.$

Здесь $\frac{(m-1-2^{i+1}j)!}{(m-1-2^i-2^{i+1}j)!}$ есть произведение $2^i$ целых чисел.

И так далее.

Последний, $k$-й шаг. Вычисляем одно целое значение ${\alpha }_1(k)$, вычисляем, пользуясь вышеописанным быстрым алгоритмом, значение $(m-1)!$, и производим одно деление целого числа ${\alpha }_1(k)$ на число $(m-1)!$ с точностью до $n$ знаков. Получившийся результат и есть сумма $S$, или константа $e$ с точностью до $2^{-n}$. Сложность всех вычислений есть

$O(M(m){\log }^{2}m)=O(M(n)\log n).$

Ссылки

• http://www.ccas.ru/personal/karatsuba/alg.htm