Интегрирование функций по выпуклым областям решетчатыми кубатурными формулами на многопроцессорных вычислительных системах тема автореферата и диссертации по математике, 01.01.07 ВАК РФ

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

Рахматуллин Джангир Ялкинович

ИНТЕГРИРОВАНИЕ ФУНКЦИЙ ПО ВЫПУКЛЫМ ОБЛАСТЯМ

РЕШЕТЧАТЫМИ КУБАТУРНЫМИ ФОРМУЛАМИ НА МНОГОПРОЦЕССОРНЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ

01.01.07 — вычислительная математика

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

Красноярск — 2006

Работз выполнена в Институте математики с вычислительным центром Уфимского научного центра РАН.

Научный руководитель: доктор физико-математических наук, • профессор Рамазанов Марат Давидович

Официальные оппоненты: доктор физико-математических наук,

доцент

Осипов Николай Николаевич

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

Васкевич Владимир Леонтьевич

Ведущая организация: Институт прикладной математики

М.В.Келдыша РАН (г. Москва)

Ззщипга состоится 21 декабря 2006 в 14 ч. 00 мин. на заседании диссертационного совета К 212.098.03 при Красноярском государственном техническом университете по адресу: 660074, г. Красноярск, ул. Корейского, 26, зуд. Г 4-17, факс (8-3912) 43-06-92, тел. 49-76-46.

С диссертацией можно ознакомиться в читальном зале библиотеки Красноярского государственного технического университета.

Автореферат разослан с_» ноября 2006.

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

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ -Актуальность темы. Кубатурной формулой К\}(/) называется линейный функционал, задающий приближенное значение интеграла

— J dxf (ж) по многомерной области П в виде линейной комбнна-п

цнн значений функции / в N произвольных точках—узлах кубатурной формулы:

ЛЛ « *$(/) = |>,{xW}^ е К». (0.1)

Теория кубатурных формул и их одномерных аналогов—квадратурных формул является хорошо развитой областью математического анализа и вычислительной математики. Данным научным направлением занималось множество" математиков —известны работы И.Ньютона, Л.Эйлера, К.Гаусса, Ш.Эрмита, русских и советских математиков П.Л.Чебышева, С. Н. Бернштейна, С.Л.Соболева, С.Н.Никольского и других. Теория квадратурных и кубатурных формул продолжает интенсивно развиваться и на сегодняшний день—по данной тематике публикуется множество работ и регулярно проводятся научные конференции.

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

Многие ученые, в частности, Н. С. Бахвалов, В. Н. Белых, О.В.Бесов, И.В.Бойков, В.Л.Васкевич, Я.М.Жилейкин, М.В.Носков, Н.Н.Осипов, В. И. Половинкин, М. Д, Рамаэаиов, Г.Н.Салихов, И. М. Соболь, Ц. Б. Шойнжуров занимались разработкой теории квадратурных и кубатурных формул в функциональных пространствах.

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

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

момент используются, в основном, методы и итерирования типа Монте-Карло, имеющие, однако, слабые стороны.

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

Актуальность проблемы обусловлена следующими факторами:

1) большой прикладной значимостью приближенного вычисления интегралов по областям больших размерностей

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

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

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

Результаты диссертации послужили основой отчетов по Программе № 17 фундаментальных исследований Президиума РАН «Параллельные вычисления на многопроцессорных вычислительных системах», по грантам РФФИ К* 03-07-90077-в «Создание библиотек программ для персональных и суперЭВМ» и № 02-01-01167-а «Теория приближенного вычисления многомерных интегралов». Целью работы является:

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

'Сы. Рахматуллил Д.Я. (Введите в MPI». • Уфа: РИД Ваш ГУ, 2006., Том 1.

s

является стандартная параллельная программа, предназначенная ■для использования в суперкомпьютерах с МРР (Massively Parallel Processing - массовый параллелизм) архитектурой — многопроцессорных системах с распределенной памятью.

2) Теоретическое исследование решеток узлов, дающих наилучший порядок приближения для оптимальных кубатурных формул в веизо-тропном пространстве IV^fK2)

Научная новизна. В диссертации получены следующие основные научные результаты:

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

2) Предложенный алгоритм преобразован в алгоритм для использования на многопроцессорных вычислительных системах; он реализован в виде параллельной программы, эффективно использующей возможности передовых технологий (суперкомпьютеров), языков программирования (С++ и MPI) и превосходящей имеющиеся

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

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

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

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

Теоретическая и практическая ценность. Результаты диссертации могут быть использованы в задачах, требующих достаточно быстрого и точного счета многомерных интегралов с размерностями до 10. Предложенные способ построения решеток узлов в пространстве неизотропной гладкости И^1Г(К2) может использоваться как в теоретических исследованиях, так и вычислительных разработках.

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

