«Факультет вычислительной математики и кибернетики Ю.Н. Киселёв, С.Н. Аввакумов, М.В. Орлов ОПТИМАЛЬНОЕ УПРАВЛЕНИЕ. ЛИНЕЙНАЯ ТЕОРИЯ И ПРИЛОЖЕНИЯ Учебное пособие для студентов факультета ВМиК МГУ Москва 2007 УДК 517.977.5 ...»

Пример. Найти решение задачи Коши Здесь n = 1, a = 1, t0 = 0, x0 = 1, u(·) 1. Применение формулы (2) даёт:

Формулу Коши (4), (5) целесообразно запомнить, так как исследование линейной задачи быстродействия основано в значительной степени на применении формулы Коши.

1.2.3 Примеры вычисления экспоненциала для конкретных матриц Пример 2.1. Найти экспоненциал etA матрицы A =.

и ряд (7) содержит лишь 2 члена:

Итак, Находим:

Применение формулы (7) даёт:

Таким образом, В примерах 2.1, 2.2 экспоненциал etA получен вычислением ряда (7). Рассмотрим теперь другой приём нахождения экспоненциала на основе его свойства (13).

Пример 2.3. Найти экспоненциал etA матрицы A =.

1) Покажем, что Для доказательства формулы (15) достаточно проверить, что матрица, стоящая в правой части (15), удовлетворяет условиям (13). Эта матрица при t = 0 превращается в единичную матрицу, далее и формула (15) доказана. Недостатком этого способа является то, что не указан способ получения самой формулы (15).

2) Рассмотрим метод получения (15) на основе свойства (13). Запишем экспоненциал в форме причём вектором начальных условий служит первый столбец единичной матрицы. Последняя система в координатной форме имеет вид:

Решая её, получаем:

Для нахождения второго столбца z(t) экспоненциала решаем задачу Коши Получаем:

Таким образом, мы пришли к формуле (15).

Обратим внимание на то, что экспоненциал (15) может быть записан в форме где p0 (t) = 1, p1 (t) = 1 et. Аналогичное представление было получено для экcпоненциала из примера 2.2, см. (14), где p0 (t) = cos(t), p1 (t) = sin(t). Это наблюдение позволяет применить для нахождения экспоненциала следующий метод.

3) Ищем экспоненциал в форме (16), где функции p0 (t), p1 (t) подлежат определению. Полагая в (16) t = 0, получаем откуда следует, что функции p0 (t), p1 (t) должны удовлетворять начальным условиям Дифференцируя (16) по t, получаем подстановка (16) в (18) даёт откуда, принимая во внимание равенство A2 = A, находим т.е.

или p0 (t) = 0, Из условий p0 (t) = 0, p0 (0) = 1 следует: p0 (t) 1. Далее из условий p1 (t)+p1 (t)p0 (t) = 0, p1 (0) = 1, p0 (t) = 1 следует, что p1 (t) = 1et.

Таким образом, в примере 2. Выбор представления экспоненциала (16), на котором основан последний метод, объясняет приведённая в разделе 1.2.4 теорема 2.3.

Пример 2.4. Найти экспоненциал etA для матрицы A =.

Решение:

Пример 2.5. Найти etA, где матрица Пример 2.6. Найти etA для матрицы Решение:

и по формуле (7) получаем Пример 2.7. Найти etA, где (n n)-матрица Решение. Так как An = 0, то по формуле (7) получаем:

Пример 2.8. Найти экспоненциал etA, где (n n)-матрица Пример 2.9. Пусть – матрица клеточно-диагональной структуры c блоками размерности (km km ) (жорданова клетка); k1 +...+ks = n. Показать, что (n n)-матрица J имеет экcпоненциал клеточно-диагональной Пример 2.10. Найти etA, если A = T 1 J T, где T – невырожденная (n n)-матрица, J – матрица из примера 2.9. Показать, что Предлагается решить примеры 2.8-2.10 самостоятельно.

1.2.4 Теорема о представлении экспоненциала в виде конечной Теорема 2.3. Пусть A – квадратная матрица n-ого порядка, t – скалярная переменная. Тогда где pj (t) – скалярные непрерывные (и даже аналитические) функции аргумента t.

2 Доказательство теоремы 2.3 основано на представлении экспоненциала etA в форме ряда (7) и теореме Гамильтона-Кэли, состоящей в том, что матрица аннулирует свой характеристический многочлен.

Запишем формулу (7) в виде Пусть – характеристический многочлен матрицы A. Утверждение теоремы Гамильтона-Кэли можно записать в форме где O = · · · · · · · · · – нулевая матрица размерности (n n).

Из (21), (22) следует, что где qj = hj, j = 0, 1,..., n1, – коэффициенты характеристического многочлена (21). Формула (23) показывает, что n-ая степень An матрицы A линейно выражается через меньшие степени A0 = E, A1, A2,..., An1 матрицы A, причём коэффициенты qj в (23) определяются матрицей A.

Покажем, что любая степень Ak, k > n, матрицы A также линейно выражается через A0, A1, A2,..., An1 с некоторыми коэффициентами, зависящими от номера k (и от матрицы A). Действительно, умножив равенство (23) на матрицу A, получаем:

где Аналогично получаем:

и так далее. Подстановка соотношений (24) – (26) в ряд (20) приводит (после перегруппировки членов) к представлению (19) экспоненциала etA.

Упражнение 2.1. Выписать ряды для коэффициентов в формуле (19) и доказать сходимость этих рядов при любом t.

Замечание 2.3. В формуле (19) фактически могут отсутствовать несколько старших степеней матрицы A. Например, для матрицы из примера 2.6, где n = 3, мы получили etA = ch(t) · E + sh(t) · A, т.е.

здесь в представлении экспоненциала имеем член с A фактически отсутствует. В случае A = E имеем:

т.е. здесь Теорема 2.3 будет использоваться в разделе 3.15 при доказательстве леммы о внутренней точке интеграла.

1.2.5 Пример применения формулы Коши для нахождения решения линейных систем где u2 (t) – заданная функция, a1, a2 – заданные числа, может быть решена двумя последовательными интегрированиями:

Полагая x1 = y, x2 = y, запишем задачу (27) в виде или где Найдём решение задачи (28), применяя формулу Коши (5). Имеем:

т.е.

Упражнение 2.2. Найти решение задачи Коши 1.2.6 Явная формула для решения задачи Коши в случае одномерного линейного неоднородного дифференциального уравнения с переменными коэффициентами Рассмотрим следующую задачу Коши где a(t), b(t) – известные непрерывные функции. Решение x(t) задачи Коши (29) определяется формулой где функция A(t) имеет вид A(t) = et0.

Упражнение 2.3. Проверить формулу (30).

1.3 Множество достижимости, множество управляемости. Их представление на основе формулы Коши. Предварительные соображения о решении линейной задачи быстродействия Рассмотрим линейную задачу быстродействия с классом допустимых управлений У = УU. При изучении этой задачи важную роль играют два множества – множество достижимости и множество управляемости.

1.3.1 Множество достижимости X(t) = X(t0, t, M0 ) Введём множество X(t0,, M0 ), определяемое множеством M0, начальным моментом времени t0, числом > t0 (это множество зависит также от матрицы A и от класса допустимых управлений У = УU ).

Рассмотрим задачу Коши и выпишем её решение по формуле Коши Поставим вопрос: куда можно перейти к моменту времени по траекториям дифференциального уравнения (1), исходящим в начальный момент времени t0 из различных точек x0 M0, если разрешается использовать всевозможные допустимые управления u(·) У? Множество концов x( ) описанных выше траекторий образует некоторое множество в E n, которое называется множеством достижимости и обозначается X(t0,, M0 ) (см. рисунок 3.1).

Таким образом, или, в более подробной записи, или Естественно считать, что X(t0, t, M0 ) = M0. Для множества доt=t стижимости часто удобно использовать краткое обозначение:

Множество X(t) с ростом t изменяется. При достаточно малых значениях t t0 > 0 множество (см. рисунок 3.2).

Если t1 t0 – оптимальное время перехода из M0 в M1, то Подчеркнём, что априори ниоткуда не следует, что множество достижимости X(t), в процессе изменения с течением времени, войдёт в контакт с множеством M1.

1.3.2 Множество управляемости Z(t) = Z(t, t1, M1 ) Введём множество Z(, t1, M1 ), определяемое множеством M1, моментом времени t1, числом < t1 (это множество зависит также от матрицы A и от класса допустимых управлений У = УU ). Рассмотрим задачу Коши Начальное условие в этой задаче задаётся на правом конце отрезка [, t1 ]. Выпишем её решение по формуле Коши:

Множество Z(, t1, M1 ) (множество управляемости) состоит из всех таких точек z E n, находясь в которых в момент времени, объект в момент времени t1 попадает на множество M1 при помощи некоторого допустимого управления:

или, в более подробной записи, или Естественно считать, что Z(t, t1, M1 ) = M1. Для множества управt=t ляемости удобно использовать краткое обозначение:

