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

Московский Государственный Университет им. М.В. Ломоносова Научно-исследовательский вычислительный ив

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

Мансур Дана Хади

Метод минимальных невязок в нестандартных крыловских подпространствах

Специальность 01.01.07 — вычислительная математика

АВТОРЕФЕРАТ

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

Москва—2006

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

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

профессор Х.Д. Икрамов

Официальные оппоненты:

— доктор физико-математических наук,

профессор В.А. Морозов

— кандидат физико-математических наук

А.Я. Белянков

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

Защита диссертации состоится 16 июня 2006 г. в 15 часов на заседании диссертационного совета К 501.001 11 в Московского государственного университета имени М.В. Ломоносова но адресу: 119992, Москва, Ленинские горы, НИВЦ МГУ, конференц-зал.

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

Ученый секретарь диссертационного совета к ф.-м.н

В. В. Суворов

-Юо5(з

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

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

Метод сопряженных градиентов (м. с. г.) был предложен Хестенсом и Штифелем (1952-53 гг.) как прямой метод решения системы линейных уравнений

Ах = Ь (1)

с положительно определенной матрицей А. В 1970-х годах м. с. г. стал рассматриваться как итерационный метод и в этом качестве приобрел огромную популярность. В 1975 г. Пэйдж и Сондерс построили методы ЗУММЬС^ и МШИЕЗ-М, близкие по духу к м. с. г., но не требующие положительной определенности от эрмитовой матрицы А.

Все три названных метода осуществляют построение ортогональных базисов Р\,Р2т ■ в последовательности крыловских подпространств

Кт{А,Ъ) = врап{Ь,АЬ,А2Ь,...,Ат^Ь}, т = 1,2,..., (2)

с помощью коротких (двух- или трехчленных) рекурсий Это привело к постановке следующего вопроса: для каких классов матриц А можно предложить методы типа с. г., которые строили бы ортогональные базисы рьрг, - • • в подпространствах (2), пользуясь рекурсиями вида

т

Рт+1 = Арт + £ а,тр, (3)

1=т—в

при некотором фиксированном малом 5?

Ответ на указанный вопрос был дан в начале 1980-х годов В. В. Воеводиным и Е. Е. Тыртышниковым и - независимо и несколько позже — американцами Фабером и Мантойфелем. Если ограничиться обычной унитарной метрикой в С™ и исключить из рассмотрения матрицы с небольшим числом различных собственных значений, то результат, полученный

1 РОС. НАЦИОНАЛЬНАЯ I

библиотека

С.-Пето" ^Н г . Я

названными математиками, состоит в следующем: построение метода типа с. г. возможно лишь при й = 1 и в этом случае А есть линейный многочлен от эрмитовой матрицы (т.е. А — матрица вида А = аН + /3/, Я = #*).

Задача о построении экономичных методов типа с. г. получила новый импульс в начале 1990-х годов, когда Грэгг, Ягеле и Райхель показали, что ортогональные базисы крыловских подпространств, порожденных унитарной матрицей 17 или линейным многочленом а1/ + /31 от такой матрицы, можно вычислять посредством пары параллельно ведущихся двучленных рекурсий. Это привело к изменению постановки сформулированной выше задачи: рекурсия (3) была заменена на рекурсию вида

т т

Рт+1 = 0,тЛр, ~ $1 , (4)

г=т~4 i=m—s

где в и Ь — фиксированные малые числа.

Наиболее общие из известных в настоящее время достаточных условий для того, чтобы А допускала рекурсию вида (4), были получены Бартом и Мантойфелем (2000 г.). В классе ЛГ нормальных матриц никаких А, отличных от указанных выше, не найдено: если исключить матрицы с малым числом различных собственных значений, то рекурсия типа (4) возможна для эрмитовых и унитарных матриц, а также линейных многочленов от них. За пределами класса N рекурсию типа (4) можно осуществить и для малоранговых возмущений только что перечисленных специальных матриц.

Цель работы

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

1. Построить метод минимальных невязок, пригодный для всего класса нормальных матриц (и называемый поэтому МШ11Е8-1Ч). Метод должен предъявлять меньшие требования к памяти и выполнять меньшую арифметическую работу на шаге, чем широко известный метод GMR.ES.

2. Определить типы нормальных матриц, для которых МДОНЕБ^ может быть реализован посредством рекурсии с фиксированным числом членов. Составить Ма^аЬ-процедуры для этих типов матриц и сравнить их производительность с производительностью библиотечной процедуры §тгез, реализующей GMR.ES в Ма1;1аЬ'е.

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

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

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

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

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

Различные варианты метода МШИББ-К реализованы в виде Ма^аЬ-процедур и показали значительно более высокую эффективность, чем библиотечная МаМаЬ-процедура §тгез.

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

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

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

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

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

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

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

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

35-я конференция математиков Ирана.

Публикации

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

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

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

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

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

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

Раздел 1.1 посвящен обобщенному методу минимальных невязок GMR.ES. Обсуждение алгоритмических деталей, таких, как пересчет нормы невязки, позволяет в дальнейшем упростить аналогичное обсуждение для метода МШКЕБ-И.

Раздел 1.2 излагает концепцию обобщенных крыловских подпространств, принадлежащую X. Д. Икрамову и Л. Эльзнеру и играющую ключевую роль в настоящей работе. Для заданных п х п-матрицы А и п-вектора Ь построим обобщенную степенную последовательность

Удобно рассматривать эту последовательность как состоящую из сегментов длины соответственно 1,2,4,8,16,.... Сегмент с номером к, называемый к-и слоем, можно описать как совокупность векторов вида и = \Уь{А, А*)Ь, где И^в, £) пробегает множество слов степени к от двух некоммутирующих переменных я и Ь.

Обобщенным подпространством Крылова (с номером т) называется подпространство

Глава 1. Предварительные сведения

Ь, АЬ, А*Ь, АЧ, АА'Ь, А'АЬ, А*\ А\ ...

(5)

£т(А 6) = врап^Л, А*)Ь : < т} .

