Методы линейной алгебры в вычислительных задачах оптимального управления тема автореферата и диссертации по математике, 01.01.07 ВАК РФ

Факультет Вычислительной математики и кибернетики

Специализированный совет N Д.053.05.37

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

Сагитов Модест Спартакович

УДК 519.612

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

Специальность 01.01.07 - "Вычислительная математика" АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-математических наук

Москва, 1992

Работа выполнена в Московском государственном университете (МГУ) им. М.В. Ломоносова на кафедре общей математики факультета Вычислительной математики и кибернетики (ВМК)

Научный руководитель: доктор физико-математических наук, доцент X.Д. Икрамов.

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

доктор физико-математических наук, в.н.с. Е.Е. Тыртышников,

кандидат физико-математических наук И.Г. Мамедов.

Ведущая организация: Институт проблем управления (ИПУ) РАН

/г 3о

Защита состоится "2ч" 7" 199£г. в час. на заседании Специализированного Совета N Д.053.05.37 МГУ им. М.В. Ломоносова по адресу 119899 Москва, Ленинские горы, МГУ, факультет вычислительной математики и кибернетики, ауд. 686.

С диссертацией можно ознакомиться в библиотеке МГУ.

Автореферат разослан "сС, о ¿,199$ г.

Ученый секретарь Специализированного Совета, проф.

.И. Моисеев

- 3-

Общая характеристика работы

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

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

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

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

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

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

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

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

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

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

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

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

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

Апробапия работы. Основные положения и результаты диссертационной работы докладывались и обсуждались на научных семинарах факультета ВМК МГУ, Отдела вычислительной математики РАН и Института системного анализа РАН.

