Оценка погрешности экстремальных квадратурных формул на некоторых классах функций тема диссертации и автореферата по ВАК РФ 01.01.07, кандидат физико-математических наук Романов, Марк Анатольевич

• Романов, Марк Анатольевич
• кандидат физико-математических наук
• 2009

Оглавление диссертации кандидат физико-математических наук Романов, Марк Анатольевич

Введение

ГЛАВА 1. Погрешности детерминированных квадратурных формул

1.1. Доказательство нижней оценки

1.2. Доказательство верхней оценки

1.2.1. Одномерный случай

1.2.2. Многомерный случай

ГЛАВА 2. Погрешности случайных квадратурных формул

2.1. Доказательство нижней оценки

2.2. Доказательство верхней оценки

Введение диссертации (часть автореферата) на тему «Оценка погрешности экстремальных квадратурных формул на некоторых классах функций»

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

S = J f(x) dx, а когда функция f(x) задана аналитически и когда может быть найден неопределенный интеграл

J f(x) dx = F(x) + С, производится по формуле ь

S = J f(x) dx = F(b) — F(a). a

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

Пусть D с Ms - некоторая область, C{D) - пространство непрерывных на D функций и / 6 C(D) - некоторая функция. Для вычисления интеграла пользуются приближенной формулой, называемой квадратурной:

Г N

D k=1 3

Здесь (1о(х) - некоторая мера; обычно предполагают, что существует плотность меры йа{х) = ю(х) йх, где с1х - мера Лебега. Точки е И (к — 1,2,., АГ) называются узлами, а числа А& - весами квадратурной формулы. Набор назовем сеткой квадратурной формулы. Всегда будем требовать, чтобы

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

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

0.2)

0.3)

Начиная с конца XVII века в работах основоположников и создателей анализа бесконечно малых интегрирование сформировалось как важнейшее понятие математического анализа. Параллельно развитию теории интегрирования создавался и совершенствовался аналогичный по своему назначению аппарат численного анализа (аппарат именно аналогичный, но не тождественный). Нет сомнения, что римановские интегральные суммы были исходными при возникновении теории квадратурных формул. Именно желание получить приближенную формулу для вычисления интеграла, максимально точную при наименьшем числе узлов, и привело к созданию теории квадратурных формул. Как результат эволюции этой математической ветви возникли и получили широкую известность квадратурные формулы Ньютона - Котеса, Эйлера - Маклорена, Грегори, Гаусса, Симпсона, Чебышева, Маркова и др. К концу прошлого XX века теория квадратурных формул сложилась из нескольких главных ветвей. Вот что писал по этому поводу в 1972 г. академик С. Л. Соболев: «Работы по теории квадратурных формул относятся к различным направлениям. В одном из них, в продолжение классических исследований Радона, отыскиваются формулы, которые могли бы точно интегрировать возможно большее число из данного набора функций, например, многочленов или тригонометрических функций. . Второе направление — направление вероятностных методов Монте-Карло. Здесь проблема состоит в том, чтобы построить алгоритмы не вполне случайные, основанные на некотором регулярном выборе случайных точек. Наконец, третье направление касается изучения формул, использующих в качестве узлов точки правильной решетки. Здесь удается сравнительно далеко продвинуться в изучении нормы функционала погрешности в различных функциональных пространствах, и, в частности, для пространств с ортогонально инвариантной нормой найти зависимость погрешности от решетки».

Функциональные методы стали широко применяться в теории приближенного интегрирования начиная с работ академика С. М. Никольского и первого издания его книги «Квадратурные формулы» [18]. Изложенные в ней результаты относятся, в основном, к квадратурным формулам на класг) сах функций одной переменной. Создание же теории квадратурных формул для функций многих переменных заслуженно связывают с исследованиями академика С. Л. Соболева. В научном наследии С. Л. Соболева работы по теории приближенного интегрирования, выполненные им в «сибирский» период жизни, занимают весьма заметное место: первую работу по кубатурным формулам он опубликовал в 1961 г., последнюю — в 1986 г., всего же их более трех десятков, в том числе фундаментальная монография [23].

Функциональный подход к исследованию формул для приближения многомерных интегралов предполагает, во-первых, использование выбранной или построенной формулы не для какой-то одной конкретной функции, а сразу для целого их семейства, представляющего собой шар в некотором наперед заданном банаховом пространстве Ш.

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

