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

На правах рукописи

Веселая Анастасия Александровна

ВЫЧИСЛЕНИЕ НУЛЕЙ И ЭКСТРЕМУМОВ ФУНКЦИЙ ПРИ ВАРИАЦИИ ПАРАМЕТРОВ НА ОСНОВЕ СОРТИРОВКИ С ПРИЛОЖЕНИЕМ К МОДЕЛИРОВАНИЮ УСТОЙЧИВОСТИ СИСТЕМ ЛИНЕЙНЫХ ДИФФЕРЕНЦИАЛЬНЫХ УРАВНЕНИЙ

Специальность:

05.13.18 - Математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ

диссертации на соискание ученой степени

кандидата технических наук

ТАГАНРОГ 2009

003489965

Работа выполнена в ГОУВПО «Таганрогский государственный педагогический институт».

Научный руководитель:

доктор технических наук, профессор Ромм Яков Евсеевич

Официальные оппоненты:

доктор физико-математических наук, профессор Илюхин Александр Алексеевич

доктор технических наук,

доцент Боженюк Александр Витальевич

Ведущая организация:

ФГНУ НИИ «СПЕЦВУЗАВТОМАТИКА»

Защита состоится « /У » срсё/гОьС*^- 20/0 г. в 14.20 на заседании диссертационного совета Д 212.208.22 Южного федерального университета по адресу: г. Таганрог, пер. Некрасовский, 44, ауд. Д- 406.

С диссертацией можно ознакомиться в Зональной научной библиотеке Южного федерального университета по адресу: 344000, г. Ростов-на-Дону, ул. Пушкинская, 148.

Автореферат разослан ЗбкСЫуи^ 2009 г.

Просим Вас прислать отзыв на автореферат, заверенный гербовой печатью учреждения, по адресу: 347928, ГСП-17А, Ростовская область, г.Таганрог, пер. Некрасовский, 44, диссертационный совет Д 212.208.22.

Ученый секретарь

диссертационного совета Д 212.208.22, доктор технических наук, профессор / Целых А.Н.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Для решения задач численной оптимизации широко используется средства вычислительной техники, накоплен огромный фонд численных методов и программ. Однако существуют трудности компьютеризации, связанные с корректным определением одновременно всех локальных и глобальных экстремумов функций в области допустимых значений. Трудности усугубляются в случае сложных топологических рельефов функций, сохраняются сложности, связанные с использованием производных на основе конечно-разностных приближений и выбором начальных приближений. Отсюда актуальна разработка компьютерного метода локализации и вычисления экстремумов функций, который осуществлял бы программную идентификацию области каждого экстремума и отличался ограничением роста погрешности при его вычислении. Разработка такого метода целесообразна для идентификации всех экстремумов произвольной алгебраической и трансцендентной функции от одной и более переменных при вариации параметров в произвольно фиксированной части области определения. Аналогично, актуально нахождение нулей функций при вариации параметров, в частности, нулей полиномов с переменными комплексными коэффициентами. Это требуется для оценки устойчивости систем линейных обыкновенных дифференциальных уравнений (ОДУ) по знаку действительных частей собственных значений матрицы коэффициентов. В этом контексте актуальна разработка программной локализации всех нулей полиномов и функций, при которой локализация эквивалентна вычислению каждого нуля с априори заданной границей погрешности. Это актуально для многих задач физики, механики, техники, при разработке практически каждой системы управления с обратной связью, включая моделирование синхронного генератора, работающего на сеть большой мощности.

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

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

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

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

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

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

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

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

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

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

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

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

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

фактически означает его вычисление с априори заданной границей абсолютной погрешности.

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

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

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

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

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

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

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

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

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

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

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

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

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

Внедрение и использование результатов работы. Полученные в работе результаты использованы: в ОАО НКБ ВС для повышения точности и быстродействия определения положения объекта в системе цифровой обработки видеосигналов; для разработки схем компьютерного анализа и оценки параметров устойчивости систем автоматического управления; для оценки устойчивости управления пространственной ориентацией движущихся объектов; в госбюджетной НИР «Математические методы устойчивой параллельной обработки, поиска и распознавания», код ГРНТИ 28.23.15, регистрационный номер 01.2.00106436; в учебном процессе кафедры информационных систем Таганрогского государственного педагогического института в рамках курсов «Информатика», «Информационные технологии в математике», «Численные методы», «Элементы абстрактной и компьютерной алгебры».

