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

• Воронцов, Юрий Олегович
• кандидат наук
• 2014

Оглавление диссертации кандидат наук Воронцов, Юрий Олегович

Содержание

Список обозначений

Введение

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

§1. Матричное уравнение Сильвестра

§2. Матричное уравнение Стейна

§3. Квадратичные матричные уравнения

Выводы

Глава 2. Матричные уравнения типа Сильвестра и Стейна.

Условия разрешимости и численные алгоритмы

§1. Уравнения типа Сильвестра

§2. Уравнения, сопряженные уравнениям типа Сильвестра

§3. Уравнения типа Стейна

Выводы

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

случае

§1. Уравнения Сильвестра и Стейна

§2. Уравнения типа Сильвестра

§3. Уравнения типа Стейна

Выводы

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

уравнения

Выводы

Заключение

Список литературы

Приложение. Функция ВЗТхахЬ

Приложение. Функция ВЗТхахЬзэ

Список обозначений

К — поле вещественных чисел С — поле комплексных чисел

Сп — арифметическое пространство размерности п над С

Мп(С) — пространство комплексных квадратных матриц порядка п

Мт^(С) — пространство комплексных т х п-матриц

Хг(Л) — собственные значения матрицы А

1п единичная матрица порядка п

,/п(Л) жорданова клетка, отвечающая собственному значению Л

— жорданова клетка, отвечающая собственному значению Л = О А — матрица, полученная из А взятием поэлементного сопряжения А1 — транспонированная матрица

А* — сопряженная матрица, А* = АТ А~1 — обратная матрица А~7 — матрица (А-1)т А~* — матрица (Л-1)*

И — символ, указывающий операцию транспонирования или сопряжения Ан

- матрица Ат или А* А~п матрица {А~1)п

— число 2; или число г {х,у) скалярное произведение

Т* — оператор, сопряженный к оператору Т ||1| — спектральная норма, ||Л|| = ||Л||2

--норма Фробениуса

А — след матрицы А гапк А — ранг матрицы А р(А) — спектральный радиус матрицы А

Введение диссертации (часть автореферата) на тему «Условия разрешимости и численные алгоритмы для решения линейных, полулинейных, квадратичных и полуторалинейных матричных уравнений»

Введение

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

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

Уравнение АХ + X1 В — С, а также уравнения АХ + Х*В = С и АХ + ХВ — С мы будем обобщенно называть уравнениями типа Сильвестра. Актуальность исследования такого рода уравнений не вызывает сомнений. Приведем несколько примеров, показывающих, почему изучение уравнений типа Сильвестра оправданно. Уравнение АХ + ХтВ = С впервые было встречено нами в статье [8], где оно было исследовано при дополнительном предположении С — С1.