(6)

Его размерность обозначается через £т. Число ит = £т — Рт-1 (т > 1) называется шириной ш-го слоя; мы полагаем и>о = 1.

Ортонормированные векторы г>з, •. •, полученные ортогонализаци-ей последовательности (5), называются векторами Ланцоша. Будем рассматривать А как линейный оператор Л, действующий в С". Из свойств обобщенных крыловскйх подпространств вытекает, что в базисе, составленном из векторов Ланцоша, А имеег блочно-трехдиагональную форму Я, причем размеры блоков определяются числами шт.

Для матриц А общего вида последовательность {и>т} может расти как 2т. Однако для нормальной матрицы А

и>т<т + 1, т = 0,1,2,... . (7)

Отсюда следует, что число ненулевых элементов в Н (называемой компактной формой матрицы А) не превосходит 3\/2п3^2. Эту величину следует сравнить с ~ |гг2 ненулевых элементов в форме Хессенберга, к которой А приводится в СМИЕБ.

Если нормальная матрица А удовлетворяет уравнению

/{А,А*) = 0, (8)

где /(х, у) — многочлен невысокой степени к, то оценку (7) можно заменить на

шт<к, т = 0,1,2,.... (9)

Это означает, что Н можно рассматривать как ленточную матрицу с шириной ленты, определяемой числом к.

В разделе 1.3, заключающем главу 1, дано краткое описание MINR.ES-N как метода, сочетающего принцип минимальных невязок с использованием обобщенных крыловскйх подпространств. Обсуждение алгоритмических деталей, общих для всех вариантов метода, откладывается до главы 2, посвященной МШКЕ!3-К2.

Глава 2. Метод МШГ1ЕЗ-К2

МШПЕЭ-Ш — это специализация МШПЕБ-К для случая, когда многочлен / в формуле (8) имеет степень 2. Иными словами, МШИ-ЕЯ-Ш ориентирован на нормальные матрицы, удовлетворяющие уравнению вида

сиА2 + 2с12АА* + с22А*2 + 2с10А + 2с20А* + сооЛ, = 0 , (10)

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

Программная реализация МШПЕБ^2 существенно различается для случаев

М + |с22| ф о (11)

(так называемый основной вариант) и

си = с22 = 0 . (12)

Заметим, что первый из них включает в себя нормальные матрицы, спектры которых расположены на эллипсе, гиперболе, параболе или паре прямых, а второй — нормальные матрицы со спектрами, сосредоточенными на окружностях (т.е. линейные многочлены от унитарных матриц). Основной вариант метода разбирается в разделе 2.1, а случай (12) — в разделе 2.2.

Оба варианта МШНЕБ-Ш управляются рекурсиями, длина которых не превосходит 6 Описание обоих проводится по одинаковому образцу: вначале обсуждаются алгоритмические детали, а затем представлены результаты численных экспериментов, в которых эффективность Ма^аЬ-процедур, реализующих МШПЕЭ-Ш, сравнивалась с эффективностью библиотечной Ма^аЬ-процедуры gmres. В целом, это сравнение очень благоприятно для МПШЕв-Ш.

Отметим, что изложение в этой главе основано на наших работах [2, 4].

Глава 3. Малоранговые возмущения эрмитовых систем

В третьей главе диссертации показано, что метод MINRES-N, разработанный первоначально для специального класса нормальных матриц, при-менйм, в действительности, к более широкому множеству нормальных и даже анормальных матриц. Чтобы описать это множество, напомним, что всякая квадратная комплексная матрица А может быть единственным образом представлена в виде

А = В + iC , (13)

где

В = В* , С = С* . (14)

Эрмитовы матрицы