В-третьих, исходное банахово пространство Ш предполагается непрерывно вложенным в пространство С {В) функций, непрерывных в замыкании области интегрирования Б. В этом случае функционал погрешности квадратурной формулы ограничен на Ш, его норму в сопряженном пространстве Ш* называют погрешностью этой квадратурной формулы на Ш1. Знание численной мажоранты для этой погрешности позволяет получать для произвольной функции из единичной сферы пространства Ш гарантированные оценки близости истинного значения интеграла от этой функции к рассматриваемой на ней квадратурной сумме.

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

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

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

2. Для заданного банахова пространства Ш найти асимптотическое разложение погрешности квадратурной формулы на Ш по числу узлов N — важнейшему параметру вычислительного процесса. Вывести эффективные двусторонние оценки для указанной погрешности в виде явных функций от N.

3. Для заданных банахова пространства Ш и числа узлов N найти оптимальную квадратурную формулу, т.е. такую формулу, погрешность которой на Ш минимальна при данном причем минимум берется по всем сеткам квадратурных формул, т.е. по всем узлам и весам. Получить 7 точную оценку оптимальной погрешности. Подобного рода задачи называются экстремальными задачами теории квадратурных формул, их постановка восходит к А. Н. Колмогорову. Качество построенной формулы обычно оценивают сравнением ее погрешности с нижней оценкой для погрешностей любых квадратурных формул на 9Л с тем же числом узлов N. Отыскание и исследование оптимальной квадратурной формулы и получение точной оценки ее погрешности становится особенно сложной задачей в многомерном случае для классов функций, встречающихся в приложениях (например, в вычислительных задачах математической физики), требующей привлечения глубоких и точных фактов теории функций, функционального анализа, теории чисел и т.д.

Другое направление в теории квадратурных формул составляют вероятностные методы типа Монте-Карло, которые при вычислении многомерных интегралов часто оказываются эффективнее детерминированных квадратурных формул. В рамках этого направления рассматриваются недетерминированные (вероятностные) квадратурные формулы, сетки которых являются вектор-функциями на некотором вероятностном пространстве. Систематическое изучение таких формул началось в 60-х годах прошлого столетия и связано в основном с работами Н. С. Ба-хвалова (например, [3]-[6]). В качестве примера приведем следующую задачу.

4. Пусть на вероятностном пространстве I/ с мерой ¡1 задано некоторое семейство сеток с фиксированным числом узлов И, узлы и веса ко/ торых — функции случайного параметра £ € V. В этом случае погрешность соответствующей квадратурной формулы на заданном банаховом пространстве Ш является случайной величиной. Требуется указать двусторонние оценки в зависимости от N для статистических характеристик этой случайной величины (математического ожидания, дисперсии, моментов и др.). По аналогии с задачей 3 построить такое вероятностное 8 пространство U и семейство сеток при которых указанные характеристики минимальны, и получить двусторонние оценки минимумов этих характеристик.

В качестве исходного банахова пространства Ш на практике выбираются самые разнообразные классы функций. Разные авторы рассматривали квадратурные формулы в пространствах Соболева (изотропных и неизотропных, конечного и бесконечного порядков), Бесова, Никольского, в классах Гельдера, пространствах с доминирующей смешанной производной, весовых функциональных пространствах и др. В данной работе приняты следующие обозначения:

1. s-мерный тор TP = Rs/Zs.

2. Для х = Oi,., х8), у = (2/ь ., у3) Е Rs s ¿=1 обычное скалярное произведение.

3. Символы Виноградова <С и Запись X <С Y при Y > 0 означает, что найдется константа С > О, такая что \Х\ ^ С -Y. Аналогично при 0 и Y > 0 определяется символ Символы <С и означат ют, что соответствующие константы в определениях зависят только от указанных под знаком параметров.

4. Запись X х У, где Y > 0, означает, что

Символ х определяется аналогично предыдущему пункту. aß,.

5. Знак суммы со штрихом означает, что при суммировании слагаемое пет,3 с номером п = (0,., 0) опускается.

6. к = тах{1, \к\}.

7. — число элементов конечного множества М. 9

8. — конечная разность <назад» порядка к по переменной у\

А°иаи = аи, Аиар = а„ - = ДуД*-1^.

9. [х] — целая часть х.

10. Если Л — функционал на функциях одной переменной, то запись ■)) или Я(/(-, у)) обозначает результат действия этого функционала на функцию / нескольких переменных по переменной, указанной точкой.

11. ии = Т2".

В дальнейшем нас будет интересовать случай, когда в равенстве (0.3) da(х) = dx — мера Лебега. С помощью замен переменных и различных методов периодизации (см. [13], гл. 3, §3.2) задача вычисления интеграла сводится к случаю, когда функция / периодична по каждой переменной с периодом 1. Другими словами, функции рассматриваются на торе Ts.

