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

ВВЕДЕНИЕ

ГЛАВА I. Оценки погрешности приближения функций полиномиальными операторами

§ I. Постановка задачи и формулировка результатов

§ 2. Асимптотически наилучшее приближение непрерывных функций многих переменных операторами Бернштейна.

§ 3. Неравномерная оценка погрешности приближения функций многих переменных операторами Бернштейна

§ 4. Оценки погрешности приближения другими операторами

ГЛАВА П. Анализ сложности некоторых алгоритмов

§ I, Постановка задачи и формулировка результатов

§ 2. Сложности одномерных алгоритмов

§ 3. Сложности многомерных алгоритмов

ГЛАВА Ш. Некоторые методы моделирования распределений и анализ их сложности

ГЛАВА 1У. Асимптотические оценки трудоемкостей способов "выделение главной части11 (ВГЧ) и "существенная выборка" (СВ)

§ I. Постановка задачи и формулировка результатов

§ 2. Оценка трудоемкости способа ВГЧ

§ 3. Оценка трудоемкости способа СВ

§ 4. Одна модификация способа СВ.

Численные эксперименты.

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

Довольно плодотворным оказалось применение вероятностно-статистических методов (методы Монте-Карло). Простейший вариант этого метода дает кубатурную формулу вида:

А/ уф где л - независимые, равномерно-распределенные в единичном гиперкубе SL , точки. Удобство этого метода заключается в том, что в приведенной формуле можно брать достаточно большие N » т.к. все точки X^вычисляются по единому алгоритму, а порядок сходимости (по вероятности) не зависит от размерности (кратности интеграла) и равен N для функций f(X)€L2 • Формулам такого рода посвящены работы Н.С.Бахвалова, С.М.Ермакова, И.М.Соболя, Н.Н.Ченцова и других.

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

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

- выделение главной части (ВГЧ);

- существенная выборка (СБ);

- понижение порядка интегрирования;

- расслоенная выборка;

- случайные квадратурные формулы и др.

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

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

T = tx>? где t - время ЭВМ, затрачиваемое в среднем для получения одного значения Щ ; - выборочная диспресия статистической оценки искомого решения (см. напр. [l2, с. ).

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

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

В обоих способах, как правило, применяются некоторые аппроксимирующие аппараты. Например, в J в качестве такого аппарата были применены полиномиальные операторы Берн-штейна. Известно ^2oJ , что последовательность операторов Бернштейна равномерно сходится к аппроксимируемой функции yf в каждой точке X непрерывности £ • Кроме того, если / имеет непрерывную частную производную порядка К уш в точке л , то соответствующая частная производная поv(aJ линома Бернштейна в точке Л также сходится к значению этой производной. Таким образом, операторы Бернштейна достаточно хорошо учитывают особенности поведения функции f , Наряду с операторами Бернштейна мы будем применять полиномиальные операторы Хсу ^ЗО , которые обладают аналогичными свойствами (см. |30, 2 ), перечисленными выше для операторов Бернштейна. Кроме того, мы применяем аппроксимирующие аппараты вида кусочно-постоянной функции и линейного интерполяционного сплайна. Поэтому, тут возникают задачи, связанные с оценкой погрешности приближения этими операторами, оценкой сложности алгоритмов вычисления значения этих операторов в заданной точке и моделированием плотностей, имеющих структуру рассматриваемых операторов.

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

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

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

Первые три параграфа четвертой главы содержат результаты, касающиеся оценок трудоемкостей обоих способов понижения дисперсии. Четвертый параграф носит самостоятельный характер и посвящен одному частному случаю, предложенного в [27 ] способа интегрирования.

В заключении перечислены основные положения, выводимые на защиту.

Приложения содержат фортран-программы, составленные для реализации способов ВГЧ и СВ на ЭВМ, а также результатов численных экспериментов.

Результаты диссертации докладывались на всесоюзном семинаре-совещании по теории кубатурных формул и смежным вопросам (г. Бухара, 1983 г.), на семинарах кафедры статистического моделирования ЛГУ им. А.А.Жданова (г.Ленинград, 1982 г., 1983 г.), на семинарах отдела статистического моделирования ВЦ СО АН СССР (г. Новосибирск, 1980 г., 1984 г.), на семинаре отдела прикладных задач Института математики и механики Уральского филиала АН СССР (г.Свердловск, 1984 г.), а также на научных конференциях ТашГУ им. В.И.Ленина (г.Ташкент, 1978-1983 г.г.).

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

ЗАКЛЮЧЕНИЕ

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

Исследовано асимптотическое поведение трудоемкости способов "выделение главной части" (ВГЧ) и "существенная выборка" (СВ) при применении следующих аппроксимирующих операторов:

- операторы С.Н.Бернштейна (Вп),

- операторы, введенные в [ ](Нп),

- кусочно-постоянные функции (Рп)

- линейные интерполяционные сплайны (SPn)

I. Исследованы погрешности приближения аппроксимирующими операторами, где в частности:

1) получено асимптотически наилучшее приближение непрерывных функций многих переменных операторами Бернштейна;

2) получена неравномерная оценка для погрешности приближения функций многих переменных операторами Бернштейна;

