Вычисление нулей и экстремумов функций при вариации параметров на основе сортировки с приложением к моделированию устойчивости систем линейных дифференциальных уравнений

Актуальность проблемы. Для решения задач оптимизации широко используется средства вычислительной техники, накоплен огромный фонд численных методов и программ. Однако существуют трудности компьютеризации, многие из которых связаны с корректным определением одновременно всех локальных и глобальных экстремумов функций в области допустимых значений. Трудности усугубляются в случае сложных топологических рельефов функций. С целью разрешения этих трудностей обычно используют несколько методов численной оптимизации, чтобы увеличить долю удачных решений. Тем не менее, сохраняются сложности, связанные с использованием производных на основе конечно-разностных приближений. Отсюда актуальна разработка компьютерного метода локализации и вычисления экстремумов функций, который осуществлял бы программную идентификацию области каждого экстремума и отличался существенным ограничением роста погрешности при его вычислении. Разработка такого метода целесообразна для проблем автоматической программной идентификации всех экстремумов произвольной алгебраической или трансцендентной функции вначале одной переменной при вариации одного параметра, а затем при вариации двух и более параметров в произвольно фиксированной части области определения. Помимо нахождения экстремумов, актуально нахождение нулей функций при вариации параметров и, как частный случай, нулей полиномов с переменными коэффициентами. В частности, это требуется для оценки устойчивости систем линейных обыкновенных дифференциальных уравнений (ОДУ), которая определяется знаком действительных частей нулей характеристического полинома матрицы коэффициентов. Известны различные системы компьютерной математики, реализующие разнообразные методы вычисления нулей функций. Однако эти методы не предполагают автоматической идентификации области нулей, иногда требуют начального приближения, игнорируя наличие нулей в некоторых сложных случаях, либо не достигают в этих случаях требуемой точности вычислений. Известные схемы поиска нулей могут проявлять неустойчивость в случае трансцендентных функций. В этом контексте актуальна разработка программного метода локализации нулей полиномов и функций, который бы выполнял локализацию как вычисление каждого нуля с произвольной априори заданной границей погрешности. В данном аспекте целесообразно принять во внимание схемы использования сортировки для приближенных вычислений [1−4]. Алгоритмы ее выполнения позволяют минимизировать количество формул и методов традиционной математики. Применение сортировки опирается на упорядочение информации при вычислениях и включает только операции сравнения. Как следствие, можно ожидать снижения роста погрешности при решении задач с ее применением. На этой основе схемы параллельной сортировки можно рассматривать как одно из средств решения проблем устойчивости параллельных вычислений [5].

Сортировка [6] практически присутствует во всех приложениях операционных систем при обработке больших объемов данных. С помощью сортировки решаются задачи «группировки», когда нужно собрать элементы по некоторому признаку. Сортировка используется при поиске с целью его ускорения, с помощью сортировки можно сделать выдачи ЭВМ более удобным для человеческого восприятия. В контексте сортировки рассматриваются многие аспекты программирования.

Рассмотрим основные качества, характеризующие алгоритмы сортировок.

Алгоритмы сортировки оцениваются по скорости выполнения и эффективности использования памяти [7−9].

Время — основной параметр, характеризующий быстродействие алгоритма. Называется также вычислительной сложностью. Для упорядочения важны худшее, среднее и лучшее поведения алгоритма в терминах мощности входного множества А. Если на вход алгоритму подаётся множество А, то обозначим п = Л. Для типичного алгоритма хорошее поведение — это 0{п log ri) и плохое поведение — это 0(п2). Идеальное поведение для упорядочения — О (п). Также существует понятие сортирующих сетей. Предполагая, что можно одновременно (например, при параллельном вычислении) проводить несколько сравнений, можно отсортировать п чисел за 0(log2 ri) операций. При этом число п должно быть заранее известно.