Апробация результатов. Основные результаты работы были доложены и получили положительную оценку на следующих конференциях: «Кубатурные формулы и их приложения», VIII Международный семинар-совещание 15-22 августа 2005 года. г. Улан-Удэ; «V Региональная школа-конференция для студентов, аспирантов и молодых ученых по математике и физике», Уфа, БашГУ, 27-28 октября 2005 года; чМеждународная уфимская зимняя школа-конференция по математике и физике с участием студентов, аспирантов и молодых ученых», Уфа, БашГУ, 30 ноября -06 декабря 2005 года; «VI Всероссийская молодежная школа-конференция „Численные методы решения задач математической физики"», Казань, НИИММ, 26 июня - 1 июля 2006 года.

Публикации. Основное содержание диссертации отражено в 5 научных работах, одна из которых опубликована в научном журнале, включенном в Перечень ВАК.

Структура и объем работы. Диссертация состоит из введения, двух разделов, заключения, библиографического списка, включающего 50 наименований, и 2 приложений. Работа изложена на 114 листах машинописного текста, содержит 17 рисунков и 13 таблиц.

СОДЕРЖАНИЕ ДИССЕРТАЦИИ

Во введении определяются объект, предмет, цели и методы исследо-

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

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

1. Численное интегрирование по многомерным областям

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

Пусть задана ограниченная область О С К" с гладкой границей дй.

Рассмотрим пространство Соболева р > 1, то > ~ периоди-

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

Г 4

£ 9к (1 + |2тг*|)га/ге2"** \ , (0.2)

Ф)^ дь* ¡¿х д(х)е~™*\ (0.3)

йег- £

где ф—единичный гиперкуб: (¿ = {х : зц е [0; 1), г = 1,п }.

Взяв это пространство за основу, построим новое пространство И^ЧП) с нормой

Требуется приближенно вычислить интеграл произвольной функции / € по области

Мы решаем эту задачу путем приближения интеграла решетчатыми кубатурными формулами с ограниченным пограничным слоем (ОПС-формулами). Поясним эти термины.

Решеткой узлов назовем множество {ЛЯй}*^-, где Ле К, Л > О, Я—матрица п х п, — I. Устремив к к нулю,

получим последовательность решеток со сгущающимися узлами. Мы будем рассматривать частный случай —Я = 1, т.е. последовательность решеток {ЛЬ}*^», называемую прямоугольной (кубической). Заметим, что выбор решетки вполне согласуется с изотропностью нашего пространства—функции из него по всем направлениям имеют одну и ту же гладкость т.

Кубатурной формулой (КФ) К$(/) назовем линейный функционал,

задающий приближенное значение интеграла /"(/)= / <кс$(х) ввидели-

_ п

иейной комбинации значений функции / е в N произвольных

точках—узлах кубатурной формулы:

*£(/) = е к". (0.5)

КФ называется решетчатой, если ее узлы лежат на решетке узлов. Мы будем рассматривать последовательности решетчатых кубатур-ных формул {К^ (/)} ) соответствующие последовательностям решеток со сгущающимися узлами Л —► 0:

*?(/) = ЛЛ £ <*(Л)/(Л*), Л^О. (0.6)

Здесь за знак суммы вынесен масштабный множитель Л", равный объему элементарной (наименьшей) ячейки, образуемой узлами решетки.

Для согласовывания решетки узлов с периодичностью функции из пространств \¥™{С1) накладывается ограличение, носящее технический характер: Н —* 0 так, что \ остается целым числом.

Будем говорить, что КФ обладает ограниченным пограничным слоем (ОПС), если выполнены следующие два условия:

1) коэффициенты КФ равномерно ограничены по к и Л :

