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

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

Воронцов Юрий Олегович

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

01.01.07 — Вычислительная математика

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

11 НАР 2015

Москва 2014

005560368

005560368

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

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

профессор Икрамов Хаким Дододжанович Официальные оппоненты: Капорин Игорь Евгеньевич,

Ведущая организация: Институт вычислительной математики РАН

Защита состоится 3 апреля 2015 г. в 15:00 на заседании диссертационного совета Д 501.002.09 при Московском государственном университете имени М.В. Ломоносова по адресу: 119991, Москва, Ленинские горы, дом 1, стр. 4, НИВЦ МГУ.

С диссертацией можно ознакомиться в Научной библиотеке МГУ имени М.В. Ломоносова (Ломоносовский проспект, 27) и на сайте: http://srcc.msu.ru/

Автореферат разослан . 2015 года.

Ученый секретарь

доктор физико-математических наук, Вычислительный центр им. A.A. Дороницына РАН, главный научный сотрудник

Козубская Татьяна Константиновна, доктор физико-математических наук, Институт прикладной математики им. М.В. Келдыша РАН, заведующая сектором

диссертационного совета

В. В. Суворов

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

Актуальность работы

Матричное уравнение Сильвестра АХ + ХВ = С, также иногда называемое непрерывным уравнением Сильвестра, и матричное уравнение Стейна X + АХ В = С, в свою очередь, называемое иногда дискретным уравнением Сильвестра, а также их частные случаи — уравнения Ляпунова АХ + ХАТ = С и X — АХАТ = С, представляют собой хорошо изученные и часто встречающиеся (например, в теории дифференциальных уравнений и теории оптимального управления) классы матричных уравнений. Давно известны условия однозначной разрешимости этих уравнений, существуют численные алгоритмы для их решения, например, алгоритмы Бартелса-Стыоарта и Голуба-Нэша-Ван Лоана.

Транспонированный аналог уравнения Сильвестра АХ + ХТВ = С начал привлекать внимание исследователей сравнительно недавно. Для этого уравнения, а также для уравнений АХ + Х'В = С, АХ + ХВ — С, (все эти уравнения мы будем называть уравнениями типа Сильвестра) по аналогии с уравнением Сильвестра может быть поставлен вопрос об исследовании на условия однозначной разрешимости и построении численных алгоритмов. Актуальность исследования такого рода уравнений не вызывает сомнений. Приведем несколько примеров, показывающих, почему изучение такого рода уравнений оправданно. Уравнение АХ + ХТВ = С впервые было встречено нами в статье Piao F., Zhang Q., Wang Z. (J. Franklin Inst. 2007. V. 344. N 8. P. 10561062), где оно было исследовано при дополнительном предположении С = Ст. Условия разрешимости и описание общего решения были даны в терминах обобщенных обратных для матриц А и В и связанных с ними проекторов. Эти условия не вполне конструктивны и трудны для проверки. Однородное уравнение АХ + ХтВ = 0 было исследовано

в статье Teran F., Dopico F.M. (Linear Algebra Appl. 2011. V. 434. N 1. P. 44-67) в частном случае В = А. Мотивировкой авторов было то обстоятельство, что множество {ХА + АХТ : X е Спхп} есть касательное пространство (вычисленное в точке А) орбиты матрицы А под действием конгруэнций. Коразмерность этой орбиты есть в точности размерность пространства решений уравнения ХА + АХТ = 0. Основным результатом работы было установление канонической структуры матриц общего положения относительно конгруэнций. Подобным образом теми же авторами (Electronic Journal of Linear Algebra. 2011. V. 22. Р. 448-465) исследовано уравнение АХ + X"А = 0. В публикации Kressner D., Schröder С., Watkins D. S. (Numerical Algorithms. 2009. V. 51. N 2. P. 209-238) уравнения АХ + XTB — Си АХ + Х'В = С возникают при построении алгоритма для палиндромных проблем собственных значений Ах = ААтх и Ах = \А'х. В процессе приведения матрицы А к антитреугольному виду возникает необходимость численного решения этих уравнений. В статье George А., Ikramov Kh. D., Matushkina E. V., Tang W.-P. (SIAM J. Matrix Anal. Appl. 1995. V. 16. N. 4. P. 11071126) сформулированы условия однозначной разрешимости и численный алгоритм для решения уравнения АХ + ХВ = С.

