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

На правах рукописи

005001173

Кириллов Кирилл Анатольевич

МИНИМАЛЬНЫЕ КУБАТУРНЫЕ ФОРМУЛЫ, ТОЧНЫЕ ДЛЯ ПОЛИНОМОВ ХААРА

01.01.07 — вычислительная математика

АВТОРЕФЕРАТ

диссертации на соискание ученой степени доктора физико-математических наук

1 7 НОЯ 2011

Красноярск — 2011

005001173

Работа выполнена на кафедре «Прикладная математика и компьютерная безопасность» Сибирского федерального университета (г. Красноярск).

Научный консультант — доктор физико-математических наук,

профессор Носков Михаил Валерианович.

Официальные оппоненты:

доктор физико-математических паук, профессор Войтишек Антон Вацлавович;

Ведущая организация: Научно-исследовательский вычислительный центр Московского государственного университета им. М. В. Ломоносова (г. Москва).

Защита состоится 14 декабря 2011 г. в 14 часов на заседании диссертационного совета ДМ 212.099.18 при Сибирском федеральном университете по адресу: 660074, г. Красноярск, ул. академика Киренского, 266. корпус «Ж» Сибирского федерального университета, ауд. УЛК-115.

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

Автореферат разослан ноября 2011 г.

доктор физико-математических наук, профессор Раыазанов Марат Давидович;

доктор физико-математических наук, профессор Рябов Виктор Михайлович.

Осипов Н. Н.

Общая характеристика работы

Актуальность темы. Построение и исследование формул приближенного интегрирования вида

[ я

/ д(х\,..., хп)/(х1,..., хп)йх\... йхп «^СгДа;^,...,^') (1) я ш

ведется со времен И. Ньютона. В данной формуле через П обозначена область интегрирования из К", д{х 1,...,хп) — весовая функция, ■ ■ ■ ,3;«') — точки из П, называемые узлами формулы, С,; — коэффициенты при узлах ..., Яп5) (некоторые действительные числа), % = 1,..., N. При п = 1 эти формулы носят называние квадратурных, а при п > 1 — кубатурных. Особый интерес в теории приближенного интегрирования вызывает задача построения таких формул вида (1), которые точно интегрируют некоторый заданный набор функций, используя наименьшее возможное число узлов. Эти формулы называются минимальными кубатурными (квадратурными) формулами, точными для функций из указанного набора. Минимизация числа узлов приводит к сокращению объема вычислений и, следовательно, к уменьшению машинной погрешности округлений. Следует отметить, что задача сокращения объема вычислений была и остается одной из самых актуальных в вычислительной математике.

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

Так, например, в случае двумерной симметричной области интегрирования И. Радоном была получена кубатурная формула с 7 узлами, точная на всех многочленах степени не выше 5, и доказана минимальность этой формулы. В монографии В. И. Крылова «Приближенное вычисление интегралов» (М.: "Наука" , 1967) приведено другое доказательство ее минимальности, автором которого является И.П. Мысовских.

Существенный интерес представляют квадратурные формулы, точно интегрирующие алгебраические многочлены на сфере. Такие формулы исследовались В. И. Лебедевым, Г. Н. Салиховым, С. И. Коняевым и другими авторами.

Минимальные квадратурные формулы, точные для тригонометрических полиномов степени не выше фиксированного d, изучены Н. П. Кеда, И. П. Мысовских, и другими авторами. Полученные ими результаты изложены в упомянутой выше книге В. И. Крылова. Минимальные кубатурные формулы, точно интегрирующие тригонометрические многочлены, исследовались в основном в работах М. В. Носкова, И. П. Мысовских, М. Beckers, R. Cools и H. H. Осипова. Следует отметить, что внимание многих авторов привлекают исследования кубатурных формул с решетчатой структурой узлов. Построение серий решетчатых кубатурных формул, точных на тригонометрических многочленах, было начато в работах М. В. Носкова и продолжено А.Р. Семеновой, H.H. Осиповым, A.B. Петровым. В частности, H. Н. Осиповым были описаны все минимальные решетчатые формулы для приближенного вычисления двойного интеграла, точные на тригонометрических многочленах степени не выше заданного числа d.

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

стема является ортогональной и обладает следующим замечательным свойством: любая непрерывная на отрезке [0,1] функция разлагается в равномерно сходящийся ряд по функциям системы. Благодаря указанному свойству функций (XfcC^)}, формулы вида (1), точные для полиномов Хаара степеней, не превосходящих достаточно большого числа d, имеют сравнительно малую погрешность. Формулы приближенного вычисления интегралов, точные для полиномов по системе функций Хаара, можно найти в работах И. М. Соболя и К. Entacher. В их трудах точность квадратурных и кубатурных формул на конечных суммах Хаара использовалась при выводе оценок погрешности этих формул, однако вопрос минимизации числа узлов, которому уделено основное внимание в настоящей работе, не рассматривался.

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

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

Научная новизна. Все результаты диссертации являются новыми. Вопросы о наименьшем возможном числе узлов и построении минимальных формул, точных для полиномов Хаара, ранее не исследовались. В настоящей работе описаны все минимальные квадратурные формулы с произвольной суммируемой весовой функцией, точные для функций Хаара первых ¿ групп, где (1 — некоторое фиксированное число. В двумерном случае получены нижние оценки числа узлов кубатурных формул, точных для полиномов Хаара степеней не выше ¿, построены минимальные кубатур-пые формулы, обладающие указанным свойством при ¿ = 1,2,3,5,6,7, а также кубатурная формула, точная для полиномов Хаара степеней не выше 4, число узлов которой на 1 больше нижней границы, фигурирующей в одной из установленных оценок. Разработан алгоритм, позволяющий на основе минимальных кубатурных формул, обладающих ¿о-свойством Хаара для ¿о = 6 (¿о = 7), строить минимальные кубатурные формулы, обладающие ¿-свойством Хаара для любого наперед заданного четного (нечетного) числа ¿. Найдены оценки погрешности на пространствах 5Р квадратурных формул с весовой функцией д € ¿оо[0,1] и д £ 1] (р-1 + q~1 = 1), обладающих ¿-свойством Хаара, а также оценки погрешности на пространствах и На квадратурных и кубатурных формул с весовой функцией д(х) = 1, обладающих ¿-свойством Хаара соответственно в одномерном и двумерном случае.

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

Апробация работы. Результаты диссертации докладывались на VI международном семинаре-совещании "Кубатурные формулы и их приложения" (Уфа, 3-7 июля 2001 г.), III международной конференции "Теория симметрии и дифференциальные уравнения"(Красноярск, 25 - 29 августа 2002 г.). Уфимской международной математической конференции "Теория функций, дифференциальные уравнения, вычислительная математика" , посвященной памяти А. Ф. Леонтьева (Уфа, 28 мая - 1 июня 2007 г.), международной конференции "Дифференциальные уравнения. Функциональные пространства. Теория приближений", посвященной 100-летию со дня рождения С. Л. Соболева (Новосибирск, 5-12 октября 2008 г.), международной конференции "Кубатурные формулы, методы Монте-Карло и их приложения" (Красноярск, 4-7 июля 2011 г.), на семинарах Сибирского

федерального университета и Института вычислительного моделирования СО РАН.

Публикации. По теме диссертации опубликованы 19 работ, в том числе 9 статей — в изданиях из перечня ВАК РФ.

Личное участие автора в получении представленных научных результатов. Все результаты, выносимые на защиту, получены лично автором диссертации. В совместных работах вклад соавторов равнозначен.

Структура и объем работы. Диссертация состоит из введения, трех глав, заключения и списка литературы, содержащего 128 наименований, включая работы автора. Объем диссертации — 188 страниц.

Положения, выносимые на защиту

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

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

3. Алгоритм построения для любого наперед заданного целого d, ^ 8 минимальных кубатурных формул, обладающих d-свойством Хаара в двумерном случае.

4. Оценки погрешности на пространствах Sp (р > 1) и На (0 < а ^ 1) формул приближенного интегрирования, обладающих d-свойством Хаара.

Диссертационная работа выполнена при поддержке грантов РФФИ 03—01—00703-а "Кубатурные формулы с узлами на решетках" (2003-2005гг.), 04-01-00823-а "Кубатурные формулы, точные на системах функций" (2004-2006гг.), 07-01-00326-а "Кубатурные формулы, точные на системах функций, и их приложения" (2007-2009гг.).

Краткое содержание работы

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

В главе 1 сформулированы определения некоторых классов функций, изложены доказанные в работах А. Хаара, С. Качмажа, Г. Штейнгауза

и И.М. Соболя свойства функций Хаара {ха(з;)}, рядов Хаара, Фурье-Хаара, Пт-сеток, используемые в теории кубатурных формул.

В разделе 1.1 формулируется определение функций и дво-

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

Хаара. Приведено известное определение коэффициентов Фурье-Хаара 1

ск = J /(х)хк(х) йх произвольной интегрируемой функции /(х), заданной о

оо

на отрезке [0,1], и ряда Фурье-Хаара £ СкХк(х) этой функции. Приведе-

*=1

ны утверждения теорем о свойствах сумм рядов Хаара и Фурье-Хаара, о связи между указанными рядами. Сформулированы свойства системы Хаара, касающиеся сходимости рядов Хаара и Фурье-Хаара в пространстве Ьр[ 0,1].

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

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

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