3 11 : вир |с^(Л)[ < Ь1 ; к, Л

(0.7)

Э : УЛ, к : (р(Нк, Е"\П) > Ь2Н) ск(Ь) « 1, (0.8)

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

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

Для оценки качества КФ введем понятие функционала погрешности (ФП). Функционалом погрешности /£(/), соответствующим КФ называется линейный функционал, представляющий собой разность точного значения интеграла /п(/) функции по области П и кубатурной формулы К%(/) :

(0-9)

или в виде обобщенной функции:

= ХФ) ~ - А*). (0.10)

ШеП,

где Хп / н-» / = ¿<1х/(х).

о

Мы также будем опускать слово «последовательность» для последовательностей функционалов погрешности, соответствующих последовательностям кубатурных формул (ПКФ), отмечая лишь стремление Л к нулю.

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

(0-11)

Желание использовать лучшие для данной последовательности решеток кубатурные формулы приводит нас к понятию оптимальной КФ, а также асимптотически оптимальной и оптимальной по порядку КФ.

КФ, минимизирующая при любом фиксированном А нормы элементов соответствующего ФП, называется оптимальной:

тЬ. (0.12)

На практике оптимальные КФ трудновычислимы, поэтому часто ограничиваются рассмотрением КФ, имеющим оптимальные свойства лишь в пределе, при к —► 0.

КФ называется асимптотически оптимальной, если выполняется равенство:

11ш " ТУ?™ = (013)

называется оптимальной по порядку, если

. 1Е < С- (0.14)

Зададимся произвольным целым числом М, таким, что М > М. Д. Рамазановьщ создан алгоритм вычисления КФ, оптимальной по порядку на каждом из пространств с т = , т.е. универ-

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

ЭС: С7Г, (0.15)

Такая КФ также будет являться универсально асимптотически оп-тималъ7юй.

Теорема (М Д. Рамазанов). ПКФ с ОПС асимптотически оптимальна на каждом пространстве из множества

тогда и только тогда, когда она оптимальна на каждом из них по порядку, при р < mi < wia < М, 1 < pi < р2 < со-

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

Алгоритм был доработан и оптимизирован диссертантом. Приведем его окончательный вид.

Пусть П — выпуклая область, лежащая внутри единичного гиперкуба вместе с замыканием: П с int Q, а параметр h стремится к нулю по одной из последовательностей, каждый член которой можно представить в виде N'1, где N е N.

Алгоритм основан на сведении задачи интегрирования по области с гладкими границами к нескольким однотипным задачам интегрирования по единичному гиперкубу. Эту последнюю задачу решает функционал погрешности

!>(£-*)' (0Л7> ftjteQ

где

(0-18)

Здесь х € R™, S С Zn, S — конечное множество, в качестве которого мы берем

S=Si х ... х ¿?„, S\ = ... = + 1}. (0.19)

На функционал А (ж) накладывается ограничение — он должен иметь порядок М, т.е. удовлетворять условию

(А(х),ха) = 0, |а| < М, (0.20)

где а — мультииндекс.

ТЬгДа ФП q^{x) является оптимальным по порядку на функциях из пространств■ W™(R")> W™(Q) и имеет порядок 0(hm):

llî?ll(îv™(Q))- х 0(hm), (0.21)

где символ обозначает двустороннюю оценку.

Случай il — произвольной области с гладкой границей dii, вложенной в единичный гиперкуб Q, сводится к разобранному случаю следующим образом.

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

1) они являются периодическими с основным периодом Q и в сумме составляют функцию, тождественно равную единице в периодически продолженной с основным периодом Q фиксированной окрестности Û области О, целиком лежащей в гиперкубе Q;

2) они принадлежат пространству CM{Q)\

3) носитель1 одной из срезывающих функций лежит полностью внутри области il, не пересекаясь с ее границей; пересечение носителя каждой из остальных срезывающих функций с границей ôiï непусто и гладко (класса См) и взаимно однозначно проектируется на одну из координатных гиперплоскостей;

Примем количество срезывающих функций за Т -Ь1. Обозначим их

как

Т

s 1. . (0.22)

ТшО

Функцию <ро(х) подберем так, чтобы множество точек £у0, где она равна единице, находилось не ближе, чем на расстоянии £о < з от границы области:

р{Е^,Жп\fî)ïï£o, £U = {ar: = (0-23)'

Введем обозначения Тт = suppyr ПП и Гг = supp tpT П Ôiî.

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

Интеграл / с1х/(х) можно представить в виде суммы интегралов:

п

= У<йе Рг(*)/(®). (0.24)

(1 т_0 Тт

Для удобства программной реализации, область О будем задавать неявно—как множество точек, где неотрицательна гладкая функция Ф(я):

: Ф(гс) 0>, Ф(я) е СМ{Я). (0.25)

При этом граница задается как

Ж={х: Ф(х) = 0}. (0.26)

Пусть градиент функции Ф(х) на границе не обращается в ноль:

УФ(®)|й, ф 0. ' (0.27)

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

Ут 3 ¿т, : Гг = {х € Тт : х}т = (0.28)

где ^ - -., Х^-и • • •»»«)•

Если каждой области Тт сопоставить ФП

= ХтМ - £ сЦЬЩх-Ьк), (0.29)

М!»

то общий функционал погрешности можно собрать из таких функционалов следующим образом:

т

#00* 5>(0.30)

т«0

При этом коэффициенты сь(/ь) функционала погрешности $ (з) получаются следующим образом:

Т -

е*(Л) = (0-31)

г=0

