Алгоритмы вычисления оптимальных коэффициентов тема автореферата и диссертации по математике, 01.01.06 ВАК РФ



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

ДОБРОВОЛЬСКАЯ Лариса Петровна

Алгоритмы вычисления оптимальных коэффициентов

Специальность 01.01.06 —математическая логика, алгебра и теория

чисел

Автореферат ^ Д Е К

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

Москва — 2009

003486037

Работа выполнена на кафедре алгебры, математического анализа и геометрии факультета математики, физики и информатики ГОУ ВПО "Тульский государственный педагогический университет имени Л. Н. Толстого".

Научный руководитель:

доктор физико-математических наук, профессор Чубариков Владимир Николаевич

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

доктор физико-математических наук, профессор Журавлев Владимир Георгиевич,

кандидат физико-математических наук Кан Игорь Давидович

Ведущая организация: Тульский государственный университет

Защита диссертации состоится " ^^'-О-АГу^д- 2009 г. в час. ^ мин. на заседании диссертационного совета Д.212.154.32 при Московском педагогическом государственном университете по адресу: 107140, г. Москва, ул. Краснопрудная, дом 14, математический факультет МП-ГУ, аудитория 301.

С диссертацией можно ознакомится в библиотеке Московского педагогического государственного университета по адресу: 119991, г. Москва, ул. Малая Пироговская, д. 1.

Автореферат разослан " 2009 г.

Ученый секретарь диссертационного совета

Муравьева О. В.

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

Актуальность темы. За пятьдесят лет развития теоретико-числового метода с 1957 года, когда вышла первая работа ['] Н. М. Коробова но этому направлению исследований, с которой и начннается отсчет в становлении теоретико-числового метода в приближенном анализе, вышло значительное количество работ десятков авторов и в пашей стране и зарубежом. Краткая история возникновения этого метода описана её основателем в [2]. Теоретические предпосылки теоретико-числового метода восходят ещё к работе [3] Г. Вейля, вышедшей в 1916 году, в которой, с одной стороны, содержался интегральный критерий равномерного распределения последовательности по модулю 1, а, с другой стороны, в этой работе были получены первые нетривиальные оценки тригонометрических сумм. Именно применение оценок А. Вейля рациональных тригонометрических сумм было основопологагощим при исследование первого класс теоретико-числовых сеток — неравномерных сеток.

Существенное изменение теории и практики вычисления кратных интегралов связано с появлением метода оптимальных коэффициентов Н. М. Коробова. Центральной проблемой в этом направлении исследований остается вопрос о построении экономных алгоритмов вычисления оптимальных коэффициентов. Именно этому и посвящена данная диссертация, что объясняет её актуальность.

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

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

Цель третьей главы — построение общего алгоритма вычисления оптимальных коэффициентов по произвольному составному модулю JV, используещему логарифмическую меру качества, пригодных для комбинированных сеток.

Цель четвертой главы — модификация общего алгоритма из третьей главы на случай специальных модулей Дг, для которых трудоемкость алгоритма понижается до 0{N) элементарных арифметических операций.

Научная новизна. Результаты работы являются новыми, полученными автором самостоятельно. Основными результатами данной работы можно считать следующие:

— дан новый критерий оптимальности набора коэффициентов, основанный на обобщенной теореме Гельфонда, для любого модуля Л";

— введена новая мера оптимальности набора коэффициентов и дан обобщенный критерий оптимальности;

— построен общий алгоритм вычисления оптимальных коэффициентов для произвольного модуля Л', основанный на минимизации обобщенной логарифмической меры качества;

— построены быстрые алгоритмы вычисления оптим&чьных коэффициентов дня специальных модулей.

'Коробов Н. М. Приближенное вычисление кратных интегралов с помощью методов теории чисел // ДАН СССР. 1357. N 6. С. 1062 - 1065.

2Коробов Н. М. О теоретико-числовых методах приближенного интегрирования . / Истирико-матем. исследования. СПб., 1!)!)4. Вып. XXXV. С. 285 - 301.

sWeyl Н. Über die Gleichvert.eihmg von Zahlen mod. Eins. // Math. Ann. 1916. Bd. 77. S. 313-352 (пер. в кн.: Вейль Г. Математика. Теоретическая физика. М.: Наука, 1984)

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

Теоретическая и практическая ценность. Диссертация носит теоретический характер. Ее результаты могут быть использованы в исследованиях по приложению методов теории чисел к вопросам приближенного анализа.

Апробация работы. Результаты настоящей диссертации докладывались автором на следующих семинарах:

— научно-исследовательский семинар "Теория аппроксимации" под руководством профессора В. И. Иванова в Тульском государственном университете;

— научно-исследовательский семинар "Арифметика, алгоритмы, теория сложности вычислений" под руководством профессора В. Н. Чубарикова в Московском государственном университете им. М. В. Ломоносова;

— научно-исследовательский семинар "Теоретико-числовые методы приближенного анализа" под руководством профессора Н. М. Добровольского в Тульском государственном педагогическом университете им. Л. Н. Толстого;

