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

• Осипов, Николай Николаевич
• доктор физико-математических наук
• 2004

Оглавление диссертации доктор физико-математических наук Осипов, Николай Николаевич

Введение.

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

§2. Об обозначениях

1. Метод воспроизводящего ядра и минимальные кубатурные формулы с тригонометрическим d-свойством.

§1. Воспроизводящее ядро функционального пространства со скалярным произведением

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

§3. Минимальные кубатурные формулы с тригонометрическим d-свойством

§4. Минимальные кубатурные формулы с тригонометрическим d-свойством при п —

§5. О минимальных решетчатых кубатурных формулах с тригонометрическим ^-свойством при п =

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

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

Проблема приближенного вычисления интегралов привлекает к себе внимание математиков уже несколько столетий и, по-видимому, еще долго будет актуальной ввиду как бесконечного разнообразия подынтегральных функций, так и весьма широкого круга постановок задач приближенного интегрирования. Эти задачи находятся, как правило, в русле трех направлений. Первое из них характеризуется построением кубатурных формул (т.е. правил приближенного интегрирования), точных на некотором конечномерном классе функций, при этом на число или расположение узлов кубатурных формул накладываются те или иные ограничения. Второе направление включает в себя изучение нормы функционала погрешности кубатурной формулы в предположении, что рассматриваемый класс интегрируемых функций представляет собой некоторое банахово пространство (обычно кубатурная формула зависит от малого параметра, а изучается поведение нормы ее функционала погрешности при стремлении этого параметра к нулю). Третье направление связано с методами Монте-Карло, в основе которых лежит моделирование случайных величин, а также с методами, использующими различные равномерно распределенные последовательности неслучайных точек (например, ЛПГ последовательности Соболя [91]).

Основное внимание в диссертации уделено первому направлению, причем в качестве класса функций выбрано множество тригонометрических многочленов, степень которых ограничена некоторой фиксированной величиной (вообще говоря, произвольной). Частично затронуто и второе направление, а вот третье по существу осталось за рамками настоящей работы (здесь мы отсылаем заинтересованного читателя к соответствующей литературе, например [4], [92], [25], [37], [38]).

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

В теории приближенного вычисления интегралов естественным образом возникает вопрос об оценке качества конструируемых кубатурных формул. Под кубатурной формулой обычно понимают приближенное равенство г N /ОФМ dx^Y] Cjf{x{:i)),

Jn j=l где x^ и Cj — соответственно узлы и коэффициенты кубатурной формулы, Q — область интегрирования, f(x) — интегрируемая функция, р(х) — фиксированная функция, называемая весовой. Существуют различные критерии качества кубатурной формулы, удовлетворить которые можно за счет соответствующего выбора параметров кубатурной формулы — ее узлов и коэффициентов.

Например, можно исходить из требования точности кубатурной формулы на всех функциях из некоторого конечномерного пространства функций (скажем, пространства алгебраических или тригонометрических многочленов степени не выше данной). Согласно этому критерию, кубатурная формула считается тем лучшей, чем большей является размерность пространства функций, на которых кубатурная формула точна. Дополнительное и естественное с практической точки зрения требование минимальности числа узлов N делает задачу построения таких кубатурных формул вполне содержательной. Эта оценка качества кубатурных формул восходит к К. Ф. Гауссу (1777 — 1855), исследовавшему вопрос о построении квадратурных формул (правил приближенного интегрирования функций одной переменной), дающих точный результат на любом алгебраическом многочлене, степень которого не превосходит заданной величины.

Можно также требовать, чтобы кубатурная формула обеспечивала некую гарантированную оценку погрешности на всех функциях из данного бесконечномерного банахова пространства. С этой точки зрения лучше та кубатурная формула, у которой норма функционала погрешности определяемого равенством N lj)= [ f(x)p(x)dx-J2Cjf(x^)

J n j^i I имеет меньшую величину (т.е. кубатурная формула тем лучше; чем меньше по абсолютной величине значение ее функционала погрешности на «наихудшей» функции из пространства). Такого взгляда придерживался в своих исследованиях С. JI. Соболев (1908 — 1989), один из создателей современной теории кубатурных формул, и его ученики (см. [13], [78], [80], [101]). Мы будем рассматривать кубатурные формулы вида N f(x)p(x)dx^Y/Cjf{x^), (0.1)

0,1)" j=1 причем преимущественно при р(х) = 1, и говорить об их точности на тригонометрических многочленах — линейных комбинациях функций (так называемых тригонометрических одночленов) fQ(x) = ехр (27гг(а, х)), х = (xh .,хп) е Rn, где i = v^—1 — мнимая единица, а = (ац,., ап) Е Zn и а, х) = OL\XI + . + апхп.

Степень тригонометрического одночлена fa(x) есть число

Н| = |ai| + . + |аг„|; степень тригонометрического многочлена определяется стандартным образом.