Ряд алгоритмов требует выделения дополнительной памяти под временное хранение данных. Как правило, эти алгоритмы требуют 0(log") памяти. При оценке не учитывается место, которое занимает исходный массив и независящие от входной последовательности затраты, например, на хранение кода программы (так как всё- это потребляет <9(1)). Алгоритмы сортировки, не потребляющие дополнительной памяти, относят к сортировкам на месте.

Немаловажным качеством сортировок является их устойчивость [7]. Устойчивая сортировка не меняет взаимного расположения равных элементов.

Ещё- одно важное свойство алгоритма — это его сфера применения. Здесь два основных типов упорядочения [7−9]:

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

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

Ниже рассматриваются некоторые примеры сортировок, а также приводятся оценки временной сложности.

Алгоритмы устойчивой сортировки:

Пузырьковая сортировка [10]. Алгоритм состоит в повторяющихся проходах по сортируемому массиву. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Проходы по массиву повторяются до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает — массив отсортирован. При проходе алгоритма, элемент, стоящий не на своём месте, «всплывает» до нужной позиции как пузырёк в воде, отсюда и название алгоритма. Временная сложность алгоритма: 0(п2).

Сортировка перемешиванием (шейкерная) [6] - разновидность пузырьковой сортировки. Отличается тем, что просмотры элементов выполняются один за другим в противоположных направлениях, при этом большие элементы стремятся к концу массива, а маленькие — к началу. Лучший случай для этой сортировкиотсортированный массив (0{п)), худший — отсортированный в обратном порядке (0(л2)).

Сортировка вставками [7]. На каждом шаге алгоритма мы выбираем один из элементов входных данных и вставляем его на нужную позицию в уже отсортированном списке, до тех пор, пока набор входных данных не будет исчерпан. Метод выбора очередного элемента из исходного массива произволенможет использоваться практически любой алгоритм выбора.

Опишем этот процесс на примере пятиэлсментного списка, А = 50,20,40,75,35 (рис. 1).

Начать с элемента 50.

Вставить 20 в позицию 0, передвинуть 50 в позицию 1.

Вставить 40 в позицию 1, передвинуть 50 в позицию 2.

Элемент 75 на месте.

Вставить 35 в позицию 1, передвинуть хвост списка вправо га m га га м.

Рис. 1. Пример работы сортировки вставками.

Сложность алгоритма измеряется числом сравнений и равна 0(п2).

Хотя этот метод сортировки намного менее эффективен, чем более сложные алгоритмы, у него есть ряд преимуществ:

• прост в реализации;

• эффективен па небольших наборах данных, на наборах данных до десятков элементов может оказаться лучшим;

• эффективен на наборах данных, которые уже частично отсортированы;

• может сортировать список по мере его получения.

Сортировка слиянием [11] - алгоритм сортировки, который упорядочивает списки (или другие структуры данных, доступ к элементам которых можно получать только последовательно) в определённом порядке. Сначала задача разбивается на несколько подзадач меньшего размера. Затем эти задачи решаются с помощью рекурсивного вызова или непосредственно, если их размер достаточно мал. Наконец, их решения комбинируются, и получается решение исходной задачи.

Для решения задачи сортировки эти три этапа выглядят так:

• сортируемый массив разбивается на две половины примерно одинакового размера;

• каждая из получившихся половин сортируется отдельно, например — тем же самым алгоритмом;

• два упорядоченных массива половинного размера соединяются в один.

Рекурсивное разбиение задачи на меньшие происходит до тех пор, пока размер массива не достигнет единицы (любой массив длины 1 можно считать упорядоченным).

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

Общая сложность алгоритма — 0(п log я), при этом алгоритму требуется 0(п) дополни: ельной памяти для хранения слитых массивов.

Алгоритмы неустойчивой сортировки:

Сортировка выбором [12]. Шаги алгоритма заключаются в следующем:

• находим минимальное значение в текущем списке;

• производим обмен этого значения со значением на первой неотсортированной позиции;

• теперь сортируем хвост списка, исключив из рассмотрения уже отсортированные элементы.

Сложность алгоритма составляет 0(п2).

Сортировка Шелла [13]. Идея алгоритма сортировки состоит в сравнении элементов, стоящих не только рядом, но и на расстоянии друг от друга. Иными словами — сортировка вставками с предварительными «грубыми» проходами.

При сортировке Шелла сначала сравниваются и сортируются между собой ключи, отстоящие один от другого на некотором расстоянии с. После этого процедура повторяется для некоторых меньших значений d, а завершается сортировка Шелла упорядочиванием элементов при d = 1 (то есть, сортировкой вставками).

Часто оказывается, что сортировка Шелла есть самый лучший способ сортировки до, примерно, 1000 элементов.

Продемонстрируем работу алгоритма сортировки на примере. Пусть дан список Л = (32,95,16,82,24,66,35,19,75,54,40,43,93,68) и выполняется его сортировка методом Шелла, а в качестве значений d выбраны 5, 3, 1 (рис.2).

Исходный массив 32 95 16 82 24 66 35 19 75 54 40 43 93 68.

После сортировки с шагом 5 32 35 16 63 24 40 43 19 75 54 66 95 93 02 6 обменов.

Посла сортировки с шагом 3 32 19 16 43 24 40 54 35 75 68 65 95 93 В2 Э обменов.

Посла сортироаки с шагом 1 16 19 24 32 35 40 43 54 66 68 75 82 93 95 15 обмен о*.

Рис. 2. Пример работы сортировки Шелла.

На первом шаге сортируются подсписки, А, составленные из всех элементов А, различающихся на 5 позиций, т. е. подсписки А51 =(32,66,40), А5 2 =(95,35,43),.

Аь з = (16,19,93), As 4 = (82,75,68),' А5 5 = (24,54). В полученном списке на втором шаге вновь сортируются подсписки из отстоящих на 3 позиции элементов. Процесс завершается обычной сортировкой вставками получившегося списка.

При поверхностном взгляде на алгоритм нельзя сказать, что он дает хороший результат и даже то, что в результате получится отсортированный массив. Однако он дает и то и другое. Эффективность этого алгоритма объясняется тем, что при каждом проходе используется относительно небольшое число элементов или элементы массива уже находятся в относительном порядке, а упорядоченность увеличивается при каждом новом просмотре данных. Время выполнения сортировки Шелла равно 0{п log2 п).

Пирамидалышя сортировка [14]. В основе пирамидальной сортировки лежит специальный тип бинарного дерева, называемый пирамидойзначение корня в любом поддереве такого дерева больше, чем значение каждого из его потомков. Непосредственные потомки каждого узла не упорядочены, поэтому иногда левый непосредственный потомок оказывается больше правого, а иногда наоборот. Пирамида представляет собой полное дерево, в котором заполнение нового уровня начинается только после того, как предыдущий уровень заполнен целиком, а все узлы на одном уровне заполняются слева направо. Сортировка начинается с построения пирамиды. При этом максимальный элемент списка оказывается в вершине дерева: ведь потомки вершины обязательно должны быть меньше. Затем корень записывается последним элементом списка, а пирамида с удаленным максимальным элементом переформировывается. В результате в корне оказывается второй по величине элемент, он копируется в список, и процедура повторяется, пока все элементы не окажутся возвращенными в список. На рис. 3 изображена пирамида и ее списочное представление.

16 11 9 10 5 6 8 1 2 4 123 456 789 10 Рис. 3. Пирамида и ее списочное представление.

Алгоритм сортировки работает в худшем, в среднем и в лучшем случае за 0(п log и) операций при сортировке п элементов. Количество применяемой служебной памяти не зависит от размера массива (то есть 0(1)).

Быстрая сортировка [13]. В основе быстрой сортировки лежит принцип разбиения. Сначала выбирается некоторое значение в качестве «основы» и затем весь массив разбивается на две части. Одну часть составляют все элементы, равные или большие «основы», а другую часть составляют все элементы меньшего значения, по которому делается разбиение. Этот процесс продолжается для оставшихся частей до тех пор, пока весь массив не будет отсортирован. Например, для массива «fedacb» при использовании в качестве значения разбиения «d» будут получены следующие проходы при выполнении быстрой сортировки: исходное состояние: fedacbпервый проход: d с a d е fвторой проход: a b с d е f.

Этот процесс продолжается для каждой части «аЬс» и «def».

Фактически быстрая сортировка реализуется посредством рекурсивного алгоритма. Выбор значения разбиения можно сделать двумя способами. Это значение можно выбирать случайным образом или путем усреднения небольшого числа значений, выбранных из массива. Для оптимальной сортировки требуется выбрать значение, которое будет находиться в точности посередине всех элементов. Однако для большинства наборов данных это сделать нелегко. Но, даже в худшем случае, когда выбирается одно из экстремальных значений, быстрая сортировка работает достаточно хорошо. При этом временная сложность алгоритма составляет 0(п log и).

Современные методы последовательных сортировок обсуждаются в работах [15−17], а состояние параллельных сортировок освещено в [18−21], где, в частности, приводятся схемы с временной сложностью 0(log2 п).

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

I. Численные схемы безусловной оптимизации. Ниже приводится характеристика наиболее часто применяемых методов вычисления экстремумов функций одной или многих переменных.

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

Под минимизацией (максимизацией) функции п переменных /(х) = /(х15×2,., х") на заданном множестве U и-мерного векторного пространства.

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

При записи математических задач оптимизации в общем виде обычно используется следующая символика: х) —> min (max), х е U, где /(х) — целевая функция, a U — допустимое множество, заданное ограничениями на управляемые переменные.

Численные методы решения задач одномерной оптимизации. Задачи одномерной минимизации представляют собой простейшую математическую модель оптимизации, в которой целевая функция зависит от одной переменной, а допустимым множеством является отрезок вещественной оси: х) —> min (max), х е [я, b.

Минимизация целевой функции эквивалента максимизации (/(х)-мпах) и эквивалентна минимизации противоположной величины (-/(х) —" min), поэтому, не умаляя общности можно рассматривать только задачи минимизации.

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

Для решения задачи минимизации функции f (x) на отрезке [a, b на практике, как правило, применяют приближенные методы. Они позволяют найти решения этой задачи с необходимой точностью в результате определения конечного числа значений функции f (x) и ее производных в некоторых точках отрезка a, b. Методы, использующие только значения функции и не требующие вычисления ее производных, называются прямыми методами минимизации.

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

Рассмотрим наиболее распространенные на практике прямые методы поиска точки минимума. Самым слабым требованием на функцию fix), позволяющим использовать эти методы, является ее унимодальность (наличие у функции одного экстремума). Поэтому далее будем считать функцию f (x) унимодальной на отрезке a, b.

Метод перебора (равномерный поиск) [22] является простейшим из прямых методов минимизации и состоит в следующем.

Разобьем отрезок [а, б] на п равных частей точками деления: xt= a + i (b-a)lп, г = 0,1,., п. Вычислив значения /(.г) в точках х, путем сравнения найдем точку хт, где тэто число от 0 до п, такую, что.

Дл-,&bdquo-) = min/Ct,), / = 0,1,., и .

