Электронный научный журнал
Современные проблемы науки и образования
ISSN 2070-7428
"Перечень" ВАК
ИФ РИНЦ = 0,791

ЭФФЕКТИВНОЕ ПО ВРЕМЕНИ И ПАМЯТИ ВЫЧИСЛЕНИЕ ДЗЕТА-ФУНКЦИИ РИМАНА В МОДЕЛИ КО-ФРИДМАНА

Яхонтов С.В. 1
1 Санкт-Петербургский государственный университет

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

дзета-функция Римана
линейно вычислимые по памяти функции
полиномиально вычислимые по времени функции
представление функциями Коши
алгоритмические (вычислимые) числа и функции

1. Ko K. Complexity Theory of Real Functions. Boston: Birkhauser, 1991. 309 p.
2. Du D., Ko K. Theory of Computational Complexity. New York: John Wiley & Sons, 2000. 491 p.

3. Edwards H. M. Riemann's Zeta Function. Dover Publications, 2001. 330 p.

4. Карацуба Е.А. Быстрое вычисление дзета-функции Римана при целых значениях аргумента . Пробл. передачи информ., 31: 4 (1995), С. 69-80.

5. Карацуба Е.А. Быстрое вычисление значений дзета-функции Гурвица и L-рядов Дирихле, Пробл. передачи информ., 34: 4 (1998), С. 62-75.

6. Cheng H., Gergel B., Kim E., Zima E. Space-efficient evaluation of hypergeometric series // ACM SIGSAM Bull. Communications in Computer Algebra, 2005. Vol. 39, No. 2. P. 41-52.

7. Hasse H. Ein Summierungsverfahren fur die Riemannsche -Reihe. Math. Z., 1930. 32: P. 458-464.

8. Sondow J. Analytic continuation of Riemann's zeta function and values at negative integers via Euler's transformation of series // Proc. Amer. Math. Soc., 1994. 120 (120): P. 421-424.

9. Яхонтов С.В. FLINSPACE конструктивная функция . // Вестник Самарского государственного технического университета. Серия «Физико-математические науки». Вып.2 (17), 2008. С. 239-249.

10. Яхонтов С.В. FLINSPACE конструктивные вещественные числа и функции. LAMBERT Academic Publishing, 2010. 176 с.

11. Яхонтов С.В., Косовский Н.К., Косовская Т.М. Эффективные по временги и памяти алгоритмические приближения чисел и функций, 2012. Учебное пособие. СПб.: Изд-во С.-Петерб. ун-та, 2012. 256 с.

12. Muller N. Th. Polynomial Time Computation of Taylor Series // Proc. 22 JAIOO-PANEL'93, Part 2, Buenos Aires, 1993. P. 259-281.

13. Higham N. J. Accuracy and Stability of Numerical Algorithms. Society of Industrial and Applied Mathematics, Philadelphia, 1996. 688 p.

14. FP//LINSPACE computability of real Riemann zeta function in Ko-Friedman model //Н 34. Научная дискуссия: вопросы математики, физики, химии, биологии. № 8 (19): сборник статей по материалам XХ международной заочной научно-практической конференции. М.: Изд. «Международный центр науки и образования», 2014 (август). С. 68-71.

В данной работе рассматриваются алгоритмические (вычислимые) вещественные числа и функции, которые представляются функциями Коши, вычислимыми на машине Тьюринга [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. Вещественная функция Римана является экспоненциально вычислимой по времени и экспоненциально вычислимой по памяти по для любого отрезка , где , , и – натуральное число, .

Рецензенты:

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

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


Библиографическая ссылка

Яхонтов С.В. ЭФФЕКТИВНОЕ ПО ВРЕМЕНИ И ПАМЯТИ ВЫЧИСЛЕНИЕ ДЗЕТА-ФУНКЦИИ РИМАНА В МОДЕЛИ КО-ФРИДМАНА // Современные проблемы науки и образования. – 2014. – № 6.;
URL: http://science-education.ru/ru/article/view?id=16788 (дата обращения: 09.12.2019).

Предлагаем вашему вниманию журналы, издающиеся в издательстве «Академия Естествознания»
(Высокий импакт-фактор РИНЦ, тематика журналов охватывает все научные направления)

«Фундаментальные исследования» список ВАК ИФ РИНЦ = 1.074