— международной конференции "Аналитические и комбинаторные методы в теории чисел и геометрии" в Московском государственном университете им. М. В. Ломоносова. Москва, 2006.

Публикации. Результаты диссертации опубликованы в работах автора [1], [2], [3], [4] и [5], выполненных по грантам РФФИ 05-01-00672 и 08-01-00790.

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

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

В 1959 году Н.М.Коробов в работе "Вычисление кратных интегралов методом оптимальных коэффициентов" ввел сетки вида

М(а, N) -

{«-({#}.....МЖ1'2.....4

(1)

где « = (аь..., а,), а^.... а, — целые числа, взаимно простые с N. Такие сетки он назвал параллелепипедалъными. В этой работе [4] Н. М. Коробовым было введено понятие оптимальных коэффициентов и указано их значение для приближенного вычисления многомерных интегралов произвольной кратности « от периодических гладких функций.

Пусть целое N > 1, Nt =

'N-1 •v _ 'N'

2 > -ч — 2

о„ = о„(Аг) - целые, взаимно

простые с N (и = 1,.... s) п символ Коробова i.v(6) задан равенствами

sN{b)=iQ- если ¡mofj2' (2)

v ^ 1, если 6 = 0 (mod Л ). Обозначим через S.vUi.....*•) сумму5

S.v(*,....*.)= f' (3)

' 777]... ш,

-N,

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

53десь ]Г)' означает суммирование по системам (mi,... .гп„) ф (0____,0).

где 2\,..., г, - произвольные целые, тп = юах(1, |т|) для любого вещественного т.

Согласно определению, если существуют константы ß = ß(s) и В = B(s) такие, что для некоторой бесконечной последовательности значений Лг выполняется неравенство

In" N

(4)

то целые щ,..., а, называются оптимальными коэффициентами индекса ß по модулю N.

Величину 5лг(п1,..., а,) называют основной мерой качества набора оптимальных

коэффициентов. Известно (см.р] С. 81), что для любых целых ai.....а, выполняется

оценка

SN[au...,a.)>Bo^, (5)

с некоторой константой Во.

Для а (N) — среднего арифметического основной меры качества набора коэффициентов по всем параллелепипедальным сеткам, заданного равенством

1

<n».JV)=l '(!•= 1.......

и для любого составного модуля N справедливо асимптотическое равенство