Апробация работы. Основные результаты работы были представлены на Международной научно-технической конференции «ММА-2006» «Математические модели и алгоритмы для имитации физических процессов» (Таганрог, ТГПИ, 2006 г.); XII Международной научной конференции «Математические модели физических процессов» (Таганрог, ТГПИ, 2007 г.); VI Международной научно-технической конференции «Информационно-вычислительные технологии и их приложения» (Пенза, МНИЦ ПГСХА, 2007 г.); Всероссийской научно-технической конференции с международным участием «Компьютерные и информационные технологии в науке, инженерии и управлении» (Таганрог, ЮФУ, 2008 г.); IX Всероссийском симпозиуме по прикладной и промышленной математике (Северо-

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

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

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

СОДЕРЖАНИЕ РАБОТЫ

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

В первой главе излагаются компьютерные схемы применения устойчивой распараллеливаемой сортировки для локализации и вычисления одновременно всех экстремумов и нулей функции одной переменной при вариации нескольких параметров у = f(x,b), где * - независимая переменная, Ь - вектор варьируемых параметров, в произвольной части области определения с априори заданной границей абсолютной погрешности. При этом ограничения на вид функции имеют общий характер, функция должна подаваться на вход метода в дискретизированном виде. Из дискретизированных на равномерной сетке значений функции формируется одномерный массив, к которому применяется сортировка. Рассматриваются разновидности сортировки слиянием с временной сложностью в параллельном варианте o(log,n), параллельная сортировка подсчетом сложности o(l). Сортировка должна сохранять порядок равных элементов и обладать взаимно однозначным соответствием входных и выходных индексов элементов. Для идентификации экстремумов к сортировке подключается условие локализации экстремальных элементов. В последовательности С = (с[1],с[2],...,с[п]) условный оператор локализует каждый минимум в окрестности произвольно заданного радиуса е среди входных индексов отсортированных элементов при том ограничении, что радиус не превосходит половины наименьшего расстояния между точками соседних минимумов. Входные индексы e[¿] на выходе сортировки располагаются в порядке отсортированных элементов c[i], данный оператор можно представить циклическим соотношением | е[к-1]-е[к]\>£, / = 1,2, ...,к-\, означающим, что в г-окрестности входного индекса нет индекса элемента отсортированного массива, который бы не превосходил элемент с входным индексом е[к]. Все локальные максимумы последовательности идентифицируются по условию | е [к + 1]-е[к] |>е, / = 1,2,...,п-к . Нули локализуются как минимумы модулей элементов при условии достаточной малости. Схема применяется к

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

Теорема 1. Рассматриваемый способ локализации с помощью сортировки минимальных (максимальных) значений или нулей функции одной действительной переменной у =/(*), определенной и непрерывной на промежутке [лгО, , означает вычисление этих экстремумов или нулей с наперед заданной границей абсолютной погрешности е0. При этом шаг дискретизации А функции на равномерной сетке, покрывающей данный промежуток, априори удовлетворяет ограничению Л < Л0 < < с0, где ¡ю таково, что все экстремумы функции на данном промежутке

сохраняются при дискретизации в узлах равномерной сетки с шагом Л ^ А„.

В предположении, что повторные пределы совпадают с пределами одновременно по всем переменным в каждой точке экстремума, теорема обобщается на случай экстремумов и нулей функции ¡// =/(х„х2,...,х.). На этой основе экстремумы идентифицируются с наперед заданной точностью, что иллюстрируется результатами численных экспериментов. Предложенные схемы обладает параллелизмом на основе разбиения области на взаимно независимые фрагменты и на основе параллелизма использованных сортировок. Для случая функции одной переменной у=/(*) имеет место доказываемая в гл. 1 теорема о параллелизме.

Теорема 2. В условиях теоремы 1 вычисление всех экстремумов и нулей функции у=/О) на произвольном отрезке из области определения с наперед заданной границей абсолютной погрешности еа можно выполнить по максимально параллельной схеме с временной сложностью Г(Л/хЛг!/2) = 2хг = 0(1), где м — количество непересекающихся промежутков, каждый из которых покрыт

Ы-хо!

равномерной сеткой из N узлов, ы =

и

- время бинарного сравнения.

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

формальными утверждениями относительно априори заданной границы погрешности программной идентификации экстремумов и минимальной временной сложности их параллельного вычисления. В главе проводится сравнение предложенных схем с методами Марк и \lathCAD. В табл.1 представлено сравнение поиска всех минимумов модуля трансцендентной функции /(х) = з'т(Ь*I+21)-соэ(Ь* 1 + 56), где вариация коэффициента ь происходит в промежутке с шагом дискретизации ИЬ = 0.001, дискретизация независимой

переменной, , выполнена с шагом Ы = 0.0002.

Таблица 1

Идентификация множества всех нулей функции /(*) = sin(¿»/ + 2])-cos(¿>*/ + 56) при ¿6 [-1,5], I е [-3,2]

метод варьируемый параметр нули значения функции

пакет Maple - - -

пакет MathCAD -1.6595512645814 -0.8447857547393 0.0248866975438 0.2056588437559 9.98400000000000Е-0004 5.57200000000000Е-0002

0.14673894746388 0.03575848473834 -0.6915676877534 -0.7557689675445 6.39000000000000Е-0005 4.8730D000DDD0DE-0DD4

0.0074821511649 0.3450065476985 2.3854764543233 -0.0964553437764 5.93670000000000Е-0004 1.13400000000000Е-ОООЗ

схема на основе сортировки -9.22000000000000000Е-0001 -6.62000000000000000Е-0001 ' 2.49999999999999999E-Ó002 2.79999999999999999Е-0002 1.78000000000000008Е-0002 9.72000000000000008Е-0002 9.85573710664060Е-0004 5.22266762794201Е-0002

-6.17399999999999999Е-0001 -5.37999999999999999Е-0001 5.88105462000761Е-0005 4.55561106963436Е-0004

-8.00000000000000007Е-0003 2.34000000000000000Е-0001 2.00280000000000000Е+0000 -6.15999999999999992Е-0002 5.6936ÓÓÍ'304Ó5Ó5EÍ0Ó'4 1.15024869734566Е-0003

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

