Содержание к диссертации
Введение
Глава 1. Программная идентификация экстремумов функций при вариации параметров на основе устойчивой распараллеливаемой сортировки 32
1.1. Временная сложность параллельных сортировок слиянием и подсчетом на основе матриц сравнения 33
1.1.1. Алгоритм слияния с взаимно однозначным соответствием входных и выходных индексов 35
1.1.2. Временная сложность сортировки слиянием массива с целой степенью по основанию два элементов 36
1.1.3. Программа сортировки слиянием массива с числом элементов, не являющимся целой степенью по основанию два 37
1.1.4. Алгоритм и временная сложность сортировки подсчетом по матрице сравнений 38
1.2. Идентификация экстремальных значений одномерной последовательности на основе сортировки 40
1.3. Сортировка как основа программной идентификации экстремумов функции одной переменной с варьируемым параметром 42
1.4. Программная идентификация на основе сортировки экстремумов функции
одной переменной при вариации двух и более параметров 47
1.5. Локализация экстремумов и нулей функции на основе сортировки как способ их вычисления с наперед заданной границей абсолютной погрешности 55
1.6. Максимально параллельная схема идентификации нулей и экстремумов функций с оценкой временной сложности 60
1.7. Сравнение схемы идентификации нулей и экстремумов функций при вариации параметров на основе сортировки с методами Maple и MathCAD 62
1.8. Выводы 65
Глава 2. Локализация и вычисление нулей полиномов с переменными комплексными коэффициентами с учетом кратности в приложении к характеристическим полиномам матриц 67
2.1. Идентификация на основе сортировки всех действительных нулей полинома в произвольно заданных границах 68
2.2. Программная локализация области всех действительных нулей полинома с одновременным их вычислением 70
2.3. Схема локализации и вычисления комплексных нулей полинома без учета кратности 77
2.4. Локализация области всех комплексных нулей полинома с одновременным их вычислением без учета кратности 82
2.5. Поиск на основе сортировки нулей полинома с переменными комплексными коэффициентами 89
2.6. Алгоритм идентификации кратности нулей полинома 94
2.7. Локализация и вычисление на основе сортировки нулей характеристического полинома матрицы с учетом кратности 96
2.8. Локализация на основе сортировки нулей полинома с априори заданной границей абсолютной погрешности 99
2.9. Сравнение метода вычисления нулей полиномов на основе сортировки с методами Maple иМаптСАБ 102
2.10. Выводы 105
Глава 3. Компьютерный анализ устойчивости линейной однородной системы дифференциальных уравнений с матрицей постоянных коэффициентов на основе идентификации знака собственных значений 106
3.1. Постановка вопроса 106
3.2. Анализ устойчивости линейной системы ОДУ с матрицей постоянных коэффициентов по критерию Гурвица и критерию Михайлова в аспекте компьютеризации 108
3.3. Компьютерный анализ устойчивости решения линейной системы ОДУ с матрицей постоянных коэффициентов на основе характеристических нулей ... 113
3.4. Практическое применение компьютерного анализа устойчивости решения систем линейных ОДУ с постоянными коэффициентами к реальным физическим системам 115
3.4.1. Линеаризация систем управления 115
3.4.2. Анализ устойчивости систем управления с обратной связью 117
3.4.3. Анализ устойчивости синхронного генератора, работающего на сеть большой мощности 123
3.5. Повышение быстродействия компьютерного анализа устойчивости путем локализации действительной части нулей характеристического полинома 137
3.6. Сравнение компьютерного анализа устойчивости с существующими методами 139
3.7. Выводы 140
Заключение 142
Литература 145
Приложение 152
- Идентификация экстремальных значений одномерной последовательности на основе сортировки
- Сортировка как основа программной идентификации экстремумов функции одной переменной с варьируемым параметром
- Схема локализации и вычисления комплексных нулей полинома без учета кратности
- Компьютерный анализ устойчивости решения линейной системы ОДУ с матрицей постоянных коэффициентов на основе характеристических нулей
Введение к работе
Актуальность проблемы. Для решения задач оптимизации широко используется средства вычислительной техники, накоплен огромный фонд численных методов и программ. Однако существуют трудности компьютеризации, многие из которых связаны с корректным определением одновременно всех локальных и глобальных экстремумов функций в области допустимых значений. Трудности усугубляются в случае сложных топологических рельефов функций. С целью разрешения этих трудностей обычно используют несколько методов численной оптимизации, чтобы увеличить долю удачных решений. Тем не менее, сохраняются сложности, связанные с использованием производных на основе конечно-разностных приближений. Отсюда актуальна разработка компьютерного метода локализации и вычисления экстремумов функций, который осуществлял бы программную идентификацию области каждого экстремума и отличался существенным ограничением роста погрешности при его вычислении. Разработка такого метода целесообразна для проблем автоматической программной идентификации всех экстремумов произвольной алгебраической или трансцендентной функции вначале одной переменной при вариации одного параметра, а затем при вариации двух и более параметров в произвольно фиксированной части области определения. Помимо нахождения экстремумов, актуально нахождение нулей функций при вариации параметров и, как частный случай, нулей полиномов с переменными коэффициентами. В частности, это требуется для оценки устойчивости систем линейных обыкновенных дифференциальных уравнений (ОДУ), которая определяется знаком действительных частей нулей характеристического полинома матрицы коэффициентов. Известны различные системы компьютерной математики, реализующие разнообразные методы вычисления нулей функций. Однако эти методы не предполагают автоматической идентификации области нулей, иногда требуют начального приближения, игнорируя наличие нулей в некоторых сложных случаях, либо не достигают в этих случаях требуемой точности вычислений. Известные схемы поиска нулей могут проявлять неустойчивость в случае трансцендентных функций. В этом контексте актуальна разработка программного метода локализации нулей полиномов и функций, который бы выполнял локализацию как вычисление каждого нуля с произвольной априори заданной границей погрешности. В данном аспекте целесообразно принять во внимание схемы использования сортировки для приближенных вычислений [1-4]. Алгоритмы ее выполнения позволяют минимизировать количество формул и методов традиционной математики. Применение сортировки опирается на упорядочение информации при вычислениях и включает только операции сравнения. Как следствие, можно ожидать снижения роста погрешности при решении задач с ее применением. На этой основе схемы параллельной сортировки можно рассматривать как одно из средств решения проблем устойчивости параллельных вычислений [5].
Сортировка [6] практически присутствует во всех приложениях операционных систем при обработке больших объемов данных. С помощью сортировки решаются задачи «группировки», когда нужно собрать элементы по некоторому признаку. Сортировка используется при поиске с целью его ускорения, с помощью сортировки можно сделать выдачи ЭВМ более удобным для человеческого восприятия. В контексте сортировки рассматриваются многие аспекты программирования.
Рассмотрим основные качества, характеризующие алгоритмы сортировок.
Алгоритмы сортировки оцениваются по скорости выполнения и эффективности использования памяти [7-9].
Время - основной параметр, характеризующий быстродействие алгоритма. Называется также вычислительной сложностью. Для упорядочения важны худшее, среднее и лучшее поведения алгоритма в терминах мощности входного множества А. Если на вход алгоритму подаётся множество А, то обозначим п = \А\. Для
типичного алгоритма хорошее поведение - это 0(п log л) и плохое поведение - это 0(п2). Идеальное поведение для упорядочения - О(п). Также существует понятие сортирующих сетей. Предполагая, что можно одновременно (например, при параллельном вычислении) проводить несколько сравнений, можно отсортировать п чисел за 0(log2 п) операций. При этом число п должно быть заранее известно.
Ряд алгоритмов требует выделения дополнительной памяти под временное хранение данных. Как правило, эти алгоритмы требуют 0(log«) памяти. При оценке не учитывается место, которое занимает исходный массив и независящие от входной последовательности затраты, например, на хранение кода программы (так как всё это потребляет Oil)). Алгоритмы сортировки, не потребляющие дополнительной памяти, относят к сортировкам на месте. Немаловажным качеством сортировок является их устойчивость [7]. Устойчивая сортировка не меняет взаимного расположения равных элементов.
Ещё одно важное свойство алгоритма - это его сфера применения. Здесь два основных типов упорядочения [7-9]:
Внутренняя сортировка оперирует с массивами, целиком помещающимися в оперативной памяти с произвольным доступом к любой ячейке. Данные обычно упорядочиваются на том же месте, без дополнительных затрат.
Внешняя сортировка оперирует с запоминающими устройствами большого объёма, но с доступом не произвольным, а последовательным (упорядочение файлов), т. е. в данный момент мы «видим» только один элемент, а затраты на перемотку по сравнению с памятью неоправданно велики. Это накладывает некоторые дополнительные ограничения на алгоритм и приводит к специальным методам упорядочения, обычно использующим дополнительное дисковое пространство. Кроме того, доступ к данным на носителе производится намного медленнее, чем операции с оперативной памятью. Доступ к носителю осуществляется последовательным образом: в каждый момент времени можно считать или записать только элемент, следующий за текущим.
Ниже рассматриваются некоторые примеры сортировок, а также приводятся оценки временной сложности.
Алгоритмы устойчивой сортировки:
Пузырьковая сортировка [10]. Алгоритм состоит в повторяющихся проходах по сортируемому массиву. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Проходы по массиву повторяются до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает - массив отсортирован. При проходе алгоритма, элемент, стоящий не на своём месте, «всплывает» до нужной позиции как пузырёк в воде, отсюда и название алгоритма. Временная сложность алгоритма: 0(п2).
Сортировка перемешиванием (шейкерная) [6] - разновидность пузырьковой сортировки. Отличается тем, что просмотры элементов выполняются один за другим в противоположных направлениях, при этом большие элементы стремятся к концу массива, а маленькие - к началу. Лучший случай для этой сортировки -отсортированный массив (0(п)), худший - отсортированный в обратном порядке (0(и2)). Сортировка вставками [7]. На каждом шаге алгоритма мы выбираем один из элементов входных данных и вставляем его на нужную позицию в уже отсортированном списке, до тех пор, пока набор входных данных не будет исчерпан. Метод выбора очередного элемента из исходного массива произволен; может использоваться практически любой алгоритм выбора.
Сортировка слиянием [11] - алгоритм сортировки, который упорядочивает списки (или другие структуры данных, доступ к элементам которых можно получать только последовательно) в определённом порядке. Сначала задача разбивается на несколько подзадач меньшего размера. Затем эти задачи решаются с помощью рекурсивного вызова или непосредственно, если их размер достаточно мал. Наконец, их решения комбинируются, и получается решение исходной задачи.
Для решения задачи сортировки эти три этапа выглядят так:
• сортируемый массив разбивается на две половины примерно одинакового размера;
• каждая из получившихся половин сортируется отдельно, например - тем же самым алгоритмом; • два упорядоченных массива половинного размера соединяются в один.
Рекурсивное разбиение задачи на меньшие происходит до тех пор, пока размер массива не достигнет единицы (любой массив длины 1 можно считать упорядоченным).
Нетривиальным этапом является соединение двух упорядоченных массивов в один. Основную идею слияния двух отсортированных массивов можно объяснить на следующем примере. Пусть мы имеем две стопки карт, лежащих рубашками вниз так, что в любой момент мы видим верхнюю карту в каждой из этих стопок. Пусть также, карты в каждой из этих стопок идут сверху вниз в неубывающем порядке. Как сделать из этих стопок одну? На каждом шаге мы берём меньшую из двух верхних карт и кладём её (рубашкой вверх) в результирующую стопку. Когда одна из оставшихся стопок становится пустой, мы добавляем все оставшиеся карты второй стопки к результирующей стопке.
При поверхностном взгляде на алгоритм нельзя сказать, что он дает хороший результат и даже то, что в результате получится отсортированный массив. Однако он дает и то и другое. Эффективность этого алгоритма объясняется тем, что при каждом проходе используется относительно небольшое число элементов или элементы массива уже находятся в относительном порядке, а упорядоченность увеличивается при каждом новом просмотре данных. Время выполнения сортировки Шелла равно 0{п log2 п).
Пирамидальная сортировка [14]. В основе пирамидальной сортировки лежит специальный тип бинарного дерева, называемый пирамидой; значение корня в любом поддереве такого дерева больше, чем значение каждого из его потомков. Непосредственные потомки каждого узла не упорядочены, поэтому иногда левый непосредственный потомок оказывается больше правого, а иногда наоборот. Пирамида представляет собой полное дерево, в котором заполнение нового уровня начинается только после того, как предыдущий уровень заполнен целиком, а все узлы на одном уровне заполняются слева направо. Сортировка начинается с построения пирамиды. При этом максимальный элемент списка оказывается в вершине дерева: ведь потомки вершины обязательно должны быть меньше. Затем корень записывается последним элементом списка, а пирамида с удаленным максимальным элементом переформировывается. В результате в корне оказывается второй по величине элемент, он копируется в список, и процедура повторяется, пока все элементы не окажутся возвращенными в список.
Алгоритм сортировки работает в худшем, в среднем и в лучшем случае за 0(п log и) операций при сортировке п элементов. Количество применяемой служебной памяти не зависит от размера массива (то есть 0(1)).
Фактически быстрая сортировка реализуется посредством рекурсивного алгоритма. Выбор значения разбиения можно сделать двумя способами. Это значение можно выбирать случайным образом или путем усреднения небольшого числа значений, выбранных из массива. Для оптимальной сортировки требуется выбрать значение, которое будет находиться в точности посередине всех элементов. Однако для большинства наборов данных это сделать нелегко. Но, даже в худшем случае, когда выбирается одно из экстремальных значений, быстрая сортировка работает достаточно хорошо. При этом временная сложность алгоритма составляет Э(п log и).
Современные методы последовательных сортировок обсуждаются в работах [15-17], а состояние параллельных сортировок освещено в [18-21], где, в частности, приводятся схемы с временной сложностью C (log2 п).
В рассматриваемом контексте исследуется применение сортировок для построения схем локализации и устойчивого вычисления нулей и экстремумов функции.
I. Численные схемы безусловной оптимизации. Ниже приводится характеристика наиболее часто применяемых методов вычисления экстремумов функций одной или многих переменных.
Формулировка математической задачи оптимизации. В достаточно общем виде математическую задачу оптимизации можно сформулировать следующим образом: минимизировать (максимизировать) целевую функцию с учетом ограничений на управляемые переменные.
Минимизация целевой функции эквивалента максимизации (/( )-» max) и эквивалентна минимизации противоположной величины (-f(x)-»min), поэтому, не умаляя общности можно рассматривать только задачи минимизации. К математическим задачам одномерной минимизации приводят прикладные задачи оптимизации с одной управляемой переменной. Кроме того, необходимость в минимизации функций одной переменной возникает при реализации некоторых методов решения более сложных задач оптимизации.
Для решения задачи минимизации функции f(x) на отрезке [a,b\ на практике, как правило, применяют приближенные методы. Они позволяют найти решения этой задачи с необходимой точностью в результате определения конечного числа значений функции f(x) и ее производных в некоторых точках отрезка [a,b]. Методы, использующие только значения функции и не требующие вычисления ее производных, называются прямыми методами минимизации.
Большим достоинством прямых методов является то, что от целевой функции не требуется дифференцируемости и, более того, она может быть не задана в аналитическом виде. Единственное, на чем основаны алгоритмы прямых методов минимизации, это возможность определения значений /(х) в заданных точках.
Рассмотрим наиболее распространенные на практике прямые методы поиска точки минимума. Самым слабым требованием на функцию f(x), позволяющим использовать эти методы, является ее унимодальность (наличие у функции одного экстремума). Поэтому далее будем считать функцию f(x) унимодальной на отрезке [a,b].
Метод поразрядного поиска [23]. Можно усовершенствовать метод перебора с целью уменьшения количества значений f(x), которые необходимо находить в процессе минимизации. Во-первых, если оказывается, что f(xl) f(xl+l), то отпадает необходимость вычислять f(x) в точках х1+2, х1+3 и т.д. Во-вторых, разумно было бы сначала определить отрезок, содержащий оптимальную точку, грубо, т.е. найти точку хт с небольшой точностью, а затем искать ее на этом отрезке с меньшим шагом дискретизации, повышая точность. Эти возможности улучшения и реализованы в методе поразрядного поиска. В этом методе перебор точек отрезка происходит сначала с шагом sh = xl+l - х, eps до тех пор, пока не
выполнится условие f(x,) Дх,+1) или пока очередная из точек не совпадет с концом отрезка. После этого шаг уменьшается (обычно в 4 раза), и перебор точек с новым шагом производится в противоположном направлении до тех пор, пока значения f(x) снова не перестанут уменьшаться или очередная точка не совпадет с другим концом отрезка и т.д. Описанный процесс завершается, когда перебор в данном направлении закончен, а использованный при этом шаг дискретизации не превосходит eps.
Метод деления пополам (дихотомический поиск) [24]. Рассмотрим функцию /, которую требуется минимизировать на интервале [о Д]. Предположим, что / строго квазивыпукла. Очевидно, что наименьшее число вычислений значений функции, которые необходимы для сокращения интервала неопределенности, равно двум. Одной из стратегий является выбор этих двух точек симметрично на расстоянии eps 0 от середины интервала. Здесь число eps настолько мало, чтобы длина нового интервала неопределенности eps + (b{-ax)l2 являлась достаточно близкой к теоретическому значению фх-ах)12, и в то же время такое, чтобы значение функции в этих двух точках были различимы.
Метод золотого сечения [25, 26]. Сравнение различных процедур линейного поиска естественно производить в соответствии со следующим коэффициентом сжатия (длина интервала неопределенности после к выполненных наблюдений)/(длина интервала неопределенности до выполнения наблюдений).
Очевидно, что более эффективные схемы соответствуют меньшим значениям коэффициента сжатия. В дихотомическом поиске значение коэффициента приблизительно равно 0.5 /2. Метод золотого сечения является более эффективным, для него значение коэффициента сжатия равно 0.618 4.
Методы безусловной минимизации функций многих переменных. Задача безусловной оптимизации состоит в нахождении минимума или максимума функции в отсутствие каких-либо ограничений. Несмотря на то, что большинство практических задач оптимизации содержит ограничения, изучение методов безусловной оптимизации важно с нескольких точек зрения. Многие алгоритмы решения задачи с ограничениями предполагают сведение ее к последовательности задач безусловной оптимизации. Другой класс методов основан на поиске подходящего направления и последующей минимизации вдоль этого направления. Обоснование методов безусловной оптимизации может быть естественным образом распространено на обоснование процедур решения задач с ограничениями.
1. Многомерный поиск без использования производных. Рассмотрим методы решения минимизации функции нескольких переменных /, которые опираются только на вычисление значений функщга /(х), не используют вычисление производных, т.е. прямые методы минимизации. Важно отметить, что для применения этих методов не требуется не только дифференцируемости целевой функции, но даже аналитического задания. Нужно лишь иметь возможность вычислять или измерять значения / в произвольных точках. Такие ситуации часто встречаются в практически важных задачах оптимизации. В основном все описанные методы заключаются в следующем. При заданном векторе х определяется допустимое направление d. Затем, отправляясь из точки х, функция / минимизируется вдоль направления d одним из методов одномерной минимизации. Задача линейного поиска заключается в минимизации f(x+tym d) при условии, чго lym принадлежит L, где L обычно задается в форме L = {lym :lym 0} или L = {lym :а lym b). Будем предполагать, что точка минимума lym существует. Однако в реальных задачах это предположение может не выполняться. Оптимальное значение целевой функции в задаче линейного поиска может быть не ограниченным или оптимальное значение функции конечно, но не достигается ни при каком lym .
Поиск точки минимума функции f(x) с помощью правильных симплексов производится следующим образом. На каждой итерации сравниваются значения функции в вершинах симплекса. Затем проводится описанная выше процедура отражения для той вершины, в которой f(x) принимает наибольшее значение. Если в отраженной вершине получается меньшее значение функции, то переходят к новому симплексу. Если же попытка отражения не приводит к уменьшению функции, то сокращают длину ребра симплекса, например, вдвое и строят новый симплекс с этим ребром. В качестве базовой выбирают ту вершину х0 старого симплекса, в которой функция примет минимальное значение. Поиск точки минимума Дх) заканчивают, когда-либо ребро симплекса, либо разность между значениями функции в вершинах симплекса становятся достаточно малыми.
Определение. Пусть Н - симметрическая матрица порядка пхп. Векторы dx,d2,...,dk называются Н-сопряэюенными, или просто сопряженнылш, если они
линейно независимы и dt{t)Hdj = 0 при / Ф j, где dt(0 - вектор строка.
Минимум квадратичной функции может быть найден не более чем за п шагов при условии, что поиск ведется вдоль сопряженных относительно матрицы Гессе направлений. Поскольку произвольная функция может быть достаточно хорошо представлена в окрестности оптимальной точки ее квадратичной аппроксимацией, понятие сопряженности становится очень удобным для оптимизации как квадратичных, так и неквадратичных функций.
Метод Дэвидона - Флетчера — Пауэлла [25]. Первоначально метод был предложен Дэвидоном и затем развит Флетчером и Пауэллом. Метод Дэвидона-Флетчера-Пауэлла называют также и методом переменной метрики. Он попадает в общий класс квазиньютоновскігх процедур, в которых направления поиска задаются в виде - D} grad(f(y)). Направление градиента является, таким образом, отклоненным в результате умножения на --D,, где D} - положительно определенная симметрическая матрица порядка пхп, аппроксимирующая обратную матрицу Гессе. На следующем шаге матрица DJ+l представляется в виде суммы Dj и двух симметрических матриц ранга один каждая. В связи с этим схема иногда называется схемой коррекции ранга два.
II. Исследование ландшафтов целевых функций на основе эволюционной оптимизации. В рамках подхода к решению задач оптимизации исследуется возможность применения эволюционных и генетических алгоритмов [31, 32]. При этом строятся новые целевые функции, обеспечивающие получение оптимальных решений для исходных функций [33]. Использование одних и тех же целевых функций в рамках схемы эволюционных алгоритмов часто приводит к достижению локального, но не глобального экстремума [34]. По этой причине возникает идея замены одной целевой функции на другую при условии, что это приводит к эквивалентному результату. Актуальна задача выбора эффективной целевой функции на ранней стадии разработки нового алгоритма. Для выбора такой функции конструируются подходы на основе анализа ландшафтов целевой функции [35, 36]. Разработанные в данном аспекте методы ориентированы на получение интегральных параметров ландшафта целевой функции, которые определённым образом характеризуют её сложность для эволюционных алгоритмов. Чтобы оптимизировать функцию модифицируется алгоритм расчета интегральных параметров на основе барьерных деревьев. На этой основе выделяются компоненты, по которым можно судить об эффективности соответствующих им целевых функций для эволюционных алгоритмов. Метод барьерных деревьев [36] позволяет оценить глубину каждого локального минимума и степень его влияния на процесс эволюционного проектирования. Основная идея метода заключается в том, что сложность поверхности отражает высота h, на которую необходимо подняться, чтобы попасть из одного локального минимума в другой.
Подход включает следующие затруднения. Сравнивать целые наборы величин затруднительно, поскольку количество локальных оптимумов обычно различно для различных целевых функций. Кроме того, для автоматического сравнения желательно иметь один интегральный параметр. Поэтому необходимо оценить вероятность не возникновения преждевременной сходимости. Для этого достаточно, чтобы генетический алгоритм мог выйти из текущего локального оптимума и найти другой с лучшим значением. В случае успеха он вероятнее найдёт локальный оптимум, который ближе всего находится к текущему локальному оптимуму. Производится [33] переход от набора параметров локального минимума к единственному параметру оценки области локального минимума. f(xt,Xj) - минимальный барьер, который необходимо преодолеть.
чтобы попасть из локального оптимума / в локальный оптимум /. Барьер - это наивысшая точка некоторого пути. Чтобы получить только один интегральный параметр для всего ландшафта, достаточно выделить из всех локальных оптимумов тот, выход из которого наиболее сложен. Значение такого оптимума интерпретируется как глубина В ландшафта. Для сравнения ландшафтов берётся отношение глубины к общей высоте ландшафта, которое называется сложностью у/. Для сравнения ландшафтов используются два параметра - глубина В и сложность у/.
Основная идея определения всех локальных оптимумов состоит в предварительной дискретизации пространства неравномерной сеткой. После этого для определения является ли некоторая точка локальным или глобальным оптимумом достаточно просмотреть соседние для неё точки. В результате получается линейный алгоритм сложности 0(3 п N), где N -количество точек исходной выборки, an- размерность пространства. Положительные результаты достигаются в случае поверхности близкой к классу унимодальных и при достаточных размерах области локализации экстремума [33]. Количество найденных решений зависит от модальности функции.
III. Методы вычисления нулей функций. Известные классические и современные методы вычисления нулей функций и нулей полиномов, как частного случая функций [37-45]: метод Лобачевского, итерационные методы к числу которых относят метод Чебышева, метод Эйткена, метод Ньютона, метод секущих, метод Мюллера, помимо того, применяются метод Брента, метод Лина, метод Фридмана, метод Лагерра, метод сопроволсдающей матрицы, интервальные лтподы и др.
Практически во всех представленных выше методах, отыскание нулей полиномов и функций осуществляется в два этапа [37]: • отделение (локализация) нулей, т.е. нахождение достаточно малых областей, в каждой из которых заключен один и только один нуль полинома. По существу это означает некоторое приближение каждого из нулей;
• полученное приближенное значение каждого нуля уточняется до заданной границы погрешности путем последовательных приближений.
Задача отделения нулей полинома (3) заключается в том, чтобы каждый из них заключи гь в интервал, не содержащий других нулей полинома. Для отделения действительных нулей полинома (3) применяют способ Фурье, основанный на теореме Бюдана. Способ отделения комплексных нулей полинома (3), подробно описанный в [37], использует понятие индекса полинома относительно некоторой заданной прямой в комплексной плоскости и позволяет отделить комплексные нули, расположенные в некоторой полосе. Программная реализация схемы отделения комплексных нулей затруднительна.
Известны различные системы компьютерной математики [47-50], реализующие разнообразные методы вычисления нулей PI экстремумов функций. В частности, в MathCAD для определения нулей функций и полиномов реализованы методы секущих, Брента, Лагерра и сопровождающей матрицы [41], а для определения экстремумов функций реализованы градиентные методы, включая метод сопряженных градиентов, метод Левенберга [51]. В пакете аналитических вычислений Maple нули полиномов вычисляются как собственные числа матрицы Фробениуса, а исследование на экстремум функции заключается в нахождении точек, в которых производная исследуемой функции равна нулю [48].
Схемы, реализованные в этих пакетах, не предполагают автоматической идентификации области нулей, иногда требуют начального приближения, соответственно они игнорируют наличие нулей в некоторых сложных случаях, либо не достигают в этих случаях требуемой точности вычислений. Рассматриваемые схемы могут проявлять неустойчивость при поиске нулей трансцендентных функций.
Устойчивая работа математических пакетов при поиске экстремумов функций зависит от сложности исследуемой функции. Иногда пакеты не могут указать точку экстремума, лишь представляя исследуемую функцию графически. В этом случае не идентифицированы числовые значения, а графически они отображены с малой точностью разрешающей способности графического редактора. Сложности использования пакетов усугубляются для функций многих переменных.
Отсюда актуальна разработка программного метода локализации нулей и экстремумов функций, который бы выполнял автоматическую идентификацию области каждого нуля или экстремума и отличался бы существенным ограничением роста погрешности при его вычислении.
В основу метода целесообразно положить алгоритмы сортировки, поскольку, они включают лишь операции сравнения и сами по себе не накапливаю: погрешность.
Сортировки традиционно применяются для поиска и моделирования методов теоретической информатики [19, 52]. Положительный опыт применения сортировки именно для рассматриваемых схем вычислений описан в [3, 4, 53-59]. При этом параллелизм сортировки [60, 61] влечет возможность построения параллельных схем определения нулей и экстремумов в целом.
К одной из целей диссертационной работы относится исследование применимости сортировки для идентификации всех экстремумов функций при вариации параметров. Конкретно, затрагивается проблема автоматической программной идентификации всех экстремумов произвольной алгебраической или трансцендентной функции вначале одной переменной при вариации одного параметра, а затем при вариации двух и более параметров, в произвольно фиксированной части области определения. Другая цель состоит в поиске нулей полиномов с переменными комплексными коэффициентами с учетом кратности. Требования устойчивости и быстродействия идентификации экстремумов функций и нулей полиномов обеспечиваются за счет устойчивости и параллелизма схем на основе сортировки.
Нулевое решение линейной системы (4) является асимптотически устойчивым в том и только в том случае, когда все характеристические числа матрицы А имеют отрицательные вещественные части.
Следовательно, наиболее естественным методом определения устойчивости системы является решение ее характеристического уравнения и определение знаков действительных частей полученных корней. Однако такой метод не может считаться приемлемым для большинства практических задач, так как возникают вычислительные трудности при решении алгебраических уравнений высоких степеней. Поэтому на практике применяются другие методы, позволяющие, не прибегая к определению корней характеристического уравнения, получить все необходимые данные по устойчивости. Такие методы называются критериями устойчивости [64, 65]. Следует отметить, что все критерии устойчивости в той или иной форме используют тот факт, что у устойчивой системы действительные части всех корней характеристического уравнения отрицательны, однако знак действительных частей корней устанавливается не непосредственно, а косвенным путем.
Имеется ряд критериев устойчивости, которые делятся на две разновидности: алгебраические {критерий Гурвгща) и частотные (критерии Михайлова и Найквиста). Алгебраические критерии являются аналитическими, а частотные - графоаналитическими. Из перечисленных критериев устойчивости рассмотрим лишь критерий Найквиста. Он основан на построении годографа передаточной функции разомкнутой системы. Критерий устойчивости Найквиста формулируется следующим образом: замкнутая система устойчива, если годограф передаточной функции разомкнутой системы не охватывает на комплексной плоскости точку с координатами (-1, _/ ). Если годограф проходит через точку (-1,./0), т0 система находится на границе устойчивости. На рис.9 показаны примеры устойчивой и неустойчивой систем управления.
На основе изложенного выше, можно утверждать, что все представленные критерии не вполне пригодны для компьютеризации и информацию об устойчивости подают в косвенном виде, характерном для качественной теории дифференциальных уравнений. С целью исследования возможности разрешения отмеченных трудностей в диссертационной работе ставится задача построения метода компьютерного анализа устойчивости, который в общем случае давал бы однозначное определение характера устойчивости, неустойчивости либо асимптотической устойчивости решения систем линейных дифференциальных уравнений с постоянными коэффициентами.
На основании изложенного целесообразно исследовать возможность построения единого метода программной идентификации нулей и экстремумов функций, направленного на анализ устойчивости решения систем линейных дифференциальных уравнений с постоянными коэффициентами. При этом данный метод должен основываться на алгоритмах распараллеливаемых сортировок. Более точно, формулируется следующая цель. Цель диссертационной работы заключается в разработке и исследовании единого метода программной идентификации нулей и экстремумов функций при вариации параметров с приложением к анализу устойчивости систем линейных ОДУ с матрицей постоянных коэффициентов. Конструкция схем идентификации должна быть инвариантной относительно вида функции, ее топологических особенностей, а также числа переменных и числа параметров. При этом должна достигаться устойчивость работы схем и требуемая точность вычислений, схемы должны эффективно распараллеливаться. Аналогично, ставится задача локализации и вычисления нулей полиномов с переменными комплексными коэффициентами с учетом кратности в приложении к характеристическим полиномам матриц. Па основе идентификации нулей характеристического полинома требуется дать решение проблемы компьютерного анализа устойчивости систем линейных ОДУ.
Для достижения поставленной цели в диссертационной работе решаются следующие задачи:
1. Разработать компьютерные схемы локализации и вычисления экстремумов функций одной и более переменных при вариации параметров в произвольной части области определения функции. Схемы должны отличаться построением на основе сортировки, автоматизмом программной идентификации одновременно всех экстремумов функций с априори заданной точностью.
2. Обеспечить обобщенность и высокую точность вычислений, а также инвариантность разрабатываемых схем идентификации экстремумов относительно вида функции при вариации параметров (как алгебраической, так и трансцендентной) и ее топологического рельефа в случае многомерной безусловной численной оптимизации.
З.Для случая функции одной комплексной переменной обеспечить программную локализацию одновременно всех минимумов модуля с точностью до наперед заданного значения радиуса окрестности и распространить метод на локализацию одновременно всех нулей полинома как минимумов его модуля для случая переменных комплексных коэффициентов. Синтезировать параллельные варианты данных схем и выполнить оценки их временной сложности.
4. Алгоритм локализации нулей полинома и его параллельное видоизменение применить для случая поиска собственных значений матрицы произвольного порядка, включая матрицу постоянных коэффициентов системы линейных ОДУ. На этой основе обеспечить компьютеризацию анализа устойчивости по Ляпунову линейной системы ОДУ как в случае асимптотической, так и неасимптотической устойчивости.
5. Разработать приложение компьютерного анализа устойчивости к системам управления с обратной связью и к анализу устойчивости синхронного генератора, работающего на сеть большой мощности. Выполнить программные и численные эксперименты по проверке достоверности искомого метода и его практической применимости.
6. Выполнить сравнение искомых результатов работы с известными методами численной безусловной оптимизации, вычисления нулей полиномов и анализа устойчивости систем линейных ОДУ.
Методы исследования опираются на численные методы оптимизации, на качественную теорию устойчивости, на теоретические основы информатики и теорию сложности параллельных вычислений.
Достоверность результатов вытекает из их математического обоснования, подтверждается оценками временной сложности, а также результатами программного моделирования и численного эксперимента.
Научная новизна результатов диссертационной работы заключается в следующем:
1. Разработаны схемы программной идентификации экстремумов функции при вариации параметров инвариантные относительно ее вида и ее топологического рельефа, которые применимы в случае многомерной безусловной численной оптимизации. Предложенные схемы отличаются от известных по построению, учетом вариации параметров, параллелизмом и тем, что реализуются в ограничениях общего характера на вид функции, идентифицируя одновременно все экстремумы в допустимой области с априори заданной границей абсолютной погрешности.
2. Предложен программный метод локализации на основе сортировки и приближенного вычисления всех нулей полиномов с переменными комплексными коэффициентами с учетом кратности. Метод отличается от известных по построению, параллелизмом и тем, что локализация каждого нуля алгоритмически и фактически означает его вычисление с априори заданной границей абсолютной погрешности.
3. Предложено видоизменение метода локализации нулей полинома на случай поиска одновременно всех собственных значений матрицы произвольного порядка, включая матрицу постоянных коэффициентов системы линейных ОДУ. Видоизменение отличается построением на основе сортировки и тем, что позволяет устойчиво определять кратность, а также знак действительной части каждого из собственных значений.
4. Синтезированы распараллеливаемые алгоритмы компьютерного анализа устойчивости линейной системы ОДУ с матрицей постоянных коэффициентов по нулям характеристического полинома, инвариантные относительно вида правой части системы. Отличие алгоритмов от известных заключается в способе построения и в том, что они позволяют программно определять характер устойчивости без преобразования правой части системы.
5. Доказаны теоремы об эквивалентности схем локализации на основе сортировки нулей и экстремумов функций одной и более переменных с их вычислением с наперед заданной границей абсолютной погрешности. Параллелизм локализации, оценки временной сложности максимально параллельных вариантов схем, включая приложения к анализу устойчивости систем линейных ОДУ, отличают схемы от известных.
6. Показана применимость компьютерных алгоритмов анализа устойчивости к системам управления с обратной связью, включая вариацию параметров и наличие трансцендентности. На этой основе выполнен компьютерный анализ устойчивости синхронного генератора, работающего на сеть большой мощности. Представлены программные и численные эксперименты, подтверждающие достоверность анализа устойчивости на основе предложенных алгоритмов.
Основные положения, выносимые на защиту:
1. Разработаны схемы программной идентификации экстремумов функции при вариации параметров инвариантные относительно ее вида и ее топологического рельефа, которые применимы в случае многомерной безусловной численной оптимизации. Схемы обладают параллелизмом и реализуются с учетом вариации параметров, идентифицируя при этом одновременно все экстремумы в допустимой области с априори заданной границей абсолютной погрешности.
2. Предложен программный метод локализации на основе сортировки и приближенного вычисления всех нулей полиномов с переменными комплексными коэффициентами с учетом кратности. Метод обладает параллелизмом и тем, что локализация каждого нуля алгоритмически и фактически означает его вычисление с априори заданной границей абсолютной погрешности.
3. Предложено видоизменение метода локализации нулей полинома на случай поиска одновременно всех собственных значений матрицы произвольного порядка, включая матрицу постоянных коэффициентов системы линейных ОДУ. Видоизменение позволяет устойчиво определять кратность, а таюке знак действительной части каждого из собственных значений.
4. Синтезированы распараллеливаемые алгоритмы компьютерного анализа устойчивости линейной системы ОДУ с матрицей постоянных коэффициентов по нулям характеристического полинома, инвариантные относительно вида правой части системы. Алгоритмы позволяют программно определять характер устойчивости без преобразования правой части системы.
5. Доказаны теоремы об эквивалентности схем локализации на основе сортировки нулей и экстремумов функций одной и более переменных с их вычислением с наперед заданной границей абсолютной погрешности. Показан параллелизм локализации и даны оценки временной сложности максимально параллельных вариантов схем, включая приложения к анализу устойчивости систем линейных ОДУ.
6. Показана применимость компьютерных алгоритмов анализа устойчивости к системам управления с обратной связью, включая вариацию параметров и наличие трансцендентности, выполнен компьютерный анализ устойчивости синхронного генератора, работающего на сеть большой мощности.
Практическая ценность диссертационного исследования заключается в прикладном характере предложенных методов и алгоритмов. Все предложенные методы ориентированы на компьютерную реализацию и актуальны для решения научно-технических задач в различных областях математического моделирования, связанных с практическими задачами теории управления. В частности, методы вычисления нулей полиномов применимы для механических моделей молекулярного синтеза; методы определения собственных значений матриц применимы для компьютерного анализа устойчивости систем управления с обратной связью, а также для компьютерного анализа устойчивости работы синхронных генераторов большой мощности.
Внедрение и использование результатов работы. Полученные в работе результаты использованы
1. В ОАО НКБ ВС для повышения точности и быстродействия определения положения объекта в системе цифровой обработки видеосигналов; для разработки схем компьютерного анализа и оценки параметров устойчивости систем автоматического управления; для оценки устойчивости управления пространственной ориентацией движущихся объектов. 2. В госбюджетной НИР «Математические методы устойчивой параллельной обработки, поиска и распознавания», код ГРНТИ 28.23.15, регистрационный номер 01.2.00106436.
3. В учебном процессе кафедры информационных систем ГОУВПО «ТГПИ» в рамках курсов «Информатика», «Информационные технологии в математике», «Численные методы», «Элементы абстрактной и компьютерной алгебры».
Апробация работы. Основные результаты работы были представлены на:
- Международной научно-технической конференции «ММА-2006» «Математические модели и алгоритмы для имитации физических процессов» (Таганрог, ТГПИ, 2006 г.);
- XII Международной научной конференции «Математические модели физических процессов» (Таганрог, ТГПИ, 2007 г.);
- VI Международной научно-технической конференции «Информационно-вычислительные технологии и их приложения» (Пенза, МНИЦ ПГСХА, 2007 г.);
- Всероссийской научно-технической конференции с международным участием «Компьютерные и информационные технологии в науке, инженерии и управлении» (Таганрог, ЮФУ, 2008 г.);
- IX Всероссийском симпозиуме по прикладной и промышленной математике (Северо-Кавказкий ГТУ, ИПИ РАН, РИНХ, Кисловодск, 2008 г.);
- Международной научно-технической конференции «Модели и алгоритмы для имитации физико-химических процессов» МАФП 2008 (Таганрог, ТГПИ, 2008 г.);
- IV Международной научно-практической конференции «Методология и практика образовательных технологий в условиях модернизации образования» (Таганрог, ТГПИ, 2008 г.).
Публикации. По материалам работы опубликовано 13 печатных работ общим объемом около 12 печатных листов, в том числе 3 статьи в журналах из перечня рекомендуемых ВАК РФ.
Структура и объём работы. Диссертационная работа состоит из введения, трех глав основного раздела, заключения, списка литературы и приложений к трем главам. Основное содержание работы изложено на 151 страницах, включая список литературы из 89 наименований.
Идентификация экстремальных значений одномерной последовательности на основе сортировки
Вначале рассмотрим схему локализации и вычисления экстремальных значений функции двух переменных, заимствованную из [71], затем внесем в эту схему изменения, связанные с варьируемым параметром. Пусть дана действительная функция двух действительных переменных
Первоначально задаются текущие промежутки [х{0),х1ю] и [у(0), УЛ,)]. Данные промежутки задают, вообще говоря, прямоугольник с текущими границами внутри априори заданной области поиска экстремумов, которая в программе идентифицируется как прямоугольник [Х00,Хпп], [Y00,Ymm]. Внутри текущих промежутков строится равномерная прямоугольная сетка с постоянным шагом по направлениям осей ОХ и OY:
Значения функции берутся во всех узлах сетки и среди них ищутся все возможные максимумы функции (1.20). Для нахождения максимумов рассматриваемой функции выполняется проход в направлении оси OY вдоль столбцов прямоугольной сетки, во время, которого находится максимальное по строкам значение ф] = тах/(х, у,) при фиксировании номера столбца, и этот максимум заносится на вход любой адресной сортировки как элемент ф] сортируемого одномерного массива. К выходу сортировки слиянием sort подсоединяется условный оператор локализации максимума. Работая после сортировки, оператор локализации максимума для текущего узла, определяемого индексом, записанным в еЗ[к], находит каждый узел x0 + e3[k] h, в проекции epsO-окрестности которого на ось ОХ нет узлов, доставляющих значения элементов входной последовательности, предшествующие фЗ[&]] в отсортированном массиве (еЗ[к],еЗЗ[Щ- элементы массивов индексов, формируемых на выходе сортировки, которые определяются аналогично е[к]). Значение локализованной абсциссы точки максимума хк := xQ + еЗ[к] h дает привязку к локализуемой точке двумерного максимума. Оно фиксируется и аналогичным образом локализуется ордината ук := уО + еЗЗ[к\] h, в которой достигается приближение к максимальному значению f(x, у), из (1.20). Остается выполнить спуск к наибольшему значению в окрестности, локализованной точки. Он осуществляется с помощью выбора наибольшего значения в сужаемой окрестности с фиксированным числом элементов сетки, причем по обеим переменным, пока не будет достигнута требуемая точность. Выбор наибольшего значения функции осуществляется с помощью программных процедур конструируемых для двух переменных соответственно max Л: , max у. Такой спуск повторяется дважды с целью повышения точности приближения, он представлен следующим фрагментом:
При исследовании всей области поиска экстремумов функции (1.20) производится смещение промежутков [х(0),х(Л] и О(0),.у(ЛО] до тех пор, пока не будет пройдена вся априори заданная область. Во избежание ложных экстремумов отсекаются все концы на текущих промежутках, дополнительная проверка границ на экстремум осуществляется при помощи сортировки sortOO и локализации экстремумов для элементов массива, образуемых значениями функции (1.20), слева от правой границы и справа от левой границы для каждого из промежутков.
В целом программная реализация предложенной схемы идентификации всех экстремальных значений любой дискретно заданной функции двух действительных переменных представлена ниже в примере, где на вход алгоритма подается функция двух переменных, роль одной из которых играет независимая переменная, роль другой - играет один варьируемый параметр.
Блок-схема локализации максимумов функции одной переменной с варьируемым параметром представлена на рисунке 1.2.
Сортировка как основа программной идентификации экстремумов функции одной переменной с варьируемым параметром
Алгоритм вычисления минимумов функции одной переменной с двумя варьируемыми параметрами и функции одной переменной с вариацией трех параметров аналогичны с точностью определения переменной и параметров алгоритмам поиска минимумов функции трех переменных и четырех переменных соответственно, представленных в [71], но отличаются различным значением шага дискретизации, выбор которого изложен и обоснован выше. Данная схема следующим образом обобщается на случай идентификации экстремумов функции произвольного числа переменных [71] у/= f{xx,x2,...,xn). Алгоритм 1.4 (идентификации экстремумов функции п переменных). 1. Первоначально фиксируется одна переменная х, и для каждого текущего ее значения на равномерной сетке находится минимум (аналогично, максимум) функции у/, который берется по п -1 другим переменным. 2.
Все такие минимумы (максимумы) поступают на вход сортировки в виде одномерной последовательности, после чего оператор локализации идентифицирует среди элементов данной последовательности все локальные минимумы (максимумы). 3. Каждая локализованная координата фиксируется (по аналогии со случаем функций двух, трех и четырех переменных) и дает привязку по этой координате к искомому локальному минимуму (максимуму) л- мерной функции. 4. После этого, при каждой фиксированной локализованной координате, для оставшихся п-\ других координат возобновляется процесс, полностью идентичный только что описанному для п первоначальных координат. Конкретно, минимумы по и-2 переменным при фиксированной локализованной координате, взятые при каждом текущем значении другой переменной на равномерной сетке, образуют новую одномерную последовательность. 5. Эта последовательность, в свою очередь, поступает на вход сортировки, и с помощью оператора локализации идентифицируются все значения второй координаты искомых локальных минимумов. 6. Далее, при фиксировании локализованных координат процесс возобновляется для оставшихся п-Ъ координат и так далее, пока в заданном порядке не будут перебраны все переменные функции ц/. Реализует этот алгоритм ниже приведенная программа нахождения минимумов функции пяти переменных sin(x y f w z) в области .те [о, 2 pi], Данная схема устойчиво программно идентифицирует (локализует) экстремумы с точностью до дискретизации входных значений функции у/ при вариации параметров. . В основе подхода к локализации экстремумов и нулей функции лежит оператор локализации минимальных (1.18) (максимальных (1.19)) элементов последовательности, так как для локализации нулей функции достаточно на вход сортировки подать абсолютные величины и искать минимумы (максимумы со знаком минус) описанным выше способом.
Все локализованные минимумы модуля исследуемой функции будут включать нули этой функции. Если других минимумов нет, то будут локализованы и вычислены именно нули в произвольно заданной и зафиксированной области на плоскости. Данный оператор локализации всегда работает только с предварительной выполненной устойчивой сортировкой с взаимно однозначным соответствием входных и выходных индексов. При этом вся информация об экстремальных элементах последовательности заключена в формируемой сортировкой этой последовательности подстановке из входных и выходных индексов ее элементов. В процедуре сортировки индексы сортируемых элементов входного массива С = (с[1],с[2],...,с[«]) запоминаются в виде элементов е [к], их массив формируется на выходе процедуры. При этом индекс к -1, 2,..., ппО задает нумерацию отсортированных по неубыванию элементов. Оператор локализации обрабатывает непосредственно элементы е [к]. Истинность условия внутри оператора локализации минимума (аналогично внутри оператора локализации максимума) означает, что узел с номером е [к-l] находится в epsO -окрестности узла с номером е [к] среди узлов равномерной сетки с шагом И. Но е[к-1] взаимно однозначно соответствует элементу с [е [-/]], предшествующему с [е [к]] в отсортированном массиве. Отсюда с [е [к-l]] с [е [к]]. Поэтому с [е [к]] не является минимальным элеменюм входной последовательности в данной окрестности. Напротив, ложность рассматриваемого условия означает, что узел с номером е[к-1] лежит вне epsQ -окрестности узла с номером е [к]. Если ложность сохраняется для всех / = 1,2,..., -1, то ни один узел, которому бы соответствовало с[е[к-1]] с [е [к]] , не попадает в рассматриваемую окрестность.
Поэтому на узлах данной сетки в epsO -окрестности узла с номером е [к] элемент с [е [к]] оказывается минимальным. Теорема 1.1. Рассматриваемый способ локализации с помощью сортировки минимальных (максимальных) значений или нулей функции одной действительной переменной y = f(x), определенной и непрерывной на промежутке [хО, xl], означает вычисление этих экстремумов или нулей с наперед заданной границей абсолютной погрешности epsO. При этом шаг дискретизации h функции на равномерной сетке, покрывающей данный промежуток, априори удовлетворяет ограничению h hQ epsQ, где h0 таково, что все экстремумы функции на данном промежутке сохраняются при дискретизации в узлах равномерной сетки с произвольным шагом h h0. Доказательство достаточно провести для локализации минимальных элементов. Рассмотрим значения функции в узлах равномерной сетки, приняв их в качестве элементов сортируемой последовательности с[1],с[2],...,с[«], где f(xk) = с[к], к = \,2,...,п. Оператор локализации минимальных элементов
Схема локализации и вычисления комплексных нулей полинома без учета кратности
Пусть дан полином п-й степени P„{z) от комплексной переменной z. Выполняется его умножение на комплексно-сопряженное значение P„(z), чтобы свести задачу к поиску нулей функции двух действительных переменных Ниже приводится видоизменение изложенной в [3,4] схемы локализации и вычисления комплексных нулей полинома. Сохраняя принцип построения исходной схемы, модифицированная обладает существенно большей точностью и осуществляет поиск ігулей в расширенной области.
В плоских декартовых координатах вводится равномерная прямоугольная сетка, включающая область, которой принадлежат все нули. Сетка строится с постоянным шагом h по направлениям осей ОХ и OY: Значения f(x,y) берутся во всех узлах сетки и среди них ищутся все возможные минимумы. На основе принципа максимума модуля [74] все минимумы f{x,у) достигаются в каждом из нулей полинома Pn(z) и других минимумов эта функция не имеет. По непрерывности f(x,y), в достаточно малой окрестности каждого из нулей, при достаточной малости шага сетки, значения f(x,y) в узлах из этой окрестности будут меньшими, чем значения f(x,y) вне этой окрестности. Эти значения можно принять за приближения к искомым нулям. Излагаемая схема сужает шаг сетки в окрестности локализованного приближения, при этом использует исключение операторами программы неточных приближений и ненулевых минимумов, возникающих на границах смещаемых прямоугольников. Приближения нулей локализуются на основе сортировки значений fix, у) на сетке (2.7) с использованием оператора локализации минимума, затем выполняется спуск к локализованным значениям. Специфика случая функции двух переменных заключается в следующем.
Во избежание квадратичного по сравнению с исходным случаем роста памяти, локализация и вычисление нулей fix,у) выполняются с предварительной минимизацией, которая сводит пространственный случай к плоскому. С этой целью посредством внешнего цикла выполняется проход в направлении оси ОХ по столбцам сетки. Внутренний цикл определяет наименьшее в текущем столбце значение f[xl ,у ). Для шага внешнего цикла с номером і это значение, заносится как і-й элемент одномерного массива на вход сортировки, /=1,2,...,N. Затем с помощью сортировки и оператора локализации минимума определяется абсцисса элемента, локально минимального среди с ( из (2.8). Значение этой абсциссы соответствует к -му элементу отсортированного массива где min - минимальный элемент входного массива, найденный с помощью оператора локализации. Значение хК дает привязку к точке минимума на плоскости, оно фиксируется и по аналогичной схеме повторно, с помощью сортировки и оператора локализации, локализуется приближение к ординате у , К искомой точки. Найденное в результате значение принимается за приближение к искомому нулю полинома. Выполняется пространственный аналог плоского спуска к наименьшему значению в окрестности точки Vxt JVJ из (2-П). Схема циклически воспроизводится по всем локализованным точкам минимума. Представленная ниже программа дана для полинома вида где z=x+Iy, z =x +Iy , I из (13).
В этом случае квадрат модуля (2.5) рассматриваемого полинома представим в виде произведения [3]. реализуемого функцией func с параметрами, соответственными х , у из (2.12). С целью численного эксперимента на входе программы можно задавать произвольные х , у и анализировать соответствие этим значениям результатов на выходе. При этом необходимо, чтобы произвольно фиксируемый параметр epsO для оператора локализации был меньше половины расстояния между ближайшими друг к Другу нулями полинома, а также выполнялись соотношения (2.1). Из сведения пространственного случая к плоскому вытекает, в частности, требование - при совпадении действительных частей двух нулей их мнимые части должны различаться более чем на epsO; при совпадении мнимых частей аналогично должны различаться действительные части. Ограничение сохраняется для вычисления действительных нулей, которое может выполняться по излагаемой схеме при условии нулевой мнимой части. Для сокращения времени вычисления сетка (2.7) задана в прямоугольнике «минимальных» размеров. В дальнейшем будет оговорена схема, не требующая такого ограничения. Пример 2.2. Требуется локализовать и вычислить приближения всех комплексных нулей полинома степени ир1 = 8, действительные и мнимые части которых заданны в разделе констант как одномерные массивы Ъ и Ы, соответственно.
Компьютерный анализ устойчивости решения линейной системы ОДУ с матрицей постоянных коэффициентов на основе характеристических нулей
Если все элементарные делители найдены (компьютеризованная схема их нахождения изложена в приложении 3.1 к главе 3), то фундаментальная система построена, поскольку ее вид с единственностью определяется системой элементарных делителей. С помощью этой системы исчерпывающим образом решается вопрос об устойчивости линейной однородной дифференциальной системы (3.1). Именно, имеет место следующая теорема [80]. Теорема 3.2. Линейная однородная система (3.1) с постоянной матрицей А устойчива тогда и только тогда, когда все характеристические нули матрицы А обладают неположительными вещественными частями, причем характеристические нули, имеющие нулевые вещественные части, допускают лишь простые элементарные делители (т. е. соответствующие клетки Жордана сводятся к одному элементу). Именно на данной теореме базируется подход к построению компьютерного анализа устойчивости системы (3.1). После нахождения всех элементарных делителей, вид всех клеток Жордана известен, равно как известны все характеристические нули, и по виду матрицы Жордана определяются необходимые и достаточные условия устойчивости системы (3.1). Необходимо принять во внимание, что решение вопроса об устойчивости может быть полностью автоматизировано без нахождения элементарных делителей. Это достигается на той основе, что по виду матрицы с помощью метода Леверье определяются коэффициенты характеристического полинома, а с помощью сортировки - все его нули без учета кратности (первоначально), затем с учетом кратности. Сформулируем алгоритм анализа устойчивости. Шаг 1. Вычисляются все нули характеристического полинома без учета кратности. Шаг 2. Если среди них хоть один имеет положительную вещественную часть, то система неустойчива и анализ закончен. Иначе выполняется шаг 3. Шаг 3. Если число нулей с неположительной вещественной частью равно п, то они все различны и система устойчива. Анализ закончен.
В противном случае выполняется шаг 4. Шаг 4. Выполняется проверка кратности с отрицательной вещественной частью. Если в результате общее число нулей равно п, то нули с нулевой вещественной частью все различны, система устойчива и анализ закончен. Если общее число нулей меньше п, то среди нулей с нулевой вещественной частью имеются кратные, система неустойчива. Анализ полностью завершен. Вопрос об асимптотической устойчивости решается в один этап: если все нули имеют отрицательную вещественную часть, то система асимптотически устойчива и анализ закончен. Иначе система не является асимптотически устойчивой. Ее можно исследовать на устойчивость по изложенной методике, но уже речь не пойдет об асимптотической устойчивости. Это утверждение опирается на следующую теорему [80]. Теорема 3.3. Линейная однородная дифференциальная система (3.1) с постоянной матрицей А асимптотически устойчива тогда и только тогда, когда все характеристические нули матрицы А имеют отрицательные вещественные части. На теоремах 3.2 и 3.3 в целом базируется подход к компьютеризации анализа, как устойчивости, так и асимптотической устойчивости системы (3.1). При этом описанная методика дает полную автоматизацию требуемого компьютерного анализа.
Применим данную методику к анализу устойчивости реальных физических систем. Изложенный подход к оценке устойчивости по нулям характеристического полинома соотносится с возможностью ее практического применения к реальным физическим системам, которые определяются набором дифференциальных уравнений, описывающих их поведение. Однако все реальные системы являются нелинейными, линейные модели с постоянными и переменными параметрами, которые используются при анализе устойчивости, представляют собой результат линеаризации того или иного вида [81]. . Для дальнейшего применения рассматриваемого метода компьютерного анализа устойчивости целесообразно детализировать процесс преобразования нелинейных систем в линейные. Для описания сути процедуры линеаризации, непосредственно в соответствии с [81], рассмотрим характеристику нелинейного коэффициента усиления (рис. 3.1). Здесь х есть вход нелинейности, a f(x) - се выход. Предположим, что рабочая точка на кривой соответствует значению входной переменной х0. Тем самым полагаем, что х0 есть установившееся значение входной переменной. Предположим также, что х получает імалое приращение Ах, и новое значение входной переменной равно х = х0+Ах. Отношение приращения Д х) к приращению л- можно приближенно оценить как в конкретной точке, есть величина постоянная. Таким образом, представлена линеаризация нелинейной характеристики в окрестности точки х0. Точность аппроксимации (3.11) зависит от величины приращения Ах и от кривизны функции f{x) в окрестности рабочей точки. Строгое определение процедуры линеаризации основано на разложении функции fix) в ряд Тейлора в окрестности точки х0 [82]. (3.13) Сравнение (3.11) и (3.13) показывает, что выражение (3.11) есть просто первый член разложения Дх) в ряд Тейлора. Для того чтобы (3.11) достаточно хорошо аппроксимировало ряд (3.13), очевидно, члены разложения (3.13), содержащие производные второго и более высокого порядка, должны быть пренебрежимо малы. Иными словами, Дх) должна быть гладкой функцией и (или) приращение Ах должно быть малым. Во многих случаях линейная модель точно отражает свойства реальной системы. Таковыми, например, являются модели электрических цепей, содержащих сопротивления, индуктивности и емкости. В других случаях линеаризованная модель дает очень плохую аппроксимацию характеристик реальной системы, и тогда необходимо использовать ее нелинейную модель и специальные методы. Теперь непосредственно перейдем к рассмотрению систем управления представленных в виде систем линейных ОДУ с постоянными коэффициентами, полученных путем линеаризации. А также выясним, как процедура линеаризации увязывается с анализом устойчивости таких систем управления. общем случае система управления с обратной связью — это замкнутая система, характеризуемая двумя основными понятиями: входы системы и выходы. Данную замкнутую систему определим как систему, в которой некоторые из воздействующих на нее сигналов (называемых входами) зависят, хотя бы частично, от реакций системы на эти сигналы (так называемых выходов). Следовательно, входы системы являются функцией ее выходов, и наоборот. При работе с системами управления, линейные дифференциальные уравнения с постоянными коэффициентами, определяющие эти системы, могут быть решены с помощью преобразования Лапласа [81]. Но, что еще более важно, такие системы можно охарактеризовать передаточной функцией, и из этой характеристики вытекают все зависимости между входом и выходом системы.
