Алгоритмы вычисления оптимальных коэффициентов тема диссертации и автореферата по ВАК РФ 01.01.06, кандидат физико-математических наук Добровольская, Лариса Петровна

• Добровольская, Лариса Петровна
• кандидат физико-математических наук
• 2009

Оглавление диссертации кандидат физико-математических наук Добровольская, Лариса Петровна

Введение

Глава 1. Меры качества для оптимальных коэффициентов

§1. Граничные функции некоторых классов .'.

§ 2. Граничные функции класса для формул приближенного суммирования .-.

§ 3. Несколько лемм о произведении синусов.

Глава 2. Теорема А. О. Гельфонда и оптимальные коэффициенты

§ 1. Суммы по приведенным системам вычетов

§ 2. Критерий оптимальности.

§ 3. Применение критерия оптимальности.

Глава 3. Алгоритмы поиска для произвольного N.

§ 1. Обобщенный критерий оптимальности

§ 2. Л-оптимальность

§ 3. Описание общего алгоритма.

§4. Применение разложения параллелепипедальной сетки на сомножители

§ 5. Обоснование алгоритма

§ 6. Трудоемкость алгоритма

§ 7. Оптимизация трудоемкости алгоритма.

Глава 4. Алгоритмы поиска для специальных N.

§ 1. Допустимые последовательности простых.

§ 2. Описание алгоритма для специальных модулей.

§ 3. Явные формулы для Т^ (z)

§ 4. Обоснование алгоритма для специальных модулей

§ 5. Трудоемкость алгоритма для специальных модулей

Введение диссертации (часть автореферата) на тему «Алгоритмы вычисления оптимальных коэффициентов»

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

За пятьдесят лет развития теоретико-числового метода с 1957 года, когда вышла первая работа [29] Н. М. Коробова по этому направлению исследований, с которой и начинается отсчёт в становлении теоретико-числового метода в приближенном анализе, опубликовано значительное количество работ десятков авторов и в нашей стране и за рубежом. Краткая история возникновения этого метода описана её основателем в [42]. Теоретические предпосылки теоретико-числового метода восходят ещё к работе [51] Г. Вейля, вышедшей в 1916 году, в которой, с одной стороны, содержался интегральный критерий равномерного распределения последовательности по модулю 1, а, с другой стороны, в этой работе были получены первые нетривиальные оценки тригонометрических сумм. Именно применение оценок А. Вейля рациональных тригонометрических сумм было основополагающим при исследование первого класс теоретико-числовых сеток — неравномерных сеток.

Существенное изменение теории и практики вычисления кратных интегралов связано с появлением метода оптимальных коэффициентов Н. М. Коробова. Центральной проблемой в этом направлении исследований остается вопрос о построении экономных алгоритмов вычисления оптимальных коэффициентов. Именно этому и посвящена данная диссертация, что объясняет её актуальность.

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

Цель второй главы — получение нового критерия для вычисления оптимальных коэффициентов на случай произвольного составного модуля, основанного на теореме А. О. Гельфонда, а также новое доказательство существования оптимальных коэффициентов для любого составного модуля N.

Цель третьей главы — построение общего алгоритма вычисления оптимальных коэффициентов по произвольному составному модулю N, используещему логарифмическую меру качества, пригодных для комбинированных сеток.

Цель четвертой главы — модификация общего алгоритма из третьей главы на случай специальных модулей N, для которых трудоемкость алгоритма понижается до O(N) элементарных арифметических операций.

Результаты работы являются новыми, полученными автором самостоятельно. Основными результатами данной работы можно считать следующие: дан новый критерий оптимальности набора коэффициентов, основанный на обобщенной теореме Гельфонда, для любого модуля N] введена новая мера оптимальности набора коэффициентов и дан обобщенный критерий оптимальности; построен общий алгоритм вычисления оптимальных коэффициентов для произвольного модуля N, основанный на минимизации обобщенной логарифмической меры качества; построены быстрые алгоритмы вычисления оптимальных коэффициентов для специальных модулей.

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

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

Результаты настоящей диссертации докладывались автором на следующих семинарах: научно-исследовательский семинар "Теория аппроксимации" под руководством профессора В. И. Иванова в Тульском государственном университете; научно-исследовательский семинар "Арифметика, алгоритмы, теория сложности вычислений" под руководством профессора В. Н. Чуба-рикова в Московском государственном университете им. М. В. Ломоносова; научно-исследовательский семинар "Теоретико-числовые методы приближенного анализа" под руководством профессора Н. М. Добровольского в Тульском государственном педагогическом университете им. Л. Н. Толстого; международной конференции "Аналитические и комбинаторные методы в теории чисел и геометрии" в Московском государственном университете им. М. В. Ломоносова. Москва, 2006.

Результаты диссертации опубликованы в работах автора [52], [53], [54], [55] и [56], выполненных по грантам РФФИ 05-01-00672 и 08-0100790.

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

Список литературы диссертационного исследования кандидат физико-математических наук Добровольская, Лариса Петровна, 2009 год

1. Бахвалов Н. С. О приближенном вычислении кратных интегралов // Вестн. Моск. ун-та, 1959. N 4. С. 3 — 18.

2. Бахвалов Н. С., Коробов Н. М., Ченцов Н. Н., Применение теоретико-числовых сеток к задачам приближенного анализа // Труды Четвертого Всесоюзного математического съезда. Л.: Наука, 1964. Т. II. С. 580 587.

3. Боревич 3. И., Шафаревич И. Р. Теория чисел. М.: Наука, 1985.