Свойства множеств X(t), Z(t) рассмотрены в разделе 3.8. В случае t1 t0 = min между множествами X(t) и Z(t) имеется тесная связь, описанная в разделе 3.11.

1.3.3 Представление множеств достижимости и управляемости на основе формулы Коши Имеют место следующие представления:

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

1.3.4 Операции над множествами в пространстве E n Определение 3.1. Алгебраической суммой двух множеств F1, F2 E n называется множество т.е.

– отрезки. Множество (см. рисунок 3.3).

Пример 3.2. Пусть F1 = {a} – множество, состоящее из одной точки a E 2, F2 = Sr (0) – круг. Тогда есть круг радиуса r с центром в точке a (см. рисунок 3.4).

Определение 3.2. Произведением (n n)-матрицы D на множество F E n называется множество т.е.

Тогда – отрезок (см. рисунок 3.5).

Определение 3.3 (интеграл от класса допустимых управлений). Пусть У – класс допустимых управлений, D(s) – (n n)матрица, непрерывно зависящая от скалярного аргумента s [t0, t];

t0 < t. Полагаем Из формул (5), (10) и определений 3.1, 3.2, 3.3 следуют представления (11), (12).

2 Элементы выпуклого анализа в пространстве E n. Три теоремы об интегралах 2.4 Основные обозначения и определения. Наименьшая выпуклая оболочка множества и её построение. Лемма об отделимости 2.4.1 Основные обозначения и определения E n – n-мерное евклидово пространство, (x, y) = x1 y1 +... + xn yn – скалярное произведение элементов x и y, x = (x, x)1/2 – норма элемента x, F – множество, лежащее в пространстве E n, 2 – начало доказательства, – конец доказательства.

Определение 4.1. Множество F называется открытым, если для любой точки x F существует число > 0 такое, что S (x) F x F > 0: S (x) F (см. рисунок 4.1).

Множества являются открытыми в E 2 ; множества Sr (a), S не являются открытыми.

Определение 4.2. Точка a E n называется предельной точкой множества F, если > 0 выполняется условие S (a) F =.

Так, для множества F = {x E n : x < 1} все его предельные точки образуют множество S1 (0).

Определение 4.3. Множество F называется замкнутым, если оно содержит все свои предельные точки.

Множества Sr (0), S замкнуты.

Определение 4.4. Множество F называется ограниченным, если существует такое число R > 0, что имеет место включение F SR (0), см. рисунок 4.2.

Определение 4.5. Модулем множества F называется число Для любого ограниченного множества F его модуль | <.

Модуль множества F = x E 2 : |x1 | 1, |x2 | 1 равен 2.

Определение 4.6. Множество F называется компактом, если оно замкнуто и ограничено.

Примерами компактов являются множества множества не являются компактами (нет замкнутости); множество не является компактом (нет ограниченности).

Определение 4.7. (E n ) – множество, элементами которого являются всевозможные непустые компакты пространства E n.

Определение 4.8. Пусть x, y – точки пространства E n. Отрезком [x, y] с концами x, y называется множество или Определение 4.9. Множество F называется выпуклым, если Так, множество Sr (a) выпукло, а множество S невыпукло. На рисунке 4.3 изображено невыпуклое множество.

Определение 4.10. conv (E n ) – множество, состоящее из непустых выпуклых компактов пространства E n.

Ясно, что conv (E n ) (E n ).

2.4.2 Наименьшая выпуклая оболочка множества и её построение Определение 4.11. Множество G E n называется выпуклой оболочкой множества F, если G выпукло и G F.

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

Определение 4.12. Множество H называется наименьшей выпуклой оболочкой множества F, если 1) H– выпуклая оболочка, 2) для любой выпуклой оболочки G множества F выполняется включение G H.

Обозначение наименьшей выпуклой оболочки множества:

Для невыпуклого множества F, изображенного на рисунке 4.5 а), наименьшая выпуклая оболочка conv F изображена на рисунке 4.5 б).

Если множество F выпукло, то conv F = F. Для множества F, состоящего из трёх точек (рисунок 4.6), conv F есть треугольник.

Теорема 4.1 (о построении наименьшей выпуклой оболочки).

Для любого множества F E n существует наименьшая выпуклая оболочка conv F, которую можно построить следующим образом. РасF conv F смотрим последовательность множеств 2 Для доказательства теоремы следует показать, что 2) множество H выпукло, 3) любая выпуклая оболочка G множества F содержит множество H: G H (см. определения 4.11, 4.12).

Из построения множеств Fm, H следует свойство монотонности:

Проверим выпуклость множества H: x, y H [x, y] H. Возьмём две точки x, y H. Существует такой номер m1, что x Fm1 ; существует такой номер m2, что y Fm2. Тогда из свойства монотонности следует, что x, y Fm, где m = max{m1, m2 }, и, привлекая определение множества Fm+1, получаем, что отрезок [x, y] Fm+1 H.

Доказана выпуклость множества H. Итак, H – выпуклая оболочка множества F.

Пусть теперь G – любая выпуклая оболочка множества F. Тогда т.е. доказано, что H = conv F.

Замечание 4.1 (о стабилизации цепочки множеств {Fm } в конечномерном пространстве E n ). Существует такой наименьший номер s = s(n, F ), что Fs = Fs+1 =... = H, причём 0 n. Так, например, для выпуклого множества F имеем F0 = F1 =... = H, т.е.

s = 0. Для множества F, состоящего из отрезка и точки, не лежащей на этом отрезке (рисунок 4.7), имеем:

Для множества F, рассмотренного выше (рисунок 4.6), n = 2, s = 2, Замечание 4.2 (об эквивалентной формулировке процесса построения наименьшей выпуклой оболочки множества). Последовательность множеств {Fm }, введённая в теореме 4.1, может быть определена соотношениями Действительно, Задача 4.1. Установить включение F F + (1 )F [0, 1].

Включение F F + (1 )F, (0, 1), может не выполняться. Так при n = 1, F = {1, +1}, = 1 имеем 1 F + 1 F = {1, 0, +1}, т.е.

множество F не содержит множество 1 F + 1 F.

Задача 4.2. Показать, что для выпуклого множества F при любом [0, 1] выполняется равенство Задача 4.3. Алгебраическая сумма F1 +F2 выпуклых множеств F1, F2 является выпуклым множеством.

Задача 4.4. Если F – выпуклое множество, D – (n n)-матрица, то множество DF выпукло.

Задача 4.5. Доказать утверждение о стабилизации цепочки множеств {Fm } в конечномерном пространстве E n, см. замечание 4.1.

Задача 4.6. Если F (E n ), то conv F conv (E n ).

2.4.3 Лемма об отделимости (строгая отделимость) и её геометрическая интерпретация. Опорная гиперплоскость Лемма 4.1. Пусть 1) H conv (E n ) (т.е. множество H – выпуклый компакт), 2) x0 H (т.е. точка x0 не принадлежит компакту H), тогда Утверждения (1) и (2) равносильны. Лемма об отделимости имеет простой геометрический смысл (рисунок 4.8):

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

Неравенство (1) означает, что вектор образует с векторами h x тупой угол при любом h H. Обратимся к доказательству леммы.

2 1. Конструктивное описание вектора. Пусть h0 – ближайшая к x0 точка множества H, т.е.

Отметим, что точка h0 называется проекцией точки x0 на компакт H (обозначение: h0 = P rH, x0 ) (см. рисунок 4.9). Минимум в (3) на основании теоремы Вейерштрасса достигается в некоторой точке h0 H, причём строгое неравенство h0 x0 > 0 выполняется, так как x0 H и H – компакт. Полагаем 2. Покажем теперь, что с определённым равенством (4) вектором справедливо неравенство (1), т.е.

Последнее неравенство равносильно следующему Неравенство (5) при h = h0 верно, так как h0 x0 > 0. Покажем, что Возьмём любую точку h H, h = h0, и рассмотрим отрезок (см. рисунок 4.10).

Поэтому в силу (3) Неравенство (7) последовательно преобразуется следующим образом:

Переход к пределу при +0 в последнем неравенстве даёт Докажем теперь неравенство (6), привлекая (8). Имеем Замечание 4.3. Оба условия леммы об отделимости существенны: утверждение леммы не сохраняется при отсутствии выпуклости компакта H, при нарушении замкнутости или ограниченности множества H, при x0 H.

Замечание 4.4. Если h0 – граничная точка выпуклого компакта H, то С геометрической точки зрения это означает, что через точку h0 можно провести гиперплоскость которая делит всё пространство E n на два полупространства, одно из которых полупространство = {x E n : (x h0, ) 0} содержит выпуклый компакт H: H (см. рисунок 4.11). Гиперплоскость называется опорной гиперплоскостью для компакта H.

Неравенство (9) запишем в форме Из него следует, что Функция c(H, ), определяемая компактом H, называется опорной функцией этого компакта в направлении вектора. При помощи этой функции можно описать гиперплоскость и полупространство :

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

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

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

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

2.5.1 Предварительные геометрические соображения Рассмотрим выпуклый компакт F на плоскости. Ясно, что компакт F можно приближённо представить при помощи описанных выпуклых многоугольников, (см. рисунок 5.1), причём при подходящем увеличении числа сторон выпуклого многоугольника выпуклый компакт F может быть представлен весьма точно.

