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

• Мансур Дана Хади
• кандидат физико-математических наук
• 2006

Оглавление диссертации кандидат физико-математических наук Мансур Дана Хади

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

Введение.

Глава 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 обрисован путь, на котором можно получить желаемое обобщение. Вкратце, он состоит в замене унитарных подобий унитарными конгруэнциями или, в терминах обобщенного процесса Ланцоша, замене сопряженной матрицы А* транспонированной матрицей Ат.

Список литературы диссертационного исследования кандидат физико-математических наук Мансур Дана Хади, 2006 год

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.