По аналогии с уравнениями типа Сильвестра, уравнениями типа Стейна будем называть уравнения Х+АХТВ - С, Х+АХ"В = С, Х+АХВ = С. Первое из них частично было исследовано в публикации Zhou В., Lara J., Duan G.-R. (Linear Algebra Appl. 2011. V. 435. N 6. P. 1370-1398). Естественным образом возникает вопрос о завершении этого исследования. Тема разрешимости других двух уравнений, напротив, исследована в этой публикации исчерпывающим образом.

Цель работы

Целью данной работы является исследование матричных уравнений

типа Сильвестра и Стейна, а также матричных уравнений, возникающих в качестве сопряженных уравнениям типа Сильвестра, на условия однозначной разрешимости и построение для этих уравнений алгоритмов численного решения, в том числе специальных, соответствующих случаям самосопряженности уравнений. Также целью является исследование квадратичного уравнения ХТБХ + АХ + ХТВ + С = 0 и полуторалинейного уравнения Х'БХ + АХ + Х'В + С = 0 на условия разрешимости и поиск алгоритма построения одного из решений.

Новые научные результаты, выносимые на защиту

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

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

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

Научная новизна работы, основные идеи

Для матричных уравнений АХ + ХТВ = С, АХ + Х*В = С, АХ + ВХТ = С, АХ + ВХ* = С, X + АХТВ = С, ХТБХ + АХ + ХТВ + С = 0 и Х'ОХ + АХ + Х'В + С = 0 разработаны и реализованы эффективные алгоритмы их численного решения. Впервые численно исследован случай, когда операторы, ассоциированные с матричными уравнениями являются самосопряженными. Созданы эффективные реализации алгоритмов в виде МаЫаЬ функций.

Условия однозначной разрешимости, полученные для уравнений АХ + ХТВ = С, АХ + Х'В = С, АХ + ВХТ = С, АХ+ВХ' = С, X+АХТВ = С, сформулированы в терминах собственных значений матриц и матричных пучков, являясь, таким образом, удобным инструментом в теоретических исследованиях.

Для уравнений ХтОХ+АХ+ХТВ+С = О, Х'ОХ+АХ+Х'В+С = О даже в случае их конечной разрешимости характерно наличие многих решений. Впервые получены условия разрешимости этих уравнений при некоторых ограничениях, наложенных на их матричные коэффициенты. Для построения конкретных решений был применен другой подход, основанный на вычислении нейтральных подпространств ассоциированных матриц.

Практическая значимость работы

Разработаны численно устойчивые прямые ортогональные методы решения уравнений АХ + ХТВ — С, АХ + Х*В = С, АХ + ВХТ = С, АХ + ВХ* = С, X + АХТВ = С. Сложность алгоритмов составляет 0(п3) арифметических операций, где п здесь и далее обозначает порядок матричных коэффициентов уравнения. Для самосопряженных уравнений типа Сильвестра и типа Стейна также разработаны специальные ортогональные алгоритмы, существенно превосходящие по скорости алгоритмы для уравнений общего вида.

Для уравнений ХтОХ+АХ+ХтВ+С = 0 и ХЮХ+АХ+Х'В+С = О на основе техники нейтральных подпространств разработаны ортогональные алгоритмы нахождения одного из решений.

Личный вклад автора

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

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

Соответствие диссертации паспорту научной специальности

Содержание и результаты работы соответствуют паспорту специальности 01.01.07, а именно соответствуют областям исследований:

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

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

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

Апробация работы

Основные результаты диссертации докладывались на следующих семинарах:

Научный семинар кафедры вычислительных методов факультета ВМК МГУ под руководством профессора А. В. Гулина.

"Матричные методы и вычисления"; научный руководитель — чл,-корр. РАН Е. Б. Тыртышников; Институт вычислительной математики РАН.

