Решетчатые кубатурные формулы высокой тригонометрической точности в четырехмерном случае тема диссертации и автореферата по ВАК РФ 01.01.07, кандидат физико-математических наук Петров, Антон Владимирович

• Петров, Антон Владимирович
• кандидат физико-математических наук
• 2004

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

0 Введение

1 Теоретико—числовые решетки и критические определители

1.1 Краткие сведения о теоретико-числовых решетках.

1.2 Критический определитель.

1.3 Критические решетки и кубатурные формулы.

1.4 Малое шевеление допустимой решетки.

1.5 Преобразование решетки узлов кубатурной формулы

2 Построение серий решетчатых кубатурных формул

2.1 Предварительные сведения.

2.2 Построение серий для случая п = 4.

2.3 Таблицы серий.

2.4 Анализ полученных результатов.

3 Построение решетчатых кубатурных формул

3.1 Предварительные сведения.

3.2 Алгоритм построения формул.

3.3 Таблицы формул, анализ результатов.

Введение диссертации (часть автореферата) на тему «Решетчатые кубатурные формулы высокой тригонометрической точности в четырехмерном случае»

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

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

Общая задача теории численного интегрирования состоит в построении и исследовании формул вида

Г N Lj(x)f(x)dn~Y,Cif(x®)t (0.1) i i=i где fi С oj(x) — весовая функция, х^ — узлы формулы, Сг — коэффициенты формулы. При n = 1 формулы вида (0.1) называют квадратурными формулами, при п ^ 2 — кубатурными.

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

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

Одна из задач построения алгебраически точных формул — это построение таких формул вида (0.1), которые точно интегрируют функции некоторого класса, используя возможно меньшее число узлов.

В частности, существенный интерес представляют решетчатые кубатурные формулы, точно интегрирующие все тригонометрические мономы степени не выше d на единичном гиперкубе [0,1)п, исследованию и построению которых, в основном, для 4-х мерного случая посвящена данная диссертация. Эти формулы интересны тем, что помимо прямого вычисления интегралов они тесно связаны с многомерным дискретным преобразованием Фурье [4].

Решетчатой кубатурной формулой называется формула вида

О Д )n 1 2 г

0.2) где 1 ^ г ^ n, N = N1N2. Nr, Р^ € 2" — порождающие векторы, {а:} означает взятие дробных частей от всех компонентов вектора х € Наименьшее из таких чисел г называется рангом данной кубатурной формулы. Коэффициенты решетчатой кубатурной формулы равны между собой, а система узлов определяет некоторую пространственную решетку. Построение и изучение решетчатых кубатурных формул, обладающих тригонометрическим d-свойством и имеющих минимально возможное число узлов, является одной из наиболее активно развивающихся в последнее время ветвей теории кубатурных формул.

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

Определение точной нижней границы для числа узлов N кубатурной формулы (0.1), обладающей d-свойством, было центральной задачей в 1960-1990 гг. Если для четного d простейшая нижняя граница определяется достаточно просто, то случай нечетного d и симметричной области был далеко не тривиален. Для n-мерной сферы оценку нижней границы впервые дал И. П. Мысовских [5]. Позднее эти результаты Мысовских были обобщены X. Мёллером [33] для широкого класса симметричных областей интегрирования. Найденная им априорная нижняя граница для числа узлов d-точной кубатурной формулы называется границей Мёл-лера. Формулы, число узлов которых совпадают с границей Мёллера, носят название минимальных. Значение границы Мёллера для формул, обладающих тригонометрическим d-свойством, была найдена и в работах М. В. Носкова [10], [13] и И. П. Мысовских [7]. Более того в [10], [12] были получены первые примеры минимальных кубатурных формул с тригонометрическим d-cвойством для п = 2. Позднее в работе [17] были описаны все минимальные формулы для случая п = 2 и нечетного d.

При п ^ 3 исследования и построения кубатурных формул с тригонометрическим d-свойством ведутся исключительно в классе решетчатых кубатурных формул. Таблицы таких формул для п = 3,4 непрерывно улучшаются, то есть в них появляются новые формулы с меньшим числом узлов. Хронологически можно выделить для п = 3 таблицы из [10], [12], [22], [27], для п = 4 таблицы из [13], [27].

Отметим, что, как правило, в основе методов построения формул заданной точности d лежит обработка большого объема экспериментальных данных. Основная проблема известных алгоритмов построения формул, обладающих тригонометрическим rf-свойством, заключается в том, что объем вычислений существенно зависит от тригонометрической точности формулы d, поэтому остается актуальной задача разработки новых, более эффективных алгоритмов построения формул.

