Содержание к диссертации
Введение
Глава 1. Функции Хаара и Пт-сетки 12
1.1. Определение и свойства функций Хаара 12
1.2. Ряды Хаара 17
1.3. Кубатурные формулы с узлами, образующими Пг-сетку 20
Глава 2. Минимальные квадратурные формулы, точные для полиномов Хаара 23
2.1. Основные определения. Свойства к-функций и квадратурных формул, точных для полиномов Хаара 23
2.2. Вспомогательные определения и леммы 28
2.3. Нижние оценки числа узлов квадратурных формул, обладающих rf-свойством 42
2.4. Необходимые и достаточные условия минимальности квадратурных формул, точных для полиномов Хаара 44
2.5. Примеры 58
Глава 3. Минимальные кубатурные формулы, точные для полиномов Хаара в двумерном случае 61
3.1. Основные определения. Свойства дс-мономов 61
3.2. Вывод простейших оценок числа узлов кубатурных формул, точных для полиномов Хаара 64
3.3. Вспомогательные определения и леммы 68
3.4. Уточнение нижних оценок числа узлов кубатурных формул, обладающих d-свойством при d ^ 4 74
3.5. Примеры 79
3.6. Построение минимальных кубатурных формул, обладающих d-свойством при d^.1 85
Заключение 96
Библиографический список использованной литературы 97
- Ряды Хаара
- Вспомогательные определения и леммы
- Вывод простейших оценок числа узлов кубатурных формул, точных для полиномов Хаара
- Построение минимальных кубатурных формул, обладающих d-свойством при d^.1
Введение к работе
0.1. О содержании диссертации.
Построение и исследование формул приближенного интегрирования вида f N / g(xi,... ,xn)f(xu... ,xn)dxi ...dxn «^Cfc/(Pfc) (1) a k=l ведется со времен И. Ньютона. В данной формуле через Q обозначена область интегрирования из Rn, д(х\,... , п) — весовая функция, Р& — точки из О, называемые узлами формулы, С к — коэффициенты при узлах Рь (некоторые действительные числа), А; = 1,... ,7V. При п = 1 эти формулы носят называние квадратурных, а при п > 1 — кубатурных. Особый интерес в теории приближенного интегрирования вызывает задача построения таких формул вида (1), которые точно интегрируют некоторый заданный набор функций, используя наименьшее возможное число узлов. Эти формулы называются минимальными кубатурными (квадратурными) формулами, точными для функций из указанного набора. Минимизация числа узлов приводит к сокращению объема вычислений и, следовательно, к уменьшению машинной погрешности округлений. Следует отметить, что задача сокращения объема вычислений была и остается одной из самых актуальных в вычислительной математике.
При п = 1 для набора функций {/(ж)}, являющихся алгебраическими многочленами степеней не выше заданного числа 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] функция разлагается в равномерно сходящийся ряд по функциям системы. Благодаря указанному свойству функций {Xk(x)}> формулы вида (1), точные для всех полиномов Хаара степеней, не превосходящих достаточно большого числа d, имеют сравнительно малую погрешность [34]. Формулы приближенного вычисления интегралов, точные для полиномов по системе функций Хаара, можно найти в работах И. М. Соболя [34, 35] и К. Entacher [42, 43, 44]. В их трудах точность квадратурных и кубатурных формул на конечных суммах Хаара использовалась при выводе оценок погрешностей этих формул, однако вопрос минимизации числа узлов, которому уделено основное внимание в настоящей работе, не рассматривался.
Цель данной диссертации заключается в установлении нижних оценок числа узлов квадратурных и кубатурных (в двумерном случае) формул, точных для полиномов по системе Хаара, и построении указанных формул с числом узлов, близким к наименьшему возможному.
Все результаты диссертации являются новыми. Вопросы о наименьшем возможном числе узлов и построении минимальных формул, точных для полиномов Хаара, ранее не исследовались. В настоящей работе опи- саны все минимальные квадратурные формулы с произвольной суммируемой весовой функцией, точные для функций Хаара первых d групп, где d — некоторое фиксированное число. В двумерном случае выведены оценки числа узлов кубатурных формул, точных для полиномов Хаара степеней не выше d, построены минимальные кубатурные формулы, обладающие указанным свойством при d = 1,2,3,5,6, а также кубатурная формула, точная для полиномов Хаара степеней не выше 4, число узлов которой на 1 больше нижней границы, фигурирующей в одной из установленных оценок. Кроме того, получены рекуррентные соотношения, которые позволяют в двумерном случае для любого d ^ 7 строить минимальные кубатурные формулы, точные для полиномов Хаара степеней, не превосходящих d.
При проведении исследований использовались методы математического анализа, вычислительной математики, в частности, теории кубатурных формул.
Результаты диссертационной работы могут быть использованы при построении алгоритмов дискретного преобразования Фурье по системе функций {xk{%)} и для дальнейшего теоретического исследования кубатурных формул, точных на полиномах Хаара.
Указанные результаты докладывались на VI международном семинаре-совещании "Кубатурные формулы и их приложения" 2—7 июля 2001 г., на III международной конференции "Симметрия и дифференциальные уравнения" 25—29 августа 2002 г., на семинарах Красноярского государственного технического университета и опубликованы в центральной и местной печати.
Перейдем теперь к краткому описанию диссертации.
В первой главе приведены свойства функций {Xk{x)}, используемые в теории квадратурных и кубатурных формул, доказанные в [3, 34, 46, 47].
В 1.1 формулируется определение функций {хк(%)} и двоичных промежутков. Отмечено, что в литературе можно встретить различные определения функций {ха,-(ж)}, отличающиеся значениями этих функций в точках разрыва. Перечислены основные свойства функций Хаара.
В 1.2 приведены утверждения теорем о свойствах сумм рядов Хаара и Фурье-Хаара, о связи между указанными рядами. Сформулированы свойства системы Хаара, касающиеся сходимости рядов Хаара и Фурье-Хаара в пространстве Lp.
В 1.3 вводятся понятия двоичного параллелепипеда и Пт-сеток. Приведено утверждение о точности кубатурных формул вида (1) с узлами, образующими Пг-сетку, и равными коэффициентами при этих узлах, для конечных сумм Хаара.
В главе 2 описаны все минимальные квадратурные формулы с произвольной весовой функцией, точные для функций Хаара, выявлена зависимость числа узлов от свойств весовой функции, указаны правила выбора узлов и значений коэффициентов при узлах таких формул, приведены примеры минимальных квадратурных формул для некоторых весовых функций. Указанные результаты были анонсированы в [4] и доказаны в
В 2.1 введено понятие полиномов Хаара, квадратурных формул, обладающих ^-свойством, Ac-функций группы номер d. Сформулирована постановка решаемой задачи. Доказаны леммы о свойствах к-функций и квадратурных формул, точных для полиномов Хаара степеней, не превосходящих заданного d.
В 2.2 доказаны леммы о необходимом условии точности квадратурных формул для полиномов Хаара степеней не выше d и необходимом условии минимальности формул, обладающих d-свойством. Введено определение группы ^-обособленных узлов, доказаны леммы, в которых сформулированы достаточные условия существования групп ^-обособленных узлов на промежутках специального вида. Приведена система равенств, которая имеет место в том и только том случае, когда квадратурная формула обладает ^-свойством. Эта система рассматривается как система уравнений относительно коэффициентов при узлах формулы. Доказаны леммы, устанавливающие достаточные, а также необходимые .и достаточные условия разрешимости указанной системы уравнений.
В 2.3 введены вспомогательные определения. Установлены нижние оценки числа узлов квадратурных формул, обладающих ^-свойством.
В 2.4 с помощью утверждений, доказанных в предыдущих параграфах главы 2, устанавливаются необходимые и достаточные условия минимальности кубатурной формулы, обладающей d-свойством. В конце параграфа сделано несколько замечаний по поводу вычисления коэффициентов минимальной квадратурной формулы, точной для полиномов Хаара.
В 2.5 приведены примеры минимальных кубатурных формул с различными весовыми функциями, обладающих ^-свойством.
В главе 3 установлены нижние оценки числа узлов кубатурных формул, точных для полиномов Хаара в двумерном случае, приведены приме- ры минимальных формул, обладающих d-свойством для 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 строить минимальные кубатурные формулы, обладающие ^-свойством.
Диссертационная работа выполнена при поддержке гранта РФФИ 99-01-00765.
0.2. Основные обозначения.
В диссертации используются следующие обозначения: IR — множество действительных (вещественных) чисел; Ш.п — n-мерное вещественное пространство; Р — точка n-мерного вещественного пространства; dP = dx\,..., dxn, где (rci,..., хп) — координаты точки Р; Кп — единичный n-мерный куб {(жі,... , хп) : 0 ^ х\ ^ 1,... , 0 ^ хп ^ 1}; supp/ — носитель функции /; Lp — пространство функций, суммируемых со степенью р на отрезке [ОД]; || \\l — норма в пространстве Lp.
Ряды Хаара
Пусть f(x) — произвольная интегрируемая функция, определенная на отрезке [0,1]. Коэффициентами Фурье-Хаара этой функции называются числа Для любой интегрируемой функции f{x) можно вычислить коэффициенты Фурье-Хаара (} и составить ряд Фурье-Хаара Основные утверждения следующих двух теорем принадлежат А. Хаару [46, 47]. ТЕОРЕМА 1. Пусть функции {хк{х)} определены согласно (3). Предположим, что функция f(x) непрерывна на отрезке [0,1]. Тогда ряд (6) сходится к /(ж) равномерно на [0,1]. Утверждение теоремы остается в силе, если функция /(ж) имеет лишь конечное число двоично рациональных точек разрыва r\ r i ... гр, в каждой из которых существуют /(г + О) = f{ri) и f{ri 0) ф fin). В [41] показано, что в случае определения функций Хаара согласно равенствам (5) первое утверждение теоремы 1 не имеет места. ТЕОРЕМА 2. Предположим, что функции {xk(x)} определены согласно (3) и /(ж) интегрируема на отрезке [0,1]. Тогда: 1) ряд (6) сходится к /(ж) почти во всех точках отрезка [0,1], 2) если в точке х = XQ функция /(ж) непрерывна, то в этой точке ряд (6) сходится к /(жо), 3) если в двоично рациональной точке х = г функция f(x) непрерывна справа, то в этой точке ряд (6) сходится к f(r), 4) если /(ж) равномерно непрерывна при г\ ж гч, где гі,гг — двоично рациональные точки, то ряд (6) сходится равномерно при Т\ ж г2. В случае определения функций Хаара согласно равенствам (1) 1-е утверждение теоремы 1 и утверждения 1), 2) теоремы 2 остаются в силе. В теории тригонометрических рядов известен так называемый "принцип локализации" Римана: если разложить функцию /(ж) в тригонометрический ряд Фурье, то сходимость этого ряда в точке жо зависит только от поведения /(ж) в окрестности точки ж = жо- Как показал А. Хаар [46, 47], аналогичным свойством обладают также ряды Фурье-Хаара: если изменить значения функции /(ж) на каком-либо отрезке [жі,жг], то это не отразится на сходимости ряда (6) в точке XQ, не принадлежащей [xi,x2]. Рядом Хаара называется ряд с произвольными действительными коэффициентами а,}.. В [34] доказана следующая теорема. ТЕОРЕМА 3. Пусть функции {хк(х)} определены согласно (1). Если ряд (7) сходится равномерно на отрезке [0,1], то его сумма f(x) непрерывна во всех точках этого отрезка, кроме, быть может, двоично рациональных точек. В случае определения (3) это утверждение остается в силе, причем в двоично рациональных точках сумма ряда (7) непрерывна справа и может иметь разрывы первого рода. Отметим, что не каждый ряд Хаара есть в то же время ряд Фурье-Хаара.
Важнейшее условие этого дается следующей теоремой [34]. ТЕОРЕМА 4. Пусть функции {Хк(х)} определены согласно (1) или (3). Если ряд Хаара (7) сходится равномерно на отрезке [0,1]; то он есть ряд Фуръе-Хаара для своей суммы. Приведем некоторые свойства системы Хаара, доказанные в [3, 46, 47]. Функции {Xk(%)} определены согласно (1) или (5). 1. Система Хаара полна в Ьр при любом р Є [1, оо]. Это значит, что в Ьр нет такой функции, которая была бы ортогональна ко всем Xk{x) и не равнялась бы почти во всех точках нулю. 2. Система Хаара образует базис в Lp при любом р Є [1, со]. Это значит, что для каждой функции /(ж) из Lp ряд Фурье-Хаара сходится к ней по норме: 3. Для каждой функции f(x) из Li справедливо равенство Парсеваля: 4. Система Хаара является системой сходимости. Это значит, что если числа {aj.} удовлетворяют условию ]Г) а\ со, то 6. Для того чтобы ряд (7) был рядом Фурье-Хаара функции f(x) из Lp (1 р со), необходимо и достаточно, чтобы его частичные суммы были равномерно ограничены по норме: В этом параграфе изложены результаты, доказанные в [34], поэтому двоичные промежутки и функции Хаара определяются так же, как в указанной монографии. Здесь рассматриваются функции от п переменных жі,... , жп, определенные на единичном n-мерном кубе Кп. Рассмотрим кубатурную формулу / /(P)dP«i/(P,), (8) Кп / =0 где узлы PQ,PI, ... ,PJV_I — произвольные (фиксированные) точки куба Кп. Координаты узла P;i обозначим (яМ1,.. , х п), а всю сетку — буквой S, так что Е = {Ро,... , PN-i} Двоичным параллелепипедом Щ назовем декартово произведение двоичных промежутков h1} ,hn, где мультииндекс k = (&i,... , kn), т. е. Пк = lkl х ... х lkn. В [34] введено понятие По-сеток: сетка Е; состоящая из N = 2й точек куба Кп, называется Щ-сеткой, если каждому двоичному параллелепипеду Як с объемом 77k = 1/N принадлежит одна точка сетки. В [34] доказано, что Щ-сетки существуют только в К1, К2 и К3. Для рассмотрения аналогичных сеток в Кп при любых п в [34] вводится следующее определение, в котором ослаблены требования к распределению точек сетки по всевозможным Пк: сетка, состоящая из N = 2V точек куба Кп, называется ПТ-сеткой, если каждому двоичному параллелепипеду Як с объемом Як = 2T V принадлежат 2Т точек сетки. При этом всегда предполагается, что г v. Заметим, что в этом определении достаточно потребовать, чтобы число точек в каждом Пк с объемом Пк = 2r v было не меньше (не больше), чем 2Т. Дело в том, что к каждому такому Пк можно подобрать еще 2T V — 1 равновеликих Пк, которые в сумме составят весь куб Кп. И число точек в Пк по необходимости окажется равным 2Т. Легко видеть, что каждая Пт-сетка является в то же время Пг+і-сеткой (если только v т +1), так как каждый Пк с объемом 2т+1 и есть сумма двух Пк с объемами 2т и и, следовательно, содержит 2 2r = 2r+1 точек сетки. В [34] доказано следующее утверждение. ТЕОРЕМА 5. Пусть г v. Формула (8) с узлами, образующими Пт-сетпку, точна для конечных сумм Хаара вида
Вспомогательные определения и леммы
Определение 4. Де оичный отрезок [d + 1)-го ранга ld+i,r назовем d-тривиалъным, если щ г = 0, 1 г 2 . Зафиксируем некоторую весовую функцию д{х) и некоторое натуральное число d. ЛЕММА 4. Если формула вида (1) обладает d-свойством, то выполняется условие (А): "каждый из двоичных отрезков (d + 1) — го ранга ld+i,j — v ti ji], we являющихся d-тривиалъными, содержит хотя бы один узел формулы вида (I)". Доказательство. Предположим, что существует хотя бы один дво ичный отрезок (d + 1)-го ранга ld+i,n не содержащий ни одного узла формулы вида (1), для которого г] г ф 0, где г — некоторое натуральное число из отрезка [l,2d]. Согласно следствию 1 леммы 2, формула вида (1) точна для полинома Хаара к )Г(ж), который, в силу леммы 3, представим в следующем виде: 2d при х Є ld+i,r, ЧГ(Ї) = { 2d l при X Є /d+l,r \ ld+l,r, О при х Є [0,1] \ /d+i,r Следовательно, /[АС )Г] = 2drjd,r Ф 0. Так как на множестве ld+i,r нет ни одного узла формулы, то Q[/c ,r] = 0. Из противоречия с условием точности формулы следует справедливость утверждения леммы. ЛЕММА 5. Минимальная формула вида (1), обладающая d-свойством, удовлетворяет условию (Б): "каждый из двоичных промежутков ld+i,i, ... ,/d+i2d содержит не более одного узла формулы". ДОКАЗАТЕЛЬСТВО. Из следствия 1 леммы 2 вытекает, что формула вида (1) точна для всех полиномов Хаара степеней, не превосходящих d, тогда и только тогда, когда имеет место система равенств Q[ d,i] = i[K d,i] Q[Kd,z\ = Лыз] Q[Kdfi -l] - I[Kd,2d-l] Q[Kd,2d] = I[ d,2d\ Рассмотрим минимальную формулу вида (1), обладающую -свойством. Предположим, что некоторый двоичный промежуток ld+i,r содержит хотя бы два узла данной формулы — жг-г,жг-г+і, 1 г . 2d. Этим узлам будет соответствовать следующая сумма из левой части г-го равенства системы (6): CirKd,r(xir) + Cir+iK(i,r(xir+i) — 2 (Cir + Cir+i) = (СІГ + Cir+i)Kdjr(xir), где dr и C{r+i — коэффициенты формулы при узлах ХІТ И г г+і соответственно. Следовательно, если удалить узел ;r+i и положить коэффициент при узле Х[г равным С;г+Сг-г+і, а коэффициенты при остальных узлах оставить без изменения, то получится формула вида (1), обладающая d-свойством, число узлов которой на единицу меньше, чем у рассмотренной формулы.
Из противоречия с условием минимальности исходной формулы вытекает справедливость утверждения леммы. Из лемм 4 и 5 следует, что искать минимальную формулу вида (1), обладающую d-свойством, имеет смысл среди формул, удовлетворяющих условиям (А) и (Б). Исходя из этого, введем следующие обозначения. ПуСТЬ t\, 2, -, -1 ТОЧКИ, Лежащие Между Промежутками ld+l,ljd+l,2, iWi i занумерованные слева направо по порядку, т.е. tj 1 2d — 1 Положим 2d J О, если на промежутке ld+i,j нет узла, 2/i Сір ЄСЛИ Существует УЗЄЛ Х{. Є /d+l,j, j = l,...,2d. Подобным образом определим у - : 0, если в точке tj нет узла, Уі = С;., ЄСЛИ Существует УЗЄЛ Х{. = tj, J — 1, ..., Z, В силу леммы 3, система (6) равносильна системе 2/1 + \У \ = Vd,i \у[ + У2 + \у!2 = Vd,2 \У2 + Уз + Уз = Vd,z (7) Уіі-г + 2/2rf—1 + 2 2d-l - %,2d-l 2 -1 +2/2«« = %,2 Положим i=p (8) где p — натуральное, к — целое неотрицательное число, причем р+ к 2d. В этом случае двоичные отрезки (с?+1)-го ранга ld+i,P, , ld+i,p+k будем называть отрезками, образующими множество Sp ОПРЕДЕЛЕНИЕ 5. Будем говорить, что узлы, расположенные в точках ip, tp+i,..., p+fc_i, k 1, образуют группу d-обособленных узлов ранга к, если на множестве Sp \ {tp,tp+i, ...,tp+k-i} нет ни одного узла формулы. Простейшей группой -обособленных узлов является группа, состоящая из одного узла — группа 1-го ранга. Например, если d = 4 и узлы формулы вида (1) расположены в точках 1/32,3/32,5/32,1/4,5/16,3/8,7/16,1/2,19/32,21/32,23/32,13/16,29/32, 31/32, то точки 1/4,5/16,3/8,7/16,1/2 образуют группу обособленных узлов ранга 5, а точка 13/16 представляет собой группу обособленных узлов 1-го ранга. Имеет место ЛЕММА 6. Пусть натуральные числа р и К удовлетворяют неравенству: р + К 2d. Если на множестве SP,K имеется менее К + 1 узлов формулы вида (1) и каждый из двоичных отрезков (d+l)-zo ранга, образующих SP)K, содержит хотя бы один узел этой формулы, то на этом множестве существует не менее одной группы d-обособленных узлов. ДОКАЗАТЕЛЬСТВО. Докажем лемму индукцией по К. При К = 1 получаем, что на множестве SP)\ = ld+i,p U ld+i,p+i лежит ровно
Вывод простейших оценок числа узлов кубатурных формул, точных для полиномов Хаара
Пусть d 2. Установим справедливость следующей теоремы. ТЕОРЕМА 1. Если координаты узлов формулы (1), обладающей d-свойством, не являются точками разрыва ни одной из функций Хаара (d — 1)-ой группы, то число узлов такой формулы удовлетворяет неравенству: N 2d. ДОКАЗАТЕЛЬСТВО. Воспользуемся техникой доказательств, примененной И. П. Мысовских [17, 19], М. Beckers, R. Cools [39], а также М. В. Носковым и Н. Н. Осиповым [27]. Положим fi{x,y) = 1, f2{x,y) = Xi,i(z), h(x,y) = Хі,і(у), ЇА(Х,У) = = Хі,і(з)хі,і(2/), /5(s,2/) = X2,i(s), /б(я,у) = Х2,2(ж), /7(я,2/) = = Х2,і(а:)хі,і(у), /в (ж, у) = X2,2(»Xi,iW, -, /2 -41( 2/) = = Xd-i.iM, /2 -42( 2/) = Xd-i,2(«), ..., 1ъ-г Ах- У) = = Xd-i,2 - (x), /3.2 -41( 2/) = Xd-i,iWxi,i(2/), /3-2 -42( ,2/) = = Xd-i,2( )xi,i(2/), , /2 К2/) = Xd-i,2« -2(a;)xi,i(2/)-Рассмотрим Так как среди i, 2/ь #2,2/2, , /v, 2/w нет точек разрыва функций Xd-i,b Xd-1,2, , Xd-1,2 -2, а, значит, и точек разрыва функций Хаара первых d — 2 групп, то, согласно лемме 3, fifi можно рассматривать как полином Хаара, степень которого не превосходит d. Тогда в силу того, что формула (1) обладает « -свойством, Легко видеть, что при I ф I а при / = / Таким образом, N Y1 СІМХ1ІУЗ)ІЇ(Х1І Уз) = V 3=1 где 5ij — символ Кронекера. Введем в рассмотрение матрицы / Іі{хиУі) /l(z2,2/2) h{XN,VN) \ І2(хиуі) /2( 2,2/2) f2{xN,yN) F — (4) \ М ъш) /2 2,2/2) Ї2 іхм,Ук) J ( Сі \ c = \ 0 Сдгу Тогда равенство (4) равносильно соотношению FCFT = Е, где Е — единичная матрица порядка 2d.
Так как ранг произведения матриц не превосходит ранга каждого из сомножителей, то N rank(F) rank{FCFT) = rank(E) = 2d. Теорема доказана. ЛЕММА 4. Если формула (1) обладает d-свойством, то носитель каждого к- монома степени d содержит хотя бы один узел этой формулы. доказательство. Предположим, что носитель некоторого к-монома К{х,у) степени d не содержит ни одного узла формулы (1). Тогда, в силу следствия леммы 3 главы 2, Q[K] = О, а по лемме 2 I[K] = 1. Полученное противоречие с условием точности формулы для К(х,у) доказывает лемму. ТЕОРЕМА 2. Если одна из координат хотя бы одного узла формулы (1), обладающей d- свойством, является точкой разрыва некоторой функции Хаара (d — 1)-ой группы, то число узлов такой формулы N 2d l + l. (5) доказательство. Положим для определенности, что абсцисса некоторого узла (a?o,2/o) Ф0РмУлы (1) является точкой разрыва одной из функций Хаара (d — 1)-ой группы, т. е. жо = гт, гДе 1 jo 1 — 2 т Носители АС-МОНОМОВ «Чі(Ж) Ыз(ж) Kd,2j0-l{x), Kd,2j0+2(x), Kd,2j0+4{x), ..., Kdf2d(x) являются подмножествами прямоугольников [О, -р т) х IP» 1] Іг331 W 1) х 1" J llF-1" F-w x L J vF-1" 2d-1-l x і Ь ($рг=т, fr=r] x [0,1],... , (1 — 2ЗГТ, 1] x [0,1] соответственно. Тогда из леммы 4 следует, что каждый из этих прямоугольников содержит хотя бы один узел формулы (1). Так как они попарно не пересекаются и общее их количество равно 2d l, то, учитывая узел (жо 2/о) получаем неравенство (5). Теорема доказана. следствие ТЕОРЕМ 1, 2. Для числа узлов формулы (1), обладающей d-свойством, справедлива оценка (5). Будем считать, что коэффициенты Ci,C2,... ,CN формулы (1) положительны. Пусть d — некоторое целое число, большее 3. Введем в рассмотрение множества: d 2м-1 2d M+1-l „ _ , Ad= U U U {( 2м ,2d M+1 М=1 т=1 Л=1 d 2м-1 М = 1 771=1 d 2Л/_1 Af=l m=l ЛЕММА 5. і. ifo/m на множестве Bd\Ad существует хотя бы один узел ( ) $орл улы ( Mi = l,...,d,mi = 1,...,2 , 0 у 1, то каждый из прямоугольников D\ = f2 "1 — г, 2щ1] х [О,1], 2 — [ щ , щ—h jz] х [0,1] содержит не менее одного узла этой формулы, отличного от {2м ,у ) 2. Если на множестве Cd\Ad найдется хотя бы один узел (ж , м ) формулы (1), Mi — 1,...,с?, Ш2 = 1,...,2М2_1, 0 ж 1, то в каждом из прямоугольников [0,1] х [Щ$± - , ], [0,1] х [ ±, Щ + } имеется не менее одного узла, отличного от [х , щ ). ДОКАЗАТЕЛЬСТВО. Докажем первую часть утверждения леммы. Пусть узел С щ1 ,у ) формулы (1) — произвольная точка множества Bd \ Ad. Тогда у Є /d-Mi+2,fc j гДе 1 & 2d_Ml+1. Следовательно, (ЩЇГ,У ) Є /мьтп! х ld M1+2,kl, поэтому, в силу следствия леммы 3 главы 2, KM1-i,m1(2 nr)i d-M1+i,k {y ) = 2d- Поскольку коэффициенты формулы (1) положительны, коэффициент при данном узле не больше 2 d. Заметим, что прямоугольники D\,D i являются носителями к-мономов ,2 - (277 -1)( ) и «d,2 -A i(2m1-i)+i(a;) соответственно, а узел ( ) формулы (1) находится на границе этих прямоугольников. Тогда по лемме 3 главы 2 ,2 1 -1)(1) = 42 1(27 -1)+1(1) = 2й"1. Так как коэффициент при узле (2м 1 ,у ) формулы (1) не превосходит 2 d, то, в соответствии с леммой 2 и следствием леммы 2 главы 2 и леммы 1 главы 3, каждый из прямоугольников D\ и D содержит хотя бы один узел формулы (1), отличный от рассматриваемого. Вторая часть утверждения леммы доказывается аналогично. Рассмотрим прямые х = ± і = 1,...,2 -1, (6) у = А j = l,...,2d-l. (7) Обозначим через Q\ и ( некоторые подмножества множеств всех прямых вида (6) и (7) соответственно. определение 5. Будем говорить, что прямые х = ,х = ,..., х = %2d множества Q\ образуют обособленную группу линий этого множества, если Q\ не содержит прямых х = -, х = , 1 і i + k 2d. Множество прямых {у — jj,y = -, ...,?/ = - d } С Q2 назовем обособленной группой линий множества Q2, если ( н содержит прямых 2/ = ,3/ = , l j j + m 2d.
Введем следующие обозначения: Ri — множество прямых вида (6), на которых расположены узлы формулы (1), принадлежащие множеству Ad, т\ — число прямых из множества R\, д\ — число обособленных групп линий из множества R\, R2 — множество прямых вида (7), на которых расположены узлы формулы (1), принадлежащие множеству Ad, r i — число прямых из множества Ri, д2 ЧИСЛО Обособленных групп линий ИЗ Множества #2) Р\ — множество прямых вида (6), отстоящих от линий множества R\ на расстоянии, большем 2 d, и содержащих узлы формулы (1), среди которых нет элементов множества Ad, р\ — число прямых из множества Р\, h\ — число обособленных групп линий из множества Р\, Рг — множество прямых вида (7), отстоящих от линий множества #2 на расстоянии, большем 2 d, и содержащих узлы формулы (1), среди которых нет элементов множества Ad, р2 — число прямых из множества Р2, /&2 — число обособленных групп линий из множества Р2. ЛЕММА 6. 1. Если прямые х = jj,x = ,...,х = Щт - принадлежат множеству Pi, l .i i + t .2d, то прямоугольник \jijr, зг] х х[0,1] содержит не менее t + І узлов формулы (1). 2. Если прямые у = jj,y = ї±г,..., у = J+ 1 принадлежат множеству Р2, 1 j j + t 2d, то прямоугольник [0,1] х [ г, г] содержит не менее t + І узлов формулы (1). ДОКАЗАТЕЛЬСТВО. Докажем первую часть утверждения леммы. Рас
Построение минимальных кубатурных формул, обладающих d-свойством при d^.1
Докажем теорему, которая позволяет на основании формул, приведенных в примерах 5,6, получить для любого наперед заданного числа d 7 минимальную кубатурную формулу, обладающую d-свойством. ТЕОРЕМА 5. Для любого d 5 существует кубатурная формула (1), удовлетворяющая следующим условиям: 1) число узлов этой формулы N = 2d — X(d), 2) числа xi, 2/1, х2, 2/2)---) x\{d)i Ущ) кратны 2 d и отличны от Out, a xX(d)+i, y\(d)+i, xx{d)+2, 2/A(d)+2,---, x2d_X{d), y2d-\{d) кратны 2 d l, но не кратны 2 d, коэффициенты формулы C\ = C2 = — ... — L x(d) — , \(d)+l — A(d)+2 — — 2d-\(d) z 3) носитель каждого к-монома степени d содержит ровно один узел формулы, 4) для любого к-монома Kd степени d, такого, что (жг-,?/г-) Є supp Kd { 2d npui = l,...,\(d), 2d l при і = X(d) + 1,..., 2d - \(d), где supp Kd — носитель функции Kd, 5) 2d-A(d) = У2 -Щ)-1 = 1 - 2 . Такая формула является минимальной кубатурной формулой, обладающей d- свойством, а кубатурная формула 1 1 2d-X{d) fff(x,y)dxdy Е (сиК У + /К Ы)+ О 0 i=l (27) + 2Е (cy(x 2ti,tf2j + су «г,2/У) г=1 с узлами (х і,пУ і,і) = (0.5ж ,0.5уг), і = І,-,A(d), (4,,-,3/ ) = (0.5s,- + 2- ,0.5 - + 2" 3), г = A(d) + 1, X(d) + 2,..., 2d - A(d) - (30) і = X(d) + l,X(d) + 2, ...,2d - X{d) K,«-i, З4и-і) = (0-5 ,- - 3 2-d-3,1 - 0.5Уі - 3 2"rf-3), (4,2,-12/4,2.-) = (0.5ХІ + 3 2- 3,1 - 0.57/i + 3 2 3), і = 1,..., AM, (31) «АЮ+,-,»WH) = (-5яї - 2"""3 ! - -5 - 2" "3) г = X(d) + 1, A(d) + 2,..., 2d - A(d) - 1, U Коэффициентами C[ 2d-\(d)-l 1 2d-A(d) == 1,г 3,г = 2 , i = l,...,A(d), Cifi = 2-d 2, i = A(d) + l, A(d)+ 2, ..., 2d-X(d), C 2i = C\{ — 2 d 2, і = 1,..., 2d — 1, является минимальной формулой, обладающей [d + 2)-свойством. ДОКАЗАТЕЛЬСТВО. Легко видеть, что формула (1), удовлетворяющая условиям 1)—5), точна для всех «-мономов степени d. Согласно следствию леммы 2 главы 2 и леммы 1 главы 3, она обладает -свойством. Тогда по теореме 4 эта формула является минимальной кубатурной формулой, обладающей d-свойством.
Нетрудно проверить, что кубатурные формулы, приведенные в примерах 5,6, удовлетворяют условиям 1)—5). Для доказательства того, что кубатурная формула (27) является минимальной формулой, обладающей (с/ + 2)-свойством, достаточно показать, что она удовлетворяет следующим условиям: 1 ) для числа узлов формулы имеет место равенство: N — 2d+2 — -A(d + 2), 2 ) абсциссы и ординаты \(d+2) узлов формулы кратны 2 d 2 и отличны от 0 и 1, коэффициенты формулы при указанных узлах равны 2 d 1, обе координаты каждого из остальных 2d+2 — 2\{d+2) узлов кратны 2 d_3, но не кратны 2 d 2, коэффициенты при этих узлах равны 2 d 2, 3 ) носитель каждого дс-монома степени d+2 содержит ровно один узел формулы, 4 ) все к-мономы степени d + 2, носители которых содержат произвольный узел формулы, принимают в этом узле значения, равные 2 +2, если абсцисса и ордината узла кратны 2d 2, и 2d+1, если обе координаты кратны 2 d 3, но не кратны 2_fi_2, 5 ) найдутся 2 узла формулы, такие, что абсцисса одного из них и ордината другого равны 1 — 2_d_3. Тем самым будет доказано и существование формул, удовлетворяю щих условиям 1)—5) для d l. Для числа узлов формулы (27) справедливо равенство: N = 2d+2 — —2X(d) — 2. Нетрудно проверить, что X(d + 2) = 2A(d) + 2. (32) ТогдьІЇ = 2d+2-X(d + 2). Из соотношений (28), (30) следует, что абсциссы и ординаты узлов (ж1,1 2/і,і) (ж1,2 2/1,2) — (ж1,А(гі) 1,А(гі)) \Xl,2d-\{d)-Vyi,2d-\{d)-V ( l -AfdJ l -ACd)) (Ж3,И 2/3,l)i ( 3,212/3,2)1 (жЗ,А(гі) 3,А(гі)) кРатньІ 2 и отличны от 0 и 1.
Согласно условию теоремы, коэффициенты формулы (27) при указанных узлах равны 2 d l. В силу равенства (32) общее число таких узлов — \{d + 2). Кроме того, из соотношений (28) — (31) следует, что обе координаты каждого из остальных 2d+2 — 2X(d + 2) узлов формулы (27) кратны 2 d z, но не кратны 2 d 2. По условию теоремы коэффициенты формулы при этих узлах равны 2 d 2. Таким образом, доказано, что кубатурная формула (27) удовлетворяет условиям Ґ), 2 ). Рассмотрим множество носителей всех АС-МОНОМОВ степени d Ed = {[1 , JL]x[Z_zI 2_] : т+п = d,m,n 0,i = 1,..., 2mJ = 1,..., 2n}. 2m 2 2n 2 -— J J Определим множества +2 (& = 1, ---,6) следующим образом: /?(!) _ ГГІ . Ы I._Ll у [I. izi І.-2-І 777 -І-Г? — г/ 77? 77 0 І = 1 2m d+2 — L L 2 2m 2 2m J L2 2n 2 2" J — "- u, t — x, ..., , , І = 1,...,2П}, t = l,...,2m,i = 1,..., 2»}, +2 = il1 - 2 - 2 1 X Iі 2 - 2 : Ш + П = d m П 0 г = 1,..., 2-, j = 1,.., 2-},