Условия разрешимости и описание общего решения были даны в терминах обобщенных обратных для матриц А и В и связанных с ними проекторов. Эти условия не вполне конструктивны и трудны для проверки. Однородное уравнение АХ + ХТВ — 0 было исследовано в статье [4] в частном случае В = А. Мотивировкой авторов было то обстоятельство, что множество {ХА + АХ'1 : X £ Спхп} есть касательное пространство (вычисленное в точке А) орбиты матрицы А под действием конгруэнций. Коразмерность этой орбиты есть в точности размерность пространства решений уравнения ХА + АХТ = 0. Основным результатом работы [4] было установление канонической структуры матриц общего положения относительно конгруэнций. Подобным образом теми же авторами в [5] исследовано уравнение АХ + Х*А = 0. В публикации [6] уравнения АХ + X1 В = С и АХ + Х*В = С возникают при построении алгоритма для палиндромных проблем собственных значений Ах = ХАтх и Ах = \А*х. В процессе приведения матрицы А к антитреугольному виду возникает необходимость численного решения этих уравнений. В статье [10] сформулированы условия однозначной разрешимости и численный алгоритм для решения уравнения АХ + ХВ = С.

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

Цель работы

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

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

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

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

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

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

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

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

Условия однозначной разрешимости, полученные для уравнений АХ + ХТВ = С, АХ + Х*В = С, АХ + ВХТ - С,

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

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

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

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

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

Апробация работы и публикации

По теме диссертации опубликовано 16 научных работ в следующих журналах из списка ВАК: Вестник Московского университета, серия 15, Вычислительная математика и кибернетика; Журнал вычислительной математики и математической физики; Записки научных семинаров

ПОМИ; Доклады РАН. Одна статья находится в печати.

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

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

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

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

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

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

Глава 1. Известные факты о матричных уравнениях Сильвестра и Стейпа, такие как условия однозначной разрешимости и численные алгоритмы, приводятся в §1-2. В §3 приводятся известные факты о квадратичном матричном уравнении ХИХ + АХ + ХВ + С = 0, такие как условия разрешимости и численный алгоритм.

Глава 2. Исследование уравнений типа Сильвестра на условия однозначной разрешимости и построение численных алгоритмов проведены в §1. Если левым частям матричных уравнений поставить в соответствие операторы, а затем должным образом ввести скалярное произведение, то можно говорить о сопряженных операторах, которым, в свою очередь, соответствуют какие-то матричные уравнения. Будем называть такие уравнения сопряженными к исходным уравнениям. Уравнениями, сопряженными к уравнениям АХ + ХтВ = С и АХ + Х*В — С, оказываются уравнения другого типа, а именно уравнения АХ + ВХТ — С и АХ + ВХ* = С. В §2 эти уравнения исследованы на условия однозначной

разрешимости и для них построены численные алгоритмы. В §3 для уравнения X + АХ1 В = С получены условия однозначной разрешимости и разработан численный алгоритм. Отметим, что уравнения, сопряженные к уравнениям типа Стейна, являются уравнениями того же типа и не нуждаются в дополнительных исследованиях.

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

Глава 4. Для хорошо изученного уравнения XDX + AX+XB + C = О, как и для его транспонированного и сопряженного аналогов, а именно квадратичного уравнения X1 DX + АХ + X1 В + С = 0 и полуторалинейного уравнения X*DX + АХ + Х*В + С = 0, характерно наличие многих решений. В последней главе для двух названных аналогов устанавливаются условия разрешимости и строятся алгоритмы вычисления частных решений.

Все численные алгоритмы, разработанные в диссертации, были реализованы в виде функций языка Matlab версии R2011b. Численные эксперименты, обсуждение которых завершает разделы, посвященные численным алгоритмам, проводились с помощью этих функций на персональном компьютере с процессором Intel Core iT 2600К и 16 гигабайтами оперативной памяти.

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

Глава 1

Матричные уравнения

В этой вводной главе мы рассматриваем уравнения Сильвестра АХ + X В — С и Стейна X + АХ В — С, а также квадратичное уравнение ХОХ + АХ + ХВ + С = 0. В §1 подробно изложено получение условий однозначной разрешимости уравнения Сильвестра. Детально описан численный алгоритм Бартелса-Стьюарта. Ввиду существенной аналогии подробности получения условий однозначной разрешимости и численного алгоритма для уравнения Стейна опущены. Это уравнение рассматривается в §2. Для квадратичного уравнения ХОХ + АХ + ХВ + С = 0 в §3 описывается метод инвариантных подпространств, позволяющий выявить условия разрешимости этого уравнения и предложить для пего численный алгоритм.

Содержание главы в своей основе представляет собой изложение материала, взятого из книг [1) и [2]. Этот материал упрощает понимание последующих глав.

§1. Матричное уравнение Сильвестра

Матричные коэффициенты А и В уравнения Сильвестра

АХ + ХВ = С (1.1)

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

Условия однозначной разрешимости. Как и для всякого линейного уравнения, условия однозначной разрешимости уравнения (1-1)

эквивалентны условиям, при которых однородное уравнение

АХ + ХВ = 0 (1.2)

допускает только тривиальное решение X = 0. Приведем матричные коэффициенты уравнения (1.2) к жордановой форме:

А = иЛи~\ В = УВУ~1. (1.3)

Здесь и и У — квадратные невырожденные матрицы соответственно порядка т и п, а А и В — жордановы формы матриц А и В.

Подставляя в уравнение (1.2) вместо Л и В их выражения (1.3), получим:

иАи~1х + хуву~х = о.

Умножим обе части этого равенства слева на и~1, а справа — на У:

Аи~1ХУ + и~1ХУВ = 0. (1.4) Произведя замену искомой матрицы

У = и~1ХУ, (1.5)

запишем уравнение (1.4) так:

АУ + УВ = 0. (1.6)

Мы заменили матричное уравнение (1.2) уравнением (1.6) того же вида, но р> котором матричные коэффициенты имеют жорданову форму. В соответствии с квазидиагональным видом матриц А и В разобьем матрицу У на блоки:

(здесь — прямоугольная матрица размером ра х д^).

Используя это разбиение, произведем умножение матриц в левой части уравнения (1.6). Тогда это уравнение распадется на ш матричных уравнений

(Ха1Ра + .1рМ)Уа0 + + ^(0)) = 0,