В = \(А + А'), С = ^(А-А*) (15)

называются соответственно вещественной и мнимой частями матрицы А. Нормальные матрицы А могут быть охарактеризованы тем свойством, что соответствующие им матрицы (15) перестановочны.

В разделе 3.1 рассматривается класс нормальных матриц А, выделяемый условием

к = rank С < п , (16)

где п --- порядок А Спектр такой матрицы А принадлежит объединению вещественной ори и, самое большее, к прямых, параллельных мнимой оси, т.е. вырожденной ал1,ебраической кривой порядка не выше к + 1. Следовательно, метод MINRES-N применйм к матрицам этого типа. Мы показываем, что для матриц со свойством (16) MINRES-N имеет следующую привлекательную особенность: начиная с некоторого шага, рекурсия длины 3(к + 1), обычно выполняемая этим методом, может быть заменена

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

В разделе 3.2 рассматриваются системы с матрицами (13), для которых

rank С = 1 . (17)

В отличие от раздела 3.1, не требуется, чтобы А была нормальной матрицей, т.е. ее вещественная и мнимая части В и С не обязаны коммутировать. Мы показываем, что к системам этого типа применйм метод MINRES-N2. Эффективность метода иллюстрируется несколькими примерами решения ленточных систем; на этих примерах производительность MINRES-N2 сопоставляется с производительностью библиотечной программы Matlab'a, реализующей GMRES.

В разделе 3.3 условие (17) заменяется на

rank С = к > 1 . (18) «

От матрицы А по-прежнему не требуется нормальности. Доказано, что матрица, удовлетворяющая этому условию, может быть приведена посред- ■

ством унитарного подобия к блочно-трехдиагональному виду, где порядок каждого диагонального блока не превосходит 1 + к. Это означает, что систему (1) с такой матрицей А можно решать методом MINRES-N(1 + к), 4 т.е. вариантом метода MINRES-N, первоначально предназначенным для нормальных матриц, которые удовлетворяют уравнению (8) для некоторого многочлена степени 1 + к. Обсуждаются примеры, в которых производительность MINRES-N(1 + к) для систем, подчиняющихся условию (18), сравнивалась с производительностью GMRES.

Изложение в третьей главе диссертации основано на наших работах [3,

Глава 4. Восстановление матриц по их одноранговым

возмущениям

Описание матриц, для которых возможна рекурсия типа (4), полученное Бартом и Мантойфелем, и результаты главы 3 являются достаточной мотивировкой для рассмотрения следующих двух задач:

Задача 4.1. Известно, что матрица А е Мп(С) является одноранговой коррекцией некоторой эрмитовой матрицы. Иначе говоря, А допускает представление

A — H + R, Я — Я*, rank R = 1 .

Однако сами матрицы Я и R неизвестны. Спрашивается, как найти эти матрицы?

Задача 4.2. Известно, что матрица А € Мп{С) является одноранговой коррекцией некоторой унитарной матрицы, т.е.

A — U + R, U*U = /„, rank R = 1 .

Найти матрицы U и R.

В первом случае мы говорим о восстановлении эрмитовой матрицы Я по ее одноранговому возмущению А, а во втором случае — о восстановлении унитарной матрицы U.

Несмотря на простоту формулировок обеих задач, их решение оказывается нетривиальным. Оно опирается на вспомогательные результаты, излагаемые в разделе 4.1. Задача 4.1 решается в разделе 4.2, а задача 4.2 — в разделе 4 3.

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

построенный для комплексных симметричных матриц Бунзе-Герстнер и Стовером, на более широкий матричный класс.

Приложения 1 и 2 содержат тексты МаЙаЬ-процедур, реализующих МШИЕЗ-Ш соответственно для основного варианта и для линейных многочленов от унитарных матриц. ^

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

Результаты диссертации можно рассматривать как вклад в развитие теории экономичных итерационных методов для решения несамосопряженных систем линейных уравнений. Оригинальность использованного в диссертации подхода состоит в том, что вместо стандартных крыловских подпространств принцип минимальных невязок применяется к обобщенным крыловским подпространствам. Полученный на этом пути метод MINR.ES-N работает для всего класса нормальных матриц и, рассматриваемый как прямой метод, имеет на порядок лучшие характеристики, чем популярный метод GMRES. Так, требования к рабочей памяти для системы порядка п составляют соответственно 0(п3/2) и 0(п2) машинных слов.

Показано, что MINRES-N может быть реализован рекурсией фиксированной длины, если нормальная матрица А удовлетворяет уравнению (8), где /(х, у) — многочлен невысокой степени к. Это число к определяет длину рекурсии.

Случай к = 2 исследован особенно подробно. Этот случай охватывает, в частности, нормальные матрицы со спектрами, сосредоточенными на алгебраических кривых 2-го порядка, т.е. значительно более широкий класс, чем нормальные матрицы Барта - Мантойфеля.

Наконец, показано, что МШКЕБ^ применйм и к малоранговым возмущениям эрмитовых матриц. Эти возмущения могут быть как нормальны-

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

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

1. Дана М., Икрамов Х.Д. О малоранговых коррекциях эрмитовых и унитарных матриц // Ж. вычисл. матем. матем. физ. 2004. Т. 44. С. 13311345.

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

3. Дана М., Икрамов Х.Д. О решении систем линейных уравнений, матрицы которых являются малоранговыми возмущениями эрмитовых матриц // Вести. МГУ. Серия "Вычисл. математика и кибернетика". 2005. N4. С. 15-22.

4. Дана М., Икрамов Х.Д. Метод минимальных невязок для линейных многочленов от унитарных матриц // Ж. вычисл. матем. матем физ. 2006. Т. 46. N6. С.

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

6. Дана М., Икрамов Х.Д. Об одноранговых коррекциях комплексных симметричных матриц // Зап. научн. семин. ПОМИ. 2006. Т. С.

7. Dana М., Ikramov Kh. On low-rank corrections of Hermitian and unitary matrices // Abstract and General Guide. 35rd Iranian Mathematics Conference. Shahid Chamran University of Ahwaz. Ahwaz, Iran, 2004, p. 21.

ÍOOSG

»10056

Издательство ЦПИ при механико-математическом факультете

МГУ им М В. Ломоносова^

Подписано в печать OZ.OS.OS

Формат 60 х 90 1/16 Усл. печ л

Тираж 100 экз Заказ -/¿>

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

Введение.

Глава 1. Предварительные сведения.

1.1. Обобщенный метод минимальных невязок.

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

1.3. Метод МШИЕЗ^.

Глава 2. Метод МШИЕЗ-Ш.

2.1. Основной вариант.

2.1.1. Детали реализации метода.

2.1.2. Численные эксперименты.

2.2. Линейные многочлены от унитарных матриц.

2.2.1. Детали реализации метода.

2.2.2. Численные эксперименты.

Глава 3. Малоранговые возмущения эрмитовых систем.

3.1. Нормальные возмущения.

3.2. Анормальные возмущения ранга 1.

3.3. Анормальные возмущения большего ранга.

Глава 4. Восстановление матриц по их одноранговым возмущениям

4.1. Вспомогательные результаты.

4.1.1. Решение задачи 4.3.

4.1.2. Решение задачи 4.4.

4.2. Восстановление эрмитовых матриц.

4.2.1. Эрмитова матрица А.

4.2.2. гапк(Л - А*) = 1.

4.2.3. гапк(А - А*) = 2.

4.2.4. Нильпотентные матрицы Я.

4.3. Восстановление унитарных матриц.

4.3.1. Унитарная матрица А.

4.3.2. rank (Л* Л - /„) = 1.

4.3.3. rank (А* А - 1п) = 2.

4.4. Восстановление комплексных симметричных матриц

4.4.1. Симметричная матрица А.

4.4.2. rank(Л — Ат) = 1.

4.4.3. тшк(А~Ат) = 2.

Пусть А — заданная п х п-матрица. Фиксируем вектор х и рассмотрим степенную последовательность х,Ах,А2х,.,Ат~1х . (0.1)

Линейная оболочка векторов (0.1) называется т-ы крыловским подпространством, порожденным матрицей А и вектором ж, и обозначается 1Ст(А,х). Если А и х известны из контекста, используется более простой символ /Ст.

С ростом тп размерность подпространства К,т растет, пока, в типичном случае, не достигнет числа ¿{А) — степени минимального многочлена матрицы А. Если в разложении вектора х по корневому базису А отсутствуют какие-либо компоненты, то максимальная размерность крыловского подпространства может оказаться меньше, чем с1(А).

Пусть нужно решить линейную систему

Ах = Ь (0.2) с невырожденной матрицей А Е Мп{С). Будем, для простоты, считать, что к системе (0.2) не применяется предобусловливание (или же что (0.2) есть система, полученная предобусловливанием некоторой первоначальной системы). Итерационный метод, в котором т-е приближение хт (:т — 1,2,.) выбирается в подпространстве /Ст(А, Ь), называется методом кры-ловских подпространств.

Наиболее известным среди этой группы методов является метод сопряженных градиентов. Он предполагает, что матрица А — симметричная (эрмитова) и положительно определенная, и описывается следующим образом:

Алгоритм 0.1. Алгоритм сопряженных градиентов: т = 0; ж0 = 0; г0 = 6; р\ = 6; repeat m = m + 1 z = A-pm

Vm = (rm-lrm-l) / (Pmz) 1 VmPm fm — fm— 1 VmZ frn+1

Pm+1 = rm + (J>m+lPm пока число H^mlb не станет достаточно малым

Здесь хт есть т-е приближенное решение, rm = Ь — Ахт — его невязка и Рт — текущее направление спуска. Вектор хт обладает тем свойством, что вектор ошибки е — хт—х (0.3) хт — точное решение системы (0.2)), рассматриваемый как функция от х е /Ст, имеет минимальную норму е|Ц = (Ае, е)1//2 (0.4) при х = хт. Норма (0.4) имеет смысл как раз потому, что А положительно определена.

Векторы хт, гт и вспомогательные векторы рт вычисляются посредством коротких (двучленных) рекурсий, что является одним из наиболее привлекательных свойств метода сопряженных градиентов. Это свойство удается сохранить для систем (0.2) с симметричными (эрмитовыми) незна-коопределенными матрицами А, изменяя способ выбора хт в подпространстве JCm. Вектор хт можно искать, пользуясь условием Галеркина, т.е. так, чтобы соответствующая невязка гт была ортогональна К,т. Это приводит к методу SYMMLQ [1]. Другая возможность — найти хт, для которого евклидова длина невязки ||гт||2 минимальна в К,т. Этот принцип минимальных невязок определяет метод МШЫЕБ [1].

Предположим теперь, что матрица системы (0.2) несимметричная (неэрмитова) и по-прежнему невырожденна. Можно ли и для этого случая построить метод типа сопряженных градиентов, управляемый короткими рекурсиями? Этот вопрос, актуальный в начале 1980-х годов (см. [2]), был решен в СССР В. В. Воеводиным и Е. Е. Тыртышниковым [3, 4] и — независимо и несколько позже, — американскими математиками Фабером и Мантойфелем [5]. Нам удобно описать полученный этими авторами результат, пользуясь терминологией статьи [5].

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

РА(Х,У) = (Ас, у) , (0.5) задаваемой матрицей А (круглыми скобками обозначено стандартное скалярное произведение в Сп). Если в качестве основной принята обычная евклидова метрика в Сп, то вместо ортогональности в смысле (0.5) говорят об А-сопряженности (или просто сопряженности) векторов рт, откуда и происходит название метода.

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

Рт+1 = АРт + Ц °'гтР1 , (0.6) г=т—в связывающей векторы спуска рт (т = 1,2,.). Эти векторы должны давать базисы крыловских подпространств /Ст, ортогональные относительно той или иной формы рв(х,у) = (Вх,у) , В = В* > 0 . (0.7)

Ортогональность векторов рт обеспечивает минимальность соответствующих векторов ошибки ет = — хт в В-норме ||ет||в. Например, выбор В = А* А отвечает принципу минимальных невязок. Однако, для простоты, мы в дальнейшем полагаем В — 1п.

Будем говорить, что матрица А принадлежит классу СО (в), если для любой системы (0.2) ортогональные базисы крыловских подпространств К,т могут быть построены посредством рекурсии (0.6). Результат Воеводина-Тыртышникова-Фабера-Мантойфеля состоит в описании класса

Как известно, матрица А е Мп{С) является нормальной тогда и только тогда, когда сопряженная матрица А* представима многочленом от А:

Степень многочлена р можно выбрать так, чтобы она не превосходила п—1. Как правило, минимальная степень р и равна п — 1, хотя для некоторых типов нормальных матриц р может быть многочленом малой степени. Так, р{г) = г, если А — эрмитова матрица.

Назовем А в-нормальной матрицей, если в соотношении (0.8) р есть многочлен степени в.

Теорема 0.1 [5]. Матрица А б Мп(С), где п > в + 2, тогда и только тогда принадлежит классу СС(з), когда А является я-нормальной матрицей либо степень й{А) ее минимального многочлена не превосходит 5 + 2.

К этому результату нужно добавить следующее описание б-нормальных матриц:

Теорема 0.2 [5]. Пусть А есть 5-нормальная матрица. Тогда:

1) если й > 1, то А имеет не более в2 различных собственных значений;

2) если б = 1, то А — матрица вида