Доказательство этой асимптотической формулы достаточно сложно (см. (7J, (8J). Из неё следует существование оптимальных коэффициентов для любого составного модуля N.

Различные критерии оптимальных коэффициентов, на которых основаны алгоритмы их вычисления, приведены в работах [9], |10] и [п]. В качестве критериев оптимальности набора естественно рассматривать различные количественные меры качества. В качестве меры качества можно брать погрешность приближенного интегрирования или суммирования граничной функции класса. В первой главе найдены в явном виде в конечной форме граничные функции некоторых классов.

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

Вторая глава посвящена применению теоремы А. О. Гсльфонда о связи решетки Л = Л(в1,... ,as; .V) решений линейного сравнения и присоединенной решетки Л'р)

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

7Доб|Ю1юлtOKlifi Н. М., Родионова О, В. Об одном конечном ряде Фурье и его приложениях //Изв. ТулГУ. Сер. Математика. Механика. Информатика. 1998. Т. 4. Вып. 3. С. 68 — 79.

"Вронская Г. Т., Добровольский Н. М., Родионова О. В. Сравнения, суммы и произведения по приведенной системе вычетов /7 Известия ТулГУ. Сер. Математика. Механика. Информатика. Т. 8. Вып. 1. Тула. 2002. С. 10 - 28.'

"Коробов Н. М. Свойства и вычисление оптимальных коэффициентов /7 ДАН СССР 132. i960. N5. С. 1UU9 - 1012.

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

^Коробов Н. М. О некоторых вопросах теории дпофантовых приближений // УМН. 1967. Т. 22. 3 (135). С. 83 - 118.

решений системы линейных сравнений к вопросу о построении набор<а оптимальных коэффициентов параллелегшпедальной сетки для любого составного модуля N.

В 1982 году Н. М. Коробов в работе [12| построил наиболее быстрый из известных алгоритм вычисления оптимальных коэффициентов по модулю равному степени двойки. Этот алгоритм был основан на теореме А. О. Гельфокда, связывающей между собой величины гиперболического параметра g(A) решетки Л = A(ai,..., a„;N) решений линейного сравнения

т + ami + ■■■ + а,т, s Q (mod N) (8)

и аналогичного параметра Q(Л) присоединенной решетки А(р) решений системы линейных сравнений

(ki = fti к

......... (mod N). (9)

к, = а,к

Согласно теореме А. О. Гельфонда (см. [и], [13], [14], [6]) для величин

д(А) = min ТПЩ...т„ Q(Л) = min (А;ИАга|... (10)

>й€л\{я) seaw,

(mod N)

справедливы неравенства

Q(Л) > С,(в)9(Л)', e(A)>Ci(e)9(^

Будем как обычно через ||г|| = шш({х}, 1 - {ж}) обозначать расстояние до бли-жайщего целого.

Обозначим через 5y(«i, —г,) сумму

**......^-Sufnw (12)

где -д,..,, z, - произвольные целые. Величину функции S^fo.....z,) будем называть присоединенной мерой качества. Основные результаты данной главы:

Теорема 5. (с. 61) Целые 1, z\,..., zs — оптимальные коэффициенты по модулю N тогда и только тогда, когда существуют константы ¡% = /Зг(^) « Вг = Bi(s) такие, что для некоторой бесконечной последовательности значений N выполняется неравенство

S:w(zu < В21п',2Л\

Теорема 6. (с. 05) Для любого нату}Х1льного N > 2 существует набор оптимальных- коэффициентов 1, oi,..., а, по модулю А' с

S'( пь ■ • ..а.) < (2 In Л" + 2 (С - hi 2) + 3)" (In Л- + С - In 2).

12Коробов Н. М. О вычислении оптимальных коэффициентов // ДАН СССР. 2С7. 1982. N2. С. 289 - 292.

13Коробов Н. М. Об одной оценке А. О. Гельфонда // Вестн. МГУ Сер.1. Математика. механика. 1983. N3. С. 3 - 7.

''Добровольский Н. М., Ванькова В. С. Об одной лемме А. О. Гельфонда. Деп. в ВИНИТИ 08.01.87, N 1467-В87.

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

Теорема 7. (с. 65) Для любого натурального Л" > 2 определим последовательно целые числа а^,..., «* из условий

• ■ •,а') = и1шп_^ ...,«*_!, а),

тогда набор 1, а},..., является набором оптимальных коэффициентов по модулю N с

Я'К, •.., а*) ^ (21п N + 2(С - 1п 2) + 3)' (1п N + С - 1ц 2) при любом ] С 1 ^ 3 ^ в.

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

Множество Мя(а1,...,а.) из N точек Мк = ,..., [к = 0.1,...,

N — 1), как уже указывалось выше, называется параллелепипедальной сеткой и

используется для построения многомерных квадратурных формул вида:

.....

о о к~°

где Ял>(/] - погрешность квадратурной формулы. Рассмотрим две функции

Шаг.....а') = ЕЙ (1 " 21п (2«п И^}))) •

.....= Е Й (1и * - 21п (2 ™ (* {¥}))) ■

первая из которых называется логарифмической мерой качества, а вторая — усиленной логарифмической мерой качества набора коэффициентов «!,...,а5 по модулю N.

Если рассмотреть обобщенную логарифмическую меру качества с константой .4^1, заданную равенством

Ткл(а,.....а,) = Е Й (А - 21л (гип . (13)

то справедливы равенства

Тх{ил.....о,) = 7^.1 (в|, ...,п,). 7>(оь.... а») = Тлмпл-(а1.....о,).

Прежде всего заметим, что логарифмическая и усиленная логарифмическая меры качества набора коэффициентов имеют простой смысл в терминах приближенных формул суммирования. Рассмотрим среднее-арифметнческоо значение по узлам равномерной сетки, лежащим в открытом единичном ¿-мерном кубе (0; 1)", для функций

......т„) = Д(1 - 21н(2кт(7г^)))

/2(ж,,..., х.) = Д(1п N - 21п(2ип(тг^))),

3*1

а именно,

Согласно лемме о произведении синусов (см. [10], стр. 115)

(14)

справедливы равенства

и

Если рассмотреть формулу приближенного суммирования с параллслепшкда.ш>-ной сеткой без нулевой точки

и "А7

-*Ь§'({#}.....Ш-ад

ТО при /(.?!, ...,х,) = /х(:С:.....х,) получим

Я[Л1 = —---

.....ц.)-ЛГ г,/1пЛЛ

.V - 1 \ N

а при /(гь-.-.т») = /2(х\,. ..,х„) находим

«ш

.V - 1

Ясно, что эти формулы являются частным случаем связи погрешности приближенного суммирования с обобщенной логарифмической мерой качества с константой

А. Если рассмотрим среднее-арифметнческое значение по узлам равномерной сетки, лежащим в открытом единичном 5-мерном кубе (0; 1)*, для функции

я

/(х,,..., аг„; Л) = П(А - 21п(2 )))

а именно, то при А > 1

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

....."

-гЪЁ'СМ.....{^И-адм*

то получим

Т>-, А(а1,.. ■, а.) - А' N ( А'"11и N + А'

N-1 V

В работе ([10], стр. 117) показано, что необходимым и достаточным условием того, чтобы целые Оь... ,о8 были оптимальными коэффициентами, является существование констант Д = и С1 = с^) таких, чтобы для логарифмической моры качества оценка

.....а.) ^ N + С11пв' Лг

выполнялась для бесконечной последовательности целых N.

Аналогичный результат для 7л'(й1...., а4) — усиленной логарифмической меры качества доказан в работе [15].

Критерий оптимальности. Необходимым и достаточным условием того, чтобы целые ..., ав были оптимальными коэффициентами, является существование констант 82 = &(«) и сз = Сг(«) таких, чтобы оценка

