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

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

ООЗОВУ424

Кокорев Сергей Алексеевич

РАЗРАБОТКА И ИССЛЕДОВАНИЕ МЕТОДА ОДНОВРЕМЕННОЙ ОЦЕНКИ КОРНЕЙ ХАРАКТЕРИСТИЧЕСКОГО УРАВНЕНИЯ ЛИНЕЙНОЙ

СИСТЕМЫ

Специальность 05.13.01 - "Системный анализ, управление и обработка информации (энергетика, приборостроение, информатика, производственные

процессы)"

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Москва - 2006

003067424

Работа выполнена в Московском энергетическом институте (техническом университете) на кафедре Управления и информатики.

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

доктор технических наук, профессор Колосов Олег Сергеевич доктор технических наук, профессор Горицкий Юрий Александрович

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

кандидат технических наук, доцент Тягунов Олег Аркадьевич

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

кафедра Кибернетики

Московского инженерно-физического института (Государственного университета) (МИФИ (ГУ)) Защита состоится 15 марта 2007 г. в 16 час. 00 мин. на заседании диссертационного совета Д 212.157.08 при Московском энергетическом институте (техническом университете) по адресу:

г. Москва, ул. Красноказарменная, дом 14 в Малом актовом зале МЭИ

С диссертацией можно ознакомиться в библиотеке МЭИ (ТУ)

Отзывы на автореферат в двух экземплярах, заверенные печатью, просим направлять по адресу: 111250, г. Москва, ул. Красноказарменная, д. 14, Ученый совет МЭИ (ТУ).

Автореферат разослан ,ЧМ Л_2007 г.

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

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

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

Основные задачи работы:

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

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

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

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

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

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

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

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

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

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

Апробация работы проведена на заседании семинара по теории автоматического управления кафедры управления и информатики ГОУ ВПО "Московский энергетический институт (технический университет)", также материалы диссертации изложены на одиннадцатой международной научно-технической конференции студентов и аспирантов "Радиоэлектроника, электротехника и энергетика", Москва, 2005 г. и на международных семинарах "Современные технологии в задачах управления, автоматики и обработки информации", Алушта, 2005 г. Результаты работы используются при чтении лекций по курсу: "Системы автоматизации и управления".

Структура и объем диссертации. Диссертация состоит из введения, 5 глав, заключения, списка источников и двух приложений. Диссертация изложена на 129 страницах машинописного текста без учета приложений, иллюстрирована 9 таблицами и 18 рисунками. В списке литературы приведено 67 источников, из них 53 отечественных и 14 иностранных.

Публикации. По теме диссертации опубликовано 3 печатные работы, одна из которых - в реферируемом ВАК журнале.

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

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

1. Методы решения систем нелинейных уравнений общего вида.

2. Специализированные методы решения полиномиальных уравнений.

Среди этих методов представлены одномерные процедуры,

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

1. Одновременно находит все корни полинома;

2. Не требует начальных приближений.

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

шага. Таким образом можно сократить количество вычислений на каждом шаге.

Во второй главе рассматривается основная идея метода, при этом изложены нижеследующие положения.

В работе используется следующая форма записи полинома:

/&>)=£«'*'. о)