Будем говорить, что кубатурная формула (0.1) обладает тригонометрическим ^-свойством, если она точна для всех тригонометрических многочленов /(ж), степень которых не превосходит d. Тривиальным примером такой ку-батурной формулы является п-я декартова степень квадратурной формулы прямоугольников: sty)- (0-2)

0,1)"

Здесь N = (d + 1)п.

Число узлов N кубатурной формулы с тригонометрическим ^-свойством не может быть меньше некоторой величины No(d), которую обычно называют нижней границей Мёллера (по аналогии с алгебраическим случаем, см. работу X. Мёллера [121]). Кубатурную формулу (0.1) с тригонометрическим ^-свойством и

N = N0(d) принято называть минимальной. Нижняя граница Мёллера является априорной, ориентировочной границей, поэтому существование минимальных ку-батурных формул не гарантируется (см. пример 1.6).

При п = 1 минимальные квадратурные формулы совпадают с квадратурными формулами наивысшей тригонометрической точности и хорошо изучены (см., например, [36]). Для произвольной неотрицательной весовой функции р(х) простую методику построения таких квадратур указал И. П. Мысов-ских в [40]. Здесь впервые был применен так называемый метод воспроизводящего ядра (об этом методе для алгебраического случая см. в монографии [39]), что позволило, в частности, установить для случая р(х) = 1 единственность минимальных квадратурных формул (с точностью до сдвигов множества узлов по модулю 1).

Отдельные результаты о кубатурных формулах, точных для тригонометрических многочленов степени не выше d, имеются в хорошо известных монографиях [32], [89]. Однако впервые постановка задачи о построении минимальных кубатурных формул с тригонометрическим d-свойством была осуществлена в работе М. В. Носкова [51] (депонированный вариант [50]). Здесь же была вычислена нижняя граница Мёллера No(d) и в двумерном случае найдены первые примеры минимальных кубатурных формул для произвольного нечетного d. Последовавшие затем работы Мысовских [41 — 43], [47 — 49], Носкова [52 — 56], [60], [61] (последние две — в соавторстве с А. Р. Семеновой), А. В. Резцова [83], Семеновой [87], а также ряда зарубежных авторов (см., например, [105], [106], [110]), продолжили это направление и ставили своей основной задачей получение минимальных кубатурных формул с тригонометрическим d-свойством, либо достаточно близких к ним по числу узлов.

Такую же цель преследовал и автор диссертации в большей части своих работ (см. [63 — 65], [67 — 69], [71], [74], [75]), а также в работах, выполненных совместно с А. В. Петровым [76], [77] и Носковым [58], [59].

Среди перечисленных выше работ других авторов выделим те, которые явились, на наш взгляд, этапными (см. также недавно вышедшую обзорную статью [62]). Все они, за одним исключением, относятся к случаю р(х) = 1.

Прежде всего отметим работу [53], где предъявлены в двумерном случае минимальные кубатурные формулы с тригонометрическим ^-свойством для любого четного d. Вместе с аналогичными примерами для нечетных d они до сих пор вызывают интерес (см., например, одну из недавних работ [128]).

За ней, несомненно, следует работа [43] (подробный вариант заметки [40]), в которой метод воспроизводящего ядра впервые был приспособлен к тригонометрическому случаю (хотя это и было сделано только лишь при п = 1). Это обстоятельство оказалось исключительно плодотворным. С помощью метода воспроизводящего ядра в 1996 году независимо были получены похожие результаты в работе [110] и в работе автора [63]. В первой из них в двумерном случае было указано некоторое семейство минимальных кубатурных формул для любого нечетного d, а во второй не только сделано то же самое, но и дополнительно показано, что этим семейством, по существу, и исчерпывается все множество рассматриваемых минимальных кубатурных формул. Этот последний результат является главным в первой главе диссертации. Для его получения пришлось существенно развить метод воспроизводящего ядра в тригонометрическом случае. Компактное и в то же время наиболее полное и последовательное изложение этого метода занимает большую часть указанной главы. В частности, здесь дано простое и естественное доказательство гипотезы Мысовских (см. [47], [48]) об узлах и коэффициентах минимальной кубатурной формулы с тригонометрическим d-свойством при нечетном d в случае симметричной весовой функции р(х).

Отметим, что задача описания в двумерном случае всех минимальных кубатурных формул для произвольного четного d до сих пор не решена. Известно только (см. [120]), что для d ^ 30 такие кубатурные формулы могут быть только решетчатыми ранга 1, а значит, исчерпываются кубатурными формулами из работы [53].