4. Бухштаб А. А. Теория чисел. М.: Учпедгиз, 1960.

5. Ванькова В. С. Многомерные теоретико-числовые сетки: Дис. . канд. физ.-мат. наук. // Моск. пед. гос. ун-т. М., 1992.

6. Виноградов И. М. Основы теории чисел. М.: Наука, 1981.

7. Воронин С. М. О квадратурных формулах // Изв. РАН. Сер. мат. 1994. Т. 58. N 5. С. 189 194.

8. Воронин С. М. О построении квадратурных формул // Изв. РАН. Сер. мат. 1995. Т. 59. N 4.

9. Воронин С. М., Темиргалиев Н. О квадратурных формулах, связанных с дивизорами поля гауссовых чисел // Мат. заметки. 1989. Т. 46. N 2. С. 34 41.

10. Вронская Г. Т., Добровольский Н. М., Родионова О. В. Сравнения, суммы и произведения по приведенной системе вычетов // Известия ТулГУ. Сер. Математика. Механика. Информатика. Т. 8. Вып. 1. Тула, 2002. С. 10 28.

11. Гельфонд А. О. Исчисление конечных разностей. М.: Наука, 1967.

12. Добровольский М. Н., Добровольский Н. М., Киселева О. В. О произведении обобщенных параллелепипедальных сеток целочисленных решёток // Чебышевский сборник 2002 Т. 3. Вып. 2(4). Тула, Из-во ТГПУ им. Л.Н.Толстого. С. 43 59.

13. Добровольский Н. М. Гиперболическая дзета функция решеток. Деп. в ВИНИТИ 24.08.84, N 6090-84.

14. Добровольский Н. М. О квадратурных формулах на классах Ef(c) и Щ(с). Деп. в ВИНИТИ 24.08.84, N 6091-84.

15. Добровольский Н. М. Теоретико-числовые сетки и их приложения. Дис. . канд. физ.-мат. наук. Тула, 1984.

16. Добровольский Н. М. Многомерные теоретико-числовые сетки и решётки и их приложения: Дис. . док. физ.-мат. наук. Тула, 2000.

17. Добровольский Н. М., Ванькова В. С. Об одной лемме А. О. Гельфонда. Деп. в ВИНИТИ 08.01.87, N 1467-В87.

18. Добровольский Н. М., Есаян А. Р., Реброва И. Ю. Об одном рекурсивном алгоритме для решеток // Известия ТулГУ. Сер. Математика. Механика. Информатика. Т. 5 Вып. 3. Тула, 1999. С. 38 — 51.

19. Добровольский Н. М., Клепикова Н. Л. Таблица оптимальных коэффициентов для приближенного вычисления кратных интегралов // ИОФАН СССР. 63. Москва, 1990. (Препринт.)

20. Добровольский Н. М., Коробов Н. М. Оптимальные коэффициенты для комбинированных сеток. // Чебышевский сборник, Т. 2, Тула, 2001, С. 41 53.

21. Добровольский Н.М., Коробов Н.М. Об оценке погрешности квадратурных формул с оптимальными параллелепипедальными сетками // Чебышевский сборник. Научные труды по математике. Т. 3. Вып. 1(3). Тула, 2002. С. 41 48

22. Добровольский Н. М., Манохин Е. В. Банаховы пространства периодических функций // Изв. ТулГУ. Сер. Механика. Математика. Информатика. Т. 4. Вып. 3. Тула, 1998. С. 56 67.

23. Добровольский Н. М., Манохин Е. В., Реброва И. Ю., Аккурато-ва С. В. О некоторых свойствах нормированных пространств и алгебр сеток // Известия ТулГУ. Сер. Математика. Механика. Информатика. Т. 5. Вып. 1. Тула, 1999. С. 100-113.

24. Добровольский Н. М., Родионова О. В. Квадратурные формулы с обобщенными параллелепипедальными сетками // Изв. ТулГУ. Сер. Механика. Математика. Информатика. Т. 2. Вып. 1. Тула, 1996. С. 71 77.

25. Добровольский Н. М., Родионова О. В. Об одном конечном ряде Фурье и его приложениях // Изв. ТулГУ. Сер. Математика. Механика. Информатика. 1998. Т. 4. Вып. 3. С. 68 — 79.

26. Карацуба А. А. Основы аналитической теории чисел. М.: Наука. ФизМатЛит, 1983.

27. Касселс Д. Введение в геометрию чисел. М.: Мир, 1965.

28. Колмогоров А. Н., Фомин С. В. Элементы теории функций и функционального анализа. М.: Наука, 1968.

29. Коробов Н. М. Приближенное вычисление кратных интегралов с помощью методов теории чисел // ДАН СССР. 1957. N 6. С. 1062 — 1065.

30. Коробов Н. М. Вычисление кратных интегралов методом оптимальных коэффициентов // Вестн. Моск. ун-та, 1959. N 4. С. 19 — 25.

31. Коробов Н. М. О некоторых теоретико-числовых методах приближенного вычисления кратных интегралов. Резюме докл. на заседании Моск. мат. об-ва. // УМН. 1959. Т. 14. Вып. 2 (86). С. 227 230.

32. Коробов Н. М. О приближенном вычислении кратных интегралов // ДАН СССР. 1959. Т. 124, N 6. С. 1207 1210.

33. Коробов Н. М. Свойства и вычисление оптимальных коэффициентов // ДАН СССР 132. 1960. N5. С. 1009 1012.

34. Коробов Н. М. О применении теоретико-числовых сеток // Вычислительные методы и программирование: Сб. Моск. ун-т. 1962. С. 80 102.35