Решение экстремальных задач при моделировании случайных размещений тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат физико-математических наук Гильманшин, Роман Ралифович

• Гильманшин, Роман Ралифович
• кандидат физико-математических наук
• 2008

Оглавление диссертации кандидат физико-математических наук Гильманшин, Роман Ралифович

Введение

Глава I. Экстремальная задана в полиномиальной схеме

§1. Задачи случайных размещений, приводящие к поиску экстремума функции Mfxr.

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

§3. Вид набора вероятностей (pi, .,Pn)

§4. Необходимое условие экстремума функции Мцг.

§5. Верхняя и нижняя оценки максимума целевой функции

§6. Решение задачи на минимум для Mfxr и нахождение максимума для некоторых частных случаев.

§7. Исследование функции М/лг(х) на границе и в точке, соответствующей равновероятному набору.

§8. Некоторые свойства функций Ф(<г) и Ф(^).

§9. Интервал, содержащий критические точки целевой функции

§10. Исследование количества решений уравнения в необходимом условии экстремума.

§11. Исследование вида решения задачи по графикам функций

§(*).

§12. Задачи с большим числом размещаемых частиц или ячеек

Глава II. Численные методы решения экстремальной задачи

§1. Поиск пар точек, в которых Ф(^) принимает равные значения

§2. Применение комбинаторных полиномов для отыскания обратной функции.

§3. Локализация корней с помощью функции ф(г).

§4. Некоторые численные методы нахождения решений

§5. Алгоритм решения экстремальной задачи.

Глава III. Случайные блуждания на прямой с равновесными траекториями

§1. Принятые понятия и обозначения.

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

§3. Число траекторий из множества Тп(к).

§4. Критерий равновесности.

§5. Существование равновесных траекторий.

§6. Асимптотика Рп(к).

Введение диссертации (часть автореферата) на тему «Решение экстремальных задач при моделировании случайных размещений»

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

Каждая схема случайного размещения частиц по ячейкам является моделью, которая может быть использована при решении некоторых задач физики, техники, биологии и пр. В последнее время появилось множество работ в области случайных размещений,, в которых рассматривались различные схемы размещений и изучались случайные величины. Самой простой и наглядной является так называемая " Классическая задача о дробинках" (см. напр. [7], [8], [28], [26], [33], [46], и др.). Эту задачу достаточно подробно изучали Мизес [64], Бекеши [58], Вейс [69], Реньи [67].

Равновероятная схема, на которой основана задача о дробинках, не может использоваться в достаточно обширном классе задач математического моделирования. В связи с этим повышенный интерес представляет более общая схема размещения — полиномиальная. В данной схеме вероятности попадания в ячейку не меняются от опыта к опыту, но могут быть различными для каждой ячейки. Значительная часть результатов, полученных до 1975 года для числа ячеек, содержащих ровно г частиц (величина \±г), приведена в монографии В.Ф. Колчина, Б. А. Севастьянова, В.П. Чистякова [32]. Более поздние результаты содержатся в работах Г.И. Ивченко, В.А. Иванова, Ю.И. Медведева, В.Г. Михайлова и др.

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

Значительный интерес представляет задача, нахождения таких параметров модели полиномиального размещения (набора вероятностей, с которыми размещаются частицы), при которых обеспечивается экстремальное значение Mjir — математического ожидания величины /ir.

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

Постановка задачи принадлежит A.M. Зубкову. Им же в работе [24] совместно с Н.Н. Поповым в качестве следствия из основной теоремы отмечено, что число занятых ячеек в равновероятной схеме "стохастически больше" числа занятых ячеек в любой полиномиальной схеме с таким же числом ячеек и размещаемых частиц.

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

Цель работы. Основные цели диссертации:

• Исследование необходимого условия экстремума функции Мцг в полиномиальной схеме случайного размещения.

• Получение двусторонних оценок максимума функции M/ir.

• Рассмотрение одной модели размещения с вероятностями, изменяющимися в зависимости от состояния системы.

• Разработка и программная реализация метода численного поиска экстремума. Его сравнение с классическими методами. Проведение вычислительного эксперимента.

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

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

