Автоматика и телемеханика, № 12, 2012
© 2012 г. О.О. ВАСИЛЬЕВ, канд. техн. наук (Институт проблем управления им. В.А. Трапезникова РАН, Москва, Российский государственный университет нефти и газа им. И.М. Губкина, Москва)
ИССЛЕДОВАНИЕ ^-РАЗБИЕНИЙ МЕТОДАМИ ВЫЧИСЛИТЕЛЬНОЙ ВЕЩЕСТВЕННОЙ АЛГЕБРАИЧЕСКОЙ ГЕОМЕТРИИ1
Предложены новые методы исследования Д-разбиения методами вычислительной вещественной алгебраической геометрии. Дана оценка числа областей Д-разбиения для полиномиальных параметрических семейств многочленов и матриц. В некоторых случаях предложенная техника, связанная с построением базисов Грёбнера и цилиндрического разложения, оказывается более точной, чем традиционная. Используется система символьных вычислений Maple v.14, в частности, входящий в ее состав пакет RegularChains.
1. Введение
Под линейной непрерывной системой будет пониматься линейное дифференциальное уравнение с постоянными коэффициентами
х(ь) = Ах(г),
где А - некоторая комплексная(вещественная) п х п-матрица. Аналогично, под линейной дискретной системой будет пониматься линейное разностное уравнение с постоянными коэффициентами
х(Ь + 1) = Ах(Ь),
где А - некоторая комплексная(вещественная) п х п-матрица.
Одной из классических задач линейной теории управления является задача поиска областей устойчивости для линейной системы, зависящей от параметров. Она может быть сформулирована следующим образом. Пусть задан многочлен Р(в, к) с комплексными (в частности, быть может, вещественными) коэффициентами, полиномиально зависящий от вектора вещественных параметров к = (к\, ...,к1) е К = Мг. Комплексные параметры можно рассматривать как пары вещественных вида а + jb. Многочлен Р(в, к) обычно предполагается характеристическим многочленом некоторой линейной системы. В этом случае к понимается как неопределенность или же как параметры регулятора.
Необходимо найти такие области и в пространстве параметров К, что Р(в, к) будет устойчивым многочленом в смысле систем дискретного или непрерывного времени для любых к е и.
1 Работа выполнена при финансовой поддержке Российского фонда фундаментальных исследований (проект №11-08-00223-а "Методы 11-оптимизации в теории управления").
Напомним, что многочлен называется устойчивым в смысле непрерывного времени (гурвицевым), если вещественные части всех его корней отрицательны; устойчивым в смысле дискретного времени (шуровским) тогда и только тогда, когда все его корни по модулю меньше единицы. Автономная система непрерывного(дискретного) времени устойчива тогда и только тогда, когда ее характеристический многочлен устойчив в смысле непрерыв-ного(дискретного) времени.
Ясно, что задачи поиска областей устойчивости для дискретного и непрерывного времени в существенной степени эквивалентны. Действительно, многочлен Р (г) шуровский тогда и только тогда, когда многочлен (в — 1)с1е§рР(|±1) гурвицев. Тем самым можно перейти к рассмотрению случая систем непрерывного времени, что и будет происходить во всех случаях, когда иное не оговорено специально.
В теории управления наиболее важными оказываются два случая, а именно: случай характеристического многочлена, аффинно зависящего от вектора параметров к, и случай аффинной зависимости матрицы исходной линейной системы от вектора параметров к. В последнем случае многочлен Р(в, к) при-
Одним из методов исследования данного вопроса является метод ^-раз-биения, основанный на разбиении пространства параметров на связные области, содержащие одинаковое число корней многочлена с заданным знаком вещественной части (области инвариантности корней или области ^-разбиения).
Ясно, что границей этих областей служит гиперповерхность в К, параметризованная уравнениями
а также, быть может, гиперповерхность, заданная уравнением |а,еёр(к)\ = 0, где а,^ р - старший член многочлена Р. Основная идея метода впервые, по-видимому, появилась у И. Вышнеградского [1], а сам метод впервые подробно рассмотрен Ю.И. Неймарком [2, 3]. С современным состоянием метода можно ознакомиться по работам [4, 5].
Основная идея предлагаемой работы состоит в применении к данной задаче методов вычислительной вещественной алгебраической геометрии.
Согласно теореме Тарского-Зайденберга [6, § 2.3], проблема описания всех областей ^-разбиения, равно как и всех стабильных областей, алгоритмически разрешима. То есть доказано, что существует процедура, которая за конечное число шагов выдает явное описание всех областей ^-разбиения в виде совокупностей систем полиномиальных уравнений и неравенств, а также выдает пробные точки из этих областей. Тем не менее конкретные алгоритмы автоматического точного исследования систем вещественных полиномиальных уравнений и неравенств стали разрабатываться лишь в последние десятилетия [7] и лишь в последнее время начали появляться в составе систем компьютерной алгебры общего назначения (так, пакет КедЫатСНатв для символьных вычислений с полиномиальными уравнениями и неравенствами
(1)
ЩР(]ш, к)) = 0, Ъ(Рк)) = 0,
появился в системе компьютерной алгебры Maple лишь в 2005 г. и продолжает крайне активно развиваться). Однако для доказательства результатов достаточно использовать лишь классические теоремы Безу (в том числе в многомерном случае) и Харнака. Кроме того, в вычислительном исследовании используются некоторые классические результаты вычислительной алгебраической геометрии в варианте, связанном с теорией базисов Грёбнера, а также один более современный - построение частичного цилиндрического алгебраического разложения [7]. Применение этих методов к задачам изучения множества стабильных точек считается нерешенной проблемой в монографии [8]. Близкий к рассматриваемому метод получения границы Д-разбиения предложен в работе А.Д. Брюно [9], где предлагается использовать результанты для изучения границы Д-разбиения.
Уравнения (1) задают пересечение двух гиперповерхностей в K. Методами теории исключения в варианте теории базисов Грёбнера или же в варианте результантов можно получить явные уравнения минимальной вещественной алгебраической гиперповерхности, содержащей множество, параметризованное уравнениями (1). Количество же областей можно оценить при помощи результатов [10].
Затем в случае dim K = 2, когда граница Д-разбиения оказывается фрагментом аффинной вещественной плоской алгебраической кривой, при помощи теорем Харнака и Безу можно дать точную верхнюю оценку числа областей, на которые приводимая и особая кривая может делить аффинную плоскость.
Во втором разделе, на основании изложенной выше техники, получена оценка числа областей Д-разбиения. Отдельный подраздел посвящен краткому введению в теорию базисов Грёбнера, которые применяются в вычислительных методах рассмотренных в данной работе.
Третий раздел посвящен вычислительному исследованию ряда конкретных систем, рассмотренных в [4]. Методами теории исключения в варианте теории базисов Грёбнера получены явные уравнения минимальной вещественной алгебраической гиперповерхности, содержащей множество, параметризованное уравнениями (1). Для них построены уравнения минимальных алгебраических кривых, содержащих границу Д-разбиения, а также при помощи построения частичного цилиндрического алгебраического разложения получены точки из каждой компоненты Д-разбиения. Для системы непрерывного времени, впервые рассмотренной в [11, Example 2] и изученной в [4, Example 15], найдена новая область Д-разбиения с одним устойчивым корнем. Это иллюстрирует важную особенность предложенных вычислительных процедур, а именно, их глобальность - они работают на всей аффинной плоскости параметров сразу, а не в конкретной заранее заданной области изменения.
2. Оценка числа областей ^-разбиения
Приведем основные результаты, касающиеся оценки числа областей Д-разбиения. Пусть задан многочлен P(s,k) с комплексными (в частности, быть может, вещественными) коэффициентами, полиномиально зависящий
от вектора вещественных параметров к = (к\,. ..,к) € К = М1. Комплексные параметры можно рассматривать как пары вещественных вида а + jb.
Необходимо найти такие области и в пространстве параметров К, что Р(в, к) будет устойчивым многочленом в смысле Гурвица или Шура для любых к € и.
В частности, можно оценить число таковых областей. Этим оценкам посвящены следующие ниже результаты.
Теорема 1. Пусть Р(в,т,р) - некоторый многочлен степени £ с комплексными (в частности, вещественными), полиномиально зависящими от вещественных параметров т и р коэффициентами (в частности, от одного комплексного параметра т + jp) с максимальной (по т и р, как многочлена двух переменных) степенью й.
Предположим также, что Ш(Р^ш,т,р)) и 3(Р^ш,т,р)) как многочлены от трех комплексных переменных не имеют общих сомножителей нетривиально зависящих от ш.
Тогда количество областей Б-разбиения не превышает
д2 + д + 2 2
где д = 2Ы + 2й.
Например, в случае многочлена степени 3 по в с линейной зависимостью от параметров число областей Б-разбиения не превышает 37.
Теорема 2. Пусть Р(в,р\,... ,рп) - некоторый многочлен степени £ с комплексными (в частности, вещественными), полиномиально зависящими от вещественных параметров р^ коэффициентами с максимальной степенью й, как многочлена п переменных по параметрам р^.
Предположим также, что Ш(Р(^ш,р\,... ,рп)) и 3(Р(^ш,р\,... ,рп)) как многочлены комплексных переменных не содержат общих множителей ненулевой по ш степени.
Тогда количество областей Б-разбиения не превышает
6(4£й + 4й)п.
В основе доказательства теоремы 1 лежит следующая лемма:
Лемма 1. Пусть X - вещественная плоская (быть может, особая и приводимая) аффинная алгебраическая кривая степени п, тогда она делит плоскость не более чем на областей, причем эта оценка неулучшаема
и достигается на объединении п прямых общего положения.
Доказательства данных результатов приведены в Приложении.
Лемма 1, дающая возможность получить близкие к достижимым оценки, основана на классической теореме Харнака о максимальном числе компонент плоской вещественной алгебраической кривой. Обобщения теоремы Харнака на высшие размерности до сих пор не существует. Так, в трехмерном случае имеетс
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.