автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.17, диссертация на тему:Разработка и реализация алгоритмов для работы с FLINSPACE конструктивными вещественными числами и алгоритмическими функциями над ними

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

На правах рукописи

ЯХОНТОВ Сергей Викторович

РАЗРАБОТКА И РЕАЛИЗАЦИЯ АЛГОРИТМОВ ДЛЯ РАБОТЫ С ЕЬШЭРАСЕ КОНСТРУКТИВНЫМИ

ВЕЩЕСТВЕННЫМИ ЧИСЛАМИ И АЛГОРИТМИЧЕСКИМИ ФУНКЦИЯМИ НАД НИМИ

05.13.17 —Теоретические основы информатики

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-математических наук

□□34В44Б4

Санкт-Петербург 2009

/А

003464464

Работа выполнена на кафедре информатики математико-механического факультета Санкт-Петербургского государственного университета

Научный доктор физико-математических наук,

руководитель: профессор КОСОВСКИЙ Николай Кириллович

Официальные доктор физико-математических наук, оппоненты: профессор ОРЕВКОВ Владимир Павлович

(ведущий научный сотрудник лаборатории математической логики, Санкт-Петербургское отделение математического института им. В.А. Стеклова)

кандидат физико-математических наук, доцент ТИШКОВ Артем Валерьевич (старший научный сотрудник, Санкт-Петербургский институт информатики и автоматизации РАН)

Ведущая Санкт-Петербургский государственный

организация: политехнический университет

Защита состоится " " ОЛл2009 г. в А5^°часов н заседании совета Д 212.232.51 по защите докторских и кандидатских дис сертаций при Санкт-Петербургском государственном университете по ад ресу: 198504, Санкт-Петербург, Петродворец, Университетский пр., д.28, математико-механический факультет, ауд. 405.

С диссертацией можно ознакомиться в Научной библиотеке им. М. Горького Санкт-Петербургского государственного университета по адресу: 199034, Санкт-Петербург, Университетская наб., 7/9.

Автореферат разослан " "с^ре^^росилЗ

2009 г.

Ученый секретарь диссертационного совета

©

Даугавет И. К.

Содержание работы

Актуальность темы. С появлением вычислительной техники встал вопрос о вычислительной сложности объектов математического анализа, в первую очередь основных классов вещественных чисел и функций. Среди работ последних 18 лет, в которых исследовалась вычислительная сложность конструктивных вещественных чисел и функций, отметим [5-7]. Данные работы в значительной степени являются обобщением накопленных знаний относительно вычислимого математического анализа и отражают современное состояние исследований в данной области. Работы [5-7] характеризуются тем, что авторы в основном рассматривают временную вычислительную сложность проблем математического анализа. В [7] вычислительная сложность рассматривается с точки зрения времени выполнения и длины входной ленты, достаточных для получения приближенных значений вещественных чисел и функций с произвольной точностью. Здесь же приводится ряд теорем относительно вычислительной сложности арифметических операций и некоторых понятий из теории функций вещественного переменного. В [5, 6] строится система полиномиально вычислимого анализа, при этом главное внимание уделяется построению и определению свойств классов конструктивных вещественных чисел и функций, аналогичных классам из теории вычислительной сложности. Линейная емкостная сложность объектов математического анализа, для оценки которой важно знать объем промежуточных вычислений, в работах [5-7] почти не затронута.

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

числения приближенных значений относительно проще, что немаловажш для уменьшения сложности программного обеспечения, например, в обла сти численных расчетов. В качестве такого класса в данной работе выбра1 FLINSPACE [4] - класс алгоритмов, для которых длина каждой проме жуточной записи вычисления ограничена линейной функцией от суммар ной длины входных данных. Подтверждением неформальной характери стики класса FLINSPACE как класса осуществимых вычислений с точ ки зрения требуемой для вычислений памяти может служить то, что в на стоящее время в работах по теоретической информатике для вычисленш в пределах FLINSPACE утвердился термин «space-efficient évaluation» Известно, что класс FLINSPACE не совпадает с классом FP и, кром того, если FLINSPACE С FP, то Р = NP [1]. Следовательно, результа ты относительно FLINSPACE вычислимости объектов математическог анализа не следуют непосредственно из FP вычислимости этих объекто и требуют отдельного доказательства в предположении Р ф NP, которо поддерживается многими специалистами в области математических ochoi информатики.

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

Цели работы. Показать, что для вещественных чисел и функций мате матического анализа, наиболее часто используемых на практике, можн построить конструктивные аналоги, позволяющие находить приближени в пределах класса FP//LINSPACE. Разработать алгоритмы для рабо ты с FLINSPACE вычислимыми приближениями объектов математиче ского анализа, которые реализуемы на объектно-ориентированном языке программирования. Реализовать такие алгоритмы на языке программиро вания С# в среде программирования Microsoft Visual Studio 7.1.

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

ческий анализ, теория вычислительной сложности, аппарат конструктивного математического анализа. При реализации библиотеки классов использовались такие элементы программирования, как абстрактные классы, функторы, интерфейсы, итераторы.

Научная новизна. Новым является изучение достаточно широкого класса вещественных чисел и функций с точки зрения вычисления двоично-рациональных приближений в пределах класса FLINSPACE, как весьма важного для практических вычислений.

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

Апробация работы. Результаты работы обсуждались на следующих научных конференциях и семинарах:

• V Международная конференция «Дискретные модели в теории управляющих систем» (Ратмино, 26—29 мая 2003 г.);