3) построены многомерные аналоги операторов и получены оценки для погрешности приближения этими операторами.

П. Разработаны алгоритмы вычисления значений операторов Е>П} и SPo в заданной точке, где:

1) доказано существование асимптотически оптимального алгоритма в множестве всех алгоритмов, вычисляющих Д, ;

2) доказана невозможность построения асимптотически оптимального алгоритма в множестве всех алгоритмов, вычисляющих Н„ ;

3) для вычисления Рп и SPn построены алгоритмы, сложности которых не зависят от ;

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

1. Проведен анализ сложности двух методов моделирования случайных векторов, а именно:

1) стандартного метода моделирования дискретных случайных векторов;

2) метода суперпозиций.

IV. Исследованы оценки трудоемкостей способов ВГЧ и СВ в случае применения операторов &п, Нп , и SPn .

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

V. Предложен эффективный способ решения задач типа вычисления коэффициентов Фурье.

На основе этих исследований можно сделать следующие заключения.

1. Трудоемкости способов ВГЧ и СВ имеют одинаковую, возрастающую асимптотику, при применении операторов и Нп .

2. Асимптотически невозрастающую трудоемкость имеют способы ВГЧ и СВ, только в том случае, когда применены для вычисления &п и Н„ алгоритмы, основанные на случайную выборку, а также способ СВ при применении операторов Рп и SPn •

3. Асимптотически убывающую трудоемкость имеет способ ВГЧ при применении операторов Р^ и SP„ .

1. Азларов Т.А., Бабаев А. Асимптотически наилучшее при-ближение непрерывных функций многих переменных полиномами Бернштёйна. ДАН УзССР, 1984, № 4.

2. Азларов Т.А,, Мансуров X. О точности аппроксимациифункций полиномами одного класса. Изв. АН УзССР, сер. физ.-мат. наук, № 2, (1966).

3. Бабаев А. Оценка трудоемкости процедуры вычислениякратных интегралов методом Монте-Карло в случае способа "выделение главной части" (ВГЧ) с применением полиномов Бернштейна. Изв. АН УзССР, сер. физ.-мат. наук, № 4 (1982).

4. Бабаев А. Сравнение трудоемкостей двух процедур интегрирования методом Монте-Карло. ДАН УзССР, № б, 1982.

5. Бабаев А. О способах ускорения сходимости при вычислении интегралов по методу Монте-Карло. Вопр. вычислит. и прикл. математики, вып. 53, Ташкент, 1978, с. 8-17.

6. Бабаев А. О трудоемкости способа "выделение главнойчасти" (ВГЧ) с применением полиномов Бернштейна для некоторых классов функций. Труды ТашГУ, ПММ, вып. 670 (1981), с. 6-10.