СОф.

А* = р(А) .

0.8)

А = аН + (31, п )

0.9) где Н — эрмитова матрица, аа и/3 - комплексные числа.

Смысл теорем 0.1 и 0.2 в том, что методы типа сопряженных градиентов, управляемые рекурсией вида (0.6), возможны лишь для нормальных матриц с небольшим числом различных собственных значений либо для матриц, мало отличающихся от эрмитовых (см. (0.9)). Этот, по-существу отрицательный результат способствовал огромной популярности обобщенного метода минимальных невязок СМЫЕБ, предложенного для несамосопряженных систем Саадом и Шульцем [6].

В основе ОМЯЕЗ лежит метод Арнольди унитарного приведения матрицы к форме Хессенберга. Векторы Арнольди, конструируемые в этом методе, составляют ортонормированные базисы крыловских подпространств )Ст(А,Ь).

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

Более подробный анализ СМЯЕБ будет дан в разделе 1.1. Этот анализ позволит нам упростить описание оригинального метода МШШ38-]Ч, развиваемого в данной работе.

Задача о построении экономичных методов типа сопряженных градиентов приобрела новый импульс в начале 1990-х годов с публикацией результатов У. Грэгга (см. [7]). Грэгг показал, что для унитарной матрицы и ортонормированные базисы крыловских подпространств можно построить с помощью двух коротких рекурсий:

Алгоритм 0.2 т+1Рт+1 = ирт + 7т+1Рт ,

Рт+1 = &т+1рт + 1т+1Рт+1 ,

7т+1 = -(ирт,рт), ' (0.10)

Тт+1 = (1 - |7т+1|2)1/2 •

Основываясь на этих формулах, Ягеле и Райхель предложили эффективный алгоритм минимальных невязок для систем (0.2) с матрицами вида

А = аИ + (31 , (0.11) где и — унитарная матрица (см. [8]).

Исключая из формул (0.10) векторы рт, получим соотношение

1 ТТ Цт+1°'ттт

Рт+1 = -иРт--ирт-1 т+1 1т&т+\ Ъ±^)Рт . (0.12)

1т°т+1 0~т+1

Для матрицы вида (0.11) аналогичное соотношение выглядит так:

Рт+1 — АРт--А-Рт-1 аат+1 аутсгт+1 ^----1--)рт -1 пРт-1 •

1тп<?т+\ «СГт+1 ат+1 ^7т^т+1Р

Эти соотношения схожи с (0.6) соответственно при в = 0 и й = 1. В то же время унитарная матрица II, все собственные значения которой различны, не может быть я-нормальной ни для какого малого значения я.

Приведенные факты все же не противоречат теореме 1. По сравнению с (0.6), формулы (0.12) и (0.13) содержат дополнительный вектор {ирт-1 или Арт-х), вычисленный на предыдущем шаге. Это приводит к расширенной постановке вопроса о существовании экономичных методов типа сопряженных градиентов: для каких матриц А ортогональные базисы крыловских подпространств можно строить посредством рекурсий вида т т

Рт+1 = £ Am4Pi ~ Е °"гтРг , (0.14) i=m—t i=m—s где s и t — некоторые малые числа?

В статье [9] даны достаточные условия для положительного ответа на этот вопрос. Назовем нормальную матрицу Л к)-нормальной, если найдутся многочлены pe(z) и (Jk{z) соответственно степени i и /с, такие, что

A*qk{A)=pe{A) . (0.15)

Если, в частности, к = 0 и до есть ненулевая константа, мы получаем ^-нормальные матрицы А. Выше было уже отмечено, что унитарные матрицы U и линейные многочлены (0.11) от них, вообще говоря, не являются ^-нормальными матрицами для малых I. В то же время, равенство

U*U = I (0.16) означает, что всякая унитарная матрица U есть (ОД)-нормальная матрица. Подстановка в (0.16) соотношения (0.11), где коэффициент а предполагается ненулевым, дает

А*(А - (31) = рА + (И2 - Щ2)1 ■ (0.17)

Таким образом, линейный многочлен от унитарной матрицы является (1,1)-нормальной матрицей.

Выделение класса &)-нормальных матриц объясняется тем обстоятельством, что для матрицы А этого класса построение ортогональных векторов спуска с помощью рекурсии вида (0.14) возможно почти для любой правой части b (см. (0.2)). При этом можно считать, что s,t) = (e,k) (o.i8) см. [9]).

Следующая теорема из [10] дает описание класса (£, /с)-нормальных матриц:

Теорема 0.3. Пусть А есть (£, /г)-нормальная матрица, причем £ и к — наименьшие числа, для которых справедливо соотношение (0.15). Тогда:

1) если £ > к + 1, то ¿{А) < £22) если £ = к + 1, то <1(А) < £2 или £ = 1, к = 0;

3) если £ < к и свободный член Д) многочлена отличен от нуля, то ¿(А) < к2 + 1;