Гдг(аь...,а,) $Л'1п".У + с21пааЛг (15)

выполнялась для бесконечной последовательности целых N.

При этом, пели выполнена оценка (15), то каждый набор коэффициентов а;,, ..., а/, (1 < < ... < < в), 7 > 2 будет оптимальным с индексом пшхЦ + А -

15Доб1ювольский Н. М., Коробов Н. М. Оптимальные коэффициенты для комбинированных сеток. /7 Чебышевокпй сборник, Т. 2, Тула, 2001, С. 41 - 53.

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

T*N = ~¡Ám .....

U-1.....»)

Е ЫЬ.....«•)■ (16)

Ü-1.....•)

Если рассмотреть среднее арифметическое обобщенной логарифмической меры качества с константой А по всем параллелепипедальным сеткам

т"-л = Ш) £ TnAüi.....0а)- (17)

0-1.....')

то

/т1* ггч гг' гг1

= 1, JiV = Inmn-Как показал Н. М. Коробов (J10], стр. 122), при простом N = р справедливо равенство

т-о-Ч-г?)'

Аналогичное равенство справедливо дня усиленной логаримической меры качества

3]> = (р-1) (lnP~~rf)' (18)

и для обобщенной логаримической меры качества с константой А

Т,л = (Р~1){А-^)'. (19)

Каждое из этих равенств позволяет утверждать, что в основном все паратлеле-пшюдальные сетки по простому модулю являются оптимальными.

Заметим, что в работе [15] для простого р и N — jJ' доказана более ебщая формула

7> = - 1)]BV +£> И ((ьрл --ьу). (20)

В третьей главе доказывается обобщенный критерий оптимальности набора коэффициентов по произвольному модулю N. выраженный в терминах величины обобщенной логарифмической меры качества T)v,^(ai.....п.).'и вычисляется среднее

Далее, центральное место в главе посвящено построению алгоритма поиска значений оь..., а, из приведенной системы вычетов по произвольному модулю N. та^

кчх что дтя обобщенной логарифмической меры качества Тр/.д(сц.....п8) выполнено

неравенство

ЗД,.....■ (21)

В частности, при .4 = 1ц N получаем неравенство

ГЛ.(П1,...,а,ХЛЧп' ЛГ. (22)

Значение именно таких наборов оптимальных коэффициентов для комбинированных сеток (см. [1в])

.........«-($♦=}.....

[к = 0,1.....N — l]ki,... ,к, = 0,1,...,М - 1),

где М - произвольное натуральное, взаимно простое с N, определяется следующим результатах! из работы [15].

Если оптимальные коэффициенты ai,...,а, удовлетворяют условию (22), М « ln(JV) ufe Е°{С), то для погрешности Лл-л;<[/] квадратурной формулы

i i

I ■•• J /(£) di =

.....{¥4})-»«

выполняется оценка

m ííh ln°'jv

Все известные алгоритмы вычисления оптимальных коэффициентов, кроме случая 5 = 2, можно отнести к различным вариантам метода полного перебора дискретного аргумента из некоторой области для поиска минимального значения специально построенной функции или нескольких функций. К такому же типу относится и предлагаемый ниже алгоритм. Так как для простых модулей N алгоритм Коробова из [10] (сы. стр. 120 — 123) совпадает с нашим, а для модуля Лг, равного степени простого р, обобщение алгоритма Коробова содержится в работе [15], то далее будет предполагаться модуль N, имеющий хотя бы два различпых простых делителей, то есть г>(Лг) > 1. Для краткости далее везде п = 1? 2.

Напомним определение произведения двух ссток Му и Мз- Как известно (см. [17]),

мх ■ мг = {£= {г+¿7)1*е Л-Л, г?б щ,

где для любого вектора {£} = ({Х]}.....{я1»})'

Для нахождения оптимальных значений аь а, переменных Хь ..., Х3. пробегающих наименьшую приведенную систему вычетов по модулю Л' = Р1-... .р„. где

Р„ = (и = 1.....п) и р!.....р,, — различные простые в каноническом разложении

числа N. переходим к рассмотрению параллелепипедальной сетки по модулю N как произведения параллслепипедальных сеток по модулям Рь... ,Р„:

.....= П л*а(й»<" • • ■ • "»")•

1йКоробов Н. М. Квадратурные формулы с комбинированными сетками // Математические заметки. 1904. Т. 55. Вып. 2. С. 83 - 90.

1'Добровольский М. Н., Добровольский Н. М., Киселева О. В. О произведении обобщенных па-раллелеиипедальных сеток целочисленных решёток // Чебышевский сборник 2002 Т. 3. Вып. 2(4). Тула, Иэ-во ТГПУ им. Л.Н.Толстого. С. 43 — 59.

где йь,,..., а.„, из приведенной системы вычетов по модулю Р„ (и = 1,..., п). Такое представление параллелегшпедальной сетки по модулю N как произведения парал-лелепипедальных сеток по модулям .. ,Р„ приводит к поиску аь..., а, в виде

(1 < ; ^

а сама параллелепипедальная сетка Мц(а\....,а,) допускает более удобную для дальнейшего кратную параметризацию точек

Мь'(аъ...,а„) =

-Ь......«-({£#}.....

О ^ и < Р„ - 11 1^ = 1 ,...,п

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

«(«1.....'*)=! }..... Е^

п

Л/'л)* = П Мл{аг......о,,,) =

|/=л+1

.....

I < и, < Р„ -11 ^ = 1.....А /'

О ^ и < Р„-1 V = А+1.....п

Мк(аи..., о.) = Мт ■ М(Л)* (0 ^ А < п).

(23)

Здесь удобно считать, что Л/(0) = Л/1"1* = {б}, кроме того полагаем ро = 1.

Такой подход приводит, сначала, к переходу к переменным пробегающим приведенные системы вычетов, соответственно, по модулю Р„, с помощью формулы

и - 1.....

Затем рассмотрим каждую из параллелепипедальных сеток Л/р„(а\„, ..., а.,„) по модулю Р„ как произведение неполных параллелепипедачьных сеток:

о„-1 /а л

МрМЪ.....о„„)= Д л/у, Е01""^'.....Е0""^

а=0 4/1=0 11=0

где неполная параллелепипедальная сетка

/а а

[ Е аь'"р-Е

\м=0 (1=0

из р„ точек имеет вид:

л/р*;+1 fe01^.....=

\»=о ,i=0 /

•••{гФ-Ч)

^aiwPÍ

0 < 1

Таким образом приходим к р-ичным представлениям переменных Z,-„:

Q„ —1

Zjv = £ Sjrtpi (j = l,...,S l/=l,...,n),

A=0

при этом величины при 1 ^ А ^ о„ — 1 пробегают полные системы вычетов по модулю р„, а величина — только приведенную систему вычетов.

Следовательно, задача о нахождении оптимальных значений а ¡,..., а, из достаточно сложной для программирования s—мерной области

l^a^N-1 (oj.JV) = 1 (KjsSs),

содержащей <p'(N) точек, где ¡¿(Лг) — функщш Эйлера, сводится к задаче о нахождении значений

(1 < j ¡S s, 1 < v < п, 0 ^ А < а„ - 1) из более простой s(fti +... + а„)-мерной области

0<а>д <р„-1 (1 < j < s, 1 $ v $ п. 1 < А < а„ - 1), 1 Í ^ Pi, - 1 (1 ^ j s, 1 í v ^ п),

в которой содержится тоже самое количество точек. Упорядочим множество индексов (j v А) по правилу: (л ¡/i Ai) < (jv А), если выполнено одно из трех условий:

(а) г/i < v\

b) i/¡ - v, Ai < А;

c) i/i =i/, Ai = A, ji < j.

Условия a),ft),c) задают на множестве индексов линейный порядок, который с точностью до перестановки индексов является лексикографическим. Минимальным элементом является набор (110), максимальным — (sr;q„ — 1).

На линейно упорядоченном множестве индексов можно ввести две функции: (j v А)' — следующий набор, (j и А)* — предыдущий набор с помощью равенств

Í(j+lv\) если j < s.

(li/A + 1) если j = s. А < - 1.

(li/ + 10) если j - s, А = au - 1,1/ < n;

Í(j - 11/ А) если

(.si/A-1) если

(si/- 1 o„_i - 1) если

> 1.

= 1, A > 0. = 1, A = O.i/ > 1.

Для описания алгоритма вычисления нам необходимо построить систему функций Т'^д(г), зависящих от параметров а^^л, со всеми наборами индексов {к ^г А1) <

Удобно ввести ещё вспомогательные функции =

Определим величины Ех и множества В„а равенствами

Г 1 при А = 0, „ г £Л = \0 при А > О, Я* = {**■•■-Я-!}.

Таким образом, множество В„\ — полная система вычетов по модулю р„ при А > О и приведенная при А = 0.

Определение функций заданной на конечном множестве проведем

последовательно, начиная с наибольшего набора индексов, следующим образом.

Ип - Ov-1 Ч ( П . Ои-1

f=0 г" а=0 ) u=0 а=0

где г = г»ш>„-ь а все остальные г^л с меньшими наборами индексов являются параметрами.

Если функция тЦ^к) уже определена, то следующая функция Г^1^' (г) от г = на конечном множестве где (.¡^А]) = 0'1л\)', задается равенством

pv—l

Построение набора функций T¡j"¿\z) для (110) ^ (J v А) ^ (sna„-l) закончено.

Алгоритм вычисления величин а по.....а„ lft„_i проводится последовательно, исходя из соотношений:

Г 1 < Оно < р\ - 1

"Л.,®-") ^

если Оцо,____о;jV\y уже определены, то а,-„л находится из условий

( г* « o,va р„ - 1

Для всех функций Tjy"A'(í), выполнив необходимые суммирования в конечном виде, удается получить явные формулы.

Центральным результатом этой главы является следующая теорема: Пусть ano: • ■ • j 0Sna„-i найдены по алгоритму, заданному формулами (24, 25). Обозначим через «i,...,а, величины, заданные по формулам

p¡ Е «^í+• • • + р- Е ] w =1.....*)■