Если выбрать достаточно представительный набор векторов 0, 1,..., N S, то получим где пересечение конечного числа полупространств (полуплоскостей) – выпуклый многоугольник MN – даёт достаточно точное описание выпуклого компакта F. При этом аппроксимация множества многоугольником носит внешний характер: MN F. Мы покажем далее2, 2 Рисунок 5.1 а) носит схематичный характер: плоское выпуклое множество грубо приближается описанным выпуклым пятиугольником. На рисунке 5.1 б) показан результат аппроксимации плоского выпуклого компакта (лунки, см. пример 21.10) которая является пересечением двух кругов радиуса 2 с центром в точках (1, 0) что выпуклый компакт F E n может быть получен как пересечение всех полупространств, когда вектор пробегает единичную сферу S:

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

Эти геометрические соображения полезно иметь в виду при изучении материала раздела 2.5.

и (1, 0), выпуклым N -угольником. Можно показать, что опорная функция лунки определяется формулой При выполнении расчёта и создании рисунка 5.1 б) количество опорных прямых выбрано равным 60: наблюдается высокое качество приближения множества L пересечением опорных полуплоскостей. В двух угловых точках лунки опорная прямая определяется неединственным образом.

2.5.2 Определение опорной функции ограниченных множеств Пусть F – ограниченное множество, лежащее в некотором шаре SR (0) пространства E n, – вектор пространства E n.

Определение 5.1. Опорной функцией множества F называется функция, определяемая равенством Опорная функция любого ограниченного множества принимает конечные значения при любом векторе E n. Действительно, где число |F | = sup f, называемое модулем множества F, не преf F восходит R. Отсюда вытекает оценка Ясно также, что Замечание 5.1. Множество F может быть незамкнутым и невыпуклым.

Рассмотрим несколько примеров.

Пример 5.1. Рассмотрим на плоскости E 2 множество F = S1 (0) – круг радиуса 1 с центром в начале координат – и найдём его опорную функцию:

Пример 5.2. Рассмотрим на плоскости E 2 множество – открытый круг радиуса 1 с центром в начале координат – и найдём его опорную функцию:

Опорная функция c(F, ) = (f0, ) равна наибольшей величине проекций векторов f F на единичный вектор. Знак (f0, ) характеризует взаимное расположение множества F и точки 0 относительно опорной гиперплоскости : если (f0, ) > 0, то компакт F и начало координат 0 расположены по одну сторону от опорной гиперплоскости, рисунок 5.3 а); если (f0, ) = 0, то 0, рисунок 5.3 б);

если (f0, ) < 0, то компакт F и начало координат 0 расположены по разные стороны от опорной гиперплоскости, рисунок 5.3 в). При S опорная функция c(F, ) равна расстоянию от начала координат до опорной гиперплоскости, причём расстоянию приписывается определённый знак.

2.5.3 Cвойства опорных функций Здесь будут рассмотрены 10 простейших свойств опорной функции.

Свойство1 (опорная функция замыкания множества):

а) пусть F (E n ), тогда б) пусть F – ограниченное множество, лежащее в пространстве E n, а F – замыкание множества F, тогда 2 В силу непрерывности скалярного произведения (f, ) (по аргументу f ) для компактного множества F максимум скалярного произведения (f, ) достигается в некоторой точке f0 F (теорема Вейерштрасса), поэтому вместо точной верхней грани (sup) в формуле (1) можно записать знак максимума (max), что доказывает утверждение а). Утверждение б) вытекает из определений опорной функции, замыкания множества и непрерывности скалярного произведения (f, ).

Свойство 1 можно проиллюстрировать примерами 5.1, 5.2.

Свойство 2 (положительная однородность опорной функции по второму аргументу):

2 Имеем:

Проверить выполнение свойства 2 для множества из примера 5.4.

Упражнение 5.2. Являются ли функции опорными функциями некоторого компакта F (E 2 )?

Свойство 3 (полуаддитивность по второму аргументу):

2 Пусть F – замыкание ограниченного множества F. Тогда множество F (E n ). Привлекая свойство 1, получаем:

Упражнение 5.3. Доказать выпуклость опорной функции c(F, ) по второму аргументу (использовать определение выпуклости функции и свойства 2, 3 опорных функций). Проверить выполнение этого утверждения в примере 5.1.

Свойство 4 (условие Липшица по второму аргументу):

здесь |F | = sup f – модуль множества F ; множитель |F | играет роль константы Липшица.

2 Используя свойство 3, получаем:

Отсюда, привлекая неравенство (2), находим:

Поменяв роли векторов 1 и 2 в предыдущих рассуждениях, приходим к неравенству Из двух последних неравенств вытекает двойное неравенство т.е.

Следствие из свойства 4. Опорная функция c(F, ) непрерывна по второму аргументу:

Свойство 5 (опорная функция линейно преобразованного множества):

пусть D – квадратная матрица n-го порядка, тогда где D – матрица, полученная из матрицы D транспонированием.

2 Свойство 5 вытекает из определений опорной функции, операции линейного преобразования множества и свойств скалярного произведения c(DF, ) = sup (x, ) = В частном случае матрицы D = E, где – число, E – единичная матрица, множество и на основании свойства Если число Итак, имеет место Свойство 6 (положительная однородность по первому аргументу):

Свойство 7 (аддитивность по первому аргументу):

2 Используя определения опорной функции и операции алгебраического сложения множеств, получаем = sup (f1 + f2, ) = sup (f1, ) + sup (f2, ) = = c(F1, ) + c(F2, ).

Свойство 8 (опорная функция объединения множеств):

а) c(F1 F2, ) = max{c(F1, ), c(F2, )}, б) для семейства {F } равномерно ограниченных множеств, зависящих от параметра, принадлежащего некоторому множеству (R > 0: |F | R ), имеет место формула 2 В случае а) получаем Свойство 9 (опорная функция неотрицательной линейной комбинации множеств):

пусть 1, 2 – неотрицательные числа, F1, F2 – ограниченные множества, лежащие в пространстве E n, тогда 2 Свойство 9 вытекает из свойств 7 и 6.

Свойство 10 (совпадение опорных функций множества и его наименьшей выпуклой оболочки):

Привлекая свойство 8 б), можно записать Покажем, что Тогда из (5), (6) вытекает утверждение (4) свойства 10. Ясно, что c(F0, ) = c(F, ). Далее F1 = свойства 8 б) и 9, получаем Итак, равенство (6) верно при m = 0, 1; его справедливость для любого номера m устанавливается индукцией.

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

2.5.4 Примеры Пример 1. Найти опорную функцию множества (единичного шара в пространстве E n ). Так как Пример 2. Найти опорную функцию множества (шара радиуса r 0 с центром в начале координат). Замечая, что Sr (0) = r · S1 (0) и, используя свойство 6 и результат примера 1, получаем:

Пример 3. Найти опорную функцию множества состоящего из одной точки a E n. По определению опорной функции Пример 4. Найти опорную функцию множества (шара радиуса r 0 с центром в точке a E n ). Привлекая равенство Sr (a) = {a} + Sr (0), свойство 7 и результат примеров 2, 3, получаем:

Установленное соотношение будет использовано при дальнейшем изложении курса.

Пример 5. Найти опорную функцию множества состоящего из двух точек v и v. Используя определение опорной функции, получаем Пример 6. Найти опорную функцию множества состоящего из двух точек (1, 0) и (1, 0). По определению опорной функции находим Пример 7. Найти опорную функцию множества (отрезка на плоскости с концами (1, 0) и (1, 0) ). Имеем:

Мы видим, что c(F7, ) = c(F6, ); это равенство иллюстрирует свойство 10, так как F7 = conv F6.

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

Имеем:

Пример 9. Найти опорную функцию множества (квадрата). Имеем:

Совпадение опорных функций множеств F8 и F9 опять иллюстрирует свойство 10, так как F9 = conv F8.

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

здесь Q– симметричная положительно определённая матрица порядка n. Для нахождения опорной функции множества F10 заметим, что где A – диагональная матрица с элементами a1,..., an на диагонали, A = A. Используя свойство 5 и результат примера 1, получаем:

Так как Доказать самостоятельно, что c(Э, ) = (Q1, ). Указание:

использовать вспомогательную переменную y = Q1/2 x S1 (0).

Пример 11. Опорная функция множества (отрезка с концами a, b E n ) определяется формулой 2.5.5 Теорема о представлении наименьшей выпуклой оболочки компакта в форме пересечения полупространств. Свойства 11 14 опорной функции, вытекающие из этой теоремы Рассматриваемая теорема, содержащая основной теоретический результат раздела 2.5, показывает в какой степени множество определяется своей опорной функцией. Как мы видели в примерах 5.1-5.3, различные множества могут иметь одну и ту же опорную функцию.

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

Теорема 5.1. Пусть F (E n ); c(F, ) – опорная функция множества F ; E n. Тогда Введём обозначения:

= {x E n : (x, ) c(F, )} – замкнутое полупространство, ограниченное гиперплоскостью = {x E n : (x, ) = c(F, )} с вектором нормали S;

– пересечение полупространств по всем векторам S, где S – единичная сфера;

H = conv F – наименьшая выпуклая оболочка множества F.

Тогда утверждение (7) теоремы 5.1 можно кратко записать в форме равенства Теорема утверждает, что наименьшая выпуклая оболочка H компакта F представляется в форме пересечения по векторам S полупространств, определяемых опорной функцией компакта F, т.е.

conv F определяется опорной функцией c(F, ) компакта F.

Это значит, что по опорной функции c(F, ) компакта F может быть однозначно восстановлен не сам компакт F, а только его наименьшая выпуклая оболочка conv F.

2 Обратимся к доказательству теоремы. Нужно установить равенство (8) – совпадение множеств H и.

1. Докажем сначала, что H. Используя определение опорной функции и свойство 10, получаем, что для любой точки x H зывает включение 2. Докажем теперь включение (методом от противного). Отметим, что множество =, так как F = и F (почему?). Допустим, что (10) неверно, тогда существует точка x0, x0 H. Так как H выпуклый компакт и x0 H, то по лемме об отделимости 0 S: (h x0, 0 ) < 0 h H, т.е.

Отсюда следует, что причём неравенство здесь строгое, так как H – компакт. Отсюда, привлекая свойство 10, получаем т.е.

тельно, Сравнение неравенств (11) и (12) приводит к противоречию, которое доказывает включение (10).

3. Из включений (9) и (10) следует равенство (8), которое является краткой записью представления (7).

Теорема доказана.

Следствие из доказанной теоремы о представлении выпуклых компактов в форме пересечения полупространств. Пусть F conv (E n ), тогда Представление (13) показывает, что выпуклый компакт однозначно определяется своей опорной функцией, т.е. при F1, F2 conv (E n ) имеем Упражнение 5.2. Найти алгебраическую сумму F двух шаров Ясно, что F1, F2, F (E n ). Найдём опорную функцию множества F = F1 + F2. Используя свойство 7, результат примера 4 из подраздела 2.5.4, получаем Итак, два выпуклых компакта F и Sr1 +r2 (a1 + a2 ) имеют одинаковые опорные функции, следовательно, в силу (14), они совпадают, т.е.

установлено правило алгебраического сложения двух шаров:

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

Рассмотрим сейчас основанные на доказанной теореме свойства 11 -14 опорных функций. В этих свойствах речь идёт о формулировке условий включения, непустоты пересечения двух множеств в терминах опорных функций этих множеств.

Свойство 11 (условие вложенности для двух множеств):

пусть F1, F2 (E n ), тогда 2 Проверим первую импликацию. Если выполняется включение F1 F2, то Проверим теперь вторую импликацию. Если выполнено неравенство c(F1, ) c(F2, ), то, привлекая представление (7) доказанной выше теоремы, получаем:

conv F1 = Следствие из свойства 11. Для F1, F2 conv (E n ) Замечание 5.2. В силу свойства 2 опорных функций условие равносильно условию Аналогичное замечание относится и к свойствам 11 14, приведенным ниже, и их следствиям.

Свойство 12 (условия принадлежности точки множеству):

пусть f E n, F (E n ), тогда 2 Свойство 12 вытекает из свойства 11 при F1 = {f }, F2 = F.

Следствие из свойства 12. Для f E n, F conv (E n ) Свойство 13 (условие принадлежности нулевой точки множеству):

пусть 0 E n, F (E n ), тогда 2 Свойство 13 вытекает из свойства 12 при f = 0.

Следствие из свойства 13. Для F conv (E n ) Чрезвычайно важную роль в дальнейшем (при исследовании вопроса об управляемости и доказательстве принципа максимума) играет следующее свойство опорных функций.

Свойство 14 (условия непустоты пересечения двух множеств):

пусть F1, F2 (E n ), тогда Знаком здесь обозначено пустое множество.

2 Докажем сначала первую импликацию. Условие F1 F2 = (непустота пересечения множеств F1 и F2 ) означает существование хотя бы одной общей точки у этих множеств: f E n, f F1, f F2.

Тогда (f ) (F2 ) и, в силу определения алгебраической суммы двух множеств, получаем: f + (f ) F1 + (F2 ), т.е. 0 F1 + (F2 ).

Первая часть свойства 13 влечёт неравенство которое, в силу свойства 7, принимает вид:

и, наконец, с помощью свойства 5, окончательную форму:

Докажем теперь вторую импликацию свойства 14. Пусть выполнено неравенство (15). Полагая H1 = conv F1, H2 = conv F2, и, привлекая свойство 10, из неравенства (15) получаем Отсюда с помощью свойств 5 и 7 приходим к неравенству Так как H1, H2 conv (E n ), то H1 +(H2 ) conv (E n ). Поэтому в силу следствия из свойства 13 неравенство (16) равносильно условию 0 H1 + (H2 ), из которого следует, что H1 H2 =, т.е.

Следствие из свойства 14. Для F1, F2 conv (E n ) Покажем на примере, что последнее утверждение для невыпуклых компактов неверно. Пусть F1 = S (0), 0 < < 1; F2 = S, тогда (шар радиуса с центром в нуле не пересекается с единичной сферой S).

2.5.6 Расстояние Хаусдорфа между множествами. Свойства 15, 16 опорной функции, связанные с расстоянием Хаусдорфа точки x0 называется шар S (x0 ) = {x0 } + S (0). Напомним, что S (x0 ) = {x E n : x x0 }. Пусть r = x0 y0 – расстояние между двумя точками x0, y0 E n ; тогда соотношения выполняются для любого числа r, причём Определение 5.2. -окрестностью множества F E n называется множество Рассмотрим пример. Пусть F = x E 2 : |x1 | 1, |x2 | 1 – квадрат, его -окрестность изображена на рисунке 5.4.

Определение -окрестности множества F как объединения шаров S (f ) по всем точкам f F позволяет в плоском случае дать “механическое” описание процедуры построения -окрестности: если считать круг S (f ) покрытым краской, то -окрестность множества F состоит из всех окрашенных точек плоскости, когда центр f этого круга пробегает все множество F.

Обратимся к определению расстояния между множествами. Рассмотрим в E n два ограниченных множества F1, F2 ; ясно, что существует такое число R > 0, что Таких чисел R существует много, и можно поставить вопрос о выборе “наименьшего” из таких чисел, для которых оба записанные включения выполняются. На этом пути приходим к определению расстояния между множествами (расстояния Хаусдорфа).

Определение 5.3. Пусть F1, F2 (E n ). Расстоянием Хаусдорфа между множествами F1 и F2 называется неотрицательное число h(F1, F2 ), определяемое формулой Расстояние Хаусдорфа h(F1, F2 ) определено для любых множеств F1, F2 (E n ).

Упражнение 5.4. Проверить, что расстояние h(F1, F2 ) удовлетворяет трём аксиомам метрики метрического пространства:

2) h(F1, F2 ) = h(F2, F1 ) (симметричность);

(неравенство треугольника).

ства F (E n ) формулу Найдём расстояние Хаусдорфа между кругом F1 = S1 (0) и квадратом F2 = x E 2 : |x1 | 1, |x2 | 1 на плоскости. Очевидно, что F1 F2 + Sr (0) для любого r 0, так как F1 F2. Далее, F ко видеть, что минимальное значение r, для которого выполняется включение F2 S1+r (0), равно 2 1. Следовательно, Замечание 5.3. Расстояние Хаусдорфа можно определить для любых множеств из E n, заменив в формуле (17) знак “min” знаком “inf”.

Пример 5.5. Пусть Покажем, что h(F1, F2 ) = 0. Действительно, F2 F1 + Sr (0) при любом r 0, так как F2 F1. Включение F1 F2 +Sr (0) выполняется при любом r > 0. Поэтому Пример 5.6. Пусть F2 = {x E : x2 = arctg x1 } – график арктангенса.

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

Свойство 15 (условие Липшица по первому аргументу):

Здесь множитель играет роль константы Липшица.

2 Из определения расстояния Хаусдорфа следует включение F F2 + Sh(F1,F2 ) (0). Отсюда, привлекая свойство 11 (часть 1), свойство 7 и пример 2 из раздела 2.5.4, получаем:

т.е.

Если поменять ролями множества F1 и F2, то, в силу симметричности расстояния Хаусдорфа, получим неравенство Из двух последних неравенств следует неравенство (18).

Следствие из свойства 15. Опорная функция c(F, ) непрерывна по первому аргументу, т.е. c(F, ) c(F, ), h(F, F ) 0. Здесь Следствие из свойств 14, 15. Опорная функция c(F, ) непрерывна по совокупности аргументов, т.е.

Упражнение 5.6. Доказать последнее утверждение.

Свойство 16 (вычисление расстояния Хаусдорфа между выпуклыми компактами при помощи опорных функций этих компактов):

пусть F1, F2 conv (E n ), тогда имеет место формула 2 Полагая M = max c(F1, ) c(F2, ), перепишем (19) в форме Докажем сначала, что Из свойства 15 следует неравенство которое в силу определения числа M влечет (21).