Пусть Ш с C(TS) — некоторое пространство функций с нормой || • ||. Через &S(N) обозначим множество всех сеток с N узлами ., х^ еГи соответствующими им весами Ai,., A ¡v Е R, удовлетворяющими, согласно требованию (0.2), условию нормировки Ai Н-----1- Адг = 1.

В соответствии с описанным выше функциональным подходом, для функции / € Ш формальное равенство N

J f{x) dx = Y, Akf(x{k)) + /) (0.4) называется квадратурной формулой для сетки П. Ее погрешность Я(Г2] /) — линейный функционал на с нормой

R(Q\ Ш) = sup \R(f2-,f)\, ll/ll=i которая называется погрешностью сетки Q на Ш.

Одной из задач данной работы является оценка оптимальной погрешности им(щ= inf ШП]Ж). i2€6s{N) 4

Далее, пусть на вероятностном пространстве U с мерой /л задано некоторое отображение Q : U —&S(N). Для функций / G положим

D(U,Q;ffl) = sup [ f \R(Q{0-,f)\2diJ,(0 ll/ll=i \J

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

Рассматривая пространства и, состоящие ровно из одной точки, немедленно получаем неравенство

Кроме того,

Ял^ШГ) < Я^Ш),

0.5) оН1{ж) ^ Ш) при N1 ^ ./V", поскольку погрешность квадратурной формулы не меняется при добавлении новых узлов с нулевыми весами.

Порядок по N величин и Ду(!$Т) существенно зависит от дифференциальных свойств функций из ШТ. Поэтому, как правило, классы функций выделяют путем ограничения производной заданного порядка в той или иной норме. Наиболее хорошо изучен класс с р е [1, ос) и а > состоящий из 1-периодических функций вида f(x) = I ip(y)Fa(x - у) dy

Ts с конечной нормой

Здесь ад = Е pdx exp(27ri(n, х))

На(п) и Н(п) = rii. ,ns с щ = max{l, \rij\}. Для оптимальной погрешности на

J1 н этом классе при а > тах < - > известна двусторонняя оценка

2 рJ

Ч^Ь^' (0,)

Верхняя оценка непосредственно следует из результатов К. К. Фролова [25] при р £ [2, оо) и М. М. Скриганова [21] при р е (1, 2). Методы доказательства нижней оценки при любых р е (1,оо) были предложены в работах В. А. Быковского [8], [9] и В.Н. Темлякова [24].

Для второй из сформулированных выше задач Н. С. Бахвалов в работе [5] доказал оценку ад^СГ)) « < к ; лга+1- при ре [1,2],

1оё ЛО^-1)^1^ при р е (2, оо).

1 1

Пусть для р £ [1, оо] число д 6 [1, оо] определяется из условия - + - = 1, 1 и а >--вещественное. В настоящей работе сформулированные выше Я задачи будут изучаться для класса Ер*\Т5), состоящего из функций вида м = £ (* € Г) с последовательностью с = {с(п)}пе^ с С и конечной полунормой

11/11 ник = (Е^мп

Таким образом, в отличие от И^СГ), функции из класса характеризуются скоростью убывания их коэффициентов Фурье. В силу равенства Парсеваля при р = 2 и натуральных а эти классы совпадают.

Класс при р = оо (в литературе используется обозначение Е") был введен Н. М. Коробовым в работе [12], в которой была доказана верхняя оценка оптимальной погрешности й„(£<?>(Г))<<М^. (о.7)

Позднее И. Ф. Шарыгин [26] получил нижнюю оценку

Оценка (0.7) уточнялась Н. С. Бахваловым [4]; в окончательном виде с показателем логарифма 5 — 1 ее получил К. К. Фролов [25]. Тем самым был установлен правильный (с точностью до констант) порядок величины (е{£\Т5)). Позднее В. Ф. Лев [17] распространил этот результат на все р 6 [2, оо] в виде отметив при этом, что вопрос о правильном порядке оптимальной погрешности при р € (1,2) остается открытым. В дополнение к этому результату, в первой главе доказываются следующие две теоремы. теорема 1. Для всехр £ (1,2) и натуральных в, N > 1 выполняется оценка я* (^>(Г)) » а,р,з ДГа+2 д теорема 2. Для всех р е (1,2) и натуральных в, N > 1 выполняется оценка я /»гт-Л «Г ('ое^)'5"1'^1"')

14

По поводу величины Ду во второй главе получены следующие результаты. теорема 3. Для всех натуральных в и N > 1 справедлива оценка О N при р е (1,2], < к^лр^Кн) при р € (2, оо).

Теорема 4. Для всех натуральных в и N > 1 справедлива оценка Б лг < а,р,з к^Ар^М)