• VIII Международный семинар «Дискретная математика и ее приложения» (Москва, 2—G февраля 2004 г.);

• IX Международный семинар «Дискретная математика и ее приложения» (Москва, 18—23 июня 2007 г.);

• семинар кафедры вычислительных методов математико-механнческого факультета Санкт-Петербургского государственного университета:

• семинар кафедры информатики математико-механического факультета Санкт-Петербургского государственного университета.

Публикации. По теме диссертации опубликованы тезисы [8-10] и статьи [11, 12]. В [8, 11] содержатся результаты о емкостной вычислительной сложности алгоритма Штурма и FP//LINSPACE конструктивности алгебраических чисел, а также рассмотрены арифметические операции на множестве FLINSPACE конструктивных вещественных чисел.

В [9,10,12] предложены алгоритмы для вычисления степенных рядов в пределах FP//LINSPACE и доказана FP//LINSPACE конструктивность некоторых элементарных функций. В статье [12] имеется описание библиотеки классов на языке программирования С# для работы с FLINSPACE конструктивными вещественными числами и функциями. Статьи [11,12] входят в перечень изданий, рекомендованных ВАК для публикаций.

Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения, списка литературы, списка таблиц, предметного указателя и приложения. Содержит 1 рисунок, 2 таблицы и список цитируемой литературы из 35 наименований. Текст диссертации изложен на 113 страницах. Исходные тексты библиотеки классов на языке программирования С# находятся в приложении на 54 страницах.

Общая характеристика работы

Во введении показывается актуальность темы, дана общая постановка задачи, кратко излагается содержание работы. Обосновывается выбор класса FLIN SPACE как базового класса для построения эффективной с вычислительной точки зрения системы конструктивных вещественных чисел и функций, при этом аргументация данного выбора основывается на свойствах класса FLINSPACE, изложенных в работе [1].

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

Затем описываются основные идеи подхода, изложенного в работах [5,6].

Данная диссертация основана на этом подходе к исследованию вычислительной сложности конструктивных чисел и функций. В качестве вычислительной используется модель, использующая понятие машины Тьюринга, а основу представления конструктивных объектов составляет понятие вычислимой последовательности, сходящейся по Коши, ф : N —> Ю (здесь и далее ./V — множество всех натуральных чисел, включая 0). В качестве множества аппроксимирующих значений О берется множество двоично-рациональных чисел (£> является всюду плотным в естественным для компьютерного использования подмножеством множества рациональных чисел). Для последовательности, сходящейся по Коши и задающей конструктивный объект х, требуют, чтобы выполнялось |ф(п) — х\ < 2~п для любого натурального п.

Рациональное число <1 называется двоично-рациональным, если <1 = р для некоторого целого т и натурального п. Числа из И имеют конечное двоичное представление: строка в, равная ±ирир-\... Щ.Ь\Ь2 ■ ■ ■ уг, обозначает число с/ = ^ 535=1 . Под точностью представления ргес(сГ) понимается число битов справа от двоичной точки, т. е. число г. С точки зрения изучения вычислительной сложности двоично-рациональные числа удобны тем, что для любого п числа из И с точностью п равномерно распределены на вещественной прямой.

Последовательность ф : N —> О двоично-рационально сходится к вещественному числу х, если для любого п 6 N выполняется ргес(ф(п)) = п + 1 и |ф(п) — х\ < 2~п. Множество всех вычислимых функций, двоично-рационально сходящихся к вещественному числу х, обозначается СРХ. Вещественное число х называется CF конструктивным, если СРХ не пусто.