I , дания числа ячеек, содержащих ровно г частиц, в множестве полиномиальных моделей размещения п частиц по N ячейкам. Исследованы свойства распределений, на которых достигаются экстремальные значения, получены двусторонние оценки экстремальных значений. Построены в явном виде B(i, 1, ^-полиномы для i = 1,12. Поставлена и решена задача случайного блуждания с равновесными траекториями. Основные результаты, выносимые на защиту:

• теорема о структуре набора вероятностей, при которых функция M[ir может достигать экстремума;

• свойства "экстремальных распределений";

• оценки для максимума функции Mfir;

• метод численного поиска экстремума на основе комбинаторных полиномов;

• критерии равновесности траекторий неоднородного по пространству дискретного случайного блуждания.

Теоретическая и практическая значимость. Существует множество реальных процессов, математические модели которых сводятся к случайному размещению частиц по ячейкам. Решение экстремальной задачи позволяет на'основе известных параметров дать оценку неизвестному параметру размещения, например, по среднему значению наблюдаемой величины [j,r и известному числу ячеек N можно ограничить с заданной вероятностью количество размещаемых частиц. Кроме прикладного значения, полученные результаты представляют и теоретический интерес в плане дальнейшего развития методов оптимизации в теории случайных размещений.

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

Апробация работы. Основные результаты работы докладывались на ежегодных научно-теоретических конференциях молодых ученых ИГУ (1999, 2000 и 2001 годах), на конференции, посвященной 275-летию Академии наук и памяти А.И. Кокорина (Иркутск, 1999), на XII Байкальской международной конференции "Методы оптимизации и юс приложения" (Иркутск-Слюдянка, 2001), на второй Восточно-Сибирской зональной межвузовской конференции по математике и проблемам ее преподавания в вузе (Иркутск, 2003), на международной конференции "Колмогоров и современная математика" (Москва, 2003), на шестой Международной конференции "Вероятностные методы в дискретной математике" (Петрозаводск, 2004), на XIII Байкальской международной конференции "Методы оптимизации и их приложения" (Иркутск-Северобайкальск, 2005), на IV Всероссийской конференции "Математика, информатика, управление" (Иркутск, 2005).

Материалы диссертации докладывались и обсуждались на семинарах кафедры теории вероятностей и дискретной (математики Иркутского государственного университета (1999—2007), кроме того, результаты обсуждались в отделе дискретной математики Математического института им. В.А. Стеклова РАН.

Публикации. По теме диссертации опубликовано 11 научных работ. Наиболее значимые результаты, представленные в диссертации, опубликованы в работах [11]—[14], [16]—[20]. В число указанных работ входят

1 статья [14] из "Перечня ведущих рецензируемых журналов и изданий ВАК РФ 2001—2007 гг.", 1 работа [12] из "Перечня ведущих рецензируемых журналов и изданий ВАК РФ 2001—2006 гг." 1 статья [18] в научном сборнике, 1 депонированная статья [17], 3 полных текста докладов [11], [20], [31] в материалах международных конференций. Работы [13], [31] выполнены в нераздельном соавторстве с научным руководителем. Из совместной публикации [14] в диссертационную работу включены результаты, полученные автором самостоятельно и не затрагивающие интересы других соавторов.

Структура и объем работы. Работа состоит из введения, трех глав, заключения, приложения и списка литературы. Общий объем диссертации составляет 139 страниц, включая 16 рисунков. Список литературы содержит 69. наименований.

Заключение диссертации по теме «Математическое моделирование, численные методы и комплексы программ», Гильманшин, Роман Ралифович

Заключение

В работе изучены экстремальные значения математического ожидания числа ячеек, содержащих ровно г частиц, в множестве полиномиальных моделей размещения п частиц по N ячейкам. Исследованы свойства распределений, на которых достигаются экстремальные значения, получены двусторонние оценки экстремальных значений. Построены в явном виде В {г, 1, д)-полиномы для i = 1,12. Поставлена и решена задача случайного блуждания с равновесными траекториями.

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

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

Интересным результатом является то, что равновесность возможна только при S(x) = S = const, а все члены последовательностей вероятно ностей перехода {i?i}, {Li} однозначно определяются величинами Lq, S.

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

Список литературы диссертационного исследования кандидат физико-математических наук Гильманшин, Роман Ралифович, 2008 год

1. Бернштейн С.Н. Теория вероятностей. — 4-е изд., М. - Л., 1946. — 412 с.

2. Болотников Ю.В. Предельные процессы в неравновероятной схеме размещения частиц по ячейкам / Ю.В. Болотников // Теория вероятностей и ее применения. — 1968. — Т. 13, №3. — С. 534—542.

3. Бондаренко Е. М. Оценки математического ожидания максимума критического процесса Гальтона — Ватсона на конечном интервале / Е.М. Бондаренко, В.А. Топчий // Сибирский математический журнал. — 2001. — Т.42. — №2. — С. 249—257.

4. Васильев Ф.П. Численные методы решения экстремальных задач. — М.: МЦНМО, 2004. — 520 с.

5. Вентцель Е.С. Теория вероятностей. М. — Высш.шк., 2002. — 575 с.

6. Викторова И.И. О предельном поведении максимума в полиномиальной схеме / И.И. Викторова, Б.А. Севастьянов // Матем. заметки. — 1967. — Т.1, №3. — С. 331—338.

7. Викторова И.И. Асимптотическая нормальность в задаче о дробинках с произвольными вероятностями попадания в ящики / И.И. Викторова, В.П.Чистяков // Теория вероятностей и ее применения. — 1965. — Т.10, №1. — С. 162—167.

8. Викторова И.И. Об асимптотическом поведении максимума в равновероятной полиномиальной схеме / И.И. Викторова // Матем. заметки. — 1969. — Т.5, №3. — С. 305—316.

9. Вилков А.В. Метод отыскания глобального минимума функции одного переменного / А.В. Вилков, Н.П. Жидков, Б.М. Щедрин // Журнал вычислит, матем. и матем. физики. — 1975. — Т.15, №4. — С. 1040—1042.

10. Гапоненко Ю.Л. Метод последовательной аппроксимации для решения нелинейных экстремальных задач / Ю.Л. Гапоненко // Известия вузов. Сер. матем. — 1980. — №5. — С. 12—15.

11. Гильманшин P.P. Исследование вида решения одной экстремальной задачи в полиномиальной схеме размещения /P.P. Гильманшин // Обозрение прикладной и промышленной математики. Тезисы докладов М.: ОпиПМ. — 2004. — С. 237—238.

12. Гильманшин P.P. Об одной экстремальной задаче в теории случайных размещений / P.P. Гильманшин, Н.А. Колокольникова // Колмогоров и современная математика. Тезисы докладов. — М.: МГУ, 2003. — С. 627—628.

13. Гильманшин P.P. Оценки экстремальных значений среднего числа ячеек, содержащих заданное число частиц / P.P. Гильманшин, A.M. Зубков, Н.А. Колокольникова // Дискретная математика. — 2007. — Т. 19, вып. 1. — С. 11—16.

14. Гильманшин P.P. Случайное блуждание на прямой прямой / P.P. Гильманшин // Студент и научно-технический прогресс: тез. докл. студ. и асп. — Иркутск: Иркут. ун-т. — 1999. — С. 72.

15. Гильманшин P.P. Случайные блуждания на прямой с равновесными траекториями / P.P. Гильманшин; Иркутский государственный университет. — Иркутск, 2001. — 15 с. — Деп. в ВИНИТИ 21.12.2001; №2646-В2001.

16. Гильманшин P.P. Применение комбинаторных полиномов в решении одной экстремальной задачи /P.P. Гильманшин // Комбинаторные и вероятностные задачи дискретной математики: Сб. науч. тр. / под ред. О-В. Кузьмина. — Иркутск: Иркут. ун-т, 2006. — С. 32—37.

17. Гильманшин P.P. Экстремальные задачи в полиномиальной схеме размещений / P.P. Гильманшин // Вестник Иркутского университета. Специальный выпуск. Материалы ежегодной научно-теоретической конф. молодых ученых. — Иркутск: Иркут. ун-т. — 2001. — С. 66—67.

18. Гульден Перечислительная комбинаторика / Гульден, Джексон. — М.: Наука, 1990. — 504 с.

19. Гусейн-Заде С.М. Задача выбора и оптимальное правило остановки последовательности независимых испытаний / С.М. Гусейн-Заде // Теория вероятностей и ее применения. — 1966. — T.ll, №3. — С. 534— 537.

20. Зорин В.А Применение разностных уравнений в задачах случайного блуждания / В.А. Зорин, М.Е. Сморкалов, В.М. Сморкалова; Ни-жегор. гос. ун-т. — Н.Новгород, 2004. — 48 с. — Деп. в ВИНИТИ 30.06.2004; №1124-В2004.

21. Зубков A.M. Отношение частичного порядка, порожденное распределением числа занятых ячеек / A.M. Зубков, Н.Н. Попов // Матем. заметки. — 1982. — Т.32, №. — С. 97—102.

22. Ивченко Г.И. Асимптотическое поведение числа комплектов частиц в классической задаче о размещении / Г.И. Ивченко, Ю.И. Медведев // Теория вероятностей и ее применения. — 1966. — Т.11, №4. — С. 701—708.

23. Ивченко Г.И. Некоторые многомерные теоремы в классической задаче о размещении / Г.И. Ивченко, Ю.И. Медведев // Теория вероятностей и ее применения. — 1965. — Т.10, №1. — С. 156—162.

24. Ивченко Г.И. Предельные теоремы в задаче о размещении / Г.И. Ивченко // Теория вероятностей и ее применения. — 1971. — Т.16, №2. — С. 292—305.

25. Ивченко Г.И. Размещение случайного числа частиц по ячейкам / Г.И. Ивченко, Ю.И. Медведев, Б.А. Севастьянов // Матем. заметки. — 1967. — Т.1, №5. — С. 549—554.

26. Канторович JI.B. Об одном эффективном методе решения некоторых классов экстремальных проблем / JI.B. Канторович // Доклады АН, нов. серия. — 1940. — Т.28, №3. — С. 212—215.

27. Колокольникова Н. А. Центральные предельные теоремы для процессов рождения и гибели с дискретным временем / Н.А. Колокольникова // Асимптотические и перечислительные задачи комбинаторного анализа. — Иркутск: Иркут. ун-т, 1997. — С. 75—89.

28. Колокольникова Н. А. Экстремальные задачи в теории случайных размещений / Н.А. Колокольникова, P.P. Гильманшин // Материалы XII Байкальской международной конференции "Методы оптимизации и их приложения", 2001. — Т.5, С.71—75.

29. Колчин В.Ф. Случайные размещения / В.Ф. Колчин, Б.А. Севастьянов, В.П. Чистяков. — М.: Наука, 1976. — 224 с.

30. Колчин В.Ф. Один случай равномерных локальных предельных теорем с переменной решеткой в классической задаче о дробинках / В.Ф. Колчин // Теория вероятностей и ее применения. — 1967. — Т. 12, Ш. — С. 62—72.

31. Колчин В.Ф. Скорость приближения к предельным распределениям в классической задаче о дробинках / В.Ф. Колчин // Теория вероятностей и ее применения. — 1966. — Т.11, №1. — С. 144—155.

32. Корсаков Г.Ф. О количестве корней полинома вне круга / Г.Ф. Корсаков // Матем. заметки. — 1973. — Т.13, №1. — С. 3—12.

33. Косарев В.И. 12 лекций по вычислительной математике / В.И. Косарев // Учеб. пособие: Для вузов. — М.: МФТИ, 2000. — 224 с.

34. Кузьмин О.В. Обобщенные пирамиды Паскаля и их приложения / О.В. Кузьмин-— Новосибирск: Наука. — 2000. — 294 с.

35. Кузьмин О.В. Пути на решетках и некоторые специальные числа / О.В.,Кузьмин, Т.Г. Тюрнева // Тр. Вост.-Сибирской зональноймежвуз. конф. по математике и проблемам ее преподавания в вузе. — Иркутск: Изд-во Иркут. гос. пед. ун-та, 1999. — С. 159—160.

36. Мейман Н.Н. Некоторые вопросы расположения нулей полиномов / Н.Н. Мейман // УМН. — 1949. — Т.4, №6(34). — С. 154—188.

37. Неймарк Ю.И. К задаче распределения корней полиномов / Ю.И. Неймарк // Доклады АН, нов. серия. — 1947. — Т.58, №3. — С. 357— 360.

38. Островский A.M. О сходимости алгоритма Ньютона и его устойчивости по отношению к округлению цифр / A.M. Островский // Математический сборник, нов. серия. — 1937. — Т.2(44), №6. — С. 1094— 1095.

39. Платонов M.JI. Обращения формулы Бруно / M.JI. Платонов //t

40. Исследования по геомагнетизму, аэрономии и физике Солнца. — М.: Наука. — 1975. — Вып.35 — С. 32—38.

41. Попова Т.Ю. Предельные теоремы в одной модели размещения частиц двух типов / Т.Ю. Попова // Теория вероятностей и ее применения. — 1968. — Т. 13, №3. — С. 542—548.

42. Прасолов В.В. Многочлены / В.В. Прасолов. — М.: МЦНМО, 2003. — 336 с.

43. Севастьянов Б. А. Асимптотическая нормальность в классической задаче о дробинках / Б.А. Севастьянов, В.П. Чистяков // Теория вероятностей и ее применения. — 1964. — Т.9, №2. — С. 223—237.

44. Севастьянов В. А. Предельные теоремы в одной схеме размещения частиц по ячейкам / Б.А. Севастьянов // Теория вероятностей и ее применения. — 1966. — Т.11, №4. — С. 696—700.

45. Селиванов Б.И. Комбинаторный подход к формуле обращения Бюрмана — Лагранжа / Б.И. Селиванов // Комбинаторный и асимптотический анализ. — 1977. — Вып.2, С. 153—169.I

46. Тырсин А.Н. Об одном способе устойчивого оценивания математического ожидания / А.Н. Тырсин, Д.С. Воронина // Обозрение прикладной и промышленной математики. Тезисы докладов М.: ОпиПМ. — 2004. — С. 261—262.

47. Феллер В. Введение в теорию вероятностей и ее приложения / В. Феллер. — М.: Мир, 1984. — Т.1. — 528 с.

48. Хакимулин А.Е. Распределение крайних членов вариационного ряIда в схеме размещения частиц комплектами случайной длины / А.Е. Хакимулин // Дискретная математика. — 2005. — Т. 17. — С. 28—44.

49. Ширяев А.Н. Вероятность / А.Н. Ширяев. — М.: МЦНМО, 2004. — 520 с.

50. Barton D.E. Combinatorial chance / D.E. Barton, F.N. David. — London, Griffin, 1962.

51. Baum L.E. Asymptotic distributions for the coupon collector's problem / L.E. Baum, P. Billingsley // Ann. Math. Stat. 1965 — Vol. 36 №6. — P. 1835—1839.

52. Bekessy A. A lottojatekal kapesolatos nehany cellabetoltesi problema-zol II / A. Bekessy // Mat. Lapok. — 1965. — Vol. 16, P. 57—67.

53. Bell E.T. Exponential polynomials / E.T. Bell // Ann. Math. — 1934. — Vol. 35 — P. 258—277.

54. Bekessy A. On classical occupancy problems / A. Bekessy //I. Magy. tud. akad. Mat. kutato int. kozl. — 1963. — Vol. 8, №1—2. — P. 59—71.

55. Bekessy A. On classical occupancy problems. II. Sequential occupancy / A. Bekessy // Magy. tud. akad. Mat. kutato int. kozl. — 1964. — Vol. 9, №1—2. — P. 133—141.

56. Brayton R.K. On the asymptotic behavior of the number of trials necessary to complite a set with a random selection / R.K. Brayton // J. Math.

57. Anal, and Appl. — 1963. — Vol. 7, №1. — P. 31—61.i

58. Erdos P. On a classical problem of probability theory / P. Erdos, A. Renyi // Magy. tud. akad. Mat. kutato int. kozl. — 1961. — Vol. 6, №1— 2. — P. 215—220.

59. Hoist L. Limit theorems for some occupancy and sequential occupancy problems /L. Hoist // Ann. Math. Stat. — 1971. — Vol. 42 №5. — P. 1671— 1680.

60. Markoff A. On the determination of the number of roots of an algebraic equation, situated in a given domain / A. Markoff // Математический сборник, нов. серия. — 1940. — Т.7(49), №1. — С. 3—6.

61. Mises R. Uber Anfteilungs und Besetzungs — Wahrscheinlichkeiten / R. Mises // Revu de la Faculte des Sciences de l'Universite d'Istandbul N.S. — 1939. — Vol. 4. — P. 145—163.

62. Newman D.J. The double dixie cup problem / D.J. Newman, L. Shepp // Amer. Math. Mon. — 1960. — Vol. 67, №. —P. 58—61.

63. Polya G. Eine Wahrscheinlichkeitsaufgabe in der Kundenwerbung, Zeitschrift fur Angewandte / G. Polya // Math, und Mech. — 1930. — Vol. 10 №1—3. P. 96—97.

64. Renyi A. Three new proofs and generalization of a theorem of Irving Weiss / A. Renyi // Magy. tud. akad. Mat. kutato int. kozl. — 1962. — Vol. 7, №1—2, P. 203—214.

65. Renyi A. Wahrscheinlichkeitsrechnung, VEB Deutscher Verlag der Wis-senschaften / A. Renyi. — Berlin, 1962.

66. Weiss I. Limiting distributions in some occupancy problems / I. Weiss // Ann. Math. Stat. — 1958. — Vol. 29, №3. — P. 878—884.