(26)

Теорема 17. (с. 130) Величины аь... , а, заданные формулами (24, 25, 26) являются оптимальными коэффициентами по модулю N индекса и для обобщенной логарифмический меры качества г. константой А этого набора коэффициентов по

модулю N справедливо неравенство

**......

В четвертой главе дается определение допустимой последовательности простых и специального модуля, для которых на основе общего алгоритма для N = pip¡...рк, где Pi,Pi, ■ ■ ■ ,Рк — допустимая последовательность простых чисел, строится алгоритм вычисления за 0(N) арифметических операций значений a¡,...,a, из приведенной системы вычетов по модулю N таких, что выполнено неравенство (21).

Пусть р — фиксированное нечетное простое число большее 3, например, любое нечетное простое число большее 3 и непревосходящее 100. Будем говорить, что монотонно возрастающая последовательность pi,p¡,... ,Pt ~ допустимая последовательность простых чисел длины к для простого р, если для этой последовательности простых чисел выполнены условия

(27)

Из постулата Бертрана легко следует, что для любого простого нечетного р > 3 существует допустимая последовательность простых чисел произвольной дайны к.

Непосредственными вычислениями, используя таблицу простых, нетрудно проверить, что для простого р = 5 допустимой последовательностью простых дайной 6 будет последовательность 5,7,11,17,53,307, которая определяет модуль N = 106493695.

Для заданного фиксированного простого р, вообще говоря, существует несколько допустимых последовательностей простых чисел pi,p2,...,pk первого типа дайны к. Среди них можно выделить одну минимальную допустимую последовательность Р\,Р2, ■■■iPi, и одну максимальную р[, p'¡: • которые обладают свойством

Pi<Pi<P¡ (28)

для любой допустимой последовательности pi,p2,--.,pk с одним и тем же р. Тем самым определяется минимальный модуль N'p k = p¡ • p¿ ■ ... • рк и максимальный

■■■•Рк-

Например, для р = 5 минимальной допустимой последовательностью длины 6 будет последовательность 5,11,43,919, а максимальной — 5,7,11,19, 67,751. Соответственно, N¡¡fi = 5-7-11-13-23-89 = 10245235 и N'¿fi = 5-7-11 ■ 19-67-751 = ЗС8068855.

Будем предполагать, что заранее перед выполнением алгоритма затабулирована таблица функции 1п (2siu (тг{^})) для к = 1,2,...,Л- — 1, что потребует разового выполнения С ■ N машинных операций. Также будем предполагать, что имеется массив всех делителей числа Лг = Pi ■ ■. ■ ■ Рк, в котором 2к различных элементов, а также массивы значений функции Мебиуса и функцин Эйлера для каждого из этих делителей. Вычислении этих массивов потребует не более 0{\ÍÑ) элементарных арифметических операций, а для хранения — не более 0{y/Ñ) байтов объема оперативной памяти.

Таким образом, подготовительная часть нашего алгоритма имеет трудоемкость О(Л') элементарных арифметических операций, а дая храпения вспомогательных таблиц необходимо О(А') байтов объема оперативной памяти.

Теорема 23. (с. 172) Пусть K'{N) — количество элсментарнш- операций необходимых для вычисления величин а\,...,а, оптимальных коэффициентов по специальному модулю N индекса s. тогда справедливо первенство

А-'(Л')« 5s2CN (l-p + 32¡) = 5 ■ С ■ s2 ■ N ■ ■ р + , (29)

где С — максимальное количество элементарных операций для вычисления и ис-

дули N принадлежат показателю 0 с константой ^ • р +

В заключение выражаю благодарность своему научному руководителю профессору Чубарикову Владимиру Николаевичу за постановку задачи и внимание к работе.

Основное содержание диссертации отражено в работах:

В журналах из списка ВАК:

[1] Бочарова (Добровольская) Л. П., Ванькова В. С., Добровольский Н. М. О вычислении оптимальных коэффициентов // Математические заметки. 1991. Т. 49. Вып. 2. С. 23 - 28. - 0,38 п.л. (авт. вклад 50%)

В прочих изданиях:

[2] Бочарова (Добровольская) Л. П. Теорема А. О. Гельфонда и оптимальные коэффициенты для составного модуля // Чебышевский сборник 2005 Т. 6. Вып. 3(15). Тула, Из-во ТГПУ им. Л. Н. Толстого. С. 34 - 50.- 1 п.л.

[3] Бочарова (Добровольская) Л. П. О граничных функциях некоторых классов // Наукоемкое образование. Традиции. Инновации. Перспективы 2006, Сборник межвузовских научных статей, С. 198 — 202. — 0,31 п.л.

[4] Бочарова (Добровольская) Л. П. Алгоритмы поиска оптимальных коэффициентов // Чебышевский сборник 2007 Т. 8. Вып. 1(21). Тула, Из-во ТГПУ им. Л. Н. Толстого. С. 4 - 109. - 6,62 п.л.