4) если £ < к - 1 и Д, = 0, то й{А) < к2;

5) если £ = к - 1 и /?0 = 0, то ¿(А) < /с2 или ^ = 0, к = 1;

6) если £ = /с, то (¿(А) < к2 + 1 или £ = /с = 1.

Поскольку (£, /с)-нормальные матрицы представляют для нас интерес лишь при малых £ и к, то смысл теоремы 0.3 заключается в следующем: если исключить матрицы с небольшим числом различных собственных значений, то возможны лишь случаи (£, к) = (1,0), (£, к) = (0,1) и (£,к) = (1,1). Первый из них соответствует линейным многочленам от эрмитовых матриц, а второй - унитарным матрицам. Можно показать, что (1,1)-нормальные матрицы, имеющие более двух различных собственных значений, — это линейные многочлены от унитарных матриц.

Итак, по сравнению с ¿-нормальными матрицами, расширение класса (£, /с)-нормальных матриц произошло лишь за счет включения матриц вида (0.11). Оказывается, однако, что рекурсия типа (0.14) возможна для еще более широкого класса так называемых обобщенных (£, к)-нормальных матриц. Будем говорить, что А £ Мп(С) — обобщенная (£, А;)-пормальная матрица, если найдутся многочлены ре(г) и (]к{%) соответственно степени £ и к, такие, что т*шк(А*дк(А) - р/(А)) =х<-п. (0.19)

В частности, значение х — 0 соответствует (£, /с)-нормальным матрицам.

Помимо (£, &)-нормальных матриц, новый класс содержит их малоранговые возмущения. Это вытекает из следующей теоремы [9]: Теорема 0.4. Пусть А — матрица вида

А = Аг + А2 , (0.20) где А\ есть (£, /с)-нормальная матрица и гапк^Ь = г. Тогда А является обобщенной (£, &)-нормальной матрицей, для которой

Х<{к + Е+1 )г . (0.21)

Если, в частности, А\ — эрмитова или унитарная матрица, то х 5: 2г. Для матрицы Лх, являющейся линейным многочленом от унитарной матрицы, % < 3г.

В [9] показано, что для обобщенной (£, А;)-нормальной матрицы А построение ортогональных векторов спуска с помощью рекурсии вида (0.14) возможно почти для любой правой части Ь в системе (0.2). При этом параметры в и. I формулы (0.14) должны удовлетворять неравенствам е - £>г-к>х ■ (0.22)

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

1. Симметризация системы, т.е. переход от системы (0.2) к самосопряженной системе

А* Ах = А*Ь . (0.23)

К системе (0.23) можно применить стандартный метод сопряженных градиентов. Явное формирование матрицы А*А не обязательно, поскольку произведения вида А*Ар можно вычислять путем последовательного умножения вектора р на А и А*.

2. Использование, наряду с подпространствами Кт(А,Ь), крыловских подпространств, порожденных сопряженной матрицей А*, и построение пар биортогональных базисов в этих двух последовательностях подпространств. На этих принципах построены такие алгоритмы, как метод би-сопряженных градиентов или метод квазиминимальных невязок.

Недостатком первого приема является то обстоятельство, что число обусловленности матрицы А*А есть квадрат числа обусловленности матрицы А. Поэтому переход к системе (0.23) не рекомендуется при решении плохо обусловленных систем. Недостатки второго приема связаны с часто наблюдаемой плохой обусловленностью биортогональных базисов и даже иногда их отсутствием (явление, называемое обрывом процесса ). Общий недостаток состоит в необходимости использования матрично-векторных произведений вида А*д наряду с произведениями вида Ар. (Справедливости ради, следует отметить, что существуют варианты этих методов, такие, как алгоритмы СОБ или Bi-CGStab, не требующие привлечения матрицы А*).

Результаты настоящей диссертации можно рассматривать как вклад в развитие теории экономичных итерационных методов для решения несамосопряженных систем линейных уравнений. Оригинальность используемого нами подхода состоит в том, что вместо стандартных крыловских подпространств принцип минимальных невязок применяется к обобщенным кры-ловским подпространствам. Эти последние были введены в другом контексте в статье X. Д. Икрамова и Л. Эльзнера ([11]; см. также [12]). Если рассмотреть обобщенную степенную последовательность ж, Ах, А*х, А2х, А*Ах, АА*х, А*2х, А3ж, . , (0.24) то линейные оболочки ее конечны отрезков и называются обобщенными подпространствами Крылова, порожденными матрицей А и вектором х.

Мотивом для введения обобщенных крыловских подпространств в [11] было желание найти компактную форму, по возможности близкую к ленточной, для произвольной нормальной матрицы. Как известно, всякую эрмитову матрицу можно привести к трехдиагональному виду посредством конечного процесса, основанного на унитарных подобиях. Для такого приведения могут использоваться различные методы; к технике, используемой в настоящей работе, ближе всего находится метод Ланцоша, тоже относящийся к числу методов (стандартных) крыловских подпространств.

Если матрица А неэрмитова, то она может быть приведена к форме Хес-сенберга посредством метода Арнольди, представляющего собой обобщение процесса Ланцоша. (Этот метод уже упоминался выше в связи с алгоритмом СМНЕБ.) Метод Арнольди не способен извлечь какие-либо выгоды из информации о нормальности матрицы А и дает для нее все ту же заполненную хессенбергову матрицу. Чтобы приблизить компактную форму к ленточной матрице, т.е. по возможности симметризовать ее, нужно, чтобы процесс приведения использовал не только А, но и сопряженную матрицу А*. Это рассуждение и приводит к обобщенным крыловским подпространствам. Более подробное их обсуждение дано в разделе 1.2.

В [11] показано, что компактная форма Н, в которую обобщенный процесс Ланцоша преобразует произвольную нормальную п х п-матрицу А, представляет собой ленточную матрицу с переменной шириной ленты (такие матрицы иногда называют профильными). Матрицу Н можно рассматривать и как блочно-трехдиагональную, причем порядок ее диагонального блока растет с ростом его индексов. Даже в наихудшем случае (т.е. тогда, когда рост порядка происходит скорее всего) общее число ненулевых элементов в Н не превосходит Зл/2пл^2. Эту величину нужно сопоставить с ~ у ненулевыми элементами хессенберговой матрицы.

Еще более важен следующий факт, также обнаруженный в [11]: пусть нормальная матрица А удовлетворяет соотношению

Л, А*) = 0 , (0.25) где /(х,у) — многочлен степени к. Тогда ширина ленты в матрице Н стабилизируется, начиная с некоторого индекса (зависящего от к). Таким образом, в этом случае компактная форма Н превращается в полноценную ленточную матрицу (или блочно-трехдиагональную матрицу, порядки диагональных блоков которой, начиная с некоторого момента, не возрастают).