Погрешность определения точки минимума хт функции f (x) методом перебора не превосходит величины eps = (b-а)/п.

Метод поразрядного поиска [23]. Можно усовершенствовать метод перебора с целью уменьшения количества значений /(х), которые необходимо находить в процессе минимизации. Во-первых, если оказывается, что /(*,) < /(.г,+1), то отпадает необходимость вычислять /(х) в точках х1+2, х (+3 и т. д. Во-вторых, разумно было бы сначала определить отрезок, содержащий оптимальную точку, грубо, т. е. найти точку хт с небольшой точностью, а затем искать ее на этом отрезке с меньшим шагом дискретизации, повышая точность. Эти возможности улучшения и реализованы в методе поразрядного поиска. В этом методе перебор точек отрезка происходит сначала с шагом sh = xl+l-xl > eps до тех пор, пока не выполнится условие /(*,)< /(х1+1) или пока очередная из точек не совпадет с концом отрезка. После этого шаг уменьшается (обычно в 4 раза), и перебор точек с новым шагом производится в противоположном направлении до тех пор, пока значения /(х) снова не перестанут уменьшаться или очередная точка не совпадет с другим концом отрезка и т. д. Описанный процесс завершается, когда перебор в данном направлении закончен, а использованный при этом шаг дискретизации не превосходит eps.

Метод деления пополам (дихотомический поиск) [24]. Рассмотрим функцию /, которую требуется минимизировать на интервале al, bl. Предположим, что / строго квазивыпукла. Очевидно, что наименьшее число вычислений значений функции, которые необходимы для сокращения интервала неопределенности, равно двум. Одной из стратегии является выбор этих двух точек симметрично на расстоянии eps > 0 от середины интервала. Здесь число eps настолько мало, чтобы длина нового интервала неопределенности eps + tb^—a.^12 являлась достаточно близкой к теоретическому значению (й1-а1)/2, и в то же время такое, чтобы значение функции в этих двух точках были различимы.

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

Очевидно, что более эффективные схемы соответствуют меньшим значениям коэффициента сжатия. В дихотомическом поиске значение коэффициента приблизительно равно 0.5*/2. Метод золотого сечения является более эффективным, для него значение коэффициента сжатия равно 0.618*-1.

Рассмотрим такое симметричное расположение точек х{ и х2 на отрезке [a, b], при котором одна из них становится пробной точкой и на новом отрезке, полученном после исключения части исходного отрезка. Использование таких точек позволяет, кроме первой, ограничиться определением только одного значения /О), так как другое значение уже найдено на одной из предыдущих итераций. Для определения точек .г, и х2 рассмотрим сначала отрезок [ОД] и для определенности положим, что при уменьшении исключается правая часть этого отрезка. Пусть х2 = q, тогда симметрично расположенная точка т, =1 -q. Пробная точка х1 огрезка [од] перейдет в пробную точку xx=-q нового отрезка. Чтобы точки x2=q и x'2=l-q делили отрезки [ОД] и [0,q] в одном и том же отношении, должно выполняться равенство /q = q/(-q) или q2 =-q откуда находим положительное значение q — 0.61 803.

Таким образом, для произвольного отрезка [a, b] выражения для пробных точек примут вид: л, = а + (1 — q){b — а), х2 = а + q (b — а) .

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

1. Многомерный поиск без использования производных. Рассмотрим методы решения минимизации функции нескольких переменных /, которые опираются только на вычисление значений функции /(х), не используют вычисление производных, т. е. прямые методы минимизации. Важно отметить, что для применения этих методов не требуется не только дифференцируемости целевой функции, но даже аналитического задания. Нужно лишь иметь возможность вычислять или измерять значения / в произвольных точках. Такие ситуации часто встречаются в практически важных задачах оптимизации. В основном все описанные методы заключаются в следующем. При заданном векторе .г определяется допустимое направление d. Затем, отправляясь из точки х, функция / минимизируется вдоль направления d одним из методов одномерной минимизации. Задача линейного поиска заключается в минимизации f{x+lym*d) при условии, чго lym принадлежит L, где L обычно задается в форме L = {lym lym > 0} или L = {lym :а < lym < b}. Будем предполагать, что точка минимума lym существует. Однако в реальных задачах это предположение может не выполняться. Оптимальное значение целевой функции в задаче линейного поиска может быть не ограниченным или оптимальное значение функции конечно, но не достигается ни при каком lym .

Метод гщклического покоординатного спуска [27]. В этом методе в качестве направлений поиска используются координатные векторы. Метод циклического покоординатного спуска осуществляет поиск вдоль направлений dx, d2,., dn, где.

— вектор, все компоненты которого, за исключением У-ого, равны нулю. Таким образом, при поиске по направлению dj меняется только переменная х}, в то время как все остальные переменные остаются зафиксированными.