Докажем теперь, что Из определения числа M следует, что или Умножив почленно последнее неравенство на и привлекая свойство 2, получаем или Используя правую часть последнего неравенства, свойство 7, получаем c(F1, ) c(F2, ) + c(SM (0), ) = c(F2 + SM (0), ) Так как компакты F1 и F2 + SM (0) выпуклы, то по следствию из свойства 11 опорных функций последнее соотношение влечёт включение Левая часть неравенства (23) при помощи аналогичных рассуждений приводит к включению Итак, для числа M одновременно выполняются включения (24), (25), и, таким образом, определение расстояния Хаусдорфа (17) приводит к обоснованию неравенства (22). Из (21) и (22) вытекает требуемое равенство (20).

Замечание 5.4. Формула (19) доказана для выпуклых компактов.

Приведем пример, показывающий, что без условия выпуклости эта формула неверна. Пусть n = 2, – множества, каждое из которых состоит из двух точек. Ясно, что включения стороны, Таким образом, h(F1, F2 ) = 2 > 1 = M, т.е. формула (19) для рассматриваемых невыпуклых компактов F1 и F2 неверна.

В заключение рассмотрим пример применения формулы (19) для нахождения расстояния между двумя шарами Sr1 (a1 ) и Sr2 (a2 ), где a1, a2 E n, r1, r2 0. Имеем:

h(Sr1 (a1 ), Sr2 (a2 )) = max c(Sr1 (a1 ), ) c(Sr2 (a2 ), ) = Мы закончили рассмотрение основных свойств опорных функций, которые являются удобным аналитическим аппаратом для описания выпуклых компактов.

2.6 Интегралы. Три теоремы об интегралах В этом разделе будут представлены три теоремы:

Теорема 6.1 – о внесении знака опорной функции под знак интеграла, Теорема 6.2 – об основных свойствах интеграла, Теорема 6.3– о непрерывной зависимости интеграла от верхнего предела интегрирования.

2.6.1 Краткое введение Мы уже знакомы с постановкой линейной задачи быстродействия, компактная запись которой имеет вид Постановка линейной задачи быстродействия требует задания следующего набора исходных данных {A, M0, M1, У = УU }, где A – матрица системы, M0 – множество начальных состояний объекта, M1 – множество конечных состояний объекта, У = УU – класс допустимых управлений, U – область управления. Напомним, что начальный момент времени t0 считается фиксированным. Класс допустимых управлений состоит из векторных функций u(s) скалярного аргумента s, принимающих значения из заданного множества U (E n ), причём каждая из этих функций u(s) интегрируема. При изучении задачи быстродействия (1) важную роль играет множество достижимости X(t0, t, M0 ) X(t), которое может быть представлено в форме Множество X(t), как показывает правая часть равенства (2), является алгебраической суммой двух множеств. На основании свойства 7 опорных функций (аддитивность по первому аргументу) опорную функцию множества достижимости X(t) можно представить в виде суммы двух слагаемых:

Последнее слагаемое в формуле (3) представляет собой опорную функцию от множества, определяемого интегралом. Возникает вопрос о том, как опорная функция интеграла выражается через опорную функцию компакта U, входящего в описание класса У = УU допустимых управлений. Ответ на поставленный вопрос даёт рассмотренная ниже теорема 6.1. Теоремы 6.2 и 6.3 дают описание некоторых свойств интеграла.

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

Определение 6.1. Пусть D(s) – непрерывная (n n)-матрица;

t0 < t; интеграл (4) определяется равенством Интеграл (4) является множеством, лежащим в пространстве E n.

Упражнение 6.1. Пусть n = 1, D(s) 1, t0 = 0, 0 < t, U = [1, 1].

Показать, что 2.6.2 Теорема о внесении знака опорной функции под знак интеграла Теорема 6.1. Пусть 2) D(s) – непрерывная (n n)-матрица, – класс допустимых управлений.

Рассмотрим множество Тогда имеет место равенство:

2 Введём обозначения:

a c(X, ) – левая часть равенства (6), b c(D(s)U, ) ds – правая часть равенства (6).

Тогда утверждение теоремы 6.1 кратко запишется в форме Доказательство теоремы 6.1 проводится по следующей схеме:

Приведём сначала некоторые вспомогательные утверждения (леммы 6.1, 6.2).

Лемма 6.1. Пусть Справедливо неравенство 2 Действительно, пусть ai = (ai,..., ai ) – i-ая строка матрицы A.

Тогда т.к. A =., Ax =., что доказывает лемму 6.1.

непрерывно зависящую от s [t0, t]; каждый её элемент di (s) являетj ся непрерывной функцией аргумента s [t0, t]. Положим, Функция j () аргумента > 0, называемая модулем непрерывности функции di (s), удовлетворяет условию j () 0 при +0 (это слеi дует из равномерной непрерывности на отрезке [t0, t] функции di (s), которая предполагается непрерывной на этом отрезке). Положим Ясно, что () 0 при +0.

u U. Имеют место неравенства c(D(s1 )U, )c(D(s2 )U, ) (D(s1 )u, )(D(s2 )u, ) правая часть которых стремится к нулю при +0.

2 Действительно, привлекая свойства опорных функций, последовательно получаем = c(U, D (s1 )) c(U, D (s2 )) Неравенство (9) доказано. Неравенство (10) доказывается аналогично:

Обратимся теперь к доказательству теоремы 6.1 по указанной выше схеме 1., 2., 3., 4.

1. a. Чтобы проверить утверждение 1. для величины a = c(X, ) (при любом фиксированном векторе E n ), мы покажем, что множество X непусто и ограничено.

Проверим сначала, что X =. Множество непусто, так как множество U непусто и существует точка u U ;

управление u (s) u s является допустимым u (s) У и точка Для доказательства ограниченности множества X возьмем любую где u(·) У, u(s) U при любом s [t0, t]. Следовательно, где Таким образом, R > 0: X SR (0). Ограниченность множества X доказана. Следовательно, при каждом E n величина a = c(X, ) определена и принимает конечное значение. Утверждение 1. доказано.

2. b. Чтобы проверить утверждение 2. для величины (при любом фиксированном векторе E n ), перепишем последнюю формулу в виде Существование интеграла (11) следует из непрерывности подынтегральной функции по переменной интегрирования s [t0, t]. Непрерывность подынтегральной функции по s вытекает из непрерывности опорной функции по второму аргументу, непрерывности D (s) по s и теоремы о непрерывности суперпозиции двух непрерывных функций.

Заметим, что непрерывность функции c(D(s)U, ) по s следует также из неравенства (9). Проверка утверждения 2. закончена.

ние Поэтому Утверждение 3. доказано.

Проведём теперь наиболее трудную часть доказательства теоремы 6.1 – проверку утверждения 4.:

Неравенство (12) вытекает из следующей леммы 6.3.

Лемма 6.3. Для любого натурального N имеет место неравенство Лемма 6.4. Для любого натурального N Очевидно, что лемма 6.4 = лемма 6.3 = неравенство (12) Действительно, т.е. a неравенстве (a и b от N не зависят, а N 0, N ) приводит к интересующему нас неравенству (12). Таким образом, для доказательства неравенства (12) остаётся установить утверждение леммы 6.4.

Лемма 6.5. Имеет место утверждение леммы 6.4, причём в (14) точка xN допускает представление где uN (·) – кусочно-постоянное допустимое управление (uN (·) У), а число N определяется равенством причём Доказательство леммы 6.5, которое мы сейчас проведём, состоит из двух частей:

() проверка требуемых утверждений (14)-(17).

() Опишем сначала построение управления uN (·). Пусть N – натуральное число; разобьём отрезок [t0, t] на N равных частей точками где tj+1 tj = (t t0 )/N > 0, = N 0 при N (см. рисунок 6.1).

Определим множества I 0 = [t0, t1 ), I 1 = [t1, t2 ),..., I j = [tj, tj+1 ),..., I N 1 = [tN 1, tN ]. Напомним, что число b определяется интегралом, стоящим в правой части формулы (6). Подынтегральная функция этого интеграла при s = tj, j = 0, 1,..., N 1, представима в форме Действительно, так как U (E n ), то Привлекая выделенные выше точки uj, определим кусочно-постоянное управление uN (s), s [t0, t], полагая Ясно, что построенное управление uN (·) У, так как функция uN (s) – интегрируема и принимает значения из компакта U при любом s [t0, t].) () Проверим утверждения (14)-(17). Так как управление (19) допустимо, то точка xN, определяемая равенствами (15), (19) принадлежит множеству X. Представим левую часть неравенства (14) в форме а число b, входящее в правую часть неравенства (14), в форме Из (20), (21) получаем вычитанием:

Оценим сверху величину |Rj |. Привлекая (22), (18), получаем + c(D(tj )U, ) c(D(s)U, ) ds, откуда с помощью леммы 6.2 приходим к оценке Следовательно, причём N 0 при N, так как () 0 при 0. Таким образом, из (23), (22) получаем, что |(xN, ) b| N, или Левая часть последнего неравенства приводит к неравенству (14).