Другим не менее важным подходом в построении решетчатых куба-турных формул, является построение серий кубатурных формул [12], то есть задание числа узлов и их координат, а также коэффициентов ку-батурной формулы как функций от тригонометрической точности куба-турной формулы d. Первые серии для п = 3,4,5 построены в работах М. В. Носкова и А. Р. Семеновой: [15], [16], [24], [25]. Однако, все эти серии хотя и описывают формулы сколь угодно высокой тригонометрической точности, но состоят далеко не из минимальных формул. Построению серий для п = 3 также посвящены работы [19], [20], так, например, в [19] получены наилучшие серии решетчатых кубатурных формул в трехмерном случае. Наилучшие серии для n ^ 4 на настоящий момент неизвестны.

Отметим, что из работ, посвященных изучению решетчатых кубатурных формул, стало известно, что минимальные решетчатые формулы, обладающие тригонометрическим d-свойством, существуют лишь для некоторых малых значений d при п ^ 3. Поэтому возник вопрос об уточнении нижней границы числа узлов решетчатой кубатурной формулы (0.2), обладающей тригонометрическим rf-свойством.

Определение уточненной нижней границы числа узлов для решетчатых кубатурных формул, обладающих тригонометрическим d-свойством, берет начало в теории числовых решеток, одной из характеристик которых является так называемый критический определитель. Точные определения, связанные с решетками, мы дадим в первой главе, но в целом, ситуация складывается следующим образом. С каждой теоретико-числовой решеткой связан определитель. Если задана некоторая область И, содержащая начало координат, то теоретико-числовая решетка, которая не имеет с V, общих точек, за исключением начала координат, называется допустимой. Определитель, значение которого совпадает с минимальным значением определителей допустимых решеток, называется критическим для Л. Задача построения формул (0.2), обладающих тригонометрическим d-свойством, с минимальным числом узлов тесно связана с задачей отыскания приближенных значений критического определителя для гипероктаэдра (см. [29]).

На сегодняшний день в теории геометрии чисел известны значения критического определителя для некоторых простых симметричных множеств в двумерном случае, в частности и для квадрата, см. [3] глава 3. Также известно точное значение критического определителя для гипероктаэдра в пространстве с размерностью п = 3 (этот результат принадлежит X. Минковскому [32]). Точного значения критического определителя для случая n ^ 4 на настоящий момент неизвестно.

В настоящей диссертации рассматривается вопрос построения решетчатых кубатурных формул (0.2), обладающих тригонометрическим d-свойством, для случая п = 4. Мы сосредоточились на случае п = 4 потому, что случаи п = 2,3 можно считать практически завершенными. Напомним, что в случае п — 2 построены все минимальные формулы для нечетных d, в случае п = 3 построены минимальные серии формул. В то же время, для случая тг = 4 построены так называемые ^-оптимальные формулы лишь для d = 2,3., 24, а формулы известных серий в случае п = 4 имеют относительно большое число узлов.

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

Все результаты диссертации являются новыми. В настоящей работе приведена уточненная оценка для критического определителя и числа узлов решетчатой кубатурной формулы для случая п = 4. Приведены серии решетчатых кубатурных, обладающих тригонометрическим d(k) = 16к + г для всех к е Ъ. Приведена таблица построенных решетчатых кубатурных формул для нечетных d = 3, 5,., 67.

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

Краткое содержание диссертации.

Первая глава посвящена уточнению известной оценки значения критического определителя для гипероктаэдра Хп при п = 4 и состоит из шести параграфов.

В первом параграфе речь идет о теоретико-числовых решетках. Приводится определение решетки, определение дуальной решетки, а также их основные свойства.

Во втором параграфе вводятся понятия критической решетки и критического определителя. Приводятся некоторые примеры множеств, для которых найдены критические решетки.

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

В четвертом параграфе описан алгоритм преобразования допустимой для гипероктаэдра Хп решетки М в некоторой окрестности, в результате которого можно получить Хп-допустимую решетку с меньшим значением определителя, чем у исходной решетки.

В пятом параграфе приведено подробное описание преобразования конкретной решетки формулы, обладающей тригонометрическим 11-свой-ством, на основе метода, описанного в четвертом параграфе. В таблице 1 приведены параметры кубатурных формул, полученных в результате преобразования указанной решетки. Получена улучшенная оценка сверху критического определителя для гипероктаэдра Х4. Тем самым получена уточненная нижняя оценка числа узлов решетчатой кубатурной формулы (0.2) для случая п = 4.