Научно-методологический семинар НИВЦ МГУ; научный руководитель — профессор А. В. Тихонравов.

Часть результатов работы была удостоена диплома победителя конкурса грантов О. Дерипаски 2012 года.

Публикации

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

Структура и объем работы

Диссертация состоит из бведения, четырех глав основного текста, списка литературы и приложения.

Объем диссертации — 134 страницы. Библиография включает в себя 45 наименований.

Краткое содержание работы

Введение

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

Глава 1. Матричные уравнения.

В этой вводной главе рассмотрены уравнения Сильвестра

АХ + ХВ = С (1)

и Стейна

X + АХ В = С, (2)

а также квадратичное уравнение

ХБХ 4- АХ + ХВ + С = 0. (3)

В §1 подробно изложено получение условий однозначной разрешимости уравнения Сильвестра. Детально описан численный алгоритм Бартелса-Стьюарта. Ввиду существенной аналогии подробности получения условий однозначной разрешимости и численного алгоритма для уравнения Стейна опущены. Это уравнение рассматривается в §2. Для квадратичного уравнения (3) в §3 описывается метод инвариантных подпространств,

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

Содержание главы в своей основе представляет собой изложение известного материала. Этот материал упрощает понимание последующих глав.

Глава 2. Матричные уравнения типа Сильвестра и Стейна. Условия разрешимости и численные алгоритмы.

В главе 2 изучаются уравнения

АХ + ХТВ = С, (4)

АХ + Х'В = С, (5)

АХ + ВХТ = С, (6)

АХ + ВХ' = С, (7)

X + АХТВ = С. (8)

Исследованию первых двух из них посвящен §1. Между этими уравнениями много общего, и мы посчитали целесообразным объединить их, введя обобщенное уравнение

АХ + Xя В = С. (9)

Символ пН" может быть заменен на символ операции транспонирования "Т" либо на символ операции эрмитова сопряжения "*". Условия однозначной разрешимости уравнения (9) удается сформулировать в терминах пучка

А + \ВН. (10)

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

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

При построении алгоритма численного решения уравнения (9) пучок (10) мы считали регулярным. Будучи удобным теоретическим инструментом, форма Вейерштрасса мало пригодна в практических расчетах. Хорошо известно, что задача вычисления формы Вейерштрасса (как и ее частный случай — вычисление жордановой формы квадратной матрицы) численно неустойчива. Поэтому разработан прямой ортогональный алгоритм для численного решения уравнения (9), который можно рассматривать как аналог алгоритма Бартелса-Стьюарта для уравнений Сильвестра, описанного в §1 главы 1. Применением С^-алгоритма исходное уравнение приводится к уравнению того же типа с треугольными матричными коэффициентами А и В. Полученное матричное уравнение эквивалентно последовательности систем уравнений малого порядка относительно коэффициентов искомого решения. Посредством численных примеров моделируется ситуация, когда "почти" нарушены условия однозначной разрешимости. Прослежено ухудшение качества вычисленного решения в этой ситуации. Для решения уравнения (9) в случае прямоугольных матриц предложено использовать метод наименьших квадратов.

В начале §2 объясняется, каким образом уравнения (6) и (7) возникают в качестве сопряженных к уравнениям типа Сильвестра. Эти уравнения также удобно объединить обобщенным уравнением

АХ + ВХН = С. 10

(П)

Мы показываем, что оператор, определяемый левой частью уравнения (11), является в том или ином смысле сопряженным к оператору, определяемому левой частью уравнения

А'Х 4- Хи{В*)п = D. (12)

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

А + А В. (13)

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

§3 начинается с обзора результатов статьи Zhou, Lam, Duan (см. стр. 4), посвященной уравнениям типа Стейна. В этой публикации найдены условия однозначной разрешимости уравнений

X + АХ'В = С (14)

и

X + АХВ = С. (15)

Этим уравнениям сопоставляются эквивалентные уравнения Стейна, что позволяет сразу же предложить численный метод, основанный на использовании алгоритма из §2 главы 1. Не так просто обстоят дела с уравнением (8): в этой статье для него найдены лишь условия разрешимости, условий однозначной разрешимости авторам получить

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

