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

Пусть, А — заданная п х п-матрица. Фиксируем вектор х и рассмотрим степенную последовательность х, Ах, А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)½ •.

Основываясь на этих формулах, Ягеле и Райхель предложили эффективный алгоритм минимальных невязок для систем (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тп.

Эти соотношения схожи с (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пл². Эту величину нужно сопоставить с ~ у ненулевыми элементами хессенберговой матрицы.

Еще более важен следующий факт, также обнаруженный в [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.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. С. 871 880.

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.