Вторая глава посвящена построению серий решетчатых кубатурных формул в четырехмерном случае с коэффициентом эффективности х = 4096/207 и состоит из четырех параграфов.

В первом параграфе приводится описание и сравнение двух методов построения серий решетчатых кубатурных формул. Приведены известные серии построенные ранее для случаев п = 2,3,4. Построена серия при п = 3 с максимально возможным коэффициентом эффективности.

Во втором параграфе на конкретном примере описан алгоритм построения серии для п = 4, обладающей тригонометрическим d(k) = 16к + 2 свойством; в качестве базовой решетки выбрана решетка формулы с коэффициентом эффективности н = 4096/207, обладающая тригонометрическим 15-свойством.

В третьем параграфе описаны серии для п = 4 обладающие тригонометрическим d{k) = 16k + r-свойством для всех г = — 1, 0,., 15. Коэффициент эффективности всех серий равен 4096/207. Число узлов полученных серий в асимпототике меньше числа узлов известных ранее серий (см. [13]) примерно на 20%. Формулы полученных серий незначительно отличаются по числу узлов от .ftT-оптимальных формул, полученных в [27] для соответствующих d.

В четвертом параграфе приводится анализ полученных результатов.

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

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

Во втором параграфе приведено описание алгоритма построения формул заданной тригонометрической точности.

В третьем параграфе приведена таблица построенных формул, полученных в результате реализации описанного алгоритма, для тригонометрической точности d = 3, 5,., 67. Исследовано число операций, приведено время работы программы, реализующей алгоритм, для различных d.

В четвертом параграфе приводится анализ полученных результатов.

Основные результаты диссертации опубликованы в [20], [21], [23]. Они докладывались на V международном семинаре-совещании «Кубатурные формулы и их приложения» (Красноярск, 1999 г.), XXXIII научной студенческой конференции (г. Красноярск, 2000 г.), на VI международном семинаре-совещании «Кубатурные формулы и их приложения» (Уфа, 2001 г ), на VII международном семинаре-совещании «Кубатурные формулы и их приложения» (Красноярск, 2003 г.), на семинарах в Красноярском государственном техническом университете.

Основные обозначения

В диссертации используются следующие обозначения: Rn — n-мерное вещественное пространство; Zn — n-мерное целочисленное пространство;

IMI = l^il + кг! + • • • + |®п| — норма вектора х\

Хп = {х G 1" : ||х|| < 1} — n-мерный гипероктаэдр; аХп — множество точек ах, где х Е Хп\

Xn = {i £ Шп : ||х|| = 1} — граница гипероктаэдра; — дробная часть числа у\ у] — целая часть числа у.

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

1. Виноградов И.М. Основы теории чисел. М. 1949.

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

3. Кашкин В.Б., Носков М.В., Осипов Н.Н. Вариант дискретного преобразования Фурье с узлами на параллелепипедальных сетках //Ж. вычисл. матем. и матем. физ. 2001. Т. 41. №3. С. 355-359.

4. Мысовских И.П. Доказательство минимальности числа узлов одной кубатурной формулы для гипершара// Ж. вычисл. матем. и матем. физ., 1966. Т. 6, N 4.

5. Мысовских И.П. О вычислении интегралов по поверхности сферы// ДАН СССР, 1977. Т. 235, N 2. С. 269-272.

6. Мысовских И.П. О кубатурных формулах, инвариантных относительно групп преобразований // Методы вычислений. Д.: Из-во Ле-нингр. ун-та, 1978. Вып.11. С. 3-21.

7. Мысовских И.П. Кубатурные формулы, точные для тригонометрических многочленов // Методы вычислений. Л.: Издательство Ле-нингр. ун-та. — 1988. Вып. 15. — С. 7 19.

8. Мысовских И. П. К построению кубатурных формул, точных для тригонометрических многочленов / / Numerical analysis and mathematical modelling. Banach Center Publications. Vol.24. Warsaw: PWN-Polish Scienntific Publishers, 1990. P. 29 38.

9. Носков М.В. Кубатурные формулы для приближенного интегрирования периодических функций // Методы вычислений. JI.: Изд-во ЛГУ, 1985. Вып. 14. С. 15-23.

10. Носков М.В. Формулы приближенного интегрирования периодических функций // Методы вычислений. JL: Изд-во ЛГУ, 1988. Вып. 15. С. 19-22.

