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

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

Моджтаба Гасеми Камалванд

Сопряженно-нормальные матрицы и методы конгруэнтного типа для систем линейных алгебраических уравнений

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

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

003468031

Москва-2009

003468031

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

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

профессор Икрамов Хаким Дододжанович

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

профессор Морозов Владимир Алексеевич

кандидат физико-математических наук, старший научный сотрудник Белянков Анатолий Яковлевич.

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

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

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

Автореферат разослан " '

и

2009 года

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

диссертационного совета , Суворов В.В

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

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

Метод сопряжённых градиентов (м.с.г.) является одним из наиболее известных алгоритмов для решения систем линейных уравнений. Предложенный первоначально (в 1952-53 гг.) как прямой метод для систем с положительно определёнными матрицами коэффициентов, он с 1970-х годов стал использоваться как итерационный метод и в таком качестве приобрёл огромную популярность. Этому способствовало следующее свойство метода: на каждом его шаге величины, необходимые для продолжения процесса, — направление спуска, текущее приближение к решению системы, его невязка, — определяются посредством коротких (двух- или трёхчленных) рекурсий через аналогичные величины, вычисленные на предыдущих шагах. В 1970-х годах была осознана связь м.с.г. с алгоритмом Ланцоша, методом, предназначенным для вычисления собственных значений симметричных матриц и не требовавшим от этих матриц знакоопределённости. Это позволило Пэйджу и Сондерсу построить в 1975 г. методы для симметричных незнакоопределённых систем, сохраняющие главное достоинство м.с.г., а именно описание каждого шага посредством коротких рекурсий.

В 1981 г. Голуб сформулировал следующую задачу: найти трёхчленные формулы спуска типа м.с.г. для несимметричных (а в комплексном случае — неэрмитовых) матриц либо доказать, что таких формул не существует. Упоминание о спуске здесь не случайно: оно подразумевает, что в пробных подпространствах, используемых методом, строятся ортогональные базисы. Это сообщает процессу некоторый запас численной устойчивости, отсутствующий в таких, например, методах, как ВЮС

1 ■ Г О

• г,

(алгоритм бисопряжённых градиентов), тоже управляемый короткими рекурсиями.

Задача Голуба была вскоре решена В.В. Воеводиным и Е.Е. Тыртышниковым в СССР и — независимо и несколько позже — американцами Фабером и Мантойфелем. Полученный ими ответ оказался разочаровывающим: если ограничиться обычной унитарной (а не прозвольной положительно определённой) метрикой в С" и исключить из рассмотрения матрицы с небольшим числом различных собственных значений, то построение метода желаемого типа возможно лишь для матриц А, являющихся линейными многочленами от эрмитовых матриц, т.е. для матриц вида А = аН + 01, Н = Н*.

Несмотря на этот отрицательный ответ, задача Голуба положила начало целому направлению исследований, в которых изучается возможность построения алгоритмов типа м.с.г. для различных классов неэрмитовых систем при тех или иных расширительных допущениях. Так, на каждом шаге методов, исследованных американскими математиками Ягелсом, Райхелем, Бартом и Мантойфелем, разрешается использовать несколько ранее вычисленных матрично-векторных произведений, а не одно, как в м.с.г. В методе MINRES-N, построенном Дана, Зыковым и Икрамовым, наряду с произведениями вида Av вычисляются произведения вида A*w, и т.д. То обстоятельство, что данное направление остаётся актуальным, подтверждается появлением в 2008 г. обзора по экономичным итерационным методам типа м.с.г. в авторитетном журнале SIAM Review.

Цель работы

В настоящей работе автор ставил перед собой следующие цели:

1. Исходя из интерпретации м.с.г., MINRES, GMRES и других методов как итерационных вариантов прямых процедур для приведения матриц к

том или иным компактным формам, исследовать возможности построения итерационных методов, проистекающие из замены в этих процедурах унитарных подобий унитарными конгруэпциями. По отношению к комплексным симметричным системам такая попытка была предпринята в 1999 г. немецкими математиками Бунзе-Герстнер и Стевером. Одной из основных задач диссертации было распространение построенного ими метода СЭУМ на как можно более широкий класс систем. Таким классом оказались системы с сопряженно-нормальными матрицами коэффициентов. От расширения метода СЗУМ, которое автор хотел построить и которое назвал МШИЕБ-ОЧ, требовалось, чтобы для систем указанного класса оно выдерживало конкуренцию с широко известным методом GMR.ES (обобщенным методом минимальных невязок). В частности, по сравнению с GMR.ES, новый метод должен предъявлять меньшие требования к памяти и выполнять меньшую арифметическую работу на каждом шаге.

2. Определить типы сопряженно-нормальных матриц, для которых КПМКЕБ-СМ может быть реализован посредством рекурсии с фиксированным числом членов. Составить МаШЬ-процедуры для этих типов матриц и сравнить их производительность с производительностью библиотечной процедуры gmres, реализующей СКШЕБ в Ма11аЬ'е.

3. Исследовать возможность применения MINRES-CN и, в особенности, его вариантов, управляемых короткими рекурсиями, к малоранговым возмущениям симметричных и сопряженно-нормальных матриц.

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

конгруэнций.

Научная новизна работы

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

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