В табл. 2 дано сравнение вычисления всех минимумов функции f(x) = sin(-x*e"u'u'2''+b*d*e"''"x'^,), 1 <х<5, fa=0.00001 при вариации двух параметров -l<6si и -2<d<7 с шагом hb = 0.0002, hd = о.ооз соответственно.

Таблица2

Идентификация множества всех минимумов функции

f(x) = sin(-x*e"■'-"м-1'+b*d*e^,u'-,) при Ь е [-1, i], d е [-2, l), jc e [l, 5]

метод варьируемый параметр А варьируемый параметр d точки минимумов значения минимумов

паки-Maple - - -

пакет MathCAD - - - -

схема на основе сортировки 1.000800... ОООЕ+ОООО -9.8400...OOOE-OOOI -1.7600...ОООЕ+ОООО -1.91837568542661Е-0008

Предложенная схема дала все минимумы, Maple и MathCAD не дали ни одного.

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

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

Предварительно приводится метод идентификации действительных нулей полинома в произвольно фиксированных границах, затем локализации и вычисления всех действительных нулей полинома без указания области их нахождения. Описываются аналогичные программные методы локализации и вычисления всех комплексных нулей полинома. Далее рассмотренные методы объединяются в единый метод программного поиска нулей полинома с переменными комплексными коэффициентами вначале без учета кратности, затем с ее учетом. В рассматриваемом аспекте все переменные коэффициенты полиномов играют роль варьируемых параметров функций. Базовой конструкцией метода является распараллеливаемая сортировка слиянием. Метод опирается на принцип максимума модуля, согласно которому функция 1/| Р,(х) | не может иметь максимума внутри области аналитичности, все минимумы модуля полинома Р,{х) совпадают с его нулями. Рассматривается полином р,(г)=аг"+аиг|+,..+а, с комплексными коэффициентами от комплексной переменной г, где * = *+/>>,/ =-/^7. В плоских декартовых координатах вводится равномерная прямоугольная сетка: *,=*„+№

1 = 0,1.....ы,; у, = у,+1Н, / = 0,1,...,//,, включающая область всех нулей. Сетка строится с

постоянным шагом А по направлениям осей ОХ и ОУ. Строится функция двух действительных переменных /(х,у)=\ я(х) |\ ее значение определяется с помощью

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

Распространение схемы вычисления нулей полиномов на случай определения кратности найденных нулей достигается рекуррентным повторением приводимого ниже алгоритма.

Алгоритм идентификации кратности нулей полинома:

1. Найти все нули исходного полинома рп(х) = а,х"+ а,_,х"'+...+ аа. Если количество найденных нулей меньше я, то среди них имеются кратные, иначе кратных нет. При наличии кратных нулей перейти к п. 2, иначе конец алгоритма.

2. Выполнить деление Р,(х) на где х, • первый из нулей полинома. После деления получим новый полином С._,(д= + + ..лЬ1х + Ь, степени п-1, коэффициенты которого вычисляются путем сравнения коэффициентов при равных степенях полиномов Р„(х) и С^(х)х :

и

Перейти к п. 3.

3. Выполнить поиск всех нулей полинома G_,(*) • Если среди них не оказалось значения х,, этот нуль не является кратным. В этом случае все операции, включая схему (1), повторяются для нуля х,. Если же среди найденных нулей оказалось значение , то выполняется переход к п. 4.

4. Выполнить деление по схеме (1) полинома G_,(x) на для проверки на наличие в нем нуля х,. Процесс продолжается до исчерпания кратности нуля х,. Выполняется переход к п. 5.

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

6. Конец алгоритма.

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

Имеет место теорема.

Теорема 3. Локализация с помощью сортировки действительных нулей полинома с действительными коэффициентами Р,(х) = а,х" + а,-,+ ...+а„ означает их вычисление с наперед заданной границей абсолютной погрешности е0. При этом шаг дискретизации h полинома на равномерной сетке, покрывающей данный промежуток, априори удовлетворяет ограничению h<,h0<<sa, где А„ таково, что все

минимумы модулей полинома на данном промежутке сохраняются при дискретизации в узлах данной сетки с шагом А < А„ .

Как следствие теоремы 3 доказывается

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

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

Следствие 2. Вычисление всех нулей полинома степени п в произвольном прямоугольнике, включающем область всех нулей, с наперед заданной границей абсолютной погрешности с0 может быть выполнено с временной сложностью Т{К) - 0(1), где число процессоров R пропорционально степени полинома.

Для параллельной модификации Ксанки метода Леверье имеет место

Следствие 3. Локализация и вычисление нулей характеристического полинома матрицы без учета кратности распараллеливается с оценками следствия 2, к которым следует присоединить известные оценки временной сложности схемы Ксанки, что влечет r(R) = 0(\ogln), я = для всей схемы нахождения собственных значений матрицы, - при условиях локализации из следствия 2.

Предложенная схема вычисления нулей полинома с учетом кратности отличается от известных по построению на основе сортировки, отсутствием необходимости отделения нулей, тем, что не требует поиска приближения к нулю и дифференцирования полинома. От близких аналогов схему отличают утверждения относительно априори заданной границы погрешности локализации всех нулей полинома и минимальном времени параллельного вычисления. Дано сравнение предложенной схемы по отношению к системам Мар1е и Ма&САЭ. В табл.4 представлено сравнение поиска нулей полинома г1+гг' - 5г' + & - Ъг1 + .

Таблица 4

Поиск всех нулей полинома Pt(z) = z" + 2z' - 5z' + 3z! - 8г! + 7z -1

метод нули полинома значения полинома

действительные части мнимые части

пакет Maple 0.1768909669 0.7721397382 1.374062600 -0.2911055493 -3.7408822006 -0.2911055493 1.157415824 -1.157415824 о о о о о о о о о о о о о о о о о о о о о о о о + + + + + + w w W w W щ о о о о о о о о о о о о о о о о о о о о о о о о о о о о о о о о о о о о о о о о о о о о о о о о о о о о о о о о сэ о о о о о о о о о о о о о о о о о о о о о о о о о о о о о о о о о

пакет MalhCAD 0.1768917743 0.7721418642 1.3740625329 -0.2911056114 -3.7408822012 -0.2911055114 1.157415847 -1.157415847 о о о о о о о о о о о о о о о о о о о о о о о о о о о о о о о о о о о о о о о о о о о о о о о о о о о о о о О О О О о о о о о с5 о о о о о о о о о о о о о о о о о о о о о о о о о о и м и и tn м + + ++ + + о о о о о о о о о о о о о о о о о о о о о о о о

схема на основе сортировки 1.76890966857905385Е-0001 7.72139738220389167Е-0001 1.37406259985020758Е+0000 -2.9110549296533598Е-0001 -3.74088220633543469Е+0000 -2.9110549296533598Е-0001 -7.95660034566752774Е-0056 -3.16008489045919537Е-0030 -3.33078986116666696Е-0030 1.15741582439969050Е+0000 -1.52644440606887366Е-0029 -1.15741582439969050Е+0000 1.19875591908180Е-0109 2.93873587705572Е-0039 4.70197740328915Е-0038 1.69058391685606Е-0029 1.20625586248895Е-0032 1.07413091459166Е-0031

Для данного примера точность вычислений нулей полинома описанным методом сравнима с точностью Maple и превышает точность MathCAD. В табл. 5 дано сравнение поиска всех нулей полинома с комплексными коэффициентами Р, (z) = г' - 25z' + iz' + 3z" + (3 - I')z3 - z: + 4< z + 2 . Таблица 5 Поиск всех нулей полинома P7(z) = z7 - 25z' + iz' + 3z* + (3 - i)z' -z! + 4/z + 2

метод нули полинома

действительные части мнимые части

пакет Maple 24.99507224 0.7572528083 0.1506448968 -0.2107310159 -0.6563745630 -0.4764991875 0.4406348163 -0.03996041571 0.1142234600 0.4480216559 0.5405649974 0.1358988094 -0.6282069188 -0.5705415882 О.ООООООООООООООЕ+ОООО О.ООООООООООООООЕ+ОООО О.ООООООООООООООЕ+ОООО О.ООООООООООООООЕ+ОООО О.ООООООООООООООЕ+ОООО О.ООООООООООООООЕ+ОООО О.ООООООООООООООЕ+ОООО

пакет MathCAD 24.99507232 0.7572528368 0.1506449074 -0.2107310210 -0.6563745638 -0.4764992567 0.4406349769 -0.0399604347 0.1142234759 0.4480216667 0.54056499854 0.1358988174 -0.6282069190 -0.5705415845 О.ООООООООООООООЕ+ОООО О.ООООООООООООООЕ+ОООО О.ООООООООООООООЕ+ОООО О.ООООООООООООООЕ+ОООО 0 .ООООООООООООООЕ+ОООО О.ООООООООООООООЕ+ОООО О.ООООООООООООООЕ+ОООО

схема на основе сортировки 2.49549842518719239Е+0001 7.67154838986370853Е-000I 1 53377870864853353Е-0001 -2.03704620 П4446824Е-0001 -6.49682343311622404 Е-0001 -4.75932754378976657Е-0001 4.46881230760859694Е-0001 -4.00888840364379673Е-0002 1.14263593449189634Е-0001 4.49825772218099703Е-0001 5.39873143632903858Е-0001 1.34556032698054608Е-0001 -6.273984 57436638529Е-0001 -5.68753838952370864Е-0001 8,91593346098189Е-0022 3.04604689096578Е-0028 1.17187970569350Е-0034 1.77296451637817Е-0029 •3.21286866593359Е-0030 1.46105618301451Е-0032 1.20544564859954Е-0029

Результаты сравнения идентичны предыдущим.

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

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

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

Алгоритм анализа устойчивости:

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

2. Если среди них хоть один имеет положительную вещественную часть, то система неустойчива и анализ закончен. Иначе выполняется переход к п. 3.

3. Если число нулей с неположительной вещественной частью равно п, то они все различны и система устойчива. Анализ закончен. Иначе выполняется переход к п. 4.

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

5. Конец алгоритма.

Вопрос об асимптотической устойчивости решается в один этап: если все нули имеют отрицательную вещественную часть, то система асимптотически устойчива, иначе система не является асимптотически устойчивой.

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

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

Идеальное Объект запаздывание

1 Р--

J ► к J(J+1)'

Рис. 1. Система управления с идеальным запаздыванием по времени

Характеристическое уравнение системы имеет вид

e-V

1 + G(s)e"- = 1+-, при G(s) = -е"' ИЛИ s' + 2s! + s + е"" = 0 .

ф + 1)1 ' у

