Разработка и реализация алгоритмов для работы с FLINSPACE конструктивными вещественными числами и алгоритмическими функциями над ними тема диссертации и автореферата по ВАК РФ 05.13.17, кандидат физико-математических наук Яхонтов, Сергей Викторович

• Яхонтов, Сергей Викторович
• кандидат физико-математических наук
• 2009

Оглавление диссертации кандидат физико-математических наук Яхонтов, Сергей Викторович

Введение

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

Цели работы.

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

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

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

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

Публикации

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

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 Выводы к главе

Введение диссертации (часть автореферата) на тему «Разработка и реализация алгоритмов для работы с FLINSPACE конструктивными вещественными числами и алгоритмическими функциями над ними»

Актуальность темы. С появлением вычислительной техники встал вопрос о вычислительной сложности объектов математического анализа, в первую очередь основных классов вещественных чисел и функций. Среди работ последних 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 вычислимого математического анализа важна принципиальная возможность построения линейных по памяти алгоритмов.

Заключение

Список литературы диссертационного исследования кандидат физико-математических наук Яхонтов, Сергей Викторович, 2009 год

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.