ТУ")^-1^ (а+р+1) при ре{ 1,2], при р Е (2, со).

Сравнение теорем 1, 2 и 3, 4 показывает, что полученные оценки точны степенной шкале и отличаются от наилучших только логарифмическими множителями.

Список литературы диссертационного исследования кандидат физико-математических наук Романов, Марк Анатольевич, 2009 год

1. Ахиезер Н. И. Лекции по теории аппроксимации / Н. И. Ахиезер. — М.: Наука, 1965.

2. Бабенко К. И. Основы численного анализа / К. И. Бабенко. — М.: Наука, 1986. 744 с.

3. Бахвалов Н. С. Оценка в среднем остаточного члена квадратурных формул / Н.С. Бахвалов // Журнал вычислит, математики и матем. физики. 1961. - Т. 1. - № 1. - С. 64-77.

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

5. Бахвалов Н. С. О скорости сходимости недетерминированных квадратурных процессов на классах функций Шр^ /Н.С. Бахвалов. / / Теория вероятностей. — Т. VII. — Вып. 1-2(2).

6. Быковский В. А. Теоретико-числовые решетки в эвклидовых пространствах и их приложения: Дис. . д-ра физ.-матем. наук / В. А. Быковский; Хабаровское отделение ИПМ ДВО РАН. — Хабаровск, 1990.- 117 с.

7. Быковский В. А. Оценки отклонений оптимальных сеток в £р-норме и теория квадратурных формул / В. А. Быковский // Препринт № 02 / Институт прикладной математики ДВО РАН. — Владивосток: Дальна-ука, 1985. — 19 с.

8. Быковский В. А. Квадратурный фазовый переход / В. А. Быковский, М.А. Романов // Доклады Академии наук. — 2007. — Т. 416, № 6. С. 727-731.

9. Корнейчук Н. П. Экстремальные задачи теории приближения / Н. П. Корнейчук. — М.: Наука, 1976.

10. Коробов Н. М. О приближенном вычислении кратных интегралов с помощью методов теории чисел / Н. М. Коробов // Доклады Академии наук СССР. 1957. - Т. 115, № 6. - С. 1062-1065.

11. Коробов Н. М. Теоретико-числовые методы в приближенном анализе / Н.М. Коробов. М.: МЦНМО, 2004. - 288 с.

12. Кронрод A.C. Узлы и веса квадратурных формул / A.C. Кронрод.- М.: Наука, 1964.

13. Крылов А. Н. Лекции о приближенных вычислениях / А. Н. Крылов.- 6-е изд. М.: ГИТТЛ, 1954. - 400 с.

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

15. Лев В. Ф. О квадратурных формулах для классов с ограничениями на коэффициенты Фурье / В.Ф. Лев // Математические заметки. — 1991. Т. 49, вып. 2. - С. 144-147.

16. Никольский С. М. Квадратурные формулы / С. М. Никольский. — 2-е. изд. — М.: Наука, 1974. — 224 с.

17. Романов М. А. О погрешности многомерных квадратурных формул на некоторых классах функций / М.А. Романов // Математические заметки. 2009. — Т. 85, вып. 3. — С. 433-439.

18. Романов М. А. О погрешности случайных квадратурных формул на некоторых классах функций / М.А. Романов // Дальневосточный математический журнал. — 2007. Т. 7, № 1-2. - С. 91-100.

19. Skriganov М. М. Constructions of uniform distributions in terms of geometry of numbers / M. M. Скриганов // Алгебра и анализ. — 1994. — Т. 6, № 3. С. 200-230.

20. Смоляк С. А. Квадратурные и интерполяционные формулы на тензорных произведениях некоторых классов функций / С. А. Смоляк // Доклады Академии наук СССР. 1963. - Т. 148, № 5. - С. 1042-1045.

21. Соболев С. Л. Введение в теорию кубатурных формул / С. Л. Соболев. — М.: Наука, 1974.

22. Темляков В. Н. Об одном приеме получения оценок снизу погрешностей квадратурных формул / В.Н. Темляков // Математический сборник. 1990. - Т. 181, № 10. - С. 1403-1413.

23. Фролов К. К. Квадратурные формулы на классах функций: Дис. . канд. физ.-матем. наук / К. К. Фролов; ВЦ АН СССР. — М., 1979.

24. Шарыгин И. Ф. Оценки снизу погрешности квадратурных формул на классах функций / И. Ф. Шарыгин // Журнал вычислительной математики и математической физики. — 1963. — № 3. — С. 370-376.