где 1Ра — единичная матрица порядка ра, а 3Ра{0) — жорданова клетка, отвечающая собственному значению 0. Перепишем эти уравнения следующим образом:

(Аа + цр)Уар = -7Рв(0)Уа/3 - УацЛДО). (1.7)

Возьмем какое-нибудь из уравнений (1.7). Возможны два случая:

1. Ха+нр Ф 0. Проитерируем равенство (1.7) (обе части равенства (1.7) умножаем на Ха +у, р и в каждом члене правой части заменяем {Ха+¡л р)Уар на -</Ра(0)Уа0 - Уа/37дД0)) г - 1 раз:

(Аа+ЫГ^=(-1)Г £ ^.(0)^(0).

<т+т=г

Если здесь взять г > ра + др — 1, то в каждом члене суммы, стоящей справа, выполняется по крайней мере одно из соотношений а > ра, т > Чр, а, значит, и по крайней мере одно из соответствующих соотношений </ра(0) = 0, ^ (0) = 0. Следовательно, правая часть равна нулю, а потому это уравнение допускает единственное решение Уар = 0.

2. Ап + цр — 0. В этом случае уравнение (1.7) принимает вид

+ = 0.

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

Теорема 1 Уравнение Сильвестра однозначно разрешимо для любой правой части С, если

\(А) + Х^В) ^ О (1.8)

Численный алгоритм. Опишем теперь один из эффективных численных алгоритмов для решения уравнения Сильвестра — алгоритм Бартелса-Стыоарта. Предполагается, что выполнены условия однозначной разрешимости, формулируемые теоремой 1. Алгоритм состоит из следующих этапов:

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

i = U*AU (1.9)

верхпстреугольная, а матрица

в = У*ВУ (1.10)

нижнетреугольная. Средством вычисления матриц (1.9) и (1.10) может служить, например, комплексный QR-алгоритм, интерпретируемый не как метод нахождения собственных значений, а именно как метод приведения к треугольному виду (см. об этом подробнее в [2, §4]).

2. Преобразование правой части. На этом этапе вычисляется матрица

D = U* СУ.

Результатом первых двух этапов является замена исходного уравнения новым уравнением Сильвестра

ÁY + yB = D. (1.11)

Неизвестная матрица У связана с X соотношением

У = U* XV. (1.12)

3. Решение уравнения (1.11). Это матричное уравнение представляет собой треугольную систему линейных уравнений относительно тп коэффициентов уц матрицы У. Вот как решается эта система: приравнивая в (1.11) элементы в позиции (т,п), имеем

(а>тт + Ьпп)утпп — dmn. (1.13)

Элементы amm и Ьпп суть собственные значения соответственно матриц А и В, поэтому amm -f bnn ф 0 и уравнение (1.13) определяет коэффициент утп. Возвращаясь к уравнению (1.11), приравниваем элементы в позиции (га, п — 1):

(®гаш ^п— 1,п— \)Ут,п—1 = dm,n—1 1 Утп-

Найдя коэффициент ут,п-1, переходим к позиции (m,n — 2):

iflmm ~Ь Ьп-2,п—2)Ут,п-2 = ^тп,тг—2 ^71—1,тг—2Ут,п—1 ^n,7i—2Утп-