(=0

при этом предполагается, что ап=\.

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

|=и=1

где р,.¡ = \,п - корни уравнения (1) с противоположным знаком, е[*,п-0-*)] ДЛЯ *е [!,./], /;,1</,,2<- < ¡¡,}, Причем (/,->ь ,/,>у)*(/т,Ь ДЛЯ 1*т.

Матрица = называется таблицей индексов для коэффициента

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

На основе формулы (2) можно построить критерий оптимизации, удовлетворяющий следующим условиям:

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

2. Критерий должен принимать наименьшее значение в точке

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

<=о

где к,(р) = -

Ф)=1(*2о>)+в?(4

1=0

, \ , 1ш(а,(р)11ш(а,)=о

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

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

Принимая во внимание формулы (2), (3) и (4), задачу оптимизации можно сформулировать следующим образом:

с(/>)-> иш (5)

реЫ2"

Так как поиск в общем случае осуществляется для 2и значений, то есть для п действительных частей и для п мнимых частей корней (1), то поиск производится в пространстве я2", при этом значение критерия всегда является вещественным числом.

Исследование поведения критерия показало, что задача оптимизации (5) имеет овражный характер, что можно достаточно легко продемонстрировать, построив на плоскости линии уровня критерия для случая л = 2 и вещественных корней, либо линии уровня в разрезе двух переменных. Для случая полинома пятого порядка с комплексными корнями такой срез показан на рис. 1.

Рис. 1. Поведение критерия для случая полинома пятого порядка в разрезе двух составляющих вектора переменных.

В третьей главе исследуются возможности существующих методов для решения задачи оптимизации (5).

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

В работе для оптимизации полученного критерия был использован метод Левенберга-Марквардта, который на данный момент является одним из самых быстрых квазиньютоновских методов оптимизации. Для построения численной процедуры по этому методу требуется вычислять значения критерия и его якобиан в произвольной точке. Такие вычисления производятся по аналитическим формулам с помощью таблиц индексов для коэффициентов полинома, частных производных коэффициентов полинома по корням, а также матриц комплексных произведений. Последние позволяют хранить в виде тернарной матрицы (каждое значение элемента матрицы выбирается из множества {-1,0,1}) аналитическую формулу произведения т комплексных чисел.

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

ЛП.

и-1

ЭА,(/>)

и-1

ЭС4

/=0

дч

1=О

ёск

дек ' 8(1к

и-1

и-1

(=0

Щ

1=0

дф) Щ

(7)

*0

дек

1Цо,) № 5Ке(д,(р))

а/*

Ке(в,) = 0

Э1т(а,(р)) |т(а ,

51тУ^)Лт(аЛ=0

, где

(8)

* о

ЭЙО>).

1т(а,] 5Л

ее*

Фа

од

а 1тп(аг(^)> =, Г) а1т(д,0>)) = ¿чО?) | _

5с/1 I Фа J' Щ

сРк

(9.1)

(9.2)

Правильность использования формул (9.1) и (9.2) в работе доказывается с помощью леммы, которая формулируется следующим образом:

Лемма. Пусть имеется произведение нескольких комплексных чисел 2 = П2" где А ' некое множество целых чисел, используемых как индексы в

/6-4

произведении. Тогда аке/г\=яе

еяеф

——г—л = - 1тп

37.

д\т[г)

= 1т

дг

д 1т (2 51т(:

= ЯеИ

Где JeA.

Теоретически, изменение формул расчета с помощью соотношений (9.1) и (9.2) не дает никакого существенного изменения самого процесса расчета, однако на практике применение этих соотношений позволяет рассчитывать необходимые частные производные, пользуясь аналогами таблиц индексов для коэффициентов, которые называются таблицами индексов для производных. Это позволяет рассчитывать составляющие вектора градиента

(6) и, соответственно, якобиана для метода Левенберга-Марквардта, по аналитическим формулам.

Исследование поведения метода Левенберга-Марквардта показало, что последний достаточно быстро сходится для рассматриваемого критерия, в особенности, если начальная точка, из которой запускается численный процесс оптимизации находится в некоторой окрестности одной из точек минимума. Такая окрестность характеризуется довольно медленным изменением критерия оптимизации по всем направлениям. Для того, чтобы задать такую точку, используется модификация метода Мадсена-Рейда, заключающаяся в том, что в отличие от оригинального метода, процедура уточнения корней (обычно производящаяся по методу Ньютона-Рапсона) запускается только после оценки всех значений корней, и вместо стандартной одномерной процедуры, используется рассмотренная многомерная процедура минимизации по методу Левенберга-Маквардта.

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

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

{п-1

«и

•ли-2 | 2

,'Н

1 . 1

2"'г

, (10)

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

И

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

= —т имеет место явление быстрого переполнения стека, поэтому в «'(л-и/

работе предлагается рассчитывать сочетания итеративно по формуле с!п = Также, среди оптимизирующих вычислительный процесс

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

производных можно воспользоваться соотношениями ——(si^ _ djmM?)) и

°Ск Sd/ç

s Re(a,(p)) = ô\m(a,(p)) ^ КОТОрЫе вытекают из рассмотрения формул (9.1) и (9.2) и

ddfr Bcjç

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

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

1. По действительной части (декременту затухания)

2. По мнимой части (частоте колебаний)

3. Комбинированный (сочетающий в себе первые два, при этом сперва применяется способ сортировки по декременту затухания, а затем в рамках получившихся групп - по частоте колебаний).

Группировка корней показана на рис. 2.

(\ • группа 2 ( Г . / р • +J' группа 1 группа1 гтппа\1.( \ +

У и ° - 1 ( 1 и °

Рис. 2 Группировка корней: сперва по декременту затухания, а затем но частоте

колебаний

Также метод применим (как это уже было сказано выше) для построения корневого годографа. В частности, в работе рассмотрен пример построения корневого годографа для системы автоматического управления лентопротяжным механизмом в устройстве памяти последовательного доступа. Указано, что при построении такого годографа метод собственных значений выполняет на каждом шаге около з«3 операций умножения (которые занимают большую часть времени вычислительного процесса), в то время как предлагаемый метод выполняет около 2п3 операций (из расчета 4-х итераций уточнения корней по методу Левенберга-Маквардта), что позволяет сократить время построения корневого годографа. Также подобная вычислительная процедура может применяться для целей адаптивного регулирования в линейной системе автоматического управления для вычисления корней системы "в темпе с объектом". При этом следует выбирать временной интервал расчета таким, чтобы новые значения корней попадали в ранее упомянутую "почти плоскую окрестность" точки экстремума на предыдущем шаге. Это гарантирует быструю сходимость для процедуры уточнения корней.

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

р10 + 10р9 + 45р8 + 120р7 + 210р6 + 252/+2ю/+120р3 + 45р2+10р + 1 = 0 были рассчитаны по предложенной методике и по методу собственных значений (использовалась реализация математического пакета МаШСас! 2000).

Были получены следующие результаты:

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

2. Метод собственных значений выдал следующий результат:

-1.054 -1 043-70.032 -I 043 + /0 032 -1.015-70 051 -1 015 + 70 051 -0 983 - 70 049 -0.983 + 70.049 -0.958-70 03 -0 958 + 7О.ОЗ -0 949

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

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

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

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

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

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

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

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

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

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

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

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

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

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

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

СПИСОК РАБОТ, ОПУБЛИКОВАННЫХ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Кокорев С.А. Численный метод определения корней характеристического уравнения для жестких систем автоматического управления//Х1 Междунар. науч.-техн. конф. студентов и аспирантов "Радиоэлектроника, электротехника и энергетика": Тез. докл. - М.: МЭИ, 2005 - Т.1. - с. 401-402.

2. Кокорев С.А. Численный метод определения всех корней полиномиального уравнения произвольного порядка//Известия ТулГУ. Сер. Вычислительная техника. Информационные технологии. Системы управления. - Тула: ТулГУ, 2005 - Вып. 4 - с. 27-33.

3. Кокорев С.А. Численный метод поиска корней характеристических уравнений жестких систем//Х1У Международный научно-технический семинар "Современные технологии в задачах управления, автоматики и обработки информации": Тез. докл. - Алушта - Самара: Самарский государственный аэрокосмический университет, 2005г. - с. 108.

Содержание.

Введение.

Глава 1. Обзор методов анализа устойчивости жестких ЛСАУ.

Введение.

1.1 Некоторые аспекты анализа ЛСАУ.

1.1.1 Необходимые и достаточные условия устойчивости ЛСАУ. Характеристическое уравнение ЛСАУ.

1.1.2 Коррекция ЛСАУ.

1.1.3 Жесткие дифференциальные уравнения. Понятие жесткости ЛСАУ.

1.2 Решение характеристического уравнения системы.

1.2.1 Общие обозначения.

1.2.2 Методы нахождения корней нелинейных уравнений.

1.2.3 Метод Лагерра.

1.2.4 Метод собственных значений.

1.2.5 Метод Дженкинса-Трауба.

1.2.6 Краткий обзор остальных методов.

Выводы.

Глава 2. Основная идея метода.

Введение.

2.1 Использование формул Виета для оценки коэффициентов полинома через корни

2.1.1 Традиционная форма записи формул Виета.

2.1.2 Модификация формул Виета в виде компактной итерационной формулы. Понятие таблиц индексов.

2.1.3 Численный пример. Запись формул Виета и таблицы индексов.

2.2 Случай комплексных корней и коэффициентов.

2.2.1 Рассмотрение составляющих комплексных корней и коэффициентов. Понятие матриц комплексных произведений.

2.2.2 Численный пример. Запись формул Виета с учетом комплексной природы коэффициентов и корней.

2.3 Формулировка задачи оптимизации для нахождения корней полиномиальных уравнений.

2.3.1 Требования, предъявляемые к критерию оптимизации.

2.3.2 Формирование критерия оптимизации. Окончательная запись задачи оптимизации.

2.3.3 Овражный характер критерия оптимизации.

2.3.4 Численный пример. Формирование критерия. Исследование области экстремума.

Выводы.

Глава 3. Использование методов поиска для решения поставленной задачи оптимизации43 Введение.

3.1 Метод подвода рабочей точки в область экстремума.

3.1.1 Трудности применения методов спуска для оптимизации сформулированного критерия.

3.1.2 Модификация градиентного метода для случая овражных функций. Сходимость метода. Задание начальных условий.

3.1.3 Вычисление градиента по аналитическим формулам. Введение дополнительных таблиц индексов.

3.1.4 Использование дробления шага.

3.1.5 Численный пример. Подвод рабочей точки в область экстремума.

3.2 Дальнейшая оптимизация критерия. Нахождение значений корней полинома.

3.2.1 Различные способы оптимизации в области экстремума.

3.2.2 Метод Левенберга-Марквардта и его применение для рассматриваемой задачи.

3.2.3 Численный пример. Результат работы метода Левенберга-Марквардта.

Выводы.

Глава 4. Некоторые аспекты реализации предлагаемой методики.

Введение.

4.1 Алгоритмы генерации статической информации.

4.1.1 Генерация таблиц индексов для коэффициентов полинома.

4.1.2 Генерация матриц комплексных произведений.

4.1.3 Генерация таблиц индексов для производных.

4.1.4 Численный пример. Генерация статической информации.

4.2 Расчет корней полинома.

4.2.1 Расчет значения критерия.

4.2.2 Расчет градиента в заданной точке.

4.2.3 Генерация релаксационной последовательности.

4.2.4 Применение метода Левенберга-Марквардта.

4.2.5 Расчет сочетаний.

4.2.6 Численный пример. Первый такт генерации релаксационной последовательности.

Выводы.

Глава 5. Использование предложенного метода и результатов его работы.

Введение.

5.1 Разделение свободного движения ЛСАУ.

5.1.1 Способы разделения свободного движения ЛСАУ.

5.1.2 Алгоритм разделения свободного движения ЛСАУ по декременту затухания. Реализация алгоритма.

5.1.3 Численный пример. Разделение свободного движения ЛСАУ с постоянными коэффициентами.

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

5.2.1 Проблемы сходимости метода.

5.2.2 Начальные условия для метода подвода рабочей точки в область экстремума.

5.2.3 Модификация предложенной методики. Улучшение сходимости.

5.2.4 Применение метода для целей адаптивного регулирования.

5.2.5 Численный пример 1. Поиск корней полинома шестого порядка.

5.2.6 Численный пример 2. Система управления лентопротяжным механизмом в устройстве памяти последовательного доступа.

5.3 Применение методики для решения задачи собственных значений.

5.3.1 Получение характеристического полинома матрицы.

5.3.2 Решение характеристического уравнения.

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

Выводы.

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

При анализе линейных систем автоматического управления, а также при синтезе регуляторов для них, часто возникает задача поиска корней характеристического уравнения исследуемой системы [53], причем левая часть уравнения представляет собой алгебраический полином, а правая равна нулю. Особенный же интерес при анализе вызывают так называемые "жесткие" системы, в которых можно выделить несколько групп корней и рассматривать движение системы с точки зрения анализа получившихся групп. На данный момент наука располагает достаточно большим количеством методов решения полиномиальных уравнений [17, 18, 28, 42, 65], но применение их для жестких систем иногда затруднительно из-за различия в значениях корней, принадлежащих разным группам. Среди имеющихся методов можно выделить методы, которые достаточно ясны для понимания, однако неэффективны, а также методы, которые считаются достаточно эффективными, но при этом численная процедура, соответствующая им, является достаточно сложной для освоения и реализации. В частности, одним из наиболее эффективных методов на сегодняшний день считается метод Дженкинса-Трауба [64], но при этом его описание достаточно сложно найти даже в книгах, описывающих большинство популярных на сегодняшний день численных методов. Например, в книге [65], являющейся основным учебником и руководством по программированию численных методов в США и Западной Европе, метод Дженкинса-Трауба только упоминается, а подробное описание его не приводится из-за слишком большой сложности этого метода для понимания. В некоторых случаях, упомянутый метод, а также наиболее популярный сейчас метод собственных значений, являются неэффективными (в смысле сходимости и быстродействия) по сравнению с более простыми методами, например, с комбинацией методик Мадсена-Рейда и Мюллера или Ньютона [64, 67]. Также есть методы, предложенные в различных источниках, но не исследованные с точки зрения эффективности, например, комбинация методов Мадсена-Рейда и наискорейшего спуска [18]. В данной работе будет предложена достаточно простая и эффективная численная методика [30-32] решения полиномиальных уравнений, основанная на переформулировке задачи отыскания корней в задачу оптимизации, использующая как аналитические выражения (формулы Виета), так и численные алгоритмы.

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

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

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

Подобные расчеты могут понадобиться для анализа систем с изменяющимися во времени коэффициентами, а также для пошагового построения корневого годографа [И, 13, 14]. Большинство методов решения полиномиальных уравнений, применяемых на практике в настоящее время, рассчитаны на то, что все коэффициенты полинома являются действительными числами. Однако следует заметить, что в некоторых ситуациях при проектировании систем автоматического управления (см., например, [11,33]) приходится сталкиваться с комплексными коэффициентами и вычислять корни. Предлагаемый метод рассчитан на общую формулировку задачи вычисления корней полиномов, то есть коэффициенты и корни полинома могут быть как действительными, так и комплексными.

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

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

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

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

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

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

Структура диссертационной работы.

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

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

В главе 3 рассматривается возможность применения различных методов для решения поставленной в главе 2 задачи оптимизации, предлагается аналитический метод расчета градиента критерия в заданной точке. Описывается применение методов градиента и Левенберга-Марквардта для оптимизации целевой функции, причем особое внимание уделяется ее овражному характеру.

В главе 4 предлагаются алгоритмы и реализации новой численной методики. В разделах этой главы также имеются модификации предлагаемых алгоритмов с целью повышения скорости их работы на вычислительной технике, например, предлагается замена деления умножением и быстрый расчет сочетаний. Приводятся соображения, исходя из которых можно делать выводы о постоянном хранении так называемой "статической информации" в оперативной памяти во время вычислений, а также и постоянном хранении этой информации в ППЗУ компьютера для использования в дальнейших вычислениях. Также приводятся исходные тексты реализации предложенных алгоритмов на языках С++ и С#.

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

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

Выводы

1) Имея корни характеристического уравнения системы можно разделять ее свободное движение на составляющие по группам с помощью алгоритма, предложенного в разделах 5.1.1-5.1.2.

2) Сходимость метода подвода рабочей точки к области экстремума зависит от начальных условий, которые можно выбирать, пользуясь правилами, изложенными в разделе 5.2.2.

3) Начальные приближения для метода Левенберга-Марквардта также можно получить пользуясь методикой, представленной в разделе 5.2.3. Более того, эта методика является предпочтительной, так как она повышает скорость работы всего алгоритма в целом.

4) Предложенной методикой можно пользоваться и для целей задач адаптивного управления, как это предложено в разделе 5.2.4.

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

Заключение

В диссертации получены следующие существенные результаты:

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

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

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

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

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

6. Предложены процедуры, оптимизирующие вычислительный процесс.

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

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

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

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

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

1. Аоки М. Введение в методы оптимизации. М.: Наука,1977.

2. Аттетков А. В.,Галкин С. В.,Зарубин В. С. Методы оптимизации. Серия: Математика в техническом университете. М.: Издательство МГТУ им. Н. Э. Баумана, 2001.

3. Ахмеров P.P. Методы оптимизации гладких функций. Режим доступа http://www.ict.nsc.ru/rus/textbooks/akhmerov/mo/index.ht ml 12.03.2006.

4. Ашманов С.А., Тимохов A.B. Теория оптимизации в задачах и упражнениях. М.: Наука, 1991.

5. Базара М., Шетти К. Нелинейное программирование. Теория и алгоритмы. М.: Мир, 1982.

6. Банди Б. Методы оптимизации. Вводный курс. М.: Радио и связь, 1988.

7. Батищев Д.И. Поисковые методы оптимального проектирования. М.: Сов. Радио, 1975.

8. Бахвалов Н.С. Численные методы. М.: Наука, 1973.

9. Бендриков Г.А., Теодорчик К.Ф. Траектории корней линейных автоматизированных систем. М.: Наука, 1964.

10. Бесекерский В.А. Попов Е.П. Теория систем автоматического управления. М.: Наука, 1972.

11. Биттар А.Б. Разработка корневых методов анализа и синтеза двусвязных систем с идентичными каналами и антисимметричными перекрестными связями. Диссертация на соискание ученой степени кандидата технических наук М.:МЭИ, 1997.

12. Биттар А.Б. Рекуррентный алгоритм оценки корней характеристического уравнения для "жестких" систем. Тезисыдокладов международной конференции "Информационные средства и технологии". МФИ-95. М., 1995.

13. Биттар А.Б. Колосов О.С. Корневые методы синтеза двусвязных систем управления//Вестник МЭИ №6 1996, с. 127-134 -М.: МЭИ, 1996.

14. Биттар А.Б. Колосов О.С. Синтез двусвязных систем управления корневыми методами. Тезисы докладов международной конференции "Информационные средства и технологии". МФИ-96. -М., 1996.

15. Булгаков Б.В. Прикладная теория гироскопов -М.:Гостехиздат, 1939.

16. Васильев Ф.П. Методы оптимизации. М.: Факториал пресс, 2002.

17. Вержбицкий В.М. Основы численных методов. Учебник для вузов. М.: ВШ, 2002.

18. Воеводин В. В.,Павленко О. А. Модифицированный метод наискорейшего спуска для определения всех корней полинома//Численный анализ на ФОРТРАНЕ, вып. 27. М.: МГУ, 1980.

19. Габасов Р., Кириллова Ф.М. Методы оптимизации. -Минск: Изд-во БГУ, 1981.

20. Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. -М.: Мир, 1985.

21. Гроссман К., Каплан A.A. Нелинейное программирование на основе безусловной оптимизации. Новосибирск: Наука, 1981.

22. Деннис Дж., Шнабель Р. Численные методы безусловной оптимизации и решения нелинейных уравнений. М.: Мир, 1988.

23. Евтушенко Ю.Г. Методы решения экстремальных задач и их применение в системах оптимизации. М.: Наука, 1982.

24. Жиглявский A.A., Жилинскас А. Г. Методы поиска глобального экстремума. М.: Наука, 1991.

25. Зангвилл У.И. Нелинейное программирование. М.: Сов. радио, 1973.

26. Измаилов А.Ф., Солодов М.В. Численные методы оптимизации: Учеб. пособие. -М.: ФИЗМАТЛИТ, 2005.

27. Казамаров A.A., Палатников A.A., Роднянский Л. О. Динамика двумерных систем автоматического управления. М.: Наука, 1967.

28. Карманов В.Г. Математическое программирование. М.: Наука, 1975.

29. Каханер Д., Моулер К., Нэш С. Численные методы и программное обеспечение. М.: Мир, 1998.

30. Кокорев С.А. Численный метод определения всех корней полиномиального уравнения произвольного порядка//Известия ТулГУ. Сер. Вычислительная техника. Информационные технологии. Системы управления. Тула: ТулГУ, 2005 - Вып. 4-е. 27-33.

31. Кокорев С.А. Численный метод поиска корней характеристических уравнений жестких систем//Труды XIV Международного научно-технического семинара. Алушта 2005г. с. 108.

32. Красовский A.A. О двухканальных системах автоматического регулирования с антисимметричными перекрестными связями.//Автоматика и телемеханика, т. XVIII, №2, 1957.

33. Лесин В. В., Лисовец Ю.П. Основы методов оптимизации. -М.: Изд-во МАИ, 1995.

34. Любчак В.А., Остривная Л.Г., Пероганич Е.М. Методы оптимизации. Режим доступа http://dl.sumdu.edu.ua/mo/ 12.03.2006.

35. Малахов H.A., Нигай P.M. Численно-аналитический метод моделирования жестких систем//Известия ВУЗов №8, с.5. М.: Приборостроение, 1991.

36. Мину М. Математическое программирование. Теория и алгоритмы. М.: Наука, 1990.

37. Михеев С.Е. Нелинейные методы в оптимизации. СПб.: Издательство Санкт-Петербургского университета, 2001.

38. Неймарк Ю.И. Устойчивость линеаризованных систем. ЛКВВИА, 1949.

39. Пантелеев A.B. Методы оптимизации в примерах и задачах: Учеб. пособие/Пантелеев A.B., Летова Т.А. 2-е изд., исправл. - М.: Высшая школа., 2005.

40. Парлетт Б. Симметричная проблема собственных значений. М.: Мир, 1983.

41. Пирумов У.Г. Численные методы: Учеб. пособие для студ. втузов. 2-е изд., перераб. и доп. - М.:Дрофа, 2003.

42. Пшеничный Б.Н., Данилин Ю.М. Численные методы в экстремальных задачах. М.: Наука, 1975.

43. Скворцов Л. М., Федосов Б. Т., Об алгебраических критериях В. С. Воронова устойчивости и качества линейных систем. Режим доступа http://model.exponenta.ru/bt/bt 00118.html 12.03.2006.

44. Стронгин Р.Г. Численные методы в многоэкстремальных заадчах. М.: Наука, 1978.

45. Струченко В.И. Методы оптимизации. М.: Экзамен, 2005.

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

47. Трифонов А. Г. Оптимизация методом наименьших квадратов. Режим доступа http://matlab.exponenta.ru/optimiz/bookl/13.php 12.03.2006.

48. Удерман Э.Г. Метод корневого годографа в теории автоматического управления. -М.: Госэнергоиздат, 1963.

49. Хайрер Э., Ваннер Г. Решение обыкновенных дифференциальных уравнений. Жесткие и дифференциально-алгебраические задачи./ Пер. с англ. М.: Мир, 1999.

50. Химмельблау Д. Прикладное нелинейное программирование. М.: Мир, 1975.

51. Черноруцкий И.Г. Методы оптимизации. СПб.: Изд-во СПбГТУ, 1998.

52. Черноруцкий И.Г. Методы оптимизации в теории управления: Учебное пособие. СПб.: Питер, 2004.

53. Bonnans J. F., Gilbert J. Ch., Lemarechal C., Sagastizabal C. Numerical optimization. Theoretical and practical aspects. Berlin: Springer-Verlag, 2003.

54. C. Sydney Burrus, James W. Fox, Gary A. Sitton, Sven Treitel. Horner's Method for Evaluating and Deflating Polynomials. Режим доступа dsp.rice.edu/software/FVHDP/horner2.pdf 09.04.2006.

55. D. Calvetti, L. Reichel, F. Sgallary A modified companion matrix method based on Newton polynomials. Режим доступа www.math.kent.edu/~reichel/publications/mcm.ps 09.04.2006.

56. В. Dumitresku, I. Tsabu A Comparison of Deflation Algorithms Режим доступа www.cs.tut.fi/~tabus/NOKIAPS/BogdanCSCS.ps 09.04.2006.

57. Walter E. Evans Control System Dynamics, Mc Graw Hill -N.Y., London, Toronto, 1954.

58. Fletcher R. Practical methods of optimization. V. 1. Unconstrainted optimization. Chichester, New York, Brisbane, Toronto: John Wiley, 1980.

59. Lance G. N., Numerical Methods for High Speed Computers. -London: ILIFFE&SONS Ltd, 1960.

60. M. Lang, B.-C. Frenzel Polynomial Root Finding. Режим доступаhttp://citeseer.ist.psu.edu/rd/23191217%2C39671 %2C 1 %2C0.25%2CDow nload/http%3AqSqqSqjazz.rice.eduqSqpublicationsqSqpubqSqSPLet-roots.ps 09.04.2006.

61. A. Leykin, J. Verschelde, A. Zhao. High-Order Deflation for Polynomial Systems with Isolated Singular Solutions. Режим доступа http://arxiv.org/PScache/math/pdf/0602/0602031 .pdf.

62. A. Leykin, J. Verschelde, A. Zhao. Newton's method with deflation for isolated singularities of polynomial systems. Режим доступа http://arxiv.org/PScache/math/pdf/0408/0408419.pdf09.04.2006.

63. Mekwi W. R. Iterative Methods for Roots of Polynomials, M. Sc. Thesis, Oxford: Trinity, 2001.

64. William H. Press, Saul A. Teukolski, William T. Vetterling, Brian P. Flannery. Numerical Recipes in C. Art of technical computing 2nd ed. - Cambrige: CUP, 1992.

65. A. Ranganathan The Levenberg-Marquardt Algorithm. Режим доступа www-static.cc.gatech.edu/~ananth/docs/lmtut.pdf09.04.2006.

66. Schmidt C.E., Rabiner L. R. A Study of techniques for finding the zeros of linear phase FIR digital filters//IEEE transactions on acoustics, speech, and signal processing, February 1977.