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

• Автор: Заика, Ирина Викторовна
• Шифр специальности: 05.13.17, 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2007
• Место защиты: Таганрог
• Количество страниц: 295 с.

Содержание
Введение
Глава 1. Сортировка как алгоритмическая основа для автоматической идентификации экстремумов и нулей функций одной и нескольких
переменных
1.1. Параллельные алгоритмы сортировки слиянием и модифицированной сортировки подсчетом

1.1.1. Последовательное слияние по матрицам сравнений .

1.1.2. Числовые параметры сортировки слиянием .

1.1.3. Сортировка слиянием массива с произвольным числом элементов.

1.1.4. Модифицированная сортировка подсчетом

1.2. Алгоритм автоматической идентификации экстремальных значений одномерной последовательности на основе сортировки
1.3. Схема автоматической идентификации всех экстремумов функции одной действительной переменной на основе сортировки
1.4. Инвариантность схемы относительно вида функции и размеров промежутка поиска экстремумов
1.5. Схема локализации и вычисления экстремальных значений функции двух переменных
1.6. Схема автоматической идентификации экстремумов функций трех и более переменных
1.7. Автоматическая идентификация на основе сортировки нулей функций одной и
многих переменных .
1.8. Параллелизм схемы автоматической идентификации экстремумов и нулей функций многих переменных .
1.9. Сравнение схемы идентификации экстремумов на основе сортировки с известными методами безусловной оптимизации .
1 Выводы
Глава 2. Сортировка как алгоритмическая основа для автоматической
идентификации экстремумов и нулей разностных решений дифференциальных уравнений.
2.1. Идентификация на основе сортировки экстремумов разностного решения обыкновенного дифференциального уравнения ОДУ первого порядка .
2.1.1. Идентификация истинных и исключение ложных экстремумов на границах
текущего промежутка при помощи сортировки
2.2. Идентификация на основе сортировки экстремумов разностного решения системы дифференциальных уравнений второго порядка .
2.3. Идентификация на основе сортировки экстремумов разностных решений ОДУ в случае схем высшего порядка и формулировка основного предложения .
2.4. Случаи систем ОДУ из трех и более уравнений с приложением к идентификации экстремумов нормы разностных решений .
2.5. Автоматическая идентификация на основе сортировки нулей разностных решений дифференциальных уравнений .
2.6. Алгоритм автоматической идентификации экстремальных значений и нулей
разностных решений уравнений в частных производных .
2.7.0 сравнении с известными методами поиска на основе сортировки
экстремумов и нулей решений дифференциальных уравнений .
2.8. Выводы .
Глава 3. Применение сортировки для многомерной оптимизации с приложениями к решениям систем дифференциальных уравнений в условиях вариации параметров и к задачам условной оптимизации
3.1. Применение алгоритма многомерной оптимизации на основе сортировки к поиску экстремумов разностных решений систем линейных ОДУ при вариации параметров
3.1.1. Многомерная оптимизация на основе сортировки дискретно представленной функции четырех переменных.
3.1.2. Приложение к поиску глобального экстремума разностного решения системы линейных ОДУ при дискретной вариации трех параметров .
3.2. Применение алгоритма многомерной оптимизации к поиску экстремумов нормы возмущений решений систем нелинейных ОДУ при вариации параметров
3.2.1. Компьютерная оценка устойчивости на основе идентификации нулей и особенностей передаточной функции.
3.3. Обобщенная схема оптимизации при вариации параметров .
3.4. Применение алгоритма многомерной оптимизации для решения задач линейного программирования .
3.4.1. Пример численного решения задачи линейного программирования для случая целевой функции двух переменных
3.4.2. Примеры численного решения задачи линейного программирования для случая целевой функции трех и четырех переменных
3.5. Схема многомерной оптимизации на основе сортировки в случае решения задач нелинейного программирования
3.6. Особенности схемы идентификации экстремумов на основе сортировки
3.7.Выводы
Заключение
Литература


