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

• Моджтаба Гасеми Камалванд
• кандидат физико-математических наук
• 2009

Оглавление диссертации кандидат физико-математических наук Моджтаба Гасеми Камалванд

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

Введение.

Глава 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 Мб.

Список литературы диссертационного исследования кандидат физико-математических наук Моджтаба Гасеми Камалванд, 2009 год

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.