О существовании минимальных кубатурных формул с тригонометрическим с?-свойством при п ^ 3 известно значительно меньше, чем в двумерном случае; вероятно, они существуют лишь в редких ситуациях (примеры см. в третьем параграфе первой главы). По ряду причин имеет смысл сосредоточиться на изучении так называемых решетчатых кубатурных формул, наиболее важным примером которых считаются кубатурные формулы Н. М. Коробова (вида (0.1), см. далее), использующие параллелепипедальные сетки узлов [32]. Решетчатые кубатурные формулы являются естественным аналогом сферических дизайнов (обобщение квадратурных формул Чебышёва на случай интегрирования по поверхности сферы) и наиболее перспективны в плане приложений. Как теоретический, так и практический интерес представляет круг задач, связанных с построением решетчатых кубатурных формул произвольно большой тригонометрической степени точности, имеющих приемлемое (близкое к минимально возможному и в идеале — минимальное) число узлов. Здесь, как нам кажется, вполне можно говорить о новом векторе исследований в рамках принятого направления.

В следующей этапной работе [54] объектом исследования являются кубатурные формулы вида /(*)<**« Е/ ({#})• (°-3)

0,1)" -7"1 где р — некоторый целочисленный вектор, называемый порождающим; фигурные скобки обозначают взятие дробных частей от всех компонент вектора. Такие кубатурные формулы называются решетчатыми ранга 1. Предложенная в [54] методика построения кубатурных формул такого вида, имеющих сколь угодно большую тригонометрическую степень точности, заключается в следующем. Сначала нужно построить значительное количество кубатурных формул не слишком большой степени точности d, но с достаточно малым числом узлов. Затем, проанализировав параметры найденных кубатурных формул (в данном случае это число узлов и компоненты порождающего вектора), можно попытаться представить их как некоторые функции переменной степени точности d. При правильном угадывании функциональных зависимостей таким способом могут быть обнаружены бесконечные серии решетчатых кубатурных формул ранга 1 с тригонометрическим с?(&)-свойством (к — параметр серии). Это особенно хорошо удается сделать в случае, когда выбираемые для численных экспериментов значения d принадлежит одному классу вычетов по некоторому модулю т (в работах [54], [61], например, т = 4).

Этот метод построения серий обладал по крайней мере двумя недостатками (помимо того, что был полуэвристическим и подразумевал существенное привлечение интуиции исследователя). Первый состоял в том, что построение кубатурных формул вида (0.3) заданной тригонометрической степени точности d с наименьшим или близким к нему числом узлов фактически осуществимо только методом полного перебора. Уже при сравнительно малых значениях d даже при п = 3 это оказывается практически неразрешимой проблемой. Второй недостаток связан с самой формой записи решетчатой кубатурной формулы ранга 1 — в виде (0.3), удобном скорее для практического использования, чем для теоретического поиска закономерностей. Отметим, что подобные недостатки характерны и для другой методики построения серий, предложенной в работе [60] и реализованной при п = 4 в [61] и при п = 5 в [87].

Тем не менее в случае п = 3 путем численных экспериментов удалось построить примеры серий решетчатых кубатурных формул ранга 1 с тригонометрическим с£(/с)-свойством и асимптотически минимальным числом узлов, где d(k) = вк- 1 см. работу [76], которую тоже можно отнести к разряду этапных — в силу принципиальной новизны предложенного там обоснования корректности построенных серий). Несколько позже аналогичные серии были найдены и для всех остальных классов вычетов по модулю 6, но уже, разумеется, при помощи совершенно иных идей (см. ниже).

Толчком к возникновению новых идей, к изложению которых мы сейчас переходим, для автора послужила работа [108], в которой для решения одной частной задачи теории решетчатых кубатурных формул, точных на тригонометрических многочленах, привлекались некоторые понятия из геометрии чисел (см. монографию [28]). Одним из основателем этого раздела теории чисел считается Г. Минковский (1864 — 1909). Именно ему, по существу, и принадлежат те классические идеи, которые мы сумели приспособить для решения задач указанного выше направления.

Вообще привлечение теоретико-числовых методов — далеко не редкое явление в приближенном интегрировании периодических функций, но раньше это в основном касалось вопроса о построении кубатурных формул, пригодных для так называемых классов функций с доминирующей производной. Данному вопросу посвящена весьма обширная литература (как российская, так и зарубежная), но мы лишь укажем на приоритетные в этой области работы Коробова и Н. С. Бахвалова, а также на некоторые работы их учеников К. К. Фролова, В. А. Быковского, Н.М. Добровольского (см. список литературы; более подробную библиографию можно найти в [33] — расширенном втором издании монографии [32]). Бывает и так, что использование теоретико-числовых фактов в приближенном интегрировании попросту необходимо. Например, в теории кубатурных формул С. J1. Соболева естественным образом возникает потребность в наиплотнейших решетчатых упаковках шаров (см. [16]). Имеется, конечно, и обратная связь: исследования по куба-турным формулам могут привести к содержательным теоретико-числовым задачам (укажем в качестве таковой задачу Соболева — Ранкина, решением которой занимался С. С. Рышков [84]).

Следует отметить, что наиболее близкой к вопросам, рассматриваемым в диссертации, и, по-видимому, одной из самых первых работ подобного рода оказалась работа [95], написанная еще в 1977 году. В ней уже угадывались некоторые аспекты современного подхода к проблемам, затронутым в диссертации. В частности, было приведено общее понятие решетчатой кубатурной формулы, которое затем в несколько ином и каноническом для нас виде появилось в работе [123].