с помощью минимальной кубатурной формулы, обладающей ¿-свойством (в, > 6), на основе этих рекуррентных соотношений разработан алгоритм, позволяющий строить минимальные кубатуриые формулы, обладающие й-свойством Хаара для любого наперед заданного четного (нечетного) числа (¿, исходя из минимальных кубатурных формул, обладающих (^-свойством Хаара для (¿о = 6 («¿о — 7).

В разделе 2.1 для одномерного и двумерного случаев приведены определения полиномов Хаара, кубатурных (квадратурных) формул, обладающих (¿-свойством Хаара, введены специальные функции и рассмотрены некоторые их свойства.

В подразделе 2.1.1 введено понятие полиномов Хаара. Полиномами Хаара степени (1 названы функции

Л 2"-1

Рл(х) = а0Х1(х) + ^ Х атХ»ьз(х),

т=1 j=l

где 6 > 1 — целое число, а0 £ К, а™ £ К, т = 1,2,...,с1, ] = 1,2,..., 2т_1, К — множество действительных чисел, при этом

2"-1 , . Ч 2

2 \ал ) ^ Под полиномами Хаара нулевой степени понимаются константы Р0(х) = ао, где оо 6 К.

Рассматриваются квадратурные формулы }

Л/1 = / <?(*)/(* « = <Э[/], (2)

О <=1

где х6 [0,1] — узлы формулы, С* 6 М — коэффициенты при ее узлах, г = 1,..., ЛГ, д{х),/(х) — определенные на отрезке [0,1] функции, такие, что функция д(х)/(х) суммируема на [0,1].

Считается, что такая формула обладает (¿-свойством Хаара, или просто — (¿-свойством, если она точна для любого полинома Хаара Р(х) степени, не превосходящей (I, т. е. <3[Р] = 1[Р]. Минимальной квадратурной формулой, обладающей (¿-свойством, названа формула (2) с наименьшим возможным числом узлов, точная для всех полииимов Хаара степеней не выше (I.

Квадратурная формула (2) названа формулой степени точности й Хаара, или (¿-точной, если она обладает (¿-свойством, но ((¿+ 1)-свойством не обладает.

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

Моментами порядка т названы числа = /[ХтлЬ т = 1,2,..., 3 = 1,2,..., 2'"-1, моментом нулевого порядка — число = 1[х\\-

Приведена лемма, которая следует из линейности функционалов /[/] и

Лемма 2.1. Формула вида (2) обладает д.-свойством, тогда и только тогда, когда = Аь Я[Хт,]\ = для всех т = 1,2,...,й. ] =

1,2.....2™-1.

Введено определение «-функции группы номер (1:

сI

««¿¿(ж) = XI (ж) +

т—\

где д. и ] — некоторые натуральные числа, 1 < ] ^ 2^, .71 = 1, индексы

• ■ • таковы, что С С ... С С ¿1,1 = [0,1],

5 [ 1, если 1т+1,}т+1 — ¿т,;п1' \ -1, если 1т+и,п+1 =

т = 1,2,...,о?, ^+1 =з.

Доказана

Лемма 2.2. Каждая функция Хаара из первых <1 групп и функция Х\(х) представимы в виде линейной комбинации к-функций группы номер и притом единственным образом.

Приведены два очевидных следствия этой леммы.

Следствие 1 леммы 2.2. Формула вида (2) обладает й-свойством, тогда и только тогда, когда она точна для всех к-функций группы номер с1.

Следствие 2 леммы 2.2. Мноэюество к-функций группы номер с1 образует базис в пространстве полиномов Хаара степеней, не превосходящих д.

Установлена справедливость лемм 2.3, 2.4.

Лемма 2.3. Для к-функций группы номер ё. имеет место равенство

(2Л при х 6 1А+и, 2<г~1 при х е \lduj, О при х € [0,1] \

3 = 1,2,...,2'.

Лемма 2.4. В точках непрерывности функции Хаара Хт^(х) имеет место равенство:

Хт,]{Х) = кт-1,]{%))

т = 1,2,..., ^ = 1,2,..., 2"1-1. Всюду, за исключением точек, в которых функции ХкЛх) и Хт,о{х) одновременно терпят разрыв (если такие точки существуют), произведение этих функций

Хы(х)ХтЛХ) = «

2 к 2 (ж), если, ¡т.] С 1к1, —2 2 если, С

О в остальных случаях,

где т ^ к, 2к~1 + г ф 2"1"1 +

В подразделе 2.1.2 введено определение полиномов Хаара степени й в двумерном случае:

Р*(х 1, ®2) = «о + Е Е аРхм(^г) + Е Ъ №хт№)+

1=1 1=1 т=1 ¿=1

2^-1 <)ГГ> — 1

+ Е Е Е <$тХ1Л*1)Хпи(х2),

2<г+т<«<»=1 ¿=1

где с/ ^ 2 — целое число, а0, а|г), 6 К, 1,т = 1,2, ...Д

г = 1,2,....2'-1, 1 = 1,2,...,2т~\ € К, ¿ + т = 2,...,<*,

£ ~ ^ (и л2

+ Е Е Е \с1,т ) Ф 0- Полиномом Хаара первой степени названа

1+т=(1г=1 ]=1 4 ' ' функция Р1{хъх2) = а0 + ахХгдСжг) + ЬшдЫ, где ао,аьЬ1 е Ж, + 0. Под полиномом Хаара степени, равной нулю, понимается некоторая константа: Ро(х\,Х2) = ао, ао € К. Рассматриваются кубатурные формулы 1 1 м ПП = // /(®1, <1Х1 йх2 и £ 4°) = (?[/], (3)

« = 1,2,..., 2'"1, ^ = 1,2.....2т~\ причем Е

¿=1

2'-1 2'"-1 / 2

О 0

¿=1

где (ж^.жг') € [0,1]2 — узлы формулы, С; е К — се коэффициенты, г — 1,2,..., ЛГ, /{х1,х2) - функция, определенная и суммируемая на [0,1]2.

Как и в главе 2, считается, что формула (3) обладает ¿-свойством Хаара. или просто — ¿-свойством, если она точна для любого полинома Хаара Р(х 1,2:2) степени, не превосходящей ¿, т. е. С}[Р\ = 1[Р\- Минимальной кубатурной формулой, обладающей ¿-свойством, названа формула (3) с наименьшим возможным числом узлов, точная для всех полигшмов Хаара степеней не выше ¿.

Кубатурная формула (3) называна формулой степени точности ¿ Хаара, или ¿-точной, если она обладает ¿-свойством, но (¿+ 1)-свойством не обладает.

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

Мономами Хаара степени ¿ названы функции Хс1,к{хъ)' Хй,к{х2), ХгМ)ХтМ1 гДе к = 1 + т = ¿, г = 1,2,...,21~\

3 = 1,2,..., 2т-1, а к-мономами степени ¿ — функции кл,к{х{), 2),

кцЫ)кп^(х2), к = 1,2,... ,2^, I + т = ¿, г = 1,2,...,2г, 3 = 1,2,..., 2'".

Приведена лемма, утверждение которой следует из линейности функционалов /[/] и СЦД:

Лемма 2.5. Формула (3) обладает ¿-свойством, тогда и только тогда, когда она точна для всех мономов Хаара степеней, не превосходящих й.

Функции ка,к(х 1), Кс1,к(х2), К1л(х\)кт,з{х2) названы к-мономамистепени ¿, где 1,2,'...,2<*, ¿ + № = ¿,¿ = 1,2,...,2', $ = 1,2,..., 2"\

Приведено очевидное утверждение:

Следствие лемм 2.2 и 2.5. Формула (3) обладает (1-свойством, тогда и только тогда, когда она точна для всех к-люномов степени ¿.

Установлена справедливость следующих утверждений.

Следствие леммы 2.3. Для к-моиомов степени й справедливо равеп-

ство:

' 2Л, если (хих2) € 1т+и х ¿,,+у,

если {ХиХ2) € {{¿т+М \ ¿т+1,«} X ¿п+и} У

X {¿п+и \

2 , если (жь х2) € \ ¿,„+и} X {1п+ц \ 1п+и),

О, если (жь х2) е [О, I]2 \ {1т+и X 1п+^},

т + п = (I, г = 1,2,..., 2"% ; = 1,2,... ,2П.

Приведена лемма, которая следует из этого утверждения

Лемма 2.6. Если ь^г) — произвольный к-моном степени й, то

1 1

1[Кв\ = Л Ка{х1,Х2) <1х1<1х2

о о

В разделе 2.2 проведено описание всех минимальных весовых квадратурных формул, обладающих ¿-свойством Хаара, рассмотрены некоторые примеры минимальных формул.

В подразделе 2.2.1 введено обозначение Т]т.: = / д(х)с1х =

1>п+14

= / д{х)йх, т = 1,2,..., ] = 1,2,...,2т и определение

0-1)/2"' _

¿-тривиального отрезка: двоичный отрезок ¿¿+1^ длины 2_с! назван ¿-тривиальным, если щ>г = 0, 1 ^ г ^ 2Л.

Доказаны следующие леммы.

Лемма 2.7. Если формула (2) обладает ¿-свойством, то выполняется условие (А): "каждый из двоичных отрезков 1,1+1.] = длины 2~й,

не являющихся й-тривиалъными. содержит хотя бы один узел формулы (2)".

Лемма 2.8. Минимальная формула (2), обладающая ¿-свойством, удовлетворяет условию (Б): "каждый из двоичных промежутков •■•> 1<1+1,2'1 содержит не более одного узла формулы".

Из лемм 2.7 и 2.8 следует, что искать минимальную формулу (2), обладающую ¿-свойством, имеет смысл среди формул, удовлетворяющих условиям (А) и (Б). В этой связи введены следующие обозначения: = .7 = 1,2,... ,2с/ - 1,

_ Г 0, если на промежутке нет узла, | С;я если существует узел х^ € /<¡+1,;,

з = 1,2,..., 2'',

, _ Г 0, если в точке ^ нет узла, ^ I Сч, если существует узел х-'1^ =

р+к_

7 = 1,2,..., 2'г_1, = и Р ~ натуральное, к — целое неотрица-

з=р _ _

телыюе число, р + к < 2е1, двоичные отрезки ..., 1а+\.р+к длины 2~'1 названы отрезками, образующими множество

Введено определение группы ¿-обособленных узлов: узлы, расположенные в точках <р, ¿р+1,.. - к ^ 1, образуют группу ¿-обособленных узлов ранга к, если на множестве \ £р+1,..., tp+k-^} нет пи одного узла формулы. Простейшей группой ¿-обособленных узлов является группа, состоящая из одного узла — группа 1-го ранга.

Устанавливается, что формула (2) точна для всех полиномов Хаара степеней, не превосходящих ¿, тогда и только тогда, когда имеет место система равенств

г/1 + Ы = Ы + У2 + Ы = %,2 Ы + ^ + ¿Уз = %.з ф

Ъ'-Р-г + У2'-1 + |г4<-1 = + У* =

Доказаны леммы 2.9, 2.10, в которых сформулированы достаточные условия существования на множествах типа Бр^ групп ¿-обособленных узлов и леммы, устанавливающие достаточные (лемма 2.12), а также необходимые и достаточные (лемма 2.11) условия разрешимости относительно коэффициентов формулы систем уравнений, образованных некоторыми равенствами системы (4).

В подразделе 2.2.2 введены следующие определения. Объединение к _

двоичных отрезков 5Р и = '<¿+1 р+з Длины 2~'1 названо:

;=0

