FEE метод

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

Класс функций, которые «похожи на экспоненциальную функцию», был назван Зигелем «E-функциями» . ^[3] Среди этих функций есть такие специальные функции, как гипергеометрическая функция , цилиндр , сферические функции и так далее.

Используя FEE, можно доказать следующую теорему:

Теорема : Пусть будет элементарная трансцендентная функция , то есть экспоненциальная функция , или тригонометрическая функция , или элементарная алгебраическая функция , или их суперпозиция, или их обратная , или суперпозиция обратных. Затем${\ Displaystyle у = е (х)}$

${\ Displaystyle s_ {е} (п) = О (М (п) \ журнал ^ {2} п). \,}$

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

Алгоритмы , основанные на методе СБОРАХ включают в себя алгоритмы для быстрого вычисления любой элементарной функции трансцендентной для любого значения аргумента, классические константы е , постоянная Эйлера Каталонская и константы обезьяньего питомника , ^[4] такие высшие функций трансцендентных как Эйлер гамма-функция и ее производные, гипергеометрические , ^[5] сферические , цилиндрические (включая функции Бесселя ) ^[6] и некоторые другие функции для алгебраических значений аргумента и параметров,${\ displaystyle \ pi,}$ ${\ displaystyle \ gamma,}$ Дзета-функция Римана для целых значений аргумента ^{[7] [8]} и дзета-функция Гурвица для целочисленного аргумента и алгебраических значений параметра ^[9], а также такие специальные интегралы, как интеграл вероятности , интегралы Френеля , интеграл экспоненциальная функция , тригонометрические интегралы и некоторые другие интегралы ^[10] для алгебраических значений аргумента с оценкой сложности, близкой к оптимальной, а именно

${\ Displaystyle s_ {е} (п) = О (М (п) \ журнал ^ {2} п). \,}$

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

FEE-вычисление классических констант [ править ]

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

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

${\ displaystyle \ arctan {\ frac {1} {3}} = {\ frac {1} {1 \ cdot 3}} - {\ frac {1} {3 \ cdot 3 ^ {3}}} + \ cdots + {\ 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}.}$

Для расчета по FEE можно использовать и другие приближения ^[13] Во всех случаях сложность${\displaystyle \pi }$

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

Чтобы вычислить гамму константы Эйлера с точностью до цифр, необходимо суммировать по FEE два ряда. А именно для${\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).\,}$

Чтобы быстро оценить константу, можно применить FEE к другим приближениям. ^[14]${\displaystyle \gamma }$

FEE-расчет определенного степенного ряда [ править ]

По FEE быстро рассчитываются две следующие серии:

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

Детали FEE на примере быстрого вычисления классической константы e [ править ]

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

${\displaystyle e=1+{\frac {1}{1!}}+{\frac {1}{2!}}+\cdots +{\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!}}+\cdots +{\frac {1}{(m-1)!}}=\sum _{j=0}^{m-1}{\frac {1}{(m-1-j)!}},}$

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

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

${\displaystyle {\begin{aligned}S&=\left({\frac {1}{(m-1)!}}+{\frac {1}{(m-2)!}}\right)+\left({\frac {1}{(m-3)!}}+{\frac {1}{(m-4)!}}\right)+\cdots \\&={\frac {1}{(m-1)!}}(1+m-1)+{\frac {1}{(m-3)!}}(1+m-3)+\cdots .\end{aligned}}}$

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

${\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 n}$

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

См. Также [ править ]

• Быстрые алгоритмы
• Метод AGM
• Вычислительная сложность

Ссылки [ править ]

Внешние ссылки [ править ]

• http://www.ccas.ru/personal/karatsuba/divcen.htm
• http://www.ccas.ru/personal/karatsuba/algen.htm