11. Носков М.В. Кубатурные формулы для приближенного интегрирования функций трех переменных // Ж. вычисл. матем. и матем. физ. 1988. Т. 28. №10. С. 1583-1586.

12. Носков М.В. О построении кубатурных формул повышенной тригонометрической точности// Методы вычислений, Под редакцией И. П. Мысовских, Л.: 1991. Вып. 16. С. 16-23.

13. Носков М.В., Осипов Н.Н. Серии кубатурных формул, точных на тригонометрических многочленах // Кубатурные ф-лы и их прилож. Материалы V Междунар. семинара-совещания. Красноярск: КГТУ, 2000. С. 132-136.

14. Носков М.В., Семенова А.Р. О сериях кубатурных формул повышенной тригонометрической точности // Кубатурные ф-лы и их прилож. Красноярск: КГТУ, 1994. С. 68-78.

15. Носков М.В., Семенова А.Р. Кубатурные формулы повышенной тригонометрической точности для периодических функций четырех переменных // Ж. вычисл. матем. и матем. физ. 1996. Т. 36. № 10. С. 5-11.

16. Осипов Н.Н. О построении серий решетчатых кубатурных формул ранга 1, точных на тригонометрических многочленах //Ж. вычисл. матем. и матем. физ. 2002. Т. 42. № 11. С. 1628-1637.

17. Осипов Н.Н., Петров А.В. Серии решетчатых кубатурных формул, точных на тригонометрических многочленах от трех переменных // Кубатурные ф-лы и их при лож. VI Междунар. семинар-совещание. Уфа: ИМВЦ УфНЦ РАН, БГПУ, 2001. С. 91-95.

18. Осипов Н.Н., Петров А.В. Построение серий решетчатых кубатурных формул, точных на тригонометрических многочленах четырех переменных // Вычисл. технологии. 2004. Т. 11, №11 С. 102-110.

19. Петров А.В. Таблица минимальных решетчатых кубатурных формул в трехмерном случае// Кубатурные формулы и их приложения: Тез. докладов V Международного семинара-совещания. Красноярск: КГТУ. 1999. С. 29.

20. Петров А.В. Алгоритмы построения решетчатых кубатурных формул// Кубатурные формулы и их приложения: Материалы VII Международного семинара-совещания. Красноярск: ИПЦ КГТУ, 2003. С. 125-130.

21. Семенова А.Р. Серии кубатурных формул для периодических формул пяти переменных // Комплексный анализ, дифференц. ур-ния, числ. методы и прилож. V. Числ. методы. Уфа: ИМ с ВЦ РАН, 1996. С. 137-146.

22. Семенова А.Р. Вычислительные эксперименты при построении кубатурных формул высокой тригонометрической точности / / Кубатурные формулы и их приложения: Материалы III Международного семинара-совещания. Красноярск: ИМВЦ УНЦ РАН, 1996. — 132 с.

23. Соболев C.JI., Васкевич В. JI. Кубатурные формулы. — Новосибирск: Изд-во ИМ СО РАН, 1996. — 484 с.

24. Cools R., Lyness J.N. Three- and four-dimensional if-optimal lattice rules of moderate trigonometric degree // Math. Comput. 2001. V. 70. P. 1549-1567.

25. Klyuchnikov В. V., Reztsov A relation between cubature formulas and denset lattice packings // East Journal an Approximations. 1995. V. 1. P. 557-570.

26. Lyness J.N. An introduction to lattice rules and their generator matrices // IMA J. of Numer. Analys. 1989. V. 9. P. 405-419.

27. Lyness J.N., S0revik TLattice rules by component scaling // Math. Сотр. 1997. V. 61. P. 799-820.

28. Minkowski H. Geometrie der Zahlen. Leipzig-Berlin, 1896.

29. Minkowski H. Dichteste gitterformige Lagerung kongruenter Korper // Nachr. Koning Ges. Wiss. Gottingen, 1904. P. 311-355.

30. Moller H.M. Lower bounds for the number of nodes in cubature formulae // in: Numerische Integration/ Herausgegeben von. G. Hammerlin, ISNM 45. Basel: Birkhauser Verlag, 1979, p. 221-230.

31. Sloan I.H., Kachoyan P.J. Lattice methods for multiple integration: theory, error analysis and examples // SIAM J. Numer. Analys. 1987. V. 24. P. 116-128.

32. Sloan I.H., Lyness J.N. The representation of lattice quadrature rules as multiple sums // Math. Comput. 1989. V. 52. P. 81-94.