Scientific journal
Modern problems of science and education
ISSN 2070-7428
"Перечень" ВАК
ИФ РИНЦ = 0,791

TIME AND SPACE EFFICIENT EVALUATION OF RIEMANN ZETA FUNCTION IN KO-FRIEDMAN MODEL

Yakhontov S.V. 1
1 Saint Petersburg State University

В данной работе строится FP//LINSPACE алгоритмический аналог вещественной функции Римана  для алгоритмических вещественных чисел , ,  с полиномиальной временной и линейной емкостной сложностью на машине Тьюринга в модели Ко-Фридмана алгоритмических чисел и функций. Для построения алгоритмического аналога функции Римана предлагается алгоритм расчета двоично-рациональных приближений данной функции для вещественных , ,  с полиномиальной временной и линейной емкостной сложностью на машине Тьюринга. Данный алгоритм строится на основе разложения в числовой ряд, который сходится для вещественных , , при этом показывается и используется в данном алгоритме линейная сходимость числового ряда.  Предложенный алгоритм вычисления вещественной функции Римана  включает использование алгоритмов вычисления вещественной функции  и гипергеометрических рядов с полиномиальным временем и линейной памятью. Предложенный алгоритм (модифицированный некоторым образом для работы с комплексными числами)  может использоваться для вычисления комплексной функции Римана  для ,  (то есть также для ), с использованием полиномиального времени и линейной памяти по , где – точность вычислений. Модифицированный алгоритм также будет использовать полиномиальное время и линейную память по  и экспоненциальное время и экспоненциальную память по .

In the present paper we construct FP//LINSPACE algorithmic analog of real Riemann function for FP//LINSPACE algorithmic real numbers , , with polynomial time and linear space on Turing machines in Ko-Friedman model of algorithmic numbers and functions. To construct algorithmic analog of real Riemann function , we consider an algorithm for the evaluation of dyadic rational approximations of the function for FP//LINSPACE algorithmic real numbers on Turing machine using polynomial time and linear space. The Algorithm is based on a series expansion which converges for real , ; it is shown and used in the algorithm that the series of the function converges linearly. The proposed algorithm of the evaluation of real Riemann function uses algorithms for the evaluation of real function  and the evaluation of hypergeometric series using polynomial time and linear space. The algorithm from the present paper modified in some way to work with the complex numbers can be used to evaluate complex Riemann function  for ,  (so, also for ), in polynomial time and linear space in  wherein  is a precision of computations. The modified algorithm will use polynomial time and linear space in  and exponential time and exponential space in .

Riemann zeta function
linear-space computable functions
polynomial-time computable functions
Cauchy function representation
algorithmic (computable) numbers and functions

В данной работе рассматриваются алгоритмические (вычислимые) вещественные числа и функции, которые представляются функциями Коши, вычислимыми на машине Тьюринга [1] (такая модель алгоритмических чисел и функций называется моделью Ко-Фридмана).

Основные результаты по теории алгоритмических чисел и функций и их вычислительной сложности находятся, например, в [1]; основные результаты по теории вычислительной сложности на машине Тьюринга находятся, например, в [2].

Известно, что вещественная функция Римана [3] является полиномиально вычислимой по времени для натуральных [4, 5]; алгоритмы из [4, 5] требуют не менее чем ячеек памяти для вычисления приближенных значений функции с точностью . Также имеется алгоритм вычисления гипергеометрических рядов с произвольной точностью с квази-линейным временем и линейной памятью [6], который применим к вычислению значения . Временная и емкостная вычислительная сложность алгоритмов из [4, 5, 6] рассматривается в контексте битовой сложности; на машине Тьюринга алгоритмы из [4, 5] являются полиномиальными по времени и квази-линейными по памяти, а алгоритм из [6] является полиномиальным по вроемени и линейным по памяти.

В данной работе показывается, что вещественная функция Римана является полиномиально вычислимой по времени и линейно вычислимой по памяти (с помощью одного и того же алгоритма) на машине Тьюринга для вещественных , , в модели Ко-Фридмана. Для доказательства данного результата строится алгоритм вычисления вещественной функции Римана с полиномиальным временем и линейной памятью на машине Тьюринга. Данный алгоритм основан на разложении функции Римана в числовой ряд [7, 8] для комплексных , ; в данном алгоритме используются алгоритмы из [9, 10, 11] вычисления вещественной функции и гипергеометрических рядов с полиномиальным временем и линейной памятью. Для построения алгоритма вычисления функции Римана используются алгоритм вычисления числовых рядов из [12] и прямой и обратный анализ ошибок округления в численных алгоритмах [9, 10, 11, 13].

Частично результат, изложенный в данной работе, представлялся на научной конференции «Научная дискуссия: вопросы математики, физики, химии, биологии» [14].

1.1 алгоритмические числа и функции

Функции Коши в модели Ко-Фридмана [1] – это функции, двоично-рационально сходящиеся к вещественным числам. Фукнция (здесь – множество двоично-рациональных чисел) двоично-рационально сходится к вещественному числу , если для всех ; с помощью обозначается множество всех функций, двоично-рационально сходящихся к числу .

Definition 1. [1] Вещественное число называется алгоритмическим вещественным число, если содержит функцию , вычислимую на машине Тьюринга.

Definition 2. [1] Вещественная функция , заданная на отрезке , называется алгоритмической вещественнойфункцией на отрезке , если существует машина Тьюринга с оракульной функцией такая, что для всех и для всех функция , вычисляемая машиной с оракульной функцией , принадлежит .

1.2 Вычислительная сложность алгоритмических функций

Definition 3. [1] Фукнция называется вычислимой по времени вещественной функцией на отрезке , если для всех алгоритмических вещественных чисел функция ( берется из определения алгоритмических вещественных функций) является вычислимой по времени.

