
9.1. Стабилизация регулятором заданной структуры 219
взгляд незначительная разница приводит к кардинальной перемене в сложности зада-
чи. Оказывается, Проблема 2 является NP -сложной, причем даже в простейших слу-
чаях, таких как поиск устойчивого полинома в интервальном семействе. Поэтому для
нее не существует методов решения полиномиальной сложности (т.е. таких, в которых
число операций полиномиально зависит от степени полинома P (s, q)). Более того, для
таких задач неверны и результаты типа теоремы Харитонова или реберной теоремы
(см. раздел 7.1). Иначе говоря, все вершины и все ребра многогранника Q могут быть
неустойчивы, однако некоторому q ∈ Q может соответствовать устойчивый полином.
Разумеется, можно предложить некоторые достаточные условия, которые гарантируют
положительный или отрицательный ответ в Проблеме 2. Однако эти условия далеки от
необходимых.
Другим возможным путем решения мог бы быть вероятностный подход, который
применялся в разделе 7.5 к задаче о робастной устойчивости. Так, можно попытаться
генерировать случайные точки q
i
из Q и проверять на устойчивость полиномы P (s, q
i
).
Однако эффективность такого подхода невелика — обычно устойчивые полиномы в
семействе P(s, Q), даже если они существуют, составляют очень небольшую по объему
долю. Например, в интервальном семействе полиномов степени n с коэффициентами
между 0 и 1 доля устойчивых полиномов v(n) оценивется как
v(n) ≤
1
[(n + 1)/2]!
(хотя эта оценка сильно завышена) или асимптотически v(n) ≈ e
−Cn
2
, где C — некото-
рая константа; для n = 10 численное моделирование дает v(n) ≈ 10
−9
. Таким образом,
вероятность получить устойчивый полином степени 10 при случайной генерации коэф-
фициентов, равномерно распределенных на [0, 1], ничтожно мала.
Существуют и численные методы решения Проблемы 2. Введем функцию
η(q)
.
= max
i
Re s
i
(q),
где s
i
(q) — корни полинома P (s, q). Ясно, что для устойчивого полинома имеем η(q) < 0,
а для неустойчивых η(q) ≥ 0. Поэтому можно решать задачу
min
q∈Q
η(q). (9.5)
Функция η(q) — дифференцируемая, если все s
i
(q) различны; с помощью теории воз-
мущений (см. раздел 10 Приложения и обсуждение в разделе 7.2) нетрудно выписать
ее градиент в таких точках. После этого естественно применить метод типа проекции
градиента для решения задачи оптимизации (9.5). К сожалению, такой подход не га-
рантирует получения правильного ответа в Проблеме 2. Дело в том, что функция η(q)
— невыпуклая, и метод может привести к локальному (а не глобальному) минимуму.
Кроме того, дополнительные трудности возникают в случае кратных корней. При этом
искомый устойчивый полином, возможно, не будет найден, хотя он и существует.
Этим же недостатком обладают численные методы, основанные на использовании
алгебраических критериев устойчивости типа Рауса-Гурвица. Именно, будем опериро-
вать с полиномом P (s, q) с помощью алгоритма Рауса, проводя вычисления в анали-
тической форме (например, с помощью пакета Symbolic Math Toolbox для символьных