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

РГ6 од

. - , АКАДЕМИЯ НАУК РОССИИ СИБИРСКОЕ ОТДЕЛЕНИЕ ВЫЧИСЛИТЕЛЬНЫЙ ЦЕНТР

На правах рукописи УДК 519.6+512.8

МАЛЫШЕВ Александр Николаевич

ГАРАНТИРОВАННАЯ ТОЧНОСТЬ

В ОБОБЩЕННОЙ СПЕКТРАЛЬНОЙ ЗАДАЧЕ

И РАЗЛОЖЕНИЕ НА МНОЖИТЕЛИ МАТРИЧНЫХ ПОЛИНОМОВ

01.01.07 - вычислительная математика

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

Новосибирск - 1993

Работа выполнена в Институте математики СО РАН.

Официальные оппоненты: доктор физико-математических наук

профессор В.П. Ильин; доктор физико-математических наук Е.Е. Тыртышников; член-корреспондент РАН профессор Ю.И. Шокин.

Ведушгия организация - Институт прикладной математики им. М.В. Келдыша РАН

Защита состоится 13: _ 1993г. в й5. час. на заседании

Специализированного СоветаД 002.10.01 при Вычислительном центре СО РАН по адресу:

630090, Новосибирск-90, пр. академика Лаврентьева, 6.

С диссертацией можно ознакомиться в читальном зале библиотеки ВЦ СО РАН (Новосибирск-90, пр. академика Лаврентьева, 6).

Автореферат разослан 15 1993г.

Ученый секретарь Специализированного совета доктор физико-математических наук

Ю.И.Кузнецов

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

Актуальность темы. Спектральные задачи для несимметричных матриц и пучков представляют собой один из наиболее важных разделов современной теории матричных вычислений. Необходимость развития методов решения этих задач обусловлена потребностями многих приложений математики. Достаточно упомянуть только проблемы устойчивости и проектирование автоматических систем управления. •

Наиболее выдающимся методом решения несимметричных спектральных задач является QR-алгоритм Френсиса-Кублановской. Большой вклад в развитие этого метода внесли также В.В. Воеводин, Б. Парлетт, П. Стюарт, Дж. Уилкинсон и др. В настоящее время можно утверждать, что глубоко развито обширное направление методов типа QR-алгоритма (в англоязычной литературе часто называемых шуровскими методами), включающее такие методы как QZ, AB и др. Успешно применяются шуровские методы и в спектральных задачах для сингулярных матричных пучков. Новые результаты для шуровских методов получили также П. вал Доорен, Дж. Деммел, Б. Когстрем.

Наряду с методами типа QR-алгоритма активно развивается метод матричной сигнум-функции, который необычайно популярен среди специалистов по численному решению задач автоматического контроля и устойчивости. Одним из первооткрывателей этого метода является A.A. Абрамов. В последнее время метод матричной сигнум-функции активно развивает А. Лауб с коллегами, который, в частности, отмечает очень высокую эффективность метода при его реализации на современных параллельных компьютерах.

В работах С.К. Годунова и А.Я. Булгакова за последний десяток лет развиты понятия и их свойства для задачи о дихотомии спектра матрицы замкнутым контуром. Частным случаем этой задачи является задача о дихотомии спектра несимметричной матрицы мнимой осью. Метод матричной сигнум-функции, как раз, решает эту последнюю задачу. Главным достижением работ С.К. Годунова и А.Я. Булгакова является разработка чисел обусловленности для задач о дихотомии спектра матрицы и

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

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

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

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

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

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

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

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

На основе разработанных в диссертации методов написаны программы библитехи LINA, предназначенные для решения задач о дихотомии спектра [7]. В [8] исследованы возможности эффективной реализации на параллельных и векторных ЭВМ алгоритмов решения задачи о дихотомии спектра, и представлены результаты численных экспериментов на ALLIANT FX/4, показавшие высокую эффективность разработанных алгоритмов для векторных и параллельных компьютеров с общей памятью.

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

Результаты диссертации докладывались на семинаре ЛОМИ АН СССР (руководители - чл.-корр. АН СССР Д.К. Фаддеев, проф. В.Н. Кублановская), на семинаре ВЦ СО АН СССР (руководитель - чл.-корр. РАН А.Н. Коновалов), на международном симпозиуме "Алгоритм-89" (апрель 1989 г., Высокие Татры, Чехословакия), на второй Всесоюзной конференции "Современные проблемы чи-

. елейного анализа" (сентябрь 1989 г., Тбилиси), на международном семинаре по численному анализу (май 1990 г., ВЦ СО АН СССР), на международном семинаре по численному анализу (июнь 1990 г., ОВМ АН СССР), на международном симпозиуме IMACS "Итерационные методы в линейной алгебре" (апрель 1991 г., Брюссель), на международных симпозиумах по вычислительной математике и матричным вычислениям (май 1991 г., Центр по математике и информатике, Амстердам), на семинарах INRIA-IRJSA (осень