Definition 4. [1] Функция называется вычислимой по памяти вещественной функцией на отрезкеl , если для всех алгоритмических вещественных чисел функция ( берется из определения алгоритмических вещественных функций) является вычислимой по памяти.

Входными данными функций и является запись (повторение данного символа раз) в случае, когда функции вычисляются с точностью .

С помощью FP//LINSPACE обозначается класс строковых функций, вычислимых за полиномиальное время и линейную память (с помощью одного и того же алгоритма) на машине Тьюринга. Полиномиально вычислимые по времени и линейно вычислимые по памяти алгоритмические вещественные числа и функции называются FP//LINSPACE алгоритмическими вещественными функциями. Множество FP//LINSPACE алгоритмических вещественных функций на отрезке обозначается с помощью FP//LINSPACE.

1.3 Вычисление приближений вещественных функций

В данной работе используются следующие результаты из [9, 10, 11].

Для умножения и с точностью , где и – вещественные числа такие, что и для некоторого натурального числа , достаточно вычислять и с точностью для , где – линейная функция натуральных аргументов.

Для вычисления величины, обратной к с точностью , где – вещественное число такое, что для некоторого натурального числа , достаточно вычислять с точностью для , где – линейная функция натуральных аргументов.

Для вычисления функции с точностью , где вещественные и вещественное число , достаточно вычислять и с точностью для , где – линейная функция натуральных аргументов.

Можно показать, что для вычисления функции с точностью , где вещественные и вещественное , достаточно вычислять с точностью для , где – линейная функция натуральных аргументов.

2 FP//LINSPACE вычисление функции

Рассмотрим числовой ряд [7, 8] фунции Римана , сходящийся для всех комплексных чисел (исключая для целых ):

(1)

Пусть

и

запишем ряд (1) следующим образом:

(2)

Пусть – натруальное число, ; пусть и – натуральное число такое, что . Будем вычислять по формуле (2) с точностью для таких , где – натуральное число.

2.1 Вычисление

Так как

(3)

выполняютя соотношения

Следовательно

,

где – некторая константа (следует из соотношений, изложенных в параграфе 2.2.3).

Это означает, что для вычисления по формуле (2) с точностью достаточно вычислять величины и с точностью , где ( – константа, зависящая от ).

Далее, для вычисления величины с точностью воспользуемся алогитмом из [9, 10, 11] вычисления функции с точностью ; при этом достаточно вычислять величину до точности для , где – линейная функция натуральных аргументов ( – некоторое натуральное число).

2.2 Вычисление

Будем вычислять функцию следующим образом:

1) вычисляем с точностью ;

2) вычисляем с точностью ;

3) вычисляем

,

где и – приближенные значения величин and соответственно с точностью ; пусть – точность вычисления величины ;

4) вычисляем

пусть – точность вычисления величины .

Для вычисления величины с точностью воспользуемся алгоритмом из [9, 10, 11] вычисления функции с точностью ; для этого достаточно вычислять величину с точностью для , где – это линейная функция натуральных аргументов ( – натуральное число).

Следовательно, для вычисления величины с точностью с помощью суммирования ряда величину достаточно вычислять с точностью , где .

2.2.1 Вычисление

Запишем величину следующим образом:

Будем вычислять в цикле по , на каждом шаге вычисляя

(при этом ), где – приближенное значение величины с точностью , – приближенное значение величины с точностью ; для всех натуральны . Будем вычислять с точностью , отбрасывая все биты после точки, начиная с -го бита.

Используя метод математической индукции по , покажем, что для каждого , если брать .

База индукции: ; в этом случае, величина , равнаяo , вычисляется с точностью . Индукционный рпереход: пусть для . В этом случае

(здесь используется оценка ). Следовательно, выполняется оценка

в частности, . Это означает, что достаточно брать и для вычисления с точностью . И, далее, для вычисления с точностью достаточно брать где – линейная функция натурального аргумента, так как .

2.2.2 Вычисление

Будем вычислять в цикле по . Так как

где и , выполняется соотношение

Далее, из

следует

Следовательно, если взять и вычислять и с точностью , то точность вычисления будет .

2.2.3 Вычисление

Найдем точность вычисления of используя следующие соотношения:

где

и

Так как

выполняется соотношение

Оценим сверху величину

Пусть – нечетное натуральное число и ; пусть

Так как , выполняются равенства

Следовательно,

и

из чего получаем

и

(те же самые соотношения выполняются в случае, когда – четное). Следовательно

Как результат, если взять , то

Это означает, что достаточно взять и для вычисления с точностью .

3 Основной результат

Как результат, получаем, что для вычисления с точностью для достаточно выполнить следующие шаги:

1) вычислить с точностью для где – линейная функция натуральных аргументов, и

2) использовать умножений двоично-рациональных чисел длины, где – линейная функция натуральных аргументов.

Следовательно выполняется следующая теорема.

Теорема 1. Вещественная функция Римана принадлежит классу FP//LINSPACE для любого интервала , где , , и – натуральное число, .

Также выполняется следующая теорема (учитывая параграф 1.3).

Теорема 2. Вещественная функция Римана является экспоненциально вычислимой по времени и экспоненциально вычислимой по памяти по для любого отрезка , где , , и – натуральное число, .

Рецензенты:

Косовский Н.К., д.ф.-м.н., профессор, зав. кафедрой информатики, математико-механический факультет, Санкт-Петербургский государственный университет (Министерство образования и науки Российской Федерации), г. Санкт-Петербург.

Ермаков С.М., д.ф.-м.н., профессор, зав. кафедрой статистического моделирования, математико-механический факультет, Санкт-Петербургский государственный университет (Министерство образования и науки Российской Федерации), г. Санкт-Петербург.