Различные варианты метода MINRES-CN реализованы в виде МаШЬ-процедур и показали значительно более высокую эффективность, чем библиотечная МаШЬ-процедура gmres.

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

Решение систем линейных уравнений является одной из важнейших задач практических вычислений. Метод МШКЕБ-СК, разработанный в данной диссертации, предназначен для нового класса линейных систем, а именно систем с сопряженно-нормальными матрицами коэффициентов. Он включает в себя, в частности, комплексные системы с симметричными и кососимметричными матрицами. В этом круге задач MINRES-CN значительно эффективней используемого в настоящее время

метода GMRES. Можно надеяться поэтому, что составленные автором программные реализации MINRES-CN и его вариантов найдут применение в практических расчетах.

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

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

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

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

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

— профессор A.B. Тихонравов.

Публикации

Основные результаты диссертации отражены в публикациях [1-5]. Структура и объем работы

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

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

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

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

Глава 1. Псевдоподобия и унитарные конгруэнции

Псевдоподобиями называются преобразования комплексных матриц, имеющие вид

А —» Р~1АР, (1)

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

А —» <этАд, (2)

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

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

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

Глава 2. Сопряженно-нормальные матрицы

Матрица А е Мп(С) (пространства комплексных п х п-матриц) называется нормальной, если

АЛ* = А* А, (3)

и сопряжённо-нормальной, если

АА* = ЖА, (4).

В вещественном случае эти определения совпадают и описывают одно и то же множество; в комплексном случае они существенно различаются. Так, свойство (3) сохраняется унитарными подобиями, а свойство (4) нет. Напротив, унитарные конгруэнции сохраняют свойство (4), но не свойство

(3).

Хорошо известно, какую важную роль нормальные преобразования и матрицы играют в классической линейной алгебре. Сопряжённо-нормальные матрицы выполняют сходную роль в теории унитарных конгруэнций. В § 2.1 дан краткий очерк основных свойств сопряжённо-нормальных матриц в сопоставлении с соответствующими свойствами нормальных матриц. Поскольку книжная литература по этому вопросу отсутствует, этот очерк, как и в случае §§ 1.1 и 1.2, составлен на основе журнальных публикаций.

Множества нормальных и сопряжённо-нормальных матриц не являются комплексными аналитическими многообразиями, чему препятствует

участие сопряжённой матрицы А* в определениях (3) и (4), а в случае свойства (4) — ещё и знак комплексного сопряжения в правой части. Однако оба множества суть вещественные аналитические (и даже алгебраические) подмногообразия в Мп{С). Анализ множества нормальных матриц как вещественного алгебраического многообразия был выполнен в 1998 г. Х.Д. Икрамовым. В § 2.2 проведен аналогичный анализ для множества сопряжённо-нормальных матриц. Вычислена размерность этого многообразия (она равна п2 + п) и показана его приводимость. Для сравнения упомянем, что многообразие Мп, состоящее из комплексных нормальных п х п-матриц, неприводимо.

Представим матрицу А 6 М„(С) (п > 3) в блочном виде

где В 6 Мт(С) (1 < т < п) и С, Б - матрицы размера т х (п — т). Для нормальной матрицы А, не являющейся эрмитовой или косоэрмитовой, нормальность подматрицы В представляет собой весьма нестандартную ситуацию, немало говорящую о частичной структуре А или ее структуре в целом. Например, в контексте приведения А к форме Хессенберга Н посредством алгоритма Арнольди, немецкий математик Хукле обнаружил следующее обстоятельство : если Н неразложима и ее ведущая главная подматрица Нт (1 < т < п) нормальна, то в действительности Н - трехдиагональная матрица. Позднее, в работе Х.Д. Икрамова и Л. Эльзнера, этот факт был оформлен и доказан как чисто теоретико-матричная теорема, без какого-либо упоминания о методе Арнольди. В § 2.3 проведено аналогичное исследование для сопряжённо-нормальной хессенберговой матрицы Я с сопряжённо-нормальной главной подматрицей Нт.

Глава 3. Метод МШНЕЯ-СК

Эта глава является основной в диссертации. Она начинается обсуждением понятия конечного ортогонального процесса (§3.1), а затем подробным анализом метода СЭУМ (§3.2). Упомянутые выше Бунзе-Герстнер и Стевер, авторы СБУМ, считают, что используемые в этом методе пробные подпространства радикально отличаются от крыловских. Однако в диссертации указана их связь с крыловскими подпространствами специального типа. Для этого комплексной симметричной матрице А рассматриваемой системы сопоставляется эрмитова матрица А удвоенного

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

полученным путем "удвоения"начального вектора <?1 метода СЭУМ, при проектировании её на Сп порождает пробные подпространства этого метода.

Найденная связь между СЭУМ и алгоритмом Ланцоша используется в §3.4 для того, чтобы распространить СЭУМ на весь класс сопряжённо-нормальных матриц. Прежним образом сопоставим матрице А и начальному вектору матрицу А и вектор V удвоенной размерности. Для сопряжённо-нормальной А матрица А оказывается нормальной в обычном смысле. В 1997 г. Х.Д. Икрамов и Л. Эльзнер показали, что всякая нормальная матрица может быть приведена к блочно-трёхдиагональной форме, в которой порядки диагональных блоков в типичном случае принимают последовательные значения 1,2,3,.... Такое приведение может

