Некоторые теоретико-числовые методы приближенных вычислений тема автореферата и диссертации по математике, 01.01.06 ВАК РФ
|
Ребров, Евгений Димитриевич
АВТОР
|
||||
|
кандидата физико-математических наук
УЧЕНАЯ СТЕПЕНЬ
|
||||
|
Москва
МЕСТО ЗАЩИТЫ
|
||||
|
2013
ГОД ЗАЩИТЫ
|
|
01.01.06
КОД ВАК РФ
|
||
|
|
||||
МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ имени М.В. ЛОМОНОСОВА
РЕВРОВ Евгений Дмитриевич
На правах рукописи УДК 511.3
НЕКОТОРЫЕ ТЕОРЕТИКО-ЧИСЛОВЫЕ МЕТОДЫ ПРИБЛИЖЕННЫХ ВЫЧИСЛЕНИЙ
01. 01. 06. — математическая логика, алгебра и теория чисел
АВТОРЕФЕРАТ
диссертации на соискание ученой степени кандидата физико-математических наук
1 6 МАЙ 2013
005058427
Москва — 2013
005058427
Работа выполнена на кафедре теории чисел математического факультета ФГБОУ ВПО "Московский педагогический государственный университет"
Научный руководитель: доктор физико-математических наук,
профессор Добровольский Николай Михайлович
Официальные оппоненты: Гриценко Сергей Александрович
доктор физико-математических наук, профессор, заведующий кафедрой алгебры, теории чисел и геометрии ФГАОУ ВПО «Белгородский государственный национальный исследовательский университет»
Шутов Антон Владимирович кандидат физико-математических наук, доцент, доцент кафедры информатики и вычислительной техники ФГБОУ ВПО «Владимирский государственный университет имени А.Г. и Н.Г. Столетовых»
Ведущая организация: ФГБОУ ВПО "Тульский государственный университет"
Защита состоится 31 мая 2013 г. в 16 ч. 45 мин. на заседании диссертационного совета Д.501.001.84 при Московском государственном университете имени М. В. Ломоносова по адресу: 119991, г. Москва, Ленинские горы, д. 1, Механико-математический факультет МГУ, ауд. 1408. С диссертацией можно ознакомиться в Фундаментальной библиотеке Московского государственного университета имени М. В. Ломоносова. Автореферат разослан 30 апреля 2013 г.
Ученый секретарь диссертационного совета Д.501.001.84 при МГУ, доктор физико-математических наук, профессор Иванов Александр Олегович
ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ
Актуальность темы диссертации. Диссертация посвящена исследованию теоретико-числовых алгоритмов численного интегрирования периодических функций многих переменных. Рассматривается актуальная задача получения оценок мультипликативной дисперсии концентрических алгоритмов численного интегрирования.
Исследование теоретико-числовых алгоритмов численного интегрирования, интерполирования, решения уравнений с частными производными и линейных интегральных уравнений на классах периодических функций - это современная отрасль теоретико-числового метода в приближенном анализе, ей посвящены многочисленные современные работы известных ученых, таких как, Н. М. Коробов р,2, 3, 4,5, 6, 7], Н. Н. Чен-цов [8], Н. С. Бахвалов [9,10], В. А. Быковский [п, 12, 13,14,15], С. М. Во-
'Коробов Н. М. Приближенное вычисление кратных интегралов с помощью методов теории чисел // ДАН СССР. 1957. N б. С. 1062 - 1065.
2Коробов Н. М. Вычисление кратных интегралов методом оптимальных коэффициентов // Вестн. Моск. ун-та, 1959. N 4. С. 19 — 25.
3Коробов Н. М. О приближенном вычислении кратных интегралов // ДАН СССР. 1959. Т. 124, N 6. С. 1207 - 1210.
4 Коробов Н. М. Свойства и вычисление оптимальных коэффициентов // ДАН СССР. 1960. Т. 132. N 5. С. 1009—1012.
5Коробов Н. М. Теоретико-числовые методы в приближенном анализе. М.: Физматгиз, 1963.
6Коробов Н. М. Квадратурные формулы с комбинированными сетками // Математические заметки. 1994. Т. 55. Вып. 2. С. 83 - 90.
7Коробов Н. М. Теоретико-числовые методы в приближенном анализе, (второе издание) М.: МЦНМО, 2004.
8Гельфанд И. М. Применение метода случайных испытаний (метода Монте-Карло) для решения кинетического уравнения / И. М. Гельфанд, С. М. Фейнберг, А. С. Фролов, Н. Н. Ченцов // Тр. II Международной конференции по мирному использованию атомной энергии (Женева, 1958, Доклад 2141), - М.: Атомиздат, 1959. - Т. 2. - С. 628-633.
9Бахвалов Н. С. О приближенном вычислении кратных интегралов // Вестн. Моск. ун-та, 1959. N 4. С. 3-18.
'"Бахвалов Н. С., Коробов Н. М., Ченцов Н. Н. Применение теоретико-числовых сеток к задачам приближенного анализа // Труды Четвертого Всесоюзного математического съезда. Л.: Наука, 1964. Т. II. С. 580 - 587.
"Быковский В. А. О правильном порядке погрешности оптимальных кубатурных формул в пространствах с доминирующей производной и квадратичных отклонениях сеток. Владивосток: ВЦ, 1985. (Препринт.)
12Быковский В. А. Экстремальные кубатурные формулы для анизотропных классов. Хабаровск,
1995. С. 1-13. (Препринт.)
13Быковский В. А. Дискретное преобразование Фурье и циклическая свертка на целочисленных
решетках // Математический сборник, 136(178), 4(8), 1988, С. 451 — 467.
"Быковский В. А. Оценки отклонений оптимальных сеток в Ьр-норме и теория квадратурных формул. // Analysis Mathematica, 22(1996), pp. 81 — 97.
15Быковский В. А.Теоретико-числовые решетки в эвклидовых пространствах и их приложения.
ронин [16, 17, "], э. Главка [и], Хуа Ло Кен, Вань Юань [20] и многих других.
Однако, оценкам мультипликативной дисперсии концентрических алгоритмов численного интегрирования было посвящено относительно мало работ и здесь остается ряд нерешенных задач.
Диссертация относится к аналитической теории чисел. В ней рассматриваются вопросы численного интегрирования периодических функций многих переменных по системе квадратурных формул с парралелепипе-дальными сетками, построенных по алгоритму JT. П. Добровольской.
Даются оценки мультипликативной дисперсии для концентрических алгоритмов численного интегрирования, основанных на указанных сетках, на классах Е".
Построен концентрический алгоритм численного интегрирования с использованием алгебраических ссток с весами по методу К. К. Фролова в модификации Н. М. Добровольского и для случая s = 4 аналога точной параметризации А. С. Герцога алгебраических сеток для модифицированных алгебраических сеток.
Цель и задачи диссертационной работы. Целью работы является создание и развитие аппарата, позволяющего получать оценки мультипликативной дисперсии концентрических алгоритмов численного интегрирования, величина которой является основой правил остановки алгоритмов интегрирования. Поэтому в диссертационном исследовании были поставлены следующие задачи:
1. Построить алгоритм численного интегрирования с правилом остановки для периодических функций многих переменных по системе квадратурных формул с парралелепипедальными сетками и его программную реализацию в системе Mathcadlö. Алгоритм будет строится для системы сеток, являющейся концентрической совокупностью параллелепипедальных подсеток параллелепипедальной
Дис....док. физ.-мат. наук. Хабаровск. ИПМ ДВО АН СССР, 1990.
"Воронин С. М. О квадратурных формулах // Изв. РАН. Сер. мат. 1994. Т. 58. N 5. С. 180-194.
"Воронин С. М. О построении квадратурных формул // Изв. РАН. Сер. мат. 1995. Т. 59. N 4.
''Воронин С. М., Темиргалиев Н. О квадратурных формулах, связанных с дивизорами поля гауссовых чисел // Мат. заметки. 1989. Т. 46. N 2. С. 34—11.
19 Hlawfca Е. Zur angenäherten Berechnung mehrfacher Integrale // Monatshefte für Math. 66, 2 1962 P. 140-151.
20Hua Loo Keng, Wang Yuan Applications of Number Theory to Numerical Analysis, - SpringerVerlag Berlin, 1981.
сетки 5, вычисленной по алгоритму Л. П. Добровольской р1].
2. Построить алгоритм численного интегрирования с правилом остановки для периодических функций многих переменных по системе квадратурных формул с алгебраическими сетками и его программную реализацию в системе МаЛсас115.
3. Построить алгоритм и его программную реализацию точной параметризации модифицированных алгебраических сеток.
Научная новизна. Впервые получены теоретические результаты, относящиеся к оценкам мультипликативной дисперсии концентрических алгоритмов численного интегрирования. Предложены алгоритмы с правилом остановки, позволяющие учитывать промежуточные результаты, соответствующие приближённому значению интеграла, рассчитанные по подсеткам.
На защиту выносятся следующие основные результаты:
• новые оценки мультипликативной дисперсии концентрических алгоритмов численного интегрирования для параллелепипедальных сеток с оптимальными коэффициентами, рассчитанными по алгоритму Л. П. Добровольской;
• новые оценки мультипликативной дисперсии концентрических алгоритмов численного интегрирования для алгебраических сеток;
• точная параметризация для модифицированных алгебраических сеток.
Все выносимые на защиту результаты являются новыми и получены самостоятельно.
Основные методы исследования. В работе используются теоретико-числовые методы в приближенном анализе и методы аналитической теории чисел.
Теоретическая и практическая ценность. Результаты работы имеют теоретический характер и будут полезны для развития как теоретико-числового метода в приближенном анализе, так и в практике разработки эффективных реализаций алгоритмов численного интегрирования функций многих переменных.
21 Бочарова Л. П. Алгоритмы поиска оптимальных коэффициентов // Чебышевский сборник 2007 Т. 8. Вып. 1(21). Тула, Из-во ТГПУ им. Л. Н. Толстого. С. 4 - 109.
Апробация результатов. Результаты диссертации докладывались
на:
научно-исследовательском семинаре "Теоретико-числовые методы в приближенном анализе" профессора H. М. Добровольского в ТГПУ им. JI. Н. Толстого (г. Тула, неоднократно с 2009 по 2012 г.);
Международной научной конференции "Современные проблемы математики, механики, информатики" (г. Тула, 2008 г.);
VII Международной конференции "Алгебра и теория чисел: современные проблемы и приложения, посвященной памяти профессора Анатолия Алексеевича Карацубы" (г. Тула, 2010 г.);
Международной научно-практической конференции "Многомасштабное моделирование структур и нанотехнологии, посвященной 190-летию со дня рождения академика Пафнутия Львовича Чебышёва, столетию со дня рождения академика Сергея Васильевича Вонсовского и 80-летию со дня рождения член-корреспондента Виктора Анатольевича Бурави-хина" (г. Тула, 2011 г.);
X Международной конференции "Алгебра и теория чисел: современные проблемы и приложения" (г. Волгоград, 2012 г.);
Международной конференции "Computer Algebra and Information Technology" (г. Одесса, Украина , 2012 г.)
Диссертация подготовлена в рамках выполнения проектов РФФИ: гранты №08-01-00790_а, №11-01-00571а.
Публикации. Основные результаты по теме диссертации опубликованы в 5 работах, в том числе публикации [1,2] — в изданиях, включенных в перечень ВАК.
Структура и объем диссертации. Диссертационная работа состоит из введения, трех глав, разбитых на 22 раздела, заключения и списка литературы. Материал изложен на 147 страницах машинописного текста, включая 3 рисунка. Библиография содержит 62 наименования.
СОДЕРЖАНИЕ РАБОТЫ
Нумерация теорем в автореферате соответствует нумерации, приводимой в диссертации.
Во введении обосновывается актуальность темы диссертационного исследования, дается краткий исторический обзор результатов, полученных ранее и связанных с тематикой диссертационной работы, формулируются основные результаты диссертации.
Первая глава — "Численное интегрирование с правилом остановки" (стр. 20 — 79) — посвящена полному изложению основ теории численного интегрирования с правилом остановки. Здесь используются результаты работы [22], но многие формулировки теорем и определений уточнены и даны в более общей ситуации.
Доказаны следующие новые основные результаты.
Два варианта обобщенного интегрального критерия Г. Вейля:
ТЕОРЕМА 3. (стр. 21) Для бесконечной возрастающей последовательности натуральных Nj с lim Nj = оо последовательность се-
j'-toо
ток с положительными весами (M(j), p(j)) из Nj взвешенных узлов образует равномерно распределенную в единичном s-мерном кубе последовательность взвешенных узлов тогда, и только тогда, когда для любой ограниченной, интегрируемой по Риману периодической с периодом 1 по каждой переменной функции f(x) справедливо равенство
Nj *! 1
Дт ^r pj,kf{xj,k) = "J...J f{x)dx.
3 k=l 0 0
ТЕОРЕМА 4. (стр. 24) Для бесконечной возрастающей последовательности натуральных Nj с lim Nj = оо последовательность сеток
j-t 00
с ограниченными весами (M(j), p{j)) из Nj взвешенных узлов образует равномерно распределенную в единичном s-мерном кубе последовательность взвешенных узлов тогда, и только тогда, когда для любой непрерывной или кусочно-постоянной периодической с периодом 1 по каждой переменной функции f(x) справедливо равенство
Nj il
Дт ~N- Й = / • /
J fc=1 0 0
Первая обобщенная теорема H. М. Коробова:
ТЕОРЕМА 5. (стр. 27) Пусть ряд Фурье функции f(x) сходится абсолютно, С (in) — ее коэффициенты Фурье и Su,p(jn) — тригономет-
22Добровольская Л. П., Добровольский H. М., Симонов А. С. О погрешности приближенного интегрирования по модифицированным сеткам // Чебышевский сборник. Т. 9. Вып. 1(25). Тула, Изд-во ТГПУ им. Л. Н. Толстого, 2008. С. 185 - 223.
рические суммы сетки с весалш, тогда справедливо равенство
\ 1 00'
RN[f] = С(0) - 1) + - C(m)SM,7(rn) =
оо
= С(б) (s;fj0) - l) + C(m)S¡f¡ií(m).
Если веса положительные или ограниченные, то при N ->• оо погрешность
Rn[A будет стремиться к нулю тогда, и только тогда, когда взвешенные узлы квадратурной формулы равномерно распределены в единичном s-мерном кубе.
Оценки мультипликативной дискретной дисперсии погрешности приближенного интегрирования по квадратурной формуле с различными типами сеток:
ТЕОРЕМА 9. (стр. 58) Для D"M г[/(£)] — мультипликативной дискретной дисперсии погрешности приближенного интегрирования по квадратурной формуле с равномерной сеткой Ms(Nk) произвольной функции f{x) € Ef справедлива оценка
Теорема 11. (стр. 64) Для И'м ((р] Рк)] г[/(я)] - мультипликативной дискретной дисперсии погрешности приближенного интегрирования по квадратурной формуле с обобщенной неравномерной сеткой М8{(рх,... ,Рк)) произвольной функции /(£) 6 справедлива оценка
Далее рассматривается алгоритм Добровольской вычисления оптимальных коэффициентов. Алгоритм вычисления величин ..., ап проводится последовательно, исходя из соотношений:
Если ask, as-u,a(jl,y уже определены, то aju находится из условий | 1 ^ aj„ < р„ - 1,
I - ^T^iiz). (2)
Так как минимальное значение не больше среднего арифметического, непосредственно из определения величин аак, а8_1ь ■■■ ,ац вытекает цепочка неравенств
Для всех функций тЦ'д(г) и величины в работе [21] получены явные формулы, которые пригодны для программной реализации. Пусть
Доказывается следующий новый, основной результат.
Теорема 17. (стр. 78) Если величины оь..., а3 заданны формулами (1, 2, 4), то они являются оптимальными коэффициентами по модулю N индекса в и для мультипликативной дискретной дисперсии £)^[/(х)] параллелепипсдальной сетки М = Млг(а1,..., а3) справедливы оценки
N1 =Рк, N2 =РкРк-1, ■ =Рк-...'Р2, N = Мк = Рк • ■ ■ ■ -Р1-
Во второй главе — "Квадратурные формулы с модифицированными алгебраическими сетками" (стр. 80 — 126) — исследуется новый класс квадратурных формул — квадратурные формулы с модифицированными алгебраическими сетками.
Пусть а = (а0, аь ..., а8_1) — целочисленный вектор, такой что мно-
тГ(ап) < Т<$(а12) < .. • < Т^Ы) < (3)
где
гочлен
8-1
1/=0
неприводим над полем рациональных чисел и все корни © //
(г/ = 1,... ,5)
многочлена (5) действительные.
( 1 . 1
Т(а) = ©1 - .. е.
• ©г1
Обозначим через Т(а) матрицу степеней алгебраически сопряженных целых алгебраических чисел ©!,...,©,,— корней многочлена Рз(х):
(6)
а через © = (©i,..., ©„) — вектор полного набора алгебраически сопряженных чисел — корней многочлена Ps{x). Напомним, что
\г(а) = \\Т(а)\и = max I©/ + ... + |©/, Л2(а) = ||Т(а)||2 = ^max^l + |0„| + ... + 1©^!) = \\ТТ{а)\\и
где Тт — транспонированная матрица к матрице Т. Тогда параллелепипед
ВД) = 11t„iXi + ... + tvaxs\ s$ | {у = 1,..., s) | , задаваемый матрицей
Тх=Г1(3) =
■Т(а),
2||Г(3)||1 содержит в—мерный куб
К.= {х I \х„\ <1, I/ = 1, . . . , 5} = {X | ЦхЦ! ^ 1},
где ¡|£|[х = ^тах^ \хи\, поскольку ||Т(а) ■ гЦх < ||Г(а)||1 • ||х||ь то есть
тех 16*®! + ... + ^ 1©!^ + ... + 10,1", (А; = 0,1,... ,5 - 1). Решётка Л(Г(а)) называется алгебраической. Она имеет вид
(7)
А(г(о)) = \х = ( J2 ©Г™,. • • •, £ e>„
Так как координаты любой ненулевой точки х 6 Л(Т(а)) — алгебраически сопряженные целые алгебраические числа, то произведение ху.. .-х3 — ненулевое целое рациональное число.
Доказаны следующие новые основные результаты.
ТЕОРЕМА 19. (стр. 104) Если в „(и = l,...,s) - действительные корпи неприводимого многочлена
3-1
Pa{x) = avx" + xs i/=0
с целыми коэффициентами, матрица Т = Т{а) и а - действительное число больше единицы, то для обобщенной гиперболической дзета-функции сдвинутой решетки (н (qQA.(T) 4- Qm • Т|а) справедлива оценка:
<н (qQMT) + Qm ■ Т\а) ^ < (б5 ■(-+!) (SaiS~l^Q + 3log2(A2(T)) + 2
( 1 ^ 3q2«+a-1 / 1 V/ С(а)У"г\ 1 Л1 + (а - 1)«"7 + (<* - l)A(T)-1 V + <?А(Т)) V <7° ) J Qsa'
где А2(Т) = max (1 + |©„| + ... + |©t_1|) > s.
ТЕОРЕМА 20. (стр. 108) Пусть параллелепипед ПДТ) содержит куб Ks и z 6 Rs. Тогда погрешность квадратурной формулы i i
[■■■[ f{x)dx = (det^AÍT)))-1 X) ~ д^'(«(А(Т)),»-)[/1
6 5 SeM'(q(A(T)),z¡
на классе функций Е"{С), (1 < а < г) с весовой функцией р(х) порядка г с константой В удовлетворяет оценке
RN'(q[MT)),¡)lEs{C)]= SUP |Длг'(«(Л(т)),г)[/]| < /е£Г(С)
^ С ■ В - (2 (1 + СИ) + (1 + 2С(а)) 2аУ Ся(дЛ(Г)|а).
ТЕОРЕМА 21. (стр. 115) Пусть 6„,(г/ = l,...,s), действительные корни неприводимого многочлена
S—1
Ра(х) = ^а^+х*
v=0
с целыми коэффициентами.
Пусть, матрица Т = Т{а) задана соотношением (6), матрица Т\ — равенством (7), и 1 < а < г.
Тогда для правила остановки А концентрического алгоритма приближенного интегрирования порядка г ^ 2 по квадратурным формулам i i
[—[ f(x)dx = (det (QjMTia))))"1 £ Plf(x) - RN.[QjMT{S)))[f]
о 0 x€M'(QJA(T(3)))
на классе функций E"{C), (1 < a < г) с весовой функцией p{x) порядка г с константой В справедлива оценка
ДЛГ'ШЛ(Т})) (С)} = SUP I^JV'(Oí(A(T)))[/]l <
}еЕ«(с)
^ С2 ■ В2\det Т\ ■ (2 (1 + СИ) + (1 + 2С(а)) 2u)2s • ?? Л« / , ^5а(а — 1) log2 Qj-i 48-1
ßS. {s + 1} + slog2(A2(T)) + 2y
gjln^Q,-!4
sct2s+a~ (a - 1)A(T)°
= o
Qj-i
Кроме этого в последнем разделе второй главы предложено решение проблемы точной параметризации модифицированной алгебраической сетки биквадратичного поля [\/2 + .
Третья глава (стр. 127 — 136) посвящена программной реализации алгоритмов численного интегрирования с правилом остановки для па-раллелепипедальных и алгебраических сеток.
Во-первых, в этой главе дается простая программа вычисления оптимальных коэффициентов для простого модуля по координатному алгоритму Коробова. Далее дается обоснование этого алгоритма для случая произвольного составного модуля.
Во-вторых, приводится программная реализация алгоритма Добровольской вычисления оптимальных коэффициентов по модулю, равному произведению различных простых чисел. Оптимальные скоростные характеристики данный алгоритм достигает на специальных последовательностях простых чисел, которые существуют любой длины в силу постулата Бертрана.
В-трстьих, дается программная реализация концентрического мультипликативного алгоритма численного интегрирования с помощью па-раллелепипедальных сеток, вычисленных по алгоритму Добровольской.
Наконец, в последнем разделе третьей главы предлагается программная реализация концентрического мультипликативного алгоритма численного интегрирования с алгебраическими сетками биквадратичного поля (¡2 ^у/2 + ч/з). Выбор конкретного биквадратичного поля обусловлен тем обстоятельством, что в предыдущей главе удалось решить именно для этого поля проблему точной параметризации точек сетки.
В заключение выражаю благодарность научному руководителю доктору физико-математических наук, профессору Н. М. Добровольскому за постановку задачи, постоянное внимание и полезные обсуждения.
РАБОТЫ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ
1. Ребров Е. Д., Селиванов С. В. О приближенном решении интегрального уравнения Фредгольма II рода // Известия Тульского государственного университета. Естественные науки. Вып. 2. — Тула: Изд-во ТулГУ, 2012. С. 83 - 92.
Автору диссертации принадлежат теоремы 3 и 4 об оценке погрешностей квадратурных формул.
2. Добровольская Л. П., Добровольский Н. М., Добровольский Н. Н., Огородничук Н. К., Ребров Е. Д., Реброва И. Ю. Некоторые вопросы теоретико-числового метода в приближенном анализе // Труды X международной конференции "Алгебра и теория чисел: современные проблемы и приложения" Ученые записки Орловского государственного университета. № 6. Часть 2. Волгоград: Изд-во ВГСПУ "Перемена 2012. С. 90 - 98.
Статья содержит обзорный доклад по итогам совместной работы и вклад соавторов неразделим.
3. Герцог А. С., Ребров Е. Д., Триколич Е. В. О методе К. К. Фролова в теории квадратурных формул // Чебышевский сборник. Т. X. Вып. 2(30). — Тула: Изд-во Тул. гос. пед. ун-та им. Л. Н. Толстого, 2009. С. 10 - 54.
Результаты работы получены совместно и вклад соавторов неразделим.
4. Ребров Е. Д. Алгоритм Добровольской и численное интегрирование с правилом остановки // Чебышевский сборник. Т. 10. Вып. 1(29). Тула: Изд-во Тул. гос. пед. ун-та им. Л. Н. Толстого, 2009. С. 65 - 77.
5. Ребров Е. Д. Квадратурные формулы с модифицированными алгебраическими сетками // Чебышевский сборник. Т. 13. Вып. 3(43). Тула: Изд-во Тул. гос. пед. ун-та им. Л. Н. Толстого, 2010. С. 53 - 90.
Издательство Тульского государственного педагогического университета им. Л. Н. Толстого. 300026, Тула, просп. Ленина, 125. Отпечатано в Издательском центре ТГПУ им. Л. Н. Толстого. 300026, Тула, просп. Ленина, 125. Формат 60x90/16. Бумага офсетная. Печать трафаретная. Усл.-печ. л. 1,0. Тираж 100 экз. Заказ 13/054.
ФГБОУ ВПО "Московский педагогический государственный университет"
04201357133
На правах рукописи УДК 511.3
Ребров Евгений Димитриевич
Некоторые теоретико-числовые методы приближенных вычислений
Специальность 01. 01. Об. — математическая логика, алгебра и теория чисел
ДИССЕРТАЦИЯ на соискание ученой степени кандидата физико-математических наук
Научный руководитель доктор физико-математических наук, профессор Н. М. Добровольский
Москва 2013
Аннотация
В данной работе, относящейся к аналитической теории чисел, рассматриваются вопросы численного интегрирования периодических функций многих переменных по системе квадратурных формул с парралелепипедальными сетками, построенных по алгоритму Л. П. Добровольской.
Даются оценки мультипликативной дисперсии для концентрических алгоритмов численного интегрирования, основанных на указанных сетках, на клас-
Построен концентрический алгоритм численного интегрирования с использованием алгебраических сеток с весами по методу К. К. Фролова в модификации Н. М. Добровольского и для случая в = 4 аналога точной параметризации А. С. Герцога алгебраических сеток для модифицированных алгебраических сеток.
сах Е*.
Оглавление
Введение 3
1 Численное интегрирование с правилом остановки 20
1.1 Равномерное распределение взвешенных узлов и приближенное интегрирование............................................................20
1.2 Алгоритмы приближенного интегрирования с правилом остановки 27
1.3 Оператор взвешенных сеточных средних...............34
1.4 Случайные величины и многомерные квадратурные формулы . . 39
1.5 Разбиение Н. М. Коробова.......................51
1.6 Обобщенные равномерные сетки....................54
1.7 Обобщенные неравномерные сетки ..................59
1.8 Параллелепипедальные сетки.....................65
1.9 Оценки мультипликативной дискретной дисперсии для разных алгоритмов вычисления параллелепипедальных сеток.......73
2 Квадратурные формулы с модифицированными алгебраическими сетками 80
2.1 Введение ..................................................................80
2.2 Вспомогательные леммы................................................84
2.3 Решётки и гиперболическая дзета-функция решёток.......91
2.4 Алгебраические решётки................................................95
2.5 Обобщенная гиперболическая дзета-функция алгебраической решётки....................................................................97
2.6 Класс функций Е°{С)..........................105
Г
2.7 Оценки сверху погрешности квадратурных формул на классах функций Ef(C) .............................107
2.8 Алгебраические сетки..........................111
2.9 Параметризация модифицированных алгебраических сеток биквадратичного поля Q (\/2 + \/з)..................117
3 Программная реализация алгоритма численного интегрирования с правилом остановки 126
3.1 Алгоритм Н. М. Коробова вычисления оптимальных коэффициентов ....................................127
3.2 Алгоритм JL П. Добровольской вычисления оптимальных коэффициентов по составному модулю...................129
3.3 Алгоритм интегрирования с правилом остановки..........132
3.4 Программы численного интегрирования для концентрических алгоритмов с алгебраическими сетками.................133
Заключение 136
Литература 138
Введение
В 1956 году по инициативе Н. Н. Ченцова в Математическом институте им. В. А. Стеклова АН СССР был организован научно-исследовательский семинар по разработке новых многомерных квадратурных формул. Этим семинаром руководили профессор, доктор физико-математических наук Н. М. Коробов и его молодые коллеги Н. С. Бахвалов и Н. Н. Ченцов.
В 1957 году вышла первая работа Н. М. Коробова [37], с которой и ведется отсчет истории создания теоретико-числового метода в приближенном анализе. В этой работе был предложен первый класс теоретико-числовых сеток — неравномерные сетки вида (1.106) (см. стр. 59).
В 1959 году в работах [38], [39] Н. М. Коробов ввёл другой очень важный класс теоретико-числовых сеток — параллелепипедальные сетки М(а; АГ) вида
"'-({тг}--{£}) (* = о.1.-."-ч. (Ч
где (о^, А^) = 1 = 1,..., в) и ах,... ,а8 — специально выбранные оптимальные коэффициенты по модулю N.
Достаточно быстро сформировались четыре основных направления приближенного анализа, где эффективными оказались методы теории чисел. Это — вычисление интегралов от периодических функций многих переменных, интерполирование периодических функций многих переменных, численное решение интегральных уравнений Фредгольма II рода и численное решение уравнений с частными производными. Анализ показывает, что из перечисленных четырех направлений исследований основным является первое. И от успехов в этом направлении зависит продвижение и в остальных трех, хотя там и возникает своя специфика [61].
Исходя из указанного обстоятельства, в данной диссертации усилия сосредоточены исключительно на проблеме численного интегрирования периодических функций многих переменных.
Задача приближенного вычисления определенного интеграла относится к числу классических проблем вычислительной математики. Решение этой задачи существенно зависит от класса функций, на котором она рассматривается.
В своей кандидатской диссертации [50] К. К. Фролов выделял следующие основные постановки задачи:
1. построение квадратурных формул, оптимальных для заданного класса функций F;
2. построение асимптотически оптимальных квадратурных формул;
3. квадратурные формулы, имеющие точный порядок погрешности;
4. квадратурные формулы, порядок погрешности которых отличается от точного на множитель вида ln7 N (N — число узлов в квадратурной формуле).
Если взять 2ls класс всех периодических функций f(x) с периодом 1 по каждой переменной, у которой её ряд Фурье
1 1 s
/(£) = Y, c(m)e2wi{™'s), С(т) = (...( f(x)e~27!i^dx, (rn,x) = ¿marnez* { { j=l
абсолютно сходится, то он оказывается слишком обширным для оценки погрешности приближенного интегрирования, так как ряд Фурье может сходиться как угодно медленно. Пространство 2ts относительно нормы
11Ж)1к = £ №й)|<оо
является сепарабельным банаховым пространством, изоморфным пространству h — всех абсолютно суммируемых комплексно-значных последовательностей (см. [31]).
Для дальнейшего мы будем рассматривать более узкий класс Es = U Е£.
а>1
Банаховы пространства быстросходящихся рядов Фурье Е^ определяются ниже (см. стр. 5).
В работе [19] отмечалось следующее обстоятельство: классические оценки погрешности численного интегрирования содержат норму функции, которая неизвестна, и получается парадоксальная ситуация — надо вычислить значение нулевого коэффициента Фурье, а оценка погрешности дается через величину нормы, которая содержит информацию о всех коэффициентах Фурье. А поэтому необходимы правила остановки, сформулированные в терминах величины, которая при росте числа точек стремится к нулю, и, следовательно, по её малости можно судить о скорости сходимости процесса.
В 1957 - 1960 годах ([37] — [39]) при создании теоретико-числового метода в приближенном анализе Н. М. Коробов ввёл в рассмотрение широкий класс периодических функций Е£(С) (а > 1) с быстро убывающими коэффициентами Фурье. Через Е£(С) обозначается множество функций из Ef с нормой, не превосходящей С, то есть шар в банаховом пространстве Ef радиуса С с центром в нуле.
Банахово пространство Ef состоит из функций f(xi,...,xs), имеющих по каждой из переменных х\,...,х3 период, равный единице, и для которых их ряды Фурье
оо
/(хь ...,х8)= •''' ma)e™<m*Xl+~+m'*J (2)
mi,...1ms=-оо
удовлетворяют условиям1
sup |C(wi,... ,me)|(mi.. .ms)a = ||/(f)||Ef < oo. (3)
me Z3
Ясно, что такие ряды Фурье сходятся абсолютно, так как
wrnwi^ ii/(f)ik(i+2C(«)r,
а поэтому для любого а > 1 они представляют непрерывные функции. Здесь и далее, как обычно, — дзета-функция Римана.
Относительно нормы пространство Ef является несепарабельным
банаховым пространством изоморфным пространству /— всех ограниченных комплексно-значных последовательностей (см. [31]).
13десь и далее для вещественных тп полагаем ш = тах(1, |т|). Таким образом, величину Ш можно назвать усеченной нормой числа тп, что согласуется с понятием усеченной нормы вектора, о которой речь пойдет дальше.
Рассмотрим понятие усеченной нормы вектора, которой называется величина д(ж) =х\-...-Ха. Усеченной норменной поверхностью с параметром t ^ 1 называется множество = = 1,хф б}, которое является границей
гиперболического креста К3(Ь), заданного соотношениями К8(Ь) = {а%(ж) < £}. Для натурального Ь на усеченной норменной поверхности имеется т*(£) целых ненулевых точек, где 2
= £'1 (4)
— число представлений натурального числа £ в виде Ь = т,\ •... • гп3.
Используя новые обозначения, можно написать другое выражение для нормы функции ||/(ж)||да. Справедливо равенство
\\f(x)\\E? =max |C(0)|,sup ie • max |C(m)|
V 1 \ m€N(t)
Нетрудно видеть, что произвольная периодическая функция f(x) из Ef(C) по модулю ограничена величиной С • (1 + 2((a))s, при этом данная оценка достижима на функции
оо „ ./(f) = У 7--- е2жг(т,х)
т=—оо
в точке х — 0.
Очевидно, что Ef(C) с Е%(С) при a ^ /3. Для любой периодической функции f(x) € Ef(C) с Е%(С) справедливо неравенство для норм
\\№\\ЕЪ > \\№\\Е!-
Равенство достигается только для конечных тригонометрических многочленов вида
/(ж) = С(б)+ J2 C{m)e2^'s\
meJV(l)
Рассмотрим квадратурную формулу с весами 11 N
... f{x1,...,xs)dx1...dxs = —^pkf[^1(k),...^s(k)]-RN[f}. (5)
J lc—1
О О
23десь и далее Y^' означает суммирование по системам (mi,...,ms) ф (0,..., 0).
Здесь через обозначена погрешность, получающаяся при замене интегра-
ла
1 1
J.. ! }'(хъ...,х8)йх1
(1х„
о о
средним взвешенным значением функции /(хь..., х8), вычисленным в точках
Мк = Ык),...,Ш) (* = 1...М).
Совокупность М точек М^ называется сеткой М, а сами точки — узлами квадратурной формулы. Величины = р(Мь) называются весами квадратурной формулы. В этой работе будем везде предполагать, что все веса веществен-нозначные.
Здесь необходимо сделать одно важное замечание. Вообще говоря, все узлы сетки М не обязаны быть различны (см. например работы [30], [35], [36], [46], посвященные сеткам Смоляка) и среди них могут быть повторяющиеся. В этом случае можно наряду с сеткой М — последовательностью узлов рассмотреть сетку М* — множество узлов, то есть
M^ = {£ = Mj\l^j^N}, \м*\ ^ |М| = И, р(х) = ^ £
У- х=М]
и квадратурная формула перепишется в виде 1 1
... }{хъ...,х3)йх1..^х3 =—— ^ р(х)/(х) - Я\М*\[Я (6)
0 0 1 ^м-
Даже в случае, когда все узлы различные, полезно различать сетку последовательность и сетку множество, так как одной сетке множеству из N различных точек соответствует ЛИ различных сеток последовательностей. Сделав это замечание, мы как правило будем отождествлять сетки множество и сетки последовательности, делая различия только там, где это необходимо.
Так, например, одна и та же параллелепипедальная сетка множество М(а; И) соответствует ^{Щ различным параллелепипедальным сеткам последовательностям М(Ь • где Ь — любое натуральное число из наименьшей приведенной системы вычетов по модулю N и — функция Эйлера.
Для произвольных целых тп\,.. .,та суммы б'м.Д^х,..тв), определённые равенством
N
5м>1,- ■ = (7)
к=1
называются тригонометрическими суммами сетки с весами.
Будем также рассматривать нормированные тригонометрические суммы сетки с весами
■ -,та) = —8м^(т±,..., т8).
N
Положим р(М) — тогда для всех нормированных тригонометриче-
з=1
ских сумм сетки с весами справедлива тривиальная оценка
< ^Р(М). (8)
Если все веса равны 1, то будем говорить просто тригонометрическая сумма сетки и писать 5"м(т) и нормированная тригонометрическая сумма сетки
В работе [19] дано следующее определение, обобщающее определение из работы [33].
Определение 1. Дзета-функцией сетки М с весами р и параметром р ^ 1 называется функция £(а,р\М, р), заданная в правой полуплоскости а = а + И
(<т > 1) рядом Дирихле
?(а,р|м,д= ¿' ^ = (9)
м (т1...т3)а к '
т.1,...,т3=—оо 4 ' п=1
где
5Г(р1М,?,п)= £ 18*м/т)Г. (10)
теТУ(п)
Непосредственно из определения следует неравенство
С(ра,р\М,р) ^(р(а,1\М,р) (а > 1). (11)
Если все веса равны 1, то будем говорить просто дзета-функция сетки М с параметром р и писать £(а,р\М) .
Справедливы следующие две обобщенные теоремы Коробова о погрешности квадратурных формул (см. [19]).
Теорема 1. Пусть ряд Фурье функции /(х) сходится абсолютно, С(гп) — ее коэффициенты Фурье и Бм^т) ~ тригонометрические суммы сетки с весами, тогда справедливо равенство
Зд/] = с(0) ( ^БМА0) - + I С{т)8м,р{т) =
N 7 ) N
с
= С(б) (5^6) - 1) + С(т)Гм/т)
7П1,...,т3=—оо оо
(12)
Ш1 ,...,тв = — оо
и при N—>00 погрешность Ядг[/] будет стремиться к нулю тогда, и только тогда, когда взвещенные узлы квадратурной формулы равномерно распределены в единичном э-мерном кубе.
Теорема 2. Если /(жь ... ,х3) £ Е°(С), то для погрешности квадратурной формулы справедлива оценка
|ад/]| < с
- 1
+ дг
\Зм,р{гп)\
= С
ТП\. .,77г5 —— оо
+С-((а,1\М,р),
(тг... тп8)а
(13)
где сумма бд^Дт) определена равенством (7). На классе Е"(С) эту оценку нельзя улучшить.
Другими словами теорему 2 можно сформулировать так: Для нормы ||Длг[/]||.е« линейного функционала погрешности приближенного интегрирования по квадратурной формуле (5) справедливо равенство
№
« Л £?
д^(0) - 1
оо
N ^ (т1...т3)а
т1,...,т.в=—оо 4 '
(14)
Модифицированной сеткой М(/3) называют сетку, состоящую из модифицированных узлов
мк0) = аш + м, • • •, {Ш + &}) (* = 1...ЛГ).
Линейный функционал погрешности приближенного интегрирования периодической функции /(х) из класса по квадратурной формуле с весами р и
модифицированной сеткой М(/3) обозначается через ЯМ(0) р[/(^)]> а ег0 норма
— через
Д
Е?
В этих обозначениях утверждение (13) применительно к модифицированным сеткам формулируется так:
для нормы линейного функционала погрешности приближенного интегрирования функций, принадлежащих классу Епо квадратурной формуле с весами р и модифицированной сеткой М(/3) выполняется равенство
Я
М{р),р
Е?
N
5м,р(0) - 1
1
+ Л7 £
¡ЗУДГП!, . . . ,Ш5)|
N ' [тщ... те,)а
т,1,...,та=—оо х '
(15)
Это равенство утверждает, что для всех модифицированных сеток М(/3) норма линейного функционала погрешности приближенного интегрирования функций, принадлежащих классу Е£, является инвариантом, который определяется исходной сеткой М и не зависит от вектора модификации.
В работе [19] дано простое объяснение этого факта через понятие граничной функции класса, которое впервые встречается в работе Н. М. Коробова [42], а более подробно в его монографии [43] (см. также [4]).
Функции /(£) с единичной нормой, для которых абсолютная погрешность приближенного интегрирования равна норме линейного функционала погрешности, следуя Коробову, называют граничными функциями класса ЕЛегко видеть, что граничной функцией класса Е® для сетки М с весами р будет функция с коэффициентами Фурье3
Со (те)
О
|5'м,р(те)|да(те)
БмЛ0) ~ 1 |5м,р(0) - 1|
при Бм,р{гп) = 0, при БмА™) ф 0, т ф 0,
при вмА®) ф1,т = 0, при БмА®) = 1, те = 0.
(16)
3 Здесь 8м,р(гп) означает комплексное сопряжение.
Граничная функция класса сеткой определена неоднозначно, если при некоторых значениях т\, ..., т8 тригонометрическая сумма Бм^п) = 0.
Пусть /(х) — граничная функция класса Е" для сетки М, тогда д(х) = = ¡{х — ¡3) — граничная функция класса Е" для модифицированной сетки М0). Так как из
/(£) = £ С0(т)е2^\ д(х) = /(£ - 0) = Е С^тУ™^,
11 11 С\(т) = С0(7п)е-2т^\ С0 (б) = ¡{х)с1х = J...J д(х)с1х = С\(б)
0 0 0 0
следует \\/{х)\\Е? = НяОЮНяу,
N к=1
и
/1 \ 1 °° Д*[/] = Соф) (^мАб) - 1] + ^ Со(т)5м,р(^) =
' т1,...,т3=—оо
/1 \ 1 °° = (м^т/о) Е' с^ммА*) = (17)
^ ' т. т .— —
7711 — 0О
то, действительно, это так.
Так как граничная функция класса зависит от вектора модификации сетки, то приближенное интегрирование одной и той же функции по модифицированным сеткам для разных векторов модификации приводит к появлению дополнительной информации о приближенном значении искомого интеграла. Такая ситуация естественно возникает при использовании произведения сеток, если соответствующим образом организовать суммирование в квадратурной формуле, как будет видно из дальнейшего.
Вопросы численного интегрирования с правилом остановки рассмотрены в работе [19]. Следуя этой работе дадим частное определение мультипликативной дискретной дисперсии для случая произведения двух параллелепипедальных сеток с равными весами.4
4 Подробному рассмотрению понятия произведения двух сеток посвящена работа [21].
Определение 2. Если параллелепипедалъная сетка М является произведением двух параллелепипедалъных сеток 5
то мультипликативной дискретной дисперсией погрешности приближенного интегрирования по квадратурной формуле с сеткой М и равными весами периодической функции f{x) из пространства Ef будем называть величину D*Ml.M2[f{x)], заданную равенством
Из определения видно, что, вообще говоря, (х)\ Ф {х)\.
В качестве правила остановки будем брать величину мультипликативной дискретной дисперсией погрешности приближенного интегрирования, так как при \М\ ->■ оо будем иметь (х)} 0.
Актуальность темы. Диссертация посвящена исследованию теоретико-числовых алгоритмов численного интегрирования периодических функций многих переменных. Рассматривается актуальная задача получения оценок мультипликативной дисперсии концентрических алгоритмов численного интегрирования.
Исследование теоретико-числовых алгоритмов численного интегрирования, интерполирования, решения уравнений с частными производными и линейных интегральных уравнений на классах периодических функций - это современная отрасль теоретико-числового метода в приближенном ана
