Минимальные квадратурные и кубатурные формулы, точные для полиномов Хаара тема автореферата и диссертации по математике, 01.01.07 ВАК РФ

Введение

§0.1. О содержании диссертации.

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

Глава 1. Функции Хаара и Пт-сетки

§1.1. Определение и свойства функций Хаара

§1.2. Ряды Хаара

§1.3. Кубатурные формулы с узлами, образующими

Пг-сетку

Глава 2. Минимальные квадратурные формулы, точные для полиномов Хаара

§2.1. Основные определения. Свойства /с-функций и квадратурных формул, точных для полиномов Хаара.

§2.2. Вспомогательные определения и леммы

§2.3. Нижние оценки числа узлов квадратурных формул, обладающих rf-свойством

§2.4. Необходимые и достаточные условия минимальности квадратурных формул, точных для полиномов Хаара.

§2.5. Примеры

Глава 3. Минимальные кубатурные формулы, точные для полиномов Хаара в двумерном случае

§3.1. Основные определения. Свойства дс-мономов

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

§3.3. Вспомогательные определения и леммы

§3.4. Уточнение нижних оценок числа узлов кубатурных формул, обладающих d-свойством при d ^ 4.

§3.5. Примеры

§3.6. Построение минимальных кубатурных формул, обладающих ^-свойством при d^.1.

§0.1. О содержании диссертации.

Построение и исследование формул приближенного интегрирования вида г N g(xi,. ,xn)f(xu. ,xn)dx 1 .dxn (1) a k=1 ведется со времен И. Ньютона. В данной формуле через Q обозначена область интегрирования из Rn, д{хi,. , жп) — весовая функция, Р& — точки из О, называемые узлами формулы, С к — коэффициенты при узлах Рь (некоторые действительные числа), А: = 1,. , 7V. При п = 1 эти формулы носят называние квадратурных, а при п > 1 — кубатурных. Особый интерес в теории приближенного интегрирования вызывает задача построения таких формул вида (1), которые точно интегрируют некоторый заданный набор функций, используя наименьшее возможное число узлов. Эти формулы называются минимальными кубатурными (квадратурными) формулами, точными для функций из указанного набора. Минимизация числа узлов приводит к сокращению объема вычислений и, следовательно, к уменьшению машинной погрешности округлений. Следует отметить, что задача сокращения объема вычислений была и остается одной из самых актуальных в вычислительной математике.

При п = 1 для набора функций {f(x)}, являющихся алгебраическими многочленами степеней не выше заданного числа d, задача построения минимальных квадратурных формул решена полностью, причем в частном случае весовой функции д(х), тождественно равной 1, ее решил

К. Гаусс. При п > 1 большая часть минимальных формул вида (1), точных для алгебраических многочленов степеней, не превосходящих заданного d, получена для узкого класса областей интегрирования. Почти все эти формулы построены в случае д(х) = 1 и при небольших значениях d.

Так, например, в случае двумерной симметричной области интегрирования И. Радоном [50] была получена кубатурная формула с 7 узлами, точная на всех многочленах степени не выше 5, и доказана минимальность этой формулы. В [12] приведено другое доказательство ее минимальности, автором которого является И. П. Мысовских.

Существенный интерес представляют квадратурные формулы, точно интегрирующие алгебраические многочлены на сфере. Такие формулы исследовались В. И. Лебедевым [13 — 16], Г. Н. Салиховым [32], С. И. Ко-няевым [9, 10, 11] и другими авторами.