порядка

(б)

быть достигнуто посредством конечной последовательности элементарных унитарных подобий или в итерационной форме, которую Икрамов и Эльзнер назвали обобщённым процессом Ланцоша. Суть этого процесса кратко изложена в § 3.3.

Предположим, что обобщённый процесс Ланцоша применён к матрице А и начальному вектору V. Спроектируем на С" векторы построенной обобщённой степенной последовательности. В результате будут получены пробные подпространства некоторого итерационного процесса, идущего в С". Ортонормированная система векторов, начинающаяся с и извлекаемая из этих пробных подпространств, определяет приведение к блочно-трёхдиагональной форме Н самой матрицы А. Это приведение достигается уже не подобиями, а унитарными конгруэнциями, но о матрице Н можно сказать то же самое, что и в обобщённом процессе Ланцоша: в общем случае порядки её диагональных блоков даются последовательными натуральными числами 1,2,3,.... Как следствие, число ненулевых элементов в Н выражается величиной 0(п3/2), тогда как форма Хессенберга матрицы А содержит ~ |п2 ненулевых элементов. Это означает, что на каждом шаге обобщённого СЭУМ-процесса, названного МЖИЕЯ-СК, выполняется значительно меньшая арифметическая работа, чем в методе СМ КЕБ.

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

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

Случаю к = 2 в диссертации уделено особое внимание. Соответствующая этому случаю разновидность метода МШИЕЯ-СМ названа МШЛЕЗ-С^. В § 3.5 обсуждаются особенности процесса ортогонализации в .\lINRES-CiN2, способы выбора приближённых решений в пробных подпространствах и экономичные способы пересчёта нормы невязки при переходе к очередному шагу. В § 3.6 описаны численные эксперименты, в которых \1INRES-CN2 сравнивался с СМЯЕЭ. Поскольку арифметическая работа, выполняемая на одном шаге, в первом методе существенно меньше, чем во втором, то основным критерием сравнения было число итераций до достижения заданного уровня для нормы невязки. Оказалось, что и по этому показателю МШНЕЯ-СШ во многих случаях значительно превосходит СМГ1ЕЗ. Распечатка МаШЬ-процедуры, реализующей МШНЕЭ-СШ, приведена в Приложении.

Глава 4. Малоранговые возмущения симметричных и сопряженно-нормальных систем

Результаты этой главы существенно развивают теорию метода MINR.ES-С1Ч. Здесь рассматривается вопрос о применимости метода в том случае, если симметричная или сопряженно-нормальная матрица коэффициентов линейной системы подвергается малоранговым возмущениям. В § 4.1

исследуется ситуация, когда матрица S симметрична, её возмущение К кососимметрично и имеет малый ранг, а матрица А = S + К всё ещё сопряжённо-нормальная. При этих предположениях применимость к А варианта MINRES-CNk при подходящем к не вызывает сомнения. Однако неожиданным оказывается то обстоятельство (доказываемое в § 4.1), что, начиная с некоторого шага, расчётные формулы для такой матрицы А можно сократить до трёхчленной рекурсии, что существенно уменьшает арифметическую работу, выполняемую методом.

Если матрицы S и К не связаны специальным соотношением псевдоперестановочности, то их сумма А = S + К не будет сопряжённо-нормальной матрицей. Эта ситуация рассматривается в § 4.2. Показано, что при малоранговой компоненте К матрица Л, несмотря на отсутствие свойства сопряженной нормальности, всё ещё может быть приведена к блочно-трёхдиагональной форме, в которой оценка на размер диагонального блока даётся числом, зависящим от к = rank К. Таким образом, MINRES-CN, построенный как метод для сопряжённо-нормальных матриц, оказывается применимым и к некоторым матрицам, не являющимся сопряженно-нормальными.

Ешё более общие результаты установлены в § 4.3. Здесь рассматриваются произвольные малоранговые возмущения нормальных или сопряжённо-нормальных матриц. Предполагается, что исходная матрица N допускает приведение к блочно-трёхдиагональному виду (посредством, соответственно, унитарных подобий или конгруэнций) с достаточно хорошей оценкой шо для размера диагонального блока. Доказано, что и возмущённая матрица А = N + R может быть приведена к блочно-трёхдиагональной форме. Разумеется, оценка на размер диагонального блока ухудшается пропорционально рангу добавки R. Заметим, что матрица А не обязана быть нормальной или сопряжённо-

нормальной.

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

Основной результат диссертации состоит в построении нового итерационного метода, предназначенного для решения систем линейных уравнений с сопряженно-нормальными матрицами коэффициентов. На этом классе систем построенный метод MINRES-CN значительно превосходит по памяти и быстродействию хорошо известный метод СМ-КЕБ. Новизна метода состоит в том, что в (неявном) приведении матрицы системы к компактной форме унитарные подобия заменяются унитарными конгруэнциями. Практическую ценность метода MINRES-CN значительно повышают следующие результаты, полученные диссертантом:

1. Если все псевдособственные значения матрицы А сосредоточены на алгебраической кривой невысокой степени к, то MINRES-CN описывается рекурсией фиксированной длины (зависящей от к). До сих пор методы с этим свойством были известны только для некоторых типов нормальных и комплексных симметричных матриц.