Лемма 6.5 доказана полностью, неравенство (12) обосновано. Доказательство теоремы 6.1 закончено.

2.6.3 Теорема об основных свойствах интеграла Теорема 6.2. Пусть 2) D(s) – непрерывная (n n)-матрица, 3) класс допустимых управлений состоит из интегрируемых по Лебегу функций, принимающих значения из компакта U.

Тогда множество обладает следующими свойствами Утверждения а), б) теоремы 6.2 легко проверяются (см. доказательство теоремы 6.1), утверждения в), г) приводятся без доказательства.

Замечание 6.1. В теореме 6.2 не предполагается выпуклости компакта U ; при этом интеграл X оказывается всегда выпуклым. Проиллюстрируем это обстоятельство примером.

Пример 6.1. Пусть n = 1, D(s) 1, U = {1, +1} – множество, состоящее из двух точек 1 и +1 (U – невыпуклое множество). Найти множество X = Класс допустимых управлений У содержит управления (кроме этих управлений в У содержится много других управлений, которые, однако, для построения интеграла X не потребуются), а множество X (интеграл) содержит точки Из рисунка 6.1 ясно, что отрезок [1, +1] X, и так как для любой Построенное в этом примере множество X = [1, +1] выпукло, хотя компакт U = {1, +1} выпуклым не является.

В примере 6.1 интеграл X был найден на основании определения интеграла. Нахождение интегралов на основании определения, требующее перебора всех допустимых управлений из У, весьма неудобно для приложений. Здесь ситуацию можно сравнить с задачей вычисления интеграла Римана от функции действительного переменного: вычисление интеграла Римана на основании определения с помощью интегральных сумм в известном смысле неудобно для практики, и в ряде случаев интеграл удобно вычислять с помощью формулы Ньютона–Лейбница. Теоремы 6.1 и 6.2 позволяют находить интегралы от класса допустимых управлений по следующей схеме: сначала вычисляется опорная функция интеграла, а затем по опорной функции восстанавливается интеграл. Покажем, как эта схема применяется в конкретных задачах.

Пример 6.2. Пусть n = 2, В силу теоремы 6.2 множество X(T ) является выпуклым компактом. Найдём сначала его опорную функцию, привлекая теорему 6.1 о внесении знака опорной функции под знак интеграла:

c(X(T ), ) = Итак, два выпуклых компакта X(T ) и ST (0) имеют одинаковые опорные функции, отсюда, на основании свойства опорных функций (см.

формулу (14) раздела 2.5), следует совпадение этих множеств:

Таким образом, интеграл X(T ) является кругом радиуса T с центром в начале координат.

Выше мы воспользовались равенством esA = ; геометрический смысл этого равенства состоит в том, что длина вектора при повороте его на угол s сохраняется. Для прямого доказательства поэтому Пример 6.3. Пусть n = 2, A = Найти интеграл X = Действуя по той же схеме, получаем:

так как c({v, v}, ) = |(v, )|, (см. раздел 2.5). Полагая находим Следовательно, Заметим, что правая часть формулы (6), в отличие от примеров 6.2, 6.3, не всегда может быть найдена аналитически (на основе формулы Ньютона–Лейбница). В таких случаях интеграл в правой части формулы (6) может быть приближённо вычислен при фиксированном методами численного интегрирования.

2.6.4 Теорема о непрерывной зависимости интеграла от верхнего предела Теорема 6.3. При выполнении условий теоремы 6.2 множество непрерывно зависит от аргумента t, т.е. Хаусдорфово расстояние 2 Действительно, в силу теоремы 6.2 множества X(t ), X(t) являются выпуклыми компактами и расстояние Хаусдорфа между ними можно выразить в терминах их опорных функций (свойство опорных функций). Опорные функции этих множеств можно найти с помощью теоремы 6.1. Поэтому имеем:

h(X(t ), X(t)) = здесь – некоторое положительное число, t t, t +.

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

3 Линейная теория быстродействия 3.7 Постановка линейной задачи быстродействия Рассмотрим линейную задачу быстродействия в E n :

Здесь x – вектор фазовых координат объекта, A – матрица системы, u – управление, M0, M1 – множества начальных и конечных состояний объекта; класс допустимых управлений состоит из функций u(s) скалярного аргумента s, принимающих значения из множества U (E n ) и интегрируемых по Лебегу. Множество U называется областью управления. Начальный момент времени t0 фиксирован.

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

Основные вопросы линейной теории быстродействия (управляемость, необходимые условия оптимальности, достаточные условия оптимальности, существование оптимального управления) рассмотрены ниже в разделах 3.10-3.15.

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

3.8 Основные свойства множеств достижимости X(t) и управляемости Z(t) Эти множества введены в разделе 1.3, где мы установили следующее свойство.

Свойство 1 (представление множеств X(t) и Z(t) на основе формулы Коши):

имеют место формулы На формулах (1) и (2) основано изучение ряда простейших свойств множеств X(t), Z(t), которые приводятся ниже.

Свойство 2 (опорная функция множеств X(t), Z(t)):

имеют место формулы 2 Для получения формул (3), (4) следует использовать представление рассмотренных множеств в виде алгебраической суммы двух множеств (см. (1), (2), свойство 7 аддитивности опорной функции по первому аргументу, раздел 2.5) и теорему 6.1 из раздела 2.6 о внесении знака опорной функции под знак интеграла. Используя свойство 5, раздел 2.5, опорных функций, формулы (3), (4) можно записать в виде В правые части формул (5), (6) входят опорные функции множеств U, M0, M1 и матрица A, другими словами, опорные функции множеств достижимости и управляемости выражены в терминах исходных данных рассматриваемой линейной задачи быстродействия.

Свойство 3 (о компактности и выпуклости множеств X(t), Z(t)):

• если же M0, M1 conv (E n ), то X(t), Z(t) conv (E n ).

2 Действительно, множества X(t) и Z(t), в соответствии с формулами (1), (2), являются алгебраической суммой двух множеств. Вторые слагаемые (интегралы) по теореме 6.2 являются выпуклыми компактами. Первые слагаемые, представляющие собой линейное преобразование компактов M0, M1, являются компактами (проверить, что умножение матрицы на компакт даёт компакт; умножение матрицы на выпуклый компакт приводит к выпуклому компакту). Алгебраическая сумма двух компактов является компактом; алгебраическая сумма двух выпуклых компактов является выпуклым компактом. Эти соображения приводят к обоснованию свойства 3.

Замечание 8.1. Для одноточечных множеств M0, M1 множества X(t), Z(t) являются выпуклыми компактами.

Свойство 4 (непрерывная зависимость множеств X(t), Z(t) от времени t):

Упражнение 8.1. Доказать свойство 4, привлекая формулы (1), (2) и теорему 6.3 раздела 2.6.

3.9 Сопряжённое уравнение. Сопряжённая переменная. Лемма о сопряжённой переменной Рассмотрим линейное дифференциальное уравнение Уравнение называется сопряжённым уравнением для уравнения (1). Здесь – неизвестная n-мерная векторная функция аргумента t, A – матрица, полученная транспонированием из матрицы A, входящей в уравнение (1). Уравнение (2) является линейным однородным. Оно, очевидно, имеет тривиальное решение (t) 0. Это нулевое решение сопряжённого уравнения нас не интересует в контексте изучения необходимых условий оптимальности. Решение сопряжённого уравнения можно записать с помощью формулы Коши:

(вектор начальных условий задан в момент времени t0 ). В силу невырожденности экспоненциала (раздел 1.2) т.е. тривиальное решение (t) 0 уравнения (2) получаем только при нулевом начальном условии (t0 ) = 0.

Определение 9.1. Любое нетривиальное решение (t) сопряжённого уравнения (2) будем называть сопряжённой переменной.

Для получения сопряжённой переменной (t) следует решить сопряжённое уравнение (2) с некоторым ненулевым начальным условием.

Если начальное условие задано в момент времени t1, то вместо формулы (3) получаем формулу В дальнейшем изложении существенно используется следующая лемма.

Лемма о сопряжённой переменной. Пусть t0 < t1, t [t0, t1 ], X(t) X(t0, t, M0 ) – множество достижимости, Z(t) Z(t, t1, M1 ) – множество управляемости. Для любой сопряжённой переменной (t) имеют место следующие равенства кроме того, справедливы соотношения где x(t) = Ax(t) + u(t) для почти всех t [t0, t1 ], т.е. в формулах (7), (8) x(t) – любая траектория, отвечающая управлению u(t).

2 Равенства (5)-(8) устанавливаются непосредственной проверкой.

Проверим сначала равенство (7). На основании формулы Коши Тогда скалярное произведение фазовой и сопряжённой переменных допускает следующее преобразование:

(x(t), (t)) = e(tt0 )A x(t0 ) + e(st0 )A u(s) ds, e(tt0 )A (t0 )= Формула (7) доказана.

Проверим формулу (8). На основании формулы Коши Тогда (x(t), (t)) = Формула (8) доказана.