Чтобы определить при каких значениях параметра /„ система устойчива, достаточно определить знак действительной части комплексных нулей характеристического уравнения при вариации параметра <„. Действительная и мнимая часть значения полинома в левой части уравнения складываются, соответственно, с действительной и мнимой частью значения трансцендентной функции e"'1" =cos(/„*x)-i*sin(<„*у), s = х + i*у . Сумма квадратов полученных значений образует функцию, которая подается на вход программы локализации ее комплексных нулей. В результате работы программы получится, что при <„ < 0,52 все действительные части нулей отрицательны, что свидетельствует об асимптотической устойчивости системы управления. Система является устойчивой, но не асимптотически при 0,52 <,!,<. 0,55 (действительные части характеристических значений являются нулевыми, причем не кратными). С ростом /0 система может быть как неустойчива, так при отдельных значениях этого параметра —устойчива.

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

'-0.561 0.6793 0.6099 0 0.4948 0.5463 0 -0.952 -0.7494 '

0 -13.7658 1.4409 0 3.6163 1.1781 0 8.5472 -3.3161

0 -15.5076 -150.1554 0 -12.6793 38.9205 0 42.4023 -21.4333

0 -6.5351 -1.1714 -2.072} 0.9552 2.2156 0 5.4592 -2.3385

0 56334 0.4076 0 -16.5675 1.1141 0 -4.2309 10.117

0 -3.Í073 52.627 0 -13.1829 -1569117 0 -38.8349 68 5987

0 2.9781 3.9766 0 -10.6238 -4.7247 -4.4063 -5.201 10.7116

10005 0 0 -10000 0 0 0 0 0

10000 0 0 0 0 0 -10000 0 0

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

Таблица 6

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

Действительные части нулей Мнимые части нулей Значения функции

-2.66500943657576565Е+0001 -2.6650094365757 6565Е+0001 -6.22055557585856523Е+0000 -6.22055557585856523Е+0000 -1.66464451731006319Е+0002 -1.03733858985095690Е+0002 -4.55027202023557511Е+0000 -1.99345676734757965Е+0000 -1.99345676734757965Е+0000 3.46476467676925324Е+0002 -3.46476467676925324Е+0002 2.28977834326906336Е+0002 -2.28977834326906336Е+0002 -2.57576896988978967Е-0023 0.00000000000000009Е+0000 3.39475765352467569Е-0034 1.27568875975037655Е+0000 -1 27568875975037655Е+0000 1.32546757977877554Е-0081 1.65468487907903862Е-0089 5.93474587906487369Е-0073 4.58545363499078375Е-0076 2.44228970765314678Е-0080 1.74746037084635676Е-0079 0.24354657687756434Е-0067 1.33460876545224145Е-0083 4.83737637454326467Е-0071

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

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

Таблица 7

Общая характеристика сравнения

метод оценка устойчивости при нулевой действительной части устойчивость параллелизм преобразование правой части системы инвариантность относительно вида системы оценка устойчивости при наличии трансцендентности

критерий Гурвица - - - + + -

критерий Михайлова - ■ - - + - -

критерий Найквиста - - •- + - -

предложенный метод + + + - + +

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

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

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

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

Список опубликованных работ по теме диссертации в изданиях ВАКа

1. Ромм Я.Е., Лабинцева A.A., Заика И.В. Схема идентификации нулей и экстремумов разностных решений уравнений в частных производных на основе сортировки // Обозрение прикладной и промышленной математики. - Т.15. - Вып.З.

- 2008. - С. 512 - 513. (лично автора - 0,1 п.л.).

2. РоммЯ.Е., Лабинцева A.A. Поиск корней полинома с переменными комплексными коэффициентами // Известия ЮФУ. Технические науки. - 2008. - № 2. - С. 103 - 110. (лично автора - 0,2 п.л.).