Продолжая таким образом, определим все коэффициенты последней строки матрицы У. После этого вычисляем коэффициенты предпоследней строки последовательным приравниванием в (1.11) элементов в позициях (га — 1, j), где j, убывая, меняется от п до 1; затем переходим к вычислению коэффициентов (тп — 2)-й строки, и т. д. Если вычислены все элементы yij, для которых i > к, и все ykj, для которых j > I, то формула для вычисления элемента уц выглядит следующим образом:

тп п

(hk + Ьц)ук1 = (hi ~ ( йkiVil + Y1 УкМ- i1-14)

i=k+1 j-l+1

4. Возврат к исходной матрице X. Обращая соотношение (1.12), получаем

X = U¥V*. 15

Сложность описанного алгоритма в случае, когда все матрицы уравнения (1.1) квадратные одного и того же порядка п, находится из формулы (1.14) и составляет 0(п3) арифметических операций.

§2. Матричное уравнение Стейна

Матричные коэффициенты А я В уравнения Стейна

X + АХ В — С, (2.1)

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

Условия однозначной разрешимости

Теорема 2 Уравнение Стейна однозначно разрешимо для любой правой части С, если

Хг(А)Х^В) ± -1 Уг,^. (2.2)

Численный алгоритм. Опишем алгоритм Голуба-Нэша-Ван Лоана для уравнения Стейна. Как и алгоритм Бартелса-Стьюарта, он состоит из четырех этапов:

1. Приведение матрицы А к верхней форме Хессенберга, а матрицы В к иилснсй форме Шура.

А = и*АЦ, В - У*ВУ. (2.3)

Форма Хессеиберга может быть вычислена последовательностью т — 2 подобий с отражениями в качестве трансформирующих матриц (см. [2, §3]).

2. Преобразование правой части. На этом этапе вычисляется матрица

В = II* СУ. 16

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

У + АУВ = Б. (2.4)

3. Решение преобразованного уравнения (2.4)- Представим матрицы У и И в виде

