Исследование некоторого класса экстремальных задач

• Автор: Кирюхина, Галина Алексеевна
• Шифр специальности: 01.01.01
• Научная степень: Кандидатская
• Год защиты: 2000
• Место защиты: Орел
• Количество страниц: 180 с. : ил.

Оглавление
Введение
Глава 1. Метрика. Описание метрики. Задачи, связанные с
рассмотрением экстремальных метрик
1.1. Описание классов задач
1.2. Диаграмма Вороного
1.3. Определение метрики р'
1.4. Методы построения диаграммы Вороного на плоскости
с метрикой р'
1.5. Вывод формул для построения диаграммы Вороного
в конкретном случае
1.6. Задача «трёх точек» и диаграмма Вороного для п точек
1.7. £-окрестности точки на плоскости с метрикойр'
1.8. Постановка задач близости и локализации точки
1.9. Задачи комбинированного типа
Глава 2. Экстремальные задачи теории распознавания образов
2.1. Элементы теории распознавания образов и её применение
в математическом анализе
2.2. Введение функционала Т7 - среднего процента ошибок
при распознавании образца
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 является евклидова метрика р(х,у) = (х, - у, )2 + (х2 - у2 )2 , где
X = (XI, х2), у = (У1, у2).
Легко видеть, что каждая из функций р'(х, у) вида
Р ’(х, у) = С, |х, - уг | + с2 |х2 - у21, (*)
(где с, с2 > 0) является метрикой пространства И2. Множество таких метрик обозначим через С.
В диссертации рассматриваются экстремальные задачи, поставленные в терминах вычислительной геометрии. Используя понятие метрики и некоторые конструкции компьютерной математики, мы ставим и разрешаем ряд экстремальных задач.
Задачи, рассматриваемые в компьютерной математике, для удобства можно сгруппировать по признаку определения объектов в следующие классы: «поиск подмножества» (в задачах такого рода задан набор объектов и требуется найти некое подмножество, которое удовлетворяет определённому условию), «вычисление» (требуется найти численную величину некоторого математического параметра на некотором множестве объектов) и «распознавание».
Двумя главными моделями поиска являются:
1) задачи локализации, когда дано разбиение пространства на области. Локализация состоит в определении области, содержащей запрошенную точку;

расположены «близко» друг к другу, а остальные удалены от них (рис. 4 в) и 4 г)).
Естественно, для решения большинства задач требуется построение диаграммы Вороного для множества точек 5, содержащего более двух точек.
На Рис. 5 а) изображена диаграмма Вороного для 15 точек на плоскости с метрикой
/>' = 3 1г -х,|+2-1У.-у I*/, К]
РИС. 5 а)
На Рис. 5 б) - диаграмма Вороного для 65 точек на плоскости с метрикой
Р = х, - х) +[>-,-у I * г. - 1,65.