Минимальные квадратурные формулы, точные для тригонометрических полиномов степени не выше фиксированного d, изучены И. И. Кеда, И. П. Мысовских [17, 18] и другими авторами. Полученные ими результаты изложены, например, в монографии В. И. Крылова [12]. Минимальные кубатурные формулы, точно интегрирующие тригонометрические многочлены, исследовались в основном в работах М. В. Носкова [22 — 28], И. П. Мысовских [17, 19, 20, 21], М. Beckers, R. Cools [39] и Н. Н. Осипова [27, 29, 30, 31]. Следует отметить, что внимание многих авторов привлекают исследования кубатурных формул с решетчатой структурой узлов. Построение серий решетчатых кубатурных формул, точных на тригонометрических многочленах, было начато в работах М. В. Носкова [23, 26] и продолжено в [27, 28 — 31]. В частности, Н. Н. Осиповым [29, 30] были описаны все минимальные решетчатые формулы для приближенного вычисления двойного интеграла, точные на тригонометрических многочленах степени не выше заданного числа d. Однако в трехмерном случае такая задача пока еще не решена.

В диссертации ставится вопрос о построении минимальных формул для функций системы {хл-(ж)}, называемых обычно функциями Хаара. Эта система является ортогональной и обладает следующим замечательным свойством: любая непрерывная на отрезке [0,1] функция разлагается в равномерно сходящийся ряд по функциям системы. Благодаря указанному свойству функций {Xfc(®)}, формулы вида (1), точные для всех полиномов Хаара степеней, не превосходящих достаточно большого числа с?, имеют сравнительно малую погрешность [34]. Формулы приближенного вычисления интегралов, точные для полиномов по системе функций Хаара, можно найти в работах И. М. Соболя [34, 35] и К. Entacher [42, 43, 44]. В их трудах точность квадратурных и кубатурных формул на конечных суммах Хаара использовалась при выводе оценок погрешностей этих формул, однако вопрос минимизации числа узлов, которому уделено основное внимание в настоящей работе, не рассматривался.

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

Все результаты диссертации являются новыми. Вопросы о наименьшем возможном числе узлов и построении минимальных формул, точных для полиномов Хаара, ранее не исследовались. В настоящей работе описаны все минимальные квадратурные формулы с произвольной суммируемой весовой функцией, точные для функций Хаара первых d групп, где d — некоторое фиксированное число. В двумерном случае выведены оценки числа узлов кубатурных формул, точных для полиномов Хаара степеней не выше d, построены минимальные кубатурные формулы, обладающие указанным свойством при d = 1,2,3,5,6, а также кубатурная формула, точная для полиномов Хаара степеней не выше 4, число узлов которой на 1 больше нижней границы, фигурирующей в одной из установленных оценок. Кроме того, получены рекуррентные соотношения, которые позволяют в двумерном случае для любого d ^ 7 строить минимальные кубатурные формулы, точные для полиномов Хаара степеней, не превосходящих d.

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

Результаты диссертационной работы могут быть использованы при построении алгоритмов дискретного преобразования Фурье по системе функций {хл-(я)} и для дальнейшего теоретического исследования кубатурных формул, точных на полиномах Хаара.

Указанные результаты докладывались на VI международном семинаре-совещании "Кубатурные формулы и их приложения" 2—7 июля 2001 г., на III международной конференции "Симметрия и дифференциальные уравнения" 25—29 августа 2002 г., на семинарах Красноярского государственного технического университета и опубликованы в центральной и местной печати.

Перейдем теперь к краткому описанию диссертации.

В первой главе приведены свойства функций используемые в теории квадратурных и кубатурных формул, доказанные в [3, 34, 46, 47].

В §1.1 формулируется определение функций {xk(%)} и двоичных промежутков. Отмечено, что в литературе можно встретить различные определения функций (х^ж)}, отличающиеся значениями этих функций в точках разрыва. Перечислены основные свойства функций Хаара.

В §1.2 приведены утверждения теорем о свойствах сумм рядов Хаара и Фурье-Хаара, о связи между указанными рядами. Сформулированы свойства системы Хаара, касающиеся сходимости рядов Хаара и Фурье-Хаара в пространстве Lp.

В §1.3 вводятся понятия двоичного параллелепипеда и Пт-сеток. Приведено утверждение о точности кубатурных формул вида (1) с узлами, образующими Пг-сетку, и равными коэффициентами при этих узлах, для конечных сумм Хаара.