Тал как в определении ФП $(аг) каждый ФП умножен на срезыва-

ющую функцию <рт(ж), мы можем в дальнейшем доопределять ^(х) вне зирр <рт(%), не изменяя итоговой суммы.

Для того, чтобы ФП был оптимальным по порядку в достаточно оптимальности по порядку каждого из функционалов Ниже для произвольного г подберем коэффициенты с£(Л) так, чтобы выполнялось ¡¡£т||(й^(П)). 0(Лт).

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

Гг^{хеТг: х„ = 7С0}, «'«(iBi.....я^-i).

■ Во-вторых, пусть

Xn>l№), Ух € Тг.

(0.32)

(0.33)

Тогда искомые коэффициенты локальной КФ выражаются следующей формулой1:

4(h) =

М+1 М+1 mlnfJ^-CT-^M+l} mln{fc„-ir-i,Ai+l}

i—l

0,

1-1

Г=1

к* < 1 + а,

(0.34)

Здесь — элементы матрицы, обратной к матрице, имеющей

определитель Вандермонда:

7 1° 2° ... (М + 1)0 4 l1 21 ... (Л/ + 1)1

(0.35)

2м ... (М+1)м ;

а <7 и Г?—целая и дробная части числа

Итоговые коэффициенты находятся по формуле (0.31).

'См. Рймизшол МД. Лекция по т»орви ку6»турин* формул. — Уфа; Изд-во БашГУ, 1973. —177

Формула (0.34) для ускорения счета изменена диссертантом следующим образом: ;