Пусть А — некоторая решетка интегрирования, т.е.

Под решетчатой кубатурной формулой с решеткой узлов А мы далее понимаем кубатурную формулу множество узлов которой составляют все точки решетки А, принадлежащие [0,1)п. Эта конструкция является естественным обобщением кубатурных формул Коробова (0.3). О применении решетчатых кубатурных формул в приближенном вычислении кратных интегралов см., например, [124].

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

А э Zn. о,*.

0.4) позволяет дать новую и правильную (т.е. в определенном смысле неулучша-емую) нижнюю границу для числа узлов решетчатых кубатурных формул с тригонометрическим d-свойством, которую можно назвать нижней границей Минковского Ni(d) и которая выражается через так называемый критический определитель А(Хп) стандартного гипероктаэдра xn = {х е Еп : ||ж|| < 1} см. второй параграф второй главы). При этом если п ^ 3, то, вообще говоря, имеет место неравенство

Ni(d) > N0(d).

Главная трудность, однако, состоит в том, что точное значение константы А(Хп) известно пока только при п = 3 (не считая почти очевидного случая п = 2). Название «нижняя граница Минковского» — не только дань уважения классику, но также и напоминание о весьма нетривиальном факте

Д№) = (0.5) установленном самим Минковским в 1904 году (см. его оригинальную работу [1191).

В случае п = 4 наилучшей оценкой для Д(ХП) до недавнего времени считалась указанная в [108] (она уточняла более известную оценку из [113]). Нам удалось несколько улучшить этот результат и, более того, указать экстремальную решетку для гипероктаэдра в R4. Последнее мы считаем одним из главных результатов второй (центральной во всех смыслах) главы диссертации. В перспективе найденная нами экстремальная решетка (претендующая также и на роль критической) сможет послужить источником хороших результатов по составлению таблиц наилучших по числу узлов четырехмерных решетчатых кубатурных формул с тригонометрическим d-свойством.

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

Другой основной результат второй главы состоит в указании естественного и сравнительно простого в реализации подхода к задаче построения серий решетчатых кубатурных формул ранга 1 с тригонометрическим £/(&)-свойством и высоким коэффициентом эффективности. Решетчатые кубатурные формулы вида (0.3) имели и до сих пор имеют первостепенное значение как в вопросах теории (см., например, [32], [33], [2]), так и в различных приложениях (например, к дискретному преобразованию Фурье [12], [29] и задачам обработки изображений [112]). Главное отличие предложенного нами подхода от всех предыдущих состоит в том, что построение серий решетчатых кубатурных формул ранга 1 осуществляется на основе общей формы записи решетчатой кубатурной формулы (0.4), а не специфической (0.3).

При р(х) = 1 коэффициентом эффективности кубатурной формулы (0.3), обладающей тригонометрическим d-свойством, в работе [54] названа величина показывающая, во сколько раз меньше число узлов этой кубатурной формулы по сравнению с аналогичной простейшей кубатурной формулой (0.2). Если речь идет о серии кубатурных формул с тригонометрическим d(k)~свойством, то коэффициент эффективности определяется как предел таковых для кубатурных формул из серии. Разработанная нами новая методика построения серий решетчатых кубатурных формул ранга 1 в случае произвольной размерности имеет и конкретные результаты: так, например, предъявлена серия с коэффициентом эффективности 4п~1/п (см. четвертый параграф второй главы).

Наибольшего эффекта от использования методов геометрии чисел удалось I • достичь в случае п = 3. Во многом, но не во всем это можно считать следствием формулы Минковского (0.5). Отметим, что последняя достаточно часто цитировалась (см., например, [95], [83], а также некоторые недавние работы [108], [116], [118]), однако, как нам кажется, должного своего применения до сих пор не находила.

Новый подход при построений серий в сочетании с формулой (0.5) привел в трехмерном случае к наилучшим по числу узлов сериям 5(тш) решетчатых кубатурных формул с тригонометрическим о?(&)-свойством, где d{k) = 6к + г, г — вычет по модулю 6 см. пятый параграф второй главы). Здесь термин «наилучшие по числу узлов» можно объяснить так. Если 7V(min)(/c) обозначает число узлов в серии g(mm) (вычет г фиксирован), а, N (к) — число узлов в произвольной серии S с тригонометрическим с/(&)-свойством, то

N(k) ^ N^Ma\k) для всех достаточно больших к. Поскольку априори N(k) и суть многочлены (третьей степени) от к, это условие можно выразить следующим образом: набор коэффициентов N(k) «лексикографически старше» набора коэффициентов N^mm\k). Разумеется, все серии gt"1111) автоматически оказываются сериями с асимптотически минимальным числом узлов. Отметим также, что они содержат в себе все ранее известные наилучшие по числу узлов решетчатые кубатурные формулы с тригонометрическим (/-свойством (за исключением случаев d = 4 и d = 6), найденные в результате многозатратного компьютерного поиска (см. таблицу 1 в работе [108]).