Проверим теперь формулу (5). Используя формулы (5) раздела 3.8, и (3) раздела 3.9, имеем Для доказательства формулы (6) следует воспользоваться формулами (6) раздела 3.8 и (4) раздела 3.9. Лемма о сопряжённой переменной доказана.

Замечание 9.1. Опорная функция множества достижимости X(t) на сопряжённой переменной (t), т.е. функция непрерывна по аргументу t вместе со своей производной Опорная функция множества управляемости Z(t) на сопряжённой переменной (t), т.е. функция непрерывна по аргументу t вместе со своей производной 3.10 Управляемость. Критерий управляемости. Основная лемма В разделе 3.10 вводится понятие управляемости, рассматривается критерий управляемости. С помощью критерия управляемости доказывается так называемая основная лемма, которая будет использована при выводе необходимых условий оптимальности в форме принципа максимума Понтрягина (раздел 3.11).

Рассматривается управляемый объект, описываемый уравнением Задан класс допустимых управлений У = УU, множества M0, M1, Поставим вопрос: можно ли при помощи какого-нибудь допустимого управления u(·) У, определённого на отрезке времени [t0, t1 ], перевести объект из множества M0 на множество M1 :

При положительном ответе на этот вопрос говорят об управляемости объекта. Исследование управляемости не связано с каким-либо критерием качества процесса управления (например, со временем перехода). Отрезок времени [t0, t1 ] считается заданным.

Определение 10.1. Объект называется управляемым на заданном отрезке времени [t0, t1 ] из множества M0 в множество M1, если существует допустимое управление u(·) У и отвечающая этому управлению траектория x(·) (т.е. x(t) = Ax(t)+u(t) для почти всех t [t0, t1 ]) с начальным условием x(t0 ) M0 такая, что x(t1 ) M1.

Из определения множества достижимости ясно, что объект управляем на заданном отрезке [t0, t1 ] из M0 в M1 тогда и только тогда, когда множество достижимости X(t1 ) X(t0, t1, M0 ) пересекается с множеством M1 :

Управляемость на [t0, t1 ] Так как X(t1 ), M1 (E n ), то, на основании утверждения (1) и первой части свойства 140 опорных функций (см. раздел 2.5), получаем необходимое условие управляемости в форме которое можно переписать, заменив на (t1 ), в виде Так как (t1 ) = 0, то этот ненулевой вектор в (3) можно рассматривать как значение сопряжённой переменной в момент времени t1.

Тогда, привлекая при t = t1 формулу (5) раздела 3.9 из леммы о сопряжённой переменной, условие (3) можно переписать в форме причём условие (4) должно выполняться для любой сопряжённой переменной (s):

Итак, получено необходимое условие управляемости в форме (4) (первая часть следующей теоремы).

Теорема (критерий управляемости).

1) При M0, M1 (E n ) условие (4) является необходимым условием управляемости объекта на заданном отрезке времени [t0, t1 ] 2) При M0, M1 conv (E n ) условие (4) является необходимым и достаточным условием управляемости объекта на заданном отрезке времени [t0, t1 ] из M0 в M1.

2 Часть 1) этой теоремы доказана выше. Для доказательства части 2) остаётся проверить, что в случае выпуклых компактов M0, M1 условие (4) влечёт управляемость. Условие (4) равносильно условию (3), а условие (3) может быть записано в форме (2), т.е.

Последнее условие и выпуклость компактов X(t1 ), M1 на основании следствия из свойства 14 раздела 2.5, влекут соотношение равносильное управляемости, см. формулу (1). Критерий управляемости установлен.

Другая формулировка критерия управляемости. Перепишем условие управляемости (4), заменив там сопряжённую переменную по формуле (3) раздела 3.9:

Введём функцию (функция управляемости). Положим Ясно, что условие управляемости (4) равносильно каждому из следующих условий:

Неравенства (6), (6 ), (6 ) являются другой формой условия управляемости (4) в терминах функции управляемости (5). Условия управляемости в форме (6 ), (6 ) удобны при рассмотрении конкретных примеров. Чтобы установить неуправляемость, достаточно указать такой вектор S, для которого 0 () < 0.

Упражнение 10.1. Записать условие управляемости в терминах функции управляемости Какая связь существует между функциями управляемости (5) и (7)?

Пример 10.1. Пусть n = 2, t0 = Исследовать управляемость объекта из M0 в M1 на отрезках времени а) [0, /2], б) [0, ], в) [0, 2].

Множества M0, M1 (см. рисунок 10.1) – выпуклые компакты, и условие (6 ) является необходимым и достаточным условием управляемости.

Для решения вопроса об управляемости найдём функцию управляемости 0 () на отрезке [0, t1 ]. Имеем:

Находим теперь функцию управляемости (5) и число Условие управляемости (6 ) принимает вид Таким образом, на отрезке [0, t1 ] объект управляем при t1 и неуправляем при 0 < t1 <. В частности, на отрезке [0, ] объект неуправляем, а на отрезках [0, ], [0, 2] объект управляем.

В примере 10.1 вопрос об управляемости был решён аналитическими средствами на основе критерия управляемости. Чтобы выяснить геометрические причины управляемости или неуправляемости на данном отрезке, мы в примере 10.2 изучим динамику множества достижимости X(t) = X(0, t, M0 ) объекта из примера 10.1.

Пример 10.2. Найти множество достижимости X(t) для объекта из примера 10.1 в произвольный момент времени t 0.

Привлекая формулу (5) раздела 3.8, (t0 = 0) найдём опорную функцию множества достижимости X(t). Имеем:

Тогда подстановка (9), (10) в (8) даёт c(X(t), ) = (3 cos t)1 + (3 sin t)2 + ( + t) = т.е. множество достижимости X(t) является кругом радиуса r(t) = + t, центр которого a(t) движется по окружности радиуса 3 в направлении вращения часовой стрелки (см. рисунок 10.2).

Ясно, что При 0 < t < множество достижимости X(t) не пересекается с множеством M1 (что соответствует неуправляемости объекта на отрезке [0, t], 0 < t < ). В момент времени t = возникает первый контакт множества достижимости с множеством M1 в точке (, 0) (время 0 = – минимальное время перехода из M0 в M1, т.е.

время быстродействия). При всех t множество X(t) пересекается с M1, что соответствует управляемости объекта на любом отрезке [0, t], где t.

Упражнение 10.2. Построить множества X 3, X(2), X(3).

Упражнение 10.3. Построить множество управляемости Z(t) = взаимное расположение множеств X(t) и Z(t) при 0 t.

Рассмотрим множества X() и M1, имеющие одну общую точку (, 0). Для этих множеств должно выполняться условие управляемости Это условие можно проверить непосредственно:

Обратим внимание на то, что для единичного вектора = выполняется равенство т.е. неравенство (12) при = превращается в равенство. Вектор, для которого выполнено равенство (13), имеет простой геометрический смысл (см. рисунок 10.3): – вектор нормали к гиперплоскости (прямой, проходящей через общую точку (, 0) множеств X() и M1 ), которая “разделяет” множества X() и M1.

Напомним, что в рассматриваемом примере момент времени t = есть первый момент касания множества достижимости X(t) с множеством конечных состояний M1.

Основная лемма. Пусть 2) t1 t0 = min, т.е. t1 t0 – оптимальное время перехода из M в M1 в рассматриваемой задаче быстродействия Тогда существует такая сопряжённая переменная (t), для которой в условии управляемости реализуется знак равенства:

или, в более подробной записи, 2 Доказательство. По условию основной леммы Условие (14) на основании теоремы об управляемости, часть 2), равносильно условию Рассмотрим последовательность {tk }, t0 < tk < t1 ; tk t1 0 при k. Из (15) следует, что Так как X(tk ), M1 conv (E n ), то из (17) в силу следствия из свойства 14, раздел 2.5, Из последовательности {pk } единичных векторов выберем сходящуюся к некоторому вектору p S подпоследовательность; не изменяя обозначений, будем считать, что pk p при k. Используя непрерывность опорной функции по совокупности двух аргументов, непрерывную зависимость множества достижимости X(t) от t, предельные соотношения tk t1, pk p (k ) и выполняя в (18) переход к пределу при k, получаем неравенство Полагая в (16) (t1 ) = p, запишем неравенство Сравнение (19) с (20) приводит к равенству которое доказывает утверждение основной леммы с сопряжённой переменной (t), удовлетворяющей условию (t1 ) = p. Основная лемма доказана.

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

Упражнение 10.4. Показать, что утверждение основной леммы без предположения о выпуклости компактов M0 и M1 неверно. Рассмотреть пример, в котором n = 2, A = O, t0 = 0, Замечание 10.1. Анализ доказательства основной леммы показывает, что её второе условие можно заменить следующим: существует последовательность {tk }, сходящаяся к t1, такая, что Это замечание объясняет, почему сформулированный принцип максимума Понтрягина, доказательство которого опирается на основную лемму, является только необходимым условием оптимальности, но в общем случае не является достаточным условием оптимальности в линейной задаче быстродействия. Геометрическая идея построения соответствующих примеров связана с тем, что множество достижимости X(t) может (после первого момента t1 встречи с M1 ) оторваться от множества M1 в некоторый момент t = t2 > t1 (при этом X(t2 ) M1 =, и X(t) M1 = при малых tt2 > 0); впоследствии при некотором t = t3 > t2 может произойти повторная встреча множества достижимости X(t) с M1 (X(t3 ) M1 = ; X(t) M1 = при малых t t3 < 0). В таких ситуациях на отрезках [t0, t1 ], [t0, t2 ], [t0, t3 ] в случае выпуклости компактов M0, M1 имеет место утверждение основной леммы.