— ¿-тривиальным множеством, если = 0, где ] = 0,1,... ,к, к — целое неотрицательное число,

к

— ¿-особым множеством 1-го рода, если ^ (—1 = 0, причем Ф

3=0

0, э = 0,1,..., к, к — натуральное число,

'к

— ¿-особым множеством 2-го рода, если ^{^У^р+з = 0> Шр+г = 0, а

з=о

при ] е [0, к] \ {г} ф О, где к, г — натуральные числа, такие, что

1 ^ г ^ к- 1.

Отмечено, что простейшим (¿-тривиальным множеством является (1-тривиальный отрезок. Из приведенных определений следует, что любое способов множество 1-го рода образовано не менее, чем двумя, а (¿-особое множество 2-го рода — не менее, чем тремя двоичными отрезками длины 2_<г, причем (¿-тривиальный отрезок, являющийся подмножеством с1~ особого множества 2-го рода, не может быть ни крайним слева, ни крайним справа из двоичных отрезков длины образующих это множество.

В дальнейшем рассматриваются совокупности ¿-особых множеств 1-го рода

«ЗрцА) 5р2,А:21 ■ • ■ > Зры,ки, (5)

которые не имеют общих внутренних точек. При этом (¿-особое множество 1-го рода считается частным случаем совокупности множеств вида (5).

Полагается, что ровно q двоичных отрезков длины 2~'1 отличны от й-тривиальных, 1 < д < 2А.

Установлена справедливость следующих утверждений.

Теорема 2.1. Пусть т — некоторое фиксированное натуральное число, т ^ 2е1-1. Если весовая функция д(х) такова, что сугцествует совокупность множеств вида (5) с М = т

<••! ) 3Р2м2 ,■■■, Зрт,кт (6)

и не су1цествует пи одной совокупности множеств вида (6), для которых М > т, то число узлов формулы (2), обладающей ¿-свойством, удовлетворяет неравенству N > ц — т.

Теорема 2.2. Если не существует, ни одного ¿-особого множества 1-го рода, то число узлов формулы (2), обладающей ¿-свойством, удовлетворяет неравенству N >

В подразделе 2.2.3 с помощью утверждений, уже доказанных в главе 2, устанавливаются необходимые и достаточные условия минимальности кубатурной формулы (2), обладающей (¿-свойством. Доказываются теоремы 2.3 — 2.6, утверждения которых приводятся в конце подраздела в более компактном виде (теоремы 2.7, 2.8).

Теорема 2.7. Пусть весовая функция д(х) такова, что сугцествует хотя бы одна совокупность множеств вида (6) и не существует ни одной совокупности множеств вида (5), для которых М > т. Формула (2) является минимальной формулой, обладаюш,ая (I-свойством, и при этом

имеет q—m узлов тогда и только тогда, когда выполняются следующие условия:

1) существует совокупность множеств вида (6)

Зр[,к{1 Зр'2,к'2, • • •,Зр'т,к'т,

такая, что узлы, расположенные па каждом из множеств ¿»р;,*;, находятся в точках 1р>,Ьр'+\,... ^р'+ь'-х, г = 1,2 т. е. являются д-обособленными и составляют т групп,

2) если й-тривиальный отрезок не является подмножеством ни одного из д.-особых множеств 2-го рода, которые попарно не пересекаются с мноэюествами ¿у.,^, г = 1,2,... ,т, то он не содерэ/сит ни одного узла формулы,

3) если с1-тривиальный от,резок является подмножеством некоторого й-особого множества 2-го рода не пересекающегося ни с одним из мнооюеств 3^., г = 1,2,... ,т, то он либо не содержит ни одного узла формулы, либо содержит ровно два узла, которые расположены на его концах и входят в группу й-обособленных узлов, находящихся в точках Ц-, ¿р+ъ • • •,

4) на каждом множестве таком, что на нет ни одного й-обособленного узла и ни один из (1-тривиа.шшх отрезков не является его подмножеством, а каждый из двоичных отрезков ¿(г+1,р-1 (если р > 1) и 1(!+1р+1+1 (если р + к < 2Л) либо является й-тривиальным, либо содерэюит й-обособленный узел, находятся ровно & +1 узлов, причем эти узлы расположены в соответствии с условиями (А) и (Б). Коэффициенты при узлах формулы однозначно определяются из системы

Ш-

Теорема 2.8. Пусть весовая функция д(х) такова, что не существует ни одного ¿-особого множества 1-го рода. Формула (2) является минимальной формулой, обладающей д-свойством, и при этом имеет (/ узлов тогда и только тогда, когда выполняются следующие условия:

1) если (1-тривиальный отрезок не является подмножеством ни одного из (1-особых множеств 2-го рода, то он не содеро/сит ни одного узла формулы,

2) если <1-тривиальный отрезок является подмножеством некоторого д,-особого мноо/сества 2-го рода то он либо не содерэюит ни одного узла формулы, либо содержит ровно два узла, которые расположены на его концах и входят в группу ¿-обособленных узлов, находящихся в точках ¿¡7, ¿р+ь • • ■ )

3) на каждом множестве таком, что на нет ни одного ¿-обособленного узла и ни один из ¿-тривиальных отрезков не является его подмножеством, а каждый из двоичных отрезков 1а+1,р-1 (еслир >

и 1,1+1,р+1+1 (если р + к < 2'9 либо является ¿-тривиальным, либо содержит ¿-обособленный узел, находятся ровно к +1 узлов, причем эти узлы расположены в соответствии с условиями (А) и (Б). Коэффициенты при узлах формулы однозначно определя7отся из системы

(4).

В подразделе 2.2.4 приведены примеры минимальных квадратурных формул с различными весовыми функциями, обладающих ¿-свойством (примеры 2.1 — 2.5). В частности, рассмотрена минимальная квадратурная формула (2), обладающая указанным свойством, с весовой функцией д(х) = 1 (пример 2.1). Число узлов такой формулы — 2й-1. Отмечено, что число узлов квадратурной формулы, рассмотренной в указанном примере, вдвое меньше числа узлов По-сетки квадратурной формулы, обладающей ¿-свойством, которая была построена И. М. Соболем.

Разделы 2.3 и 2.4 посвящены построению минимальных кубатурных формул, точных для полиномов Хаара в двумерном случае.

В разделе 2.3 рассмотрены минимальные кубатурные формулы, обладающие ¿-свойством Хаара для ¿ = 1,2,3.

В подразделе 2.3.1 доказана

Лемма 2.13. Вели формула (3) обладает ¿-свойством, то носитель каждого к- монома степени ¿ содержит хотя бы один узел этой формулы.

С помощью сформулированных выше утверждений получены оценки числа узлов кубатурной формулы, обладающей ¿-свойством, где ¿ ^ 2. Эти оценки приведены в следующих теоремах.

Теорема 2.9. Если координаты узлов формулы (3), обладающей ¿-свойством, не являются точками разрыва ни одной из функций Хаара (¿ — 1)-й группы, то 'число узлов такой формулы удовлетворяет неравенству: N > 2а.

Теорема 2.10. Если одна из координат хотя бы одного узла формулы (3), обладающей ¿- свойством, является точкой разрыва некоторой функции Хаара [й — 1) -й группы, то число узлов такой формулы

Отмечено, что из указанных теорем вытекает следующее утверждение.

Следствие теорем 2.9, 2.10. Для числа узлов формулы (3), обладающей ¿-свойством, справедлива оценка (7).

В подразделе 2.3.2 приведены примеры минимальных кубатурных формул, обладающих ¿-свойством Хаара для ¿ = 1,2,3 (примеры 2.6 — 2.8).

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

В подразделе 2.4.1 доказана лемма 2.14, устанавливающая достаточные условия существования не менее двух узлов формулы (3) на каждом из множеств вида

2 тг

2 м.

и [0,1] х

1. 2т1 ~~ 1 2е1

х [0,1],

2шг

2Л/,

1 1 2ГП2 - 1

2т1 - 1 2т! - 1 1 2м1 > 2М1 + 23

х [0,1]

2м2

2е1' 2м*

, [0,1] х

2т2 - 1 2т2 - 1

' 2м* + ¥

Установлена справедливость лемм 2.15,2.16, формулирующих достаточные условия существования не менее Ь + 1 узлов формулы (3) на прямоугольниках вида [трг, х [0,1] и [0,1] х [¿-г, , при этом в некоторых случаях рассматриваются прямоугольники, не являющиеся замкнутыми множествами.

В подразделе 2.4.2 введены следующие обозначения: через Ь обозначено множество некоторых прямых вида Х\ ~ ф, = ф (г = 1,2,..., — 1, ] = 1,2,..., 2й — 1), объединение которых включает множество

ии и )}•

М=1 т=1 Ь=1 4 ' >

С помощью указанных выше лемм доказана

Теорема 2.11. Число узлов формулы (3), обладающей ¿-свойством, удовлетворяет неравенству: N ^ 2й — |£|.

Установлено, что из теоремы 2.11 следует

Теорема 2.12. Если формула (3) обладает (1-свойст,вом, то для числа ее узлов справедливо неравенство: N ^ 2й — Л{<£), где

х/гА _ / 21+1 - 2 прга = 2к, т-\Зх2^-2 при<1 = 2к + 1, (8)

/с = 2,3,...

В подразделе 2.4.3 приведены примеры минимальных кубатурных формул, обладающих ¿-свойством Хаара для ¿ = 5,6,7 (примеры 2.10 — 2.12), и пример кубатурной формулы, точной для всех полиномов Хаара степеней, не превосходящих 4, число узлов которой на 1 больше нижней границы, фигурирующей в оценке из теоремы 2.12 (пример 2.9).

В подразделе 2.4.4 доказана

Лемма 2.17. Пусть кубатуриая формула (2) удовлетворяет следующим условиям,:

1) число узлов этой формулы N{6) = 2Л — X(й),

я, (1) (1) (2) (2) (АШ (А(<0) п-Л

2) числа х\,х2,х\,х2,---,х1 ,х2 кратны 2 а и отличны от 0 и 1, кратны 2~Л~1, но не кратны 2~а, коэффициенты формулы С\ = С2 = ... =

= С\(4) = 2~4+1, Сщ)+1 = Сщ)+2 = • • • = =

3) носитель каждого к-монома степени ¿ содержит ровно один узел формулы,

4) для любого к-монома К<1 степени ¿, такого, что

= 4 = 1.....А(с0'

при г = Х(д) + 1,..., 2а — Л(й),

5) = = 1 - 2~Л-\

где Бирр{/'£Гсг} — носитель функции Кд. а параметр Х((1) опредемется формулой (8).

Указанная формула является минимальной кубатурной форлщлой, обладающей (1-свойством.

Установлена справедливость следующей теоремы, в которой приведены рекуррентные соотношения для нахождения координат узлов минимальной кубатурной формулы, обладающей (с1 + 2)-свойством Хаара, с помощью минимальной кубатурной формулы, обладающей ¿-свойством ((1 > 6).

Теорема 2.13. Если (ж^,!^) ~~ узлы кубатур)юй формулы (2), удовлетворяющей условиям 1) — 5) леммы 2.17 ( г = 1,2,...,2<г — А(с1) ), то кубатурная формула

11 2Л-Х(с1)

// f(x1,x2)dx1dx2* Е (С{д/(^,'1),4,')) +

О 0 ¿=1

А(<й

2"'-А(й)-2 ч (9)

с узлами

— i — 1, ■ • • , A(oi),

/ (U) (UK _ (I d) , _J_ 1 («) , 1 \

г = A(d) + 1,... ,2rf - A(d) — 2, (10)

(J2"-X(d)-l,l) (2"-A(d)-l,lK rj (2'>-Md)-l) ц

(Xj ,¿2 J — (2xl '2'>

,J2«-A(d),l) (2'-A(d).lk _ /1 1_(2"-A(<0)x ) х2 I ~ \2' 2 2 i'

i2 i 'г-*'

2 2

Jb±2)

{xi ) ' ) — (1 — гз+s > ^я-г г — 1,..., A(d),

i = X(d) + 1,..., 2d - X(d) - 1,

4i,3)) = (1 - 1 - i = 1.....A(d),

4"3') = (i - + 1 - 54° + (12)

г = A(d) + l,...,2d-A(d) (.Tj' \ X2 ') = ^ ± 1 — 5^2 ^ ± ^та)' 2 = 1,..., A(d),

{Xi' ,^2' ) = (j^'I — — 5^2 — ^^^

i = A(d) + 1,..., 2d - A(d) - 2, г = 2d - A(d)

u коэффициентами при узлах

^2'J-A(d)-l,l = C2''-A(d),l = = C»,3 = 2~d~1, i — 1, . . . , A(d),

Ci,i = 2~d~\ i = A(d) + 1, A(d) + 2,... ,2d - A(d) - 2, Ci,-2 = Q,-4 = 2~d_2, ¿ = 1,2,..., A(d),

a.2 = 2~d~2, i = 1,2,..., 2d - \{d) - 1,

Сг.з = 2~d-2, i = A(d) + 1, A(d) + 2,..., 2d -\{d), a,4 = 2~d~2, i = 1,2,..., 2d - A(d) -2, i = 2d- X(d), является минимальной формулой, обладающей (d + 2) -свойством.

В подразделе 2.4.5 разработан алгоритм, позволяющий строить минимальные кубатурные формулы, обладающие d-свойством Хаара при d = п, где п ^ 8 — фиксированное целое число. Используется следующее представление числа п:

Г 6 при четном ii, п = ао + 2т, тбй, а0= , ,

[7 при нечетном а,

где N — множество натуральных чисел.

Для кубатурных формул, обладающих ¿-свойством при d ^ do, рассматриваются следующие условия:

(а) число узлов N(d) = 2d — Л (d), где Л (d) определяется согласно (8),

(б) каждый замкнутый двоичных1 прямоугольник lm+ij х 1п+и площади 2~d (m + п = d, j = 1,..., 2т, г = 1,..., 2n) codepotcum ровно один узел формулы, причем этот узел отличен от eepiuuu прямоугольника — точек (£,£),

(в) обе координаты A (d) узлов кратны 2 d и отличны от, Oui, коэффициенты формулы при этих узлах равны 2~d+x, а обе координаты каждого из остальных N(d) - A (d) узлов кратны 2~d~l, но не кратны 2~d, и коэффициенты при них равны 2~d,

(г) существует, узел, абсцисса которого равна 1 — 2~d~l, и узел, ордината которого равна 1 — 2~d~l, причем эти узлы различны,

(д) существует узы. абсцисса которого равна 2~d~1, и узел, ордината которого равна 2~d~l, причем эти узлы различны.

Для определенности считается, что в случае кубатурной формулы (3) Ж(Д№-3) _ 2-d-1 xWd)-2) _

Отмечено, что условия (а) — (г) выполняются для любой кубатурной формулы, удовлетворяющей условиям 1) — 5) леммы 2.17. Условию (д), а также условиям (а) — (г) удовлетворяют кубатурные формулы, приведенные в примерах 2.11, 2.12.

В данном подразделе на основе рекуррентных соотношений (10) - (13) разработан алгоритм, позволяющий строить минимальные кубатурные формулы, обладающие d-свойством Хаара для любого наперед заданного четного (нечетного) числа d, исходя из минимальных кубатурных формул, обладающих do-свойством Хаара для do = 6 (do = 7) и удовлетворяющих условиям (а) — (д), в которых полагается d = do.

Отмечено, что кубатурные формулы, рассмотренные в примерах 2.6 — 2.12 и лемме 2.17, имеют существенно меньше узлов, чем По-сетки кубатурных формул, обладающих d-свойством, которые были построены И. М. Соболем.

В разделе 2.5 рассмотрены методы двумерного дискретного преобразования Хаара.

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

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

Глава 3 посвящена оценкам погрешности формул приближенного интегрирования, точных для полиномов Хаара.

В разделе 3.1 эти оценки получены в одномерном случае.

В подразделе 3.1.1 рассматриваются квадратурные формулы (2) с весовой функцией д(х) = 1, т.е. формулы вида

1 N

Л/1 = f № dx « £ Cifix®) = Qlf], (14)

о i=1

где f(x) — функция, определенная и суммируемая на [0,1], х£ [0,1] — узлы формулы, С; — коэффициенты формулы при узлах (вещественные числа), г = 1,2,... ,N.

Функционал погрешности квадратурной формулы (14) обозначается через 5N\f}-

1 N

<Ш = Л/1 - Q[f] = I № dx-J2 0 i=1

Доказаны вспомогательные утверждения (леммы 3.1 - 3.6 и теорема 3.1), из которых следует

Теорема 3.2. Для нормы функционала погрешности квадратурной формулы (Ц), точной на константах, имеет место следующая нижняя оценка:

IIMU. > 2

Если квадратурная формула (Ц) обладает d-свойством, то

IIMU 4 (2")-'.

Здесь р > 1 — фиксированное действительное число. Показано, что минимальная квадратурная формула (14), обладающая (¿-свойством, является наилучшей формулой на пространствах 5Р — норма ее функционала погрешности на указанных пространствах удовлетворяет равенству

Эта квадратурная формула есть минимальная формула (2) с весовой функцией д{х) = 1, рассмотренная в примере 2.1. Такая формула единственна; число ее узлов N = 2<г_1, узлы этой формулы определяются равенствами = ^¡г, коэффициенты С; при узлах равны 2~а+1, % = 1,2,..., 2<г~1.

В подразделе 3.1.2 с помощью лемм 3.7 — 3.10 доказана

Теорема 3.3. Для нормы функционала погрешности квадратурной формулы (14), обладающей й-свойством, имеет место следующая оценка:

О—СЪ(1—1

Здесь а 6 (0,1] — фиксированное действительное число. Отмечено, что для нормы функционала погрешности рассмотренных И.М. Соболем кубатурных формул с 2Л узлами, образующими Пт-сетки (0 ^ т < 6), на пространствах На имеет место соотношение

ИМк = 0(М~а) при N 00.

В случае минимальной квадратурной формулы (14), обладающей й-свойством, выполняется такое же асимптотическое равенство. В то же время указанная формула, будучи минимальной формулой приближенного интегрирования, обеспечивает наилучшую поточечную сходимость к нулю при N —> оо.

В подразделе 3.1.3 рассматриваются весовые квадратурные формулы (2), коэффициенты при узлах этих формул считаются положительными:

С; > 0, ¿ = 1,2,..., N. (15)

Выражение для функционала погрешности таких формул принимает следующий вид:

Вводятся следующие обозначения:

С = 1д{х)йх, (16)

о

1

С0 = ! \д(х)\(1х. (17)

о

Фиксируется действительное число р > 1, через q обозначается сопряженное ему значение:

Р'1 + Т1 = 1.

Доказаны вспомогательные утверждения (леммы 3.11 — 3.13), на основании которых установлена справедливость следующих теорем.

Теорема 3.4. Если д 6 ¿1 [0,1], то для нормы функционала погрешности квадратурной формулы (2), удовлетворяющей условию (15) и точной па константах, имеет место нижняя оценка

||<Ы|5; ^ 2

где константа С определяет,ся согласно (16).

Теорема 3.5. Если д € Ь^О, 1]. то для нормы функционала погрешности квадратурной формулы (2), удовлетворяющей условию (15) и обладающей й-свойством, имеет место оценка

^ 2(2-*)^1Ы1(0Д1,

где константа Со определяется согласно (17).

Теорема 3.6. Если д £ ¿д[0,1], то для нормы функционала погрешности квадратурной формулы (2), удовлетворяющей условию (15) и обладающей (1-свойством, имеет место следующая оценка:

ИМ*; < 2(2-^11511^0,

Теорема 3.7. Если д е ¿«¡[0,1] и д(х) > 0 почти всюду на [0,1], то для нормы функционала погрешности квадратурной формулы (2) с N = 2Л узлами, удовлетворяюи^или условиям

х{1) е ¿<¡+1,1)

и коэффициентами при узлах, определяющгшися равенствами

н= ! д{х)йх,

С;

г = 1,2,..., 2а, имеет место неравенство

где константа б определяется согласно (16).

Отмечено, что для квадратурных формул, рассматриваемых в подразделе 3.1.3, и для формул, исследованных И. М. Соболем, величина

имеет один и тот же порядок — М~Т>.

В разделе 3.2 найдены оценки нормы функционала погрешности куба-турных формул (3), обладающих ¿-свойством Хаара в двумерном случае. Указанные формулы для удобства записываются в следующем виде:

1 1

N

ПП = Ц И ¿а/(х10,4°) = <2[/]. (18)

О О ®=1

С4ек, (яМ5) е [0,1]2,» = 1,2,...,ЛГ.

Погрешность кубатурной формулы (18) обозначается через 5дг[/]:

1 1 м Ы/] = '[/]-<?[/] = // 1(хих2)с1х1с1х2-^2аПх<(\х^). о о ;=1

В подразделе 3.2.1 коэффициенты при узлах кубатурной формулы (18) считаются положительными:

а > 0, г = 1,2,..., ЛГ.

Установлена справедливость вспомогательных утверждений (лемм 3.14 — 3.21 и теоремы 3.8), из которых вытекает

Теорема 3.9. Для нормы функционала погрешности кубатурной формулы (18), точной на константах, имеет место следующая нижняя оценка:

ИМи* >

Если кубатурная формула (18) обладает d-свойством, то \SN[f]\<ti(2dy>>\\f\\Sp, f€Sp,

IIMs; < 2Í(2d)~K

Здесь p > 1 — фиксированное действительное число. Доказаны вспомогательные утверждения (леммы 3.22, 3.23 и теорема 3.10), на основании которых получена

Теорема 3.11. Если кубатурная формула (18), число узлов которой N ~ 2d при d оо, обладает, d-свойством, то норма ее функционала погрешности

IIMU. ~ 2pN~r при N —► оо.

Показано, что в случае N ~ 2е1 при й—* оо исследованные в диссертации кубатурные формулы имеют наилучший порядок сходимости 5к по норме, равный ТУ-?. В частности, указанным свойством обладают формулы, рассмотренные в подразделе 2.4.5, в то же время они, будучи минимальными формулами приближенного интегрирования, обеспечивают наилучшую поточечную сходимость ¿лг[/] к нулю при N —► оо.

В подразделе 3.2.2 с помощью лемм 3.24 — 3.28 доказана

Теорема 3.12. Для нормы функционала погрешности кубатурной формулы (18), обладающей d-c6oйcmвoм, имеет место следующая оценка:

4 2а+2 -

11<Ы1я- < 2

-ad-2

2a - 1 (2a- 1 )2

Здесь а £ (0,1] — фиксированное действительное число.

Из теоремы 3.12 следует

Теорема 3.13. Если кубатурная формула (18), число узлов которой N ~ 2й при d оо, обладает d-cвoйcmвoм, то норма ее функционала погрешности удовлетворяет неравенству

|1М1я; < 0где ~ ПРи ^

Например, указанному в теореме 3.13 условию N ~ 2^, й —» оо, удовлетворяют минимальные кубатурные формулы, обладающие ¿-свойством, рассмотренные в подразделе 2.4.5 — число узлов каждой такой формулы N = 2й — (с? ^ 5), где определяется равенством (8).

Отмечено, что для нормы функционала погрешности рассмотренных И. М. Соболем кубатурных формул с 2й узлами, образующими Пг-сетки (О ^ г < в), на пространствах На в двумерном случае имеет место соотношение

\Ыщ=0{Н-а\пМ), ЛГ-> 00.

В случае минимальной кубатурной формулы (18), обладающей ¿-свойством, выполняется такое же асимптотическое равенство. В то же время указанная формула, будучи минимальной формулой приближенного интегрирования, обеспечивает наилучшую поточечную сходимость 5дг[/] к нулю при N оо.

В заключении приведены основные научные результаты, изложенные в диссертации.

Основные научные результаты

1. Описаны все минимальные весовые квадратурные формулы, обладающие ¿-свойством Хаара.

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

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

4. На пространствах 5Р (р > 1) и На (0 < а < 1) получены оценки погрешности формул приближенного интегрирования, обладающих й-свойством Хаара.

Работы автора по теме диссертации

Статьи в изданиях, рекомендованных ВАК РФ для опубликования материалов кандидатских и докторских диссертаций

[1] Кириллов К. А. Нижние оценки числа узлов кубатурных формул, точных для полиномов Хаара в двумерном случае // Вычислительные технологии. 2004. Т. 9. С. 62-71.

[2] Кириллов К. А. Построение минимальных кубатурных формул, точных для полиномов Хаара высших степеней в двумерном случае // Вычислительные технологии. 2005. Т. 10. С. 29-47.

[3] Кириллов К. А. Об оценке погрешности минимальных весовых квадратурных формул, точных для функций Хаара // Вычислительные технологии. Т. И. 2006. С. 44-50.

[4] Кириллов К. А. Алгоритм построения минимальных кубатурпых формул, обладающих d-свойством Хаара в двумерном случае // Журнал Сибирского федерального ун-та. Серия "Математика и физика". 2010. Т. 3. № 2. С. 205-215.

[5] Кириллов К. А. Об оценках погрешности квадратурных формул, точных для полиномов Хаара // Вычислительные методы и программирование. 2011. Т. 12. Раздел 1. С. 330-337 (http://num-metli.srcc.msu.ru/).

[6] Кириллов К. А. Оценки нормы функционала погрешности квадратурных формул, точных для полиномов Хаара // Журнал Сибирского федерального ун-та. Серия "Математика и физика". 2011. Т. 4. № 4. С. 479-488.

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

[8] Кириллов К. А., Носков М.В. Оценки погрешности на пространствах Sp кубатурных формул, точных для полиномов Хаара в двумерном случае // Журнал вычислительной математики и математической физики. 2009. Т. 49. № 1. С. 3-13.

[9] Noskov M. V., Kirillov К. A. Minimal cubature formulas exact for Haar polynomials // Journal of Approximation Theory. Volume 162. Issue 3. March 2010. P. 615-627.

Прочие публикации

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

[11] Кириллов К. А. Минимальные кубатурные формулы, точные для полиномов Хаара в двумерном случае // Теория симметрии и дифференциальные уравнения: Сборник трудов международной научной конференции "Теория симметрии и дифференциальные уравнения". Красноярск: ИВМ СО РАН, КГУ. 2002. С. 130-133.

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

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

[14] Кириллов К. А. О минимальных кубатурных формулах, точных для полиномов Хаара в двумерном случае // Кубатурные формулы и их приложения: Материалы VII международного семинара-совещания. Красноярск: КГТУ, 2003. С. 66-72.

[15] Кириллов К. А. Построение минимальных кубатурных формул, точных для полиномов Хаара в двумерном случае // Кубатурные формулы и их приложения: Материалы VIII международного семинара-совещания. Улан-Удэ: Изд-во ВСТГУ, 2005. С. 55-59.

[16] Кириллов К. А. Оценка погрешности минимальных квадратурных формул с весовой функцией, точных для полиномов Хаара // Математические методы и моделирование: Межвузовский сборник научных трудов. Вып. 42. Красноярск: ИПЦ КГТУ, 2006. С. 45-50.

[17] Кириллов К. А. Об оценках погрешности минимальных формул приближенного интегрирования, точных для конечных сумм Хаара // Теория функций, дифференциальные уравнения, вычислительная математика: Сборник материалов Уфимской международной математической конференции, посвященной памяти А. Ф. Леонтьева. Уфа: ИМВЦ УНЦ РАН, 2007. С. 19-22.

[18] Кириллов К. А. Верхняя оценка погрешности минимальных кубатурных формул, точных для полиномов Хаара в двумерном случае /'/ Труды IX международного семинара-совещания "Кубатурные формулы и их приложения". Уфа: ИМВЦ УНЦ РАН, 2008. С. 62-70.

[19] Кириллов К. А. Об оценках погрешности кубатурных формул, точных для полиномов Хаара // Кубатурные формулы, методы Монте-Карло и их приложения: Материалы международной конференции. Красноярск: Сибирский федеральный университет, 2011 г. С. 63-67.

с.

Подписано в печать 03.11.2011 Формат 60x84/16. Усл. печ. л. 1,6 Тираж 100 экз. Заказ № 5263

Отпечатано полиграфическим центром Библиотечно-издательского комплекса Сибирского федерального университета 660041 Красноярск, пр. Свободный, 82 а Тел./факс. (391)249-74-81, 249-73-55 E-mail: print_sfu@mail.ru; http://lib.sfu-krasn.ru

Введение

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

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

Глава 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.3. Необходимые и достаточные условия минимальности квадратурных формул, обладающих (¿-свойством Хаара.

2.2.4. Примеры минимальных квадратурных формул, обладающих ¿/-свойством Хаара.

2.3. Минимальные кубатурные формулы, обладающие й-свойством Хаара для (I ^ 3 в двумерном случае.

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

2.3.2. Примеры минимальных кубатурных формул, обладающих ¿-свойством Хаара для (¿=1,2,3.

2.4. Построение в двумерном случае минимальных кубатурных формул, обладающих (¿-свойством Хаара для й >

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

2.4.2. Уточнение нижних оценок числа узлов кубатурных формул, обладающих (¿-свойством Хаара при

2.4.3. Некоторые примеры минимальных кубатурных формул, обладающих (¿-свойством Хаара в случае с1 >

2.4.4. Построение минимальной кубатурной формулы, обладающей {й + 2)-свойством, на основе минимальной кубатурной формулы, обладающей (¿-свойством

2.4.5. Построение минимальных кубатурных формул высших степеней точности Хаара.

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

Построение и исследование формул приближенного интегрирования вида

И г ■

П г=1 ведется со времен И. Ньютона. В данной формуле через П обозначена область интегрирования из Мп, д(х\,. , хп) — весовая функция, — точки из П, называемые узлами формулы, — коэффициенты при узлах . . ,(некоторые действительные числа), г = 1,. , N. При п = 1 эти формулы носят называние квадратурных, а при п > 1 — кубатурных. Особый интерес в теории приближенного интегрирования вызывает задача построения таких формул вида (0.1), которые точно интегрируют некоторый заданный набор функций, используя наименьшее возможное число узлов. Эти формулы называются минимальными кубатурными (квадратурными) формулами, точными для функций из указанного набора. Минимизация числа узлов приводит к сокращению объема вычислений и, следовательно, к уменьшению машинной погрешности округлений. Следует отметить, что задача сокращения объема вычислений была и остается одной из самых актуальных в вычислительной математике.

При п = 1 для набора функций {/(ж)}, являющихся алгебраическими многочленами степеней не выше заданного числа (2, задача построения минимальных квадратурных формул решена полностью, причем в частном случае весовой функции д{х)) тождественно равной 1, ее решил К. Ф. Гаусс. Квадратурные формулы Гаусса с N узлами точны для любого алгебраического многочлена степени не выше 2А7" — 1 и являются формулами наивысшей алгебраической степени точности. Большинство алгоритмов вычисления узлов и коэффициентов при узлах квадратур Гаусса реализовано для сравнительно небольших значений числа узлов N (меньше или порядка 100), причем эти алгоритмы требуют О (Л7"2) операций при различных значениях константы в знаке О. Я.М. Жилейки-ным и Л. Г. Васильевой [11] построен и реализован алгоритм вычисления узлов и коэффициентов при узлах квадратуры Гаусса для сколь угодно большого N за количество операций О (АО

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

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

Существенный интерес представляют квадратурные формулы, точно интегрирующие алгебраические многочлены на сфере. Такие формулы исследовались В. И. Лебедевым [57] - [60], Г. Н. Салиховым [98], С. И. Ко-няевым [51] - [53] и другими авторами.

Минимальные квадратурные формулы, точные для тригонометрических полиномов степени не выше фиксированного с/, изучены А. X. Турецким [107], [108], Н. П. Кеда [28], [29], И. П. Мысовских [63], [64] и другими авторами. Полученные ими результаты изложены в монографии В. И. Крылова [56]. Минимальные кубатурные формулы, точно интегрирующие тригонометрические многочлены, исследовались в основном в работах М. В. Носкова [68] - [81], И. П. Мысовских [63] - [67], М. Beckers, R. Cools [112] и Н. Н. Осипова [76], [82] - [93]. Следует отметить, что внимание многих авторов привлекают исследования кубатурных формул с решетчатой структурой узлов. М.Д. Рамазановым [94] - [97] установлены достаточные условия оптимальности по вариации коэффициентов и решетки, даны алгоритмы построения решетчатых кубатурных формул, удовлетворяющих установленным достаточным условиям оптимальности, по этим алгоритмам составлены программы вычисления интегралов по двумерным ограниченным областям произвольных форм. Построение серий решетчатых кубатурных формул, точных на тригонометрических многочленах, было начато в работах М.В. Носкова [71], [74] и продолжено в [76] - [93]. В частности, H.H. Осиповым [82], [83] были описаны все минимальные решетчатые формулы для приближенного вычисления двойного интеграла, точные на тригонометрических многочленах степени не выше заданного числа d. В трехмерном и четырехмерном случаях им построены серии решетчатых кубатурных формул с тригонометрическим ¿¿(^-свойством: в трехмерном случае — наилучшие по числу узлов [88], [91], [92], в четырехмерном — серии, имеющие высокий коэффициент эффективности [93]. Для n-мерного случая Н. Н. Осипов предложил методику построения серий решетчатых кубатурных формул ранга 1 с тригонометрическим ¿¿(/с)-свойством и высоким коэффициентом эффективности.

В диссертации ставится вопрос о построении минимальных формул для функций системы {Хк{%)}) называемых обычно функциями Хаара. Эта система является ортогональной и обладает следующим замечательным свойством: любая непрерывная на отрезке [0,1] функция разлагается в равномерно сходящийся ряд по функциям системы. Благодаря указанному свойству функций {х/е(я)}, формулы вида (0.1), точные для всех полиномов Хаара степеней, не превосходящих достаточно большого числа d, имеют сравнительно малую погрешность [104]. Формулы приближенного вычисления интегралов, точные для полиномов по системе функций Хаара, можно найти в работах И.М. Соболя [104], [105] и К. Entacher [115] - [117]. В их трудах точность квадратурных и куба-турных формул на конечных суммах Хаара использовалась при выводе оценок погрешности этих формул, однако вопрос минимизации числа узлов, которому уделено основное внимание в настоящей работе, не рассматривался.

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

Все результаты диссертации являются новыми. Вопросы о наименьшем возможном числе узлов и построении минимальных формул, точных для полиномов Хаара, ранее не исследовались. В настоящей работе описаны все минимальные квадратурные формулы с произвольной суммируемой весовой функцией, точные для функций Хаара первых d групп, где d — некоторое фиксированное число. В двумерном случае получены нижние оценки числа узлов кубатурных формул, точных для полиномов Хаара степеней не выше d, построены минимальные кубатурные формулы, обладающие указанным свойством при d — 1,2,3,5,6,7, а также кубатурная формула, точная для полиномов Хаара степеней не выше 4, число узлов которой на 1 больше нижней границы, фигурирующей в одной из установленных оценок. Разработан алгоритм, позволяющий на основе минимальных кубатурных формул, обладающих ¿¿о-свойством Хаара для do = 6 (do = 7), строить минимальные кубатурные формулы, обладающие d-свойством Хаара для любого наперед заданного четного (нечетного) числа d. Получены оценки погрешности на пространствах Sp квадратурных формул с весовой функцией g Е Ь^О,1] и g G Lq[0,1} р-1 -Ьд-1 = 1), обладающих ¿¿-свойством Хаара, а также оценки погрешности на пространствах и На квадратурных и кубатурных формул с весовой функцией д{х) = 1, обладающих ¿¿-свойством Хаара соответственно в одномерном и двумерном случае.

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

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

Указанные результаты докладывались на VI международном семинаре-совещании "Кубатурные формулы и их приложения" (Уфа, 3-7 июля 2001 г.), III международной конференции "Теория симметрии и дифференциальные уравнения"(Красноярск, 25 - 29 августа 2002 г.), уфимской международной математической конференции "Теория функций, дифференциальные уравнения, вычислительная математика" , посвященной памяти А. Ф. Леонтьева (Уфа, 28 мая - 1 июня 2007 г.), международной конференции "Дифференциальные уравнения. Функциональные пространства. Теория приближений" , посвященной 100-летию со дня рождения С. Л. Соболева (Новосибирск, 5-12 октября 2008 г.), международной конференции "Кубатурные формулы, методы Монте-Карло и их приложения" (Красноярск, 4-8 июля 2011 г.), на семинарах Сибирского федерального университета и Института вычислительного моделирования СО РАН.

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

В главе 1 приведены свойства функций (х*;^)}» используемые в теории квадратурных и кубатурных формул, доказанные в [25], [104], [121], [122].

В разделе 1.1 формулируется определение функций {Хк(%)} и двоичных промежутков. Отмечено, что в литературе можно встретить различные определения функций {х/с(ж)}5 отличающиеся значениями этих функций в точках разрыва. Перечислены основные свойства функций Хаара. Приведены утверждения теорем о свойствах сумм рядов Хаара и Фурье - Хаара, о связи между указанными рядами. Сформулированы свойства системы Хаара, касающиеся сходимости рядов Хаара и Фурье - Хаара в пространстве Ьр[0,1].

В разделе 1.2 приводятся определения классов функций и Н0 в одномерном и двумерном случаях.

В разделе 1.3 формулируются определения двоичного параллелепипеда и Пт-сеток. Приведено утверждение о точности кубатурных формул вида (0.1) с узлами, образующими Пт-сетку, и равными коэффициентами при этих узлах, для конечных сумм Хаара, а также теорема об оценках нормы функционала погрешности кубатурных формул на пространствах ¿>р и На, исследованных И. М. Соболем [104].

В главе 2 описаны все минимальные квадратурные формулы с произвольной весовой функцией, точные для функций Хаара, выявлена зависимость числа узлов от свойств весовой функции, указаны правила выбора узлов и значений коэффициентов при узлах таких формул, приведены примеры минимальных квадратурных формул для некоторых весовых функций. В этой главе исследованы также кубатурные формулы, точные для полинимов Хаара в двумерном случае: получены нижние оценки числа узлов кубатурных формул, обладающих ¿-свойством Хаара (в, ^ 2), приведены примеры минимальных формул, обладающих ¿-свойством Хаара для с1 = 1,2,3,5,6,7, пример кубатурной формулы, точной для всех полиномов Хаара степеней, не превосходящих 4, число узлов которой на 1 больше нижней границы, фигурирующей в одной из полученных оценок, доказаны рекуррентные соотношения для нахождения координат узлов минимальной кубатурной формулы, обладающей (¿ + 2)-свойством Хаара, с помощью минимальной кубатурной формулы, обладающей ¿¿-свойством {<& ^ 6), на основе этих рекуррентных соотношений разработан алгоритм, позволяющий строить минимальные куба-турные формулы, обладающие ¿-свойством Хаара для любого наперед заданного четного (нечетного) числа ¿, исходя из минимальных кубатур-ных формул, обладающих ¿о-свойством Хаара для ¿о = б (¿о =

В разделе 2.1 для одномерного и двумерного случаев приведены определения полиномов Хаара, кубатурных (квадратурных) формул, обладающих ¿-свойством Хаара, введены специальные функции и рассмотрены некоторые их свойства. В подразделе 2.1.1 введено понятие полиномов Хаара одной переменной, квадратурных формул, обладающих ¿-свойством, Ас-функций — специальных функций, представимых в виде линейных комбинаций функций Хаара. Сформулирована постановка задачи, решаемой в одномерном случае. Доказаны свойства к-функций и квадратурных формул, точных для полиномов Хаара степеней, не превосходящих заданного числа ¿. В подразделе 2.1.2 введено определение полиномов Хаара двух переменных, мономов Хаара, к-мономов — попарных произведений к-функций переменной х\ на ас функции переменной ^2, понятие кубатурной формулы, обладающей ¿-свойством. Сформулирована постановка задачи, решаемой в двумерном случае. Доказаны свойства к-мономов и кубатурных формул, точных для полиномов Хаара степеней, не превосходящих заданного ¿, а также лемма о представлении произведения функций Хаара в точках непрерывности этих функций.

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

Разделы 2.3 и 2.4 посвящены построению минимальных кубатурных формул, точных для полиномов Хаара в двумерном случае.

В разделе 2.3 рассмотрены минимальные кубатурные формулы, обладающие (¿-свойством Хаара для с? = 1,2,3. В подразделе 2.3.1 доказано необходимое условие точности кубатурной формулы для полиномов Хаара степеней не выше (¿. Получены оценки числа узлов кубатурной формулы, обладающей (¿-свойством Хаара. В подразделе 2.3.2 приведены примеры минимальных кубатурных формул, обладающих (¿-свойством Хаара для (¿=1,2, 3.

В разделе 2.4 рассмотрены минимальные кубатурные формулы, обладающие (¿-свойством Хаара для (I > 3. Коэффициенты при узлах рассматриваемых кубатурных формул считаются положительными. В подразделе 2.4.1 доказана лемма, устанавливающая достаточные условия существования не менее двух узлов кубатурной формулы на каждом из замкнутых прямоугольников специального вида. Установлена справедливость лемм, формулирующих достаточные условия существования не менее t + I узлов рассматриваемой формулы на указанных прямоугольниках, причем в некоторых случаях рассматриваются прямоугольники, не являющиеся замкнутыми множествами. В подразделе 2.4.2 выведены нижние оценки числа узлов кубатурных формул, обладающих в,-свойством при О 4. В подразделе 2.4.3 приведены примеры минимальных кубатурных формул, обладающих ¿¿-свойством Хаара для д, = 5,6,7, и пример кубатурной формулы, точной для всех полиномов Хаара степеней, не превосходящих 4, число узлов которой на 1 больше нижней границы, фигурирующей в одной из полученных оценок. В подразделе 2.4.4 получены рекуррентные соотношения для нахождения координат узлов минимальной кубатурной формулы, обладающей 2)-свойством Хаара, с помощью минимальной кубатурной формулы, обладающей д,-свойством (О 6). В подразделе 2.4.5 на основе этих рекуррентных соотношений разработан алгоритм, позволяющий строить минимальные ку-батурные формулы, обладающие (¿-свойством Хаара для любого наперед заданного четного (нечетного) числа с/, исходя из минимальных кубатурных формул, обладающих (¿о-свойством Хаара для (¿о = 6 ((¿о = 7).

В разделе 2.5 рассмотрены методы двумерного дискретного преобразования Хаара. В подразделе 2.5.1 приведен классический метод дискретного преобразования Хаара. В подразделе 2.5.2 предложен вариант дискретного преобразования Хаара, основанный на По-сетках с 2^ узлами, которые являются сетками кубатурных формул, обладающих й-свойством Хаара; проведено сравнение этого варианта с классическим методом.

Глава 3 посвящена оценкам погрешности формул приближенного интегрирования, точных для полиномов Хаара.

В разделе 3.1 эти оценки рассмотрены в одномерном случае. В подразделе 3.1.1 на пространствах Бр найдена нижняя оценка нормы функционала погрешности квадратурных формул, точных на константах, и верхняя оценка нормы функционала погрешности квадратурных формул, обладающих ¿-свойством Хаара. В подразделе 3.1.2 на пространствах На получена верхняя оценка нормы функционала погрешности квадратурных формул, обладающих ¿-свойством Хаара. В подразделе 3.1.3 на пространствах исследованы весовые квадратурные формулы: в случае весовой функции д £ Ь\[0,1] найдена нижняя оценка нормы функционала погрешности формул, точных на константах, в случаях д £ Ь^У0,1] и д £ Ьд[0,1] (1 + q~l = 1) — верхние оценки нормы функционала погрешности формул, обладающих ¿-свойством Хаара; отдельно исследованы минимальные весовые квадратурные формулы, обладающие ¿-свойством Хаара, которые были рассмотрены в примере 2.3 — в случае весовой функции д £ ¿^[0,1], почти всюду положительной на отрезке [0,1], получена верхняя оценка нормы функционала погрешности таких формул.

В разделе 3.2 найдены оценки нормы функционала погрешности ку-батурных формул, обладающих ¿-свойством Хаара в двумерном случае. В подразделе 3.2.1 на пространствах Бр получена нижняя оценка нормы функционала погрешности кубатурных формул, точных на константах, и верхняя оценка нормы функционала погрешности кубатурных формул, обладающих ¿-свойством Хаара. В подразделе 3.2.2 на пространствах На получена верхняя оценка нормы функционала погрешности кубатурных формул, обладающих ¿-свойством Хаара.

Диссертационная работа выполнена при поддержке грантов РФФИ 03-01-00703-а "Кубатурные формулы с узлами на решетках" (2003-2005гг.), 04-01-00823-а "Кубатурные формулы, точные на системах функций" (2004-2006гг.), 07-01-00326-а "Кубатурные формулы, точные на системах функций, и их приложения" (2007-2009 гг.).

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

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

Следующие обозначения используются в работе без пояснений: Мп — п-декартова степень множества М; \М\ — число элементов (конечного) множества М; К — множество действительных (вещественных) чисел; Мп — п-мерное вещественное пространство; N — множество натуральных чисел;

Кп — единичный п-мерный куб {(х\,. , хп) : 0 ^ Х\ ^ 1,., О ^ хп ^ 1}; вирр / — носитель функции /;

Ьр[0,1] — пространство функций, суммируемых со степенью р на отрезке

ОД];

II • ||х — норма элементов линейного нормированного пространства с1е1 (Л) — определитель матрицы А.

Остальные обозначения либо вводятся в диссертации, либо являются общеизвестными.

Заключение

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

1. Описаны все минимальные весовые квадратурные формулы, обладающие ¿¿-свойством Хаара.

2. В двумерном случае получены нижние оценки числа узлов куба-турных формул, обладающих (¿-свойством Хаара. ;

3. В двумерном случае разработан алгоритм построения для любого наперед заданного целого (/ ^ 8 минимальных кубатурных формул, обладающих (¿-свойством Хаара.

4. В одномерном и двумерном случаях на пространствах 5р (р > 1) и На (0 < а ^ 1) получены оценки погрешности формул приближенного интегрирования, обладающих (¿-свойством Хаара.

1. Акишев Г. А. Обобщенная система Хаара и теоремы вложения в симметричные пространства // Фундаментальная и прикладная математика. 2002. Т. 8. № 2. С. 319-334. ' '

2. Алферова Е.Д. Равенство Парсеваля для рядов Фурье-Стилтьеса по системе Хаара // Вестн. Моск. ун-та. Сер. 1: "Математика. Механика". 2003. № 6. С. 47-50.

3. Алферова Е.Д. Равенство Парсеваля для кратных рядов Фурье-Стилтьеса по системе Хаара // Вестн. Моск. ун-та. Сер. 1: "Математика. Механика". 2007. № 4. С. 8-12 .

4. Андрианов А. В. Приближение функций из классов МНrq полиномами Хаара // Математические заметки. Т. 66. Вып. 33. Сентябрь 1999. С. 323-335.

5. Арунянц Г. Г., Казарян М. Л. Класс систем ортогональных функций Хаара, построенных на базе модифицированных комплексных функций Радемахера // Владикавказский математический журнал. Январь-март 2005. Том 7. Выпуск 1. С. 16- 24.

6. Ахмед Н., Pao К. Р. Ортогональные преобразования при обработке цифровых сигналов: Пер. с англ. /Под ред. И. Б. Фоменко. М.: Связь, 1980. 248 с.

7. Белов А. М. Обобщенные вейвлет-преобразования Хаара и их применение к компрессии изображений. Дисс. . канд. физ.-мат. наук. Самара, 2007. 124 с.

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

9. Бочкарев С. В. О коэффициентах рядов по системе Хаара // Матем. сб. 1969. Т. 80. № 1. С. 97-116.

10. Брыскин И. БЛелонд О. В., Семенов Е. М. Мультипликаторы рядов Фурье-Хаара // Сибирский математический журнал. Июль-август, 2000. Том 41. № 4. С. 758-766.

11. Васильева Л. Р., Жилейкин Я. М. О быстром вычислении узлов и весов квадратуры Гаусса // Ж. вычисл. матем. и матем. физ., 44:3 (2004), С. 426-431.

12. Волосивец С. С. Приближение функций ограниченной ]э-вариации полиномами по системам Хаара и Уолша // Математические заметки. Т. 53. Вып. 6. Июль 1993. С. 11-21.

13. Еогладзе Л. Д., Цагарейшвили В. Ш. Абсолютная сходимость рядов Фурье-Хаара двух переменных // Известия вузов. Математика. 2008. № 5. С. 14-25.

14. Гогян С. Л. Нелинейная аппроксимация в 1/1(0, 1) по системе Хаара. Дисс. . канд. физ.-мат. наук. Ереван, 2005 г. 83 с.

15. Голубое Б. И. О рядах Фурье непрерывных функций по системе Хаара // Изв. АН СССР. Сер. матем. 1964. Т. 28. № 6. С. 12711296.

16. Голубое Б. И. Ряды по системе Хаара // Математический анализ. М.: ВИНИТИ, 1971. С. 109-146.

17. Голубое Б. И. Наилучшие приближения функций в метрике Ьр полиномами Хаара и Уолша // Математический сборник. 1972. Т. 87 (129), № 2. С. 254-274.

18. Горлов С. К., Новиков И. Я., Родин В. А. Коррекция полиномов Ха-ара, применяемых для сжатия графической информации // Известия высших учебных заведений. Математика. 2000. № 7 (458). С. 6-10.

19. Дагман Э. Е., Кухарев Г. А. Быстрые дискретные ортогональные преобразования. Новосибирск: Наука, 1983.

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

21. Жарких A.A. Обработка изображений на основе вейвлет-преобразования в базисе Хаара над конечным полем нечетной характеристики // Вестник МГТУ. 2009. Т. 12. № 2. С. 197-201.

22. Залманзон Л. А. Преобразования Фурье, Уолша, Хаара и их применение в управлении, связи и других областях'. М.: Наука. Гл. ред. физ.-мат. лит., 1989. 496 с.

23. Иванов В. Р Преобразование Хаара для произвольного числа точек // Радиоэлектроника. 1989. № 7. С. 41-45.

24. Канторович Л. В., Акилов Г. П. Функциональный анализ. М.: Наука, 1984.

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

26. Кашин Б. С., Саакян А. Л. Ортогональные ряды. М.: Наука, 1984.

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

28. Кеда Н. П. Квадратурные формулы с производными для периодических функций // Весщ АН БССР. Сер. ф1з.-тэхн. 1961. № 4. С. 35 — 39.

29. Кеда Н. П. К теории квадратур для периодических функций // ДАН БССР. 1961. Вып. 5. № 9. С. 55-59.

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

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

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

33. Кириллов К. А. Минимальные квадратурные и кубатурные формулы, точные для полиномов Хаара. Дисс. . канд. физ.-мат. наук. Красноярск, КГТУ, 2003 г. 104 с.

34. Кириллов К. А. О минимальных кубатурных формулах, точных для полиномов Хаара в двумерном случае // Кубатурные формулы и их приложения: Материалы VII международного семинара-совещания. Красноярск: КГТУ, 2003. С. 66-72.

35. Кириллов К. А. Нижние оценки числа узлов кубатурных формул, точных для полиномов Хаара в двумерном случае // Вычислительные технологии. Специальный выпуск. 2004. Т. 9. С. 62-71.

36. Кириллов К. А. Построение минимальных кубатурных формул, точных для полиномов Хаара в двумерном случае // Кубатур-ные формулы и их приложения: Материалы VIII международного семинара-совещания. Улан-Удэ: Изд-во ВСТГУ, 2005. С. 55-59.

37. Кириллов К. А. Построение минимальных кубатурных формул, точных для полиномов Хаара высших степеней в двумерном случае // Вычисл. технологии. 2005. Т. 10. Спец. выпуск. С. 29-47.

38. Кириллов К. А. Оценка погрешности минимальных квадратурных формул с весовой функцией, точных для полиномов Хаара //Математические методы и моделирование: Межвузовский сборник научных трудов. Вып. 42. Красноярск: ИПЦ КГТУ, 2006. С. 45-50.

39. Кириллов К. А. Об оценке погрешности минимальных весовых квадратурных формул, точных для функций Хаара // Вычислительные технологии. Специальный выпуск. 2006. Т. 11. С. 44-50.

40. Кириллов К. А. Верхняя оценка погрешности минимальных кубатурных формул, точных для полиномов Хаара в двумерном случае // Труды IX международного семинара-совещания " Кубатур-ные формулы и их приложения". Уфа: ИМВЦ УНЦ РАН, 2008. С. 62-70.

41. Кириллов К. А. Алгоритм построения минимальных кубатурных формул, обладающих ¿-свойством Хаара в двумерном случае // Журнал Сибирского федерального ун-та. Серия "Математика и физика". 2010. Т. 3. № 2. С. 205-215.

42. Кириллов К. А. Об оценках погрешности кубатурных формул, точных для полиномов Хаара // Кубатурные формулы, методы Монте-Карло и их приложения: Материалы международной конференции. Красноярск: Сибирский федеральный университет, 2011 г. С. 63-67. , .

43. Кириллов К. А. Об оценках погрешности квадратурных формул, точных для полиномов Хаара // Вычислительные методы и программирование. 2011. Т. 12. Раздел 1. С. 330-337 (Шр://пит-meth.srcc.msu.ru/).

44. Кириллов К. А. Оценки нормы функционала погрешности квадратурных формул, точных для полиномов Хаара // Журнал Сибирского федерального ун-та. Серия "Математика и физика". 2011. Т. 4. № 4. С. 479-488.

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

46. Кириллов К. А., Носков М.В. Оценки погрешности на пространствах Sp кубатурных формул, точных для полиномов Хаара в двумерном случае // Журнал вычислительной математики и математической физики. 2009. Т. 49. № 1. С. 3-13.

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

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

49. Коненков В. Н., Мясников В. В. Быстрые алгоритмы локального дискретного вейвлет-преобразования с- базисом Хаара // НТК с межд. участием: "ПИТ-2006" Том 2. 2006 г. Самара. С. 113-118.

50. Кротов В. Г. О безусловной сходимости рядов Хаара в // Мат. заметки. 1978. Т. 5. Ш 23. С. 685-695.

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

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

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

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

55. Лукомский С. Ф. О рядах Хаара на компактной нуль-мерной группе // Известия Саратовского университета. 2009. Т. 9. Сер. "Математика. Механика. Информатика". Вып. 1. С. 14-19.

56. Малоземов В. Н., Машарский С. М. Основы дискретного гармонического анализа. Часть вторая. СПб.: НИИММ, 2003. 100 с.

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

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

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

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

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

62. Носков М. В. Кубатурные формулы для приближенного интегрирования периодических функций. Деп. в ВИНИТИ, 1983. № 4528-83. 11с. ! ' •

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

64. Носков М. В. Приближенное интегрирование периодических функций от двух переменных // Уравнения неклассического типа. Новосибирск: ИМ СО АН СССР, 1986. С. 97-98.

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

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

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

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

69. Носков М. В. Некоторые вопросы приближенного интегрирования периодических функций. Дисс. . докт. физ.-мат. наук. Красноярск, 1992. 226 с.

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

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

72. Носков М. В., Осипов Н. Н. Минимальные и почти минимальные решетчатые кубатурные формулы ранга 1, точные на тригонометрических многочленах двух переменных // Сибирский журнал вычислительной математики. 2004. Т. 7. № 2. С. 125-134.

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

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

75. Носков М. В., 8с1гт((1 Н. J. Кубатурные формулы высокой тригонометрической точности // Журнал вычислительной математики и математической физики. 2004. Т. 44. № 5. С. 786-795.

76. Осипов Н. Н. О семействах минимальных кубатурных формул четной тригонометрической точности в 2-мерном случае // Кубатурные формулы и их приложения: Доклады, представленные на

77. I семинар-совещание "Кубатурные формулы и их приложения". Уфа: ИМВЦ УНЦ РАН. 1996. С. 61-63.

78. Осипов Н. Н. Почти минимальные решетчатые кубатурные формулы с тригонометрическим ¿¿-свойством в 2-мерном случае // III Сибирский конгресс по прикладной и индустриальной математике: Тезисы докладов. Ч. I. Новосибирск: ИМ СО РАН, 1998. С. 120.

79. Осипов Н. Н. Нижняя граница для числа узлов кубатурных формул нечетной тригонометрической степени // Кубатурные формулы и их приложения: Материалы V международного семинара-совещания. Красноярск: КГТУ, 2000. С. 137-140.

80. Осипов Н. Н. Симметрия узлов и коэффициентов минимальных кубатурных формул с тригонометрическим ¿/-свойством при нечетном d // Методы вычислений. СПб.: Изд-во С.-Петерб. ун-та, 2001. Вып. 19. С. 166-171.

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

82. Осипов И. Н. Асимптотика нормы функционала погрешности решетчатых кубатурных формул на пространствах W^s'p'q\A) // Вычислительные технологии. 2004. Т. 9. Спец. выпуск. С. 95-101.

83. Осипов Н. Н. О минимальных кубатурных формулах с тригонометрическим ¿-свойством в двумерном случае // Журнал вычислительной математики и математической физики. 2005. Т. 45. № 1. С. 8-16.

84. Осипов Н. Н. Наилучшие по числу узлов серии решетчатых куба-турных формул, точных на тригонометрических многочленах трех переменных // Журнал вычислительной математики и математической физики. 2005. Т. 45. № 2. С. 212-223.

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

86. Осипов H.H., Петров A.B. Построение серий решетчатых кубатурных формул, точных на тригонометрических многочленах четырех переменных // Вычислительные технологии. 2004. Т. 9. Спец. выпуск. С. 102-110.

87. Рамазанов М.Д. Оптимальная решетчатая кубатурная формула на банаховых пространствах периодических функций. Математические заметки. 1975. Т. 17. № 1. С. 67-69.

88. Рамазанов М.Д. О порядке сходимости решетчатых кубатурных формул в пространствах с доминирующей производной // Докл. АН СССР. 1984. Т. 277. № 3. С. 551-553.

89. Рамазанов М.Д. Решетчатые кубатурные формулы могут дать наилучший порядок точности на пространствах с доминирующими производными // Кубатурные формулы и их прилож. Красноярск: КГТУ, 1994. С. 102-113.

90. Рамазанов М.Д. Новый алгоритм асимптотически оптимальных решетчатых кубатурных формул. Уфимский математический журнал. 2010. Т. 2. № 3. С. 63-82.

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

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

93. Соболь И. М. Точная оценка погрешности многомерных квадратурных формул для функций класса 5Р // ДАН СССР. 1960. Т. 132. № 5. С. 1041-1044.

94. Соболь И.М. О вычислении многомерных интегралов // ДАН СССР. 1960. Т. 139. № 4. С. 821-823.

95. Соболь И. М. О применении рядов Хаара в теории квадратурных формул // Вопросы вычислительной математики и вычислительной техники: Сборник научных трудов. М.: Машгиз, 1963. С. 31-35.

96. Соболь И. М. О распределении точек в кубе и приближенном вычислении интегралов // Журнал вычислительной математики и математической физики. 1967. Т. 7. № 4. С. 784-802.

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

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

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

100. Турецкий А. X. О формулах квадратур, точных для тригонометрических полиномов // Уч. записки Белгосуниверситета: Сер. матем. 1959. Вып. 1 (49). С. 31-54.

101. Турецкий А. X. О квадратурных формулах с четным числом узлов, точных для тригонометрических полиномов // ДАН БССР. I960. Вып. 4. № 9. С. 365-368.

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

103. Шарапудинов И. И., Муратова Г. Н. Некоторые свойства г-кратно интегрированных рядов по системе Хаара // Известия Саратовского университета. 2009. Т. 9. Сер. "Математика. Механика. Информатика". Вып. 1. С. 68-76.

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

105. Beckers M., Cools R. A relation between cubature formulae of trigonometric degree and lattice rules // Numerical Integration IV, Birkhauser Verlag. 1993. P. 13-24.

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

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

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

109. Entacher K. Quasi-Monte Carlo methods for numerical integration of multivariate Haar series II // BIT (Dan). 1998.Vol. 38. № 2. P. 283292.

110. Fischer B., Preston J. Wavelets based on orthogonal polynomials // Math. Comput. 1997. Vol. 66. № 226. P. 1593-1618.

111. Gogyan S. On divergence of the Ll-greedy algorithm by Haar system // Journal of Contemporary Mathematical Analysis. V. 39 (2004). № 5. P. 23-34.

112. Gogyan S. Greedy algorithm with regard to Haar subsystems // East Journal on Approximations. V. 11 (2005). № 2. P. 221-236.

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

114. Haar A. Osszegyujtott munkai. Budapest: Gesammelte Arbeiten, 1959.

115. Kamont A. General Haar systems and greedy approximation // Studia Mathematica. 145(2001). № 2. P. 165-184.

116. Kampe de Feriet J. Pseudo-integrales de Stiltjes aleatoires // C. R. Ac ad. Sei. 1961. Vol. 252. № 15. P. 2162-2165.

117. Kolzow L.} Pietrich V. Wavelets. A tutorial and bibliography // Workshop "Teor. Misurae anal, reale". Rend. I-st math. Univ. Trieste. 1994. № 26. P. 49-220.

118. Noskov M. V., Kirülov K. A. Minimal cubature formulas exact for Haar polynomials // Journal of Approximation Theory. Volume 162. Issue 3. March 2010. P. 615-627.

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

120. Temlyakov V. N. Nonlinear m-term approximation with regard to the multivariate Haar system // East Journal on Approximations. V. 4 (1998). № 1. P. 87-106.