3. РоммЯ.Е., Лабинцева А. А, Заика И.В. Безусловная оптимизация на основе сортировки с приложением к компьютерному анализу устойчивости систем управления // Известия вузов. Северо-Кавказский регион. Технические науки. Серия «Управление, вычислительная техника и информатика». - 2008. - № 6. - С. 11-17. (лично автора - 0,25 пл.).

Основные публикации по теме работы

4. Ромм Я.Е., Заика И.В., Лабинцева A.A. Идентификация нулей и экстремумов разностных решений обыкновенных дифференциальных уравнений и уравнений в частных производных на основе сортировки / ТГПИ. - Таганрог, 2006.

- 32 с. Деп. в ВИНИТИ 07.03.2006, № 230 - В2006. (лично автора - 0,5 п.л.).

5. Ромм Я.Е., Лабинцева A.A. Программная идентификация нулей и экстремумов разностных решений уравнений в частных производных. - В кн.: Материалы Международной научно-технической конференции «ММА-2006». -«Математические модели и алгоритмы для имитации физических процессов». Т 1. Физико-математические и физико-технические модели и алгоритмы для имитации физических процессов. - Таганрог. - 2006. - С. 317 - 321. (лично автора - 0,2 п.л.).

6. Ромм Я.Е., Лабинцева A.A. Идентификация нулей и экстремумов разностных решений уравнений в частных производных на основе сортировки / ТГПИ. - Таганрог, 2007. - 30 с. Деп. в ВИНИТИ 20.02.2007, № 154 - В2007. (лично автора - 0,7 п.л.).

7. Лабинцева A.A. Идентификация на основе сортировки нулей и экстремумов разностных решений уравнений в частных производных // Информационно-вычислительные технологии и их приложения: сборник статей VI Международной научно-технической конференции. Пенза: РИО ПГСХА - 2007. - С. 115-117.

8. Ромм Я.Е., Лабинцева A.A. Программная идентификация корней полинома с переменными коэффициентами. - В кн.: «Математические модели физических процессов». Т 1. Физико-математические и физико-технические модели, проблемы технологии. - Таганрог. - 2007. - С. 153 - 158. (лично автора - 0,2 п.л.).

9. Ромм Я.Е., Заика И.В., Лабинцева A.A. Безусловная численная оптимизация при вариации параметров. I / ТГПИ. - Таганрог, 2008. - 31 с. Деп. в ВИНИТИ 04.03.2008 № 193 - В2008. (лично автора-0,45 п.л.).

10. Ромм Я.Е., Заика И.В., Лабинцева A.A. Безусловная численная оптимизация при вариации параметров. II / ТГПИ. - Таганрог, 2008. - 44 с. Деп. в ВИНИТИ 04.03.2008 № 194 - В2008. (лично автора - 0,7 п.л.).

11. Ромм Я.Е, Веселая A.A. Программная идентификация экстремумов функций при вариации параметров. - В кн.: Материалы Международной научно-технической конференции МАФП' 2008. - «Модели и алгоритмы для имитации физико-химических процессов». - Таганрог. - 2008. - С. 259 - 265. (лично автора -0,12 п.л.).

12. Ромм Я.Е, Веселая A.A. Схема идентификации корней многочлена с переменными комплексными коэффициентами на основе сортировки. - В кн.: 4-я Международная научно-практическая конференция. - «Методология и практика образовательных технологий в условиях модернизации образования». - Таганрог. -2008. - С. 109 - 111. (лично автора - 0,2 пл.).

13. Ромм Я.Е, Веселая A.A. Вычисление нулей полинома с переменными комплексными коэффициентами в применении к компьютерному анализу устойчивости линейной однородной системы дифференциальных уравнений с постоянной матрицей коэффициентов / ТГПИ. - Таганрог, 2009. - 62 с. Деп в ВИНИТИ 26.02.2009, № 111 - В2009. (лично автора - 1,4 пл.).

Личный вклад автора в работах, написанных в соавторстве, состоит в следующем [1,4-6] - разработка схем идентификации нулей и экстремумов функции двух переменных на основе сортировки и их компьютерное моделирование в приложении к разностным решениям уравнений в частных производных; [9-11] - синтез и анализ распараллеливаемых алгоритмов локализации с наперед заданной точностью экстремумов функции при вариации параметров, компьютерное моделирование алгоритмов; [8,2, 12] - разработка схем распараллеливаемой локализации на основе сортировки и приближенного вычисления всех нулей полиномов с переменными комплексными коэффициентами, компьютерное моделирование схем; [3] -синтез и анализ алгоритма компьютерной идентификации кратности нулей полиномов и его моделирование; [13] - разработка распараллеливаемых схем компьютерного анализа устойчивости систем линейных ОДУ с матрицей постоянных коэффициентов при вариации параметров по локализованным нулям характеристического полинома, компьютерное моделирование.

Соискатель

Веселая A.A.

Тип.ТТИ ЮФУ Заказ № ^Г5тир. у^экз.

ВВЕДЕНИЕ.

ГЛАВА 1. ПРОГРАММНАЯ ИДЕНТИФИКАЦИЯ ЭКСТРЕМУМОВ ФУНКЦИЙ ПРИ ВАРИАЦИИ ПАРАМЕТРОВ НА ОСНОВЕ УСТОЙЧИВОЙ РАСПАРАЛЛЕЛИВАЕМОЙ СОРТИРОВКИ.

1.1. Временная сложность параллельных сортировок слиянием и подсчетом на основе матриц сравнения.

1.1.1. Алгоритм слияния с взаимно однозначным соответствием входных и выходных индексов.

1.1.2. Временная сложность сортировки слиянием массива с целой степенью по основанию два элементов.

1.1.3. Программа сортировки слиянием массива с числом элементов, не являющимся целой степенью по основанию два.

1.1.4. Алгоритм и временная сложность сортировки подсчетом по матрице сравнений.

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

1.3. Сортировка как основа программной идентификации экстремумов функции одной переменной с варьируемым параметром.

1.4. Программная идентификация на основе сортировки экстремумов функции одной переменной при вариации двух и более параметров.

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

1.6. Максимально параллельная схема идентификации нулей и экстремумов функций с оценкой временной сложности.

1.7. Сравнение схемы идентификации нулей и экстремумов функции при вариации параметров на основе сортировки с методами Maple и MathCAD.

