Содержание к диссертации
Введение
Глава 1. Сортировка как алгоритмическая основа для автоматической идентификации экстремумов и нулей функций одной и нескольких переменных 38
1.1. Параллельные алгоритмы сортировки слиянием и модифицированной сортировки подсчетом 39
1.1.1. Последовательное слияние по матрицам сравнений 41
1.1.2. Числовые параметры сортировки слиянием 42
1.1.3. Сортировка слиянием массива с произвольным числом элементов 43
1.1.4. Модифицированная сортировка подсчетом 44
1.2. Алгоритм автоматической идентификации экстремальных значений одномерной последовательности на основе сортировки 47
1.3. Схема автоматической идентификации всех экстремумов функции одной действительной переменной на основе сортировки 50
1.4. Инвариантность схемы относительно вида функции и размеров промежутка поиска экстремумов 54
1.5. Схема локализации и вычисления экстремальных значений функции двух переменных 56
1.6. Схема автоматической идентификации экстремумов функций трех и более переменных 62
1.7. Автоматическая идентификация на основе сортировки нулей функций одной и многих переменных 67
1.8. Параллелизм схемы автоматической идентификации экстремумов и нулей функций многих переменных 69
1.9. Сравнение схемы идентификации экстремумов на основе сортировки с известными методами безусловной оптимизации 71
1.10. Выводы 75
Глава 2. Сортировка как алгоритмическая основа для автоматической идентификации экстремумов и нулей разностных решений дифференциальных уравнений 77
2.1. Идентификация на основе сортировки экстремумов разностного решения обыкновенного дифференциального уравнения (ОДУ) первого порядка 77
2.1.1. Идентификация истинных и исключение ложных экстремумов на границах текущего промежутка при помощи сортировки 80
2.2. Идентификация на основе сортировки экстремумов разностного решения системы дифференциальных уравнений второго порядка 82
2.3. Идентификация на основе сортировки экстремумов разностных решений ОДУ в случае схем высшего порядка и формулировка основного предложения 86
2.4. Случаи систем ОДУ из трех и более уравнений с приложением к идентификации экстремумов нормы разностных решений 90
2.5. Автоматическая идентификация на основе сортировки нулей разностных решений дифференциальных уравнений 93
2.6. Алгоритм автоматической идентификации экстремальных значений и нулей разностных решений уравнений в частных производных 94
2.7. О сравнении с известными методами поиска на основе сортировки экстремумов и нулей решений дифференциальных уравнений 99
2.8. Выводы 103
Глава 3. Применение сортировки для многомерной оптимизации с приложениями к решениям систем дифференциальных уравнений в условиях вариации параметров и к задачам условной оптимизации 106
3.1. Применение алгоритма многомерной оптимизации на основе сортировки к поиску экстремумов разностных решений систем линейных ОДУ при вариации параметров 106
3.1.1. Многомерная оптимизация на основе сортировки дискретно представленной функции четырех переменных 107
3.1.2. Приложение к поиску глобального экстремума разностного решения системы линейных ОДУ при дискретной вариации трех параметров 110
3.2. Применение алгоритма многомерной оптимизации к поиску экстремумов нормы возмущений решений систем нелинейных ОДУ при вариации параметров 118
3.2.1. Компьютерная оценка устойчивости на основе идентификации нулей и осо
бенностей передаточной функции 123
3.3. Обобщенная схема оптимизации при вариации параметров 124
3.4. Применение алгоритма многомерной оптимизации для решения задач линейного программирования 127
3.4.1. Пример численного решения задачи линейного программирования для случая целевой функции двух переменных 129
3.4.2. Примеры численного решения задачи линейного программирования для случая целевой функции трех и четырех переменных 131
3.5. Схема многомерной оптимизации на основе сортировки в случае решения задач нелинейного программирования 133
3.6. Особенности схемы идентификации экстремумов на основе сортировки 138
3.7.Выводы 140
Заключение 142
Литература 145
Приложение 1 155
Приложение! 178
Приложение 3 206
- Алгоритм автоматической идентификации экстремальных значений одномерной последовательности на основе сортировки
- Схема автоматической идентификации экстремумов функций трех и более переменных
- Идентификация на основе сортировки экстремумов разностного решения системы дифференциальных уравнений второго порядка
- Применение алгоритма многомерной оптимизации к поиску экстремумов нормы возмущений решений систем нелинейных ОДУ при вариации параметров
Введение к работе
Актуальность проблемы. Первые задачи, связанные с отысканием наименьших и наибольших величин, преимущественно геометрического содержания появились в древности. Развитие промышленности в XVII— XVIII веках привело к более сложным задачам на экстремум. В XX веке при развитии производства в условиях ограниченности ресурсов возникли задачи оптимального расхода энергии, материалов, рабочего времени. Приобрели актуальность вопросы наилучшего в том или ином смысле управления различными процессами физики, техники, экономики. В частности, потребовалось организовать производство с целью получения максимальной прибыли при заданных затратах ресурсов. Актуальны задачи управления системой гидростанций и водохранилищ с целью получения максимального количества электроэнергии, построения оптимальной траектории космического перелета с наименьшей затратой энергии. Аналогичные задачи ставятся при нагреве или охлаждении металла до заданного температурного режима и др. В различных разделах математики возникают задачи наилучшего приближения функций, оптимального выбора параметров итерационного процесса, узлов интерполирования, минимизации невязки уравнений и т. д. Все такие задачи могут быть идентифицированы как задачи отыскания экстремума (максимума или минимума) некоторой функции или функционала.
Современное состояние теории оптимизации характеризуется фундаментальными направлениями в области линейного, выпуклого, стохастического программирования, оптимального управления, а также в области численных методов приближенного решения экстремальных задач.
I. При изучении экономического поведения возникают проблемы точного описания стремления индивидуума к извлечению максимальной пользы или прибыли. Постановка и решение таких задач достигаются при помощи математических методов, существенно отличающихся от классических методов решения задач на экстремумы.
Одна из трудностей, возникающих при решении как статических, так и динамических задач на условный экстремум в виде задачи вариационного исчисления, состоит в том, что для получения конкретного ответа необходимо знать конкретный вид исследуемой функции. В тех экономических задачах, где нужны качественные свойства решения, достаточно общего представления о виде функции. Если же необходимо построить модель конкретной практической задачи, то без конкретных функций не обойтись. Для современных приложений разработан подход к задаче оптимизации при ограничениях, относящийся к разделам линейного программирования.
С помощью метода линейного программирования удалось связать два вида решений в теории фирмы, а именно: выбор технологии производства и выбор состава и размеров выпуска, обеспечивающих максимальную прибыль. Для случая, когда целевую функцию нельзя представить в виде линейной функции, была разработана теория нелинейного программирования.
Помимо этого метода для решения задач нелинейного программирования используются методы аппроксимирующего программирования, включая методы линеаризации /94, 100, 101, 115/, и применимые к ним методы линейного программирования /33/, а также метод неопределенных множителей Лагранжа.
Для решения динамических задач вместо вариационного исчисления стали использоваться в основном современные методы динамического программирования и теории оптимального управления. Теорию оптимизации можно рассматривать как особый раздел математики или же, как набор средств, необходимых экономисту-прикладнику для решения вполне определенных прикладных задач, при этом необходимо улучшение перечисленных методов, которые разрабатывались, чтобы находить ответы на вопросы, поставленные более конкретно, чем нужно экономической теории. Таким образом, экономическая теория продолжает оставаться качественной наукой.
П. Один из основных подходов к решению экономических задач дает теория игр /64, 120/. На начальных этапах развития теории игр ее рассматривали как обобщение теории оптимизации на случай двух и более участников экономического процесса. Однако подлинное отличие от традиционной теории заключалось в том, что в теории игр учитывается взаимодействие участников экономического процесса и возможность конфликта между ними. Это отличие нашло выражение в целевой функции, которая определяет размер выигрыша в зависимости от выбранного решения: выигрыш одного участника экономического процесса зависит не только от того, какие альтернативы выберет он сам, но и от того, какие альтернативы выберут другие. Благодаря этому в экономических исследованиях игровой подход применялся преимущественно для изучения таких экономических проблем, как двусторонняя монополия или олигополия. Кроме того, теория простых игр позволила уточнить понятие равновесия в экономике. В играх двух участников с нулевой суммой равновесной стратегией любого участника экономического процесса является такая, которая дает данному участнику наибольший минимальный выигрыш при любой возможной стратегии другого игрока. Такое равновесие консервативно, поскольку участник экономического процесса должен выбирать не ту стратегию, которая приносит ему наибольший выигрыш при неразумном выборе стратегии соперником, а ту стратегию, которая в наибольшей степени предохраняет от потерь в игре с умудренным соперником.
III. Теория игр признана классической наукой, играет значительную роль в ряде прикладных областей, включая военное дело и экономику /1,112-114/. В качестве основного подхода к задачам теории игр используются средства классического анализа и дифференциальные уравнения. В этом контексте рассматривается теория дифференциальных игр, которая исследует игры, где противники принимают целый ряд последовательных решений, которые так логически связаны друг с другом, что эта связь может послужить основой наглядной и численно анализируемой модели.
Примером дифференциальных игр может быть боевая игра, где каждый игрок стремится уничтожить боевые силы противника. Аналогию этой игры можно найти, например, в бизнесе, когда каждая из двух коммерческих фирм старается разорить конкурента. Подобные игры можно рассматривать и как игры степени, где платой является количество уцелевших ресурсов победившей стороны, и как игры качества, цель которых - истребление. Типичными примерами дифференциальных игр также являются сражения, воздушные бои, футбол, преследование судна торпедой, перехват самолета зенитной ракетой, охрана объектов от нападения. Если один из игроков выключается из игры, то получаем обычную задачу максимизации. Она уже относится к вариационному исчислению и составляет основную часть теории оптимального управления.
Дифференциальные игры, описывающие конфликтно-управляемые системы, являются обобщением задач оптимального управления. В теории оптимального управления рассматриваются также задачи, учитывающие запаздывание информации, задачи с параметрами, с дискретным временем, с общим видом целевой функции, задачи для уравнений с частными производными. К решению таких задач сводится большой объем вычислительных задач прикладной математики, теоретической и экспериментальной физики, технической кибернетики.
Помимо принципа максимума Понтрягина в области динамического программирования широко известен принцип оптимальности Беллмана. Описание принципа в содержательном смысле заключается в следующем /20,104 /.
Принцип оптимальности. Оптимальная политика (или стратегия, понимаемая как последовательность допустимых решений) обладает тем свойством, что, каковы бы ни были начальное состояние и начальное решение, последующие решения должны составлять оптимальную политику относительно состояния, являющегося результатом применения первого решения. Принципа максимума Понтрягина и принцип оптимальности Беллмана находят разнообразное применение при решении задач вариационного исчисления и задач условной оптимизации /68, 104/
V. Для решения задач оптимизации широко используется современные средства вычислительной техники. В процессе использования последовательных компьютеров был накоплен и отработан огромный фонд численных методов и про 14 грамм. Однако оказалось, что современные персональные компьютеры не в состоянии решить за приемлемое время многие задачи, имеющие большой объем вычислений. Использование параллельных компьютеров позволяет минимизировать время реализации алгоритмов. При этом существенно, чтобы параллельная реализация алгоритма имела такие же вычислительные свойства, как и любая другая. В частности, если исходный алгоритм (последовательный) был численно устойчив, то он должен оставаться таким же и в параллельной форме. Как отмечается в /27/, на практике подавляющее большинство алгоритмов оказалось несостоятельным. Огромное число требуемых процессоров, сложные информационные связи между операциями, численная неустойчивость, конфликты в памяти препятствуют применению быстрых параллельных алгоритмов. Перечисленные трудности относятся к существующим задачам оптимизации. Поэтому необходима разработка машинного метода приближенных вычислений, позволяющего экономить время и усилия, затрачиваемые на решение оптимизационной задачи.
В данном аспекте целесообразно принять во внимание схемы использования сортировки для приближенных вычислений /75, 76, 78, 79 /. Алгоритмы ее выполнения позволяют минимизировать количество формул и методов традиционной математики. Применение сортировки опирается на упорядочение информации при вычислениях и включает только операции сравнения. Как следствие, можно ожидать снижения роста погрешности при решении задач с ее применением. На этой основе схемы параллельной сортировки можно рассматривать как одно из средств решения проблем устойчивости параллельных вычислений.
Сортировка /24/ практически присутствует во всех приложениях операционных систем при обработке больших объемов данных. С помощью сортировки решаются задачи "группировки", когда нужно собрать элементы по некоторому признаку. Сортировка используется при поиске с целью его ускорения, с помощью сортировки можно сделать выдачи ЭВМ более удобным для человеческого восприятия. В контексте сортировки рассматриваются многие аспекты программирования.
Сортировки делятся /53/ на внутренние и внешние. Внутренние сортировки выполняются в оперативной памяти. Внешние сортировки приемлемы для файлов данных, которые превосходят размер основной памяти, и поэтому должны в течение процесса сортировки располагаться на устройствах внешней памяти. В процессе внешней сортировки часть файла считывается в основную память, там упорядочивается, а затем переписывается на внешние устройства. Во всех внешних сортировках используются внутренние сортировки. Ниже рассматриваются некоторые примеры сортировок, а также параллельное слияние, приводятся оценки временной сложности.
Временная сложность алгоритмов будет измеряться количеством последовательных шагов их выполнения. В частности, временная сложность сортировки измеряется числом последовательно выполняемых сравнений. Временная сложность параллельных алгоритмов будет оцениваться на модели неветвящихся параллельных программ /2, 19, 77, 93/ без учета обмена. Временная сложность параллельной сортировки будет обозначаться Г(Я) = &г, где т - время бинарного сравнения, к количество последовательных сравнений, R - число используемых процессорных элементов (при описании параллельных сортировок иногда их называют компараторами).
Сортировка вставками /53/. Элементы просматриваются по одному, каждый новый элемент вставляется в подходящее место среди ранее упорядоченных элементов (временная сложность - Г(1) = 0(N2), где 0(f) - класс функций, растущих не быстрее /). Сортировка Шелла, временная сложность которой Т(\) = 0(N 5),
представляет собой усовершенствование сортировки вставками. Эта сортировка представляет собой многопроходную сортировку, при которой список разбивается на подсписки, каждый из них сортируется отдельно, причем на каждом проходе число подсписков уменьшается, а их длина растет.
Обменная сортировка /53, 83, 84/. Предусматривает систематический обмен местами между элементами пар, в которых нарушается упорядоченность, до тех пор, пока таких пар не останется. Существуют несколько типов сортировки, для которых обмены являются основной характеристикой. Выделяют обменную сортировку с выбором ("метод пузырька"), поразрядную сортировку, обменную сортировку с разделением ("быстрая сортировка" Хоара), обменная сортировка со слиянием (параллельная сортировка Бэтчера).
Сортировка выбором /53/. Из последовательности выделяется наименьший (наибольший) элемент и каким- либо образом отделяется от остальных, затем выбирается наименьший (наибольший) из оставшихся, процесс повторяется до тех пор, пока все элементы последовательности не будут отсортированы. На идее выбора основан алгоритм пирамидальной сортировки
Пирамидальная сортировка (T(Y) = 0(N log2 N)) строит бинарное дерево, значение каждого узла в котором превышает значение потомков. В результате наибольший элемент списка помещается в корень, при его удалении и выборе очередной пирамиды в корне оказывается следующий по величине элемент. Процесс повторяется, пока все элементы не окажутся в отсортированном списке.
Сортировка подсчетом /53, 86/. При сортировке подсчетом (T(l) = 0(N2)), каждый элемент сравнивается со всеми остальными; окончательное положение элемента определяется подсчетом числа меньших ключей.
Для параллельного слияния двух упорядоченных массивов из т и п элементов сравнение всех элементов между собой в матрице сравнений производится одновременно. Временная сложность параллельного слияния Т(т п) = 0(1).
Замечание 1. Вся сортировка слиянием по матрице сравнений в параллельном варианте имеет временную сложность T(N2 /4)=0(log2 N). При этом данная сортировка относится к числу наиболее быстрых и в последовательном варианте r(l)= 9(WIog2AO/80, 81/.
Немаловажным качеством сортировок является их устойчивость. Сортировка называется устойчивой, если она обладает свойством сохранения порядка записей с одинаковыми ключами /53/. К числу устойчивых относятся, например, сортировка вставками, к числу неустойчивых - корневая, пирамидальная, быстрая. В /83, 84/ предложены такие параллельные модификации известных схем сортировок, при которых модифицированные сортировки приобретают устойчивость, включая параллельное видоизменение сортировок подсчетом и слиянием.
В рассматриваемом контексте исследуется применение сортировок для построения схем локализации и устойчивого вычисления экстремумов функций.
VI. Численные схемы безусловной оптимизации. Ниже приводится сравнительная характеристика наиболее часто применяемых методов вычисления экстремумов функций.
Методы численного решения задач многомерной безусловной оптимизации многочисленны и разнообразны. С некоторой нестрогостью их можно разделить на три класса в зависимости от информации, используемой при реализации метода.
1. Методы нулевого порядка, или прямого поиска, стратегия которых основана на использовании информации только о свойствах функции.
2. Методы первого порядка, в которых при построении итерационной процедуры наряду с информацией о функции используется информация о первых производных этой функции. 3. Методы второго порядка, в которых наряду с информацией о значениях функции и ее первых производных используется информация о ее вторых производных.
В литературе /3, 6, 14, 25, 29, 36/ не выделяется универсальный метод, применимость которого была бы оправдана и эффективна во всех случаях. Выбор того или иного метода, его программная реализация должны быть согласованы с конкретными условиями, вытекающими из специфики решаемой задачи безусловной минимизации.
Для функции одной переменной классический подход /6, 20, 40, 47, 50/ при поиске минимума (максимума) функции f(x) состоит в последовательном вычислении функции при возрастающих значениях х до тех пор, пока не будет достигнуто наименьшее (наибольшее) значение функции. Значения дг должны быть заключены в интервале а х Ь. В начале процесса оптимизации интервал имеет длину Ь-а. Вычислив значения функции f{xl) и f(x2) при значениях х, и х2 в
указанном интервале, интервал сужают. В зависимости от способов сужения интервала различают следующие методы оптимизации: метод общего поиска, метод Фибоначчи, метод золотого сечения, метод парабол.
Функция f(x) может иметь на исследуемом множестве более одного локального минимума. В конкретных прикладных задачах далеко не всегда удается заранее исследовать свойства функции. Поэтому желательно, чтобы численный алгоритм позволял определить число минимумов и их расположение.
Метод золотого сечения применим даже к недифференцируемым функциям и всегда сходится; сходимость его линейна. Если на отрезке [а, Ь] функция имеет несколько локальных минимумов, то процесс сойдется к одному из них (но не обязательно к наименьшему). Этот метод применяют в технических или экономических задачах оптимизации, когда минимизируемая (максимизируемая) функция не-дифференцируема, а каждое вычисление функции выполняется по сложному алгоритму.
4.Метод парабол /21,49/. Если f(x) дифференцируема, то можно построить более быстрые методы, основанные на решении уравнения / ( ) = 0. На практике часто f(x) имеет первую и вторую производную. Поэтому для нахождения нулей первой производной применяют метод линеаризации, что приводит к итерацион f(x ) ному процессу хк+] =хк - й . Для успешной работы метода парабол необходи мы дополнительные поправки к алгоритму. В ходе вычислений надо проверять, продвигаются ли вычисления к минимуму. Если функция имеет несколько локальных минимумов, то метод может сойтись к любому из них или не сойтись вовсе. Описанный способ не дает гарантии того, что будут найдены все минимумы (и тем самым, что будет найден абсолютный минимум).
Наилучшими критериями сравнения методов поиска являются их эффективность и универсальность. Под эффективностью алгоритма обычно понимают количество вычислений функции, необходимое для достижения требуемого сужения интервала неопределенности. Лучшим в этом отношении является метод Фибоначчи, худшим — метод общего поиска. Как правило, методы Фибоначчи и золотого сечения, обладающие высокой эффективностью, наиболее подходят для решения одномерных унимодальных задач оптимизации /31,35, 106/.
Универсальность алгоритма означает его применимость для решения самых разнообразных задач. В этом отношении метод Фибоначчи уступает другим, мало 22
эффективный метод общего поиска можно с успехом применять и для не унимодальных функций, если они достаточно гладкие. Нередко заранее не известно, является ли рассматриваемая целевая функция унимодальной. В таких случаях следует воспользоваться несколькими разными алгоритмами и посмотреть, дают ли они все один и тот же оптимум.
Принято считать, что не существует универсального алгоритма, который позволял бы решать любые задачи безусловной оптимизации /6, 95, 96/. При решении сложных задач оптимизации пользуются разными методами, так как это позволяет увеличить долю удачных решений.
Замечание 2. Схема оптимизации, разрабатываемая в диссертационной работе, отличается по построению от существующих методов безусловной оптимизации и инвариантна относительно вида исследуемой функции при том ограничении, что функция на вход схемы поступает после дискретизации.
Функции многих переменных. Численное решение задач безусловной минимизации (максимизации) функций многих переменных, как правило, значительно сложнее, чем решение задач минимизации (максимизации) функций одного переменного. С ростом числа переменных возрастают объемы вычислений и усложняются конструкции вычислительных алгоритмов, более сложным становится анализ поведения функции Основные трудности многомерного случая удобно рассмотреть на примере функции двух переменных f{x,y). Она описывает некоторую поверхность в трехмерном пространстве с координатами х, у, f. Задача f{x,y) = min означает поиск низшей точки этой поверхности. Рельеф этой поверхности можно изобразить линиями уровня. Проведем равноотстоящие плоскости / = const и найдем линии их пересечения с поверхностью f(x,y); проекции этих линий на плоскость хОу называют линиями уровня. Направление убывания
функции указывают штрихами, рисуемыми около линий уровня. Полученная картина напоминает топографическое изображение рельефа горизонталями. По виду линий уровня условно выделяют три типа рельефа: котловинный, овражный и неупорядоченный. При котловинном рельефе линии уровня похожи на эллипсы (рис. 5, а). В малой окрестности невырожденного минимума рельеф функции котловинный.
Все эффективные методы поиска минимума сводятся к построению траекторий, вдоль которых функция убывает; разные методы отличаются способами построения таких траекторий. Метод, приспособленный к одному типу рельефа, может оказаться плохим на рельефе другого типа.
5. Метод спуска по координатам /20, 90/. Рассмотрим функцию трех переменных f(x,y,z). Выберем нулевое приближение х0, у0, z0. Фиксируем значения
двух координат у = у0, z = z0. Тогда функция будет зависеть только от одной переменной х, обозначим ее через fx(x) = f(x,y0,z0). Используя методы поиска экстремума для функции одной переменной, находим минимум функции /{(х), обозначив его через х,. Выполнение шага из точки (x0,y0,z0) в точку (xvy0,z0), по направлению, параллельному оси х, уменьшает значение функции.
Метод спуска по координатам несложен и легко программируется, но сходится медленно, а при наличии оврагов - очень плохо. Поэтому его используют в качестве «первой попытки» при нахождении минимума.
6. Наискорейший спуск. Спускаться можно не только параллельно осям ко ординат. Вдоль любой прямой г = r0 + at функция зависит только от одной пере менной, f(rQ + at) = p{t), и минимум на этой прямой находится методами поискаэкстремума для функции одной переменной. Наиболее известным является метод наискорейшего спуска, когда выбирается a = -(grad /)r_r , т. е. направление, в котором функция быстрее всего убывает при бесконечно малом движении из данной точки. Спуск по этому направлению до минимума определяет новое приближение г,. В этой точке снова определяется градиент и делается следующий спуск. Этот
метод сложнее спуска по координатам, требуется вычислять производные и градиент (иногда конечно-разностными методами) и переходить к другим переменным. По сходимости наискорейший спуск не лучше спуска по координатам. При попадании траектории в истинный овраг спуск прекращается, а в разрешимом овраге сильно замедляется /50/.
7. Сопряженные направления /6, 9/. Методы наискорейшего спуска или спуска по координатам требуют бесконечного числа итераций, но можно построить такие направления спуска, что для квадратичной функции f(r) = (r, Ar) + (b,r) + c, (г есть n-мерный вектор) с симметричной положительно определенной матрицей А процесс спуска сойдется к минимуму за конечное число шагов. Вводится норма вектора.
Определение (8) подразумевает скалярное произведение векторов х и у вида (x, Ay). Векторы, ортогональные в смысле скалярного произведения, называют сопряженными (по отношению к матрице А). Поочередный спуск по сопряженным направлениям особенно выгоден при поиске минимума (максимума). На этом основана большая группа методов: сопряженных градиентов, сопряженных направлений, параллельных касательных и др. Для квадратичной функции они применяются с одинаковым успехом, на произвольные функции хорошо обобщается метод сопряженных направлений, у которого детали алгоритма тщательно отработаны. Метод сопряженных направлений относят к наиболее эффективным методам спуска. Он неплохо работает при вырожденном минимуме, при разрешимых оврагах, при наличии слабо наклонных участков рельефа - "плато". Методы спуска неполноценны на неупорядоченном рельефе. Если локальных экстремумов много, спуск из нулевого приближения может сойтись лишь к одному из них, не обязательно абсолютному, в этом случае применяют случайный поиск /50, 90/.
8. Случайный поиск. Предполагают, что минимум (или все минимумы) лежит в некоторой замкнутой области; линейным преобразованием координат помещают ее внутрь единичного п -мерного куба. Выбирают в этом кубе N случайных точек; если о расположении экстремумов заранее ничего не известно. Вероятность, что хотя бы одна точка попадет в небольшую окрестность локального минимума, мала. Поэтому берут небольшое число точек и каждую рассматривают как нулевое приближение. Из каждой точки совершают спуск, быстро попадая в ближайший овраг или котловину; когда шаги спуска сильно укорачиваются, его прекращают, не добиваясь высокой точности. Этого достаточно, чтобы судить о величине функции в ближайшем локальном минимуме. Сравнивая окончательные значения функции на всех спусках между собой, можно изучить расположение локальных минимумов функции и сопоставить их величины. Метод случайного поиска зачастую позволяет найти все локальные минимумы функции 10-20 переменных со сложным рельефом. Он полезен при исследовании функции с единственным минимумом; в этом случае можно обойтись заметно меньшим числом случайных точек. Недостаток метода в том, что надо заранее задать область, в которой выбираются случайные точки. Широкая область затрудняет детальное исследование, узкая область влечет потерю экстремумов.
Метод Дэвидона - Флетчера - Пауэлла /106/ представляет собой алгоритм отыскания безусловного минимума целевой функции от нескольких переменных. Необходимы частные производные целевой функции по независимым переменным. В основе метода лежит допущение об унимодальности целевой функции, при нарушении допущения следует брать несколько исходных точек. Метод Дэвидона -Флетчера - Пауэлла позволяет обходить трудности, связанные с разрывами производных в пространстве проектирования. Распространено мнение, что этот метод наиболее эффективен из всех градиентных методов, дает полную информацию о кривизне поверхности целевой функции в точке минимума, однако при этом требуется больший объем памяти и длительность счета. При исследовании унимодальной функции, откуда бы ни начинался поиск, вычисления приведут к нужной точке. На рис. 6 приведены линии уровня функции с двумя локальными минимумами в точках 0] и 02, Сравнивая между собой значения функции в точках Oi и 02, находят, что наименьшее значение функции достигается в точке 02.
Пример функции с двумя локальными минимумами в точках 0{ и Рис. 6. Если начать поиск наименьшего значения с помощью градиентного спуска из точки Ах, поиск приведет в точку 0{, которую ошибочно можно принять за искомый минимум, С другой стороны, если поиск начинается с точки А2, то вычисления приведут в точку 02.
Принято считать /11, 90, 95/, что универсального приема, который бы позволил эффективно справляться с многоэкстремальностью, не существует. Самый простой прием состоит в том, что проводят поиск несколько раз из разных начальных точек. Если при этом получаются разные значения целевой функции, то сравнивая их, выбирают наименьшее /90, 106/, Расчеты останавливают после того, как несколько новых поисков не меняют полученного ранее результата. Выбор начальных точек поиска, обоснованность прекращения расчетов в значительной степени зависят от опыта и интуиции специалистов, решающих задачу. Во многих случаях необходима различная дополнительная информация о характере задачи, которая существенно помогает при выборе метода, начальной точки поиска. Если нет никаких предположений о специальных свойствах целевой функции и о характере рассматриваемой области, это затрудняет анализ. Конкретизация задачи, выделение определенных классов функций и областей позволяет провести более глубокое исследование и разработать специальные методы, которые решают задачу исчерпывающим образом. П. Исследование ландшафтов целевых функций на основе эволюционной оптимизации. В рамках подхода к решению задач оптимизации исследуется возможность применения эволюционных и генетических алгоритмов /10, 13/. При этом строятся новые целевые функции, обеспечивающие получение оптимальных решений для исходных функций /54/. Использование одних и тех же целевых функций в рамках схемы эволюционных алгоритмов часто приводит к достижению локального, но не глобального экстремума. По этой причине возникает идея замены одной целевой функции на другую при условии, что это приводит к эквивалентному результату. Актуальна задача выбора эффективной целевой функции на ранней стадии разработки нового алгоритма. Для выбора такой функции конструируются подходы на основе анализа ландшафтов целевой функции /32, 57/. Разработанные в данном аспекте методы ориентированы на получение интегральных параметров ландшафта целевой функции, которые определённым образом характеризуют её сложность для эволюционных алгоритмов. Чтобы оптимизировать функцию модифицируется алгоритм расчета интегральных параметров на основе барьерных деревьев. На этой основе выделяются компоненты, по которым можно судить об эффективности соответствующих им целевых функций для эволюционных алгоритмов. Метод барьерных деревьев /57/ позволяет оценить глубину каждого локального минимума и степень его влияния на процесс эволюционного проектирования. Основная идея метода заключается в том, что сложность поверхности отражает высота h, на которую необходимо подняться, чтобы попасть из одного локального минимума в другой.
Подход включает следующие затруднения. Сравнивать целые наборы величин затруднительно, поскольку количество локальных оптимумов обычно различно для различных целевых функций. Кроме того, для автоматического сравнения желательно иметь один интегральный параметр. Поэтому необходимо оценить вероятность не возникновения преждевременной сходимости. Для этого достаточно, чтобы генетический алгоритм мог выйти из текущего локального оптимума и найти другой с лучшим значением. В случае успеха он вероятнее найдёт локальный оптимум, который ближе всего находится к текущему локальному оптимуму. Производится /54/ переход от набора параметров локального минимума к единственному параметру оценки области локального минимума. /(х,,х - минимальный
барьер, который необходимо преодолеть, чтобы попасть из локального оптимума / в локальный оптимум j. Барьер - это наивысшая точка некоторого пути. Чтобы
получить только один интегральный параметр для всего ландшафта, достаточно выделить из всех локальных оптимумов тот, выход из которого наиболее сложен. Значение такого оптимума интерпретируется как глубина В ландшафта. Для сравнения ландшафтов берётся отношение глубины к общей высоте ландшафта, которое называется сложностью ц/. Для сравнения ландшафтов используются два параметра - глубина В и сложность у/.
Основная идея определения всех локальных оптимумов состоит в предварительной дискретизации пространства неравномерной сеткой. После этого для определения является ли некоторая точка локальным или глобальным оптимумом достаточно просмотреть соседние для неё точки. В результате получается линейный алгоритм сложности 0(3nN), где yV -количество точек исходной выборки, а п размерность пространства. Положительные результаты достигаются в случае поверхности близкой к классу унимодальных и при достаточных размерах области локализации экстремума /54/. Количество найденных решений зависит от модальности функции.
VII. Предварительная характеристика проблем вычислительных схем оптимизации. Как отмечалось, принята точка зрения /6, 20, 50, 90/, что не существует универсального алгоритма численного решения задач оптимизации. Метод, приспособленный к одному типу рельефа функции, может оказаться непригодным на рельефе другого типа. При решении сложных задач оптимизации пользуются несколькими методами, чтобы увеличить долю удачных решений. Поиск экстремума выполняется несколько раз с различными начальными приближениями, сравнивая значения целевой функции и выбирая наименьшее (наибольшее). Итерации прекращаются, когда несколько повторений не меняют результата.
Можно отметить, что по причинам изложенных затруднений в рамках существующих вычислительных схем безусловной оптимизации не ставится задача автоматического определения всех локальных экстремумов функции в области допустимых значений. Существующие системы компьютерной математики /41/ реализуют разнообразные схемы вычисления экстремальных значений функций. В частности, в Mathcad для определения экстремумов функций реализованы градиентные методы, включая метод сопряженных градиентов, метод Левенберга /41, 106/. В пакете Maple исследование на экстремум функции заключается в нахождении точек, в которых производная исследуемой функции равна нулю /41/. Устойчивая работа математических пакетов зависит от сложности исследуемой функции. Иногда пакеты не могут указать точку экстремума, лишь представляя исследуемую функцию графически. В этом случае не идентифицированы числовые значения, а графически они отображены с малой точностью разрешающей способности графического редактора. Сложности использования пакетов усугубляются для функций многих переменных.
Вычислительные методы безусловной оптимизации глубоко опираются на аналитические критерии экстремумов классической математики. Как отмечалось, для компьютерной идентификации аналитических признаков, основанных на поведении производных, их аналитические выражения заменяются на конечно-разностные приближения значений. Следствием может оказаться потеря точности идентификации экстремумов, иногда - потеря самих экстремумов. С другой стороны, переборные методы могут оказаться неэффективными и быть не чувствительными к сложностям рельефа целевой функции, особенно, в случае функции нескольких переменных.
Рассмотренные схемы (возможно, в виду затруднений), не предполагают автоматической идентификации области экстремумов, требуют начального приближения, игнорируют наличие экстремумов в некоторых сложных случаях, либо не достигают в этих случаях требуемой точности вычислений.
Зачастую трудности решения актуальных задач оптимизации /42, 46/, включая задачи современной теории управления /34, 56/ сводятся к отмеченным трудностям известных методов безусловной оптимизации.
Отсюда актуальна разработка программного метода локализации экстремумов функций, который бы выполнял автоматическую идентификацию области каждого экстремума и отличался бы существенным ограничением роста погрешности при его вычислении.
В качестве основы разработки целесообразно рассмотреть алгоритмы сортировки, поскольку они включают лишь операции сравнения и сами по себе не накапливают погрешности.
Сортировки традиционно применяются для поиска и моделирования методов теоретической информатики /102/. Положительный опыт применения сортировки именно для схем оптимизации описан в /77-79, 71, 75/. При этом необходимо принять во внимание параллелизм сортировки /77, 82/, который влечет возможность построения параллельных схем определения экстремумов в целом.
К одной из целей диссертационной работы относится исследование применимости сортировки для идентификации всех локальных и глобальных экстремумов функций одной и нескольких переменных в области допустимых значений. Конкретно, затрагивается проблема автоматической программной идентификации всех экстремумов произвольной алгебраической и трансцендентной функции одной и нескольких переменных, в произвольно фиксированной части области определения. Требования устойчивости и быстродействия идентификации экстремумов обеспечиваются за счет устойчивости и параллелизма схем на основе сортировки.
На основании изложенного целесообразно исследовать возможность разработки единой схемы оптимизации на общей основе алгоритмов распараллеливаемых сортировок. Более точно, формулируется следующая цель.
Цель диссертационной работы заключается в разработке и исследовании единой алгоритмической схемы решения задач оптимизации на основе применения алгоритмов сортировки. Цель включает разработку и программную отладку схем автоматической программной идентификации всех экстремумов функций в области допустимых значений. Помимо того, аналогичная задача ставится для идентифика-ципи всех экстремумов разностных решений систем обыкновенных дифференциальных уравнений (ОДУ) и уравнений в частных производных, а также для идентификации многомерной точки экстремума нормы решений систем ОДУ при вариации параметров. Наряду с этим исследуется применение схем к приближенному решению задач условной оптимизации.
Предполагается, что конструкция схем идентификации экстремумов и нулей функций должна быть инвариантной относительно вида функции, ее топологических особенностей, а также числа переменных. В частности, схема должна быть инвариантной относительно правой части системы ОДУ, относительно выбора разностных схем, относительно длины промежутка и шага решения. При этом должна достигаться устойчивость работы схем и требуемая точность вычислений, схемы должны эффективно распараллеливаться.
Иными словами, цель состоит в разработке и исследовании схем автоматической программной идентификации экстремумов функций в произвольной части их области определения не на математической, а исключительно на алгоритмической основе. В качестве базового алгоритма выбирается алгоритм устойчивой (сохраняющей порядок равных элементов) распараллеливаемой адресной сортировки (используются параллельные сортировки подсчетом и слиянием).
Для достижения поставленной цели в диссертационной работе ставятся следующие задачи:
1. Разработать и исследовать распараллеливаемые схемы устойчивой программной идентификации всех локальных и глобальных экстремумов, а также нулей функций одной и более переменных на основе сортировки в области допустимых значений. Искомые схемы должны быть инвариантными относительно области поиска и вида функции при условии ее дискретного представления на входе схемы.
2. Исследовать границы применимости схем автоматической идентификации экстремумов на основе сортировки для функций с рельефом значений различной топологической сложности; выполнить оценки временной сложности максимально параллельного варианта предложенных схем.
3. Разработанные на основе сортировки схемы применить для идентификации всех экстремумов и нулей разностных решений систем ОДУ на произвольном промежутке; оценить достоверность идентификации в случае разностных схем различного порядка, включая методы Эйлера, Эйлера - Коши и Рунге - Кутта.
4. Обеспечить инвариантность программной идентификации экстремумов и нулей разностного решения системы ОДУ относительно правой части системы, разностных схем решения, а также относительно числовых параметров из экспериментально устанавливаемого диапазона значений, включая длину промежутка и шаг решения.
5. На той же основе построить схему программной идентификации экстремумов и нулей разностного решения уравнений в частных производных; провести численный и программный эксперимент в условиях меняющихся значений числовых параметров схемы и установить границы параметров, при которых сохраняется достоверность идентификации.
6. Видоизменить основанную на сортировке схему для программной идентификации глобальных и локальных экстремумов нормы разностного решения систем ОДУ при вариации параметров и исследовать связь видоизменения с оценкой устойчивости решения; дать аналоги схемы для случаев вариации параметров трансцендентных, алгебраических уравнений и уравнений в частных производных.
7. Показать применимость схем оптимизации на основе сортировки для задач условной оптимизации, на основе численных экспериментов установить границы применимости схем для задач линейного и нелинейного программирования.
8. Выполнить сравнительный анализ устойчивости, точности, инвариантности и корректности предложенных схем путем проведения программного и численного экспериментов, в рамках эксперимента подтвердить достоверность результатов оптимизации на основе сортировки.
Методы исследования базируются на теории многомерной оптимизации, теории разностных схем решения дифференциальных уравнений, теории сложности, качественной теории устойчивости, включают схемы линейного и нелинейного программирования, алгоритмы параллельных вычислений и параллельных сортировок.
Достоверность результатов вытекает из их математического обоснования, подтверждается оценками временной сложности, а также результатами программного моделирования и численного эксперимента.
Научная новизна диссертационной работы заключается в построении обобщенной схемы применения сортировки для решения задач оптимизации. Как частный случай, в нее включаются схемы автоматической программной идентификации всех экстремумов и нулей дискретно представимых функций общего вида, аналогичные схемы для разностных решений систем ОДУ и уравнений в частных производных, схемы для задач условной оптимизации.
Предложенный подход отличается тем, что не использует аналитическое и конечно-разностное представление производных, не опирается на начальное приближение. Отличие от переборных методов заключается в использовании упорядочения входной информации с помощью сортировки и в циклической идентификации локальных экстремумов на основе подстановки индексов отсортированных элементов.
Конкретно, научная новизна характеризуется следующим образом:
1. На основе сортировки синтезированы схемы идентификации экстремумов функций многих переменных, которые отличаются от известных по построению. Схемы отличаются, помимо того, возможностью автоматической локализации одновременно всех экстремумов и нулей функций из области допустимых значений, вычислительной устойчивостью, параллелизмом с единичным порядком временной сложности максимально параллельной формы.
2. Показано, что схема локализации всех экстремумов функций многих переменных с рельефом различной топологической сложности не включает ограничений на вид входной функции, отличаясь этим от известных методов; от методов перебора схема отличается сортировкой входных данных и идентификацией экстремальных элементов в произвольной окрестности с использованием только подстановки индексов отсортированных элементов.
3. Предложена схема идентификации экстремумов и нулей разностных решений систем ОДУ, которая отличается от известных методов по построению на основе сортировки, инвариантностью относительно правой части системы, а также относительно разностных методов решения и длины промежутка разностного решения.
4. Разработана схема программной идентификации экстремумов и нулей разностных решений уравнений в частных производных, отличающаяся от известных по построению. Схема не включает иных математических операций, кроме сравнения входных дискретных значений, поэтому не вносит дополнительной погрешности, помимо погрешности дискретизации; отличие заключается также в устойчивости и параллелизме схемы, опирающемся на параллельность сортировки.
5. Предложено видоизменение основанной на сортировке схемы для автоматической программной идентификации глобальных и локальных экстремумов нормы разностного решения системы ОДУ при вариации параметров. Схема отличается областью применения численной оптимизации и программной оценкой возмущения решения системы ОДУ при вариации параметров.
6. Дано применение схемы оптимизации на основе сортировки для численного решения задач линейного и нелинейного программирования. Отличаясь единством построения в этих случаях, схема позволяет программно идентифицировать глобальные и локальные экстремумы целевой функции при заданных ограничениях.
7. На основе предложенных схем безусловной оптимизации идентифицируются нули и особенности передаточных функций динамических систем при наличии трансцендентности, выполняется компьютерный анализ их устойчивости, исследуется распределение нулей характеристического многочлена и полюсов передаточной функции на комплексной плоскости для линейного стационарного четырехполюсника.
Основные положения, выносимые на защиту:
1. Инвариантные относительно вида функции схемы оптимизации на основе сортировки, которые программно выполняют идентификацию всех экстремумов и нулей функции произвольного вида от нескольких переменных и отличаются существенным ограничением роста погрешности при вычислении экстремумов.
2. Схемы программной идентификации на основе сортировки всех экстремумов и нулей разностных решений систем ОДУ и уравнений в частных производных в произвольной части области сходимости разностных методов.
3. Схема применения сортировки для программной идентификации экстремумов норм разностных решений систем ОДУ при вариации параметров системы с приложением к компьютерному анализу устойчивости решения.
4. Основанная на сортировке схема численного решения задач условной оптимизации в области линейного и нелинейного программирования, отличающаяся единством построения и позволяющая программно идентифицировать глобальные и локальные экстремумы целевой функции при заданных ограничениях.
Связь с плановыми исследованиями, проводимыми по месту выполнения диссертационной работы. Диссертационная работа выполнялась в рамках госбюджетной НИР «Математические методы устойчивой параллельной обработки, поиска и распознавания» (№ гос. регистрации 01.2.00 106436, код ГРНТИ 28.23.15), проводимой на кафедре информатики ГОУВПО ТГПИ в рамках приоритетного направления развития науки и техники в РФ «Информационные и телекоммуникационные системы» в соответствии с перечнем критических технологий РФ «Технологии обработки, хранения, передачи и защиты информации» по направлению фундаментальных исследований «Информатика. Искусственный интеллект, системы распознавания образов, принятие решений при многих критериях».
Практическая ценность диссертационного исследования заключается в прикладном характере предложенных схем численной оптимизации, которые ориентированы на компьютерную реализацию и актуальны для решения научно-технических задач в различных областях, включая проектирование электрических цепей, оптимизацию конструкции летательных аппаратов, задачи об ударах и колебаниях с определением амплитуды резонанса при наличии источников колебаний. Предложенные схемы оптимизации могут найти применение в промышленной технологии, в системах автоматического регулирования, управления и контроля.
Внедрение и использование результатов работы. Полученные в работе результаты использованы
1. В ОАО «Таганрогский завод «Прибой», приняты к использованию в качестве единой алгоритмической схемы оптимизации функционалов при обработке алгоритмов автоматической классификации гидроакустических изображений.
2. В госбюджетной НИР «Математические методы устойчивой параллельной обработки, поиска и распознавания» (№ гос. регистрации 01.2.00 106436, код ГРНТИ 28.23.15), проводимой на кафедре информатики ГОУВПО ТГПИ.
3. В учебном процессе кафедры информатики Таганрогского государственного педагогического института в рамках курсов «Информатика», «Информационные технологии в математике», «Численные методы», «Элементы абстрактной и компьютерной алгебры».
Апробация работы. Основные результаты работы докладывались на:
— X, XI международных конференциях «Математические модели физических процессов» (Таганрог, ТГПИ, 2004,2005 гг.);
— V международной научно-практической конференции по программированию УкрПРОГ 2006 (Украина, Киев, 2006 г.)
— VIII международных научно-практических конференциях «Фундаментальные и прикладные проблемы приборостроения, информатики, экономики и права» (Москва, МГАПИ, 2005 гг.);
— VI научно-практической конференции преподавателей, студентов, аспирантов и молодых ученых (Таганрог, ТИУиЭ, 2005 г.);
— IV-й международной научно-практической конференции «Проблемы регионального управления, экономики, права и инновационных процессов в образовании» (Таганрог, ТИУиЭ, 2005 г.);
— Ill межрегиональной научно-практической конференции студентов, аспирантов и молодых ученых «Молодежь XXI века - будущее российской науки» (Ростов, РГУ, 2005г.); — международной научно-практической конференции «Модернизация отечественного педагогического образования: проблемы, подходы, решения» (Таганрог, ТГПИ, 2005 г.)
Публикации. По материалам диссертационной работы опубликовано 13 печатных работ с общим объёмом 14,3 печатных листов.
Структура и объём работы. Диссертационная работа состоит из введения, 3 глав основного раздела, списка литературы и 5 приложений. Основное содержание работы изложено на 153 страницах, включая список литературы из 120 наименований.
Алгоритм автоматической идентификации экстремальных значений одномерной последовательности на основе сортировки
Пусть программно требуется идентифицировать все минимальные и максимальные значения одномерного массива (1.17). Способ заключается в следующем. Используется сортировка одномерного массива.
Для конструируемой идентификации экстремумов способ дополнительно включает алгоритмическое условие локализации каждого экстремального элемента последовательности (1.17). Это условие выполняется в программе вслед за сортировкой, осуществившей перевод входного массива (1.17) в выходной массив (1.20). Условный оператор осуществляет локализацию каждого минимума в окрестности произвольно заданного радиуса є среди элементов (1.17) при условии, что радиус меньше половины расстояния между любыми двумя соседними минимумами. Такой оператор можно представить соотношением \е[к-1] е[к]\ є, / = 1,2,..., -1. (1.21)
В этом фрагменте ппО- число элементов, epsO- радиус окрестности текущего индекса (epsO имеет тот же смысл, є что в (1.21)). В операторе локализации epsO можно заменить натуральным числом, например, 3, если epsO = 3. Оператор работоспособен при любом меньшем значении натурального числа в диапазоне от 1 до 3, при неизменности априорного задания epsO.
Необходимо отметить, что данная схема не меняет значений экстремумов, поскольку только сравнивает элементы последовательности, но не преобразует их. Это качество систематически используется в дальнейшем. Оно обеспечивает поиск экстремумов с точностью до шага дискретизации входной функции. С таким шагом дискретные значения нумеруются, образуя массив на входе сортировки, и значения элементов этого массива более нигде не изменяются по ходу метода.
Схема автоматической идентификации всех экстремумов функции одной действительной переменной на основе сортировки.
Элементы (1.24) поступают на вход сортировки и сортируются. К выходу процедуры sort подсоединяется условный оператор, осуществляющий локализацию каждого минимума в окрестности произвольно заданного радиуса є среди элементов (1.24), при условии, что радиус меньше половины расстояния между любыми двумя соседними минимумами. Такой оператор можно представить соотношением (1.21), с помощью которого локализуются минимальные значения исследуемой функции в наперед заданной окрестности.
Локализовать элемент в рассматриваемом смысле можно только при сохранении обратных адресов на выходе сортировки, причем строго в том порядке, в каком располагаются отсортированные элементы.
В дальнейшем под локально минимальным элементом дискретной последо 51 вательности понимается тот, который найден с помощью оператора локализации минимума (1.21).
Данная ранее трактовка оператора локализации минимума непосредственно ниже конкретизируется с учетом значения аргумента функции. Работая после процедуры сортировки, данный оператор для текущего узла, определяемого индексом, записанным в е[к], находит каждый узел хО + е[&] /г, в є- окрестности которого нет узлов, доставляющих значения элементов входной числовой последовательности, предшествующие с[е[]] в отсортированном массиве. Это означает, в частности, что значение функции в узле 0 + е[] /г не больше значений в остальных узлах его є -окрестности, точнее, - строго меньше, или это значение является первым слева направо среди равных на выходе отсортированного массива. Это обусловлено тем, что при выполнении (1.21) с [е[к]]является в данной окрестности наименьшим в смысле отношения порядка , что не полностью совпадает со смыслом арифметического неравенства. Среди узлов с равными значениями решения в рассматриваемой окрестности - при истинности оператора (1.21) - оператор локализации минимума всегда фиксирует узел, соответствующий первому в порядке нумерации элементу отсортированного массива, независимо от его расположения на сетке. Этот факт опирается на устойчивость сортировки sort - сохранение порядка равных элементов. Здесь є - то же, что в (1.21), (1.22), его программный идентификатор в (1.25) обозначен epsO.
Присоединение программного оператора (1.25) к программе сортировки элементов массива (1.24) дает устойчивую локализацию минимумов исследуемой функции (1.23) /78, 79/. В операторе локализации (1.21) epsQ/h можно заменить натуральным числом. Смысл такой замены - в измерении е-окрестности локального минимума целочисленным количеством шагов, определяющих расстояние между узлами сетки. Данное количество с точностью до единицы совпадает с числом узлов в этой окрестности и, соответственно, с числом считанных элементов одно 52 мерного массива из значений функции в узлах. Инвариантность схемы относительно вида функции и размеров промежутка поиска экстремумов. При изменении размеров промежутка ставится цель не использовать определение динамических массивов. В результате программной особенностью конструируемой схемы должна стать ее инвариантность относительно границ стационарных массивов. При этом сохраняется ограничение, определяемое числовым диапазоном языка программирования.
Искомые программные особенности достигаются на следующей основе. На входе алгоритма (в разделе констант программы) задается число сортируемых элементов «00 (равное числу узлов сетки N). Узлы первоначально определяются на текущем промежутке [хт, x{N) ] постоянной длины иООх/г. После отработки схемы на текущем промежутке (в конце приводимой ниже программы) производится смещение текущего промежутка на его длину до тех пор, пока не будет пройден весь априори заданный промежуток, обозначаемый [ , ]. При анализе на экстремум, во избежание ложных экстремумов (они могут появляться на концах текущего промежутка), отсекаются обе границы текущего промежутка. Дополнительная проверка отсекаемых границ на экстремумы производится с помощью еще одной сортировки sortOO. При достижении границ полностью воспроизводится процесс сортировки и локализации экстремумов по ранее описанной схеме для элементов массива, образуемых значениями функции (1.23) слева от правой границы и справа от левой границы.
Этим достигается инвариантность схемы относительно размеров промежутка поиска экстремумов. По построению схема инвариантна относительно вида функции (1.24), на которую не накладывается математических ограничений.
Функция, в частности, может быть задана таблично, в этом случае спуск окажется излишним.
В программе дополнительная проверка на ложный минимум осуществляется с помощью процедуры sortOO, присоединяемой к выходу процедуры sort, и соответственного программного фрагмента оператора (1.21) для значения п00« элементов в окрестности границы исследуемого промежутка. Предложенная схема автоматически локализует и вычисляет все экстремумы функции одной действительной переменной на произвольно заданном промежутке из области определения функции.
Качеством автоматической программной идентификации значений всех локальных экстремумов и значений их аргументов в окрестности локализации произвольного радиуса описанная схема отличается от известных методов безусловной оптимизации. Это качество в дальнейшем распространяется на функции многих переменных, его отличительные особенности детально обсуждаются ниже в разделе сравнения излагаемого метода с известными.
Следует отметить, что длина смещаемого промежутка [ (0), xiN) ] не должна превышать длину исходного промежутка [ , ] поиска экстремумов. Кроме того, длина промежутка [ х{0), x N) ] не должна быть меньше длины радиуса окрестности є (в программе epsO). Ограничение имеет технический характер и сохраняется для области поиска экстремумов функции двух и более переменных.
Схема автоматической идентификации экстремумов функций трех и более переменных
При фиксировании индекса і этот минимум заносится на вход описанной сортировки sort как элемент c[i] сортируемого в дальнейшем одномерного массива. К выходу процедуры подсоединяется условный оператор, локализующий после выполнения сортировки все минимумы среди этих значений. Оператор локализации минимума выбран в виде (1.21). Работая после сортировки, оператор для текущего узла, определяемого индексом, записанным в ех[к], находит каждый узел xO + e;c[&] /z, в проекции epsO -окрестности которого на ось ОХ нет узлов, доставляющих значения элементов входной последовательности, предшествующие с[ех[Л:]] в отсортированном массиве.
Теперь при фиксированном значении локализованной абсциссы xk:=xO + ex[k] h осуществляется проход по направлению оси OY вдоль каждого столбца оси OZ, во время которого находится минимальное (максимальное) по строкам (матрицы узлов сетки на плоскостиYOZ) значение: с[р]= min f(xk,y,z). p=const \ j M
При фиксировании номера столбца, этот минимум заносится на вход описанной сортировки sort как элемент с[р] сортируемого одномерного массива. Работая после сортировки, оператор локализации минимума (максимума) для текущего узла, определяемого индексом, записанным в ez[l], находит каждый узел zO + ez[&l] /j, в проекции еряО-окрестности которого на ось OZ нет узлов, доставляющих значения элементов входной последовательности, предшествующие c[ez[&l]] в отсортированном массиве. Значения локализованных абсцисс точки минимума (максимума) xk:=xO + ex[k] h, zk := zO + ez[ki] h дают привязку к локализуемой точке трехмерного минимума (максимума), оно фиксируется и аналогичным образом локализуется ордината ук := уО + еу[к2] h, в которой достигается приближение к минимальному (аналогично к максимальному) значению f(x,y,z) из (1.29).
Ниже (рис. 1.5) представлена блок-схема локализации минимума функции трех переменных. Программа идентификации экстремумов функции трех переменных приводится в / 86 / и в приложении к главе 1, п 1.3. Непосредственно ниже приводится алгоритм и программа автоматической идентификации функций четырех переменных, которая включает описанный вариант как частный случай.
Схема идентификации экстремальных значений функции четырех переменных аналогична схеме идентифицирующей экстремумы функции трех переменных. В качестве привязки используется программно вычисляемый минимум (аналогично, максимум) этой функции, который вначале берется по трем переменным при фиксировании четвертой, затем по двум переменным при фиксированных двух других, а затем по одной переменной при фиксировании трех переменных. Экстремумы по фиксируемым переменным после их использования в качестве привязок локализуются программно по аналогии с описанной выше схемой. Программная реализация схемы идентификации экстремумов функции трех и более переменных требует существенных затрат машинного времени. По этой причине реализация представлена только для локализации экстремумов без спуска к локализованному значению.
Первоначально фиксируется одна переменная , и для каждого текущего ее значения на равномерной сетке находится минимум (аналогично, максимум) функции (1.30), который берется по п-\ другим переменным. Все такие минимумы (максимумы) поступают на вход сортировки в виде одномерной последовательности, после чего оператор локализации идентифицирует среди элементов данной последовательности все локальные минимумы (максимумы). Каждая локализованная координата фиксируется (по аналогии со случаем функций двух, трех и четырех переменных) и дает привязку по этой координате к искомому локальному минимуму (максимуму) п - мерной функции.
После этого, при каждой фиксированной локализованной координате, для оставшихся п-\ других координат возобновляется процесс, полностью идентичный только что описанному для п первоначальных координат. Конкретно, минимумы по п - 2 переменным при фиксированной локализованной координате, взятые при каждом текущем значении другой переменной на равномерной сетке, образуют новую одномерную последовательность. Эта последовательность, в свою очередь, поступает на вход сортировки, и с помощью оператора локализации идентифицируются все значения второй координаты искомых локальных минимумов. Далее, при фиксировании локализованных координат процесс возобновляется для оставшихся п 3 координат и так далее, пока в заданном порядке не будут перебраны все независимые переменные функции (1.30).
Данная схема устойчиво программно идентифицирует (локализует) экстремумы с точностью до дискретизации входных значений функции (1.30). Замечание 1.8. Изложенная схема безусловной оптимизации отличается от известных /62, 100/ построением на основе сортировки, автоматичностью программной локализации нулей и экстремумов, отсутствием ограничений на вид входной функции. В отличии от схем, ориентированных только на вычисление нулей /85/, изложенная схема позволяет вычислять как плохо отделенные нули так и произвольные экстремумы в произвольной области. Отличие достигается за счет исключения эвристических элементов при обнаружении ложных экстремумов на стыке текущих промежутков. На этой основе схема приобретает качество программно реализованного алгоритма со свойством массовости в рассматриваемом классе задач безусловной оптимизации. Схема обладает параллелизмом на основе разбиения области на взаимно независимые фрагменты, а также на основе параллелизма использованных сортировок /80, 81/.
Параллелизм схемы автоматической идентификации экстремумов и нулей функций многих переменных. Существенным качеством предложенной схемы является ее параллелизм. На основе взаимной независимости рассматриваемого алгоритма относительно всех фрагментов в произвольно выбранном прямоугольном разбиении области, произведем оценку параллельного по данным фрагментам выполнения предложенного алгоритма (листинг примера 1.5).
Идентификация на основе сортировки экстремумов разностного решения системы дифференциальных уравнений второго порядка
Описанная для одного уравнения схема безусловной оптимизации без принципиальных изменений переносится на случай двух и более уравнений путем буквального повторения для каждого уравнения в отдельности. Конкретно для случая двух уравнений схема формализуется следующим образом.
Конструируемый алгоритм ниже представлен в форме программы, в которой одновременно идентифицируются все локальные минимумы и максимумы разностного решения системы вида (2,4) в окрестности произвольно заданного радиуса epsQ. Экстремумы идентифицируются при помощи двух процедур xyl, ху2 - для первого и второго уравнения, соответственно. Программа пригодна для произвольной правой части (2,4), с точностью до задания в разделе описаний подпрограмм function fl, function f2, в теле которых задаются конкретные правые части, соответственно, первого и второго уравнений (2,4), В примере 2.2 в рамках схемы удается идентифицировать все локально экстремальные значения разностного приближения к каждой координате решения уравнения (2.6) с точностью до формата представления данных на произвольно заданном промежутке. Программа применима к произвольной системе ОДУ вида (2.4) при условии соответственного задания function fl, function f2 в разделе описаний. Программно представленный в примере 2.2 алгоритм инвариантен относительно длины промежутка разностного решения, с точностью до накопления погрешности разностного метода при вычислении приближений входных элементов сортируемого массива.
Необходимо отметить следующее существенное ограничение на выбор параметров программы. Замечание 2.2. Как и в случае одного уравнения первого порядка, длина смещаемого текущего промежутка [ х0, хп ] не должна превышать длину исходного промежутка [А оо, ] поиска экстремумов разностных решений ОДУ. Кроме того, длина промежутка [ х0, хп ] не должна быть меньше значения радиуса окрестности epsO. Данное ограничение существенно не только для уравнений вида (2.1), (2.4), но и для случая безусловной оптимизации функций, как уже отмечалось в главе 1. В дальнейшем это ограничение сохраняется для области поиска экстремумов разностных решений систем ОДУ произвольной размерности.
Предложенная схема не требует применения специальных математических приемов, ввода математических ограничений и предварительной обработки разностных значений решения ОДУ. Для применения метода, по-прежнему, достаточно сформировать входной массив дискретных значений и применить изложенную схему идентификации экстремумов числовой последовательности.
Как отмечалось, схема не накапливает погрешность, обладает точностью идентификации экстремумов в той мере, в какой это допускает граница погрешности разностного метода приближенного решения задачи Коши.
Алгоритм в программном представлении строится совершенно аналогично программно представленному для случая двух уравнений алгоритму program ejlerl, при этом учитывается специфика формул Эйлера-Коши, запрограммированная непосредственно выше, и конкретный вид правой части системы (2.4).
Замечание 2.3. При означенном выборе шага h = 0.0000001 результатом работы программы оказались все значения экстремумов решений системы уравнений (2.6), вычисленные на рассматриваемом промежутке с точностью до 14 верных знаков после десятичной точки. В численных экспериментах этот результат достигался для каждого из трех разностных методов - Эйлера, Эйлера-Коши и Рунге-Кутта Для каждого из них все экстремальные значения решений системы дифференциальных уравнений (2.6), соответственные данному выбору eps0 = 0.001, удавалось найти фактически без погрешности в рамках формата представления чисел при отмеченном выборе шага. Такой же результат достигался при произвольном значении epsO, меньшем половины расстояния между двумя соседними минимумами (максимумами). Для решений ух = sin , у2 = cosx системы (2.6) epsO окрестность выбиралась меньше одного полупериода.
Этот результат объясняется следующим образом. Все значения решения ОДУ поступают на вход сортировки в том первоначальном виде, в котором они были получены при помощи разностной схемы. Алгоритм сортировки включает лишь операции сравнения (из числа математических) и сам по себе не изменит погрешности входных данных. Аналогично, на эту погрешность не окажут влияния операции сравнения индексов в операторах локализации экстремумов. Поэтому предложенная схема обладает точностью приближения в той и только в той мере, в какой это допускает граница погрешности разностной схемы приближенного решения задачи Коши. Регулировать погрешность нахождения экстремумов можно только путем уменьшения шага h разностной схемы и путем выбора самой разностной схемы решения.
На основании изложенного можно сформулировать следующее Предложение 2.1. Рассматриваемая схема программно идентифицирует на основе сортировки все экстремумы дискретно представленной функции одной действительной переменной на произвольном промежутке из области определения функции, с точностью до погрешности дискретизации входных значений на равномерной сетке.
Следствие 2.1. В частности, если с помощью такой функции задается каждая координата разностного приближения решения системы ОДУ, то данная схема программно идентифицирует все экстремумы каждой компоненты решения на произвольном промежутке из области допустимых значений независимой переменной, с точностью до погрешности разностного приближения решения.
Необходимо принять во внимание, что входная погрешность разностной схемы приближенного решения задачи Коши принципиально зависит от устойчивости этого решения в смысле Ляпунова.
Данное обстоятельство является следствием неустойчивости решения в смысле Ляпунова. Особенности вычислительной устойчивости приближенного решения дифференциальных уравнений и устойчивости решений в смысле Ляпунова ограничивают возможности предложенной схемы безусловной оптимизации разностных решений ОДУ. Следует, однако, заметить, что данные ограничения сохраняют силу по отношению к любому математическому методу нахождения экстремумов решения задачи Коши, в то время как применить такой метод для программного нахождения экстремумов по разностному приближению решения дифференциального уравнения затруднительно.
В целом, численный эксперимент показывает, что по изложенной схеме возможно локализовать и идентифицировать с высокой точностью все экстремальные значения разностных решений систем ОДУ в произвольно заданной области внутри области существования решения при условии сходимости разностной схемы.
В произвольно фиксированной области метод позволяет программно локализовать и с высокой точностью приближения найти все экстремальные значения решения системы ОДУ путем непосредственного переноса изложенной схемы со случая п= 2 на случай произвольного п. Число уравнений может быть произвольным при произвольной правой части, произвольна длина промежутка изменения независимой переменной при наличии сходимости и устойчивости.
Применение алгоритма многомерной оптимизации к поиску экстремумов нормы возмущений решений систем нелинейных ОДУ при вариации параметров
Поставим задачу найти максимальное и минимальное отклонение от нуля нормы разности между возмущенным и невозмущенным решениями ОДУ (3.4) при условии вариации числовых параметров, заданных в виде коэффициентов правой части (3.4) (задача может ставиться и аналогично решаться для системы с произвольным числом уравнений).
Одна из целей такой постановки вопроса - исследование системы нелинейных ОДУ на предмет устойчивости при вариации параметров. Другая цель - конкретная оценка отклонения возмущенного решения в случае вариации параметров.
Метод сводится к программной идентификации экстремумов функций четырех переменных при помощи сортировки.
Норма разности решений системы (3.4) при возмущенных и невозмущенных начальных данных формируется для взятых с постоянным шагом (варьируемых) значений коэффициентов а\, а2, аЪ. Диапазоны вариации коэффициентов соответственно обозначены в виде alO al all, а20 а2 а2\, аЗО аЗ а31. В данных диапазонах выбираются дискретные значения варьируемых коэффициентов с шагами, соответственно, haly, ha2w и ha3z. Их количество соответственно обозначено nnny, nnnw и nnnz. Выбранные значения задают трехмерный массив, к которому добавляется еще одно измерение по независимой переменной t, обозначаемой в программе х. Диапазон ее изменения фиксируется в промежутке хОО л: д:11, равномерный шаг дискретизации обозначается АО, число шагов обозначено nnnx. С этими шагами по четырем данным значениям переменных считы-ваются значения рассматриваемой нормы. Для определенности рассматривается эвклидова норма разности возмущенного и невозмущенного решений = . -Ух\ +1 -5 +1 3-2 (3-5)
В итоге сформируется дискретное представление функции (3.5) от переменных а\, а2, аЗ, х вобласти д10 а1 а11, а20 а2 а21, д30 дЗ д31, х00 х х11. с указанными шагами дискретизации. Далее задача оптимизации решается по описанной ранее для функции четырех переменных схеме.
При конкретном осуществлении рассматриваемой схемы система (3.4) решается методом Эйлера (при достаточно малом шаге h) для каждого сочетания коэффициентов а\, я2 и оЗ. В то же время на промежутке хОО ,v х\ 1 шаг дискретизации независимой переменной АО существенно превосходит шаг h.
В результате формируется четырехмерный массив, который в программе обозначается norma\[rx,ry,rw,rz] (в квадратных скобках - его индексы), элементами которого являются значения нормы разности возмущенного и невозмущенного решений (3.5) для рассматриваемой системы (3.4).
Для полученной комбинации экстремальных значений коэффициентов осуществима проверка решения системы на устойчивость при помощи метода компьютерного анализа устойчивости, представленного в / 89/.
Полный текст программы max Nelin 4 с проверкой на устойчивость решений нелинейных ОДУ представлен в приложении к главе 3, п.3.5. В приложении к главе 3, п.3.6 представлены результаты численного эксперимента для различных интервалов изменения параметров системы рассматриваемой в примере 3.2. Изложенный метод реализуется на персональном компьютере в режиме реального времени для матриц и систем большой размерности, обладает резервом повышения быстродействия за счет параллелизма.
