Содержание к диссертации
Введение
Глава 1. Псевдоподобия и унитарные конгруэнции 14
1.1. Некоторые сведения из теории псевдоподобий 15
1.2. Некоторые сведения об унитарных конгруэнциях 25
1.3. О достижимости компактных форм посредством унитарных конгруэнции 30
Глава 2. Сопряжённо-нормальные матрицы 37
2.1. Основные свойства. Связь с нормальными матрицами...38
2.2. Множество сопряжённо-нормальных матриц как вещественное алгебраическое многообразие 43
2.3. Сопряжённо-нормальные матрицы с сопряжённо-нормальными главными подматрицами 48
Глава 3. Метод MINRES-CN 53
3.1. Приведение к компактным формам посредством конечных ортогональных процессов 55
3.2. Алгоритм CSYM. Связь с крыловскими подпространствами 59
3.3. Обобщённый процесс Ланцоша...- 63
3.4. Приведение сопряжённо-нормальной матрицы к блочно-трёхдиагональной форме. Метод MINRES-CN 65
3.5. Особенности программной реализации метода MINRES-CN2 67
3.6. Численные результаты. Сравнение с GMRES 76
Глава 4. Малоранговые возмущения симметричных и сопряжённо-нормальных систем 86
4.1. Сопряжённо-нормальные возмущения симметричных матриц 89
4.2. Произвольные возмущения симметричных матриц 91
4.3. Малоранговые возмущения нормальных и сопряжённо-нормальных матриц 92
Литература 99
Приложение. Процедура MINRES-CN2 104
- О достижимости компактных форм посредством унитарных конгруэнции
- Множество сопряжённо-нормальных матриц как вещественное алгебраическое многообразие
- Приведение сопряжённо-нормальной матрицы к блочно-трёхдиагональной форме. Метод MINRES-CN
- Малоранговые возмущения нормальных и сопряжённо-нормальных матриц
Введение к работе
Метод сопряжённых градиентов (м.с.г.) является одним из наиболее известных алгоритмов для решения систем линейных уравнений. Предложенный первоначально как прямой метод для систем с положительно определёнными матрицами коэффициентов (см. [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. Спроектируем на Сп векторы построенной обобщённой степенной последовательности. В результате будут получены пробные подпространства некоторого итерационного процесса, идущего в Сп. Ортонормированная система векторов, начинающаяся с 5i и извлекаемая из этих пробных подпространств, определяет приведение к блочно-трёхдиагональной форме Н самой матрицы А. Это приведение достигается уже не подобиями, а унитарными конгруэнциями, но о матрице
Н можно сказать то же самое, что и в обобщённом процессе Ланцоша: в общем случае порядки её диагональных блоков даются последовательными натуральными числами 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 симметрична, её возмущение К кососимметрично и имеет малый ранг, а матрица A = S 4- К всё ещё сопряжённо-нормальная, то применимость к А варианта MINRES-CNk при подходящем к не вызывает сомнения. Однако оказывается, что, начиная с некоторого шага, расчётные формулы для такой матрицы А можно сократить до трёхчленной рекурсии, что существенно уменьшает арифметическую работу, выполняемую методом.
Если матрицы S и К не связаны специальным соотношением псевдоперестановочности, то их сумма" A = S 4- К не будет сопряжённо-нормальной матрицей. Тем не менее мы показываем, что при малоранговой компоненте К матрица А всё ещё может быть приведена к блочно-трёхдиагональной форме, в которой оценка на размер диагонального блока даётся числом, зависящим от к = rank К. Таким образом, MINRES-CN, построенный как метод для сопряжённо-нормальных матриц, оказывается применимым и к некоторым матрицам, не обладающим
свойством сопряжённой нормальности.
Ешё более общие результаты установлены в 4.3. Здесь рассматриваются произвольные малоранговые возмущения нормальных или сопряжённо-нормальных матриц. Предполагается, что исходная матрица N допускает приведение к блочно-трёхдиагональному виду (посредством, соответственно, унитарных подобий или конгруэнции) с достаточно хорошей оценкой too для размера диагонального блока. Доказано, что и возмущённая матрица А = N + R может быть приведена к блочно-трёхдиагональной форме. Разумеется, оценка на размер диагонального блока ухудшается пропорционально рангу добавки R. Заметим, что матрица А не обязана быть нормальной или сопряжённо-нормальной.
Выше было отмечено, что сопряжённо-нормальные матрицы известны гораздо меньше, чем нормальные. К этому можно добавить, что и изучены они гораздо хуже. Некоторые новые факты, касающиеся сопряжённо-нормальных матриц, приведены в параграфах 2.2 и 2.3. В 2.2 множество CJ\fn сопряжённо-нормальных матриц порядка п изучается как вещественное алгебраическое многообразие в МП(С), рассматриваемом как вещественное линейное пространство размерности п2. Вычислена размерность этого многообразия и показана его приводимость. Для сравнения упомянем известный факт неприводимости многообразия Afn, состоящего из комплексных нормальных п х тг-матриц. В 2.3 исследуется ситуация, когда сопряжённо-нормальная хессенбергова матрица Н имеет сопряжённо-нормальную же главную подматрицу порядка т, 1 < т < п. Оказывается, что в этом случае Н необходимо является трёхдиагональной матрицей. Ранее аналогичный факт был установлен относительно нормальных матриц (см. [22, 23]).
Большая часть первой главы носит справочный характер. В 1.2
приведены необходимые для дальнейшего сведения об унитарных конгруэнциях, а в 1.1 дан очерк теории псевдоподобий. Подобно сопряжённо-нормальным матрицам, этот тип матричных преобразований, включающий в себя унитарные конгруэнции, недостаточно освещен в книжной литературе по теории матриц и материал для этих двух параграфов был отобран из журнальных публикаций. Здесь, в частности, введены важные понятия псевдособственных значений и псевдоинвариантных подпространств, а также сформулированы основные факты, связанные с этими понятиями.
Заключительный параграф первой главы имеет оригинальное содержание. Рассматривается вопрос о достижимости различных компактных форм посредством унитарных конгруэнции. Основной результат состоит в том, что если компактная форма содержит более п(п — 1)/2 нулевых элементов, то найдутся п х n-матрицы, которые не могут быть приведены к такой форме. Отсюда, в частности, следует, что при п > 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 всё еще применим.
Исследование множества СМп сопряжённо-нормальных матриц как вещественного алгебраического многообразия в МП(С).
Исследование достижимости компактных форм с большим числом нулевых элементов посредством унитарных конгруэнции.
Заканчивая это введение, отметим, что все численные эксперименты, описанные в диссертации, проведены на двухъядерном PC 2Duo Е630 OEM с тактовой частотой 1.86 Ггц и объемом оперативной памяти 1024 Мб.
О достижимости компактных форм посредством унитарных конгруэнции
Существенным вкладом в теорию метода MINRES-CN можно считать результаты главы 4. Здесь рассматривается вопрос о применимости метода в том случае, если симметричная или сопряжённо-нормальная матрица коэффициентов линейной системы подвергается малоранговым возмущениям. Если матрица S симметрична, её возмущение К кососимметрично и имеет малый ранг, а матрица A = S 4- К всё ещё сопряжённо-нормальная, то применимость к А варианта MINRES-CNk при подходящем к не вызывает сомнения. Однако оказывается, что, начиная с некоторого шага, расчётные формулы для такой матрицы А можно сократить до трёхчленной рекурсии, что существенно уменьшает арифметическую работу, выполняемую методом.
Если матрицы S и К не связаны специальным соотношением псевдоперестановочности, то их сумма" A = S 4- К не будет сопряжённо-нормальной матрицей. Тем не менее мы показываем, что при малоранговой компоненте К матрица А всё ещё может быть приведена к блочно-трёхдиагональной форме, в которой оценка на размер диагонального блока даётся числом, зависящим от к = rank К. Таким образом, MINRES-CN, построенный как метод для сопряжённо-нормальных матриц, оказывается применимым и к некоторым матрицам, не обладающим свойством сопряжённой нормальности.
Ешё более общие результаты установлены в 4.3. Здесь рассматриваются произвольные малоранговые возмущения нормальных или сопряжённо-нормальных матриц. Предполагается, что исходная матрица N допускает приведение к блочно-трёхдиагональному виду (посредством, соответственно, унитарных подобий или конгруэнции) с достаточно хорошей оценкой too для размера диагонального блока. Доказано, что и возмущённая матрица А = N + R может быть приведена к блочно-трёхдиагональной форме. Разумеется, оценка на размер диагонального блока ухудшается пропорционально рангу добавки R. Заметим, что матрица А не обязана быть нормальной или сопряжённо-нормальной.
Выше было отмечено, что сопряжённо-нормальные матрицы известны гораздо меньше, чем нормальные. К этому можно добавить, что и изучены они гораздо хуже. Некоторые новые факты, касающиеся сопряжённо-нормальных матриц, приведены в параграфах 2.2 и 2.3. В 2.2 множество CJ\fn сопряжённо-нормальных матриц порядка п изучается как вещественное алгебраическое многообразие в МП(С), рассматриваемом как вещественное линейное пространство размерности п2. Вычислена размерность этого многообразия и показана его приводимость. Для сравнения упомянем известный факт неприводимости многообразия Afn, состоящего из комплексных нормальных п х тг-матриц. В 2.3 исследуется ситуация, когда сопряжённо-нормальная хессенбергова матрица Н имеет сопряжённо-нормальную же главную подматрицу порядка т, 1 т п. Оказывается, что в этом случае Н необходимо является трёхдиагональной матрицей. Ранее аналогичный факт был установлен относительно нормальных матриц (см. [22, 23]).
Большая часть первой главы носит справочный характер. В 1.2 приведены необходимые для дальнейшего сведения об унитарных конгруэнциях, а в 1.1 дан очерк теории псевдоподобий. Подобно сопряжённо-нормальным матрицам, этот тип матричных преобразований, включающий в себя унитарные конгруэнции, недостаточно освещен в книжной литературе по теории матриц и материал для этих двух параграфов был отобран из журнальных публикаций. Здесь, в частности, введены важные понятия псевдособственных значений и псевдоинвариантных подпространств, а также сформулированы основные факты, связанные с этими понятиями.
Заключительный параграф первой главы имеет оригинальное содержание. Рассматривается вопрос о достижимости различных компактных форм посредством унитарных конгруэнции. Основной результат состоит в том, что если компактная форма содержит более п(п — 1)/2 нулевых элементов, то найдутся п х n-матрицы, которые не могут быть приведены к такой форме. Отсюда, в частности, следует, что при п 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.2) унитарной матрицей U. О полученном соотношении говорят, что матрицы А и В унитарно конгруэнтны, а само преобразование называют унитарной конгруэнцией.
Известно, что в вычислительной линейной алгебре унитарные подобия являются излюбленным типом преобразований подобия. Это объясняется тем, что, наряду с собственными значениями, унитарные подобия сохраняют и сингулярные числа матрицы. Сохраняются, следовательно, и функции от сингулярных чисел, такие, как унитарно-инвариантные матричные нормы, среди которые наиболее важны спектральная норма и евклидова (или фробениусова) норма Инвариантность нормы есть необходимое условие численной устойчивости преобразований, используемых в практической линейной алгебре, и унитарность матрицы преобразования гарантирует выполнение этого условия. По тем же самым причинам унитарные конгруэнции являются наиболее практичным типом преобразований псевдоподобия. Помимо псевдособственных значений, они сохраняют сингулярные числа и производные функции от них. В классической линейной алгебре важнейшим результатом об унитарных подобиях является теорема Шура о триангуляризации. Согласно этой теореме, всякую матрицу А є Мп{0) посредством подходящего унитарного подобия можно привести к треугольной форме (по желанию, верхней или нижней). Естественно, что диагональными элементами этой формы являются собственные значения матрицы А. Отсюда следует, между прочим, что при п 5 приведение к форме Шура, вообще говоря, нельзя осуществить, выполняя конечную последовательность арифметических операций и взятия радикалов над С. Аналогом теоремы Шура в теории псевдоподобий является теорема, доказанная в 1961 г. канадским математиком Юла (см. [12]). Теорема 1.5 (теорема Юла). Всякая матрица А Є МП(С) может быть посредством унитарной конгруэнции приведена к блочно-треугольной форме (по желанию, верхней или нижней) с диагональными блоками порядков 1 и 2. Блоки порядка 1 суть неотрицательные псевдособственные значения матрицы А, а каждый блок порядка 2 соответствует паре её комплексно сопряжённых псевдособственных значений. Без ограничения общности, можно считать, что такой 2 х 2-блок Yj подчиняется соотношению Блочно-треугольную матрицу У из теоремы 1.5 будем называть нормальной формой Юла матрицы А. Как и в случае формы Шура, приведение к форме Юла при п 5, вообще говоря, нельзя осуществить посредством конечной последовательности арифметических операций и взятия радикалов над С. В противном случае было бы возможно вычисление в радикалах для собственных значений матриц вида АА. Однако существуют компактные формы относительно унитарных подобий и конгруэнции, которые могут быть получены с помощью конечного числа арифметических операций и квадратичных радикалов. Упомянем, например, о приведении матрицы А Є Мп{С) к (верхней) форме Хессенберга, т.е. п х n-матрице Н, такой, что Если п не слишком велико, то такое приведение может быть достигнуто посредством п — 2 подобий, использующих отраоюения (иначе называемые элементарными унитарными матрицами или матрицами Хаусхолдера). На первом шаге строится п х п-отражение 7i\ так, чтобы аннулировать элементы (3,1), (4,1),..., (п, 1) произведения Тії А. Шаг , завершается достраиванием этого произведения до матрицы унитарно подобной исходной матрице А и имеющей требуемую форму в первом столбце. На втором шаге используется матрица вида где 7Ї2 — отражение порядка п — 1, выбранное так, чтобы обратить в нуль элементы (4,2), (5,2),..., (п, 2) произведения 7 2 1- Результатом второго шага является матрица имеющая желаемую форму в своих первых двух столбцах. Продолжая таким образом и уменьшая на каждом шаге порядок активного отражения, мы в п — 2 шага придём к хессенберговой матрице Н. Если матрица А на входе этого процесса эрмитова, то унитарно подобные ей матрицы Лі, 2,... также будут эрмитовыми. Это означает, что эрмитова хессенбергова матрица Ап-2 = Н в действительности является трёхдиагональной. Таким образом, всякую эрмитову матрицу посредством конечного процесса можно привести к трёхдиагональному виду.
Приведение сопряжённо-нормальной матрицы к блочно-трёхдиагональной форме. Метод MINRES-CN
В вещественном случае эти определения совпадают и описывают одно и то же множество; в комплексном случае они существенно различаются. Так, свойство (2.1) сохраняется унитарными подобиями, а свойство (2.2) нет. Напротив, унитарные конгруэнции сохраняют свойство (2.2), но не свойство (2.1).
Хорошо известно, какую важную роль нормальные преобразования и матрицы играют в классической линейной алгебре. Сопряжённо-нормальные матрицы выполняют сходную роль в теории унитарных конгруэнции. В 2.1 мы даём краткий очерк основных свойств сопряжённо-нормальных матриц, сопоставляя их с соответствующими свойствами нормальных матриц.
Множества нормальных и сопряжённо-нормальных матриц не являются комплексными аналитическими многообразиями, чему препятствует участие сопряжённой матрицы А в определениях (2.1) и (2.2), а в случае свойства (2.2) — ещё и знак комплексного сопряжения в правой части. Однако оба множества суть вещественные аналитические (и даже алгебраические) подмногообразия в МП(С).
Анализ множества нормальных матриц как вещественного алгебраического многообразия был выполнен в [20]. В 2.2 мы проводим аналогичный анализ для множества сопряжённо-нормальных матриц. I Изложение в этом параграфе основано на совместной статье [21] автора и Х.Д. Икрамова. Представим матрицу А є МП(С) (п 3) в блочном виде где В Є Мт(С) (1 т п) и С, D - матрицы размера т х (n — т). Для нормальной матрицы А, не являющейся эрмитовой или косоэрмитовой, нормальность подматрицы В представляет собой весьма нестандартную ситуацию, немало говорящую о частичной структуре А или ее структуре в целом. Например, в контексте приведения А к форме Хессенберга Н посредством алгоритма Арнольди, Т. Хукле обнаружил следующее обстоятельство (см. [22]): если Н неразложима и ее ведущая главная подматрица Нт (1 т п) нормальна, то в действительности Н -трехдиагональная матрица. В [23] этот факт был оформлен и доказан как чисто теоретико-матричная теорема, без какого-либо упоминания о методе Арнольди. В 2.3 мы проводим аналогичное исследование для сопряжённо-нормальной хессенберговой матрицы Н с сопряжённо-нормальной главной подматрицей Нт. Изложение в этом параграфе основано на совместной статье [24] автора и Х.Д. Икрамова. 2.1. Основные свойства. Связь с нормальными матрицами Среди многочисленных характеризаций нормальных матриц следующая является наиболее важной: Свойство 1. Матрица А є Мте(С) тогда и только тогда является нормальной, когда А может быть приведена к диагональному виду посредством унитарного подобия: U AU = Л. (2.4) Диагональными элементами матрицы Л = diag(Ai,..., Хп) являются собственные значения матрицы А. В геометрических терминах свойство 1 может быть переформулировано таким образом: матрица А є Мп(С) тогда и только тогда является нормальной, когда А имеет ортонормированный базис из собственных векторов. Одним из .таких базисов являются столбцы матрицы U в равенстве (2.4). Свойству 1 соответствует следующее свойство сопряжённо-нормальных матриц: Свойство 1. Всякая сопряжённо-нормальная матрица А є Мп(С) посредством подходящей унитарной конгруэнции может быть приведена к блочно-диагональному виду с диагональными блоками порядков 1 ш 2. Блоки порядка 1 суть неотрицательные псевдособственные значения матрицы А; блоки порядка 2 соответствуют парам её сопряжённых комплексных псевдособственных значений lJLj, pj и имеют вид Обратно, всякая блочно-диагональная матрица Л указанного вида, а, значит, и всякая матрица, полученная из Л унитарной конгруэнцией, является сопряжённо-нормальной. Свойство 1 (при несколько иной форме 2 х 2-блоков) было установлено в [25]. Форма (2.5) для 2 х 2-блоков была найдена в более ранней работе [26]. Свойство 1 может быть записано матричным соотношением, аналогичным равенству (2.4), а именно где Л теперь является блочно-диагональной матрицей. Столбцы унитарной матрицы U, соответствующие её 1 х 1-блокам, суть псевдособственные векторы матрицы Л, а пары столбцов, отвечающие её 2 х 2-блокам, образуют базисы двумерных А-псевдоинвариантных подпространств. Таким образом, геометрическая трактовка формулы (2.6) состоит в том, что для сопряжённо-нормальной матрицы Л Є Мп(С) существует разложение пространства Сп в ортогональную сумму одно- и двумерных псевдоинвариантных подпространств этой матрицы. Определение (2.1) нормальной матрицы А есть требование, чтобы А коммутировала со своей сопряжённой матрицей А . Неудивительно поэтому, что А и А имеют ряд общих характеристик. Свойство 2 . Если А є Мп(С) — нормальная матрица, то: а) ітА = ітЛ , кет А — кегЛ ; б) А и А имеют одни и те же собственные векторы; более общо, в) А и А имеют одни и те же инвариантные подпространства. Определение (2.2) сопряжённо-нормальной матрицы А допускает сходную интерпретацию. Переписав (2.2) в виде ЛЖ = Ат А, видим, что А должна быть псевдоперестановочна с транспонированной матрицей Ат. Теперь общие характеристики имеют А и Ат. Свойство 2. Если А Є Мп(С) — сопряжённо-нормальная матрица, то: а) ітА = ітАТ, кет А = кетАт; б) Л и Ат имеют одни и те же псевдоинвариантные подпространства. В основе замечательной численной устойчивости, свойственной алгоритмам для нормальных матриц, лежит следующее свойство: Свойство 3. Матрица А є Мте(С) тогда и только тогда является нормальной, когда её сингулярные числа совпадают с модулями её собственных значений. Аналогичное свойство справедливо для сопряжённо-нормальных матриц: Свойство 3. Матрица А є Мп(С) тогда и только тогда является сопряжённо-нормальной, когда её сингулярные числа совпадают с модулями её псевдособственных значений. Рассмотрим теперь декартово разложение (1.21). Свойство 4. Матрица А Є Мп(С) тогда и только тогда является нормальной, когда эрмитовы матрицы В и С в её декартовом разложении перестановочны. Как следствие свойства 4 , имеем Свойство 5 . Если матрица А є Мп(С) нормальна, то собственные значения эрмитовой матрицы В (С) в её декартовом разложении суть вещественные (мнимые) части собственных значений самой матрицы А. В случае сопряжённо-нормальной матрицы А вместо декартова разложения нужно рассматривать SSS-разложение (1.24). Свойство 4- Матрица А є Мп(С) тогда и только тогда является сопряжённо-нормальной, когда симметричная матрица S и кососимметричная матрица К в разложении (1.24) псевдоперестановочны.
Малоранговые возмущения нормальных и сопряжённо-нормальных матриц
Некоторые методы (например, MINRES и GMRES), широко применяемые при решении систем линейных уравнений, в известном смысле являются итерационными вариантами прямых процедур для приведения матрицы к специальным компактным формам посредством унитарных подобий. Этот тезис мы разъясняем в 3.1. Там же определяется понятие конечного ортогонального процесса, используемое в дальнейшем тексте диссертации.
Названные выше методы, как и многие другие популярные методы решения линейных систем, ищут приближённые решения в так называемых крыловских подпространствах. Для системы и заданного начального вектора х$ подпространство Крылова размерности га (1 т п) определяется как Тем самым Km(A,xo) есть линейная оболочка начального отрезка степенной последовательности порождённой матрицей А и вектором Хо. Условимся писать просто /Ст, если А и Хо ясны из контекста. Отметим, что использование крыловских подпространств для итерационного решения линейных алгебраических систем считается одной из десяти важнейших алгоритмических идей 20-го столетия (см. [29, 30]).
Метод CSYM, предложенный в [31] для решения комплексных симметричных систем, был первым итерационным методом, в основе которого лежит приведение матрицы к компактной форме посредством унитарных конгруэнции, а не унитарных подобий. Мы описываем этот метод в 3.2.
Авторы [31] считают, что CSYM фундаментально отличается от методов крыловских подпространств. Действительно, пробные подпространства, в которых CSYM ищет приближения к решению системы, не являются крыловскими. Однако мы показываем в 3.2, что CSYM можно интерпретировать как проекцию на Сп обычного ланцошева процесса, проводимого в пространстве удвоенной размерности с эрмитовой матрицей и специальным начальным вектором. Эта интерпретация позволяет нам в 3.4 обобщить CSYM на случай систем с сопряжённо-нормальными матрицами коэффициентов. Для сопряжённо-нормальной матрицы А матрица (3.4) нормальна в обычном смысле. Поэтому наше расширение метода CSYM строится на основе обобщённого процесса Ланцоша, предложенного в [32] именно для нормальных матриц. Краткое описание этого процесса дано в 3.3. Компактная форма нормальной матрицы А, вычисляемая обобщённым процессом Ланцоша, представляет собой блочно-трёхдиагональную матрицу, порядки диагональных блоков которой медленно возрастают. Такова же компактная форма сопряжённо-нормальной матрицы А, получаемая проектированием ланцошева процесса на Сп. Если А удовлетворяет уравнению вида где /(гг, у) — многочлен степени fc п, то порядки диагональных блоков, достигнув значения к, стабилизируются на этом значении, а компактные л формы матриц А и. А превращаются в ленточные матрицы с шириной ленты d, определяемой числом к. По отношению к итерационному процессу это означает, что глубина рекурсии, определяющей очередной вектор, не превосходит d. В 3.5 подробно обсуждается метод MINRES-CN2. Это вариант нашего расширения метода CSYM, рассчитанный на случай, когда многочлен / в формуле (3.5) имеет степень к = 2. Результаты численных экспериментов с этим методом и его сравнение с GMRES даны в заключительном параграфе 3.6. Изложение в данной главе в значительной мере построено на основе совместной статьи [35] автора и Х.Д. Икрамова. В 1.2 были описаны два процесса для приведения матрицы А є Мп(С) к форме Хессенберга посредством последовательности отражений. В одном из процессов использовались подобия, в другом — конгруэнции. Рассматриваемые на уровне элементарных операций, эти процессы представляют собой конечные последовательности четырёх арифметических действий и извлечения квадратных корней. Такие конечные последовательности мы для краткости будем называть конечными ортогональными процессами. Это название можно оправдать тем, что на каждом шаге приведения к форме Хессенберга текущая матрица умножается (слева и справа) на унитарные, а в вещественном случае — ортогональные матрицы, а именно матрицы Хаусхолдера. Однако термин "конечный ортогональный процесс" мы будем использовать и в том случае, когда никакого формального умножения заданной матрицы на унитарные или ортогональные матрицы не происходит. Рассмотрим с этой точки зрения, например, метод Арнолъди для приведения матрицы А є МП(С) к (верхней) форме Хессенберга (см. [33])