1.8. Выводы.

ГЛАВА 2. ЛОКАЛИЗАЦИЯ И ВЫЧИСЛЕНИЕ НУЛЕЙ ПОЛИНОМОВ С ПЕРЕМЕННЫМИ КОМПЛЕКСНЫМИ КОЭФФИЦИЕНТАМИ С УЧЕТОМ КРАТНОСТИ В ПРИЛОЖЕНИИ К ХАРАКТЕРИСТИЧЕСКИМ ПОЛИНОМАМ МАТРИЦ.

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

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

2.3. Схема локализации и вычисления комплексных нулей полинома без учета кратности.

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

2.5. Поиск на основе сортировки нулей полинома с переменными комплексными коэффициентами.

2.6. Алгоритм идентификации кратности нулей полинома.

2.7. Локализация и вычисление на основе сортировки нулей характеристического полинома матрицы с учетом кратности.

2.8. Локализация на основе сортировки нулей полинома с априори заданной границей абсолютной погрешности.

2.9. Сравнение метода вычисления нулей полиномов на основе сортировки с методами Maple и MathCAD.

2.10. Выводы.

ГЛАВА 3. КОМПЬЮТЕРНЫЙ АНАЛИЗ УСТОЙЧИВОСТИ ЛИНЕЙНОЙ ОДНОРОДНОЙ СИСТЕМЫ ДИФФЕРЕНЦИАЛЬНЫХ УРАВНЕНИЙ С МАТРИЦЕЙ ПОСТОЯННЫХ КОЭФФИЦИЕНТОВ НА ОСНОВЕ ИДЕНТИФИКАЦИИ ЗНАКА СОБСТВЕННЫХ ЗНАЧЕНИЙ.

3.1. Постановка вопроса.

3.2. Анализ устойчивости линейной системы ОДУ с матрицей постоянных коэффициентов по критерию Гурвица и критерию Михайлова в аспекте компьютеризации.

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

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

3.4.1. Линеаризация систем управления.

3.4.2. Анализ устойчивости систем управления с обратной связью.

3.4.3. Анализ устойчивости синхронного генератора, работающего на сеть большой мощности.

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

3.6. Сравнение компьютерного анализа устойчивости с существующими методами.

3.7. Выводы.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

50

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

20

60

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

20

40

50

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

20

40

50

75

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

20

36

40

50

75

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

0] [1] И [3] [4]

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

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

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

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

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

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

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

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

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

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

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

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

Рекурсивное разбиение задачи на меньшие происходит до тех пор, пока размер массива не достигнет единицы (любой массив длины 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) и выполняется его сортировка методом Шелла, а в качестве значений с1 выбраны 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 82 6 обмен оа

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Разобьем отрезок [а,Ь] на п равных частей точками деления: х, = а + г'(6-а)/п, i' = 0,l,.,n. Вычислив значения fix) в точках х,, путем сравнения найдем точку хт, где т -это число от 0 до п, такую, что fixm) = min/(x,), / = 0,1,.,и .

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

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

Метод деления пополам (дихотомический поиск) [24]. Рассмотрим функцию /, которую требуется минимизировать на интервале \ах,Ь{]. Предположим, что / строго квазивыпукла. Очевидно, что наименьшее число вычислений значений функции, которые необходимы для сокращения интервала неопределенности, равно двум. Одной из стратегий является выбор этих двух точек симметрично на расстоянии еря > 0 от середины интервала. Здесь число ерБ настолько мало, чтобы длина нового интервала неопределенности ер$ + ф{-ах)12 являлась достаточно близкой к теоретическому значению фх-ах)12, и в то же время такое, чтобы значение функции в этих двух точках были различимы.

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

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

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

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

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

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

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

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

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

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

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

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

На рис.5 новые направления обозначены через и д2. У х1

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

Опишем построение направлений поиска. Пусть - линейно независимые векторы, по норме равные единицы. Предложим, что эти векторы взаимно ортогональны, т. е. (Д *с/у.) = 0 для / ^ j. Начиная из текущей точки хк, целевая функция последовательно минимизируется вдоль каждого из направлений, в результате чего получается точка хк+1. В частности, хш ~хк = 5ит(1ут, где

1ут] - длина шага по направлению йг Новый набор направлений строится с помощью процедуры Грамма-Шмидта следующим образом:

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

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

В пространстве Е2 правильным симплексом является совокупность вершин равностороннего треугольника, а в Ег - правильного тетраэдра. Если я:0 - одна из вершин правильного симплекса в Е", то координаты остальных п вершин х{,х2,.,хп можно найти, например, по формулам: где ^ = a{sqrt{n + \)-Y)lп*sqrt(2), (12 = а(ядМ(п + 1) + п-1)/п*5^(2), а - длинаребра.

Г dj, если lym j- О,

