WikiSort.ru - Не сортированное

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

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

Теорема

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

Теорема.

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

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

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

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

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

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

Для быстрого вычисления константы ${\displaystyle \pi }$ можно воспользоваться формулой Эйлера ${\displaystyle {\frac {\pi }{4}}=\arctan {\frac {1}{2}}+\arctan {\frac {1}{3}},}$

и применить БВЕ к суммированию рядов Тейлора для

${\displaystyle \arctan {\frac {1}{2}}={\frac {1}{1*2}}-{\frac {1}{3*2^{3}}}+\dots +{\frac {(-1)^{r-1}}{(2r-1)2^{2r-1}}}+R_{1},}$

${\displaystyle \arctan {\frac {1}{3}}={\frac {1}{1*3}}-{\frac {1}{3*3^{3}}}+\dots +{\frac {(-1)^{r-1}}{(2r-1)3^{2r-1}}}+R_{2},}$

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

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

${\displaystyle |R_{2}|\leq {\frac {9}{10}}{\frac {1}{2r+1}}{\frac {1}{3^{2r+1}}};}$

и при

${\displaystyle r=n,}$

${\displaystyle 4(|R_{1}|+|R_{2}|)\ <\ 2^{-n}.}$

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

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

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

${\displaystyle \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}).}$

При этом

${\displaystyle s_{\gamma }=O(M(n)\log ^{2}n).}$ Для быстрого вычисления константы ${\displaystyle \gamma }$ можно также применить метод БВЕ к другому приближению^[13]

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

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

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

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

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

Сложность вычисления этих рядов ${\displaystyle s_{f_{1}}(n)=O\left(M(n)\log ^{2}n\right),}$

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle m,m-2,m-4,\dots .}$

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

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

${\displaystyle m_{1}={\frac {m}{2}},m=2^{k},k\geq 1.}$

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

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

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

Шаг ${\displaystyle i+1}$ (${\displaystyle i+1\leq k}$ ).

${\displaystyle 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),}$

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

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

${\displaystyle \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)!}},}$

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

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

И так далее.

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

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

Примечания

См. также

• Быстрые алгоритмы
• АГС метод Гаусса
• Сложность вычисления (битовая)

Ссылки

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