Алгоритм типа Бартелса-Стьюарта, построенный для уравнения (8) на основе доказательства теоремы об условиях однозначной разрешимости, имеет сложность 0(п4) арифметических операций. Это может вызвать недоумение, ведь все численные алгоритмы, рассматривавшиеся нами до сих пор, имеют сложность 0(п3) арифметических операций. Обратимся к алгоритму Голуба-Нэша-Ван Лоана для уравнения Стейна, описанному в §2 главы 1: важную роль в быстродействии этого алгоритма играют сохранение результатов промежуточных расчетов и их использование при вычислении последующих элементов. Именно этот прием компенсирует неприятное соседство матриц А и В (которого нет в уравнениях типа Сильвестра) и снижает сложность этого алгоритма до 0(п3) арифметических операций. Добиться аналогичного снижения сложности на соответствующем этапе алгоритма, решающего уравнение (8), не так просто. Вводится специальная матрица 2, в которой при вычислении каждого внедиагонального элемента сохраняются промежуточные результаты, используемые в дальнейшем повторно. Завершает главу замечание, показывающее возможность распространения полученных для уравнения (8) результатов на случай прямоугольных матриц.

Глава 3. Решение матричных уравнений в самосопряженном случае.

В §2 главы 2 мы связали с уравнением (9) линейный оператор Т и изучили свойства сопряженного к нему оператора. Для уравнений (1),

(2), (8), (14), (15) также найдены операторы, сопряженные операторам, связанным с левыми частями этих уравнений. Предположим теперь, что оператор Т самосопряжен. В контексте методов типа Бартелса-Стьюарта этот случай соответствует наибольшей устойчивости численного алгоритма. На основе условий самосопряженности уравнений типа Сильвестра и Стейна удалось построить алгоритмы численного решения, учитывающие особенности соответствующих им операторов. Во всех случаях эти условия позволяют привести матричные коэффициенты А и В рассматриваемых уравнений к диагональному виду. В результате сложность этапа решения эквивалентных систем уравнений уменьшается с 0(п3) до 0(п2) арифметических операций. Проведены численные эксперименты, иллюстрирующие выигрыш в скорости при использовании для решения самосопряженных уравнений этих специальных алгоритмов вместо алгоритмов, рассчитанных на уравнения общего вида.

Глава 4. Квадратичные и полуторалинейные матричные уравнения.

В этой главе рассматриваются квадратичные

ХТБХ + АХ + ХТВ + С = 0 (16)

и полуторалинейные

ХЮХ + АХ + Х'В + С = 0 (17)

матричные уравнения. Эти уравнения удобно объединить в обобщенное уравнение

ХпБХ + АХ + Xя В + С = 0. (18)

Если матрица О нулевая, то уравнение (18) сводится к уравнению (9). Для случая (АБ^В—С)71 = АВ~ХВ—С вопрос разрешимости этого уравнения

удается свести к уравнению вида

IУБШ = Ы,

(19)

в котором матричные коэффициенты 5, N и неизвестная матрица IV — симметричны (эрмитовы), а матрица Б невырожденна. Сопоставим теперь уравнению (18) матрицу

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

Основные выводы

В работе установлены условия однозначной разрешимости уравнений АХ + ХТВ = С, АХ + Х'В = С, АХ + ВХТ = С, АХ + ВХ* = С, X + АХТВ = С в самых общих случаях. Построены устойчивые численные алгоритмы для решения этих уравнений. Подтверждена экспериментально устойчивость и эффективность этих алгоритмов. Исследован случай самосопряженности уравнений типа Сильвестра и Стейна. Построены эффективные алгоритмы для таких случаев. Экспериментально подтверждена их высокая скорость по сравнению с алгоритмами для уравнений общего вида.

(20)

Заключение

Для уравнений Хт БХ+АХ+ХТ В+С = О, Х'БХ+АХ+Х'В+С = О найдены условия разрешимости. Построены алгоритмы вычисления одного из решений. С алгоритмами проведены эксперименты, подтверждающие их устойчивость.

Рекомендации по применению результатов

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