Вещественная функция /, заданная на [а,Ь], называется СЕ конструктивной вещественной функцией на этом отрезке, если существует машина Тьюринга М с оракульной функцией такая, что для любого х € [а, Ь] и любой функции ф (Е С Рх машина по произвольной точности 2 п £ ./V, последовательно вычисляет т Е N и (], £ И так, что выполняются неравенства

\ф(т)-х\<2-"\ \d-fix) \<2~п.

Под построением конструктивного аналога вещественного числа или вещественной функции / на отрезке [а, 6] понимается описание алгоритма, вычисляющего приближения из й с произвольной точностью данного числа или значений /(х) для х £ [а, 6].

Вычислительная сложность конструктивных чисел и функций определяется в [5] как сложность алгоритмов, вычисляющих приближенные значения. Входными данными таких алгоритмов является точность вычисления 2-п, которая записывается на входе как последовательность из п пулей (обозначается 0"), и поэтому иод длиной входных данных понимается п.

Целью второй главы являются определение и основные свойства конструктивных вещественных чисел и функций с ограниченной линейной функцией сложностью вычисления двоично-рациональных приближений.

В разделе 2.2 проводится построение множеств F Ы N Б Р АС Е конструктивных вещественных чисел и функций [12].

Определение 1. Число х из П. называем РЫМ БРАСЕ конструктивным вещественным числом, если существует Е Ы N Б Р АС Е вычислимая функция ф £ СЕХ.

Говорят, что однородная емкостная вычислительная сложность функции / на отрезке [а, ?)] ограничена функцией в : N Ы, если существует машина Тьюринга М с оракульной функцией такая, что для любого х € [а, Ь] и любой функции ф € СЕХ машина вычисляет приближение /(х) с точностью 2~" так, что при этом используется не более з(п) ячеек промежуточной памяти.

Определение 2. Функцию / : [а,Ь] —► 1{ называем ЕЬШБРАСЕ конструктивной вещественной функцией на от,резке [а, Ь], если однородная емкостная вычислительная сложность функции / ограничена линейной функцией.

Множества FL/ЛГБРАСЕ конструктивных чисел и функций обозначаются ЕЬШБРАСЕср и РЬШБРАСЕс^ащ соответственно. Индекс С[а, Ь] в обозначении FЫNБРАСЕс[а.ь) обусловлен тем, что конструктивные фун ции являются непрерывными на всей области определения [5]. Аналогич-

ным образом определяются FP/JLINSPACE конструктивные вещественные числа и функции.

Рассматриваются арифметические операции на FLINSPACEqf [11]-Основная идея алгоритмов арифметических операций состоит в вычислении двоичио-рациональиых приближений аргументов с точностью, достаточной для вычисления результата, и затем выполнении арифметической операции над полученными приближениями. Устанавливается замкнутость FLINSPACEcf относительно таких операций.

Для операций обращения и деления обычно используется расчет нижней границы модуля числа но двоично-рациональным приближениям, что в общем случае может оказаться вычислением вне класса FLIN SPACE. Поэтому для эффективной реализации обращения и деления определяются множество 1а и операция high:

• la для а ф 0 —множество натуральных к, к > 0, таких, что |ct| > 2к\

• high(a) — произвольное целое к такое, что |а| < 2fc.

Показывается, каким образом можно вычислять элементы 1а для результатов арифметических операций.

В разделах 2.4 и 2.5 рассматриваются вещественные функции одного аргумента, представимые степенными рядами двух видов, и показывается вычислимость таких функций в пределах FLIN SPACE [9,12] при условии линейной сходимости соответствующих рядов на отрезке [—д, р] из области сходимости, т. е. если для остаточного члена выполняется < 2"п

для любого х G [—0,0], где 0 < ¡i(n) < С1П + С2 (при этом предполагается, что /л вычисляется алгоритмом класса FLINSPACE).

Предположим, что имеется степенной ряд

оо

S(x) = ^ aiX1 — ао + aix + а2Х2 + ... + а^хк + ... (1)

г=0

для х из [—£>,£>], в > 0, д < р, где р — радиус сходимости. Пусть щ — FLINSPACE конструктивные числа, х — FLINSPACE конструктивное число из отрезка [—0, £>], а, — FLINSPACE вычислимые функции из CFQi,

ф — F LIN SPACE вычислимая функция из CFX. Пусть также т— некоторое натуральное число, »¿(т) — двоично-рациональные приближения коэффициентов щ с точностью 2~т, ф(т) — двоично-рациональные приближения аргумента х с точностью 2~т.

Рассматриваются частичные суммы Sk(x) = Yli=oaix1, РяДа (1) с П°Д" становкой щ(т) вместо коэффициентов ai и ф(т) вместо аргументах:

к

Sk(m) = ^c*i(m)0(m)1. ¿=о

Для расчета приближенных значений S^(m) таких выражений используется схема Горнера с округлением промежуточных результатов:

ho{m) = ак(т),

hr(m) = ак-г{т) + кг-\{т)ф{т), (2)

hr(m) = hr(m) + er,

где г = 1,2, ...,к\ при г = к полагается S%.(m) = hk(m). Величины hr(m) получаются отбрасыванием битов qm+iqm+2 ■ ■ ■ Чт+р чисел hr(m) после двоичной точки, начиная с (ш + 1)-го, т. е.

М = \К(т) - hr{m)\ = 0.0 ... 0qm+iqm+2 ... qm+p,

а знак ег совпадает со знаком hT{m). Оценивается погрешность вычислений Д(к, т) = |Sl(m) — Sjt(z)| при следующих ограничениях на модуль щ и д:

3 г

Ifljl < 1 для всех г, д < - + 2~J.

4

Утверждение 1. Если т > 5, то погрешность вычислений по схеме (2) оценивается как

A(k,m) < 2~т25(к + 1). (3)

Пусть требуется вычислить приближенное значение частичной суммы ¡(к){х) РяДа (1) с точностью 2~к для некоторого натурального к. Положим

т - т(к) = т(к\, к2) = 5 + [log2(A-'i + 1)] + к2, (4)

где к\ = ц(к), = к. Тогда т > 5, и, следовательно, погрешность вычисления Б^^х) оценивается как Д(//(/с), т(к)) < 2~к. Так как для остаточного члена выполняется = — Б(х)\ < 2-(п+1' для любого х е [-£>,£>], где С = ц(п + 1), то Щ{т)-3{х)\ < Д(С,т) + 2"(п+1). Возьмем т — т(к1, А;г) по формуле (4) для = ц(п + 1), к2 — п + 1. Тогда

1- 5(аг)| < 2"<п+1> + = 2~п.

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

Предположим, что коэффициенты щ ряда (1) получаются последовательным умножением на некоторые величины с ростом номера коэффициента, т. е. а{ = с начальным значением ао = &о:

оо

5(х) = = ьй + Ьфхх + Ьфф2х2 + ... + Ь0 ... Ьк^Ькхк + ... (5)

«=о

При вычислении Зк(т) удобно не пересчитывать коэффициенты щ, а накапливать их значение вместе с вычислением промежуточных величин. Поэтому для расчета приближений величин используется следующая схема с округлением промежуточных результатов, отличная от (2):

Ь0(т) = /Зк(т),

Нг{т) = Рк-Лт)[1 + К-1(т)ф{т)], (6)

кг(т) = кг{т) + ег,

где г — 1,2,... ,к; при г = к полагается ¿'¿(т) = кк{т). Проводится оценка погрешности А(к,т) для такой схемы, аналогичная (3).

На основании вычислительных процессов (2) и (6) строятся алгоритмы 5еггеб'5ит1 и 5еггеб'5ыпг2 расчета приближений рядов (1) и (5).

Теорема 1. Если степенной ряд вида (1) аналитической функции /(х) линейно сходится на отрезке [—£>,£>], в < | + 2-5, и коэффициенты, щ являются ЕЫЛ^РАСЕ вычислимыми, то /(х) 6 ЕЬШЗРАСЕс\-0.0]-

Аналогичная теорема формулируется для функций, представимых рядами вида (5). Если коэффициенты ряда аналитической функции / явля-

ются также полиномиально вычислимыми по времени, то / будет принадлежать FP//LIN SP АСЕс[_дву

В третьей главе рассматриваются конструктивные объекты математического анализа, наиболее часто используемые на практике, и доказывается РР//LINSPACE вычислимость таких объектов, при этом для построения алгоритмов вычисления приближений используются только разложения в ряды и эквивалентные преобразования.

В разделе 3.1 устанавливается РР//LINSPACE конструктивность алгебраических и некоторых трансцендентных чисел. Из известных результатов приводится ссылка на статью [2] и ссылки на ряд других работ.

Для построения конструктивных аналогов алгебраических чисел [8,11] используется стандартное представление вещественных корней полинома Р £ Z[x] списком отделяющих интервалов, при этом такой список вычисляется с помощью алгоритма Штурма. Предполагается, что полином задается списком всех своих коэффициентов, включая нулевые.

Теорема 2. Пусть Р(х) = Yl*b=oPix% ~ примитивный полином с целы,мг1 коэффициентами, свободный от квадратов. Тогда емкостная сложность алгоритма Штурма ограничена сверху функцией C{m3l{m) + m2w(P)).

Здесь 1(т)-~длина двоичной записи т, w(P) = (т + 1 )(l(h(P)) + 1), h(P) = тах"2:1 \pi \ — полунорма полинома Р. Алгоритм Штурма позволяет по полиному Р £ Z[x] построить набор CF конструктивных вещественных чисел, являющихся конструктивными аналогами корней полинома Р. Для вычисления рациональных приближений к корню а используется итеративный алгоритм, на каждом шаге которого интервал, содержащий а, делится на два подинтервала. Если 2~" — заданная точность вычисления двоично-рационального приближения, то для концевых точек т получающихся подинтервалов и значений Р(т) в этих точках выполняются неравенства 1(т) < С\п, 1{Р(т)) < Сгп.

Теорема 3. Пусть Р £ Z[x] — примитивный полином, свободный от квадратов, {а.;} — набор вещественных корней Р. Тогда каждое число из набора {ai} принадлежит РР//LINSPACEcf-

Для построения конструктивных аналогов трансцендентных чисел тт и е используется формула Мэшина (J. Machin) для числа тг:

7г = 16а — 4/3, а — arctg(5_1), ¡3 = arctg(239_1),

и ряд Jj для числа е.

В разделе 3.2 рассматривается вычислительная сложность основных элементарных функций. Для небольших по абсолютному значений аргументов элементарные функции вычисляются напрямую с помощью подходящего алгоритма для степенного ряда. Расчет таких функций па всей области определения выполняется с использованием аддитивной или мультипликативной редукции интервала.

Покажем схему расчета в пределах FP//LINSPACE элементарных функций на примере логарифмической функции [10,12].

Ряд Тейлора логарифмической функции ln(l + х) = сходится для значений х в интервале (—1,1]. С помощью мультипликативной редукции интервала вычисление логарифма для аргумента и = 1 + х сводится к расчету логарифма для аргумента

Ни) = lnQ^) = In (!) + г • 1п(2) = 1п(!) -г • InQ);