[•5] Добровольская Л. П., Добровольский Н. М., Симонов А. С. О погрешности приближенного интегрирования по модифицированным сеткам // Чебышевский сборник 2008 Т. 9. Вып. 1(25). Тула, Из-во ТГПУ им. Л. Н. Толстого. С. 185 - 223. - 2,37 п.л. (авт. вклад 80%)

пользования одного множителя вида А — 21и

а специальные мо-

Подп. к печ. 17.11.2009 Объем 1 п.л. Заказ №. 181 Тир 100 экз. Типография Mill У

Введение

Глава 1. Меры качества для оптимальных коэффициентов

§1. Граничные функции некоторых классов .'.

§ 2. Граничные функции класса для формул приближенного суммирования .-.

§ 3. Несколько лемм о произведении синусов.

Глава 2. Теорема А. О. Гельфонда и оптимальные коэффициенты

§ 1. Суммы по приведенным системам вычетов

§ 2. Критерий оптимальности.

§ 3. Применение критерия оптимальности.

Глава 3. Алгоритмы поиска для произвольного N.

§ 1. Обобщенный критерий оптимальности

§ 2. Л-оптимальность

§ 3. Описание общего алгоритма.

§4. Применение разложения параллелепипедальной сетки на сомножители

§ 5. Обоснование алгоритма

§ 6. Трудоемкость алгоритма

§ 7. Оптимизация трудоемкости алгоритма.

Глава 4. Алгоритмы поиска для специальных N.

§ 1. Допустимые последовательности простых.

§ 2. Описание алгоритма для специальных модулей.

§ 3. Явные формулы для Т^ (z)

§ 4. Обоснование алгоритма для специальных модулей

§ 5. Трудоемкость алгоритма для специальных модулей

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

За пятьдесят лет развития теоретико-числового метода с 1957 года, когда вышла первая работа [29] Н. М. Коробова по этому направлению исследований, с которой и начинается отсчёт в становлении теоретико-числового метода в приближенном анализе, опубликовано значительное количество работ десятков авторов и в нашей стране и за рубежом. Краткая история возникновения этого метода описана её основателем в [42]. Теоретические предпосылки теоретико-числового метода восходят ещё к работе [51] Г. Вейля, вышедшей в 1916 году, в которой, с одной стороны, содержался интегральный критерий равномерного распределения последовательности по модулю 1, а, с другой стороны, в этой работе были получены первые нетривиальные оценки тригонометрических сумм. Именно применение оценок А. Вейля рациональных тригонометрических сумм было основополагающим при исследование первого класс теоретико-числовых сеток — неравномерных сеток.

Существенное изменение теории и практики вычисления кратных интегралов связано с появлением метода оптимальных коэффициентов Н. М. Коробова. Центральной проблемой в этом направлении исследований остается вопрос о построении экономных алгоритмов вычисления оптимальных коэффициентов. Именно этому и посвящена данная диссертация, что объясняет её актуальность.

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

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

Цель третьей главы — построение общего алгоритма вычисления оптимальных коэффициентов по произвольному составному модулю N, используещему логарифмическую меру качества, пригодных для комбинированных сеток.

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

Результаты работы являются новыми, полученными автором самостоятельно. Основными результатами данной работы можно считать следующие: дан новый критерий оптимальности набора коэффициентов, основанный на обобщенной теореме Гельфонда, для любого модуля N] введена новая мера оптимальности набора коэффициентов и дан обобщенный критерий оптимальности; построен общий алгоритм вычисления оптимальных коэффициентов для произвольного модуля N, основанный на минимизации обобщенной логарифмической меры качества; построены быстрые алгоритмы вычисления оптимальных коэффициентов для специальных модулей.

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

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

Результаты настоящей диссертации докладывались автором на следующих семинарах: научно-исследовательский семинар "Теория аппроксимации" под руководством профессора В. И. Иванова в Тульском государственном университете; научно-исследовательский семинар "Арифметика, алгоритмы, теория сложности вычислений" под руководством профессора В. Н. Чуба-рикова в Московском государственном университете им. М. В. Ломоносова; научно-исследовательский семинар "Теоретико-числовые методы приближенного анализа" под руководством профессора Н. М. Добровольского в Тульском государственном педагогическом университете им. Л. Н. Толстого; международной конференции "Аналитические и комбинаторные методы в теории чисел и геометрии" в Московском государственном университете им. М. В. Ломоносова. Москва, 2006.

Результаты диссертации опубликованы в работах автора [52], [53], [54], [55] и [56], выполненных по грантам РФФИ 05-01-00672 и 08-0100790.

Диссертация изложена на 181 страницах и состоит из введения, четырех глав и списка литературы, включающего 55 наименований.

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

2. Бахвалов Н. С., Коробов Н. М., Ченцов Н. Н., Применение теоретико-числовых сеток к задачам приближенного анализа // Труды Четвертого Всесоюзного математического съезда. Л.: Наука, 1964. Т. II. С. 580 587.

3. Боревич 3. И., Шафаревич И. Р. Теория чисел. М.: Наука, 1985.