Метод Хука и Дживса [28] осуществляет два типа поиска — исследующий поиск и поиск по образцу. Первые две итерации процедуры показаны на рис. 4.

Рис. 4. 1-поиск по образцу- 2- исследующий поиск вдоль координатных осей.

При заданном начальном векторе х, исследующий поиск по координатным направлениям приводит в точку х2. Последующий попек по образцу в направлении л-j — х2 приводит в точку у. Затем исследующий поиск, начинающийся из точки у, дает точку х3. Следующий этап поиска по образцу вдоль направления дг3 — х2 дает у. Затем процесс повторяется.

Метод Розенброка [28]. Рассмотрим вариант метода с применением одномерной минимизации. На каждой итерации процедура осуществляет итеративный поиск вдоль п линейно независимых и ортогональный направлений. Когда получена новая точка в конце итерации, строится новое множество ортогональных векторов.

На рис. 5 новые направления обозначены через ql и q2.

Рис. 5. Построение новых направлений поиска в методе Розенброка.

Опишем построение направлений поиска. Пусть dx, d2,., dn — линейно независимые векторы, по норме равные единицы. Предложим, что эти векторы взаимно ортогональны, т. е. (dl*dj) = 0 для i ^ j. Начиная из текущей точки хк, целевая функция последовательно минимизируется вдоль каждого из направлений, в результате чего получается точка xk+l. В частности, xkll ~хк = Sum (lym j*d), где lymj — длина шага по направлению d}. Новый набор направлений qx, q2,—, qn строится с помощью процедуры Грамма-Шмидта следующим образом:

Новые направления, построенные таким образом, являются линейно независимыми и ортогональными.

Минимизация по правильному симплексу [29]. Правильным симплексом в пространстве Е" называется множество из п +1 равноудаленных друг от друга точек (вершин симплекса). Отрезок, соединяющий две вершины, называется ребром симплекса.

В пространстве Е2 правильным симплексом является совокупность вершин равностороннего треугольника, а в Ег — правильного тетраэдра. Если х0 — одна из вершин правильного симплекса в Е", то координаты остальных п вершин х{, х2,., хп можно найти, например, по формулам: где dx = a (sqrt (n +1) -1) / п * sqrt{2), d2 = a{sqrt (n +1) + я -1) / и * sqrt{2), а — длина ребра. dj, если lym j — О, Sum (lym i * dt), i = [/, n если lym j ^ 0,.

1).

Вершину v0 симплекса, построенного по формулам (1), будем называть базовой. В алгоритме симплексного метода используется следующее важное свойство правильного симплекса. По известному симплексу можно построить новый симплекс путем отражения какой-либо вершины, например, к симметрично относительно центра тяжести хс остальных вершин симплекса. Новая и старая вершины у и хк связаны соотношением: (у + хк)/2 = хс, где хс = (I/ n) Sum (xJ для всех 1Фк. В результате получаем новый симплекс с тем же ребром и вершинами у = 2с-хк. Таким образом, происходит перемещение симплекса в пространстве. На рис. 6 представлена иллюстрация этого свойства симплекса для двумерной области.

Поиск точки минимума функции fix) с помощью правильных симплексов производится следующим образом. На каждой итерации сравниваются значения функции в вершинах симплекса. Затем проводится описанная выше процедура огражения для той вершины, в которой fix) принимает наибольшее значение. Если в отраженной вершине получается меньшее значение функции, то переходят к новому симплексу. Если же попытка отражения не приводит к уменьшению функции, то сокращают длину ребра симплекса, например, вдвое и строят новый симплекс с этим ребром. В качестве базовой выбирают ту вершину х0 старого симплекса, в которой функция примет минимальное значение. Поиск точки минимума /О) заканчивают, когда-либо ребро симплекса, либо разность между значениями функции в вершинах симплекса становятся достаточно малыми.

Поиск точки минимума по деформируемому симплексу [29]. Алгоритм минимизации по правильному симплексу можно модифицировать, добавив к процедуре отражения при построении нового симплекса процедуры сжатия и растяжения. А именно, положение новой вершины у вместо вершины хп, соответствующей наибольшему значению функции, находится сравнением и выбором наименьшего среди значений целевой функции в точках:

Рис. 6. Построение нового симплекса в Е2 отражением точки х2 xc-a (xt-xn), Q< 1.

Геометрическая иллюстрация этих процедур для двумерного пространства приведена на рис. 7 и более общий случай на рис. 8. хО х2×1.

Рис. 7. Геометрическая иллюстрация поиска точки минимума по деформируемому симплексу, а х1 Ь х1×1×1 с d.

Рис. 8. Новые симплексы, полученные в результате процедуры сжатия (a, b) — отражения (с) — растяжения (d).

Так как величина, а принадлежит интервалу (0,1), то выбор точек zx и z2 соответствует сжатию симплексаb приближенно равно 1, поэтому выбор точки z3 соответствует отражению, a g > 1 и выбор точки z4 приводит к растяжению симплекса.

Отметим, что при деформациях утрачивается свойство правильности исходного симплекса.

2. Многомерный поиск, использующий производные. Пусть функция f (x) дифференцируема в Е". В этом разделе рассматривается итерационная процедура минимизации вида: xk =xk{+lym[k]*dk, к = 1,2,., где направление убывания dk определяется тем или иным способом с учетом информации о частных производных функции f{x), а величина шага 1утк > 0 такова, что.

Л = 1,2,.

Так как функция предполагается дифференцируемой, то в качестве критерия останова в случае бесконечной итерационной последовательности {х^}, как правило, выбирают условие ||grad (f (xk)).

Метод наискорейшего спуска [30] является одной из наиболее фундаментальных процедур минимизации дифференцируемой функции нескольких переменных. Вектор d называется направлением спуска для функции / в точке х, если существует такое d >0, что f (x + lym*d).

Нш j (х + lym *d)~ /(х) < 0, при lym -" 0 +, то d — направление спуска. В методе наискорейшего спуска осуществляется движение вдоль направления d, для которого ||с/|| = 1 и которое минимизирует приведенный выше предел. Если / дифференцируема в точке х и grad (f (x))=t 0. то — grad (f (х)) /\grad (f (х))\ является направлением наискорейшего спуска. В связи с этим метод наискорейшего спуска иногда называют градиентным методом.