1991 г., Ренн, Франция), на семинаре университета в Хагене (май

1992 г., ФРГ, руководитель - проф. К. Веселич).

Публикации. Основные результаты диссертации опубликованы в работах [1-11].

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

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

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

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

Прежде чем представить сводку результатов первой главы, введем ряд определений. Пучок N X N-маТриц А В — А назовем регулярным относительно единичной окружности, если det(Afl — А) £ 0 для любого комплексного числа А, лежащего на единичной окружности |А| = 1. Комплексные числа А и 1 /ц (если ц = 0, то 1/ц = оо) называются собственными числами регулярного пучка А В—А, если det(Aß—А) = 0 или det(B — цА) = 0 соответственно.

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

6

Теорема 1 Если det(AB — А) ф 0 при любом комплексном А, удовлетворяющем условию |А| = 1, то существуют такие невырожденные матрицы Qi и QT, что

Qi{XB - A)QT = block diag{AJ - J0, A J«, - /}, (1)

Jo = block diag{Ji,(Ai),..., /,„(Am)}, |A,| < 1, Joo = block diag-fj^x),..., «/,•„(/*»)}, \fij\ < 1, где I - единичная матрица подходящих размеров, а

Jt{v) =

i/l О и 1

О v

- блок Жордана размеров t xt.

Тем самым пучок А В —А, удовлетворяющий условиям теоремы, имеет собственные числа Ai соответствующей кратности внутри единичного круга и собственные числа вне единичного круга.

Запишем матрицу QT в блочном виде

Qr = [<?1 • • • QmQm+l • ■ • Qm+n]»

где разбиение на блочные столбцы соответствует размерам диагональных блоков в разложении (1). Будем называть подпространство Со, порождаемое столбцами блоков Qi, Qi,Qm, (правым) инвариантным подпространством пучка А В — А, отвечающим собственным числам внутри единичного круга. В англоязычной литературе такие подпространства обычно называются deflating. Соответственно, подпространство А», порождаемое столбцами блоков Qm+i, Qm+2, • • • 1 Qm+n, назовем (правым) инвариантным подпространством пучка А В — Л, отвечающим собственным числам вне единичного круга.

Задача о дихотомии спектра регулярного линейного пучка матриц А В — А единичным кругом состоит в

• выяснении вопроса о том, лежат ли какие-либо точки спектра пучка на единичной окружности,

• и, если таких точек нет, то вычислении инвариантного подпространства £о, отвечающего собственным числам внутри единичного круга, и инвариантного подпространства £го, отвечающего собственным числам вне единичного круга.

7

Для наших целей удобно задавать векторные подпространства с помощью проекторов на эти подпространства. Пусть N0 - размерность £о, а N00 — N — N0 - размерность ■£«>. Рассмотрим матрицы

P0 = Qr

IN. О О О

Q;\ POO = I-P0 = QT

о о о L

No,

Q7\

которые являются парой спектральных проекторов на подпространства Со и Соо соответственно. Таким образом, при решении задачи о дихотомии спектра матричного пучка единичной окружностью нашей задачей обычно будет вычисление матрицы Р = Ро. Вместе с тем, в диссертации рассматривается и вычисление ортогональных проекторов П0 и Пто на подпространства £0 и

Обсуждение введенных спектральных понятий и их свойств приводится в параграфе 1.1 диссертации.

В параграфе 1.2 определяется спектральная последовательность матриц

Pk = Qr

Pk = Qr

$ О О о

о о

Q;

-1

при целых к > +0,

Joo

Q~x при целых к < —0,

являющаяся важнейшим инструментом всей построенной теории задач о дихотомии спектра. Отметим, что при к = 0 имеется две матрицы: Р+0 = Ро И Р- 0 = Роо-

В терминах спектральной последовательности матриц Рк регулярный относительно единичной окружности пучок А В — А имеет следующий канонический вид:

ХВ - А = Г"1[А(Р+ о + P-i) - (Р-о + P+i)].

Этот канонический вид также чрезвычайно эффективен в теоретических построениях.

Заметим, что последовательность матриц Грина G* для разностного уравнения Вхп—Ae„_i = /« связана с матрицами Рк соотношениями вида:

G0 = Р+0Т, Gk = РкТ при к > 1, G-1 = — Р_оТ, Gk = -Рк+iT при к < -2. Следовательно, Т = Gq — GL1.

В параграфе 1.3 вводятся новые понятия: обобщенная матрица Ляпунова Я, ассоциированная с задачей о спектральной дихотомии пучка \В — А относительно единичной окружности, и параметр дихотомии и = и>(А,В) = ||Я||, который, по существу, является числом обусловленности этой задачи.

А именно, рассмотрим эрмитову матрицу

Я = Н{А,В) = Г {В - е'^А)-1(АА* + ВВ'){В - е<фА)~Чф,

которая определена для регулярного относительно единичной окружности пучка матриц А В — А. Пучок А В0 - Ао будем называть нормированным пучком, полученным нормировкой пучка А В — А, если Во = Ь~ХВ, Ао = Ь~гА для какой-либо матрицы Ь, удовлетворяющей равенству ЬЬ* = АА* + В В*. Очевидно, что все нормированные пучки, полученные из одного и того же пучка А В - А, отличаются лишь на унитарный множитель слева. Более того, обобщенная матрица Ляпунова у всех таких нормированных пучков совпадает с обобщенной матрицей Ляпунова Я для исходного пучка.

Параметр ш отражает спектральные свойства нормированного пучка АД) — Ао. Справедлива

Теорема 2 Пусть А0А^ + ВоВ^ — I и <1е1;(Яо — е'^Ао) ф 0 при любом вещественном ф, тогда

шах ||(Я0 - е'^Ао)-1!! < 14а;. Ф

Из этой теоремы следует, в частности, что собственные числа нормированного пучка ХВа — А0, а значит и исходного пучка А В - А, регулярных относительно единичной окружности, отстоят от единичной окружности на расстоянии не менее, чем 1/(14ы).

Далее показано, что, если АоАЗ+ВоВЗ = I и ||(А0 Во)-(Ао Во)|| < где 42ш(Ао,ВоМ < 1, то

ш(А0,Во) - ы(А0, В0)

||Я(А0> Во) - Я(А0) В0)|1 4МА0, Вр)6 ЦАо.Яо) - ||Я(Ао,Во)|| 1-42и>(Ао,ЯоМ'

На основе связи между матрицами Рк и функцией Грина (7* выводится важное тождество

я = (г 2 - -Р+ОР;0 - Р-ор:о,

,= оо д

откуда, например, легко получить неравенство и) > 1. Затем доказана следующая теорема, которая используется для исследования сходимости многих методов вычисления спектральных характеристик, а также для вывода ряда оценок в теории задач о дихотомии спектра.

Теорема 3 Если А В—А - регулярный относительно единичной окружности пучок матриц, то

/ 1 \ 1*1 Ш < ^ (1 - < у^е-|Ч/(1+ы).

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

Схема метода, называемого далее БГСН-алгоритмом, довольно проста и состоит из трех этапов:

Этап I. Вначале исходный пучок матриц А В — А нормируется, т.е. вычисляются такие матрицы Ао и Во, что А В — А — Ь(ХВо — Ао) с невырожденной матрицей Ь. Как правило, это нормировка условием АоАо + В0В1 = I.

Этап II. Выполняются итерации перехода от пары матриц Ат, Вт к паре Ат+1, Вт+1 для 0 < т < т0 по формулам Ат+1 = ХтАт, Вт+1 = УтВт, где Хт и Ут удовлетворяют системе

| Хт-Хт + ^т^т = ^> I ХтВт — УтАт = 0.

Алгоритмически вычисление матриц Ат+1 и Вт+1 может быть сведено к подбору ортогонального преобразования, применение которого слева к матрице

/ —Ат Вт 0 N I 0 \-Ат\ Вт I

аннулирует блок в рамке; в результате этой процедуры получаем матрицу

(Сщ+1 Лт+1 АтЦ-1 ] -Ат+1 0 Вт+1 ) •

Этап III. При достаточно большом то вычисляются матрицы — (Агъ, + Вто)_1Ято И2Ю = (Л^ + В^)'1 А^, ЯВЛЯЮЩИвСЯ ПрнбЛИ-жепиями для матриц проекторов Ро и Л» соответственно.

В параграфе 2.1 дано описание этого алгоритма и представлены идеи, хоторые привели к его формулировке.

Если есть необходимость в вычислении ортогональных проекторов По и Пто на инвариантные подпространства £0 и £га пучка А В — А, как, например, при решении задачи о факторизации матричных полиномов, рассмотренной в главе 8, то предлагается поступить следующим образом: сначала проводятся этапы I и II ИЮН-алгоритма, затем вычисляется нормированный пучок АВ^—Ата нормировкой пучка Ат,о) где Л.^Лто 4- Вт^В^ — /, откуда определяются матрицы 50 = I - А^, 5Ю = / - В*тоВт0. Утверждается, что при т0 -» оо матрицы 5с и 5«, стремятся к П0 и Псе соответственно.

В параграфе 2.2 выведена следующая оценка сходимости алгоритма:

11% -РоИЧ!^ -P.il

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

Кроме этого, выясняется крайне выгодное свойство, что (Ат,, + В^)"1^ + Вггь,)-' н = Г (В - ¿*А)-\АА* + ВВ*){В - е<фА)-(1ф,

причем

\\Н-(Ак + Вк)~\Ак + Вк)-\\<

4а,3/2е-21/(1+«) + 2а,2е-2к+,/(14~) + 2М-2а,е-2'/(1+иО - 1 - • В качестве простейшего, но важного для безаварийности Б1СН-алго-ритма следствия сходимости (Агпа + ВГГ10)~1(АГТ10 + Вт<,)~* к Я может быть показано, что обусловленность матрицы (А^ + В^) в пределе ограничена сверху величиной 2у/ш.

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

11

рассматривать как доказательство корректности алгоритма при реализации его на ЭВМ.

В параграфе 3.1 приведена сводка результатов о погрешностях матричных вычислений на ЭВМ, включающая оценки ошибок округления при выполнении арифметических и элементарных матричных операций, при выполнении ортогональных преобразований Хаусхолдера и при вычислении обратной матрицы ортогональным методом. Эти оценки обычно выражаются через полиномы малой степени от размерностей матриц с коэффициентами порядка единицы и две машинные константы, fi и (д. Параметр ti является относительной ошибкой выполнения элементарных арифметических операций, а ео - порогом обнуления, underflow.

В параграфе 3.2 доказаны три технические леммы, необходимые в анализе ошибок округления для DIGII-алгормтма. Одна из них, в частности, формулируется следующим образом.

Лемма 1 Предположим, что пучок N х N-матриц А В — А регулярен относительно единичной окружности, и пусть

В

-А В О

-А В О —А

- блочная двухдиагональная матрица размеров [Л^(п + 1)] х [ТУп], где. п > 1 - любое целое число. Тогда для любого вектора х € справедливо неравенство

>_Ё1!_

11 11 - тиц||(В-е'"М)-1|Г

В параграфах 3.3-3.5 изучается накопление погрешностей округления на всех трех этапах алгоритма. Устойчивость задачи о дихотомии спектра пучка матриц А В — А единичной окружностью ь диссертации оценивается с помощью двух чисел обусловленности: одно число, ц(А,В). обусловленность N х 2//-матрицы (А В), является классическим числом обусловленности нормировки исходного пучка А В — А условием АоАц + ВоВ$ — I, другое число, введенный выше параметр

дихотомии w(A, В), является числом обусловленности спектральных характеристик нормированного пучка А£?о — Ао.

Для процесса нормировки исходного пучка посредством стандартного алгоритма, основанного на вычислении QR-разложения с предварительным масштабированием N х 2TV-матрицы (А В), получена априорная оценка ошибок округления вида:

|!(А0 В0)сатР-(А0 В0)|| < А> = Ш Ю + 1].

где Ji(N) х (6TV + 23)yV3^2/{l - (6N + 23)N3'2c1{fx(A В) + 1]} при fo << с1- Через (Ao)comp, (Ва)сотр обозначен результат реальных вычислений на ЭВМ, а ХВо — Ао - некоторый, специальным образом подобранный, нормированный пучок, полученный нормировкой исходного матричного пучка А В — А.

После т0 итераций второго этапа получаем приближенные матрицы {Ато)сотр И (ßmjcomp, удовлетворяющие следующей оценке:

\\(-л то В то) comp ( А-ухо tfmJI < ßi = f2(N,m0,€Ußo)[2MA,B)+V2l

где f2{N,m0,eЬА>) и [А, + 2iV3/2(6JV + 23)m0ci]/{l - 20w[2N3/2(6N + 23)m0ei + ß0] - 2N3^(ñN + 23)m0fi} при e0 << fi- Следует отметить, что пучок АВгъ - Ama ~ специальным образом подобранный результат вычислений без ошибок округлений.

В параграфе 3.5 обсуждаются оценки ошибок округления при вычислении Матриц {[Amalcomp + {Вт^сотрТ^Вщ^сотр И

{[Amolcomp [-B^jconip) ([Ауп^еогор "Ь [Brruj]comp)

В качестве следствия получена оценка возмущений для матрицы Р = Ра при возмущении нормированного матричного пучка АВ0 — Ао:

где S = \\(Äo Во) - (Ао В„)||.

В четвертой главе разрабатывается методика оценки точности вычисленных DICH-алгоритмом спектральных характеристик регулярного относительно единичной окружности пучка А В — А. По существу, рассматриваются только нормированные пучки (например, условием A0AJ + Soflo = Л или близкие к ним, так как первый этап, нормировка, оценивается независимым способом с помощью параметра

13

Стах(А В)/<гт{п(А В), где через <т обозначены соответствующие сингулярные числа. Заметим, что оценки погрешностей вычисления матриц Р и Я и параметра и, полученные в предыдущей главе, зависят от величины параметра а». Следовательно, на их основании невозможно оценить точность вычисления самого параметра и. Один выход из этого порочного круга предлагается в главе 4.

Эта методика в большой степени основана на одном фундаментальном свойстве БЮН-алгоритма, которое формулируется в следующей теореме.

Теорема 4 Если с1е1;(.Вт — е'^Ат) ф 0 при любом вещественном ф, а пучок \Вт+1 — Ат+1 получается из пучка АВт — Ат с помощью Б1СН-алгоритма, то

± /02Т(Ят+1 - Ат+ге^Г\Вт+1 - Ап+;е«)-<1ф =

= ^ /02'(вт - Ап^Г\Вт - Атг*учф.

Таким образом, обобщенная матрица Ляпунова, фактически, инвариантна при итерациях СН-алгоритма. А в пределе при га —► оо имеем

Аса — Т^'Р-О, В00 = Т001Р+о,

^ - - А^ГЧф =

= р_о(Аоо+ДовГЧл»+вт)-р:0+р+о(Ло<,+в00)-1(Лх>+вт)-*р;0.

В результате выстраивается следующая схема контроля точности для БЮН-алгоритма:

в для каждого т (возможно, с некоторым интервалом) вычисляются матрица Ът = (Ат + Вт)~1Вт и невязка -

в если норма — 2то11 достаточно мала при некотором то, то итерационный процесс обрывается из-за того, что он "практически сошелся";

в вычисляется эрмитова матрица Н^ = 2та(Ато + Втз)~1{Ата + Вто)"*^+(/-^то)(Ато+Вто)-1(Ато+Вто)-*а-2то)% которая является приближением к обобщенной матрице Ляпунова Я;

• норма ЦЯ^ - Я|| эффективно оценивается через ||- и^Ц и ЦЯтоЦ, если 11^ - ^Ц достаточно мала.

14

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

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

\Ат)

где /(^У), - полиномы малой степени от N с коэффициентами порядка 1; затем к возмущенной паре Ат, Вт применяется "точная" итерация; после этого полученная пара Ат+1, Вт+\ возмущается с оценкой

||(Лт+1 Вт+\) — (Ап+\ Вт+1)\\<2/(Юег\\(Ат Вт)\\ + 2д(Юе0.

Здесь тильдой мы обозначили результаты реальных вычислений на ЭВМ.

Второй момент в анализе погрешностей — теория возмущений интеграла

Пт в Ь 1о'{Вт ~ Ате1фГ1{Вт-Ате^)-Чф в зависимости от возмущений матриц Ат и Вт- Выполнено

Предложение 1 Если&ъ\.{Вт — Ате'ф) ф 0 при любом вещественном ф, то

шах||(Вт- Л^Г1!! < шах |ншш(||Ат||,||Ят||)||Ят||,

на основе которого может быть получена оценка \\Й п \\<\\п II 80*1М-

где5=||(Лт Вт) — {Ат Ят)||,

= ^ Ц\вп - Ате*)~\Вт - Ате*)~Чф.

Последняя оценка справедлива, когда ||Ят|| > 1, пип(|| Лт||, ||Вт||) < 2, что в наших алгоритмах всегда выполнено, и 80<$||Ят|| < 1.

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

1|Я!1 = 1№1|<

ll^moli

1 - ЗбОшоЦЯ^Ц^)^ +я(ЛОео]'

И, наконец, третий важный момент — это оценка величины ¡¡Я^Ц при достаточно больших то- В диссертации получена следующая оценка:

' I-" 1-(8+ 3001^1, где Ф^ = Z^ - Z^, г = Щ.^, (/ - ZmJKÂ^ + Я^Г'Ц.

В пятой главе обсуждаются так называемые обобщенные уравнения Ляпунова, которые впервые появились в незамкнутом виде в одной работе С.К. Годунова для задачи о дихотомии спектра матрицы мнимой осью, а затем дополнены до замкнутой формы и детально исследованы в работах А.Я. Булгакова. В диссертации предложены и детально разработаны два варианта обобщенных уравнений Ляпунова для регулярных относительно единичной окружности матричных пучков. Этот инструментарий предоставляет альтернативный способ оценки точности вычисленных спектральных характеристик, не зависящий от алгоритма, которым вычислены проекционные матрицы и соответствующие обобщенные функции Ляпунова.

Рассмотрим следующую систему матричных уравнений относительно тройки N х TV-матриц (Р,Т,Х):

Р2 - Р = О, ТА{1 - Р) - (/ - Р) = 0, (/ - Р)ТА - (I - Р) = 0, ТВР - Р = О, РТВ - Р = 0, РХР* + (/ - Р)Х{1 - Р*) - X = 0,

ТАХ(ТА)* - ТВХ{ТВУ = (/ - Р)С(Г - Р*) - PCP*, которую назовем обобщенным уравнением Ляпунова I (ОУЛ I). Имеет место

Теорема 5 Предположим, что существуют матрицы Р, Т, X, С, удовлетворяющие обобщенному уравнению Ляпунова I, причем X = X* > 0, С = С* > 0. Тогда det(В - е{фА) ф 0 при любом вещественном ф, Р - проектор на инвариантное подпространство пучка А В — А, отвечающее собственным числам внутри единичного круга, а I — Р - проектор на инвариантное подпространство, отвечающее собственным числам вне единичного круга.

16

Нас интересует главным образом решение ОУЛ I при С — I. В этом случае

х= t Р;Р*Ц(Я + Р+0Р;0 + Р-ОР:0) /=-00 *

с

я = JL £'{В - е'^А)~1(АА* + - е*А)-<1ф,

и справедлива следующая модификация предыдущей теоремы.

Теорема 6 Пусть матрицы Р, Т и X удовлетворяют системе матричных уравнений

Р2 - Р = О,

ГА(/ - Р) - (/ - Р) = О, (/ - Р)ТА - (/ - Р) = О,

ГЯР - Р = 0, (2)

РТВ - Р = О,

РХР* + (/ - Р)Х{1 - Р')-Х = О, TAX (ТА)* - ТВХ{ТВУ + Р + Р*-/ = Ф

с ||Ф|| < 1. Тогда det(В — е'^А) Ф 0 при любом вещественном ф, а Р и I — Р - проекторы пучка А В — А на инвариантные подпространства, отвечающие собственным числам соответственно внутри и вне единичного круга. Более того,

Х- Е PjPj

< Е PjPjlЦФЦ-

Предположим, что все уравнения системы (2) выполнены приближенно, т.е. некоторые матрицы Р,Т и X удовлетворяют равенствам

Р2- Р = Ф1(

ТА(1 — Р) - (I - Р)— Ф2, (I - Р)ТА - (I - Р) = Ф3, ТВР - Р = Ф4,

Р = Ф5, 17

РХР* + (/- Р)Х(1 -Р')-Х = Фв,

TAX {ТА)* - ТВХ{ТВ)* + Р+Р*-1 = Ф7

с матрицами Ф, малой нормы. Будем также предполагать, что X — X' > pl с положительным р. Требуется оценить величины ¡|Л" — Е PjPj 11 и ||Р — Р+0||, а также получить условия на матрицы Ф,-, i = 1,2,...,7, и константу р, при которых такие оценки возможны. Матрицы Pj, j — —со,... ,+оо, определяются для пучка А В — А.

Идея получения таких оценок состоит в построении матриц Т, Р, А, В, X, мало отличающихся от матриц Т, Р, А, В, X, но уже удовлетворяющих условиям теоремы 6. Действительно, в диссертации показано, как построить пучок матриц А В — А, имеющий спектральную матричную последовательность Pj, j = —со, ..., оо, и удовлетворяющий оценкам

||Р -P||<pi||/(1-2M,

||Ф3|| + ||Фз11 + ЦФ1||||ГА||

II(P_O + P+I)-TA|| <гЛ =

||(Р+о + P-i) — ТА\\ < 6д =

1-2ЦФХ11

ЦФ4Ц + ЦФ5Ц + ЦФгНЦГВЦ

1 -2||Ф

j=-oo

^( 11Фб|| + 6||<M|||*|| ,Л/Г1 — 8ЦФ1Ц — 4||4i||||P|| / _

где

Эти оценки имеют место при условии выполнения следующих неравенств:

||Ф,|| + ||Ф«||<1, ' 8ЦФ1Ц + цфлцрц < 1, «¿<1,

||Ф8|| + 6||Ф1М1_ Л ' и-вцфхц-^фхцнрц; •

В параграфе 5.3 выводятся оценки теории возмущений, применимые к построенному выше пучку матриц А В — А. Итак, предположим, что

\\А - (Р_о + Р+ОЦ < £л, \\В -(Р+0+Р-,)\\<6в

с некоторыми малыми ¿д, 6в- Требуется оценить ||Р+0 - Р+о|| и ||Х — где X = Е^-оо X = -оо Р,Р/. В диссертации получены

18

оценки

I р Р + +

~+0 — -М-0 Ь --Г75-,

1 - 2ш0{ёл + - 4о>3о/2(6л + 6В)

8О>03/2(^ + ¿в) + 4и>0(£л +

"о ' 1 - 4£0 (¿л + 6В)</Ы - Ъй30'\бА + 6в)' где (1>о = 11^11-

В параграфе 5.4 представлен второй вариант обобщенных уравнений Ляпунова (ОУЛ II), применимый непосредственно к "почти" нормированному Пучку (А2?д — Ло^сотр И матрицам Рсотр, Нсотр. Рассмотрим уравнения

Р2-Р = 0, ЯР* - РП = 0,

(3)

АН А* - ВНВ* -А(1-Р- Р*)А* -В{1-Р- Р')В* = Ф и соотношения

гапкИР, ВР] < гапкР, гапк[Л(/-Р), В(/-Р)] < гапк(/-Р), (4) где \АР, ВР] и [А{1 - Р), В(1 - Р)] - матрицы размеров N х 2И. Теорема 7 Предположим, что П = Я* > О,

У|Щ<<тт1П(А,я),

где <гт;а - минимальное сингулярное число, выполнены уравнения (3) и соотношения (4). Тогда АеХ{В - е;*А) Ф 0 при всех вещественных ф, а матрицы Р и I — Р являются проекторами на инвариантные подпространства пучка А В — А, отвечающие собственным числам соответственно внутри и вне единичного круга. Более того,

Я - ^ /> - е^А)-\АА* + ВВ')(В - <

Предположим теперь, что система (3) и соотношения (4) выполнены приближенно, т.е. имеется система матричных уравнений

Р2-Р = фь ЯР*-РЯ = Ф2,

' 19

AHA* - BHB* -A(I-P- P')A* -B[J-P- P*)B* = Ф3, а также соотношения

&n-t({AP, BP]) = ф, <rr([A(/ - P), B(I - P)j) = ф,

где г - целое число, 0 < г < N, а о\ < <тг < ... < сгц - сингулярные числа, упорядоченные по возрастанию. Величины ||®i||, ЦФгЦ, ||Фз||, Ф, ф достаточно малы. Тогда

1|я («1 +11«,II + ^пяи) +

АЫЧавШ, В)\\ + 6АВ)

о-т,ч(А, В) - ¿лв - 42еМ*в(||(А, В)|| + 6АВУ

||Р_ Р|| < И*'» , 73йа^(||(Л, В)\\ + 6лв)

11 11 - 1 - 2||Фг|| ^ оыМ, В) - 6АВ - бЗс^/^лвСКА, В)||-+ ¿дв)'

raew = [||Ф2||+||Я||/(1-2||Ф1||)]/(1-г)1Л,и, =^+2||Ф1||||(А, В)||/(1-2||Ф:||),

= МФзИ -ь -ь W (||Ф3|| -ь 2"Т-Ю) ^

+2«ДВ(2||(А, В)|| + 6ЛВ) (||Я|| + ||Р|| + у^щ) • Эти оценки не имеют места, если не выполнены условия

6 > + 1-Sll1^11) ^ ~ amiM' В) " бАВ'

В шестой главе представлены применения DICH-алгоритма к решению ряда задач численного анализа. В параграфе 6.1 рассматривается задача об отделимости спектра матрицы от мнимой оси, т.е. задача о дихотомии спектра матрицы мнимой осью, которая была впервые подробно изучена С.К. Годуновым и А.Я. Булгаковым.

Пусть А - N х iV-матрица, не имеющая точек спектра на мнимой оси. Эрмитову матрицу

Я = 2||А|| jT (if / - A)-(i(I - АГЧ) 20

назовем обобщенной матрицей Ляпунова, ассоциированной с задачей о дихотомии спектра А мнимой осью. Параметром дихотомии матрицы А будет число /с(Л) = ||Я||.

Чтобы вычислить матрицу Я и проектор Р на инвариантное подпространство матрицы А, отвечающее точкам спектра слева от мнимой оси, используется модифицированный РЮН-алгоритм, состоящий из трех этапов.

Этап I. Вычисляем матричную экспоненту от матрицы В = А*/(2||А||), затем определяем матрицу Ь, удовлетворяющую уравнению

LV - Г

Jo

ешеш*А.

'о

В итоге получаем матричный пучок ХВо — А0 = L '(А/ — ев).

Этап II. Проводится то итераций второго этапа основного DICH-алгоритма над исходным пучком А Л о — Ао.

Этап III. Вычисляются матрицы — (.Amо + В По

УЧА

ТПф + Вто) *> Сгто — [(А^ + В то/ ^то] • Можно показать, что Н^ Я, G^ —► Р при то —► оо. Более того,

2 у/ке'2"0'1/*

HGmo - РII < ! _

||Я - (Arno + Впю)"1^ + Д».П1 < 2к2е~2т°'л + 4 к^е-2"0'1^ + 2т°+1ке-2т"-1'к

~ 1 - 4i/icc~2mo_1/t '

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

В пункте 6.1.3 диссертации выявляется родство DICH-алгоритма с методом матричной сигнум-функции. Расчетные формулы метода сигнум-функции очень просты:

А0 = А, А* = afcAjt_i +(1 - k = 1,2,...,

где ак - специальным образом подбираемый параметр. Мы рассмотрим только выбор а к — 1/2. Можно доказать, что в методе матричной сигнум-функции Ак I - 2Р при к —► оо, где Р - проектор на инвариантное подпространство А, отвечающее собственным числам в левой полуплоскости.

Оказывается, что метод сигнум-функции можно проинтерпретировать как метод неортогонального исключения для пучка А(А—/)—(А+ I), неортогональный аналог БЮН-алгоритма, что и продемонстрировано в пункте 6.1.3 диссертации. Как следствие этой связи, показано, что скорость сходимости метода матричной сигнум-функции оценивается параметром дихотомии ш для пучка А (А — I) — (А + I):

4о;е-2'/(1+и')

В параграфе 6.2 предлагается применение БЮН-алгоритма к решению матричного уравнения Риккати С} + АГА + Л А — ЛВЯ-1ЯТЛ = О, возникающего, например, в теории автоматического управления. Здесь матричная пара (А,<2) детектируема, матричная пара {А, В) стабилизируема, £2 = фт>0,Д = Яг>0. Чтобы вычислить матрицу решения Л, сначала применим первый и второй этапы модификации Б1СН-алгоритма для решения задачи о дихотомии спектра гамильто-новой матрицы

А -В11-1ВТ —Ат

мнимой осью. Затем предельную матрицу А^ разобьем на два блока (А„^ = размеров х N и решим линейную систему А^Л — —А$ методом наименьших квадратов.

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

Будем рассматривать только регулярные матричные полиномы вида А(А) = Ао + А\А -I-... + АЯА", п > 2, где А] - матрицы одинаковых размеров N х И, а <1е1 А(А) не равен тождественно нулю при всех комплексных А. При этом ограничимся только такими полиномами, для которых выполняется условие

Я =

ёе^Ао + АцР + ... + Апе{пф) ф О 22

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

Собственные числа регулярного матричного полинома А(А) определяются стандартным способом: а именно, корни скалярного полинома det Л(А) называются конечными собственными значениями А(А), а нулевые собственные значения матрицы Ап - бесконечными собственными значениями полинома А(А).

Для матричного полинома, удовлетворяющего условию (5), поставим следующую задачу о факторизации: найти матричный полином В(А) = В0 + ... + BiXd, Bi — I (если это возможно!), который делит А(А) справа, и выполнены следующие условия:

det В(А) Ф 0 при |А| > 1,

det(A(A)B-1(A)) ф 0 при |А| < 1.

Другими словами, требуется разложить А(А) в произведение многочленов С(А)В(А) так, чтобы спектр полинома 5(A) лежал внутри единичного круга, а спектр С(А) - вне единичного круга.

Схема алгоритма, решающего поставленную задачу, следующая:

в конструируется линейный пучок матриц

А» 0 '

Ап-1 Лп Ai Аг....Ал

в если det(A" + е'^М) ф 0 для любого вещественного ф, то при помощи DICH-алгоритма вычисляются спектральные проекторы Ро и Poo = I — Ро пучка К + fiM, отвечающие собственным числам внутри и вне единичного круга соответственно;

о если rank(Po) = Nd, то проверяется невырожденность верхней угловой Nd х Nd-подматрицы IIq ортогонального проектора По, отвечающего собственным числам пучка К + цМ внутри единичного круга (проектор По также вычисляется DICH-алгоритмом и одновременно с Ро, как показано в параграфе 2.1);

• если величина обусловленности матрицы П$ не слишком велика, то вычисляется угловая Ndx iVd-подматрица Pf матрицы (iiTPOT + MP0)~lKYlo, и находится решение линейной системы УП^ = Р*.

23

К+ »м

Ао Ах А0

О

An-i Ап-2

Ао

В результате получается матрица

-1 а ' ' "

I |

О I

... ,

О / В( ... . Вл-1

которая дает В(А) = Во -I- В] Л +... 4- * А"*-' +1 Аа - решение задачи о факторизации.

Обусловленность рассмотренной задачи о факторизации матричных полиномов в нашей методике определяется параметрами дихотомии пучка К -I- цМ и обусловленностью матрицы Пд.

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

В диссертации

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

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

3. предложен и детально разработан ортогональный вариант метода матричной сигнум-функции (Б1СН-алгоритм) для решения задачи о спектральной дихотомии пучка матриц единичной окружностью, а также некоторые модификации этого метода;

4. разработана теория сходимости БЮН-алгоритма и проведен априорный анализ ошибок округления при вычислениях по этому алгоритму в арифметике чисел с плавающей точкой, тем самым обеспечив математически строгое доказательство эффективной сходимости 01СН-алгоритиа в условиях реальных вычислений на ЭВМ;

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

24

У =

Во

О

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

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

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

1. Малышев А.Н. Факторизация матричных полиномов //Сиб. мат.журн.-1982.-Т.23,Ш.-С. 136-146.

2. Малышев А.Н. Вычисление инвариантных подпространств регулярного линейного пучка матриц.-Новосибирск,1988.-24 с.-(Препринт /АН СССР.Сиб.отд-ние.Ин-т математики; N 6)

3. Малышев А.Н. Численная факторизация матричных полиномов.-Новосибирск,1989.-9 с.-(Препринт /АН СССР.Сиб.отд-ние.Ин-т математики; N 5)

4. Малышев А.Н. Вычисление инвариантных подпространств регулярного линейного пучка матриц //Сиб.мат.журн.-1989.-Т.30,М.-С.76-86.

5. Малышев А.Н. Гарантированная точность в спектральных задачах линейной алгебры //Тр.Ин-та математики /АН СССР.Сиб.отд-ние.-Новосибирск,1990.-Т.17.-С. 19-104.

6. Малышев А.Н. Программа исследования устойчивости матриц методом Ляпунова //ГосФАП CCCP.-1990.-Per.N 50900000539.

7. Малышев А.Н. Введение в вычислительную линейную алгебру.-Новосибирск: Наука,1991.-228 с.

8. Malyshev A.N. Parallel aspects of some spectral problems in linear algebra.-Amsterdam,1991.-38p.-(Tech.report /Centre for Mathematics and Computer Science; NM-R9113).

9. Malyshev A.N. Guaranteed accuracy in spectral problems of linear algebra. I //Siberian Advances in Mathematics.-1992.-Vol.2,No.l.-P.144-197.

10. Malyshev A.N. Guaranteed accuracy in spectral problems of linear algebra. II //Siberian Advances in Mathematics.-1992.-Vol.2,No.2.-P.153-204.

11. Malyshev A.N. Parallel algorithm for solving some spectral problems of linear algebra //Linear Algebra and Its Applic.-1992.-Vols.188/189.-P.489-520.

V