Метод БВЕ

Метод БВЕ (быстрого вычисления 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 {arctg} {\frac {1}{2}}+\mathrm {arctg} {\frac {1}{3}},$ и применить БВЕ к суммированию рядов Тейлора для

$\mathrm {arctg} {\frac {1}{2}}={\frac {1}{1\cdot 2}}-{\frac {1}{3\cdot 2^{3}}}+\ldots +{\frac {(-1)^{r-1}}{(2r-1)2^{2r-1}}}+R_{1},$

$\mathrm {arctg} {\frac {1}{3}}={\frac {1}{1\cdot 3}}-{\frac {1}{3\cdot 3^{3}}}+\ldots +{\frac {(-1)^{r-1}}{(2r-1)3^{2r-1}}}+R_{2},$

с остаточными членами $R_{1},\ R_{2},$ для которых справедливы оценки

$|R_{1}|\leqslant {\frac {4}{5}}{\frac {1}{2r+1}}{\frac {1}{2^{2r+1}}};$

$|R_{2}|\leqslant {\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\geqslant 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}^{\infty }{\frac {a(j)}{b(j)}}z^{j},$

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

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

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

$s_{f_{1}}(n)=O\left(M(n)\log ^{2}n\right),$

$s_{f_{2}}(n)=O\left(M(n)\log n\right).$

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

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

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

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

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

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

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

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

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

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

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

Таким образом, на первом шаге сумма $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\geqslant 1.$

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

$\alpha _{m_{1}-j}(1)=m-2j,\quad j=0,\;1,\;\ldots ,\;m_{1}-1,$

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

Шаг $i+1$ ($i+1\leqslant 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,\;\ldots ,\quad m_{i+1}-1,\quad m=2^{k},\quad k\geqslant 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\left(M(m)\log ^{2}m\right)=O\left(M(n)\log n\right).$

Ссылки

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