При некоторых значениях г (именно, при г = 1 и г = 3) возможное отклонение N^mm\k) от точной нижней границы всего лишь пропорционально к, т.е. весьма мало (грубо говоря, из 1000 = 103 узлов самое большее 10 могут быть лишними). Вполне можно допустить, что это отклонение на самом деле просто равно нулю.

Предложенный общий подход к построению серий дает неплохие результаты и в случае п = 4. Нам удалось построить серии решетчатых кубатурных формул с коэффициентом эффективности

164

3312 И 19'78'

Это почти на четверть больше, чем 16 — именно такой коэффициент эффективности имеют серии из работы [61] (последние были получены полуэмпирическими методами, кратко охарактеризованными нами выше). Этот результат мы также относим к основным во второй главе.

Теперь скажем несколько слов о результатах последней, третьей главы диссертации. В ней речь идет об оценке нормы функционала погрешности простейших решетчатых кубатурных формул в классах периодических функций с доминирующей производной. Следует отметить, что основные результаты этой главы — теоремы 3.1 и 3.2 — в другой форме были ранее получены соответственно Фроловым (см. [96], а также [33, гл. 6]) и коллективом соавторов во главе с Добровольским (см. [23]). Однако из-за определенного отличия в постановке задач наш способ доказательства представляется логически более простым и во всяком случае не требует большого количества вспомогательных утверждений технического характера (это относится в первую очередь к теореме 3.2). В принципе, эту главу можно было бы представить как дополнение к диссертации. Тем не менее, учитывая общий в диссертации объект исследования — кубатурные формулы для периодических функций — и преследуя полноту изложения материала, мы предпочли включить ее в основной текст.

Далее для удобства читателя приводится краткое описание содержания диссертации по главам.

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

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

Во втором параграфе появляется основной объект исследования — куба-турные формулы, обладающие тригонометрическим d-свойством. Ставится задача об описании кубатурных формул с тригонометрическим d-свойством и минимально возможным числом узлов. Первым шагом в решении этой трудной задачи является почти столь же трудное установление точной нижней границы для числа узлов таких кубатурных формул. Естественным ориентиром здесь может быть нижняя граница Мёллера No(d).

В третьем параграфе рассматривается задача об описании минимальных кубатурных формул с тригонометрическим d-свойством (т.е. таких, у которых число узлов совпадает с нижней границей Мёллера). Наиболее естественным, на наш взгляд, способом решения этой задачи является метод воспроизводящего ядра, позволяющий дать теоретически простые критерии существования минимальных кубатурных формул с тригонометрическим «/-свойством. Последовательное изложение этого метода и составляет основное содержание параграфа.

В четвертом параграфе приводится основной результат главы — полное описание в двумерном случае всех минимальных кубатурных формул с тригонометрическим d-свойством для любого нечетного d (теорема 1.11). Это описание получено нами методом воспроизводящего ядра.