В главе 2 описаны все минимальные квадратурные формулы с произвольной весовой функцией, точные для функций Хаара, выявлена зависимость числа узлов от свойств весовой функции, указаны правила выбора узлов и значений коэффициентов при узлах таких формул, приведены примеры минимальных квадратурных формул для некоторых весовых функций. Указанные результаты были анонсированы в [4] и доказаны в [8].

В §2.1 введено понятие полиномов Хаара, квадратурных формул, обладающих с?-свойством, «-функций группы номер d. Сформулирована постановка решаемой задачи. Доказаны леммы о свойствах /с-функций и квадратурных формул, точных для полиномов Хаара степеней, не превосходящих заданного d.

В §2.2 доказаны леммы о необходимом условии точности квадратурных формул для полиномов Хаара степеней не выше d и необходимом условии минимальности формул, обладающих ^-свойством. Введено определение группы ^-обособленных узлов, доказаны леммы, в которых сформулированы достаточные условия существования групп ^-обособленных узлов на промежутках специального вида. Приведена система равенств, которая имеет место в том и только том случае, когда квадратурная формула обладает ^-свойством. Эта система рассматривается как система уравнений относительно коэффициентов при узлах формулы. Доказаны леммы, устанавливающие достаточные, а также необходимые .и достаточные условия разрешимости указанной системы уравнений.

В §2.3 введены вспомогательные определения. Установлены нижние оценки числа узлов квадратурных формул, обладающих ^-свойством.

В §2.4 с помощью утверждений, доказанных в предыдущих параграфах главы 2, устанавливаются необходимые и достаточные условия минимальности кубатурной формулы, обладающей d-свойством. В конце параграфа сделано несколько замечаний по поводу вычисления коэффициентов минимальной квадратурной формулы, точной для полиномов Хаара.

В §2.5 приведены примеры минимальных кубатурных формул с различными весовыми функциями, обладающих ^-свойством.

В главе 3 установлены нижние оценки числа узлов кубатурных формул, точных для полиномов Хаара в двумерном случае, приведены примеры минимальных формул, обладающих ^-свойством для d = 1,2,3,5,6, пример кубатурной формулы, точной для всех полиномов Хаара степеней, не превосходящих 4, число узлов которой на 1 больше нижней границы, фигурирующей в одной из полученных оценок, доказаны рекуррентные соотношения, позволяющие построить для любого d ^ 7 минимальную кубатурную формулу, обладающую ^-свойством. Результаты, изложенные в указанной главе, были анонсированы в [5] и доказаны в [6, 7].

В §3.1 введено определение полиномов Хаара степени d в двумерном случае, мономов Хаара, /^-мономов, понятие кубатурной формулы, обладающей ^-свойством. Сформулирована постановка решаемой задачи. Доказаны леммы о свойствах к-мономов и кубатурных формул, точных для полиномов Хаара степеней, не превосходящих заданного d, а также о представлении произведения функций Хаара в точках непрерывности этих функций.

В §3.2 доказано необходимое условие точности кубатурной формулы для полиномов Хаара степеней не выше d. Получены оценки числа узлов кубатурной формулы, обладающей d-свойством.

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

В §3.3 доказана лемма, устанавливающая достаточные условия существования не менее двух узлов кубатурной формулы на каждом из замкнутых прямоугольников специального вида. Установлена справедливость лемм, формулирующих достаточные условия существования не менее t + 1 узлов рассматриваемой формулы на указанных прямоугольниках, причем в некоторых случаях рассматриваются прямоугольники, не являющиеся замкнутыми множествами.

В §3.4 выведены нижние оценки числа узлов кубатурных формул, обладающих ^-свойством.