здесь г —некоторое целое число. Введем следующие обозначения: и' = ^г, х* — приближение х, (и')*— приближение и'. Приближенные значения аргумента конструктивной функции являются двоично-рациональными числами, а такие числа, как уже говорилось, имеют конечное двоичное представление. Поэтому для вычисления (и')* достаточно сдвигать битовое представление и* так, чтобы старший значащий бит оказался сразу после двоичной точки (т. е. (и1)* = 0.1... ). Если и* > 1, то г > 0, иначе г < 0. При этом (и')* будет принадлежать интервалу l), а величина (х')*, равная (и')* — 1, будет находиться в интервале [—5,0). Так как (ж')* G [—0), то х' 6 [—j — 2-5,2~5) при условии, что х' вычисляется с точностью 2~т, m >5. Обозначим интервал [—5 — 2~5,2~5) через а(5).

Для модуля остаточного члена логарифмического ряда на интервале - 2~5,0) имеет место оценка \гп(х')| < 2-°-9(п+1)+2. Для х' £ [0,2"5)

заведомо будет |rn(a;')| < 2_n. То есть логарифмический ряд линейно сходится на интервале <т(5). Так как коэффициенты данного ряда ограничены по модулю сверху 1 и <х(5) С [—д, д], где д = то используется схема

(2) для расчета логарифмического ряда в пределах FP//LINSPACE для х' на интервале сг(5), в частности для расчета ln(2-1) = 1п(1 — 2-1). При этом в качестве ц(п + 1) берется выражение [1.2п + 3], так как в этом случае будет |г,4(п+1)(.т')| < 2-а9(1-2"+3+1)+2 < 2^п+1\

Учитывая, что к\ = [1.2n + 3], к2 = п+1, получаем точность аргумента, достаточную для определения значения 1п(1 4- х') с точностью 2~п:

где m(kh к2) = 5 + [log2(/ci + 1)1 + к2.

Теорема 4. Функция 1п(1+х) является FP//LINSPАСЕ конструктивной на любом отрезке [2~р — 1,2Р — 2], где р — натуральное, р > 1.

Аналогичные теоремы доказываются для функций (1 + x)h (ft—рациональное число, |ft| < 1), sin(x'), arcsin(a;), ехр(х).

Четвертая глава содержит описание библиотеки классов [12] для работы с FLINSPACE конструктивными вещественными числами и функциями, реализованной на языке программирования С# 1.1. Приводятся результаты пробных вычислений некоторых констант и функций. Например, для вычисления приближенного значения 1п(5) с 3320 двоичными знаками на компьютере с процессором AMD Athlon 64 Х2 Dual Core 3800^ после точки понадобилось 27 с. При этом для умножения двоично-рациональных чисел использовался простой алгоритм с временной сложностью Сп2.

В заключении сформулированы основные результаты работы:

• Предложены алгоритмы для расчета в пределах FP//LINSPАСЕ полиномов и степенных рядов двух видов, в частности рядов Тейлора. Приведены условия на степенные ряды аналитических функций, при которых такие функции являются FLINSPACE конструктивными.

• Доказана FP//LINSPАСЕ вычислимость наиболее часто используемых на практике классов вещественных чисел и функций: алгебраических чисел, некоторых трансцендентных чисел, основных элементар-

ных функций (получены соответствующие оценки погрешностей вычислений двоично-рациональных приближений и на основе этих оценок построены алгоритмы класса FP//LINSPACE).

• Реализована библиотека классов на языке программирования С# в среде программирования Microsoft Visual Studio 7.1 для работы с FP//LINSPACE конструктивными числами и функциями и на примерах некоторых чисел и функций математического анализа продемонстрирована практическая пригодность данной библиотеки.

Предложенные алгоритмы не всегда оптимальны по времени выполнения, но для построения FLINSPACE вычислимого математического анализа важна принципиальная возможность построения линейных по памяти алгоритмов.

Список литературы

[1] Косовская Т. М., Косовский Н. К. Различия между классом LINSPACE и рядом других классов сложности. — Тезисы докладов XIV Международной конференции «Проблемы теоретической кибернетики» (Пенза, 23—28 мая 2005 г.). М.: Изд-во мех.-матем. факультета Моск. ун-та, 2005. - С. 72.

[2] Оревков В. П. О сложности разложения алгебраических ирра-циональностей в непрерывные дроби. — Труды Матем. ин-та им В. А. Стеклова, CXXIX. Л.: Наука, 1973.-С. 24-29.

[3] Шанин Н. А. Конструктивные вещественные числа и конструктивные функциональные пространства. — Труды Матем. ин-та АН СССР им. В. А. Стеклова, Т. 67, изд. АН СССР, 1962.-С. 15-294.

[4] Du D., Ко К. Theory of Computational Complexity. — New York: John Wiley & Sons, 2000.-491 p.

[5] Ко К. Complexity Theonj of Real Functions. — Boston: Birkhauser, 1991.-309 p.

[6] Ко К. Polynomial-time computability in analysis.—in «Handbook о Recursive Mathematics», Vol. 2, Recursive Algebra, Analysis an Combinatorics, 1998.-P. 1271-1317.

[7] Weihrauch К. Computable analysis. — New York: Springer, 2000. — 285 p

Работы автора по теме диссертации

[8] Яхонтов С. В. LINSPАСЕ-конструктивность алгебраических чи сел. — Труды V Международной конференции «Дискретные модели теории управляющих систем» (Ратмино, 26—29 мая 2003 г.). М.: Изд-в факультета ВМиК Моск. ун-та, 2003. - С. 96-97.

[9] Яхонтов С. В. Вычисление степенных рядов в предела LINSPACE. —Материалы VIII Международного семинара «Дискретная математика и ее приложения» (Москва, 2—6 февраля 2004 г.). М.: Изд-во мех.- матем. факультета Моск. ун-та, 2004.— С. 118—122.

[10] Яхонтов С. В. Вычисление логарифмической функции в предела LINSPACE для конструктивных вещественных чисел. — Материалы IX Международного семинара «Дискретная математика и ее приложения» (Москва, 18—23 июня 2007 г.). М.: Изд-во мех.- матем. факультета Моск. ун-та, 2007. — С. 149 151.

[11] Яхонтов С. В. Вычисление алгебраических чисел и операции над ними с линейной памятью. — Системы управления и информационные технологии. №1 (31), 2008 (март).-С. 97-102.-ISSN 1729-5068.

[12] Яхонтов С. В. LINSPACE конструктивный аналог логарифмической функции. — Вестник С.-Петерб. ун-та, Сер. 10. Прикладная математика, Информатика. Процессы управления. Вып. 2, 2008 (июнь).— С. 97-110.-ISSN 1811-9905.

Подписано к печати 21.01.2009. Формат бумаги 60 х 90 1/16. Бумага офсетная. Печать ризографическая. Объем 1,0 п.л. Тираж 100 экз. Заказ 4383. Отпечатано в отделе оперативной полиграфии НИИХ СПбГУ с оригинал-макета заказчика. 198504, Санкт-Петербург, Старый Петергоф, Университетский пр., 2.

Введение

Актуальность темы.

Цели работы.

Методы исследования.

Научная новизна.

Практическая ценность.

Апробация работы.

Публикации

Структура и объем работы.

1 Обзор литературы

1.1 Вычислимый математический анализ.

1.1.1 Конструктивный анализ Маркова.

1.1.2 Рекурсивный анализ Гудстейна.

1.2 Сведения из теории вычислительной сложности.

1.2.1 Машина Тьюринга.

1.2.2 Машина Тьюринга с оракульной функцией.

1.2.3 Классы вычислительной сложности.

1.2.4 Классы FP и FLINSPACE.

1.3 Монография К. Weihrauch.

1.3.1 Вычислительная модель

1.3.2 Конструктивные вещественные числа и функции.

1.3.3 Представление рациональных чисел.

1.3.4 Вычислительная сложность чисел и функций.

1.4 Работы К. Ко.

1.4.1 Двоично-рациональные числа.

1.4.2 CF конструктивные вещественные числа.

1.4.3 CF конструктивные вещественные функции.

1.4.4 Определение FP конструктивных чисел.

1.4.5 Определение FP конструктивных функций.

1.4.6 Свойства FP конструктивных объектов.

1.5 Вычисление значений констант и функций.

1.5.1 Арифметико-геометрическое среднее.

1.5.2 Разложения в ряды с рациональными коэффициентами.

1.6 Выводы к главе

2 Множества FLINSPACEcf и F LI N S Р АС Ес[а,ь]

2.1 Двоично-рациональные числа.

2.2 Определение и основные свойства.

2.2.1 FLINSPACE конструктивные числа.

2.2.2 FLINSPACE конструктивные функции.

2.2.3 Арифметические операции на FLINSPACEcf.

Сложение и вычитание.

Умножение.

Обратное значение.

Деление.

2.2.4 Суперпозиция конструктивных функций.

2.3 Вычисление значений полиномов

2.4 Вычисление частичных сумм степенных рядов

2.4.1 Схема с коэффициентами вида ^

2.4.2 Схема с составными коэффициентами

2.5 Аналитические функции.

2.5.1 Вычисление степенных рядов

2.5.2 Разложение в ряд Тейлора.

2.6 Выводы к главе

3 FLINSPACE конструктивные числа и функции

3.1 Конструктивные числа.

3.1.1 Целые и рациональные числа.

3.1.2 Иррациональные алгебраические числа.

Операции над полиномами.

Вычисление аппроксимаций корней.

3.1.3 Некоторые трансцендентные числа (тг и е).

3.2 Элементарные функции.

3.2.1 Алгебраические функции.

Рациональные функции.

Иррациональные функции.

3.2.2 Тригонометрические функции.

3.2.3 Обратные тригонометрические функции.

3.2.4 Показательная функция

3.2.5 Логарифмическая функция

3.3 Выводы к главе 3.

4 Библиотека классов на языке программирования С#

4.1 Иерархия классов.

4.2 Вспомогательные классы.

4.2.1 Двоично-рациональные числа.

Нормализованное представление.

Основные методы.

Конструкторы.

Класс DRNumPair.

Операции сравнения.

Операции сложения, вычитания и умножения.

Операции обращения и деления.

Дополнительные операции.

Двоично-рациональный интервал.

4.2.2 Полиномы

Представление массивом коэффициентов.

Основные методы.

Конструкторы.

Операции сложения и умножения.

Дополнительные операции.

4.3 Вычисление полиномов и степенных рядов.

4.3.1 Реализация алгоритма из 2.3.

4.3.2 Реализация алгоритмов из 2.4.

4.3.3 Определение рядов для чисел и функций

4.4 Конструктивные числа.

4.4.1 Класс CompRealNumber

Отношение порядка.

Арифметические операции.

4.4.2 Целые и рациональные числа.

4.4.3 Иррациональные алгебраические числа.

Псевдоделение с остатком

Вычисление набора отделяющих интервалов.

Представление алгебраических чисел.

Вычисление аппроксимаций корней.

4.4.4 Трансцендентные числа (л- и е)

4.5 Конструктивные функции.

4.5.1 Класс CompRealFunc.

4.5.2 Элементарные функции.

4.6 Результаты пробных вычислений.

4.7 Выводы к главе

Актуальность темы. С появлением вычислительной техники встал вопрос о вычислительной сложности объектов математического анализа, в первую очередь основных классов вещественных чисел и функций. Среди работ последних 18 лет, в которых исследовалась вычислительная сложность конструктивных вещественных чисел и функций, отметим [30,31,34]. Данные работы в значительной степени являются обобщением накопленных знаний относительно вычислимого математического анализа и отражают современное состояние исследований в данной области. Работы [30,31,34] характеризуются тем, что авторы в основном рассматривают временную вычислительную сложность проблем математического анализа. В [34] вычислительная сложность рассматривается с точки зрения времени выполнения и длины входной ленты, достаточных для получения приближенных значений вещественных чисел и функций с произвольной точностью. Здесь же приводится ряд теорем относительно вычислительной сложности арифметических операций и некоторых понятий из теории функций вещественного переменного. В [30, 31] строится система полиномиально вычислимого анализа, при этом главное внимание уделяется построению и определению свойств классов конструктивных вещественных чисел и функций, аналогичных классам из теории вычислительной сложности. Линейная емкостная сложность объектов математического анализа, для оценки которой важно знать объем промежуточных вычислений, в работах [30,31,34] почти не затронута.

Вместе с тем, представляет существенный теоретический и практический интерес построение системы конструктивных вещественных чисел и функций, которая позволяла бы выполнять базовые вычисления в пределах некоторого емкостного класса сложности, подпадающего под понятие «осуществимые вычисления», как, например, класс FP, т. е. класс вычислений на машинах Тьюринга за полиномиальное время от длины исходных данных [25]. Теоретический интерес имеет место в силу неизвестной точной взаимосвязи классов временной и емкостной вычислительной сложности; практический интерес следует из того, что получающиеся алгоритмы вычисления приближенных значений относительно проще, что немаловажно для уменьшения сложности программного обеспечения, например, в области численных расчетов. В качестве такого класса в данной работе выбран FLINSPACE [25] —класс алгоритмов, для которых длина каждой промежуточной записи вычисления ограничена линейной функцией от суммарной длины входных данных. Подтверждением неформальной характеристики класса FLINSPACE как класса осуществимых вычислений с точки зрения требуемой для вычислений памяти может служить то, что в настоящее время в работах по теоретической информатике для вычислений в пределах FLINSPACE утвердился термин «space-efficient evaluation». Известно, что класс FLINSPACE не совпадает с классом FP и, кроме того, если FLINSPACE С FP, то Р = NP [9]. Следовательно, результаты относительно FLINSPACE вычислимости объектов математического анализа не следуют непосредственно из FP вычислимости этих объектов и требуют отдельного доказательства в предположении Р ф NP, которое поддерживается многими специалистами в области математических основ информатики.

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

Цели работы. Показать, что для вещественных чисел и функций математического анализа, наиболее часто используемых на практике, можно построить конструктивные аналоги, позволяющие находить приближения в пределах класса FP/ / LIN SPACE. Разработать алгоритмы для работы с FLINSPACE вычислимыми приближениями объектов математического анализа, которые реализуемы на объектно-ориентированном языке программирования. Реализовать такие алгоритмы на языке программирования С# в среде программирования Microsoft Visual Studio 7.1.

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

Научная новизна. Новым является изучение достаточно широкого класса вещественных чисел и функций с точки зрения вычисления двоично-рациональных приближений в пределах класса FLINSPACE, как весьма важного для практических вычислений.

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

Апробация работы. Результаты работы обсуждались на следующих научных конференциях и семинарах:

• V Международная конференция «Дискретные модели в теории управляющих систем» (Ратмино, 26—29 мая 2003 г.);

• VIII Международный семинар «Дискретная математика и ее приложения» (Москва, 2-6 февраля 2004 г.);

• IX Международный семинар «Дискретная математика и ее приложения» (Москва, 18—23 июня 2007 г.);

• семинар кафедры вычислительных методов математико-механического факультета Санкт-Петербургского государственного университета;

• семинар кафедры информатики математико-механического факультета Санкт-Петербургского государственного университета.

Публикации. По теме диссертации опубликованы тезисы [17-19] и статьи [20,21]. В [17, 20] содержатся результаты о емкостной вычислительной сложности алгоритма Штурма и FP//LINSPACE конструктивности алгебраических чисел, а также рассмотрены арифметические операции на множестве FLINSPACE конструктивных вещественных чисел. В [18,19,21] предложены алгоритмы для вычисления степенных рядов в пределах FP//LINSPACE и доказана FP//LINSPACE конструктивность некоторых элементарных функций. В статье [21] имеется описание библиотеки классов на языке программирования С# для работы с FLINSPACE конструктивными вещественными числами и функциями. Статьи [20, 21] входят в перечень изданий, рекомендованных ВАК для публикаций.

Структура И объем работы. Диссертация состоит из введения, четырех глав, заключения, списка литературы, списка таблиц, предметного указателя и приложения. Содержит 1 рисунок, 2 таблицы и список цитируемой литературы из 35 наименований. Текст диссертации изложен на 113 страницах. Исходные тексты библиотеки классов на языке программирования С# находятся в приложении на 54 страницах.

Основные результаты. Сформулируем основные результаты, полученные в данной диссертации:

• Предложены алгоритмы для расчета в пределах FPJ/LINSPACE полиномов и степенных рядов двух видов, в частности рядов Тейлора. Приведены условия на степенные ряды аналитических функций, при которых такие функции являются FLINSPACE конструктивными.

• Доказана FPj / LIN SPACE вычислимость наиболее часто используемых на практике классов вещественных чисел и функций: алгебраических чисел, некоторых трансцендентных чисел, основных элементарных функций (получены соответствующие оценки погрешностей вычислений двоично-рациональных приближений и на основе этих оценок построены алгоритмы класса FP/ / LIN SPACE).

• Реализована библиотека классов на языке программирования С# в среде программирования Microsoft Visual Studio 7.1 для работы с FP/ / LIN SPACE конструктивными числами и функциями и на примерах некоторых чисел и функций математического анализа продемонстрирована практическая пригодность данной библиотеки.

Предложенные алгоритмы не всегда оптимальны по времени выполнения, но для построения FLINSPACE вычислимого математического анализа важна принципиальная возможность построения линейных по памяти алгоритмов.

Заключение

1. Бухбергер Б., Коллинз Дж., JIooc Р. Компьютерная алгебра. Символьные и алгебраические вычисления. — М.: Мир, 1986, —392 с.

2. Воробьев Н. Н. Теория рядов: Учеб. пособие для вузов. — 5-е изд. М.: Наука, Гл. ред. физ.-мат. лит., 1986. — 408 с.

3. Гудстейн P. JL Рекурсивный математический анализ. — М.: Наука, 1970. — 472 с.

4. Гэри М., Джонсон Д. Вычислительные машины и трудно решаемые задачи. — М.: Мир, 1982.-416 с.

5. Двайт Г. Б. Таблицы интегралов и другие математические формулы. — 9-е изд. СПб.: Изд-во «Лань», 2005.-232 с.

6. Зорич В. А. Математический анализ. Часть I. — 4-е изд. М.: МЦНМО, 2002. — 664 с.

7. Кнут Д. Искусство программирования, том 2. Получисленные алгоритмы. — Изд. дом «Вильяме», 2001. — 832 с.

8. Косовский Н. К. Об алгорифмических последовательностях из начального класса иерархии Гжегорчика. — Зап. научн. сем. Ленингр. отд. Матем. ин-та АН СССР им. В. А. Стеклова, Т. 20, 1971.-С. 60-66

9. Кушнер Б. А. Лекции по конструктивному математическому анализу. — М.: Наука, 1973. —448 с.

10. Оревков В. П. О сложности разложения алгебраических иррациональностей в непрерывные дроби. — Труды Матем. ин-та им В. А. Стеклова, CXXIX. Л.: Наука, 1973.-С. 24-29.

11. Секунов Н. Ю. Самоучитель С#. — СПб.: БХВ-Петербург, 2001. —576 с.

12. Троелсен Э. С# и платформа .NET. Библиотека программиста. — СПб.: Питер, 2002. —800 с.

13. Фихтенгольц Г. М. Курс дифференциального и интегрального исчисления. — Т. 2. М.: ФИЗМАТЛИТ, 2003. —864 с.

14. Шанин Н. А. Конструктивные вещественные числа и конструктивные функциональные пространства. — Труды Матем. ип-та АН СССР им. В. А. Стеклова, Т. 67, изд. АН СССР, 1962. — С. 15-294.

15. Шурыгин В. А. Основы конструктивного математического анализа. — М.: Едито-риал УРСС, 2004. —328 с.

16. Яхонтов С. В. LI N S Р АС Е-конструктивность алгебраических чисел. — Труды V Международной конференции «Дискретные модели в теории управляющих систем» (Ратмино, 26—29 мая 2003 г.). М.: Изд-во факультета ВМиК Моск. ун-та, 2003. —С. 96-97.

17. Яхонтов С. В. Вычисление степенных рядов в пределах LINSPACE. — Материалы VIII Международного семинара «Дискретная математика и ее приложения» (Москва, 2—6 февраля 2004 г.). М.: Изд-во мех.- матем. факультета Моск. ун-та, 2004. С. 118-122.

18. Яхонтов С. В. Вычисление алгебраических чисел и операции над ними с линейной памятью. — Системы управления и информационные технологии. №1 (31), 2008 (март).-С. 97-102.-ISSN 1729-5068.

19. Яхонтов С. В. LINSPACE конструктивный аналог логарифмической функции. — Вестник С.-Петерб. ун-та, Сер. 10. Прикладная математика. Информатика. Процессы управления. Вып. 2, 2008 (июнь). —С. 97—110. —ISSN 1811-9905.

20. Boehm H.J., Cartwright R., O'Donnel M. J., Riggle M. Exact real arithmetic: a case study in higher order programming. — Proc. ACM conf. on Lisp and Functional Programming, 1986. —P. 162—173.

21. Brent R. P. Fast multiple-precision evaluation of elementar-у functions. — Journal of the ACM. 1976, Vol. 23, N 2.-P. 242-251.

22. Cheng H., Gergel В., Kim E., Zima E. Space-efficient evaluation of hypergeometric series.— ACM SIGSAM Bulletin, Communications in Computer Algebra 2005, Vol. 39, N 2.-P. 41—52.

23. Du D., Ко К. Theory of Computational Complexity. —New York: John Wiley & Sons, 2000.-491 p.

24. Gathen J., Gerhard J. Modern Computer Algebra. — Cambridge University Press, 1999. — 754 p.

25. Haible В., Papanikolaou T. Fast multiple-precision evaluation of series of rational numbers. — Proc. of the Third Intern. Symposium on Algorithmic Number Theory. June 21-25, 1998. — P. 338-350.

26. Hur N., Davenport J. H. An exact real algebraic arithmetic with equality determination. — Proceedings of the 2000 international symposium on symbolic and algebraic computation, 2000. — P. 169-174.

27. Koren I. Computer arithmetic algorithms. — 2nd ed. Massachusetts: А К Peters, 2002. — 281 p.

28. Ко К. Complexity Theory of Real Functions. — Boston: Birkhauser, 1991. —309 p.

29. Ко К. Polynomial-time computability in analysis. — in «Handbook of Recursive Mathematics», Vol. 2, Recursive Algebra, Analysis and Combinatorics, 1998. — P. 1271— 1317.

30. Muller J.-M. Elementary Functions. Algorithms and Implementation. — Boston: Birkhauser, 1997. — 204 p.

31. Vuillemin J. Exact real computer arithmetic with continued fractions. — Proceedings of the 1988 ACM conference on LISP and functional programming, 1988. — P. 14—27.

32. Weihrauch K. Computable analysis. — New York: Springer, 2000. — 285 p.

33. Yap C. Fundamental Problems of Algorithmic Algebra. — New York: Oxford University Press, 2000, —511 p.