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

Введение.

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

1.1. Описание классов задач.

1.2. Диаграмма Вороного.

1.3. Определение метрики р'.

1.4. Методы построения диаграммы Вороного на плоскости с метрикой р'.

1.5. Вывод формул для построения диаграммы Вороного в конкретном случае.

1.6. Задача «трёх точек» и диаграмма Вороного для п точек.

1.7. £-окрестности точки на плоскости с метрикойр'.

1.8. Постановка задач близости и локализации точки.

1.9. Задачи комбинированного типа.*.

Глава 2. Экстремальные задачи теории распознавания образов.

2.1. Элементы теории распознавания образов и её применение в математическом анализе.

2.2. Введение функционала Р - среднего процента ошибок при распознавании образца.

2.3. Решение экстремальных задач численными методами.

Глава 3. Некоторые аналоги классических экстремальных задач вычислительной геометрии.

3.1. Классические задачи вычислительной геометрии.

3.2. Задачи близости.

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

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

Глава 4. Экстремальные задачи, связанные с траекториями движущихся частиц.

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

4.2. Принцип столкновения частиц друг с другом.

4.3. Определение времени столкновения.

4.4. Косой удар.

4.5. Столкновение шаров разных масс и диаметров.

4.6. Функции распределения и броуновское движение.

4.7. Экстремальные зависимости числа столкновений частиц от различных величин.

4.8. Применение теории математических бильярдов для рассмотрения движения частиц по поверхностям рода 2.

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

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

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

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

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

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

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

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

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

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

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

Как известно, «естественной» метрикой двумерного пространства К2 является евклидова метрика р(х,у) = Л/(х1 - у,)2 + (х2 -у2)2 , где

X = (х1, Х2), у = (У1, у2).

Легко видеть, что каждая из функций р' (х, у) вида

Р'(х,у) = С 1 + 'К ~Уг\, (*) где с\, с2 > 0) является метрикой пространства К . Множество таких метрик обозначим через С.

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

Задачи, рассматриваемые в компьютерной математике, для удобства можно сгруппировать по признаку определения объектов в следующие классы: «поиск подмножества» (в задачах такого рода задан набор объектов и требуется найти некое подмножество, которое удовлетворяет определённому условию), «вычисление» (требуется найти численную величину некоторого математического параметра на некотором множестве объектов) и «распознавание».

Двумя главными моделями поиска являются:

1) задачи локализации, когда дано разбиение пространства на области. Локализация состоит в определении области, содержащей запрошенную точку;

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

Задачи локализации точки можно также с полным основанием назвать задачами о принадлежности точки, а задачи регионального поиска можно рассматривать как двойственные, в определённом смысле, к задачам локализации точки.

При решении такого рода задач необходимо выделить области точек, обладающие требуемым свойством (локусы) [25], и попытаться организовать их в виде некоторой структуры данных.

Отметим, что исследование плоских метрик специального вида тесно связано с так называемой задачей Вороного. Эта задача состоит в следующем: «На плоскости дано конечное множество точек {Аи i =1, 2,., п). Требуется разбить плоскость на области {Д, i = 1, 2,., п}, каждая из которых состоит из точек X, расстояние которых до Ai минимально по г.» л