3. Методы, использующие сопряженные направления [25, 29]. Понятие сопряженности очень важно в задачах безусловной минимизации. В частности, если целевая функция квадратичная, то поиском вдоль сопряженных направлений можно получить точку минимума не более чем за п шагов.

Определение. Пусть Н — симметрическая матрица порядка п х п. Векторы dx, d2,., dk называются FT-сопряженными, или просто сопряженными, если они линейно независимы и dl{t)lld] = 0 при 1Ф j, где dt (0 — вектор строка.

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

Метод Дэвидона — Флетчера — Пауэлла [25]. Первоначально метод был предложен Дэвидоном и затем развит Флетчером и Пауэллом. Метод Дэвидона-Флетчера-Пауэлла называют также и методом переменной метрики. Он попадает в общий класс квазиньютоновских процедур, в которых направления поиска задаются в видеD * grad (f (у)). Направление градиента является, таким образом, отклоненным в результате умножения на — -О, где D — положительно определенная симметрическая матрица порядка пхп, аппроксимирующая обратную матрицу Гессе. На следующем шаге матрица D х представляется в виде суммы Dj и двух симмегрических матриц ранга один каждая. В связи с этим схема иногда называется схемой коррекции ранга два.

II. Исследование ландшафтов целевых функций на основе эволюционной оптимизации. В рамках подхода к решению задач оптимизации исследуется возможность применения эволюционных и генетических алгоритмов [31, 32]. При этом строятся новые целевые функции, обеспечивающие получение оптимальных решений для исходных функций [33]. Использование одних и тех же целевых функций в рамках схемы эволюционных алгоритмов часто приводит к достижению локального, но не глобального экстремума [34]. По этой причине возникает идея замены одной целевой функции па другую при условии, что это приводит к эквивалентному результату. Актуальна задача выбора эффективной целевой функции на ранней стадии разработки нового алгоритма. Для выбора такой функции конструируются подходы на основе анализа ландшафтов целевой функции [35, 36]. Разработанные в данном аспекте методы ориентированы на получение интегральных параметров ландшафта целевой функции, которые определённым образом характеризуют её- сложность для эволюционных алгоритмов. Чтобы оптимизировать функцию модифицируется алгоритм расчета интегральных параметров на основе барьерных деревьев. На этой основе выделяются компоненты, по которым можно судить об эффективности соответствующих им целевых функций для эволюционных алгоритмов. Метод барьерных деревьев [36] позволяет оценить глубину каждого локального минимума и степень его влияния на процесс эволюционного проектирования. Основная идея метода заключается в том, что сложность поверхности отражает высота h, на которую необходимо подняться, чтобы попасть из одного локального минимума в другой.

Подход включает следующие затруднения. Сравнивать целые наборы величин затруднительно, поскольку количество локальных оптимумов обычно различно для различных целевых функций. Кроме того, для автоматического сравнения желательно иметь один интегральный параметр. Поэтому необходимо оценить вероятность не возникновения преждевременной сходимости. Для этого достаточно, чтобы генетический алгоритм мог выйти из текущего локального оптимума и найти другой с лучшим значением. В случае успеха он вероятнее найдёт локальный оптимум, который ближе всего находится к текущему локальному оптимуму. Производится [33] переход от набора параметров локального минимума к единственному параметру оценки области локального минимума. f (xt, xj) — минимальный барьер, который необходимо преодолеть. чтобы попасть из локального оптимума г в локальный оптимум j. Барьер — это наивысшая точка некоторого пути. Чтобы получить только один интегральный параметр для всего ландшафта, достаточно выделить из всех локальных оптимумов тот, выход из которого наиболее сложен. Значение такого оптимума интерпретируется как глубина В ландшафта. Для сравнения ландшафтов берётся отношение глубины к общей высоте ландшафта, которое называется сложностью ц/. Для сравнения ландшафтов используются два параметра — глубина В и СЛОЖНОСТЬ If/.

Основная идея определения всех локальных оптимумов состоит в предварительной дискретизации пространства неравномерной сеткой. После этого для определения является ли некоторая точка локальным или глобальным оптимумом достаточно просмотреть соседние для неё- точки. В результате получается линейный алгоритм сложности 0(3 nN), где N —количество точек исходной выборки, а п — размерность пространства. Положительные результаты достигаются в случае поверхности близкой к классу унимодальных и при достаточных размерах области локализации экстремума [33]. Количество найденных решений зависит от модальности функции.

III. Методы вычисления нулей функций. Известные классические и современные методы вычисления нулей функций и нулей полиномов, как частного случая функций [37−45]: метод Лобачевского, итерационные методы к числу которых относят метод Чебышева, метод Эйткена, метод Ньютона, метод секущих, метод Мюллера, помимо того, применяются метод Брента, метод Лина, метод Фридмана, метод Лагерра, метод сопровождающей матрицы, интервальные jметоды и др.

Практически во всех представленных выше методах, отыскание нулей полиномов и функций осуществляется в два этапа [37]:

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

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

Способы отыскания границ нулей полинома.

Pn (z) = ±aeze (3) обусловлены рядом положений. Для нахождения границы всех нулей (действительных и комплексных) используются: теорема о числе корней алгебраического уравнения Pn (z) = 0, теорема о свойстве парной сопряженности комплексных нулей (3) [46], теорема об оценке модулей нулей полинома [37]. Границы дейс1вительных нулей, возможно найти с помощью теоремы Лагранжа о верхней границе положительных нулей полинома, теоремы о нижних и верхних границах положительных и отрицательных корней алгебраического уравнения Рп (х) = 0, теоремы Гюа о необходимом условии действительности всех корней алгебраического уравнения [46]. Точное число действительных нулей полинома (3), заключенных в данных пределах, может быть определено с помощью теорем Декарта, Штурма и Бюдана [37].

Задача отделения нулей полинома (3) заключается в том, чтобы каждый из них заключи гь в интервал, не содержащий других нулей полинома. Для отделения действительных нулей полинома (3) применяют способ Фурье, основанный на теореме Бюдана. Способ отделения комплексных нулей полинома (3), подробно описанный в [37], использует понятие индекса полинома относительно некоторой заданной прямой в комплексной плоскости и позволяет отделить комплексные пули, расположенные в некоторой полосе. Программная реализация схемы отделения комплексных нулей затруднительна.

Известны различные системы компьютерной математики [47−50], реализующие разнообразные методы вычисления нулей и экстремумов функций. В частности, в MathCAD для определения пулей функций и полиномов реализованы методы секущих, Брента, Лагерра и сопровождающей матрицы [41], а для определения экстремумов функций реализованы градиентные методы, включая метод сопряженных градиентов, метод Левенберга [51]. В пакете аналитических вычислений Maple нули полиномов вычисляются как собственные числа матрицы.

Фробениуса, а исследование на экстремум функции заключается в нахождении точек, в которых производная исследуемой функции равна нулю [48].

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

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

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

В основу метода целесообразно положить алгоритмы сортировки, поскольку, они включают лишь операции сравнения и сами по себе не накапливаю: погрешность.

Сортировки традиционно применяются для поиска и моделирования методов теоретической информатики [19, 52]. Положительный опыт применения сортировки именно для рассматриваемых схем вычислений описан в [3, 4, 53−59]. При этом параллелизм сортировки [60, 61] влечет возможность построения параллельных схем определения нулей и экстремумов в целом.

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

Требования устойчивости и быстродействия идентификации экстремумов функций и нулей полиномов обеспечиваются за счет устойчивости и параллелизма схем на основе сортировки.

Следует отметить, что задача вычисления нулей полиномов тесно связана с задачей нахождения собственных чисел матрицы (полная проблема собственных значений [62]). На этой основе дается классическое решение задачи об устойчивости линейной системы дифференциальных уравнений с постоянной матрицей коэффициентов [63], которое основывается на следующей теореме:

Теорема 1. Нулевое решение линейной системы в матричной форме вида = (4) где /1 = const — матрица коэффициентов системы, является устойчивым по Ляпунову, если: 1) все характеристические числа матрицы, А имеют отрицательные или нулевые вещественные части- 2) все характеристические числа с нулевыми вещественными частями, т. е. чисто мнимые характеристические числа (если таковые имеются), являются простыми корнями минимального многочлена матрицы, А и не устойчивым, если хотя бы одно из условий 1), 2) не выполняется.

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