Метод МШКЕБ-И, составляющий основное^ содержание настоящей диссертации, предназначен для класса нормальных матриц, охватываемых (при различных к) соотношением (0.25). Этот класс включает в себя, в частности, эрмитовы матрицы (поскольку Н = Н* есть уравнение (0.25) с к = 1), линейные многочлены от них, унитарные матрицы 17 и матрицы вида А = а17 4- /31 (см. (0.16) и (0.17)), т.е. по-существу, весь класс ¿-нормальных матриц. При этом он гораздо шире этого последнего класса.

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

Вторая глава диссертации посвящена более подробному обсуждению метода МШЯЕЗ-Ш, который представляет собой специализацию МШНЕБ-^ для случая, когда в (0.25) к = 2. Иными словами, МШИБЭ-Ш ориентирован на нормальные матрицы, удовлетворяющие уравнению вида спА2 + 2с12АА* + с22А*2 + 2сюЛ + 2с20А* + с001п = 0 , (0.26) где хотя бы один из коэффициентов квадратичной части Сц, С\2 и не равен нулю. При этом случаи сц|2 + |С22|2^0 (0.27) и

Си = С22 - о (0.28) существенно различаются своей реализацией. Заметим, что первый из них включает в себя нормальные матрицы, спектры которых расположены на эллипсе, гиперболе, параболе или паре прямых, а второй — нормальные матрицы со спектрами, сосредоточенными на окружностях (т.е. линейные многочлены от унитарных матриц). Случай (0.27) разбирается в разделе 2.1, а случай (0.28) — в разделе 2.2.

Отметим, что изложение в этой главе основано на наших работах [13, 14].

В третьей главе диссертации показано, что метод МШЯЕЗ-!^, разработанный нами для специального класса нормальных матриц, применйм, в действительности, к более широкому множеству нормальных и даже анормальных матриц. Чтобы описать это множество, напомним, что всякая квадратная комплексная матрица А может быть единственным образом представлена в виде

А = В + гС, (0.29) где в = В* , С = с*.

0.30)

Эрмитовы матрицы

0.31) называются соответственно вещественной и мнимой частями матрицы А. Нормальные матрицы А могут быть охарактеризованы тем свойством, что соответствующие им матрицы (0.31) перестановочны.

В разделе 3.1 рассматривается класс нормальных матриц А, выделяемый условием где п — порядок А. Спектр такой матрицы А принадлежит объединению вещественной оси и, самое большее, к прямых, параллельных мнимой оси, т.е. вырожденной алгебраической кривой порядка не выше к + 1. Следовательно, метод МШЯЕЗ-К применйм к матрицам этого типа. Мы показываем, что для матриц со свойством (0.32) МШЯЕБ-К имеет следующую привлекательную особенность: начиная с некоторого шага, рекурсия длины 3(к + 1), обычно выполняемая этим методом, может быть заменена трехчленной рекурсией, после чего метод фактически совпадает с эрмитовым процессом Ланцоша. Достигаемое этим путем ускорение сходимости иллюстрируется несколькими примерами.

В разделе 3.2 рассматриваются системы с матрицами (0.29), для которых

В отличие от раздела 3.1, не требуется, чтобы А была нормальной матрицей, т.е. ее вещественная и мнимая части В и С не обязаны коммутировать. Мы показываем, что к системам этого типа применйм метод МЩИЕЗ-Ш. к = гапк С <С п ,

0.32) гапк С —1 .

0.33)

Эффективность метода иллюстрируется несколькими примерами решения ленточных систем; на этих примерах производительность MINRES-N2 .сопоставляется с производительностью библиотечной программы Matlab'a, реализующей GMRES.

В разделе 3.3 условие (0.33) заменяется на rank С = к > 1 . (0.34)

От матрицы А по-прежнему не требуется нормальности. Доказано, что матрица, удовлетворяющая этому условию, может быть приведена посредством унитарного подобия к блочно-трехдиагональному виду, где порядок каждого диагонального блока не превосходит 1+/с. Это означает, что систему (0.2) с такой матрицей А можно решать методом MINRES-N(1 + к), т.е. вариантом метода MINRES-N, первоначально предназначенным для нормальных матриц, которые удовлетворяют уравнению (0.25) для некоторого многочлена степени 1 + к. Обсуждаются примеры, в которых производительность MINRES-N(1 + к) для систем, подчиняющихся условию (0.34), сравнивалась с производительностью GMRES.