В общем случае область Вороного на R с расстоянием Р (х, у) = VO^i - Л f + (х2 У2 Y точки i получается как пересечение всех полуплоскостей, содержащих эту точку и ограниченных срединными перпендикулярами к отрезкам, соединяющим z'-тую точку с остальными опорными точками.

V(i) = f\H{pitPj)

Поэтому области Вороного Vi будут ограничены выпуклой ломаной.

Получившаяся решётка обладает любопытным свойством: её рёбрами являются отрезки срединных перпендикуляров. Цоэтому, если некоторая точка О области Уь получена пересечением срединных перпендикуляров к отрезкам АВ и ВС, то она равноудалена от А и В, от В и С, т.е. О является центром окружности, описанной около треугольника ABC и срединный перпендикуляр к АС тоже проходит через О. Так как О е Уь, то не существует опорных точек, расположенных к О ближе, чем В, но ОА = ОВ = ОС, поэтому О е Уа и Ое Ус. Области Вороного образуют решётку, в каждой вершине которой сходятся три ребра и три области.

В процессе работы мы заметили , что применение метрик из класса С позволяет поставить и успешно разрешить некоторые новые задачи, ранее рассмотренные только в вычислительной геометрии для евклидовой метрики. В диссертации данные экстремальные задачи поставлены в терминах вычислительной геометрии, а решены методами математического анализа с применением компьютерных средств Список таких задач приведён на страницах 38-39, 59 - 60, 62-63.

Построение диаграммы Вороного применяется также при решении поставленных на страницах 46 - 47 задач. Задачи такого рода не являются абстрактными. Они имеют непосредственное приложение в теории распознавания образов. В них рассматриваются экстремумы функционала являющегося по сути средним процентом ошибок при распознавании образца и задаваемого в пространстве Ы метриками вида п

7 = 1

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

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

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

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

Суть задачи распознавания - это распознавание данного неизвестного образца, а не образа. Под образом же понимается совокупность образцов, класс образцов, в чём-то близких друг другу.

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

Алгоритмы - это программы, исполнимые на удобной абстракции реальных компьютеров; структуры данных - это способы организации информации, которые в совокупности с алгоритмами приводят к эффективному и элегантному решению вычислительных задач. В интересах ясности, изобразительной эффективности и краткости используют языки высокого уровня (в нашем случае - Turbo Pascal 7.0).

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

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

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

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

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

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

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

В нашем исследовании рассматриваются экстремальные случаи движения частиц по поверхностям рода 2. Речь пойдёт о простейшей модели газа - идеальном газе. Рассмотрим задачу столкновения частиц, движущихся в некоторой единице объёма. Для начала «упростим» условия данной задачи. Пусть движущиеся молекулы представляют собой абсолютно гладкие и упругие шары; стенки сосуда, в котором происходит движение молекул, также абсолютно гладкие. Такие частицы можно рассматривать как шары математического бильярда. Тогда бортики бильярдного стола будут играть роль стенок сосуда.

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

Данные по анализу одной из «бильярдных задач двумерного газа были опубликованы ещё Г. А. Лоренцом. В дальнейшем математическая теория бильярда была развита в работах [7], [8], [11], [12], а математические методы в классической механике - [3].

Авторы перечисленных выше источников рассматривали движения такого рода с точки зрения эргодической теории. Мы же изучаем движение двух отдельно взятых частиц («индивидуальной» пары точек), не усредняя результаты.

Перейдём к краткому изложению основных положений.

Диссертация состоит из введения, четырёх глав, списка литературы и 22 приложений. Объём работы составляет 102 страницы текста (без приложений). Библиографический список используемой литературы содержит 41 наименование. Основные результаты диссертации опубликованы в 11 работах автора.

1. Александров 77. С., Пасынков Б. А. Введение в теорию размерности. -М.: Наука, 1973.

2. Алгоритмы обучения распознаванию образов / под ред. ВапникаВ.Н. М.: Советское радио, 1973.

3. Арнольд В. 77. Математические методы классической механики. -М.: Наука, 1974.

4. Архангельский А. В., Пономарёв В. 77. Основы общей топологии в задачах и упражнениях. М.: Наука, 1974.

5. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М.:Мир, 1979.

6. Васильев Ф. 77. Численные методы решения экстремальных задач. М.: Наука, 1988.

7. Гальперин Г. А. Бильярд. //Квант №4, 1981.

8. Гальперин Г. А., Земляков А. Н. Математические бильярды. // б-чка «Квант». Вып. 77. М.: Наука, 1990.

9. Гершензон Е. М., Малое H. Н., Мансуров А. Н., Эткин В. С. Курс общей физики. Молекулярная физика. М.: Просвещение, 1982.

10. Горбань А. Н. Функции многих переменных и нейронные сети. // Соросовский образовательный журнал, № 12, 1998.

11. Епанешников А. М., Епанешников В. А. Программирование в среде Turbo Pascal 7.0. M.: Диалог-МИФИ, 1996.

12. Земляков А. Н. Арифметика и геометрия столкновений. // Квант №4, 1978.

13. Земляков А. 77. Математика бильярда. //Квант №5, 1976.

14. Информатика: энциклопедический словарь для начинающих. / сост. Поспелов Д.А. М.: Педагогика-Пресс, 1994.

15. Квасова Л. Б., Подрез Е. А., Симанёва ТА. Изучение языка программирования Turbo Paskal. 4.1. Орёл, 1995.

16. Компьютер и задачи выбора. М.: Наука, 1989.

17. Компьютеры, модели, вычислительный эксперимент. М.: Наука, 1988.

18. Коткин Г. Л. Газ бильярдных шаров. // Квант №6, 1989.

19. Лаврентьев М. А., Люстерник Л. А. Курс вариационного исчисления. -М.-Л.: ГИТТЛ, 1950.

20. Лаврова И. В. Курс физики. М.: Просвещение, 1981.

21. Леей 77. Стохастические процессы и броуновское движение. М.: Наука, 1976.

22. Ливенцев А. М. Курс физики для медвузов. М.: Высшая школа, 1974.

23. Марюков М. Н. Построение некоторых вычислительных алгоритмов на конечных множествах точек плоскости.// Успехи математических наук. Т. 50, вып. 2 (302) М.: Наука, 1995.

24. Математическая энциклопедия. / Гл. ред. Виноградов И.М. Т. 1-5. -М.: Советская энциклопедия, 1984.

25. Препарата Ф., Шеймос М. Вычислительная геометрия. Введение. М.: Мир, 1989.

26. Топологические и геометрические методы в математической физике. Воронеж: изд. ВГУД983.

27. Фриш С. Э., Тимофеева А. В. Курс общей физики. T.l. JL: Гос. изд. технико-теоретической лит-ры, 1949.

28. Эксперимент на дисплее. Первые шаги. М.: Наука, 1989.

29. Maryukov M.N. Computational geometry and mathematical modelling. 3 Международная конф-ция «Математика. Компьютер. Образование.»: Тез. докл. - Дубна, 1996.

30. Preparata F., Shamos М. Computational geometry. Springer Verlag, 1985.

31. Кирюхина Г. А. Применение методов математического анализа к решению задачи распознавания образов в компьютерной геометрии. VII международная конференция «Математика. Компьютер. Образование.» г. Дубна: Тез. докл. -М.: Прогресс-Традиция, 1999, с. 150.

32. Кирюхина Г. А. Решение некоторых экстремальных задач на распознавание образов методами математического анализа и компьютерными средствами. Сб. научных трудов «Математика. Компьютер. Образование.» М., 2000, 4с. чг- ¡а >

33. Кирюхина Г. А. Задачи близости точек в вычислительной геометрии и их практические применения. Сб. научных трудов «Математика. Компьютер. Образование.». Вып. 6, Ч. 2 - М.: Прогресс-Традиция, 1999, с. 287 -292.

34. Кирюхина Г. А. Решение компьютерными средствами некоторых экстремальных задач, связанных с рассмотрением различных метрик плоскости. Международная конференция «Экономика. Компьютер. Образование.» г. Симферополь: Тез. докл. - Симферополь, 2000, 1с.

35. Кирюхина Г.А. Компьютерное моделирование процесса столкновения частиц в единице объёма. Сб. научных трудов учёных Орловской обл. «Вестник науки». Вып. 5, Т. 1 - Орёл, ОрёлГТУ, 1999, с. 304-306.

36. Кирюхина Г.А. Описание и некоторые методы решения задач локализации точек в компьютерной геометрии. Орловск. гос. ун-т. Деп. в ВИНИТИ, 04. 08. 99, № 2560 - В 99, 13 с.

37. Кирюхина Г. А. Исследование экстремальных задач, связанных с рассмотрением различных метрик на плоскости. Орловск. гос. ун-т. Деп. В ВИНИТИ, 31. 07. 00, № 2140 - В 00, 17с.