Вероятность, что хотя бы одна точка попадет в небольшую окрестность локального минимума, мала. Поэтому берут небольшое число точек и каждую рассматривают как нулевое приближение. Из каждой точки совершают спуск, быстро попадая в ближайший овраг или котловину когда шаги спуска сильно укорачиваются, его прекращают, не добиваясь высокой точности. Этого достаточно, чтобы судить о величине функции в ближайшем локальном минимуме. Сравнивая окончательные значения функции на всех спусках между собой, можно изучить расположение локальных минимумов функции и сопоставить их величины. Метод случайного поиска зачастую позволяет найти все локальные минимумы функции переменных со сложным рельефом. Он полезен при исследовании функции с единственным минимумом в этом случае можно обойтись заметно меньшим числом случайных точек. Недостаток метода в том, что надо заранее задать область, в которой выбираются случайные точки. Широкая область затрудняет детальное исследование, узкая область влечет потерю экстремумов. Метод Ньютона 6, 0 относится к методам спуска. В этом методе очередная точка хкв последовательности аг0,,л,х2,. Ы xixix к 1,2. Вычисления заканчиваются, если ,хе, где е 0 малое, наперед заданное число. Сходимость метода Ньютона зависит от выбора д0, метод отличается трудоемкостью, требуя обращения на каждом шаге матрицы вторых производных минимизируемой функции. Метод Дэвидона Флетчера Пауэлла 6. Среди алгоритмов многомерной минимизации следует выделить группу алгоритмов, которые объединяют достоинства наискорейшего спуска и метода Ньютона. Такие алгоритмы принято называть квазиныотоновскими. Особенность состоит в том, что при их применении нет необходимости вычислять и обращать матрицу Гессе целевой функции, в то же время удается сохранить высокую скорость сходимости алгоритмов. Метод Дэвидона Флетчера Пауэлла 6 представляет собой алгоритм отыскания безусловного минимума целевой функции от нескольких переменных. Необходимы частные производные целевой функции по независимым переменным. В основе метода лежит допущение об унимодальности целевой функции, при нарушении допущения следует брать несколько исходных точек. Метод Дэвидона Флетчера Пауэлла позволяет обходить трудности, связанные с разрывами производных в пространстве проектирования. Распространено мнение, что этот метод наиболее эффективен из всех градиентных методов, дает полную информацию о кривизне поверхности целевой функции в точке минимума, однако при этом требуется больший объем памяти и длительность счета. При исследовании унимодальной функции, откуда бы ни начинался поиск, вычисления приведут к нужной точке. На рис. О, и . Сравнивая между собой значения функции в точках Ох и , находят, что наименьшее значение функции достигается в точке . Рис. Если начать поиск наименьшего значения с помощью градиентного спуска из точки А, поиск приведет в точку 0, которую ошибочно можно принять за искомый минимум. С другой стороны, если поиск начинается с точки А2, то вычисления приведут в точку . Принято считать , , , что универсального приема, который бы позволил эффективно справляться с многоэкстремальностью, не существует. Самый простой прием состоит в том, что проводят поиск несколько раз из разных начальных точек. Если при этом получаются разные значения целевой функции, то сравнивая их, выбирают наименьшее , 6. Расчеты останавливают после того, как несколько новых поисков не меняют полученного ранее результата. Выбор начальных точек поиска, обоснованность прекращения расчетов в значительной степени зависят от опыта и интуиции специалистов, решающих задачу. Во многих случаях необходима различная дополнительная информация о характере задачи, которая существенно помогает при выборе метода, начальной точки поиска. Если нет никаких предположений о специальных свойствах целевой функции и о характере рассматриваемой области, это затрудняет анализ. Конкретизация задачи, выделение определенных классов функций и областей позволяет провести более глубокое исследование и разработать специальные методы, которые решают задачу исчерпывающим образом.