| Математические заметки |
|
|
|
|
|
О сложности вычисления “сжатых” степенных рядов Е. А. Карацуба Вычислительный центр им. А. А. Дородницына РАН, г. Москва
Англоязычная версия:
Mathematical Notes, 2023, Volume 114, Issue 1, Pages DOI: https://doi.org/10.1134/S000143462307009X 
Реферативные базы данных:
  1. Введение. Основные определения. Быстрые алгоритмы. Метод БВЕПод “сжатыми” степенными рядами будем иметь в виду ряды вида
$$
\begin{equation}
W_r(x)=\sum_{j=0}^\infty\,d(j)x^{j^r}, \qquad |x|<1, \quad r =2,3,\dots\,.
\end{equation}
\tag{1}
$$
Такие ряды возникают в разных областях математики и физики. В теории чисел и теории специальных функций такими рядами являются: эйлерова тэта-функция и тэта-ряды Якоби (см.,например, [1]), а также функция, введенная Риманом (см.,например, [2]), Очевидно, что если положить в (2) $y=e^{-\pi x}$, можно рассматривать (2) в качестве ряда $W_2(y)$. Такие ряды и суммы встречаются в квантовой физике, например, в квантовой оптике (см. [3], [4]). Настоящая статья посвящена проблеме быстрого (или эффективного) вычисления ряда (1) и оценке сложности такого вычисления для аргумента $x$ разной арифметической природы. Под алгоритмом ниже предполагается правило или способ вычисления без формализации этого понятия. Далее считаем, что числа записаны в двоичной системе счисления, знаки которой $0$ и $1$ называются битами. Определение 1. Запись знаков $0$, $1$, плюс, минус, скобка; сложение, вычитание и умножение двух битов называется одной элементарной или битовой операцией (далее – просто операцией). Пусть $y=f(x)$ есть вещественная функция вещественного переменного $x$, $a\leqslant x\leqslant b$, которая на интервале $(a,b)$ удовлетворяет условию Липшица порядка $\alpha$, $0<\alpha<1$, так что при $x_1,x_2\in(a,b)$: $|f(x_1)-f(x_2)|\leqslant|x_1-x_2|^\alpha$. Пусть $n$ – натуральное число. Определение 2. Вычислить функцию $y=f(x)$ в точке $x=x_0\in(a,b)$ с точностью до $n$ знаков, значит найти такое число $A$, что $|f(x_0)-A|\leqslant 2^{-n}$. Определение 3. Количество операций, достаточное для вычисления функции $f(x)$ в точке $x=x_0$ с точностью до $n$ знаков посредством данного алгоритма, называется сложностью вычисления $f(x)$ в точке $x_0$ и обозначается $s_f(n)=s_{f,x_0}(n)$. Сложность умножения двух $n$-значных чисел получила специальное обозначение $M(n)$. Сложность школьного метода умножения оценивается как В 1960 г. (см. [5]–[8]) А. А. Карацуба нашел первый быстрый метод умножения двух $n$-значных чисел с оценкой сложности открыв тем самым новое направление в математике – быстрые алгоритмы или быстрые вычисления. В зарубежной литературе метод А. А. Карацубы получил несколько наименований, самыми распространенными из которых являются “divide and conquer” и “binary splitting”, а его развитие и усовершенствование привело к созданию новых быстрых алгоритмов, в частности, быстрых алгоритмов умножения с лучшей оценкой сложности (см. [9]–[11]). Далее считаем, что для сложности умножения справедлива оценка Шенхаге–Штрассена (см. [10])Определение 4. Назовем быстрым такой алгоритм вычисления функции $f$, что для этого алгоритма где $C$ есть константа. Тем самым, сложность какого-либо быстрого алгоритма оценивается следующим образом: для любого $\varepsilon >0$ и $n>n_1(\varepsilon)$, $n\to\infty$.Для быстрого вычисления широкого класса простейших и высших трансцендентных функций автором был построен (см. [12]–[18]) новый метод – метод БВЕ – Быстрого Вычисления Е-функций (о Е-функциях Зигеля см. [19]). Применяя БВЕ, можно вычислить любую элементарную трансцендентную функцию для любого аргумента, классические константы $e$, $\pi$, постоянную Эйлера $\gamma$, постоянные Апери и Каталана, такие высшие трансцендентные функции как гамма-функцию Эйлера, гипергеометрические функции, сферические функции, цилиндрические функции и т.д. для алгебраических значений аргумента и параметров, дзета-функцию Римана для целых значений аргумента, дзета-функцию Гурвица для целого аргумента и алгебраических значений параметра, а также такие специальные интегралы, как интеграл вероятности, интегралы Френеля, интегральную экспоненциальную функцию, интегральные синус и косинус и т.д. с оценкой сложности не хуже, чем Метод БВЕ – это метод суммирования рядов специального вида. Рассмотрим степенной ряд $f$, $f=f(z)=\sum_{j=0}^\infty\,d(j)z^j$. Пусть $R=1/\varlimsup_{j\to\infty}\sqrt[j]{|d(j)|}$ есть радиус сходимости этого ряда. Предположим, что $|z|\leqslant R-\delta$, $0<\delta<R$, $\delta$ – некоторая константа. Тогда существует такая константа $A\geqslant 1$, что Поэтому, чтобы вычислить функцию $f$ в точке $z$ с точностью $2^{-n}$, достаточно вычислить с точностью $2^{-n-1}$ сумму $S$,Применим к вычислению суммы $S$ метод БВЕ (см. детальное описание в [12]–[18]): т.е., комбинируя на каждом шаге слагаемые $S$ последовательно попарно и вынося за скобки “очевидный” общий множитель, вычисляем на каждом шаге значения выражений в скобках, которые по построению будут целыми числами. Чтобы вычислительная сложность была не слишком большой, вычисляемые на каждом шаге значения “скобок” должны расти не слишком быстро. Например (см. [12]), с помощью БВЕ можно вычислить быстро следующие два вида степенных рядов:
$$
\begin{equation}
f_2 =f_2(z)=\sum_{j=0}^\infty\frac{a(j)}{b(j)}\,\frac{z^j}{j!},
\end{equation}
\tag{5}
$$
при условии, что $a(j)$, $b(j)$ – целые числа, $|a(j)|+|b(j)|\leqslant(K_1j)^{K_2}$, $|z|<1$, $K_1$, $K_2$ есть константы, и $z$ есть алгебраическое число. Сложность вычисления рядов (4), (5) оценивается так:
$$
\begin{equation}
s_{f_1}(n)=O(M(n)\log^2n),\qquad s_{f_2}(n)=O(M(n)\log n).
\end{equation}
\tag{6}
$$
Структура метода БВЕ допускает распараллеливание БВЕ-алгоритмов.
2. Вычисление “сжатых” степенных рядов с помощью БВЕЛегко видеть из (1) и (4), (5), что если числа $d(j)$ таковы, что
$$
\begin{equation}
\begin{gathered} \, d(j)=\frac{a(j)}{b(j)} \qquad\text{или}\qquad d(j)=\frac{a(j)}{b(j)j!}, \\ a(j),b(j)-\text{целые числа}, \quad |a(j)|+|b(j)|\leqslant(K_1j)^{K_2},\qquad K_1,K_2-\text{константы}, \end{gathered}
\end{equation}
\tag{7}
$$
то при алгебраическом $x$, $|x| <1$, “сжатые” ряды (1) являются подмножеством множества рядов (4), (5) и вычисляются методом БВЕ точно так же, как и ряды (4), (5). Единственным отличием является количество слагаемых ряда, которые нужно просуммировать, чтобы получить значение суммы ряда с точностью до $n$ знаков. Для достижения точности $2^{-n}$ в (4) достаточно взять $\sim n$ членов ряда (4) и потом просуммировать сумму $\sim n$ слагаемых методом БВЕ (см. для деталей [12], [15], [18]). Для достижения точности $2^{-n}$ в (5) достаточно взять $\sim n/\log n$ членов ряда (5) и потом вычислить сумму $\sim n/\log n$ слагаемых методом БВЕ (см. для деталей [12]). В то же время, чтобы вычислить ряд (1) с точностью $2^{-n}$, достаточно взять $\sqrt[r]{n}$, а затем просуммировать сумму $\sim\sqrt[r]{n}$ слагаемых (точнее, количество суммируемых слагаемых должно равняться первому целому числу, не меньшему, чем $\sim\sqrt[r]{n}$, и равному степени двойки) методом БВЕ. Поскольку количество шагов в таком БВЕ алгоритме есть $\log\sqrt[r]{n}=1/r\log n$, оценки сложности вычисления “сжатых” степенных рядов в этом случае совпадают с оценками (6), и алгоритмы БВЕ вычисления “сжатых” рядов являются быстрыми. С другой стороны, оценка сложности вычисления ”сжатых” рядов вида (2) методом БВЕ будет отличаться от оценок сложности вычисления методом БВЕ рядов (4), (5) с трансцендентным аргументом, поскольку существенно зависит от количества суммируемых слагаемых. В случае рядов (4), (5) оценка сложности вычисления (в общем случае) будет $O(n^{2+\varepsilon})$. В случае “сжатого” степенного ряда с трансцендентным аргументом сложность вычисления методом БВЕ будет для любого $\varepsilon>0$, $n\to\infty$. Таким образом (см. выше определение быстрого алгоритма), такие алгоритмы не будут быстрыми.Далее рассмотрим другой способ вычисления изучаемого ряда с трансцендентным аргументом и оценим сложность нового вычисления. Для простоты будем рассматривать “сжатые” степенные ряды (1) с $d(j)\equiv 1$ $\forall\mspace{1mu}j$, т.е. такие, как функция $\omega(x)$ из (2). 3. Вспомогательные утверждения Доказательство. Легко видеть, что сумма слагаемых с биномиальными коэффициентами, стоящая в скобках в правой части формулы (10) под знаком суммы по $m$ от $1$ до $k$, представляет собой выражение Отсюда имеем Замечание 1. Заметим, что первая формула из (9) – это известная табличная формула (см., например, [20]). Следствие 1. Из леммы 1 следует, что примечательную формулу Фаульхабера от 1631 г. из [21] можно записать в новом виде. Формулу Фаульхабера (сам Иоганн Фаульхабер подсчитал в численном виде 17 первых коэффициентов), с выведенными для любой степени коэффициентами $B_j$, названными впоследствии в его честь числами Бернулли, Бернулли доказал в следующей форме (см. [22]):
$$
\begin{equation*}
\sum_{k=1}^nk^p=\frac{1}{p+1}\sum_{j=0}^p(-1)^j\binom{p+1}{j}B_jn^{p+1-j}.
\end{equation*}
\notag
$$
Из леммы 1 следует, что Лемма 2. Сумма “сжатого” степенного ряда Доказательство. Пользуясь леммой 1, получаем последовательно значения коэффициентов от $a_1=\sum_{m=1}^r(-1)^{m-1}\binom{r}{m}1^{r-m}=1$ до $a_l=\sum_{m=1}^r(-1)^{m-1}\binom{r}{m}l^{r-m}$.
4. Новый алгоритм и сложность вычисления “сжатого” степенного рядаВычислим ряд (12) с точностью $2^{-n}$, предположив для простоты, что $|x|\leqslant 1/2$. В этом случае в сумме (11) достаточно просуммировать $l$ слагаемых, где $l$ – наименьшее целое число такое, что Чтобы вычислить (11) будем вычислять произведение (13).На вычисление значения произведения $x^{2^r-1}=x* x^2*x^4*\dotsb*x^{2^{r-2}}*x^{2^{r-1}}$, где каждый следующий сомножитель является квадратом предыдущего, достаточно $O((2r-1)M(n))$ операций ($r$ – фиксированное), для вычисления всех значений $x^{3^r-2^r},x^{4^r-3^r},x^{5^r-4^r},\dots,x^{l^r-(l-1)^r}$ (вычисляем последовательно), с учетом (16) достаточно операций. С предварительно вычисленными значениями
$$
\begin{equation*}
x^{2^r-1},\ x^{3^r-2^r},\ x^{4^r-3^r},\ x^{5^r-4^r}, \ \dots,\ x^{l^r-(l-1)^r}
\end{equation*}
\notag
$$
произведение (13) при условии (16) вычисляется со сложностью Из (17), (18) и (3) следует, что для вычисления с точностью $2^{-n}$ ряда (12) достаточно операций. Если $1/2<|x|\leqslant a<1$, то определив такое $k$, что $a^k< 1/2$, или $k\geqslant 1/\log_2(1/a)$, нужно просуммировать не (16) членов ряда (12), а $L$ членов ряда, где $L$ наименьшее целое число такое, что $L\geqslant(kn)^{1/r}$. Поскольку $k$ является фиксированной постоянной, оценка сложности вычисления не меняется с точностью до констант в $O$. Тем самым доказана Теорема 1. Сложность вычисления ряда где $x$ – трансцендентное число, есть для любого $\varepsilon>0$ и $n>n_1(\varepsilon)$, $n\to\infty$. 5. ЗаключениеПоскольку в теории сложности вычислений до сих пор (июль 2022) не найдено ни одной оценки битовой сложности вычисления снизу (кроме тривиальных), трудно заявлять о существовании (или не существовании) быстрого алгоритма вычисления “сжатого” степенного ряда с трансцендентным аргументом. Однако, то что оценка сложности вычисления такого ряда посредством двух совершенно разных методов оказалась одинаковой по $n$, $n\to\infty$, с точностью до констант, стоящих в $O$, свидетельствует о том, что полученная оценка близка к “естественной” (возможно даже к оптимальной) для вычисления “сжатого” степенного ряда с трансцендентным аргументом. 
Цитирование в формате AMSBIB
\RBibitem{Kar23} |
|
||||||||||||||||||||||
|
Обратная связь: |
Пользовательское соглашение
|
Регистрация посетителей портала |
Логотипы |
|