Следовательно, наиболее естественным методом определения устойчивости системы является решение ее характеристического уравнения и определение знаков действительных частей полученных корней. Однако такой метод не может считаться приемлемым для большинства практических задач, так как возникают вычислительные трудности при решении алгебраических уравнений высоких степеней. Поэтому на практике применяются другие методы, позволяющие, не прибегая к определению корней характеристического уравнения, получить все необходимые данные по устойчивости. Такие методы называются критериями устойчивости [64, 65]. Следует отметить, что все критерии устойчивости в той или иной форме используют тот факт, что у устойчивой системы действительные части всех корней характеристического уравнения отрицательны, однако знак действительных частей корней устанавливается не непосредственно, а косвенным путем.

Имеется ряд критериев устойчивости, которые делятся на две разновидности: алгебраические {критерий Гурвица) и частотные {критерии.

Михайлова и Найквиста). Алгебраические критерии являются аналитическими, а частотные — графоаналитическими. Из перечисленных критериев устойчивости рассмотрим лишь критерий Найквиста. Он основан на построении годографа передаточной функции разомкнутой системы. Критерий устойчивости Найквиста формулируется следующим образом: замкнутая система устойчива, если годограф передаточной функции разомкнутой системы не охватывает на комплексной плоскости точку с координатами (-1, /<>). Если годограф проходит через точку (-1,/0), то система находится на границе устойчивости. На рис. 9 показаны примеры устойчивой и неустойчивой систем управления.

1 ^ Im.

-, 1 Г /4 v- / ' / Re, а б.

Рис. 9. Годограф передаточной функции в случае устойчивой (а) и неустойчивой (б) системы управления.

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

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

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

Для достижения поставленной цели в диссертационной работе решаются следующие задачи:

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

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

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

4. Алгоритм локализации нулей полинома и его параллельное видоизменение применить для случая поиска собственных значений матрицы произвольного порядка, включая матрицу постоянных коэффициентов системы линейных ОДУ. На этой основе обеспечить компьютеризацию анализа устойчивости по Ляпунову линейной системы ОДУ как в случае асимптотической, так и неасимптотической устойчивости.

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