4. Бухштаб А. А. Теория чисел. М.: Учпедгиз, 1960.

5. Ванькова В. С. Многомерные теоретико-числовые сетки: Дис. . канд. физ.-мат. наук. // Моск. пед. гос. ун-т. М., 1992.

6. Виноградов И. М. Основы теории чисел. М.: Наука, 1981.

7. Воронин С. М. О квадратурных формулах // Изв. РАН. Сер. мат. 1994. Т. 58. N 5. С. 189 194.

8. Воронин С. М. О построении квадратурных формул // Изв. РАН. Сер. мат. 1995. Т. 59. N 4.

9. Воронин С. М., Темиргалиев Н. О квадратурных формулах, связанных с дивизорами поля гауссовых чисел // Мат. заметки. 1989. Т. 46. N 2. С. 34 41.

10. Вронская Г. Т., Добровольский Н. М., Родионова О. В. Сравнения, суммы и произведения по приведенной системе вычетов // Известия ТулГУ. Сер. Математика. Механика. Информатика. Т. 8. Вып. 1. Тула, 2002. С. 10 28.

11. Гельфонд А. О. Исчисление конечных разностей. М.: Наука, 1967.

12. Добровольский М. Н., Добровольский Н. М., Киселева О. В. О произведении обобщенных параллелепипедальных сеток целочисленных решёток // Чебышевский сборник 2002 Т. 3. Вып. 2(4). Тула, Из-во ТГПУ им. Л.Н.Толстого. С. 43 59.

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

14. Добровольский Н. М. О квадратурных формулах на классах Ef(c) и Щ(с). Деп. в ВИНИТИ 24.08.84, N 6091-84.

15. Добровольский Н. М. Теоретико-числовые сетки и их приложения. Дис. . канд. физ.-мат. наук. Тула, 1984.

16. Добровольский Н. М. Многомерные теоретико-числовые сетки и решётки и их приложения: Дис. . док. физ.-мат. наук. Тула, 2000.

17. Добровольский Н. М., Ванькова В. С. Об одной лемме А. О. Гельфонда. Деп. в ВИНИТИ 08.01.87, N 1467-В87.

18. Добровольский Н. М., Есаян А. Р., Реброва И. Ю. Об одном рекурсивном алгоритме для решеток // Известия ТулГУ. Сер. Математика. Механика. Информатика. Т. 5 Вып. 3. Тула, 1999. С. 38 — 51.

19. Добровольский Н. М., Клепикова Н. Л. Таблица оптимальных коэффициентов для приближенного вычисления кратных интегралов // ИОФАН СССР. 63. Москва, 1990. (Препринт.)

20. Добровольский Н. М., Коробов Н. М. Оптимальные коэффициенты для комбинированных сеток. // Чебышевский сборник, Т. 2, Тула, 2001, С. 41 53.

21. Добровольский Н.М., Коробов Н.М. Об оценке погрешности квадратурных формул с оптимальными параллелепипедальными сетками // Чебышевский сборник. Научные труды по математике. Т. 3. Вып. 1(3). Тула, 2002. С. 41 48

22. Добровольский Н. М., Манохин Е. В. Банаховы пространства периодических функций // Изв. ТулГУ. Сер. Механика. Математика. Информатика. Т. 4. Вып. 3. Тула, 1998. С. 56 67.

23. Добровольский Н. М., Манохин Е. В., Реброва И. Ю., Аккурато-ва С. В. О некоторых свойствах нормированных пространств и алгебр сеток // Известия ТулГУ. Сер. Математика. Механика. Информатика. Т. 5. Вып. 1. Тула, 1999. С. 100-113.

24. Добровольский Н. М., Родионова О. В. Квадратурные формулы с обобщенными параллелепипедальными сетками // Изв. ТулГУ. Сер. Механика. Математика. Информатика. Т. 2. Вып. 1. Тула, 1996. С. 71 77.

25. Добровольский Н. М., Родионова О. В. Об одном конечном ряде Фурье и его приложениях // Изв. ТулГУ. Сер. Математика. Механика. Информатика. 1998. Т. 4. Вып. 3. С. 68 — 79.

26. Карацуба А. А. Основы аналитической теории чисел. М.: Наука. ФизМатЛит, 1983.

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

28. Колмогоров А. Н., Фомин С. В. Элементы теории функций и функционального анализа. М.: Наука, 1968.

29. Коробов Н. М. Приближенное вычисление кратных интегралов с помощью методов теории чисел // ДАН СССР. 1957. N 6. С. 1062 — 1065.

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

31. Коробов Н. М. О некоторых теоретико-числовых методах приближенного вычисления кратных интегралов. Резюме докл. на заседании Моск. мат. об-ва. // УМН. 1959. Т. 14. Вып. 2 (86). С. 227 230.

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

33. Коробов Н. М. Свойства и вычисление оптимальных коэффициентов // ДАН СССР 132. 1960. N5. С. 1009 1012.

34. Коробов Н. М. О применении теоретико-числовых сеток // Вычислительные методы и программирование: Сб. Моск. ун-т. 1962. С. 80 102.35