Обобщенные параллелепипедальные сетки и их приложения Родионова, Ольга Владимировна

Введение к работе

Актуальность темы.

Краткая история создания теоретико-числовых методов в приближенном анализе содержится в работе Н. М. Коробова ', в которой также приводится достаточно обширная библиография. Одним из главных направлений теоретико-числовых методов приближенного вычисления кратных интегралов является теория квадратурных формул с оптимальными параллелешшедальными сетками, предложенными Н. И. Коробовым в 1959 году.

Пусть натуральные N > 1, s > 2 и целые ai,..., a_s взаимно простые с N. Множество точек М_к = ({^),-.-,( {к = 0,1,.. ;,ЛГ-1), как известно, называется параллелешшедальной сеткой и используется для построения многомерных квадратурных формул вида:

где і?л'[/] ~ погрешность квадратурной формулы, /(f) - функция, интегрируемая на [О, l]^s.

Здесь и далее ТІ означает, что из суммирования исключена точка т = (0,..., 0), х — тах(1, |#|) для любого вещественного .г, и

S_N(a) = { I ^ПР" ^s (^mdiV)

[ 0 в остальных случаях.

По определению, если для бесконечной последовательности Л^г н целых а„ — a„(N) (и = 1,2,...,*) существуют константы /3 = /3(s) и со — cq(-9) такие, что для функции

- N-1

S„{ai—,o_s)= Y! 5^{aimi + ... + a_sm_s) (пц ...-mj)""

mi,...,m,=-(W-l)

выполняется неравенство

bfr[ai; ...,a_s)

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

то целые a\,...,a_s называются оптимальными коэффициентами по модулю iV, а константа /3 - их индексом. Погрешность интегрирования

Ддг(Я?(С))= sup |ВД]|

/ЄЕ?(С)

на классе Ef(C) периодических функций

m С

ll/IUf(C) = sup|C(m_b...,m_s)(mr-...-m7)^a| < С, выражается следующей формулой:

mi,...,»!,=—оо \ТЦ ' ' O^s)

Если целые bi = 1, b2,...,b_s удовлетворяют сравнениям bjuj = a.j (j = 1,..., s), то квадратурная формула

^{///««4s/(s.m--m)-*w <2»}

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

mi_,...,m_t——cc (,^ml ' * "Wis)

Множество решений сравнения ті + Ь%т<і + ... + b_sm_s — O(modiV) являются точками целочисленной решетки A(b2,...,b_s,N) с базисом Xi = (N,0,...,0), Xj =-(-b_j,52_j,...,8_sj) (j = 2,...,s), где 5ц Кроне-кера задается равенствами

,5- = / ^{г п}Р^иг'=І ^,J (_ 0 при г ф j.

Узлы квадратурных формул (1) и (2) являются точками взаимной решетки A*(b2,...,b_s,N) с базисом Л| = (#,#» >#) Д> =

(6ij,...,6_Sj),(j — 2,...,s), лежащими в единичном 5-мерном полуоткрытом кубе G_s = [0; l)^s. Основной результат метода оптимальных коэффициентов состоит в том, что для любого N можно выбрать b-2,...,b_e таким образом, что для гиперболической дзета-функции решетки

(_H(A(h,...,b_s,N)\a)= ' (2Г-....ж;)-⁰

гел(ь₅,...,»„л')

справедлива оценка

C_H(A(b₂,...,b_s,N)\a) = 0(N~^aln^a(s-^N),

где константа в знаке О не зависит от JV, а только от s и а. Таким образом, для погрешности

Длг(Я?(С)) = С (я(Л(6₂,.. .,6„JV)|a)

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

R_N{E{C)) > С Ci (a, s)N~^a In⁵"¹ JV, где Сі (а, s) > 0.

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

R_N{E{C)) = 0{N-^aW~^l N).

Различные варианты аналогичных конструкций квадратурных формул с использованием алгебраических решеток были предложены В. А. Быковским ⁴, II. М. Добровольским ⁵ М. М. Скригановым. Другое направление развития метода оптимальных коэффициентов, связанное с по-

²Шарыгин И.Ф. Оценки снизу погрешности квадратурных формул на классах функций. Ж. вычисл. матем. и матем. физ., N4, 1963.

³Фролов К.К. Оценки сверху поргешности квадратурных формул на классах функций. ДАН СССР 231, N4, 1976.

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

⁵Добровольский Н.М. О квадратурных формулах на классах Ef (С) и Я(С). - Ren., 1984.

строением алгоритмов вычисления оптимальных коэффициентов с помощью теории дивизоров, развивается в серии работ С. М. Воронина ^е и Н. Темиргалиева ⁷.

На первый взгляд теории предложенные Н. М. Коробовым и К.К.Фроловым далеки друг от друга. Но, как показал Н. М. Добровольский ⁸, здесь есть тесное единство. Его конструкция выглядит следующим образом.

Пусть Л произвольная s-мерная полная решетка и Л* ее вза мная решетка. Обобщенной параллелепипедальной сеткой решетки Л называется сетка М(Л) = Л*П[0; l)^s — состоящая из точек взаимной решетки Л*, лежащих в s-мерном единичном кубе G_s = [0; l)^s. Пусть для произвольного вектора х {} = ({xi},...,{x_s}), Mi (Л) = Л*П[—1;1)* и М'(Л) = {х\х — {у},у Mi (Л)} — обобщенная параллелепипедальная сетка II типа. Ясно, что М(Л) С М'(Л), а для целочисленной решетки Л имеем М(Л) = М'(Л).

Гладкая функция р{х), удовлетворяющая условиям

Y, р(ж +(!,...,,)) = 1 ПрИ І Є G«,

1,...,,=-1

/>()= О при х (-1-, i)^s,

J ---J p(x)e^2ri{^dx -і -і

< B(oi ... _s) ^r для любого R^s

называется весовой функцией порядка г с константой В.

Квадратурной формулой с обобщенной параллелепипедальной сеткой II рода и весовой функцией р(х) называется формула вида

її ///(*)*?= (detA)-¹ р*№ - R_N,_{A)(f),

0 0 єМ'(Л)

где р_г= р(у), JV'(A) = |М'(Л)|,

^Mj(A),{5}=2

⁶Воронин СМ., Темиргалиев Н. О квадратурных формулах, связанных с дивизорами поля гауссовых чисел. 1989.

'Темиргалиев Н. Применение теории дивизоров к численному интегрированию периодических функций многих переменных, 1990.

⁸Добровольский Н.М. Гиперболическая дзета-функция решеток. Деп. 1984.

І?_Л"(Л)(/) — погрешность квадратурной формулы.

Для погрешности квадратурной формулы с обобщенной параллеле-пипедальной сеткой II рода на классе Ef справедлива оценка

Rn>(a)(E:(C)) = |Д*'(/)| < С ВС,(аУС_и(А\а),

feEf(C)

С_х{а) = 2*⁺¹ (з + —) , (нЩа) = '(*! ^: -^Г*.
\ ос — і у _геЛ

Рассмотрим произвольную квадратурную формулу с параллелепи-педальной сеткой (1) при (a,j,N) = 1, (j = 1,..., s) Для линейного функционала погрешности квадратурной формулы (1) справедливо следующее выражение для его нормы

IIP МП - V⁵ Mw+'-ra,

Так как функция

_{як... ^до^І^^ІИШ}

связана с |Ji?7v[/]||f неравенствами

j) (tf(_ai,...,a_s__i;iV)-l),

то один из известных алогритмов поиска оптимальных коэффициентов ai,... ,a_s_i по произвольному модулю N основан на последова- тельном поиске оптимальных значений if (ai,iV), H(ai,a^N),. ,.,FI(ai.... ,a_s_i,]V) методом последовательного перебора всех aj. при уже найденных значениях ai,... ,а^_і и, таким образом, требует 0(s² - iV"²) арифметических операций.

При s = 1 легко получить полное решение задачи, так как при (а,Д^т) = d имеем:

up ми - ^2d^H

где (0:) - дзета-функция Римана

Следующий по сложности случай s = 2 при прямом использовании формулы (2) для поиска оптимальных коэффициентов требует 0(N²) арифметических операций сложения и умножения.

И. Д. Кан в своей кандидатской диссертации "Рекуррентные последовательности и их приложения", в частности, рассмотрел вопрос о существовании алгоритма вычисления величины H(a,N) за O(lniV) арифметических операций. Он показал, что такой алгоритм существует, но его явный вид не был найден. Актуальность построения * ^кого алгоритма связана с тем, что вычисления величины Н(а, N) за O(lniV) арифметических операций позволяет за 0(N In N) арифметических операций находить наилучшую параллелепипедальную сетку из N точек для квадратурных формул вида (1) на классе Е\.

Методы исследования.

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

Цель диссертационного исследования.

1. Рассмотреть комбинированные сетки Н. М. Коробова и п среднее преобразование периодических функций.

1. Найти рекурсивные формулы для вычисления степенных сумм с дробными долями.

2. Найти явные формулы для вычисления степенных сумм с дробными долями типа (а, /3) с а+/3 < 4, (3 < 2 через числители и знаменатели подходящих дробей и неполные частные.

5. Найти явную формулу для вычисления функции Н(а, N) за
0(1иЛ^г) операций.

Новизна результатов.

1. Для квадратурной формулы с комбинированными сетками Н. М. Ко
робова предложена интерпретация как квадратурной формулыъ с па-
раллелепипедальной сеткой для n-среднего преоблазования интегриру
емой функции.

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

3. Получены рекуррентные формулы для вычисления степенных сумм с дробными долями.

4. Получены явные формулы для вычисления степенных сумм с дробными долями типа (а, /?) с о -f (3 < 4, /3 < 2 через числители и

знаменатели подходящих дробей и неполные частные.

5. Построены новые алгоритмы вычисления за С (In N) операций погрешности двумерной квадратурной формулы с параллелепипедальной сеткой.

Все результаты являются новыми.

Теоретическое и практическое значение.

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

Апробация работы.

Результаты докладывались на Ш-ей международной конференции "Современные проблемы теории чисел и ее приложения" (Тула, 1997), теоретико-числовом семинаре под руководством кандидата физ. - мат. наук Н. М. Добровольского в ТГПУ им. Л.Н.Толстого, Всероссийской научной конференции "Современные проблемы математики, механики, информатики" (Тула, 2000), теоретико-числовом семинаре под руководством доктора физ. - мат. наук Д. А. Митькина в МПГУ, семинаре под руководством доктора физ. - мат. наук В. И. Иванова в ТулГУ.

Публикации.

Основное содержание диссертации отражено в 5 публикациях. Их список приведен в конце автореферата.

Структура и объем диссертации.