Публикации по теме диссертации

Публикации в журналах из перечня ВАК:

1. Воронцов Ю. О., Икрамов X. Д. Численный алгоритм для решения матричного уравнения АХ + ХтВ = С // Журнал вычислительной математики и математической физики. 2011. Т. 51, № 5. С. 739-747.

2. Воронцов Ю. О. Численный алгоритм для решения матричного уравнения АХ + X*В — С // Вестник Московского Университета. Сер. 15. Вычислительная математика и кибернетика. 2013. № 1. С. 3-9.

3. Икрамов X. Д., Воронцов Ю. О. Об однозначной разрешимости матричного уравнения АХ + ХТВ = С в сингулярном случае // Доклады РАН. 2011. Т. 438. № 5. С. 599-602.

4. Воронцов Ю. О., Икрамов X. Д. Об условиях однозначной разрешимости матричного уравнения АХ + Х'В = С // Журнал

вычислительной математики и математической физики. 2012. Т. 52. № 5. С. 775-783.

5. Воронцов Ю. О., Икрамов X. Д. О численном решении матричных уравнений АХ + ХТВ = С и X + АХТВ = С с прямоугольными коэффициентами А и В // Записки научных семинаров ПОМИ. 2012. Т. 405. С. 54-58.

6. Икрамов X. Д., Воронцов Ю. О. Матричное уравнение X + АХТВ = С: условия однозначной разрешимости и алгоритм численного решения // Доклады РАН. 2012. Т. 443. № 5. С. 545-548.

7. Воронцов Ю. О., Икрамов X. Д. Численное решение матричных уравнений вида X + АХТВ = С // Журнал вычислительной математики и математической физики. 2013. Т. 53. № 3. С. 331-335.

8. Воронцов Ю. О. Модификация численного алгоритма для решения матричного уравнения X + АХТВ = С // Журнал вычислительной математики и математической физики. 2013. Т. 53. № 6. С. 853-856.

9. Икрамов X. Д., Воронцов Ю. О. Матричные уравнения АХ + ВХТ = С и АХ + ВХ' = С // Доклады РАН. 2013. Т. 449. № 5. С. 513-515.

10. Воронцов Ю. О., Икрамов X. Д. Численные алгоритмы для решения матричных уравнений АХ + ВХТ = С и АХ + ВХ* = С // Журнал вычислительной математики и математической физики. 2013. Т. 53. № 6. С. 843-852.

11. Икрамов X. Д., Воронцов Ю. О. Численное решение матричных уравнений Сильвестра в самосопряженном случае // Вестник Московского Университета. Сер. 15. Вычислительная математика и кибернетика. 2014. № 2. С. 7-9.

12. Воронцов Ю. О., Икрамов X. Д. Численное решение матричных уравнений АХ + ХтВ = С и АХ + Х'В = С в самосопряженном случае // Журнал вычислительной математики и математической физики. 2014. Т. 54. № 2. С. 179-182.

13. Воронцов Ю. О., Икрамов X. Д. Численное решение матричных уравнений типа Стейна в самосопряженном случае // Журнал вычислительной математики и математической физики. 2014. Т. 54. № 5. С. 723-727.

14. Воронцов Ю. О., Икрамов X. Д. Численное решение матричного уравнения X + АХВ = С в самосопряженном случае // Журнал вычислительной математики и математической физики. 2014. Т. 54. № 3. С. 371-374.

15. Воронцов Ю. О., Икрамов X. Д. Алгоритм численного решения одного класса полуторалинейных матричных уравнений // Журнал вычислительной математики и математической физики. 2014. Т. 54. № 6. С. 901-904.

16. Воронцов Ю. О., Икрамов X. Д. Алгоритм численного решения одного класса квадратичных матричных уравнений // Журнал вычислительной математики и математической физики. 2014. Т. 54. № 11. С. 1707-1710.

Подписано в печать: 26.01.15

Объем: 1,0 п.л. Тираж: 70 экз. Заказ № 166 Отпечатано в типографии «Реглет» г. Москва, Ленинский проспект, д.2 (495) 978-66-63, www.reglet.ru