В данной работе строится FP//LINSPACE алгоритмический аналог вещественной функции Римана для алгоритмических вещественных чисел , , с полиномиальной временной и линейной емкостной сложностью на машине Тьюринга в модели Ко-Фридмана алгоритмических чисел и функций. Для построения алгоритмического аналога функции Римана предлагается алгоритм расчета двоично-рациональных приближений данной функции для вещественных , , с полиномиальной временной и линейной емкостной сложностью на машине Тьюринга. Данный алгоритм строится на основе разложения в числовой ряд, который сходится для вещественных , , при этом показывается и используется в данном алгоритме линейная сходимость числового ряда. Предложенный алгоритм вычисления вещественной функции Римана включает использование алгоритмов вычисления вещественной функции и гипергеометрических рядов с полиномиальным временем и линейной памятью. Предложенный алгоритм (модифицированный некоторым образом для работы с комплексными числами) может использоваться для вычисления комплексной функции Римана для , (то есть также для ), с использованием полиномиального времени и линейной памяти по , где – точность вычислений. Модифицированный алгоритм также будет использовать полиномиальное время и линейную память по и экспоненциальное время и экспоненциальную память по .
В данной работе рассматриваются алгоритмические (вычислимые) вещественные числа и функции, которые представляются функциями Коши, вычислимыми на машине Тьюринга [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: https://science-education.ru/ru/article/view?id=16788 (дата обращения: 29.03.2024).