Последний, пятый параграф содержит описание (также в двумерном случае) всех минимальных кубатурных формул с тригонометрическим d-свойст-вом в специальном классе решетчатых кубатурных формул ранга 1, но уже для произвольного d (теорема 1.12). Как и выше, результат достигается применением метода воспроизводящего ядра. Кроме того, в конце параграфа на конкретном примере демонстрируется, как этот метод сделать пригодным и для описания решетчатых кубатурных формул ранга 1 с тригонометрическим (/-свойством и числом узлов, близким к нижней границе Мёллера (см. теорему 1.13).

Глава завершается приложением, в которое вынесены доказательства теорем первого параграфа о представлении воспроизводящих ядер конечномерных пространств алгебраических многочленов со скалярным произведением специального вида. Это представление описывается в терминах классических ортогональных многочленов одной переменной (многочленов Гегенбауэра) и может быть использовано при построении методом воспроизводящего ядра кубатурных формул с (алгебраическим) с?-свойством для приближенного вычисления интегралов по n-мерному единичному шару с весом (1 — |#|2)7.

2. Основным объектом исследования во второй главе являются кубатур-ные формулы с тригонометрическим d-свойством, расположение узлов которых имеет наиболее простую структуру — решетчатую. Нам представляется естественным применять здесь методы геометрии чисел — раздела теории чисел, изучающего точечные решетки (центральное понятие геометрии чисел) в их связи с геометрическими фигурами. Основными «рабочими» понятиями для нас являются понятие критического определителя и критической (а иногда и просто экстремальной) решетки данной геометрической фигуры. Определение тригонометрического ^-свойства содержит в себе намек и на саму эту геометрическую фигуру — ею оказывается гипероктаэдр (crosspolytope), обобщение обычного октаэдра на n-мерный случай.

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

Второй параграф начинается с критерия, позволяющего определить, обладает ли решетчатая кубатурная формула тригонометрическим d-свойством. Этот критерий открывает путь к применению фактов геометрии чисел, оперирующих понятием критического определителя. Решение поставленных задач о решетчатых кубатурных формулах оказывается тесно связанным с решением задачи о вычислении критического определителя гипероктаэдра. Основным результатом этого параграфа следует считать найденный методом «малых шевелений» пример экстремальной решетки для гипероктаэдра в М4 (теорема 2.2).

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

Четвертый параграф является наиболее важным с идейной точки зрения. Здесь мы излагаем простой и в то же время эффективный подход к задаче построения так называемых серий решетчатых кубатурных формул с тригонометрическим d(k)~свойством. Как результат, в n-мерном случае легко предъявляется вполне конкретная серия решетчатых кубатурных формул ранга 1, коэффициент эффективности которой существенно больше, чем в ранее известных примерах подобного типа (см. пример 2.6). В предлагаемом способе построения серий предусмотрена возможность оптимизации, что позволяет для конкретных значений п получать еще более качественные результаты.

В пятом параграфе при п = 3 найдены наилучшие по числу узлов серии решетчатых кубатурных формул с тригонометрическим d(k)~свойством (теорема 2.4). Этот результат является одним из основных результатов данной главы и дает наиболее полное представление об эффективности применяемых нами методов геометрии чисел. Как уже было отмечено выше, отправным пунктом здесь оказывается точное значение критического определителя октаэдра, вычисленное Минковским.

В шестом параграфе построены примеры серий решетчатых кубатурных формул с тригонометрическим б?(&)-свойством при п = 4 (см. таблицы 12 и 13). По коэффициенту эффективности эти серии являются наилучшими из известных на данный момент. Следует подчеркнуть, что полученный нами результат не может быть окончательным — хотя бы по той причине, что указанная во втором параграфе экстремальная решетка для гипероктаэдра в М4 является иррациональной. Именно эта экстремальная (и, что не исключено, даже критическая) решетка может служить источником новых результатов, некоторые из которых нам уже удалось получить. (Не считая целесообразным излагать в диссертации эти еще нигде не опубликованные факты, мы ограничиваемся лишь указанием перспективы их получения.)

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

3. В третьей главе изучаются решетчатые кубатурные формулы на пространствах Жр'р,<^(Л) периодических функций с доминирующей производной (здесь Л — решетка периодов).

Первый параграф носит вспомогательный характер. Во-первых, здесь сообщаются необходимые определения и факты, относящиеся к геометрическому методу в теории алгебраических чисел. Во-вторых, излагается способ решения так называемых норменных уравнений, в основе которого лежат идеи П. Г. JI. Дирихле (1805 — 1859). (Именно теория норменных уравнений послужит для нас главным инструментом при доказательстве теорем следующего

параграфа.) В-третьих, вводятся сами пространства Л).

Второй параграф содержит основные результаты главы — теоремы 3.1 и 3.2. В этих теоремах речь идет об оценке при- h —> О функции через которую легко выражается норма функционала погрешности lh рассматриваемых решетчатых кубатурных формул (в предположении, что М — решетка, дуальная к Л — имеет «алгебраическое» происхождение, т.е. ее конструкция связана с некоторым полем алгебраических чисел).

В третьем параграфе приводятся некоторые дополнительные результаты, касающиеся только случая р = 2, q = 0 (теоремы 3.3 и 3.4). Для их формулировки и доказательства используются понятия и факты теории диофантовых приближений.

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

Нумерация формул, принятая в диссертации, является двойной: первый номер обозначает главу, в которой расположена формула, а второй номер есть порядковый номер формулы в главе. Аналогичным образом нумеруются и различные «теоремоподобные» конструкции — определения, теоремы, леммы и т.д. (так, например, «теорема 2.4» означает «четвертая теорема второй главы»). Замечания не нумеруются (как правило, необходимости в ссылках на них не возникает). Текст, набранный мелким шрифтом, играет роль дополнительного комментария и при первом чтении может быть пропущен. 1

§2. Об обозначениях

Без пояснений используются следующие стандартные обозначения: Z, Q, R, С — множества целых, рациональных, вещественных, комплексных чисел соответственно;

Хп ~ п-я декартова степень множества Х\

Х\ — число элементов (конечного) множества Х\

С* — биномиальный коэффициент (число сочетаний из п по 5); det (Л) — определитель матрицы А\ ехр (а) — показательная функция с основанием е = 2.718.; Г (а) — гамма-функция Эйлера; ^(а) — дзета-функция Римана.

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

Остальные обозначения либо общеприняты и потому не могут быть неправильно истолкованы (как dimV — размерность пространства V), либо их смысл ясен из контекста (например, на стр. 25: L\ JL L2 — подпространства L\ и Li ортогональны), либо же они носят специальный характер и объясняются по ходу дела.

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

1. Ароншайн Н. Теория воспроизводящих ядер j j Сб. пер. «Математика». М.: ИЛ, 1963. Т. 7. № 2. С. 67-130.

2. Бабенко К. И. Основы численного анализа. Москва-Ижевск: НИЦ «Регулярная и хаотическая динамика», 2002. 848 с.

3. Бахвалов Н.С. О приближенном вычислении кратных интегралов // Вестн. Моск. ун-та. 1959. № 4. С. 3 — 18.

4. Бахвалов Н. С. Об оптимальных оценках сходимости квадратурных процессов и методов интегрирования типа Монте-Карло на классах функций // Числ. методы решения дифференц. и интегр. ур-ний и квадратурные ф-лы. М.: Изд-во АН СССР, 1964. С. 5-63.

5. Бахвалов Н.С. Оценки снизу асимптотических характеристик классов функций с доминирующей смешанной производной // Матем. заметки. 1972. Т. 12. № 6. С. 655-664.

6. Бахвалов Н.С. Численные методы. М.: Наука, 1975. 632 с.

7. Бейтмен Г., Эрдейи А. Высшие трансцендентные функции. Функции Бесселя, функции параболического цилиндра, ортогональные многочлены. М.: Наука, 1974. 296 с.

8. Беленькая О.В., Жилейкин Я.М., Кукаркин А.Б. О вычислении оптимальных коэффициентов квадратурных формул методом полного перебора // Вычислительные методы и программирование. 2003. Т. 4. С. 126-129.

9. Блейхут Р. Быстрые алгоритмы цифровой обработки сигналов. М.: Мир, 1989. 448 с.

10. Боревич З.И., Шафаревич И.Р. Теория чисел. М.: Наука, 1985. 504 с.ИБухштаб А.А. Теория чисел. М.: Учпедгиз, 1960. 376 с.

11. Быковский В.А. Дискретное преобразование Фурье и циклическая свертка на целочисленных решетках // Матем. сб. 1988. Т. 136. № 4. С. 451-467.

12. Васкевич В.Л. Гарантированная точность вычисления многомерных интегралов. Дисс. . докт. физ.-мат. наук. Новосибирск, 2003. 243 с.14. ван дер Варден Б.Л. Алгебра. М.: Наука, 1976. 648 с.

13. Верба М.С., Осипов Н.Н. О воспроизводящих ядрах шара // Журн. вычисл. матем. и матем. физ. 1999. Т. 39. № 2. С. 204 — 207.

14. Войтишек Л. В. О выборе решеток для интегрирования по формулам С. Л. Соболева // Сиб. матем. журн. 1976. Т. XVII. № 4. С. 774-781.

15. Геронимус Я.Л. Многочлены, ортогональные на окружности и на отрезке. М.: Физматгиз, 1958.

16. Даугавет И.К. О постоянных Лебега для двойных рядов Фурье // Методы вычислений. Л.: Изд-во Ленингр. ун-та, 1970. Вып. 6. С. 8 — 13.

17. Даугавет И.К. О представлении некоторых воспроизводящих ядер // Алгебра и анализ. 1999. Т. 11. Вып. 3. С. 53-78.

18. Делоне Б.Н. Геометрия положительных квадратичных форм // Успехи матем. наук. 1937. № 3. С. 16 — 62.

19. Делоне Б.Н., Фаддеев Д. К. Теория иррациональностей третьей степени // Тр. Матем. ин-та АН СССР. 1940. Т. 11. С. 1-340.

20. Добровольский Н.М. Гиперболическая дзета-функция. Деп. в ВИНИТИ, 1984. № 6090-84.

21. Добровольский Н.М., Ванъкова B.C., Козлова С.Л. Гиперболическая дзета-функция алгебраических решеток. Деп. в ВИНИТИ, 1990. № 2327 — В90. 27 с.

22. Дэвенпорт Дж., Сире И., Турнье Э. Компьютерная алгебра. М.: Мир, 1991. 352 с.

23. Ермаков С.М., Михайлов Г.А. Статистическое моделирование. М.: Наука, 1982.

24. Жидков Н.П. Линейные аппроксимации функционалов. М.: Изд-во Мос-ков. ун-та, 1977. 262 с.

25. Касселс Дж. Введение в теорию диофантовых приближений. М.: ИЛ, 1961. 216 с.

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

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

28. Коробов Н.М. О приближенном вычислении кратных интегралов // Докл. АН СССР. 1959. Т. 124. № 6. С. 1207-1210.

29. Коробов Н.М. Вычисление кратных интегралов методом оптимальных коэффициентов // Вестн. Моск. ун-та. 1959. № 4. С. 19 — 25.

30. Коробов Н.М. Теоретикочисловые методы в приближенном анализе. М.: Физматгиз, 1963. 224 с.

31. Коробов Н.М. Теоретико-числовые методы в приближенном анализе. М.: МЦНМО, 2004. 288 с.34.Костприкии А.И. Введение в алгебру. М.: Наука, 1977. 496 с.

32. Кострикин А.И., Манин Ю.И. Линейная алгебра и геометрия. М.: Наука, 1986. 304 с.

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

34. Михайлов Г.А. Оптимизация весовых методов Монте-Карло. М.: Наука, 1987.

35. Михайлов Г.А. Весовые методы Монте-Карло. Новосибирск: Изд-во СО РАН, 2000. 248 с.

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

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

38. Мысовских И. П. О кубатурных формулах, точных для тригонометрических многочленов // Докл. АН СССР. 1987. Т 296. № 1. С. 28-31.

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

40. Мысовских И. П. Алгоритм построения квадратурных формул наивысшей тригонометрической степени точности j j Методы вычислений. Л.: Изд-во ЛГУ, 1991. Вып. 16. С. 5-16.

41. Мысовских И.П. О воспроизводящих ядрах шара и сферы // Журн. вычисл. матем. и матем. физ. 1993. Т. 33. № 6. С. 952-958.

42. Мысовских И. П. Представление воспроизводящего ядра шара // Методы вычислений. СПб.: Изд-во СПбГУ, 1995. Вып. 17. С. 145-152.

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

44. Мысовских И. П. К построению кубатурных формул наивысшей тригонометрической степени точности // Вестник СПбГУ. Сер. 1. 1997. № 22. С. 27—32.

45. Мысовских И. П. О кубатурных формулах, точных для тригонометрических многочленов // Журн. вычисл. матем. и матем. физ. 1998. Т. 38. № 7. С. 1114-1117.

46. Мысовских И. П. Распространение метода воспроизводящего ядра построения кубатурных формул на тригонометрический случай // Методы вычислений. СПб.: Изд-во СПбГУ, 1999. Вып. 18. С. 160-178.

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

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

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

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

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

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

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

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

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

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

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

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

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

60. Осипов Н.Н. О минимальных кубатурных формулах данной тригонометрической точности в 2-мерном случае // Кубатурные ф-лы и их прилож. Уфа: ИМВЦ УНЦ РАН, 1996. С. 52-60.

61. Осипов Н.Н. О семействах минимальных кубатурных формул четной тригонометрической точности в 2-мерном случае // Кубатурные ф-лы и их прилож. Уфа: ИМВЦ УНЦ РАН, 1996. С. 61-63.

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

63. Осипов Н.Н. О воспроизводящих ядрах шара // Вопросы матем. анализа. Красноярск: КГТУ, 1999. Вып. 3. С. 118-128.

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

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

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

67. Осипов Н.Н. Оценка некоторых сумм по n-мерным решеткам // Кубатурные ф-лы и их прилож. Труды VI Междунар. семинара — совещания. Уфа: ИМВЦ УфНЦ РАН, БГПУ, 2002. С. 127-134.

68. Осипов Н.Н. Наилучшие по числу узлов серии решетчатых кубатурных формул, точных на тригонометрических многочленах трех переменных // Кубатурные ф-лы и их прилож. Материалы VII Междунар. семинара — совещания. Красноярск: ИПЦ КГТУ, 2003. С. 111 — 118.

69. Осипов Н.Н. Оценка некоторых сумм по плоским решеткам // Кубатурные ф-лы и их прилож. Материалы VII Междунар. семинара — совещания. Красноярск: ИПЦ КГТУ, 2003. С. 105-111.

70. Осипов Н.Н. Асимптотика нормы функционала погрешности решетчатых кубатурных формул на пространствах W^^ (А) // Вычислительные технологии. 2004. Т. 9. С. 95-101.

71. Осипов Н.Н. Наилучшие по числу узлов серии решетчатых кубатурных формул, точных на тригонометрических многочленах трех переменных // Журн. вычисл. матем. и матем. физ. 2004. Т. 44. № 12. С. 2150-2161.

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

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

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

75. Половинкин В. И. Последовательности кубатурных формул и функционалов с пограничным слоем. Дисс. . докт. физ.-мат. наук. Ленинград, 1979. 240 с.

76. Прудников А.П., Брычков Ю.А., Маричев О. И. Интегралы и ряды. Элементарные функции. М.: Наука, 1981. 800 с.

77. Рамазанов М.Д. Лекции по теории приближенного интегрирования. Уфа: Изд-во БашГУ, 1973. 177 с.

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

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

80. Резцов А.В. Об оценке для числа узлов кубатурных формул гауссова типа // Журн. вычисл. матем. и матем. физ. 1991. Т. 31. N® 3. С. 451 — 453.

81. Рышков С. С. К вопросу о финальной ("-оптимальности решеток, дающих наиплотнейщую решетчатую упаковку n-мерных шаров // Сиб. матем. журн. 1973. Т. XIV. № 5. С. 1065-1075.

82. Рышков С. С., Барановский Е.П. Классические методы теории решетчатых упаковок // Успехи матем. наук. 1979. Т. 34. К2 4. С. 3 — 63.

83. Сегё Г. Ортогональные многочлены. М.: Физматгиз, 1962.

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

85. Соболев C.JI. О формулах механических квадратур на поверхности сферы // Сиб. матем. журн. 1962. Т. III. № 5. С. 769-791.9094