Sum (lym i * dt), i = [/, n\ если lym j Ф 0, aj,npuj= 1, a, - Sum (a j i = [l, j-\\ при j> 2,

1)

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

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

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

Рис.6. Построение нового симплекса в Е2 отражением точки х2 хс-а(хс-хп),0<а<1, 22=хс + а(хс-хп),0<а<\, 2з =хс + Ь(хс-хп\Ъ*1,

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

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

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

Так как величина а принадлежит интервалу (0,1), то выбор точек г! и г2 соответствует сжатию симплекса; Ъ приближенно равно 1, поэтому выбор точки соответствует отражению, а g > 1 и выбор точки г4 приводит к растяжению симплекса.

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

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

-1), Л = 1,2,.

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

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

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

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

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

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

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

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

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

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

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

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

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

Способы отыскания границ нулей полинома pn(z) = ±aize (3)

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

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

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

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

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

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

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

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

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

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

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

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

Теорема 1. Нулевое решение линейной системы в матричной форме вида

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

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

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

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

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

1 ^ 1т

-,1 г\ /4 V; / ' / Ее а б

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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 г.);

- Международной научно-технической конференции «Модели и алгоритмы для имитации физико-химических процессов» МАФП12008 (Таганрог, ТГПИ, 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.00106436.

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

1. Ромм Я.Е., Тюшнякова И.А, Заика И.В. Идентификация экстремумов функций на основе сортировки с приложением к вычислительным схемам алгебры, анализа и распознаванию изображений // Проблемы программирования. Киев, 2006. №2-3.-С. 708-717.

2. РоммЯ.Е. Метод вычисления нулей и экстремумов функций на основе сортировки с приложением к поиску и распознаванию. I // Кибернетика и системный анализ. 2001. - № 4. - С. 142 - 159.

3. Ромм Я.Е. Метод вычисления нулей и экстремумов функций на основе сортировки с приложением к поиску и распознаванию. II // Кибернетика и системный анализ. 2001. - № 5. - С. 81 - 101.

4. Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. СПб.: БХВ-Петербург. 2004.- 608 с.

5. Вирт П. Алгоритмы и структуры данных. М.: Мир, 1989. - 360 с.

6. Кнут Д. Искусство программирования. Т.З. Сортировка и поиск. 2-е изд. - М.: Вильяме, 2007. - 824 с.

7. Томас X. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн. Алгоритмы: построение и анализ 2-е изд. - М.: Вильяме, 2006. - 1296 с.

8. СеджвикР. Фундаментальные алгоритмы на С. Анализ/Структуры данных/Сортировка/Поиск. СПб.: ДиаСофтЮП, 2003. - 672 с.

9. Левитин А. Алгоритмы: введение в разработку и анализ. М.: Вильяме, 2006, —С. 144- 146.

10. Левитин А. Алгоритмы: введение в разработку и анализ. М.: Вильяме, 2006. - С. 169 - 172.

11. Левитин А. Алгоритмы: введение в разработку и анализ. М.: Вильяме, 2006. - С. 143 - 144.

12. Макконнелл Дж. Анализ алгоритмов. Вводный курс. М.: Техносфера, 2002.-304 с.

13. Левитин А. Алгоритмы: введение в разработку и анализ. М.: Вильяме, 2006. - С. 275 - 284.

14. Gerbessiotis A.V., Siniolakis C.J. Probabilistic integer sorting. Information Processing Letters, Volume 90, Issue 4, 31 May 2004. - P. 187 - 193.

15. BiedlTh., Chan T., DemaineE.D., Fleischer R., GolinM., KingJ.A., Munro J.I. Fun-Sort or the chaos of unordered binary search. Discrete Applied Mathematics, Volume 144, Issue 3, 15 December 2004. - P. 231 - 236.

16. Sanguthevar Rajasekaran, Sandeep Sen. A generalization of the 0-1 principle for sorting. Information Processing Letters, Volume 94, Issue 1, 15 April 2005.-P. 43 -47.

17. РоммЯ.Е., Виноградский B.B. Преобразование сортировок в форму устойчивых схем со свойствами прямой и обратной адресности / ТГПИ. Таганрог, 2003.-43 с. Деп. в ВИНИТИ 08. 12. 2003, № 2130 - В2003.

18. Цейтлин Г.Е. Введение в алгоритмику. Киев: Сфера, 1998. 473 с.

19. Цейтлин Г.Е. Распараллеливание алгоритмов сортировки // Кибернетика- 1989.-№6.-С. 67-74.

20. NardelliE., Proietti G. Efficient unbalanced merge-sort. Information Sciences, Volume 176, Issue 10 , 22 May 2006. - P. 1321 - 1337.

21. Васильев Ф.П. Численные методы решения экстремальных задач. М.: Наука, 1980. - 552 с.

22. Сухарев А.Г., Тимохов А.В., Федоров В.В. Курс методов оптимизации. -М.: Наука, 1986.-328 с.

23. Поляк Б.Т. Введение в оптимизацию. М.: Наука, 1983. - 384 с.

24. Аттетков А.В. Методы оптимизации. Учебн. для студ. втузов / М. изд. МГТУ им. Н.Э. Баумана, 2003. - 439 с.

25. Харчистов Б.Ф. Методы оптимизации. Таганрог: Изд-во ТРТУ. - 2004.- 140 с.

26. Сеа Ж. Оптимизация. Теория и алгоритмы. М.: Мир, 1973. - 244 с.

27. Зангвилл У. Нелинейное программирование. Единый подход. М.: Сов. радио, 1973.-312 с.

28. Банди Б. Методы оптимизации (вводный курс). М.: Радио и связь, 1988.- 128 с.

29. Калиткин H. Н. Численные методы. М.: Наука, 1978. - 512 с.

30. Батищев Д.И. Генетические алгоритмы решения экстремальных задач: Учебное пособие. Воронеж: ВГТУ, 1995. - 69 с.

31. Букатова И.Л. Эволюционные технологии средства интенсивной информатизации. М.: ИРЭ РАН. - Препринт N 5 (593). 1994.-25 с.

32. Коляда А.В. Исследование ландшафтов целевых функций при эволюционной оптимизации. Таганрог: ТРТУ, 2005, автореферат диссертации на соискание ученой степени канд. техн. наук. - 18 с.

33. Кунцман Ж. Численные методы. М.: Паука, 1979. 160 с.

34. Гладков Л.А., Зипченко Л.А., Курейчик В.В., Курейчик В.М., Лебедев Б. К, Нужнов Е.В, Сорокин С.Н. «Методы генетического поиска». Под ред. В.М. Курейчика. Таганрог, изд-во ТРТУ, 2002. 147 с.

35. Курейчик В.В. Эволюционные методы решения оптимизационных задач. Таганрог, ТРТУ, 1999. 99 с.

36. БерезинИ.С., Жидков Н.П. Методы вычислений. Т. 2. - М.: Государственное издательство физико-математической литературы, 1962. - 640 с.

37. Демидович Б.П., Марон И.А. Основы вычислительной математики. Учебное пособие: М.: Наука, 1970. 664 с.

38. КулишУ., РацД., Хаммер Р., Хокс М. Достоверные вычисления. Базовые численные методы. М.: РХД, 2005. - 495 с.

39. Самарский А.А. Введение в численные методы. М.: Наука, 1987.288 с.

40. Тарасевич Ю.Ю. Информационные технологии в математике. М.: СОЛОН-Пресс, 2003. - 144 с.

41. Baase S., Van Gelder A. Computer Algorithms, Addison-Wesley Longman. Reading, MA, 2000. 436 p.

42. IiansenE.R., Sengupta S. Bounding solutions of system of équations using interval analysis // BIT. 1981. - Vol. 21. - P. 203 - 211.

43. Алефельд Г., Херцбергер Ю. Введение в интервальные вычисления. -М.: Мир, 1987.-278 с.

44. Калмыков С.А., ШокинЮ.И., Юлдашев З.Х. Методы интервального анализа. Новосибирск: Наука, 1986. - 493 с.

45. Киреев В.И., Пантелеев А.В. Численные методы в примерах и задачах. -М.: Высш. шк., 2004. 480 с.

46. Говорухин В., Цибулин В. Компьютер в математическом исследовании. Учебный курс. СПб.: Питер, 2001. - 624 с.

47. Дьяконов В. Maple 9 в математике, физике и образовании. М.: СОЛОН, 2004. - 688 с.

48. Дьяконов В. Mathcad 2001: специальный справочник. СПб.: Питер, 2002. - 832 с.

49. Очков В.Ф. Mathcad 12 для студентов и инженеров. СПб.: БХВ -Санкт-Петербург, 2005. - 464 с.

50. Шуп.Т. Решение инженерных задач на ЭВМ. М.: Мир, 1982. - 240 с.

51. Цейтлин Г.Е. Алгоритмы адаптивной сортировки и их классификация. 4.2 // Пробл. упр. и информат. 1995. - № 3. - С. 95 - 103.

52. РоммЯ.Е. Бесконфликтные и устойчивые методы детерминированной параллельной обработки / Диссертация на соискание ученой степени доктора технических наук. Таганрог: ТРТУ. - 1998. - 546 е.; ВНТИ Центр. - № 05.990.001006.

53. РоммЯ.Е., ЛабинцеваA.A. Поиск корней полинома с переменными комплексными коэффициентами // Известия ЮФУ. Технические науки. Тематический выпуск: «Компьютерные и информационные технологии в науке, инженерии и управлении» 2008. - № 2. - С. 103 - 110.

54. Ромм Я.Е., Заика И.В., Лабинцева A.A. Безусловная численная оптимизация при вариации параметров. I / ТГПИ. Таганрог, 2008. - 31 с. Деп. в ВИНИТИ 04.03.2008 № 193 - В2008.

55. РоммЯ.Е., Заика И.В., Лабинцева A.A. Безусловная численная оптимизация при вариации параметров. II / ТГПИ. Таганрог, 2008. - 44 с. Деп. в ВИНИТИ 04.03.2008 № 194 - В2008.

56. РоммЯ.Е. Параллельная сортировка слиянием по матрицам сравнений.1.// Кибернетика и системный анализ. 1994. - № 5. - С. 3 - 23.

57. РоммЯ.Е. Параллельная сортировка слиянием по матрицам сравнений.1. // Кибернетика и системный анализ. 1995. - № 4. - С. 13 - 37.

58. Уилкинсон Д.Х. Алгебраическая проблема собственных значений. М.: Наука, 1970. - 564 с.

59. Гантмахер Ф.Р. Теория матриц: 5-е изд. М.: Физматлит, 2004. - 560 с.

60. Баскаков С.И. Радиотехнические цепи и сигналы. М.: Высшая школа, 1983.-214с.

61. Гоноровский И.С. Радиотехнические цепи и сигналы М.: Радио и связь, 1986. - 408 с.

62. Фаддеев Д.К., ФаддееваВ.Н. Вычислительные методы линейной алгебры. СПб: Лань, 2002. - 736 с.

63. Форсайт Д.Э., Малькольм М., Моулер К. Машинные методы математических вычислений. -М.: Мир, 1980. 279 с.

64. РоммЯ.Е., Лабинцева A.A. Идентификация нулей и экстремумов разностных решений уравнений в частных производных на основе сортировки / ТГПИ. Таганрог, 2007. - 30 с. Деп. В ВИНИТИ 20. 02. 2007, № 154 - В2007.

65. Ромм Я.Е. Локализация и устойчивое вычисление нулей многочлена на основе сортировки. I // Кибернетика и системный анализ. 2007. - № 1. - С. 165 — 183.

66. Ромм Я.Е. Локализация и устойчивое вычисление нулей многочлена на основе сортировки. II // Кибернетика и системный анализ. 2007. - № 2. - С. 161 -175.

67. Маркушевич А.И., Маркушевич Л.А. Введение в теорию аналитических функций. М.: Просвещение, 1997. 320 с.

68. ГалисеевГ.В. Программирование в среде Delphi 7. Самоучитель. М.: Диалектика, 2003. - 288 с.

69. Фаронов B.B. Delphi 2005. Язык, среда, разработка приложений. СПб.: Питер, 2005. - 560 с.

70. Фаддеев Д.К. Лекции по алгебре. М.: Наука, 1984. - 416 с.

71. Солодовников В.И. Верхние оценки сложности решения систем линейных уравнений. В кн.: Теория сложности вычислений. I: Записки научных семинаров ЛОМИ АН СССР.-Л., 1982, т. 118.-С. 159- 187.

72. Демидович Б.П. Лекции по математической теории устойчивости. М.: Наука, 1967.-472 с.

73. Филлипс Ч., Харбор Р. Системы управления с обратной связью. -М.: Лаборатория Базовых Знаний. 2001. - 615 с.

74. Фихтенгольц Г.М. Курс дифференциального и интегрального исчисления. Т 1. -М.: Наука, 1969. 608 с.

75. Ишлинского А.Ю. Прикладные задачи механики. Кн.1. М.: Наука. -1986. - 356 е.; Кн.2. - М.: Наука. - 1986. - 412 с.

76. Журавлёв В.Ф. Об одной форме уравнений движения симметричного твёрдого тела // Изв. АН СССР. Механ. твёрд, тела. 1986. - №3. - С. 5 - 11.

77. Каменков Г.В. Избранные труды. Т.2. Устойчивость и колебания нелинейных систем. М.: Наука. - 1972. - 218 с.

78. Кузьмин П.А. Устойчивость круговой формы гибкой нити, имеющей счётное множество степеней свободы // Тр. Казанск. авиац. ин-та. — Вып.22. — 1949. С. 3 - 15.

79. Меркин Д.Р. Введение в теорию устойчивости движения. М.: Наука. -1971.-312 с.

80. Четаев Н.Г. Устойчивость движения. Работы по аналитической механике. М.: Изд-во АН СССР. - 1962. - 534 с.