У = [У\У2 ■ • • Уп], В = [(11(12 ■ ■ • с!п],

где У1 и (1г — столбцы соответствующих матриц.

Пусть уже определены столбцы У с номерами &+1,..., п. Тогда столбец У)с вычисляется из системы линейных уравнений с хессенберговой матрицей

п

(/ + ЪккА)ук = 4 - £ ЬгкАу{. (2.5)

г=к+1

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

4. Возврат к исходной матрице X.

X = иуу*.

Сложность алгоритма (для квадратных матриц порядка п) так же, как и в случае уравнения Сильвестра, составляет 0(п3) арифметических операций.

§3. Квадратичные матричные уравнения

Матричное уравнение

ХБХ + АХ + ХВ + С = 0 (3.1)

при О = 0 превращается в уравнение Сильвестра. Будем далее считать, что В ф 0. Матричные коэффициенты А, В являются квадратными

матрицами, вообще говоря, различных порядков тип, матричный коэффициент В имеет размер п х т, а матрицы X и С имеют размер

772 X П.

Условия разрешимости. По коэффициентам уравнения (3.1) составим блочную матрицу

Порядок матрицы М равен т + п; ее диагональные блоки —В и А суть квадратные матрицы.

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

ми = имс. (3.3)

Представим матрицу С/ в блочном виде, согласованном с (3.2):

Предположим, что подматрица 11\ размера пхп невырожденна. Покажем, что в этом случае матрица

= ВД-1 (3.5)

является решением уравнения (3.1). Действительно, из формул (3.2) — (3.4)

следует

-ви{ - ии2 = игМс,

сих + Аи2 = и2М£. 18

Умножим каждое из этих равенств справа на

-В-БХо^игМси^,

С + АХо = и2МсиI1. Умножая теперь (3.6) слева на Хо и вычитая из (3.7), получим

(3.6)

(3.7)

Х0£Х0 + АХ0 + Х0В + С = О,

(3.8)

что и требовалось. Если

/7 =

— другая базисная матрица подпространства £п, то блок 11\ также

матрицы и и и связаны соотношением II — 11Р, где Р — невырожденная матрица порядка п (матрица перехода от одного базиса подпространства Сп к другому). Тогда матрица 11\ = 11\Р невырожденна как произведение невырожденных матриц и

Покажем, что и, наоборот, каждое решение Хо уравнения (3.1) определяет некоторое п-мерное инвариантное подпространство матрицы М и что Х() может быть выражено посредством (3.5) через любую базисную матрицу и этого подпространства. Запишем (3.8) в виде

невырожден и £/2^1 1 совпадает с матрицей (3.5). Действительно, базисные

и2й{1 - и2рр~1и{1 = ЩЩ1 =

С + АХ0 = Х0(-В-ОХ0).

(3.9)

Полагая

-В - БХп = К

(3.10)

и подставляя в (3.9), получим

С + = Х0К.

(3.11)

Вместе соотношения (3.10), (3.11) означают, что подпространство Сп с базисной матрицей

является инвариантным подпространством матрицы (3.2). Для этой базисной матрицы и решения Х0 формула (3.5) выполняется. Но тогда, как показано выше, она выполняется и при любом другом выборе базисной матрицы для Сп.

Итак, установлено соответствие между решениями уравнения (3.1) и п мерными инвариантными подпространствами Сп матрицы М такими, что в любой их базисной матрице верхняя п х п-подматрица невырождениа. Специальный выбор базисной матрицы (3.12) показывает, что это соответствие взаимно однозначно: различным решениям отвечают различные инвариантные подпространства, и обратно.

Численный алгоритм. Опишем алгоритм построения какого-либо решения уравнения (3.1).

Алгоритм состоит из трех этапов.

1. Составление матрицы М. По формуле (3.2) из коэффициентов исходного уравнения строится матрица М.

2. Приведение матрицы М к форме Шура. Это достигается (^11-алгоритмом. Пусть и — унитарная матрица, трансформирующая М к верхней форме Шура 5:

(3.12)

и* ми = Б.

(3.13)

Представим матрицу и в блочном виде:

и =

ии и 12 и2\ и22

(С/ц — квадратная матрица размерапхп). Подпространство Сп, натянутое на столбцы матрицы

является п-мерным инвариантным подпространством матрицы М. Подматрицу С/ц будем считать невырожденной. 3. Вычисление решения Xо. Согласно (3.5),

Выводы

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

Хо = £/21 С^п1.

Глава 2

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

Матричными уравнениями типа Сильвестра, кроме, собственно, самого уравнения Сильвестра, мы называем следующие уравнения: АХ + ХТВ = С, АХ + Х*В = С и АХ + ХВ = С. Исследованию первых двух из них посвящен §1 (сведения о последнем уравнении можно найти в [10]). Между этими уравнениями много общего, и мы посчитали целесообразным объединить их, введя обобщенное уравнение

АХ + Хп В = С.

Символ ""Н" может быть заменен на символ операции транспонирования "Т" либо на символ операции эрмитова сопряжения "*". Это уравнение подробно исследовано па условия однозначной разрешимости в случаях, когда матричный пучок А + ХВп является регулярным либо сингулярным. Кроме того, предложен численный алгоритм (в том числе и для случая прямоугольных матриц), с которым проведены различные эксперименты. Содержание параграфа построено на статье [9] Икрамова X. Д., статье [11] автора и совместных статьях [12]-[15] автора и Икрамова X. Д.

В начале §2 объясняется, каким образом уравнения АХ + ВХ1 = С и АХ + ВХ* — С возникают в качестве сопряженных к уравнениям типа Сильвестра (первое из них появляется уже в конце первого параграфа). Далее эти уравнения исследуются на условия однозначной разрешимости, строится численный алгоритм для их решения и с ним проводятся эксперименты. Содержание этого параграфа построено на совместных

статьях [19], [20] автора и Икрамова X. Д.

Матричные уравнения Х+АХТВ = С, Х+АХ*В = С и Х+АХВ = С наряду с уравнением Стейна будем называть уравнениями типа Стейна. §3 начинается с обзора результатов большой статьи [7], посвященной этим уравнениям. Уравнение X + АХТВ — С исследовано в этой статье лишь частично, и дальнейшее содержание параграфа посвящено именно этому уравнению. Устанавливаются условия однозначной разрешимости, разрабатывается численный алгоритм (в том числе и для прямоугольного случая), производится его сравнение с алгоритмами, предложенными в [7], и проводятся численные эксперименты. Этот параграф основан на статье автора [18] и совместных статьях [15]-[17] автора и Икрамова X. Д.

§1. Уравнения типа Сильвестра

Матричные коэффициенты А я В уравнения

АХ + ХпВ = С (1.1)

суть прямоугольные матрицы размеров соответственно тп х п и п х т, а С — квадратная матрица порядка т. Если т ф- п, то и искомая матрица X — прямоугольная и ее размер совпадает с размером В. С уравнением (1.1) свяжем матричный пучок

А + \ВН. (1.2)

Условия однозначной разрешимости уравнения (1.1) будут сформулированы в терминах этого пучка. Матричный пучок (1.2) называется регулярным, если т = п и с!е1(Л + ХВп) не обращается в нуль тождественно по Л. В противном случае пучок (1.2) называют сингулярным. При установлении условий однозначной разрешимости

уравнения (1.1) случаи регулярного и сингулярного пучка будем рассматривать раздельно.

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

В отличие от уравнения

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

уравнение

АХ + Х*В = С (1.4)

не является линейным. Однако оно будет линейным, если допускается умножение матрицы X только на вещественные числа. Иначе говоря, (1.4) есть система (неоднородных) линейных уравнений относительно вещественных и мнимых частей элементов хц. Этого свойства достаточно для того, чтобы вопрос об однозначной разрешимости уравнений (1.3), (1.4) при любой правой части С можно было заменить эквивалентным вопросом об однозначной разрешимости однородного уравнения

АХ + ХпВ = 0. (1.5)

Пусть Р и (3 — невырожденные матрицы порядков соответственно п и т. Положим

X = РУЯ (1.6)

и выполним в (1.5) замену переменного (1.6). Имеем

Аруд + диуирив = о,

откуда

{д~пАР)у + уп(рквд-1) = о.

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

Л = д-'«АР, в = рпв(2~1,

заключаем, что У есть решение уравнения

АУ + УпВ = О

(1.7)

того же типа, что и (1.5). При этом матричные коэффициенты А и В исходного уравнения преобразуются по правилам

Формулы (1.8) означают, что матричный пучок (1.2) заменяется строго эквивалентным (см. определение в [1, гл. XII, §1]) пучком

Преобразование, описываемое формулами (1-8), будем называть эквивалентным преобразованием пучка (1-2). Все дальнейшие преобразования этого пучка будут эквивалентными и направлены на максимальное упрощение вида матриц А и В. Степень такого упрощения различна для случаев регулярного и сингулярного пучка (1.2).

Список литературы диссертационного исследования кандидат наук Воронцов, Юрий Олегович, 2014 год

СПИСОК ЛИТЕРАТУРЫ

1. Гантмахер Ф. Р. Теория матриц. М.: Наука, 1966.

2. Икрамов X. Д. Численное решение матричных уравнений. М.: Наука, 1984.

3. Ильин В. А., Ким Г. Д. Линейная алгебра и аналитическая геометрия. М.: Проспект и МГУ, 2007.

4. Тети F., Bopico F. М. The solution of the equation XA+AXT = 0 and its application to the theory of orbits // Linear Algebra Appl. 2011. V. 434. N 1. P. 44-67.

5. Teran F., Bopico F. M. The equation XA + AX* = 0 and the dimension of *-congruence orbits // Electronic Journal of Linear Algebra. 2011. V. 22. P. 448-465.

6. Kressner В., Schroder C., Watkins B. S. Implicit QR algorithms for palindromic and even eigenvalue problems // Numerical Algorithms. 2009. V. 51. N 2. P. 209-238.

7. Zhou В., Lam J., Buan G.-R. Toward solution of matrix equation X = Ai(X)B + C // Linear Algebra Appl. 2011. V. 435. N 6. P. 1370-1398.

8. Piao F., Zhang Q., Wang Z. The solution to matrix equation AX + XTC = B // J. Franklin Inst. 2007. V. 344. N 8. P. 1056-1062.

9. Икрамов X. Д. Об условиях однозначной разрешимости матричного уравнения АХ + ХТВ = С // Докл. РАН. 2010. Т. 430. № 4. С. 444-447.

10. George A., Ikramov Kh. D., Matushkina E. V., Tang W.-P. On a QR-Like Algorithm for Some Structured Eigenvalue Problems // SIAM J. Matrix Anal. Appl. 1995. V. 16. N. 4. P. 1107-1126.

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

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

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

14. Воронцов Ю. О., Икрамов X. Д. Об условиях однозначной разрешимости матричного уравнения АХ+Х*В = С // Ж. вычисл. матем. и матем. физ. 2012. Т. 52. № 5. С. 775-783.

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

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

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

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

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

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

21. Braden Н. W. The Equations АТХ ± ХтА = В // SIAM J. Matrix Anal. Appl. 1998. V. 20. N. 2. P. 295-302.

22. Икрамов X. Д. Матричные пучки — теория, приложения, численные методы. Итоги науки и техники. Серия "Математический анализ т. 29. М.: ВИНИТИ, 1991, с. 3-106.

23. Bojanczyk A., Golub G., Van Booren P. Periodic Schur decomposition: algorithms and applications //In Proc. SPIE Conference. 1992. V. 1770. P. 31-42.

24. Kressner B. The periodic QR algorithm is a disguised QR algorithm // Linear Algebra Appl. 2006. V. 417. N 2-3. P. 423-433.

25. Kressner B. An efficient and reliable implementation of the periodic QZ algorithm // IFAC Workshop on Periodic Control Systems. 2001.

26. Zhou ВLam J., Buan G.-R. On Smith-type iterative algorithms for the Stein matrix equation // Appl. Math. Lett. 2009. V. 22. N 7. P. 1038-1044.

27. Хорн P., Джонсон Ч. Матричный анализ. M.: Мир, 1989.

28. Икрамов X. Д. Линейные матричные уравнения типа Сильвестра в самосопряженном случае // Докл. РАН. 2013. Т. 450. № 2. С. 147-149.

29. Икрамов X. Д. Условия самосопряженности полулинейных матричных уравнений // Докл. РАН. 2013. Т. 450. № 5. С. 511-513.

30. Икрамов X. Д. Условия самосопряженности матричных уравнений типа Стейна // Докл. РАН. 2013. Т. 451. № 5. С. 498-500.

31. Икрамов X. Д., Воронцов Ю. О. Численное решение матричных уравнений Сильвестра в самосопряженном случае // Вестник Московского

Университета. 2014. № 2. С. 7-9.

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

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

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

35. Голуб Дж., Ван Лоун Ч. Матричные вычисления. М.: Мир, 1999.

3G. Икрамов X. Д. Задачник по линейной алгебре. М.: Наука, 1975.

37. Fafibender Н., Ikramov Kh. В. Sorrie observations он the Youla form and conjúgate-normal matrices // Linear Algebra Appl. 2007. V. 422. N 1. P. 29-38.

38. Higham N. J. Functions of Matrices: Theory and Computation. SIAM, 2008.

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

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

41. Ikramov Kh. В. Solutions to sesquilinear matrix equations: Conspectral approach // Textos de Matematica, Departamento de Matematica Universidade de Coimbra. 2013. V. 44. P. 73-79.

42. Икрамов X. Д. О разрешимости одного класса полуторалинейных матричных уравнений // Докл. РАН. 2Ü14. Т. 454. № 1. С. 265-267.

43. Икрамов X. Д. О разрешимости одного класса квадратичных матричных уравнений // Докл. РАН. 2014. Т. 455. № 2. С. 135-137.

44. Horn R. А., Johnson С. R. Topics in Matrix Analysis. Cambridge University Press, Cambridge, 1991.

45. 14крамов X. Д. Разложение Такаги симметричной унитарной матрицы как конечный алгоритм // Ж. вычисл. матем. и матем. физ. 2012. Т. 52. № 1. С. 4-7.