В §3.5 приведены примеры минимальных кубатурных формул, обладающих ^-свойством для d = 1,2,3,5,6, и пример кубатурной формулы, точной для всех полиномов Хаара степеней, не превосходящих 4, число узлов которой на 1 больше нижней границы, фигурирующей в одной из полученных оценок.

В §3.6 доказана теорема, позволяющая для любого d ^ 7 строить минимальные кубатурные формулы, обладающие ^-свойством.

Диссертационная работа выполнена при поддержке гранта РФФИ 9901-00765.

ЗАКЛЮЧЕНИЕ.

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

1. Описаны все минимальные квадратурные формулы с произвольной суммируемой весовой функцией, точные для функций Хаара (теоремы 4,4' главы 2).

2. В двумерном случае установлены простейшие оценки числа узлов кубатурных формул, точных для полиномов Хаара степеней, не превосходящих d (теоремы 1, 2 главы 3).

3. Указанные выше оценки уточнены для d ^ 4 (теорема 4 главы 3).

4. В двумерном случае построены минимальные кубатурные формулы, точные для полиномов Хаара степеней, не превосходящих d при d = 1,2,3,5,6, а также кубатурная формула, точная для полиномов Хаара степеней не выше 4, число узлов которой на 1 больше нижней границы, фигурирующей в оценке из теоремы 4 главы 3 (§3.5).

5. Установлены рекуррентные соотношения, позволяющие в двумерном случае для любого d ^ 7 строить минимальные кубатурные формулы, точные для полиномов Хаара степеней, не превосходящих d (теорема 5 главы 3).

1. Бойко JI. Л. Обобщенное преобразование Фурье-Хаара на конечной абелевой группе // Цифровая обработка сигналов и ее применения. М.: 1981. — С. 12 22.

2. Ермаков С. М. Интерполирование по случайным точкам // Журнал вычислительной математики и математической физики. — 1963. Т. 3. №1. — С. 186 190.

3. Качмаж СШтейнгауз Г. Теория ортогональных рядов. — М.: Физматгиз, 1958.

4. Кириллов К. А. Минимальные квадратурные формулы, точные для полиномов Хаара // Кубатурные формулы и их приложения: Материалы VI международного семинара-совещания «Кубатурные формулы и их приложения». Уфа: ИМВЦ УНЦ РАН. — 2001. — С. 66 -72.

5. Кириллов К. А. Минимальные кубатурные формулы, точные для полиномов Хаара в К2 // Вопросы математического анализа. Красноярск: Изд-во Краснояр. гос. техн. ун-та. — 2002. Вып. 6. — С. 108 117.

6. Кириллов К. А. Минимальные кубатурные формулы, точные для полиномов Хаара в двумерном случае// Рукопись деп. в ВИНИТИ 06.02.2003., №231 — В2003. — 23 с.

7. Кириллов К. А. , Носков М. В. Минимальные квадратурные формулы, точные для полиномов Хаара // Журнал вычислительной математики и математической физики. — 2002. Т. 42. №6. — С. 791 -799.

8. Коняев С. И. Квадратурные формулы на сфере, инвариантные относительно группы икосаэдра: Препринт ИАЭ — 2516. — М., 1975.

9. Коняев С. И. Инвариантные формулы интегрирования на сфере: Препринт ИАЭ — 2553. — М., 1975.

10. Крылов В. И. Приближенное вычисление интегралов. — М.: Наука, 1967.

11. Лебедев В. И. О квадратурах на сфере // Журнал вычислительной математики и математической физики. — 1976. Т. 16. №2. — С. 293- 306.

12. Лебедев В. И. Квадратурные формулы для сферы 25 29 порядка точности // Сибирский математический журнал. — 1977. Т. 18. № 1.1. С. 132 142.

13. Лебедев В. И. , Скороходов A. Л. Квадратурная формула 59-го порядка для сферы // ДАН. — 1994. Т. 338. № 4. — С. 454 456.

14. Мысовских И. П. Интерполяционные кубатурные формулы. — М.: Наука, 1981.

15. Мысовских И. П. Квадратурные формулы наивысшей тригонометрической степени точности // Журнал вычислительной математики и математической физики. — 1985. Т.25. №8. — С. 1246 1252.

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

17. Мысовских И. П. Об одном представлении воспроизводящего ядра // Журнал вычислительной математики и математической физики.1996. Т.36. №3. — С. 28 33.

18. Мысовских И. П. Лекции по методам вычислений. — СПб,1998.

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

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

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

22. Носков М. В. О кубатурных формулах для функций, периодических по части переменных // Журнал вычислительной математики и математической физики. — 1991. Т. 30. №9. — С. 1414 1419.

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

24. Носков М. В. , Осипов Н. Н. Минимальные приближенные представления линейных функционалов, точные на алгебраических многочленах // Кубатурные формулы и их приложения: Сборник трудов IV семинара-совещания. Улан-Удэ: ВСГТУ. — 1997. — С. 57 75.

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

26. Салихов Г. Н. Кубатурные формулы для многомерных сфер. Ташкент: Фан. — 1985. — 104 с.

27. Середа С. П. Построение дискретных ортогональных преобразований // Рукопись деп. в ВИНИТИ 12.01.1999., №25 — В 99. — 5 с.

28. Соболь И. М. Многомерные квадратурные формулы и функции Хаара. — М.: Наука, 1969.

29. Соболь И. М. О весовых квадратурных формулах // Сибирский математический журнал. — 1978. 19. №5. — С. 1196 1200.

30. Тетунашвили Ш. Г. О нуль-рядах по тригонометрической системе и по системам Уолша и Хаара // Мат. сб. — 1996. Т. 187. №3. —1. С. 103 142.

31. Ульянов П. Я. О рядах по системе Хаара. Матем. сб. — 1964. Т. 63. №3. — С. 356 391.

32. Шер А. П. Алгоритмы разложения по системе дискретных произвольно упорядоченных функций Хаара // Прикл. вопросы статист, анализа. Владивосток. — 1988. — С. 103 119.

33. Beckers М. , Cools R. A relation between cubature formulae of trigonometric degree and lattice rules j j Numerical Integration IV, Birkhauser Verlag.1993. — P. 13 24.

34. Birkhoff G., Kampe de Feriet J. Kinematics of homogeneous turbulence 11 J. Math. Mech. — 1962. — №3. — P. 319-340.

35. Entacher K. Quasi-Monte Carlo methods for numerical integration of multivariate Haar series // BIT (Dan). — 1997.— Vol. 37. — №4. — P. 846 861.

36. Entacher K. Quasi-Monte Carlo methods for numerical integration of multivariate Haar series II // BIT (Dan). — 1998. — Vol. 38. — №2.1. P. 283 292.

37. Entacher К. Generalized Haar function system, digital nets and quasi-Monte Carlo integration //In H.H. Szu, editor Wavelet Application III, Proc. SPE 2762. — 1996.

38. Fischer ВPreston J. Wavelets based on orthogonal polynomials // Math. Comput. — 1997. — Vol. 66. — №226. — P. 1593 1618.

39. Haar A. Osszegyujtott munkai. — Budapest: Gesammelte Arbeiten, 1959.

40. Haar A. Zur Theorie der orthogonalen Funktionensysteme // Math. Ann. — 1910. — Vol. 69. — P. 331 371.

41. Kampe de Feriet J. Pseudo-integrales de Stiltjes aleatoires // C. R. Acad. Sci. — 1961. — Vol. 252. — № 15. — P. 2162 2165.

42. Kolzow L.} Pietrich V. Wavelets. A tutorial and bibliography // Workshop «Teor. Misura e anal, reale». Rend. I-st math. Univ. Trieste. — 1994. — №26.— P. 49 220.

43. Radon J. Zur mechanischen Kubatur // Monatsh. Math. — 1948. — Vol. 52. — №4. — P. 286 300.- vxb