Упражнение 10.5. Проиллюстрировать замечание 10.1 конкретными примерами.

3.11 Принцип максимума Понтрягина. Теорема о необходимых условиях оптимальности в линейной задаче быстродействия 3.11.1 Постановка задачи Рассмотрим линейную задачу быстродействия определяемую набором исходных данных {A, M0, M1, У = УU, t0 }.

Напомним, что M0, M1, U (E n ). Изучим сейчас основной вопрос нашего курса – теорему о необходимых условиях оптимальности для линейной задачи быстродействия (1) (принцип максимума Понтрягина). При доказательстве этой теоремы существенно используется основная лемма, доказанная в разделе 3.10.

3.11.2 Основная лемма В случае M0, M1 conv (E n ), t1 t0 = min, существует сопряжённая переменная (t), для которой выполняется равенство 3.11.3 Принцип максимума Понтрягина Рассмотрим пару где 1) u(t) У, т.е. u(t) – допустимое управление, определённое на отрезке t0 t t1, причём в каждый момент времени t [t0, t1 ] 2) x(t) – траектория, отвечающая управлению u(t), т.е. x(t) = Ax(t) + u(t) для почти всех t [t0, t1 ], и удовлетворяющая краевым условиям x(t0 ) M0, x(t1 ) M1.

Будем говорить, что эта пара (x(t), u(t)) удовлетворяет принципу максимума Понтрягина на отрезке [t0, t1 ], если существует такая сопряжённая переменная (t) (ненулевое решение сопряжённого уравнения = A ), что выполнены следующие три условия:

а) условие максимума:

(u(t), (t)) = c(U, (t)) б) условие трансверсальности на множестве M0 :

(x(t0 ), (t0 )) = c(M0, (t0 )), в) условие трансверсальности на множестве M1 :

(x(t1 ), (t1 )) = c(M1, (t1 )).

Геометрический смысл условий а), б), в) указан на рисунке 11.1.

Содержанием настоящего подраздела 3.11.3 является введение терминологии, разъясняющей, что подразумевается, когда говорят, что “пара (x(t), u(t)) удовлетворяет принципу максимума Понтрягина на отрезке [t0, t1 ]”.

3.11.4 Теорема о необходимых условиях оптимальности в форме принципа максимума Понтрягина Теорема 11.1 (основная теорема линейной теории быстродействия). Пусть 2) пара (x(t), u(t)), t0 t1, решает линейную задачу быстt родействия (1), т.е.

Тогда пара (x(t), u(t)) удовлетворяет принципу максимума Понтрягина на отрезке [t0, t1 ].

Структура сформулированной теоремы отражена на рисунке 11.2.

Оптимальность пары 2 По условиям теоремы В соответствии с основной леммой существует сопряжённая переменная (t), с которой выполнено равенство (2):

здесь X(t1 ) = X(t0, t1, M0 ) – множество достижимости. Покажем, что с этой же сопряжённой переменной (t) выполняются условия а), б), в) принципа максимума Понтрягина.

Вычитая из (2) почленно очевидное равенство получаем Каждая из двух разностей в левой части (3) неотрицательна; это следует из определения опорной функции и включений Поэтому каждая из этих разностей равна нулю, т.е.

Равенство (4) доказывает справедливость условия в) принципа максимума Понтрягина (условие трансверсальности на множестве M1 ).

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

Используя лемму о сопряжённой переменной (раздел 3.10, формулы (5) и (7) при t = t1 ), запишем условие (5) в форме c(M0, (t0 ))(x(t0 ), (t0 )) + Так как x(t0 ) M0, то так как u(s) U, s [t0, t1 ], то Из (6), (7) и (9) следуют равенства Равенство (10) равносильно условию б) принципа максимума Понтрягина (условию трансверсальности на множестве M0 ). Из условий (11) и (8) следует, что Последнее утверждение доказывает условие а) принципа максимума Понтрягина (условие максимума).

3.11.5 Лемма об эквивалентной формулировке принципа максимума Понтрягина в терминах множеств достижимости X(t) и управляемости Z(t). Геометрическая интерпретация сопряжённой переменной (t) В этом пункте мы не будем предполагать оптимальности пары (x(t), u(t)), t0 t t1, и выпуклости компактов M0, M1.

Лемма. Пусть M0, M1 (E n ). Равносильны следующие два условия:

I. Пара x(t), u(t)), t0 t1, удовлетворяет принципу максимуt ма Понтрягина с сопряжённой переменной (t).

II. Выполняются равенства с сопряжённой переменной (t).

Здесь X(t) = X(t0, t, M0 ) – множество достижимости, Z(t) = Z(t, t1, M1 ) – множество управляемости, (t) – сопряжённая переменная (в каждом из условий I и II участвует одна и та же сопряжённая переменная).

2 Проверим сначала, что условие I влечет условие II. Пусть выполнено условие I. Тогда c(X(t), (t)) = = (x(t), (t)), т.е. доказано равенство (12). Равенство (13) доказывается совершенно аналогично с помощью леммы о сопряжённой переменной:

= (x(t), (t)).

Проверим теперь, что условие II влечёт условие I. Пусть выполнено условие II; полагая в (12) t = t0 и в (13) t = t1, получаем условия трансверсальности принципа максимума Понтрягина; используя (12) и выполняя почленное вычитание формул (5) и (7) из раздела 3.9, получаем выполнив здесь дифференцирование по аргументу t, приходим к соотношению т.е. к условию максимума а) принципа максимума Понтрягина.

Равенства (12), (13) позволяют дать геометрическую интерпретацию сопряжённой переменной с привлечением множеств X(t) и Z(t).

Пусть пара (x(t), u(t)) удовлетворяет принципу максимума Понтрягина на отрезке [t0, t1 ] с сопряжённой переменной (t). Рассмотрим гиперплоскость вектором нормали которой служит сопряжённая переменная (t). Точка x(t) принадлежит каждому из множеств X(t), Z(t), (t). Гиперплоскость (t) в каждый момент времени t [t0, t1 ] разделяет множества достижимости X(t) и управляемости Z(t) (см. рисунок 11.3).

Задача 11.1. Пусть пара (x(t), u(t)) удовлетворяет принципу максимума Понтрягина на отрезке [t0, t1 ] с сопряжённой переменной (t).

Доказать, что гиперплоскость (t) разделяет множества X(t) и Z(t), т.е.

(см. рисунок 11.4).

3.12 Теорема существования оптимального управления При доказательстве теоремы существования оптимального управления в линейной задаче быстродействия предполагается компактность множеств M0, M1 (выпуклости этих множеств не требуется) и существенно используется компактность множества достижимости X(t) и его непрерывная зависимость от времени t (см. раздел 3.8); кроме того, предполагается управляемость объекта из M в M1 на некотором конечном отрезке времени [t0, T ].

В случае выпуклости компактов M0, M1 доказательство теоремы сильно упрощается (см. ниже замечание 12.1).

Теорема 12.1. Пусть 2) класс допустимых управлений У состоит из функций, интегрируемых по Лебегу;

3) на некотором конечном отрезке времени [t0, T ] объект управляем Тогда в классе допустимых управлений У существует оптимальное управление u(t), t0 t t1, t1 T, для рассматриваемой линейной задачи быстродействия.

2 Пусть X(t) = X(t0, t, M0 ) – множество достижимости. По третьему условию теоремы т.е. множество X(T ) имеет хотя бы одну общую точку с множеством M1 (см. рисунок 12.1).

Рассмотрим множество Это множество непусто, так как T I, см. (1), и ограничено снизу числом t0. Положим Из определения числа t1 следует, что Мы покажем ниже, что Выполнение соотношений (2) и (3) означает оптимальность времени t1. Из (3) и определения множества достижимости X(t1 ) следует существование допустимого управления u(t), t0 t1, переводяt щего объект из множества M0 на множество M1. Это управление и является оптимальным управлением для рассматриваемой линейной задачи быстродействия.

Итак, остаётся доказать утверждение (3). Это доказательство опирается на следующую лемму.

Лемма 12.1. Существует такая точка x M1, что 2 Возьмём последовательность {T k } такую, что Возможность выбора такой последовательности {T k } вытекает из определения числа t1. Существует такая точка xk E n, что Так как xk M1 k, и M1 – компакт, то из последовательности {xk } можно выбрать сходящуюся к некоторой точке x M1 подпоследовательность. Не изменяя обозначений, будем считать, что Из непрерывной зависимости множества достижимости X(t) от времени t (свойство 4, раздел 3.8) и предельного соотношения T k t (k ) следует, что Из (5), (6) следует, что для любого числа > т.е.