Структура и обърм работы. Диссертация состоит из введения, двух глав и списк{ литературы из 40 наименований. Основная часть работы изложена на 86 странице машинописного текста, содержит 9 рисунков и одну таблицу.

-5-

Содержание работы

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

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

В параграфе 1.1 содержатся необходимые факты линейной алгебры и теории матриц.

, - (°п 7"

Введем матрицу и — I _^ 0 )'

Определение /. (2пх2п¡-матрица М называется гамильтоновой, N называется J-симметричной, 5 - симплектической, если

(1) гш = -мт,

(2) 1ТШ = КТ,

(3) 8Т18 = 1.

Важную роль в работе играет известная

Теорема I. Пусть А и В - перестановочные тхт-матрицы, причем А имеет блочно-треугольную структуру (А = , к - количество диагональных блоков, а блоки Ау -

нулевые при 1>]), и сг(Ац)П о(Ац) = 0 при (здесь и далее а(А) - спектр матрицы А). Тогда матрица В также верхняя блочно-треугольная, причем ее блочное строение совпадает со строением А.

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

Параграф 1.3 посвящен описанию известного метода Шура решения АУР

(4) ХвХ - А т X - ХА - Б = О,

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

для п-мерного устойчивого инвариантного подпространства гамильтоновой матрицы

с последующим решением относительно X уравнения XV11 = [/21- При этом столбцы матрицы и\ суть первые п столбцов ортогональной матрицы и, приводящей М к форме Шура

(6) итми = Т = , а(Гц) С С".

В параграфе 1.4 описан алгоритм Ван Лоана вычисления спектра матрицы М. В этом

2

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

следующим образом:

1. Сформировать матрицу N = М , являющуюся 1-симметричной.

2. Найти блочно-треугольную матрицу N1 (назовем ее J-формой Шура для N0 и ортогональное симплектическое преобразование 0 к этой форме:

(7) Ы\ = (^ЫО. = ^ , К = —КГ, Я ~

верхняя треугольная. 3. Вычислить

а{Ы) = \-Vli, уПх , ..., -{Аь = о(Я).

где

Центральным в главе 1 является параграф 1.5, посвященный методу блочного приведения гамильтоновой матрицы к форме Шура. Несмотря на то, что векторы Шура матриц М и 2

N = М , вообще говоря, не совпадают, с помощью представления (7) можно найти такой ортонормированный базис, в котором блочно-треугольная структура М будет нетривиальной. Построим такой базис, предполагая для краткости изложения, что М имеет вещественный простой спектр. Изменения, которые необходимо внести в алгоритм для остальных случаев, рассмотрены в диссертации.

1. Приводим матрицу (7) к обычной форме Шура:

Ы2 = р 'N1 Р, где Р =

(1п (М

, Р = ( еп,еп-1,..., е2, е{) .

2. Вычисляем ортогональную матрицу V, переупорядочивающую верхнюю треугольную, с диагональюГП, Глл, Глл, • •., Г1 1, матрицу N2 к другой форме Шура,

N3 = УтМг V, диагональ которой имеет вид

ГЦ, ГЦ, Г22, Г22, ГПп, Гпп.

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

з. г = ()руим = гтмг,у»й=гтмг.

Т 2 - ~

на основании теоремы 1 и того, что N3 = 2 М г коммутирует с М, выводим, что А/ имеет

ту же блочнотреугольную структуру, что и N3-

4. Завершает алгоритм преобразование матрицы М к искомой форме Шура (6).

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

2 3

собственных значений. Метод Шура требует 146^ л операций в первом случае и (в среднем)

159.5 л во втором. Для метода блочного приведения аналогичные характеристики составля-

3 3

ют соответственно 66.5 л и 105.5 п операций.

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

В параграфе 1.8 аналогичный подход применяется для решения дискретного уравнения Риккати. Здесь ,1-форма Шура (7) вычисляется для .1-симметричной матрицы Б + Б"', где Б -симплектическая сопровождающая матрица дискретного уравнения Риккати. Вычислительные характеристики нового метода в дискретном и непрерывном случае эквивалентны.

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

Пусть вычисленная форма Шура (2п*2п) -матрицы М (5) имеет вид

Х1МХ = {Х+ЦГ)ТМ(Х+Щ=Ъ= 'Еи Е\г

Ег\ Егг

'Ъ\ \ Ъ\2 В\ \ В\2

= В+Е =

%2\ Ъгг \ / В2\ В22 \ /

,где В - точное произведение ХТМХ, 2,,- = + Ъц ,

1 — 1,2, Кц имеют точную форму Шура, а([?11) лежит в левой, а а(Я22) - в правой открытой полуплоскости;X = (XI I Х2 ]-точкаяортогональнаяматрица.,являю1цаясябазиснойдля приближенно вычисленного искомого инвариантного подпространства.

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

* =

♦ || или ||*|| =|МЬ« = »¿И " + II 2^22 II +НЕпИ + 11^22 И, Г 2

Ц= II #12 и, >7= "ВиМгоах = шахЫ,^], (р Р = РВпР, <р Р = РЪпР,у = 11 #21II, У = II ®21 II, Ушах = тах{у, утах},

ТР = РВи-В22Р , д = IIГ -1 \\-'ТкР = РПп-КггР, бк= II Тн И^1

к = ут]д~2, К к = уудя2, <5т!п = тт(б, <5я), Кшх = Утах»7тах<5т!п,

а = 4 ктлх,Ь = утахе <5т1п + ¿т/п IIЕ 11(1 + утах(1 + 2<5ш!п)).

Известно, что если оператор Т не вырожден и к < 0.25, то точная базисная матрица У инвариантного подпространства матрицы М (5) может быть вычислена по формуле

У = +Х2Р, где Р - решение уравнения

ТР = Я21 -<р Р.

Сформулируем основной результат параграфа.

Теорема 2. Пусть операторы Т и Тц не вырождены и <тах < 0.25. Тогда для последовательности {Р^},

(8) Я=Гл1г2ь

(9) Р> = Т*\Ъгх ~ ^Я-1),1 = 1,2,...

справедливы неравенства:

(10) I 1Р, - Р I I < Ь (1-а) + а' \\Po- Р II

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

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

В параграфе 1.10 приведены результаты тестовых расчетов. Они показывают, что метод блочного приведения, объединенный с процедурой итерационного уточнения (8), (9), дает решения АУР, сравнимые по точности с полученными методом Шура.

ГЛАВА 2 посвящена исследованию свойств матричных пучков, связанных с обобщенными матричными уравнениями Риккати. Выделены классы вещественных и комплексны-хобобщенных задач на собственные значения, допускающие конечную редукцию к задачам половинной размерности. Построены конечные симплектические алгоритмы, осуществляющие такое расщепление.

Параграф 2.1 содержит необходимые сведения об обобщенных АУР и сопровождающих спектральных задачах. Вводится определение J-симметричного матричного пучка, названного так из-за сходства стандартной и обобщенной J-симметричных задач на собственные значения. Здесь же в виде лемм сформулированы основные свойства таких пучков.

Определение 2. (2п* 2п)-матричный пучок (N - X L) называется J-симметричным, если

NJLT = UNT.

В параграфе 2.2 предложен конечный симплектический ортогональный алгоритм, позволяющий свести вещественную регулярную Симметричную обобщенную проблему собственных значений к задаче вдвое меньшей размерности. В результате применения этого алгоритма будет построена следующая форма пучка (N - X L):

Q(N - Я L)Z = (А - Я В),

где Q ортогональная, Z - ортогональная и симплектическая,

А] ], А22 - соответственно верхняя и нижняя хессенберговы, В11, В22 - верхняя и нижняя треугольные. При этом спектры пучков (All - X Bl 1) и (А22 - Я В22) совпадают.

Параграф 2.3 посвящен комплексной J-симметричной обобщенной проблеме собственных значений. Вводятся симплектические элементарные матрицы, используемые при расщеплении Симметричного пучка.

Доказанные в параграфах 2.2 и 2.3 утверждения мо1ут быть сформулированы следующим образом:

Теорема 3. Пусть (N - A L) - регулярный J-симметричный (вещественный или комплексный) пучок размеров 2п*2 п. Тогда его спектр состоит из пар ( АД ).

Построен конечный симплектический алгоритм приведения J-симметричного пучка к виду (11). Вычисленное в ходе алгоритма преобразование Z, вообще говоря, уже не является унитарным, и можно гарантировать лишь условную устойчивость процесса. Именно: каждое симплектическое преобразование пучка (N - A L) увеличивает его норму не более, чем в

<р = (VI + 1) /2раз.

В параграфе 2.4 проведен подсчет требований к памяти и вычислительной сложности алгоритмов параграфов 2.2 и 2.3, а сводка результатов тестовых расчетов содержится в параграфе 2.5.

Основные результаты работы

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

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

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

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

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