6. Выполнить сравнение искомых результатов работы с известными методами численной безусловной оптимизации, вычисления нулей полиномов и анализа устойчивости систем линейных ОДУ.

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

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

Научная новизна результатов диссертационной работы заключается в следующем:

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

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

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

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

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

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

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

Основные положения, выносимые на защиту:

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

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

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

4. Синтезированы распараллеливаемые алгоритмы компьютерного анализа устойчивости линейной системы ОДУ с матрицей постоянных коэффициентов по нулям характеристического полинома, инвариантные относительно вида правой части системы. Алгоритмы позволяют программно определять характер устойчивости без преобразования правой части системы.

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

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

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

Внедрение и использование результатов работы. Полученные в работе результаты использованы.

1. В ОАО НКБ ВС для повышения точности и быстродействия определения положения объекта в системе цифровой обработки видеосигналовдля разработки схем компьютерного анализа и оценки параметров устойчивости систем автоматического управлениядля оценки устойчивости управления пространственной ориентацией движущихся объектов.

2. В госбюджетной НИР «Математические методы устойчивой параллельной обработки, поиска и распознавания», код ГРНТИ 28.23.15, регистрационный номер 01.2.106 436.

3. В учебном процессе кафедры информационных систем ГОУВПО «ТГПИ» в рамках курсов «Информатика», «Информационные технологии в математике», «Численные методы», «Элементы абстрактной и компьютерной алгебры».

Апробация работы. Основные результаты работы были представлены на:

— Международной научно-технической конференции «ММА-2006» «Математические модели и алгоритмы для имитации физических процессов» (Таганрог, ТГПИ, 2006 г.);

— XII Международной научной конференции «Математические модели физических процессов» (Таганрог, ТГПИ, 2007 г.);

— VI Международной научно-технической конференции «Информационно-вычислительные технологии и их приложения» (Пенза, МНИЦ ПГСХА, 2007 г.);

— Всероссийской научно-технической конференции с международным участием «Компьютерные и информационные технологии в науке, инженерии и управлении» (Таганрог, ЮФУ, 2008 г.);

— IX Всероссийском симпозиуме по прикладной и промышленной математике (Северо-Кавказкий ГТУ, ИПИ РАН, РИНХ, Кисловодск, 2008 г.);

— Международной научно-технической конференции «Модели и алгоритмы для имитации физико-химических процессов» МАФП12 008 (Таганрог, ТГПИ, 2008 г.);

— IV Международной научно-практической конференции «Методология и практика образовательных технологий в условиях модернизации образования» (Таганрог, ТГПИ, 2008 г.).

Публикации. По материалам работы опубликовано 13 печатных работ общим объемом около 12 печатных листов, в том числе 3 статьи в журналах из перечня рекомендуемых ВАК РФ.

Структура н объём работы. Диссертационная работа состоит из введения, трех глав основного раздела, заключения, списка литературы и приложений к трем главам. Основное содержание работы изложено на 151 страницах, включая список литературы из 89 наименований.

3.7. Выводы.

1. Предложен метод компьютерного анализа устойчивости линейной системы ОДУ с матрицей постоянных коэффициентов по нулям ее характеристического полинома. Базовый алгоритм синтезирован на основе сортировки, опирается на теоремы 3.2 и 3.3, обеспечивая в результате комплексного построения метода в целом компьютеризацию анализа устойчивости системы.

2. Показана инвариантность предложенного метода относительно вида правой части системы, обоснована его вычислительная устойчивость. Отличительной чертой метода является компьютеризация анализа устойчивости по Ляпунову линейной системы ОДУ как в случае асимптотической, так и неасимптотической устойчивости.

3. Доказана теорема о достоверности результатов предложенного компьютерного анализа устойчивости линейной системы ОДУ, показан параллелизм метода и дана оценка временной сложности параллельной схемы анализа устойчивости при ограничениях, исключающих кратность нулей характеристического полинома матрицы коэффициентов системы.

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

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

ЗАКЛЮЧЕНИЕ

.

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

Работа включает следующие научные результаты.

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

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

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

4. Синтезированы распараллеливаемые алгоритмы компьютерного анализа устойчивости линейной системы ОДУ с матрицей постоянных коэффициентов по пулям характеристического полинома, инвариантные относительно вида правой части системы. Алгоритмы позволяют программно определять характер устойчивости без преобразования правой части системы.

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

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

Научная новизна результатов диссертационной работы заключается в следующем.

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

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

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

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

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

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

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

Практическое использование результатов работы:

1. В ОАО НКБ ВС для повышения точности и быстродействия определения положения объекта в системе цифровой обработки видеосигналовдля разработки схем компьютерного анализа и оценки параметров устойчивости систем автоматического управлениядля оценки устойчивости управления пространственной ориентацией движущихся объектов.

2. В госбюджетной НИР «Математические методы устойчивой параллельной обработки, поиска и распознавания», код ГРНТИ 28.23.15, регистрационный номер 01.2.106 436.

3. В учебном процессе кафедры информационных систем Таганрогского государственного педагогического института в рамках курсов «Информатика», «Информационные технологии в математике», «Численные методы», «Элементы абстрактной и компьютерной алгебры».

.