7. Вороновская Е.В. Определение асимптотического видаприближения функций полиномами Бернштейна, ДАН (А), (1932), с. 79-85.

8. Голенко Д.И. Моделирование и статистический анализпсевдослучайных чисел на ЭВМ. М.: Наука, 1965.9. ^дман С., Хидетниеми С. Введение в разработку и анализ алгоритмов. М.: Мир, 1981.

9. Дзядык В.К. Введение в теорию равномерного приближения функций полиномами. М.: Наука, 1977.

10. Ермаков С.М. Метод Монте-Карло и смежные вопросы.1. Изд. 2, М.: Наука, 1975.

11. Ермаков С.М., Михайлов Г.А. Статистическое моделирование. М.: Наука, 1982.

12. Завьялов Ю.С., Квасов Б.И., Мирошниченко В.Л.

13. Метод сплайн-функций. Наука, 1980.

14. Кнут Д. Искусство программирования, т. 2, М.: Мир,1977.

15. Кондюрин Ю.Н. О моделировании случайных величин методом суперпозиций. IBM и МФ, 1970, 10, № I, с. 262-266.

16. Корн Г., Корн Т. Справочник по математике (для научных работников и инженеров), изд. 4, М.: Наука,1978.

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

18. Коровкин П.П. Линейные положительные операторы итеория приближения. М., Мизматгиз, 1959.

19. Куликов Л.Я. Алгебра и теория чисел. М., Высшаяшкола, 1979.

20. Мансуров X. Об одном методе улучшения сходимости втеории приближений. Изв. АН УзССР, сер. физ.-мат. наук, 3 (1962).

21. Михайлов Г.А. К вопросу о построении экономичныхалгоритмов моделирования случайных величин. IBM и МФ, 1966, 6, № 6, с. II34-II36.

22. Стечкин С.Б., Субботин Ю.Н. Сплайны в вычислительной математике. М.: Наука, 1980.

23. Тихомиров Н.Б. О применении метода Монте-Карло квычислению непрерывных функций. В сб.: Методы Монте-Карло в вычислительной математике и математической физике. Новосибирск, 1979, ч. I, с. 39-47.

24. Тихомиров Н.Б. О вероятностных аналогах теоремы

25. Коровкина. Применение функционального анализа в теории приближений. Калинин, 1973, с. 62-71.25. bu.tt£ez t J.VJ., Mctc/iu>e sim/>£injj fzo/r? ^cir&zо/? Af(?s?te С&гб'о //et/zocts, etf. //.A. f/a^ez, №.2W-26i

26. J~ssees7jC.6.; udezafce gesrdcstcc/7 A/^^rez. Sfctt/г. ^ 2c?6 /f£7£0J,27. £\SC£/7S y Orty yJ/yr&ec* /n^f^&^c srcz^fty?^ Tec/is7c>M7edz£cs ( /963J >T 3 ^ jVz-jJV.

27. Yozk «Z/саЫ. Sec . £6 (О J , fVV- S 7 V.29. r/&sr?s7?e2S fey, J./*/., Obvat /So:/7a!scc>sn£? .tt.C.,

28. Afо site. Саг £<? /VetAosct, Afet/te.a.'n, /.о/гс/о/7, /96V t /yp. /V3-/S/C.

29. Г7 C0/7/7ec£c0sr и/б£/г, ZG./7 0S&S7V //osrtafb/УОМеем T. t SecZ O^OyO zoxtlsnexr^osy fu.s7C.-6d0/7S co/7rexаё'аггэйе St^e*.a&/i.c.s77/2T^dca f CfctyJ <ы-гГУ

30. Pc?se/767ег/ ^ez^st.cc/7 гх^о/

31. Mo/76c- Caz£<? Crt tc-0 га zZcoos S/J*/ J. Mts&a ^36. SdXAresr?*2 , <г., Ыег