2. Показано, что экономичные варианты метода МШНЕЗ-СИ применимы и к матрицам, являющимся малоранговыми возмущениями сопряженно-нормальных матриц. Эти возмущенные матрицы могут уже не быть сопряженно-нормальными.

3. Доказано, что для сопряженно-нормальной матрицы с малоранговой кососимметричной компонентой МШПЕЭ-ОЧ, начиная с некоторого шага, фактически управляется трехчленной рекурсией подобно классическому методу Ланцоша.

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

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

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

1. Гасеми Камалванд М., Икрамов X. Д. Сопряженно-нормальные матрицы с сопряженно-нормальными подматрицами // Зап. научн. семин. ПОМИ. 2007. Т. 346. С. 21-25.

2. Гасеми Камалванд М., Икрамов X. Д. О достижимости компактных форм посредством унитарных конгруэнций // Ж. вычисл. матем. и матем. физ. 2008. Т. 48. N 8. С. 1339-1343.

3. Гасеми Камалванд М., Икрамов X. Д. О размерности многообразия сопряженно-нормальных матриц // ДАН. 2008. Т. 423. N 6. С. 727-729.

4. Гасеми Камалванд М., Икрамов Х.Д. Об одном методе конгруэнтного типа для линейных систем с сопряжённо-нормальными матрицами коэффициентов // Ж. вычисл. матем. и матем. физ. 2009. Т. 49. N 2. С. 203-216.

5. Гасеми Камалванд М., Икрамов Х.Д. Малоранговые возмущения симметричных матриц и их компактные формы относительно унитарных конгруэнций // Ж. вычисл. матем. и матем. физ. 2009. Т. 49. N 4. С. 595600.

6. Гасеми Камалванд М., Икрамов Х.Д. Малоранговые возмущения нормальных и сопряженно-нормальных матриц и их компактные формы относительно унитарных подобий и конгруэнций // Вести. Моск. ун-та. Серия "Вычисл. математика и кибернетика". 2009. N 3. С.

Подписано в печать 10.04.09 Формат 60x88 1/16. Объем 1 п.л. Тираж 75 экз. Заказ № 838 Отпечатано в ООО «Соцветие красок» 119991 г.Москва, Ленинские горы, д.1 Главное здание МГУ, к. А-102

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

Введение.

Глава 1. Псевдоподобия и унитарные конгруэнции.

1.1. Некоторые сведения из теории псевдоподобий.

1.2. Некоторые сведения об унитарных конгруэнциях.

1.3. О достижимости компактных форм посредством унитарных конгруэнций.

Глава 2. Сопряжённо-нормальные матрицы.

2.1. Основные свойства. Связь с нормальными матрицами.

2.2. Множество сопряжённо-нормальных матриц как вещественное алгебраическое многообразие.

2.3. Сопряжённо-нормальные матрицы с сопряжённо-нормальными главными подматрицами.

Глава 3. Метод MINRES-CN.

3.1. Приведение к компактным формам посредством конечных ортогональных процессов.

3.2. Алгоритм CSYM. Связь с крыловскими подпространствами.

3.3. Обобщённый процесс Ланцоша.-.

3.4. Приведение сопряжённо-нормальной матрицы к блочно-трёхдиагональной форме. Метод MINRES-CN.

3.5. Особенности программной реализации метода MINRES-CN2.

3.6. Численные результаты. Сравнение с GMRES.

Глава 4. Малоранговые возмущения симметричных и сопряжённонормальных систем.

4.1. Сопряжённо-нормальные возмущения симметричных матриц.

4.2. Произвольные возмущения симметричных матриц.

4.3. Малоранговые возмущения нормальных и сопряжённо-нормальных матриц.

Метод сопряжённых градиентов (м.с.г.) является одним из наиболее известных алгоритмов для решения систем линейных уравнений. Предложенный первоначально как прямой метод для систем с положительно определёнными матрицами коэффициентов (см. [41]), он с 1970-х годов стал использоваться как итерационный метод и в таком качестве приобрёл огромную популярность. Этому способствовало следующее свойство метода: на каждом его шаге величины, необходимые для продолжения процесса, — направление спуска, текущее приближение к решению системы, его невязка, — определяются посредством коротких (двух- или трёхчленных) рекурсий через аналогичные величины, вычисленные на предыдущих шагах. В 1970-х годах была осознана связь м.с.г. с алгоритмом Ланцоша (см. [34]), методом, предназначенным для вычисления собственных значений симметричных матриц и не требовавшим от этих матриц знакоопределённости. Это позволило построить для симметричных незнакоопределённых систем методы, сохраняющие главное достоинство м.с.г., а именно описание каждого шага посредством коротких рекурсий (см. [42]).

В 1981 г. Е. Голуб сформулировал следующую задачу: найти трёхчленные формулы спуска типа м.с.г. для несимметричных (а в комплексном случае — неэрмитовых) матриц либо доказать, что таких формул не существует. Упоминание о спуске здесь не случайно: оно подразумевает, что в пробных подпространствах, используемых методом, строятся ортогональные базисы. Это сообщает процессу некоторый запас численной устойчивости, отсутствующий в таких, например, методах, как BiCG (алгоритм бисопряжённых градиентов), тоже управляемый короткими рекурсиями.