Изложение в третьей главе диссертации основано на наших работах [15, 16]. Классы матриц, рассматриваемые в этой главе, играют по отношению к обобщенным крыловским подпространствам роль, сходную с ролью обобщенных /с)-нормальных матриц в стандартной теории. В частности, эти классы включают в себя малоранговые возмущения (£, /с)-нормальных матриц.

Для одного и того же типа (£, /с)-нормальных матриц длина рекурсии в MINRES несколько больше, чем длина соответствующей рекурсии вида (0.14). Так, для унитарной матрицы U правая часть (0.14) содержит только три слагаемых, поскольку

5, t) = (г, к) = (о, 1).

Максимальная длина рекурсии для той же матрицы в MINRES-N2 равна 6. Однако, в целом, различия в длинах рекурсий не столь существенны, чтобы повлечь значительные различия в общем времени решения системы. Гораздо важнее различия в скорости сходимости, вызываемые различием аппроксимационных свойств стандартных и обобщенных крыловских подпространств. Но в этом отношении никаких однозначных выводов сделать нельзя: для одних типов матриц быстрее сходятся приближения, выбираемые из подпространств /Сш, для других — приближения, порождаемые обобщенными крыловскими подпространствами.

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

Отметим, что все численные эксперименты, обсуждаемые в главах 2 и 3, выполнялись на персональном компьютере Pentium IV с тактовой частотой 256 Мгц.

В разделе 4.2 четвертой главы рассматривается и решается следующая задача, мотивированная теоремой 0.4 и теоремами из главы 3: известно, что матрица А Е Мп(С) является одноранговой коррекцией эрмитовой матрицы. Иначе говоря, А есть матрица вида

A = H + R, (0.35) где = #*, rank R= 1 . (0.36)

Однако сами матрицы Н и R неизвестны. Спрашивается, как найти эти матрицы?

В разделе 4.3 рассматривается и решается аналогичная задача, в которой эрмитова матрица Н заменена унитарной матрицей U. В основе изложения — наша статья [17].

В разделе 4.4 мы решаем аналогичную задачу по отношению к разложению

А = X + Y , (0.37) где

X = Хт, rank Y = 1 . (0.38)

Это решение основывается на нашей публикации [18], а сама задача мотивируется желанием распространить метод типа сопряженных градиентов, построенный для комплексных симметричных матриц в [19], на одноранговые возмущения таких матриц. В заключительном разделе 4.5 обрисован путь, на котором можно получить желаемое обобщение. Вкратце, он состоит в замене унитарных подобий унитарными конгруэнциями или, в терминах обобщенного процесса Ланцоша, замене сопряженной матрицы А* транспонированной матрицей Ат.

1. Paige С.С., Saunders М.А. Solution of sparse indefinite systems of linear equations // S1.M J. Numer. Anal. 1975. V. 12. P. 617-629.

2. Past meetings // SIGNUM Newsletter. 1981. V. 16. N4. P. 7.

3. Воеводин В. В. Проблема несамосопряженного расширения метода сопряженных градиентов закрыта //Ж. вычисл. матем. матем. физ. 1983. Т. 23. N2. С. 477-479.

4. Воеводин В.В., Тыртышников Е.Е. Об обобщении методов сопряженных направлений // Числ. методы алгебры. М.: Изд-во МГУ, 1981, с. 3-9.

5. Faber V., Manteuffel Т. Necessary and sufficient conditions for the existence of a conjugate gradient method // SIAM J. Numer. Anal. 1984. V. 21. N2. P. 352-362.

6. Saad Y., Schultz M. H. GMRES: a generalized minimal residual algorithm for solving nonsymmetric linear systems // SIAM J. Sci. Statist. Comput. 1986. V. 7. P. 856-869.

7. Gragg W.B. Positive definite Toeplitz matrices, the Arnoldi process for isometric operators, and Gaussian quadrature on the unit circle // J. Comput. Appl. Math. 1993. V. 46. P. 183-198.

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

9. BarthT., Manteuffel T. Multiple recursion conjugate gradients algorithms. Part I: Sufficient conditions // SIAM J. Matrix Anal. Appl. 2000. V.21. N3. P. 768-796.

10. Barth Т., Manteuffel T. Conjugate gradient algorithms using multiple recursions. Linear and Nonlinear Conjugate Gradient-Related Methods, SIAM, Philadelphia, 1996, pp. 107-123.

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

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

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

14. Дана М., Икрамов Х.Д. Метод минимальных невязок для линейных многочленов от унитарных матриц // Ж. вычисл. матем. матем. физ. 2006. Т. 46. N6. С.

15. Дана М., Икрамов Х.Д. О решении систем линейных уравнений, матрицы которых являются малоранговыми возмущениями эрмитовых матриц // Вестн. МГУ. Серия "Вычисл. математика и кибернетика". 2005. N4. С. 15-22.

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

17. Дана М., Икрамов Х.Д. О малоранговых коррекциях эрмитовых и унитарных матриц // Ж. вычисл. матем. матем. физ. 2004. Т. 44. С. 1331— 1345.

18. Дана М., Икрамов Х.Д. Об одноранговых коррекциях комплексных симметричных матриц // Зап. научн. семин. ПОМИ. 2006. Т. С.

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

20. Деммель Дж. Вычислительная линейная алгебра. Теория и приложения. М.: Мир, 2001.

21. Greenbaum A. Iterative methods for solving linear systems. Philadelphia: SI AM, 1997.

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

23. McCullough S. A., Rodman L. Hereditary classes of operators and matrices // Amer. Math. Monthly. 1997. V. 104. N5. P. 415-430.