сйп{(»,Л1} М ,

«Л) = (М> (0.36)

„о, С < о.

Здесь t' = У, tn^kn-<7 -2; Vij =«¡+1, i+i, tJ=0,Af;

^-Е^гтЕ^ i = ™ (0.37)

н^ i-О

Заметим, что, в отличие от формулы (0.34), в формуле (0.36) явно выделены множители Ai, которые для каждого M можно вычислить заранее, избавившись от необходимости пересчитывать четыре вложенные суммы в правой части (0.34) в каждой точке.

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

По алгоритму была написана многопроцессорная программа на языке С-1—|- с библиотекой параллельных функций MPI. Расчеты проводились со следующими входными данными:

• Количество процессоров Р — от 1 до 1000.

• Подынтегральная функция f(x) = 1.

• Размерность п—от 2 до 10.

• Гладкость М—от 2 до 6.

• Функция, задающая область £"! : Ф(а?) = 1 — — 1)

(«О

• Число точек на ребре гиперкуба N = £ — от 10 до 10s.

В таблице 1 приведены погрешности вычислений для двумерного случая, в таблице 2 —для четырехмерного, в таблице 3—для десятимер-

Ткблица 1. n = 2

N \ M 2 - 3 4

100 2.92E-06 4.64E-05 2.31E-04

1000 4.04E-09 1.61E-11 8.50E-13

2000 5.00E-10 1.51E-12 2.04E-14

3000 1.48E-Ï0 3.40E-13 1.55E-15

4000 6.26E-11 1.33E-13 3.33E-16

5000 3.21E-11 4.87E-14 1.33E-15

10000 4.03E-12 0.00E+00 1.11E-16

N\M 5 6

100 6.35E-04 6.18E-03

1000 4.00E-15 5.44E-15

2000 1.78E-15 2.22E-15

3000 : 4.44 E-16 O.OOE+00

4000 1.78E-15 1.44E-15

5000 2.22Б-16 5.55 E-16

10000 1.11E-16 1.11E-16

Ткблица 2. n = 4

N\M 2 3 4

60 4.78E-06 1.18E-05 9.68E-05

70 3.84E-07 5.42E-09 1.28E-09

80 1.13E-07 6.51E-10 4.56E-11

SO 4.78E-08 1.24E-U 5.18E-11

100 2.22E-0S 1.33E-11 7.57E-11

150 1.48E-08 1.74E-11 3.35E-11

200 8.47E-09 9.85E-11 'L92E-11

250 2.81E-09 1.04E-11 1.31E-13

N\ M 5 6

60 1.32E-04 1.67E-03

70 9.87E-10 5.12E-08

80 2.87E-10 3.49E-10

90 5.37E-11 7.98 E-11

100 4.55E-11 8.06E-11

150 1.52E-11 1.32E-11

200 7.21E-12 8.6SE-12

250 1.55E-12 1.65E-12

Таблица 3. n = 10

N\M, 2

10 4.19Е-05

11 1.15Е-04

12 1 8.51Е-05

Анализ результатов вычислений показал, что точность счета во многих случаях не уступает теоретической, а порой даже превосходит ее на несколько порядков. Исключение составляют случаи, когда М велико при малом N (т.е. слишком широк пограничный слой толщины 2Mh). Естественное ограничение на точность вычислений налагается конечным количеством верных цифр (15) типа данных double. С ростом размерности увеличивается количество множителей и слагаемых, из которых составляются срезывающие функции, что также ухудшает точность. Однако эксперимент с десятимерным интегралом показывает, что при малом М можно добиться удовлетворительного результата даже при N = 10.

Перейдем теперь к анализу быстроты счета и качества распараллеливания программы. Рассмотрим, для примера, результаты счета для п = 3,Л/ = 2,N = 1000. Для анализа качества распараллеливания введем понятия ускорения и эффективности программы:

Т 5

Sp = (ускорение), Ер = — (эффективность), lp f

где Тр — время, за которое задача выполняется на Р процессорах. Будем

варьировать Р от 100 до 1000 с шагом 100. При этом положим Т\ =

100 Гц». На рис. 1 показано отклонение экспериментального ускорения

Sp (темная ломаная) от идеального ускорения (светлая прямая).

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

Второй раздел диссертации посвящен теоретическому результату, полученному совместно М.Д, Рамазановым и Д.Я. Рахматуллиным. В отличие от пространства iV^(il) функций, имеющих одинаковую по всем направлениям гладкость т, здесь рассматривается неизотропное пространство H^fE®), М = (тьггсг) размерности 2. Исследуются после-

Experiment

Рис. 1. Зависимость ускорения от числа процессоров (п=3)

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

N

<**(/) = (0.38)

Awl

где функции / принадлежат банахово му пространству Bt называется наилучшей, если при любом фиксированном N она минимизирует норму ее разности с точным значением интеграла Iя как по набору коэффициентов {£*,«}> так и по расположению узлов {я^}:

К^Шьщ шш||— /п||е, нarg (0.39)

ПКФ называется наилучшей по порядку, если выполняется

неравенство:

ЗС : ТЕГ !J"~Kin,!B' ^ С. (0.40)

Известен наилучший возможный порядок приближения в гг-мерном пространстве Wj^R"), т = (mi,...,mn) интегралов по ограниченной

области с помощью кубатурных формул вида (0.38):

= (,<«,> И^И™- = С <°'41>

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

/^(Ль-..,/*), АГ = -.. = А?".

Еще большее родство с темой первого раздела диссертации дает выносимый на защиту результат. Оказывается, в двумерном случае наилучший порядок аппроксимации достигается и на кубических решетках за счет поворота на угол в, тангенс которого есть «золотое сечение», а. = tgв = -Ц^. То есть следует взять последовательность решеток узлов (не зависящую от параметров гладкости пц и тг)-

г 5 ^ соэ 0) \-а \ } ^ '

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

Приведем теперь формальную постановку задачи. Пусть П обладает кусочно-гладкой границей и лежит в круге {х: |ж| < ф < 1}.

Функционал погрешности кубатурной формулы с кубической решеткой узлов {ННк},к 6 23, где Н находится из (0.42), имеет вид

СЯК> = Хп(*)-Аа £ съ^х - кНк). (0.43)

1 Си. Соболев С Л., Васкемм В Л. Кубиурнъи формулы. Новосибирск; ГЬд-во ИМ СО РАН, 1996. Стр. 259

В работе показывается, что вычисление порядка сходимости ФП ■ (0.43) в пространстве сводится к оценке суммы

для которой при условии ГП2 > тп\ ^ | получаем искомую оценку сверху

£(Л) ^ СЛ^ч+^а = СN »1+™». Теорема. Решетчатые кубатурние формулы вида

*?(/)= £ а(Л)/(ЛЯЙ), Л->0 (0.44)

ПНкСП

с узлами на кубической решетке

и оптимальные по порядку в неизотропном пространстве И^(К2), Щ = (тьт2), 1шп{т1,т2} > -являются в нем наилучшими по порядку.

ЗАКЛЮЧЕНИЕ

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

В диссертации предложен, реализован и проанализировав один из самых быстрых и точных способов приближенного интегрирования по многомерным выпуклым областям с гладкими границами по функциям различной гладкости (из пространства с т = 2..6). За основу бе-

рется алгоритм1 М.Д. Рамазанова, модифицированный и реализованный в виде стандартной параллельной программы автором диссертации.

Полученный результат обладает как вычислительными достоинствами (точностью, быстродействием, эффективностью, масштабируемостью

1Сы., например, Соболев С Л, Васкевяч В Л. Кубатурньк формулы. Новосибирск-. Изд-во ИМ СО РАН, 1096. 484с. С 354-363.

на. произвольное количество процессоров, переносимостью на любые платформы, совместимые с библиотекой MPI), так и теоретическими —строгим обоснованием алгоритма и гарантированной оценкой погрешности вычислений. Теоретическое обоснование стало возможным благодаря достижениям теории кубатурных формул, развитой С.Л. Соболевым и продолженной его последователями, в частности М.Д. Рамазановым.

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

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

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

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

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

ПУБЛИКАЦИИ

Основное содержание диссертации изложено в публикациях:

1) Рам азанов М. Д., Рахкатуллин Д. Я. Достижение наилучшего порядка приближения интегралов функций из И^Ш2) на решетчатых

кубатурных формулах за счет поворота решетки узлов // Материалы VIH международного семинара-совещания 15-22 августа 2005 г., ВСГТУ, г. Улан-Удэ. — 2005. — С. 109-116.

2) Рахматуллин Д. Я. Вычисление интегралов по многомерным обла-

- стям на многопроцессорных вычислительных системах // Международная уфимская зимняя школа-конференция по математике и физике с участием студентов, аспирантов и молодых ученых, Бага ГУ, Уфа, 30 ноября - 06 декабря 2005 года. - Уфа: РИО БашГУ, 2005. - С. 151-157.

3) Рахматуллин Д. Я. Достижение наилучшего порядка приближения интегралов функций из в частных случаях // V Региональная школа-конференция дня студентов, аспирантов и молодых ученых по математике и физике: Тезисы докладов. — Уфа: РИО Б а-шГУ, 2005. —С. 20.

4) Рахматуллин Д. Я. Вычисление интегралов по многомерным областям на многопроцессорных вычислительных системах // Вычислительные технологии. 2006, —Т. 11, №3. —С. 118-125.

5) Рахматуллин Д. Я. Интегрирование на суперкомпьютере. Математика. Механика. Информатика: Тез. докл. Всерос. науч. конф., Челябинск, 19-22 сентября 2006 г. — С. 114.

Рахматуллин Джангир Ялшнович

ИНТЕГРИРОВАНИЕ ФУНКЦИЙ ПО ВЫПУКЛЫМ ОБЛАСТЯМ РЕШЕТЧАТЫМИ КУБАТУРНЫМИ ФОРМУЛАМИ НА МНОГОПРОЦЕССОРНЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ

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

Лицензия на издательскую деятельность ЛР№ 021319 от 05.01.99 г

Подписано в печать 09.11.2006 г. Бумага офсетная. Формат в0х84Н6. Гарнитура Times. Отпечатано на ризографе. Усл. печ. л. 1,26. Уч.-изд. л. 1.52. Тираж 100 экз. Заказ 808,

Редакционно-из дательский центр Башкирского государственного университета 450074, ре, г. Уфа, ул. Фрунзе. 32,

Отпечатано на множительном участке Башкирского государственного университета 450074, РБ, г. Уфа. ул. Фрунзе, 32.

Введение.

§1 Основные положения диссертации.

§2 Краткая история вопроса.

§3 Список основных обозначений.И

I Численное интегрирование по многомерным областям.

§1 Общая постановка проблемы.

§2 Алгоритм.

§3 Модификация алгоритма.

§4 Программа.

§5 Вычислительный эксперимент.

II Наилучший порядок приближения интегралов функций из

Wf{ R2).

§1 Постановка задачи.

§2 Теорема о достижении наилучшего порядка на решетчатых формулах.

§3 Вычислительный эксперимент.

§1. Основные положения диссертации

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

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

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

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

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

Вот почему так важно квалифицированное отображение математических достижений в «механическую» плоскость.

Объектом исследования данной диссертации является приближенное интегрирование функций по многомерным областям (УДК 519.644 + 517.518.87).

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

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

Кубатурной формулой (КФ) назовем линейный функционал, задающий приближенное значение интеграла /п(/)— f dxf(x) в виде лип нейной комбинации значений функции / £ W™(Q) в N произвольных точках — узлах кубатурной формулы: k=1 ' Перечислим основные методы построения кубатурных формул.

• Вероятностные методы типа Монте-Карло.

• Методы построения формул высокого алгебраического порядка (точных на многочленах большой степени) и инвариантных относительно некоторой группы изометрических преобразований.

• Функциональные методы построения решетчатых кубатурных формул.

• Теоретико-числовые методы построения формул, точных для конечных тригонометрических рядов.

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

Слабыми сторонами вероятностного подхода, однако, являются

• малый порядок сходимости кубатурных формул

• вероятностные оценки точности формул

• «подстроение» класса интегрантов под свойства решений интегральных уравнений, а также итерационный метод их решения

Существуют также программы, реализующие методы решетчатых кубатурных формул, созданные в разные годы Н. И. Блиновым [3, 2], JI. В. Войтишек [10], И. Умархановым [45], а также на основе методов теоретико-числового анализа, созданные Н. М. Коробовым [14]. Их основные недостатки:

• малая доступная размерность пространства интегрирования (не больше трех)

• малая точность вычислений

• реализация на устаревших языках программирования и, следовательно, плохая переносимость программ

• реализация на устаревших вычислительных платформах, а значит, отсутствие возможности реального применения на практике

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

• большой прикладной значимостью приближенного вычисления интегралов по областям больших размерностей

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

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

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

Для решения указанной выше проблемы определим предмет исследований — решетчатые кубатурные формулы с ограниченным пограничным слоем.

Основными целями данной диссертации являются:

• решение задачи численного интегрирования функций по многомерным областям. В качестве теоретической базы используется аппарат решетчатых кубатурных формул с ограниченным пограничным слоем. Посредником, обеспечивающим преобразование математического алгоритма в машинный, является язык программирования С++ [25] с библиотекой параллельных функций MPI [36]. Конечным результатом является стандартная параллельная программа, предназначенная для использования в суперкомпьютерах с МРР (Massively Parallel Processing - массовый параллелизм) архитектурой — многопроцессорных системах с распределенной памятью.

• теоретическое исследование решеток узлов, дающих наилучший порядок приближения для оптимальных кубатурных формул в неизотропном пространстве ТУ™ (К2)

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

• теоретические методы функционального анализа

• теоретические методы вычислительной математики

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

Перечислим результаты, выносимые на защиту (попутно отмечая их новизну).

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

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

• Создана параллельная программа, эффективно использующая возможности передовых технологий (суперкомпьютеров) и языков программирования (С++ и MPI).

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

• Впервые была произведена модификация существующего алгоритма, оптимизирующая его программную реализацию.

• Найден новый способ построения решеток узлов в пространстве W^iR2), на которых оптимальные формулы имеют наилучший порядок приближения.

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

• Экспериментально исследованы вычислительные свойства предложенного способа, сделаны выводы.

Основные результаты диссертанта отражены в работах [29, 34, 35, 37,

38].

Заключение

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

В диссертации предложен, реализован и проанализирован один из самых быстрых и точных способов приближенного интегрирования по многомерным выпуклым областям с гладкими границами по функциям различной гладкости (из пространства W™(Cl) с т = 2.6). За основу берется алгоритм М.Д. Рамазанова, дополненный, оптимизированный и реализованный в виде стандартной параллельной программы автором диссертации.

Полученный результат обладает как вычислительными достоинствами (точностью, быстродействием, эффективностью, хорошей масштабируемостью на произвольное количество процессоров, переносимостью на любые платформы, совместимые с библиотекой MPI), так и теоретическими — строгим обоснованием алгоритма и гарантированной оценкой погрешности вычислений. Теоретическое обоснование стало возможным благодаря достижениям теории кубатурных формул, развитой C.JI. Соболевым и продолженной его последователями, в частности М.Д. Рамазановым.

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

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

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

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

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

1. Блинов Н. И. Приближенное вычисление двойных интегралов // Ан-нот. сб.: Алгоритмы и программы. ВНТИ центр. — 1974. — № 2, 3.

2. Блинов Н. И. Алгоритм для вычисления кратных интегралов от функций с особенностями // Аннот. сб.: Алгоритмы и программы. ВНТИ центр. 1977. - № 2.

3. Васкевич В. Л. О сходимости квадратурных формул Грегори // Докл. АН СССР. 1981. - Т. 261, № 5. - С. 1041-1043.

4. Васкевич В. JI. Об одной задаче теории квадратурных формул. — Препринт АН СССР. Сиб. отд-ние. Институт математики, Новосибирск, № 3.- 1982.

5. Васкевич В. Л. Кубатурные формулы в гармонических пространствах типа Бергмана-Половинкина // Кубатурные формулы и их приложения. Доклады III семинара-совещания. — Уфа: ИМВЦ УНЦ РАН, 1996. С. 4-13.

6. Васкевич В. JI. Гарантированная точность вычисления многомерных интегралов: Дис. . д-ра физ.-мат. наук. — Новосибирск, 2003. — 243 с.

7. Виноградов И. М. К вопросу об оценке тригонометрических сумм // Изв. АН СССР. 1965. - Т. 29, № 3.

8. Войтишек А. В. Использование аппроксимационных функциональных базисов в методах Монте-Карло // Кубатурные формулы и их приложения. Материалы VII семинара-совещания. — Красноярск, 2003. — С. 45-53.

9. Войтишек Л. В. Об одном частном случае построения кубатурных формул с пограничным слоем // ЖВМ и МФ. — 1969. — Т. 9, № 2. — С. 774-781.

10. Игнатьев А. Н. Универсальный алгоритм вычисления интегралов по ограниченным областям с гладкими границами // Кубатурные формулы и их приложения: Доклады, представленные на III семинар-совещание. Уфа, ИМВЦ УНЦ РАН, 1996. - С. 21-31.

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

12. Коробов Н. М. Вычисление кратных интегралов методом оптимальных коэффициентов // Вестник МГУ. — 1959. — № 4.

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

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

15. Лебедев В. И. О квадратурах для сферы // Журн. вычисл. математики и мат. физики. 1976. - Т. 16, № 2. - С. 293-306.

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

17. Никольский С. М. Квадратурные формулы. — М.: Наука, 1979. — 256 с.

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

19. Носков М. В. О декартовых произведениях кубатурных формул. — Новосибирск: Наука, 1980.— 114-116 с.

20. Осипов Н. Н. Минимальные кубатурные формулы для тора и сферы: Автореферат дис. . д-ра физ.-мат. наук. — Красноярск, 1997. — 14 с.

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

22. Осипов Н. Н. Кубатурные формулы для периодических функций: Дис. . д-ра физ.-мат. наук. — Красноярск, 2005. — 192 с.

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

24. Подбельский В. В. Язык Си++: Учеб. пособие. — М.: Финансы и статистика, 2004. — 560 с.

25. Половинкин В. И. О кубатурных формулах с регулярным пограничным слоем // Сиб. мат. журн. 1972. - Т. 13, № 4. - С. 951-954.

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

27. Рамазанов М. Д., Шадиметов X. М. Весовые оптимальные кубатурные формулы в периодическом пространстве Соболева // Докл. РАН. — 1999. Т. 368, № 4. - С. 453-455.

28. Рамазанов М. Д. Лекции по теории кубатурных формул. — Уфа: Изд-во БашГУ, 1973. 177 с.

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

30. Рамазанов М. Д. Теория решетчатых кубатурных формул с ограниченным пограничным слоем // Кубатурные формулы и их приложения: Доклады, представленные на III семинар-совещание. — Уфа, ИМВЦ УНЦ РАН, 1996.-С. 77-89.

31. Рахматуллин Д. Я. Вычисление интегралов по многомерным областям на многопроцессорных вычислительных системах // Вычислительные технологии. 2006. - Т. 11, № 3. - С. 118-125.

32. Рахматуллин Д. Я. Интегрирование на суперкомпьютере // Математика. Механика. Информатика: Тез. докл. Всерос. науч. конф., Челябинск. Челябинск: ЧГУ, 2006. - С. 114.

33. Салихов Г. Н. К теории кубатурных формул на сферах // Теория кубатурных формул и приложения функционального анализа к некоторым задачам математической физики. — 1973. — С. 22-27.

34. Соболев С. Л., Васкевич В. Л. Кубатурные формулы. — Новосибирск: Изд-во ИМ СО РАН, 1996. 484 с.

35. Соболев С. Л. О кубатурных формулах на сфере, инвариантных при преобразованиях конечных групп вращений // Докл. АН СССР. — 1962. Т. 146, № 2. - С. 310-313.

36. Соболев С. Л. О числе узлов кубатурной формулы на сфере // Докл. АН СССР. 1962. - Т. 146, № 4. - С. 770-773.

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

38. Соболь И. М. Численные методы Монте-Карло. — М.: Наука, 1973. — 311 с.

39. Умарханов И. Построение и обоснование решетчатых кубатурных формул для областей с кусочно-гладкими границами: Дис. . канд. физ.-мат. наук. — Ташкент: ТашГУ, 1986. — 173 с.

40. Шойнжуров Ц. Б. Некоторые вопросы теории кубатурных формул в пространстве w™ // Сиб. мат. жури. — 1967. — Т. 7, № 2. — С. 41-45.

41. Шойнжуров Ц. Б. Некоторые вопросы теории кубатурных формул в неизотропных пространствах C.JI. Соболева // Докл. ДАН СССР. — 1973. Т. 209, № 5. - С. 1036-1038.

42. Ramazanov М. D. То the Lp-theory of Sobolev formulas // Siberian advances in mathematics. — 1999. — Vol. 9, no. 1. — Pp. 99-125.

43. Sard A. Best approximate integration formulas, best approximate formulas 11 Amer. J. Math. 1949. - Vol. 71. - Pp. 80-91.

44. Stroud A. H. Approximate calculation of multiple integrals. — Englewood Chiffs, New Jersey: Prentice-Hall, 1971.