Задача Голуба была вскоре решена В.В. Воеводиным и Е.Е. Тыртышниковым в СССР и — независимо и несколько позже — американцами Фабером и Мантойфелем. Полученный ими ответ оказался разочаровывающим: если ограничиться обычной унитарной (а не прозвольной положительно определённой) метрикой в Си и исключить из рассмотрения матрицы с небольшим числом различных собственных значений, то построение метода желаемого типа возможно лишь для матриц А, являющихся линейными многочленами от эрмитовых матриц, т.е. для матриц вида А = аН + (31, Н = Н*.

Несмотря на этот отрицательный ответ, задача Голуба положила начало целому направлению исследований, в которых изучается возможность построения алгоритмов типа м.с.г. для тех или иных классов неэрмитовых систем при тех или иных расширительных допущениях. Так, на каждом шаге методов, рассматриваемых в [43, 44], разрешается использовать несколько ранее вычисленных матрично-векторных произведений, а не одно, как в м.с.г. В методе MINRES-N, построенном в [45], наряду с произведениями вида Av вычисляются произведения вида A*w, и т.д. То обстоятельство, что данное направление остаётся актуальным, подтверждается появлением недавнего обзора [46].

В настоящей работе мы развиваем взгляд на такие методы, как м.с.г., алгоритм Ланцоша, MINRES, GMRES и др., как на итерационные варианты прямых процедур для приведения матриц к тем или иным компактным формам. Приведение достигается посредством унитарных подобий, а компактной формой является трёхдиагональная матрица или матрица Хессенберга. Приведение сопровождается выбором приближённых решений в пробных подпространствах, в качестве которых названные методы используют подпространства Крылова. Приближённое решение выбирается в соответствии с условием минимальности вектора ошибки б специальной норме, определяемой матрицей системы (м.с.г.), или по принципу минимальной невязки (MINRES, GMRES).

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

Именно этот тип преобразований является основным для данной диссертации. Отправной пункт здесь — известный факт о возможности приведения произвольной симметричной матрицы к трёхдиагональному виду посредством конечной последовательности элементарных унитарных конгруэнций. Этот факт положен в основу алгоритма CSYM, предложенного в 1999 г. для решения комплексных симметричных систем (см. [31]). Наша основная цель состояла в том, чтобы распространить CSYM на как можно более широкий класс линейных систем подобно тому как в [45] метод MINRES был обобщен на весь класс систем с нормальными матрицами коэффициентов.

Матричным классом, на который данный подход переносится наиболее естественно, являются сопряжённо-нормальные матрицы. Эти матрицы играют в теории унитарных конгруэнций ту же роль, какую обычные нормальные матрицы выполняют относительно унитарных подобий. Однако известны сопряжённо-нормальные матрицы гораздо меньше, чем нормальные, в связи с чем мы даём в § 2.1 очерк основных сведений о них. Этих сведений нет в справочных книгах по теории матриц и собраны они путём просмотра большого объёма специальной литературы.

Основной в диссертации является глава 3. Она начинается с подробного анализа метода CSYM. Как отмечено в [31], используемые в этом методе пробные подпространства отличаются от крыловских. Однако нам удалось найти их связь с крыловскими подпространствами специального типа. Для этого комплексной симметричной матрице А рассматриваемой системы по определённому правилу сопоставляется эрмитова матрица А удвоенного порядка. Оказывается, что степенная последовательность, генерируемая л матрицей А и начальным вектором, специальным образом связанным с начальным вектором метода CSYM, при проектировании её на Сп порождает пробные подпространства этого метода.

Найденная связь между CSYM и алгоритмом Ланцоша позволяет понять, каким образом CSYM может быть распространён на весь класс сопряжённо-нормальных матриц. Прежним образом сопоставим матрице А л и начальному вектору q\ матрицу А и вектор v удвоенной размерности. Для сопряжённо-нормальной А матрица А оказывается нормальной в обычном смысле. Известно (см. [32]), что всякая нормальная матрица может быть приведена к блочно-трёхдиагональной форме, в которой порядки диагональных блоков в типичном случае принимают последовательные значения 1,2,3,. Такое приведение может быть достигнуто посредством конечной последовательности элементарных унитарных подобий или в итерационной форме, которая в [32] названа обобщённым процессом Ланцоша.

Предположим, что обобщённый процесс Ланцоша применён к матрице А и начальному вектору v. Спроектируем на Сп векторы построенной обобщённой степенной последовательности. В результате будут получены пробные подпространства некоторого итерационного процесса, идущего в Сп. Ортонормированная система векторов, начинающаяся с q\ и извлекаемая из этих пробных подпространств, определяет приведение к блочно-трёхдиагональной форме Н самой матрицы А. Это приведение достигается уже не подобиями, а унитарными конгруэнциями, но о матрице

Н можно сказать то же самое, что и в обобщённом процессе Ланцоша: в общем случае порядки её диагональных блоков даются последовательными натуральными числами 1,2,3,. Как следствие, число ненулевых элементов в Н выражается величиной 0(n3/2), тогда как форма Хессенберга матрицы А содержит « |?г2 ненулевых элементов. Это означает, что на каждом шаге обобщённого CSYM-процесса, который мы назвали MINRES-CN, выполняется значительно меньшая арифметическая работа, чем в методе GMRES.

Ситуация ещё более благоприятна, если о вспомогательной матрице л

А известно, что её спектр лежит на плоской алгебраической кривой невысокой степени к. (Эту же ситуацию можно эквивалентным образом описать в терминах величин, называемых псевдособственными значениями матрицы А.) Для такой А порядки диагональных блоков в блочно-трёхдиагональной форме Н, достигнув значения к, стабилизируются на этом значении, а саму Н можно интерпретировать как ленточную матрицу с шириной ленты, определяемой числом к. В итерационном процессе решения линейной системы Ах = Ь ленточность матрицы Н означает, что число членов в рекурсии, дающей очередной вектор ортонормальной системы, не зависит от номера шага. Такой процесс можно рассматривать как положительное решение задачи Голуба, если вместо трёхчленных рекурсий допустить рекурсии с любым фиксированным числом членов, не зависящим от порядка п системы. Обнаружение подобных процессов и указание соответствующих им классов матриц мы относим к числу главных результатов диссертации.

Случаю к = 2 в диссертации уделено особое внимание. Соответствующая этому случаю разновидность метода MINRES-CN названа MINRES-CN2. В § 3.5 обсуждаются особенности процесса ортогонализации в MINRES-CN2, способы выбора приближённых решений в пробных подпространствах и экономичные способы пересчёта нормы невязки при переходе к очередному шагу. В § 3.6 описаны численные эксперименты, в которых MINRES-CN2 сравнивался с GMRES. Поскольку арифметическая работа, выполняемая на одном шаге, в первом методе существенно меньше, чем во втором, то основным критерием сравнения было число итераций до достижения заданного уровня для нормы невязки. Оказалось, что и по этому показателю MINRES-CN2 во многих случаях значительно превосходит GMRES. Распечатка Matlab-процедуры, реализующей MINRES-CN2, приведена в Приложении.

Существенным вкладом в теорию метода MINRES-CN можно считать результаты главы 4. Здесь рассматривается вопрос о применимости метода в том случае, если симметричная или сопряжённо-нормальная матрица коэффициентов линейной системы подвергается малоранговым возмущениям. Если матрица S симметрична, её возмущение К кососимметрично и имеет малый ранг, а матрица А = S 4- К всё ещё сопряжённо-нормальная, то применимость к А варианта MINRES-CNk при подходящем к не вызывает сомнения. Однако оказывается, что, начиная с некоторого шага, расчётные формулы для такой матрицы А можно сократить до трёхчленной рекурсии, что существенно уменьшает арифметическую работу, выполняемую методом.

Если матрицы S и К не связаны специальным соотношением псевдоперестановочности, то их сумма" А = S 4- К не будет сопряжённо-нормальной матрицей. Тем не менее мы показываем, что при малоранговой компоненте К матрица А всё ещё может быть приведена к блочно-трёхдиагональной форме, в которой оценка на размер диагонального блока даётся числом, зависящим от к = rank К. Таким образом, MINRES-CN, построенный как метод для сопряжённо-нормальных матриц, оказывается применимым и к некоторым матрицам, не обладающим свойством сопряжённой нормальности.

Ешё более общие результаты установлены в § 4.3. Здесь рассматриваются произвольные малоранговые возмущения нормальных или сопряжённо-нормальных матриц. Предполагается, что исходная матрица N допускает приведение к блочно-трёхдиагональному виду (посредством, соответственно, унитарных подобий или конгруэнций) с достаточно хорошей оценкой соо для размера диагонального блока. Доказано, что и возмущённая матрица А = N + R может быть приведена к блочно-трёхдиагональной форме. Разумеется, оценка на размер диагонального блока ухудшается пропорционально рангу добавки R. Заметим, что матрица А не обязана быть нормальной или сопряжённо-нормальной.

Выше было отмечено, что сопряжённо-нормальные матрицы известны гораздо меньше, чем нормальные. К этому можно добавить, что и изучены они гораздо хуже. Некоторые новые факты, касающиеся сопряжённо-нормальных матриц, приведены в параграфах 2.2 и 2.3. В § 2.2 множество CjVn сопряжённо-нормальных матриц порядка п изучается как вещественное алгебраическое многообразие в Мп{С), рассматриваемом как вещественное линейное пространство размерности п2. Вычислена размерность этого многообразия и показана его приводимость. Для сравнения упомянем известный факт неприводимости многообразия Afn, состоящего из комплексных нормальных п х те-матриц. В § 2.3 исследуется ситуация, когда сопряжённо-нормальная хессенбергова матрица Н имеет сопряжённо-нормальную же главную подматрицу порядка m, 1 < т < п. Оказывается, что в этом случае Н необходимо является трёхдиагональной матрицей. Ранее аналогичный факт был установлен относительно нормальных матриц (см. [22, 23]).

Большая часть первой главы носит справочный характер. В § 1.2 приведены необходимые для дальнейшего сведения об унитарных конгруэнциях, а в § 1.1 дан очерк теории псевдоподобий. Подобно сопряжённо-нормальным матрицам, этот тип матричных преобразований, включающий в себя унитарные конгруэнции, недостаточно освещён в книжной литературе по теории матриц и материал для этих двух параграфов был отобран из журнальных публикаций. Здесь, в частности, введены важные понятия псевдособственных значений и псевдоинвариантных подпространств, а также сформулированы основные факты, связанные с этими понятиями.

Заключительный параграф первой главы имеет оригинальное содержание. Рассматривается вопрос о достижимости различных компактных форм посредством унитарных конгруэнций. Основной результат состоит в том, что если компактная форма содержит более п(п — 1)/2 нулевых элементов, то найдутся п х п-матрицы, которые не могут быть приведены к такой форме. Отсюда, в частности, следует, что при п > 5 существуют (несимметричные) матрицы, неприводимые к трёхдиагональному виду. Возможность приведения к трёхдиагональному виду матриц порядка 3 легко доказывается непосредственно. Тот же вопрос для матриц порядка 4 остаётся в настоящее время открытым. Заметим, что аналогичные вопросы относительно унитарных подобий были ранее изучены в [13-18].

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

MINRES-CN имеет для матриц этого класса на порядок лучшие характеристики, чем GMRES. Так, требования к памяти для системы порядка п составляют соответственно 0(п3/2) и 0(п2) машинных слов.

Разумеется, и MINRES-CN, и GMRES являются итерационными методами. Если для конкретной системы с сопряжённо-нормальной матрицей коэффициентов А оба метода сходятся за сравнимое число итераций, то преимущество MINRES-CN проявляется в меньших требованиях к памяти и существенно меньшей арифметической работе, выполняемой на каждом шаге. Эти достоинства MINRES-CN проявляются особенно выпукло, если псевдособственные значения матрицы А сосредоточены на плоской алгебраической кривой невысокой степени к.

Если создание и алгоритмическую проработку метода MINRES-CN и его вариантов, таких, как MINRES-CN2, можно оценить как главное достижение диссертации, то теоретический и практический интерес представляют ещё несколько результатов, полученных диссертантом. Среди них:

1. Указание матриц за пределами класса сопряжённо-нормальных матриц, к которым MINRES-CN всё еще применим.

2. Исследование множества СМп сопряжённо-нормальных матриц как вещественного алгебраического многообразия в Мп(С).

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

Заканчивая это введение, отметим, что все численные эксперименты, описанные в диссертации, проведены на двухъядерном PC 2Duo Е630 OEM с тактовой частотой 1.86 Ггц и объемом оперативной памяти 1024 Мб.

1. Гасеми Камалванд М., Икрамов X. Д. О достижимости компактных форм посредством унитарных конгруэнций // Ж. вычисл. матем. и матем. физ. 2008. Т. 48. N 8. С. 1339-1343.

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

3. Haantjes J. Klassifikation der antilinearen Transformationen j j Math. Annalen. 1935. B. 112. S. 98-106.

4. Asano K., Nakayama T. Ueber halblineare Transformationen // Math. Annalen. 1938. B. 115. S. 87-144.

5. Bevis J.H., Hall F.J., Hartwig R.E. Consimilarity and the matrix equation AX — XB = C. Proceedings of the Third Auburn Matrix Theory Conference. North Holland, Amsterdam, 1987, pp. 51-64.

6. 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.

7. Fassbender H., Ikramov Kh.D. Some observations on the Youla form and conjugate-normal matrices // Linear Algebra Appl. 2007. V. 422. P. 29-38.

8. Ikramov Kh. D. On condiagonalizable matrices // Linear Algebra Appl. 2007. V. 424. P. 456-465.

9. Воеводин В.В. Линейная алгебра. М. : Наука, 1980.

10. Hong Y.P., Horn R.A. A canonical form for matrices under consimilarity // Linear and Multilinear Algebra. 1989. V. 25. N 2. P. 105-119.

11. Hong Y.P., Horn R.A. On simultaneous reduction of families of matrices to triangular or diagonal form by unitary congruences // Linear and Multilinear Algebra. 1985. V. 17. N 3-4. P. 271-288.

12. Youla D.C. A normal form for a matrix under the unitary congruence group // Canad. J. Math. 1961. V. 13. P. 694-704.

13. Longstaff W.E. On tridiagonalization of matrices // Linear Algebra Ap-pl. 1988. V. 109. P. 153-163.

14. Fong C.K., Wu P.Y. Band-diagonal operators // Linear Algebra Appl. 1996. V. 248. P. 185-204.

15. Pati V. Unitary tridiagonalization in // Proc. Indian Acad. Sci. (Math. Sci.). 2001. V. 111. P. 381-397.

16. Davidson K.R., Djokovic D.Z. Tridiagonal forms in low dimensions // Linear Algebra Appl. 2005. V. 407. P. 169-188.V

17. Djokovic D.Z., MacDonald M.L. Orthogonal invariants of a matrix of order four and applications //J. Pure Appl. Algebra. 2005. V. 202. P. 258-283.

18. Djokovic D.Z., Johnson C.R. Unitarily achievable zero patterns and traces of words in A and A* f / Linear Algebra Appl. 2007. V. 421. P. 63-68.

19. Милнор Дж., Уоллес А. Дифференциальная топология. Начальный курс. М.: Мир, 1972.

20. Икрамов X. Д. О размерности многообразия нормальных матриц // Ж. вычисл. матем. и матем. физ. 1998. Т. 38. N 1. С. 5-10.

21. Гасеми Камалванд М., Икрамов Х.Д. О размерности многообразия сопряжённо-нормальных матриц // ДАН. 2008. Т. 423. N6. С. 727-729.

22. Huckle Т. The Arnoldi metod for normal matrices // SIAM J. Matrix Anal. Appl. 1994. V. 15. N2. P.479-489.

23. Икрамов X. Д., Эльзнер JI. О нормальных матрицах с нормальными главными подматрицами // Зап. научн. семин. ПОМИ. 1995. Т. 229. С 6394.

24. Гасеми Камалванд М., Икрамов Х.Д. Сопряжённо-нормальные матрицы с Сопряжённо-нормальными подматрицами // Зап. научн. семин. ПОМИ. 2007. Т. 346. С. 21-25.

25. Vujicic М., Her but F., Vujicic G. Canonical forms for matrices under unitary congruence transformations I: conjugate-normal matrices // SIAM J.Appl. 1972. V. 23. P. 225-238.

26. Wigner E. P. Normal form of antiunitary operators // J. Math. Phys. 1960. V. 1. P. 409-413.

27. Fassbender H., Ikramov Kh. D. Conjugate-normal matrices: A survey // Linear Algebra Appl. 2008. V. 429. P. 1425-1441.

28. Рид M. Алгебраическая геометрия для всех. М.: Мир, 1991.

29. Cipra В. A. The best of the 20th century: Editors name top 10 algorithms // SIAM News. 2000. V. 33. N 4. P. 1-3.

30. Dongarra J., Sullivan F. The top 10 algorithms in the 20th century // Comput. Sci. Engrg. 2000. V. 2. P. 22-23.

31. Bunse-Gerstner A., Stover R. On a conjugate gradient-type method for solving complex symmetric linear systems // Linear Algebra Appl. 1999. V. 287. P. 105-123.

32. Eisner L., Ikramov Kh.D. On a condensed form for normal matrices under finite sequences of elementary unitary similarities // Linear Algebra Appl. 1997. V. 254. P. 79-98.

33. Arnoldi W. E. The principle of minimized iterations in the solution of the matrix eigenvalue problem // Quart. Appl. Math. 1951. V. 9. N 1. P.17-29.

34. Lanczos C. An iteration method for the solution of the eigenvalue problem of linear differential and integral operators // J. Res. Nat. Bur. Standards. 1950. V. 45. N 4. P. 255-282.

35. Гасеми Камалванд M., Икрамов Х.Д. Об одном методе конгруэнтного типа для линейных систем с сопряжённо-нормальными матрицами коэффициентов // Ж. вычисл. матем. и матем. физ. 2009. Т. 49. N 2. С.

36. Икрамов Х.Д. Сопряжённо-нормальные матрицы и матричные уравнения относительно А, А и АТ // ДАН. 2007. Т. 412. N 3. С. 305307.

37. Дана М., Икрамов Х.Д. Еще раз о решении систем линейных уравнений, матрицы которых являются малоранговыми возмущениями эрмитовых матриц // Зап. научн. семин. ПОМИ. 2005. Т. 334. С. 68-77.

38. Икрамов Х.Д., Эльзнер J1. О матрицах, допускающих унитарное приведение к ленточному виду // Матем. заметки. 1998. Т. 64. N 6. С. 871-880.

39. Гасеми Камалванд М., Икрамов Х.Д. Малоранговые возмущения симметричных матриц и их компактные формы относительно унитарных конгруэнций // Ж. вычисл. матем. и матем. физ. 2009. Т. 49. N 4. С.

40. Гасеми Камалванд М., Икрамов Х.Д. Малоранговые возмущения нормальных и сопряженно-нормальных матриц и их компактные формы относительно унитарных подобий и конгруэнций // Вестн. Моск. ун-та. Серия "Вычисл. математика и кибернетика". 2009. N 3. С.

41. Hestenes M.R., Stiefel Е. Methods of conjugate gradients for solving linear systems // J. Res. Nat. Bur. Standards. 1952. V.49. R 409-436.

42. Paige C.C., Saunders M.A. Solution of sparse indefinite systems of linear equations // SIAM J. Numer. Anal. 1975. V. 12. P. 617-629.

43. Jagels C.F., Reichel L. A fast minimal residual algorithm for shifted unitary matrices // Numer. Linear Algebra Appl. 1994. V. 1. P. 555-570.

44. Barth Т., ManteufFel T. Multiple recursion conjugate gradients algorithms. Part I : Sufficient conditions // SIAM J. Matrix Anal. Appl. 2000. V. 21. N 3. P. 768-796.

45. Дана M., Зыков А.Г., Икрамов Х.Д. Метод минимальных невязок для специального класса линейных систем с нормальными матрицами коэффициентов // Ж. вычисл. матем. матем. физ. 2005. Т. 45. N 11. С. 1928-1937.

46. Liesen J., Strakos Z. On optimal short recurrences for generating orthogonal Krylov subspace bases // SIAM Review. 2008. V. 50. N 3. P. 485-503.