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

Оглавление
Введение
О содержании диссертации......................................
Основные обозначения..........................................
Глава 1. Функции Хаара и Пг-сетки
1.1. Определение и свойства функций Хаара. Ряды Хаара . . .
1.2. Линейные нормированные пространства 5Р и На..............
1.3. Кубатурные формулы с узлами, образующими Пг-сетку . .
Глава 2. Построение минимальных формул приближенного интегрирования, точных для полиномов Хаара
2.1. Основные определения и леммы.............................
2.1.1. Полиномы Хаара одной переменной. Понятие квад-
ратурной формулы, обладающей (/-свойством Хаара. Определение к-функций и их свойства..........
2.1.2. Полиномы Хаара двух переменных. Понятие куба-турной формулы, обладающей (/-свойством Хаара в двумерном случае. Определение /с-мономов и их свойства ...............................................
2.2. Описание всех минимальных весовых квадратурных фор-
мул, обладающих (/-свойством Хаара.......................
2.2.1. Вспомогательные определения и леммы...............
2.2.2. Нижние оценки числа узлов квадратурных формул,
обладающих (/-свойством Хаара.....................
2
2.2.3. Необходимые и достаточные условия минимальности
квадратурных формул, обладающих (2-свойством Хаара.............................................. 52
2.2.4. Примеры минимальных квадратурных формул, об-
ладающих (2-свойством Хаара........................ 63
2.3. Минимальные кубатурные формулы, обладающие (1-свойством Хаара для с1 ^ 3 в двумерном случае................. 66
2.3.1. Вывод простейших оценок числа узлов кубатурных
формул, точных для полиномов Хаара................. 66
2.3.2. Примеры минимальных кубатурных формул, обла-
дающих (2-свойством Хаара для (I = 1, 2, 3........ 69
2.4. Построение в двумерном случае минимальных кубатурных
формул, обладающих (2-свойством Хаара для <2 > 3 . . . . 70
2.4.1. Вспомогательные определения и леммы............... 70
2.4.2. Уточнение нижних оценок числа узлов кубатурных
формул, обладающих (2 свойством Хаара при (I ^ 4 74
2.4.3. Некоторые примеры минимальных кубатурных фор-
мул, обладающих (2-свойством Хаара в случае (I. > 3 78
2.4.4. Построение минимальной кубатурной формулы, об-
ладающей (с/ + 2)-свойством, на основе минимальной кубатурной формулы, обладающей (2-свойством 82
2.4.5. Построение минимальных кубатурных формул выс-
ших степеней точности Хаара......................... 96
2.5. Приложение кубатурных формул, точных для полиномов
Хаара, к двумерному дискретному преобразованию Хаара 106
2.5.1. Классический метод дискретного преобразования Хаара......................................................107
2.5.2. Вариант дискретного преобразования Хаара с узлами
на По-сетках........................................109
Глава 3. Оценки погрешности формул приближенного
•3
интегрирования, точных для полиномов Хаара 114
3.1. Оценки погрешности квадратурных формул, обладающих (/-свойством................................................115
3.1.1. Оценки нормы функционала погрешности квадратурных формул на пространствах Зр (весовая функция д(х) = 1)...........................................115
3.1.2. Оценки нормы функционала погрешности квадратурных формул на пространствах Иа.......................124
3.1.3. Оценки нормы функционала погрешности весовых
квадратурных формул на пространствах 5Р...........127
3.2. Оценки погрешности кубатурных формул, обладающих (I-
свойством в двумерном случае............................146
3.2.1. Оценки нормы функционала погрешности кубатур- -ных формул на-пространствах 5Р . . . . 146
3.2.2. Оценки нормы функционала погрешности кубатур-
ных формул на пространствах На....................166
Заключение 172
Список литературы 173
4
Введение
О содержании диссертации
Построение и исследование формул приближенного интегрирования вида
г *
д(х и...,хп)/(хи...,хп)с1хх ... (1хп (0.1)
О
ведется со времен И. Ньютода, В. данной формуле через П обозначена область интегрирования из Кп, д(х),..., хп) — весовая функция, (#1 ,... ,Хп^) — точки из О, называемые узлами формулы. С* — коэффициенты при узлах (х^\... ,а4^) (некоторые действительные числа.), г = 1,... ,ЛГ. При п = 1 эти формулы носят называние квадратурных, а при п > 1 — кубатурных. Особый интерес в теории приближенного интегрирования вызывает задача построения таких формул вида (0.1), которые точно интегрируют некоторый заданный набор функций, используя наименьшее возможное число узлов. Эти формулы называются минимальными кубатурными (квадратурными) формулами, точными для функций из указанного набора. Минимизация числа узлов приводит к сокращению объема вычислений и, следовательно, к уменьшению машинной погрешности округлений. Следуег отметить, что задача сокращения объема вычислений была и остается одной из самых актуальных в вычислительной математике.
При ?г = 1 для набора функций {/(х)}, являющихся алгебраическими многочленами степеней не выше заданного числа ф задача построения минимальных квадратурных формул решена полностью, причем в
5
частном случае весовой функции д(х), тождественно равной 1, ее решил К.Ф. Гаусс. Квадратурные формулы Гаусса с N узлами точны для любого алгебраического многочлена степени не выше 2N - 1 и являются формулами наивысшей алгебраической степени точности. Большинство алгоритмов вычисления узлов и коэффициентов при узлах квадратур Гаусса реализовано для сравнительно небольших значений числа узлов N (меньше или порядка 100), причем эти алгоритмы требуют 0(N'2) операций при различных значениях константы в знаке О. Я. VI. Жилейки-ным и Л. Г. Васильевой [11| построен и реализован алгоритм вычисления узлов и коэффициентов при узлах квадратуры Гаусса для сколь угодно большого N за количество операций O(N).
При п > 1 большая часть минимальных формул вида (0.1), точных для алгебраических многочленов степеней, не превосходящих заданного d, получена для узкого класса областей интегрирования. Почти все эти формулы построены в случае д(х) = 1 и при небольших значениях d.
Так, например, в случае двумерной симметричной области интегрирования И. Радоном [127) была получена кубатурная формула с 7 узлами, точная на всех многочленах степени не выше 5, и доказана минимальность этой формулы. В [56] приведено другое доказательство ее минимальности, автором которого является И. П. Мысовских.
Существенный интерес представляют квадратурные формулы, точно интегрирующие алгебраические многочлены на сфере. Такие формулы исследовались В. И. Лебедевым [57] - [60], Г. Н. Салиховым |98], С. И. Ко няевым |51| - [53] и другими авторами.
Минимальные квадратурные формулы, точные для тригонометрических полиномов степени не выше фиксированного (/, изучены А. X. Турецким [107], [108], Н. П. Кеда [28], [29], И. И. Мысовских [63], [64] и другими авторами. Полученные ими результаты изложены в монографии В. И. Крылова [56]. Минимальные кубатурные формулы, точно интегрирующие тригонометрические многочлены, исследовались в основном в
6
работах М. В. Носкова [68] - |81], И. Г1. Мысовских [63) - [67], М. Beckers, R. Cools [112] и Н. Н. Осипова [76|, [82] - [93]. Следует отметить, что внимание многих авторов привлекают исследования кубатурных формул с решетчатой структурой узлов. М. Д. Рамазановым [94| - [97) установлены достаточные условия оптимальности по вариации коэффициентов и решетки, даны алгоритмы построения решетчатых кубатурных формул, удовлетворяющих установленным достаточным условиям оптимальности, по этим алгоритмам составлены программы вычисления интегралов по двумерным ограниченным областям произвольных форм. Построение серий решетчатых кубатурных формул, точных на тригонометрических многочленах, было начато в работах М. В. Носкова [71], [74] и продолжено в [76| - (93|. В частности, Н. Н. Осиповым [82], [83| были описаны все минимальные решетчатые формулы для приближенного вычисления двойного интеграла, точные на тригонометрических многочленах степени не выше заданного числа d. В трехмерном и четырехмерном случаях им построены серии решетчатых кубатурных формул с тригонометрическим г/(/с)-свойством: в трехмерном случае — наилучшие по числу узлов [88), [91), [92), в четырехмерном — серии, имеющие высокий коэффициент эффективности [93]. Для n-мерного случая Н. И. Осипов предложил методику построения серий решетчатых кубатурных формул ранга 1 с тригонометрическим <Д/с)-свойством и высоким коэффициентом эффективности.
В диссертации ставится вопрос о построении минимальных формул для функций системы {Xfc(x)}, называемых обычно функциями Хаара. Эта система является ортогональной и обладает следующим замечательным свойством: любая непрерывная на отрезке [0,1] функция разлагается в равномерно сходящийся ряд по функциям системы. Благодаря указанному свойству функций {Xfe(s)}i формулы вида (0.1), точные для всех полиномов Хаара степеней, не превосходящих достаточно большого числа d) имеют сравнительно малую погрешность [104]. Формулы при-
7
ближенного вычисления интегралов, точные для полиномов но системе функций Хаара, можно найти в работах И. М. Соболя [104], [105] и К. Entacher [115] - [117]. В их трудах точность квадратурных и куба-турных формул на конечных суммах Хаара использовалась при выводе оценок погрешности этих формул, однако вопрос минимизации числа узлов, которому уделено основное внимание в настоящей работе, не рассматривался.
Цель данной диссертации заключается в установлении нижних оценок числа узлов квадратурных и кубатурных (в двумерном случае) формул, точных для полиномов по системе Хаара, построении указанных формул с минимальным возможным числом узлов, а также в нахождении оценок погрешности формул приближенного интегрирования, точных для полиномов Хаара.
Все результаты диссертации являются новыми. Вопросы о наименьшем возможном числе узлов и построении минимальных формул, точных для полиномов Хаара, ранее не исследовались. В настоящей работе описаны все минимальные квадратурные формулы с произвольной суммируемой весовой функцией, точные для функций Хаара первых d групп, где d — некоторое фиксированное число. В двумерном случае получены нижние оценки числа узлов кубатурных формул, точных для полиномов Хаара степеней не выше d, построены минимальные кубатурные формулы, обладающие указанным свойством при d = 1,2,3,5, б, 7, а также кубатурная формула, точная для полиномов Хаара степеней не выше 4, число узлов которой на 1 больше нижней границы, фигурирующей в одной из установленных оценок. Разработан алгоритм, позволяющий на основе минимальных кубатурных формул, обладающих do-свойством Хаара для d0 = 6 (do = 7), строить минимальные кубатурные формулы, обладающие d-свойством Хаара для любого наперед заданного чегного (нечетного) числа d. Получены оценки погрешности на пространствах Sp квадратурных формул с весовой функцией g € Loo[0,1) и g € Lç[0> l
8
(р~] +Ц~] = 1), обладающих ^-свойством Хаара, а также оценки погрешности на пространствах *$р и На квадратурных и кубатурных формул с весовой функцией д(х) = 1, обладающих ^-свойством Хаара соответственно в одномерном и двумерном случае.
При проведении исследований использовались методы теории функций. функционального анализа, а также вычислительной математики, в частности, теории кубатурных формул.
Результаты диссертационной работы могут быть использованы для приближенного вычисления интегралов, при построении алгоритмов дискретного преобразования Хаара и для дальнейшего теоретического исследования кубатурных формул, точных на полиномах Хаара.
Указанные результаты докладывались на VI международном семинаре-совещании "Кубатурные формулы и их приложения" (Уфа, 3-7 июля 2001 г.), III международной конференции "Теория симметрии и дифференциальные уравнения"(Красноярск, 25 - 29 августа 2002 г.), уфимской международной математической конференции "Теория функций, дифференциальные уравнения, вычислительная математика" , посвященной памяти А. Ф. Леонтьева (Уфа, 28 мая - 1 июня 2007 г.), международной конференции "Дифференциальные уравнения. Функциональные пространства. Теория приближений" , посвященной 100-летию со дня рождения С. Л. Соболева (Новосибирск, 5 - 12 октября 2008 г.), международной конференции "Кубатурные формулы, методы Монте-Карло и их приложения" (Красноярск, 4-8 июля 2011 г.), на семинарах Сибирского федерального университета и Института вычислительного модели рован ия СО РАН.
Перейдем к краткому описанию диссертационной работы.
В главе 1 приведены свойства функций {х/ь(зО}> используемые в теории квадратурных и кубатурных формул, доказанные в [25), |Ю4], [121],
В разделе 1.1 формулируется определение функций {хД.т)} и двоич-
9
ных промежутков. Отмечено, что в литературе можно встретить различные определения функций {х*(я)Ь отличающиеся значениями этих функций в точках разрыва. Перечислены основные свойства функций Хаара. Приведены утверждения теорем о свойствах сумм рядов Хаара и Фурье - Хаара, о связи между указанными рядами. Сформулированы свойства системы Хаара, касающиеся сходимости рядов Хаара и Фурье - Хаара в пространстве ЬР\О, Г.
В разделе 1.2 приводятся определения классов функций Зр и На в одномерном и двумерном случаях.
В разделе 1.3 формулируются определения двоичного параллелепипеда и Пг-сеток. Приведено утверждение о точности кубатурных формул вида (0.1) с узлами, образующими П,-сетку, и равными коэффициентами при этих узлах, для конечных сумм Хаара, а также теорема об оценках нормы функционала погрешности кубатурных формул на пространствах 5Р и ЯЛ, исследованных И. VI. Соболем (104).
В главе 2 описаны все минимальные квадратурные формулы с произвольной весовой функцией, точные для функций Хаара, выявлена зависимость числа узлов от свойств весовой функции, указаны правила выбора узлов и значений коэффициентов при узлах таких формул, приведены примеры минимальных квадратурных формул для некоторых весовых функций. В этой главе исследованы также кубатурные формулы, точные для полинимов Хаара в двумерном случае: получены нижние оценки числа узлов кубатурных формул, обладающих ^-свойством Хаара ((]. ^ 2), приведены примеры минимальных формул, обладающих ^свойством Хаара для (I = 1,2,3,5,6,7, пример кубатурной формулы, точной для всех полиномов Хаара степеней, не превосходящих 4, число узлов которой на 1 больше нижней границы, фигурирующей в одной из полученных оценок, доказаны рекуррентные соотношения для нахождения координат узлов минимальной кубатурной формулы, обладающей (^-Ь2)-свойством Хадра, с помощью минимальной кубатурной формулы,
10
обладающей ^-свойством ((1. ^ 6), на основе этих рекуррентных соотношений разработан алгоритм, позволяющий строить минимальные куба-турные формулы, обладающие ^-свойством Хаара для любого наперед заданного четного (нечетного) числа ф исходя из минимальных кубатур-ных формул, обладающих Ду-свойством Хаара для Д) = б (с!о — 7).
13 разделе 2.1 для одномерного и двумерного случаев приведены определения полиномов Хаара, кубатурных (квадратурных) формул, обладающих ^/-свойством Хаара, введены специальные функции и рассмотрены некоторые их свойства. В подразделе 2.1.1 введено понятие полиномов Хаара одной переменной, квадратурных формул, обладающих сI-свойством, ас-функций — специальных функций, представимых в виде линейных комбинаций функций Хаара. Сформулирована постановка задачи, решаемой в одномерном случае. Доказаны свойства «-функций и квадратурных формул, точных для полиномов Хаара степеней, не превосходящих заданного числа (I. В подразделе 2.1.2 введено определение полиномов Хаара двух переменных, мономов Хаара, ас-мономов — попарных произведений ас- функций переменной X] на ас функции переменной Х‘2, понятие кубатурной формулы, обладающей ^-свойством. Сформулирована постановка задачи, решаемой в двумерном случае. Доказаны свойства ас-мономов и кубатурных формул, точных для полиномов Хаара степеней, не превосходящих заданного с/, а также лемма о представлении произведения функций Хаара в точках непрерывности этих функций.
В разделе 2.2 проведено описание всех минимальных весовых квадратурных формул, обладающих ^-свойством Хаара, рассмотрены некоторые примеры минимальных формул. В подразделе 2.2.1 доказаны леммы о необходимом условии точности квадратурных формул для полиномов Хаара степеней не выше с/ и необходимом условии минимальности формул, обладающих ^-свойством. Введено определение группы (I-обособленных узлов, доказаны леммы, в которых сформулированы до-
11
статочные условия существования групп (/-обособленных узлов на промежутках специального вида. Приведена система равенств, которая имеет место в том и только том случае, когда квадратурная формула, облада-ет (1 -свойством. Эта система рассматривается как система, уравнений относительно коэффициентов при узлах формулы. Доказаны леммы, устанавливающие достаточные, а также необходимые и достаточные условия разрешимости указанной системы уравнений. Б подразделе 2.2.2 введены вспомогательные определения. Установлены нижние оценки числа узлов квадратурных формул, обладающих (/-свойством. В подразделе 2.2.3 с помощью уже доказанных в диссертации утверждений устанавливаются необходимые и достаточные условия минимальности кубатурной формулы, обладающей (/-свойством. В конце подраздела сделано несколько замечаний о вычислении коэффициентов минимальной квадратурной формулы, точной для полиномов Хаара. В подразделе 2.2.4 приведены примеры минимальных квадратурных формул с различными весовыми функциями, обладающих (/-свойством.
Разделы 2.3 и 2.4 посвящены построению минимальных кубатурных формул, точных для полиномов Хаара в двумерном случае.
В разделе 2.3 рассмотрены минимальные кубатурные формулы, обладающие (/-свойством Хаара для (1 = 1,2,3. В подразделе 2.3.1 доказано необходимое условие точности кубатурной формулы для полиномов Ха.-ара степеней не выше г/. Получены оценки числа, узлов кубатурной формулы, обладающей (/-свойством Хаара. В подразделе 2.3.2 приведены примеры минимальных кубатурных формул, обладающих (/-свойством Хаара для (I = 1,2,3.
В разделе 2.4 рассмотрены минимальные кубатурные формулы, обладающие (/-свойством Хаара для (/ > 3. Коэффициенты при узлах рассматриваемых кубатурных формул считаются положительными. В подразделе 2.4.1 доказана лемма, устанавливающая достаточные условия существования не менее двух узлов кубатурной формулы на каждом из
12
замкнутых прямоугольников специального вида. Установлена справедливость лемм, формулирующих достаточные условия существования не менее £ 4- 1 узлов рассматриваемой формулы на указанных прямоугольниках, причем в некоторых случаях рассматриваются прямоугольники, не являющиеся замкнутыми множествами. В подразделе 2.4.2 выведены нижние оценки числа узлов кубатурных формул, обладающих (I-свойством при (I. ^ 4. В подразделе 2.4.3 приведены примеры минимальных кубатурных формул, обладающих (/-свойством Хаара для с1 = 5,6,7, и пример кубатурной формулы, точной для всех полиномов Хаара степеней, не превосходящих 4, число узлов которой на 1 больше нижней границы, фигурирующей в одной из полученных оценок. В подразделе 2.4.4 получены рекуррентные соотношения для нахождения координат узлов минимальной кубатурной формулы, обладающей (с/-(-2)-свойством Хаара, с помощью минимальной кубатурной формулы, обладающей е£-свойством (с1 ^ 6). В подразделе 2.4.5 на основе этих рекуррентных соотношений разработан алгоритм, позволяющий строить минимальные ку-батурные формулы, обладающие (/-свойством Хаара для любого наперед заданного четного (нечетного) числа (/, исходя из минимальных кубатурных формул, обладающих (/о-свойством Хаара для (/о = 6 (</0 = 7).
В разделе 2.5 рассмотрены методы двумерного дискретного преобразования Хаара. В подразделе 2.5.1 приведен классический метод дискретного преобразования Хаара. В подразделе 2.5.2 предложен вариант дискретного преобразования Хаара, основанный на По-сетках с 2е1 узлами, которые являются сетками кубатурных формул, обладающих (I-свойством Хаара; проведено сравнение этого варианта с классическим методом.
Глава 3 посвящена оценкам погрешности формул приближенного интегрирования, точных для полиномов Хаара.
В разделе 3.1 эти оценки рассмотрены в одномерном случае. В подразделе 3.1.1 на пространствах Бр найдена нижняя оценка нормы функцио-
13
нала погрешности квадратурных формул, точных на константах, и верхняя оценка нормы функционала погрешности квадратурных формул, обладающих d -свойством Хаара. В подразделе 3.1.2 на пространствах IIQ получена верхняя оценка нормы функционала погрешности квадратурных формул, обладающих (/-свойством Хаара. В подразделе 3.1.3 на пространствах Sp исследованы весовые квадратурные формулы: в случае весовой функции д G L\ (0,1 найдена нижняя оценка нормы функционала погрешности формул, точных на константах, в случаях д 6 />оо|0, lj и д € Ьд{0,1] (р 1 + д"1 = 1) — верхние оценки нормы функционала погрешности формул, обладающих (/-свойством Хаара; отдельно исследованы минимальные весовые квадратурные формулы, обладающие d-свойством Хаара, которые были рассмотрены в примере 2.3 — в случае весовой функции д € L^O, 1], почти всюду положительной на отрезке г(), 1], получена верхняя оценка нормы функционала погрешности таких формул.
В разделе 3.2 найдены оценки нормы функционала погрешности ку-батурных формул, обладающих (/-свойством Хаара в двумерном случае. В подразделе 3.2.1 на пространствах Sp получена нижняя оценка, нормы функционала погрешности кубатурных формул, точных на константах, и верхняя оценка нормы'функционала погрешности кубатурных формул, обладающих d. свойством Хаара. В подразделе 3.2.2 на пространствах На получена верхняя оценка нормы функционала погрешности кубатурных формул, обладающих (/-свойством Хаара.
Диссертационная работа выполнена при поддержке грантов РФФИ 03-01-00703-а "Кубатурные формулы с узлами на решетках" (2003-2005 гг.), 04-01 -00823-а "Кубатурные формулы, точные на системах функций” (2004-2006гг.), 07-01-00326-а "Кубатурные формулы, точные на системах функций, и их приложения” (2007-2009 гг.).
14
Основные обозначения
R диссертации используется двойная нумерация формул: сначала ставится номер текущей главы, затем — порядковый помер формулы в данной главе. Аналогично нумеруются определения, теоремы, леммы, утверждения, замечания.
Следующие обозначения используются в работе без пояснений:
Мп — п-декартова степень множества М\
\М\ — число элементов (конечного) множества М;
Е — множество действительных (вещественных) чисел;
R7' — n-мерное вещественное пространство;
N — множество натуральных чисел;
Кп — единичный n-мерный куб {(®i,..., хп) : 0 < Ti ^ 1,...,
О ^ хп ^ 1};
supp / — носитель функции /;
Ьр[0,1] — пространство функций, суммируемых со степенью р на отрезке
10,4;
|| • \\х — норма, элементов линейного нормированного пространства Х\ det. (А) — определитель матрицы А.
Остальные обозначения либо вводятся в диссертации, либо являются общеизвестными.
15
Глава 1
Функции Хаара и Пг-сетки
Последовательность функций {хь(я)}> называемых обычно функциями Хаара, была построена в диссертации известного венгерского математика А. Хаара в 1909 году [121]. Это была первая ортогональная система со следующим замечательным свойством: любая непрерывная на отрезке [0,1 функция разлагается в равномерно сходящийся ряд по функциям системы.
Функции Хаара широко используются в теории функций и функциональном анализе (например, (1] - |5], |9], |10|, [12] - [17], [25], [26], [55], [61], |106|, |109], [110], |119| - 1122], 1128]). В последние полвека функции (х/с(-'г)} находят применение и в прикладной математике — в теории кубатурных формул [104], (105], [115] - [117], при интерполировании функций [20], в теории вероятностей [114], [124], при изучении изотропной турбулентности [113], в теории равномерного распределения |104|, для построения алгоритмов дискретных преобразований [6], |8], 119], |22], [23], |54), |62], |99], [111], а также в вейвлет-анализе [7], (18), |21|, ]118), [125].
В настоящей главе приведены свойства функций {хд(х)Ь используемые при построении квадратурных и кубатурных формул и доказанные в [25], [100| - [104], [121|, [122].
16