Двухпараметрические попеременно-треугольные и двуциклические методы решения сильно несимметричных систем линейных алгебраических уравнений

Теория итерационных методов является интенсивно развивающейся областью численного анализа и занимает важное место в вычислительной математике и механике.

Для решения задач математической физики широко используются методы дискретизации исходных дифференциальных или интегральных уравнений, краевых и начальных условий, которые позволяют преобразовать исходную непрерывную задачу в дискретную, т. е. перейти из бесконечномерного в конечномерное пространство, как правило, достаточно большой размерности. Далее, в этом конечномерном пространстве задачу преобразуют в систему линейных алгебраических уравнений, которую затем надо решить на ЭВМ. Такая технология решения сложных научно-технических задач, описываемых системами интегро-дифференциальных уравнений, краевых и начальных условий была разработана в начале 60-тых годов А. А. Самарским и была названа им вычислительным экспериментом. В данной работе особое внимание уделяется предпоследнему этапу технологии вычислительного эксперимента — решению системы линейных алгебраических уравнений. В соответствии с мировой статистикой 80% задач, решаемых на ЭВМ — это задачи нахождения решения системы линейных алгебраических уравнений (СЛАУ). В работе рассматриваются итерационные методы решения этой задачи, т.к. речь идет о СЛАУ содержащих сотни тысяч неизвестных и уравнений, а прямые методы их решений при таком размере СЛАУ не эффективны. Несмотря на то, что теория итерационных методов в достаточной степени разработана для достаточно большого класса матриц, остаются проблемы по созданию новых эффективных итерационных методов решения СЛАУ для матриц, обладающих достаточно специфическими свойствами. Одним из таких классов матриц являются сильно несимметричные матрицы, которые получаются, например, при центрально-разностной аппроксимации уравнения конвекции-диффузии с малым параметром при старшей производной.

В связи с этим актуальность работы обусловлена потребностью в эффективных методах решения такого класса СЛАУ.

Построение «быстрых» итерационных методов решения сильно несимметричных систем в данной работе основываются на включении в обращаемый оператор итерационного метода треугольной части лишь кососимметрической составляющей исходной матрицы.

Целью данной работы является разработка эффективных численных методов решения сильно несимметричных систем линейных алгебраических уравнений. В работе предложены двухпараметрические попеременно-треугольный и дву-циклический методы для решения СЛАУ из рассматриваемого класса.

В соответствии с этими целями решен ряд задач:

• разработаны, теоретически обоснованы и численно проверены двухпараметрические попеременно-треугольный (ПТКМ) и двуциклический (ДТКМ) итерационные методы решения СЛАУ с сильно несимметричной матрицей;

• рассмотрены вопросы ускорения двухпараметрических ПТКМ и ДТКМ;

• предложено использование параметрических и безпараметрических ПТКМ и ДТКМ в качестве переобуславливателей для методов вариационного типа.

Научная новизна работы определяется полученными теоретическими результатами исследования:

• доказательством сходимости предложенных новых классов двухпараметрических попеременно — треугольных и двуциклических кососимметрических методов решения СЛАУ с сильно несимметричными матрицами;

• определением (в частных случаях) оптимальных параметров двухпараметрических ПТКМ и ДТКМ;

• исследованием возможности использования этих методов в качестве переобуславливателей для методов вариационного типа.

Разработанные итерационные методы вносят вклад в развитие численных методов решения систем линейных алгебраических уравнений специального вида. Вместе с тем, с помощью разработанных методов можно эффективно решать задачи типа «пограничного слоя» при конвективно-диффузионном переносе с преобладанием конвекции.

К защите представлены следующие результаты диссертационной работы:

1. предложены двухпараметрические итерационные методы решения сильно несимметричных систем: попеременно-треугольный (ПТКМ) и двуцик-лический (ДТКМ) кососимметричные методы;

2. получены достаточные условия сходимости двухпараметрических ПТКМ и ДТКМ;

3. для частных случаев проведены исследования по нахождению оптимального итерационного параметра для двухпараметрических ДТКМ и ПТКМ;

4. предложен метод ускорения сходимости двухпараметрических ДТКМ и ПТКМ за счет специального выбора компонент обращаемого оператора;

5. показана эффективность использования этих методов в качестве пере-обуславливателя для методов вариационного типа.

Основные результаты диссертации докладывались на IX и X Всероссийских школах-семинарах молодых ученых «Современные проблемы математического моделирования» (п. Абрау-Дюрсо, 2001 г., 2003 г.) — на 5-ой Всероссийской конференции «Сеточные методы для краевых задач и приложения» (г. Казань, 2004 г.) — на международной конференции «Математическое моделирование и вычислительный эксперимент в механике и физике» (г. Ростов-на-Дону, 2001 г.) — на международной конференции IMMC-2002 «Итерационные методы и матричные вычисления» (г. Ростов-на-Дону, 2002 г.) — IX и X Всероссийские Совещания по проблемам построения сеток для решения задач математической физики (п. Абрау-Дюрсо, 2002 г., 2004 г.), Всероссийской научно-технической конференции «Параллельные вычисления в задачах математической физики» (Ростов-на-Дону, 2004). Annual Scientific Congerence GAMM 2003; Session 22, 2003, Abano TermePaduaConference computational linear algebra with applications, MILOVI, 2002; International Conference on Computational Mathematics, Novosibirsk, 2002.

По теме диссертации опубликовано 12 печатных работ, из них 4 статьи в российских и зарубежных реферируемых журналах, 6 статей в сборниках трудов и 2 в тезисах докладов российских и международных конференций. В совместных работах автор принимал участие на всех этапах исследования.

Во введении обоснована актуальность темы диссертации, определенны цели и задачи исследования, приведена структура диссертации, а также сформулированы основные положения, выносимые на защиту.

В первой главе содержится обзор известных сведений по тематике работы. Рассмотрена общие формулировки теории сходимости итерационных методов решения систем линейных алгебраических уравнений (СЛАУ).

Ay = f. (1).

Большинство итерационных методов, которые применяются для решения СЛАУ, могут быть объединены общей канонической формулой v" +1 — у" .

В/-+ (2) где Вп — операторы метода, А — исходная матрица системы, тп> 0 — последовательность итерационных параметрову0 — начальное приближение, / - правая часть (1), f, у0 е Н, Н — конечномерное гильбертово пространство, у11 — решение на «-ой итерации, п — номер итерации.

Итерационный метод (2) можно записать в эквивалентном виде z" +I =z" -rn5−1r", где г" = Ау" - f — вектор невязки на п-ой итерации, a z" =у" -увектор погрешности (ошибки) этого метода, у — точное решение системы (1).

В разделе 1.1. и его подразделах изложены некоторые сведения из теории матриц и теории итерационных методов, а именно: типы матриц и их основные свойства, теоремы о локализации спектра матриц, лемма Келлога и ее обобщение, а также методы ускорения сходимости.

В разделе 1.2. рассматриваются классические итерационные методы: Якоби, Гаусса-Зейделя, последовательной верхней релаксации (SOR), симметричной и несимметричной последовательной верхней релаксации (SSOR и USSOR), треугольные, попеременно-треугольные и методы неполного разложения.

Там же даны определения^{-циклического,} стационарного и треугольного (ТМ) (попеременно-треугольным (ПТМ)) итерационных методов.

В разделе 1.3. рассматриваются различные итерационные методы решения сильно несимметричных СЛАУ1: вариационные методы, методы эрмитова и ко-соэрмитова разложения и кососимметрические методы (КМ) — треугольные (ТКМ), попеременно-треугольные (ПТКМ) и двуцикличиские (ДТКМ), которые являются основой нашего исследования.

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

А^Ао+А], А0= (А + АТ)/2=А0Т, А1=(А-Ат)/2 = -А]т Причем для кососимметричной составляющей справедливо следующее разложение.

А^Кц+Кь где К1 и Ку строго нижняя и верхняя треугольные части матрицы А], причем.

Ки= -К.1 .

Для исследования итерационного метода (2) рассмотрим однородное уравнение для векторов погрешностей.

В2м~*к+А2к= 0,? = 0,1,2,.- г0=у0-у, т или в разрешенной относительно форме гк+х =, где в = В~В-тА) (3) называется оператором перехода итерационного метода (2).

Если оператор перехода С = зависит от итерационного параметра г, то метод (2) будем считать однопараметрическим итерационным методом, если же <7 = О (г, со) зависит не только от г, но и от некоторого второго параметра со, то — двухпараметрическгш. Оператор, А называется сильно несимметричным, если в какой либо норме.

Л, Л.

Для получения условий сходимости итерационного метода (2) надо исследовать его оператор перехода (3) и оценить его спектр р{р) = тах^ (С)| < 1 или его норму ¡-|Ст| < 1.

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

В = (Вс+2тКь) или В = (Вс+2тКи), где ВС=ВТС.

Теоретическое и численное исследование этого класса методов, выполненное за последние годы, позволило построить сходящиеся методы для СЛАУ с диссипативными сильно несимметричными матрицами. Были получены однопа-раметрические треугольные (ТКМ), попеременно треугольные (ПТКМ) и дву-циклические (ДТКМ) кососимметрические итерационные методы решения для сильно несимметричных диссипативных2 матриц.

Отметим, что основное свойство этого класса методов состоит в том, что ко-сосимметричная составляющая оператора метода пропорциональна кососиммет-ричной составляющей оператора системы, причем:

Вх = тАх.

Исследования были проведены в энергетической норме + В*^> 0.

Оператор перехода ТКМ в этой норме имеет вид.

0(т) = {Е + тРх)~Е + тР,-), где р0=в-^в-^2=р- > о, рх=в-х'2 ах12 = -р- • 2.

Оператор, А называется диссипативиым, если для любого вектора X Ф 0 его симметричная часть положительно определена (Ах, х) = > 0.

Т.к. норма оператора (Е + тРх) <1, а оператор Е + тР0 симметричен, то исследование оператора Е + тР0 дало достаточное условие сходимости ТКМ (ПТКМ, ДТКМ) в виде В0 > 0,5 тА0.

Во второй главе представлены основные теоретические и численные результаты.

Исследовано обобщение однопараметрических ПТКМ и ДТКМ, введением в оператор метода В параметра со, отличного, в общем случае, от параметра метода т. Исследования таких двухпараметрических ПТКМ (т, со) и ДТКМ (т, со) проводилось по методике, отличной от разработанной ранее для однопараметрических методов.

Энергетический подход позволил доказать достаточные условия сходимости в норме = В0- 0,5а>А0 ^(г,^)^ <1|, отличной от рассмотренной ранее. Вначале достаточные условия сходимости методов даны, без каких либо ограничений на свойства невырожденного оператора системы А, а затем в следствиях они приведены для случая диссипативного оператора системы (1).

В разделе 11.1. и 11.2 и их подразделах рассмотрен энергетический подход исследования ДТКМ (т, со) и ПТКМ (т, со), доказаны теоремы сходимости и следствия к ним. В частных случаях доказаны теоремы о нахождении оптимального параметра методов.

Двухпараметрический ДТКМ имеет вид уИ+1 — V" *1'2.

Diag[BL) + соКь) —-?-+Ауп*т =/,.

Т (4) л+½ п V >

Diag [Ви) + соКи^——-——+Ау" = / где В, =(Diag (BL) + й) KL) — оператор первого цикла, Ви = (Diag (Ви) + соКи)~ оператор второго цикла. Оператор перехода метода (4) имеет следующий вид.

С = в-1 (ВьтА)В~- (ВитА) = ед,.

Проделывая простые преобразования с оператором й, приводим его к виду.

GL = z J.

Nlo Vlrr^ = Blo ~тл =.

Требование положительной определенности оператора N^>0, позволяет получить оператор перехода в виде.

Gl = Nil Gl Nil, где.

4−1.

E±PL.

CO.

X-2 h.

— i p AN'1 rL LO LO т. е. исследование сходимости метода проводится в энергетической норме Аналогичные преобразования производятся и для оператора Си. Тогда для сходимости метода достаточно, чтобы fJ’iQ ДГ2 IyL0 «LiViO.

N~* G N* lyU0 и lyU0.

1.

А это в свою очередь означает, что достаточно потребовать Двухпараметрический ПТКМ имеет вид.

Л)П+1 п.

Вс+аК^Вс+аК,)*—^-Ау" = / .

5).

Оператор перехода метода (5) имеет следующий вид в = В~х (В-гА), (6) где.

В = {ВС+ аКь) В~1 (Вс +(оКи). Сделав достаточно простые преобразования в (6), получаем.

Далее потребовав положительную определенность оператора N?>0, получаем оператор перехода в виде 0 = где д = (Е + соР)~,(Е-(т-(о)Р), Р = ^*А¹¹.

Т.к. оператор С подобен оператору С, то исследование сходимости метода будем проводить в энергетической норме, т. е. для сходимости метода достаточно потребовать ЦбЦ =.

1.

Доказаны достаточное условие сходимости двухпараметрических ДТКМ и ПТКМ. В приведенных следствиях из этих теорем эти достаточные условия упрощены для класса диссипативных матриц.

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

В разделе И.З. рассмотрены возможности ускорения сходимости предложенных методов, на примере двухпараметрического ДТКМ.

Ускорение треугольных методов может быть достигнуто не только за счет наличия параметров и их оптимального выбора, но и за счет специального построения операторов Вс, Вь и Ви, входящих в структуру обращаемого оператора методов ПТКМ и ДТКМ. Такой выбор оказывает существенное влияние на скорость сходимости метода. Очевидно, что этот оператор должен быть диагональным, иначе его обращение представляет достаточно трудоемкую вычислительную задачу.

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

Хо = Diag (Вь) + 0,5со (К1+К1)-0,5соА^ > О = (Ви)-0,5а>[К1+ К{)-0,5й)Ло>0.

Так как матрицы Ы10 и Ыио симметричны, их собственные числа действительны, то по теореме Гершгорина, для положительной определенности операторов и Ыио достаточно выполнения следующих условий:

Ко1>0,.

М/о}й>0, причем хотя бы для одной строки в каждой системе неравенство должно быть строгим.

Тогда, очевидно, что если в качестве диагоналей операторов метода взять следующие выражения: где Д, ={4,1 = К10 + Ки0, то они обеспечат выполнения условий положительной определенности операторов Ы10 и Ыио, тем самым дадут сходимость двухпараметрического ДТКМ с диссипативным исходным оператором, сохраняя при этом в операторах Вь и Ви информацию об изменениях в строках и столбцах исходной матрицы. Кроме того, построение диагоналей матриц Вь и Ви не требует существенных вычислительных затрат, что не снижает эффективность метода.

В разделе 11.4. приведены численные результаты тестирования рассмотренных методов и их сравнения с классическими методами.

Модельной задачей, на которой проведено тестирование методов, является стационарное двумерное уравнение конвекции-диффузии, записанное в симметричное форме, в единичном квадрате, с граничными условиями первого рода.

Правая часть f и краевые условия выбирались таким образом, чтобы аналитическим решением задачи была гладкая функция и{х, у)=ехувт{71х)ът{71у).

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

ДС/ + -Ре /(х, у), и дП~ Олась центральными разностями, получается система линейных алгебраических уравнений с диссипативной пятидиагональной матрицей А.

Поле скоростей подобранно таким образом, чтобы удовлетворить условие несжимаемости среды, т. е. Div (V)=0, V=fv/, v2}.

Численное исследование на модельной задачи проводилось для кососиммет-рических методов, разработанных ранее, их модификаций, SSOR и двухпарамет-рических ПТКМ, ДТКМ. Все эти методы имеют похожую структуру и требуют одинакового числа арифметических операций на каждой итерации. Таким образом, для оценки эффективности методов достаточно сравнивать лишь число итераций. Все расчеты выполнялись на одной и той же ПЭВМ.

В главе III рассмотрены вариационные методы BiCG и GMRES (m), которые использовались для решения модельной задачи как самостоятельно, так и с пере-обуславливанием, где в качестве переобуславливателей использовались двухпа-раметрические ПТКМ и ДТКМ. Для оценки эффективности такого подхода, полученные численные результаты сравнивались с аналогичными результатами для «классического» переобуславливателя, которым является SSOR. Для улучшения сходимости вариационных методов предлагалась технология левого переобу-славливания.

По результатам данных тестов можно заметить, что все рассматриваемые операторы являться хорошими переобуславливателями для метода GMRES (IO), но достаточно слабыми переобуславливателями для метода BiCG.

Таким образом, использование разработанного класса двуциклических и попеременно-треугольных методов в качестве переобуславливателей методов вариационного типа наиболее эффективно для задач конвекции-диффузии с преобладающей конвекцией и сильно меняющимся полем скоростей, соответствующей модельной задаче 4.

I. ИТЕРАЦИОННЫЕ МЕТОДЫ РЕШЕНИЯ СЛАУ.

1. Андерсон Д., Таннехил Дж., Плетчер Р. Вычислительная гидромеханика и теплообмен: В 2-х т. М: Мир, 1990.

2. Булеев Н. И. Пространственная модель турбулентного обмена. М.: Наука, 1989.

3. Вабищевич П. Н. Итерационные методы решения задач конвекции-диффузии.// Труды Международной летней школы молодых ученых «Итерационные методы и матричные вычисления». Ростов-на-Дону: Изд-во РГУ, 2002, стр. 328−367.

4. Воеводин В. В. Линейная алгебра. М: Наука, 1980.

5. Воеводин В. В., Кузнецов В. А. Матрицы и вычисления. М: Наука, 1984.

6. Г. И. Шишкин Г. И. Сеточная аппроксимация сингулярно возмущенных уравнений с конвективными членами в случае смешанных краевых условий.// Дифференциальные уравнения, 1996, 32 (5), 689−701.

7. Гантмахер Ф. Р. Теория матриц, М: Наука, 1966.

8. Голуб Дж., Ван Лоун Ч. Матричные вычисления, Москва: Мир, 1999.

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

10. Еремин А. Ю., Капорин И. Е. Реализация явных чебышевских методов при решении задач большой размерности. в кн. Многопроцессорные вычислительные структуры, Таганрог, ТРТИ, 1985, вып.7, стр. 43−46.

11. Капорин И. Е. О предобуславливании и распараллеливании метода сопряженных градиентов. в кн. Ортега Дж. «Введение в параллельные и векторные методы решения линейных систем». Москва: Мир, 1991, стр. 180−190.

12. Крукиер Л. А, Чикина Л. Г. Кососимметрические итерационные методы решения стационарных задач конвекции-диффузии.// Изв. ВУЗов, Матем., 2000. № 11. с.62−76.

13. Крукиер Л. А. Достаточное условие сходимости треугольного итерационного метода с несамосопряженным исходным оператором.// Изв. СКНЦ ВИТ. Ест. Науки, 1989, № 4, стр. 52−54.

14. Крукиер Л. А. Кососимметричные итерационные методы решения стационарной задачи конвекции-диффузии с малым параметром при старшей производной.//Изв. ВУЗов. Математика, 1997, № 4, стр.77−85.

15. Крукиер Л. А. Мартынова Т.С. О влиянии формы записи уравнения конвек-ции-дифузии на сходимость метода верхней релаксации.// ЖВМиМФ, т. 39, № 11, 1999, стр. 1821−1827.

16. Крукиер Л. А. Неявные разностные схемы и итерационный метод их решения для одного класс систем квазилинейных уравнений.// Изв. Вузов. Математика, 1979, № 7, стр. 41−52.

17. Крукиер Л. А. Математическое моделирование гидродинамики Азовского моря при реализации проектов реконструкции его экосистемы// Матем. мо-дел. 1991. — Т.З. -№ 9. — С.3−20.

18. Крукиер Л. А. Решение сильно несимметричных систем линейных алгебраических уравнений итерационным методом, основанным на кососимметрич-ной части исходной положительной матрицы.// Математическое моделирование, том13, № 3, 2001, стр. 49−56.

19. Крукиер Л. А., Бочев М. А. Об итерационном решении сильно несимметричных систем линейных алгебраических уравнений.// ЖВМ и МФ, т. 37, № 11, 1997, стр. 1283−1293.

20. Крукиер Л. А., Чикина Л. Г. Двуциклический треугольный кососимметриче-ский итерационный метод решения сильно несимметричных систем.// Известия высших учебных заведений. Математика, № 5, 2001, стр. 36−42.

21. Крукиер Б. Л. Ускорение метода ДДТКМ и его численное исследование, Сборник трудов X Всероссийской школы-семинара «Современные проблемы математического моделирования», Изд. РГУ, Ростов-на-Дону, 2004, стр. 127−133.

22. Лебедев В. И. Финогенов С.А. О порядке выбора итерационных параметров в чебышевском циклическом итерационном методе.// ЖВМ и МФ, 1971, т. 11, № 2.

23. Лойцянский Л. Г. Механика жидкости и газа. М: Наука, 1970.

24. Маркус М., Минк X. Обзор по теории матриц и матричным неравенствам. М.: Наука, 1972.

25. Марчук Г. И. Методы вычислительной математики. Новосибирск: Наука, 1973.

26. Ортега Дж.

Введение

в параллельные и векторные методы решения линейных систем. Москва: Мир, 1991.

27. Роуч П. Вычислительная гидродинамика. М.: Мир, 1980.

28. Самарский A.A. О регуляризации разностных схем //ЖВМ и МФ, -1967. -Т.7. -№ 1. С.62−93.

29. Самарский A.A.

Введение

в теорию разностных схем, М: Наука, 1971.

30. Самарский A.A.

Введение

в численные методы. М: Наука, 1987.

31. Самарский A.A. Николаев Е. С. Методы решения сеточных уравнений М: Наука, 1978.

32. Самарский A.A. Теория разностных схем М: Наука, 1977.

33. Самарский A.A., Вабищевич П. Н. Численные методы решения задач конвекции-диффузии. Изд. УРСС, Москва, 1998.

34. Самарский A.A., Вабищевич П. Н., Матус П. П. Разностные схемы с операторными множителями, Минск, 1998.

35. Самарский A.A., Гулин A.B. Численные методы. М: Наука, 1989.

36. Тартышников Е. Е. Краткий курс численного анализа, Москва: ВИНИТИ, 1994.

37. Фадеев Д. К., Фадеева В. Н. Вычислительные методы линейной алгебры. Спб: Лань, 2002, 736 стр.

38. Хейгеман Л. Янг Д. Прикладные итерационные методы, Москва: Мир, 1986.

39. Хорн Р. Джонсон Ч. Матричный анализ. Москва: Мир, 1989.

40. Чикина Л. Г. Об одном методе решения уравнения конвекции-диффузии с преобладающей конвекцией.// Математическое моделирование, 1997, т. 9, № 2, стр. 20−25.

41. Чикина Л. Г., Крукиер Б. Л. Двухпараметрический двуциклический итерационный метод решения сильно несимметричных систем линейных алгебраических уравнений. Вычислительные технологии, Новосибирск, Том 9, № 5, 2004, стр. 102−113.

42. Arnoldi W.E. The principle of minimized iteration in the solution of the matrix eigenproblem.// Quart. Appl. Math., 1951, № 9, p. 17−29.

43. Axelsson O. A generalized SSOR method.// BIT, 1972, 12, p. 443−467.

44. Axelsson O. Iterative solution Methods. Cambridge University Press, Cambridge, 1994.

45. Axelsson O., Vasilevski P. S. A black box generalized conjugate gradient solver with inner iterations and variable-step preconditioning.// SIAM J. Matrix Analysis and Applications, 1991, № 12, p.625−644.

46. Bai Z.Z., Golub G., Ng M. Hermitian and Skew-Hermitian splitting methods for non-Hermitian positive definite systems, SIAM J. Matrix Anal.Appl., 24, 2003, pp.603−626.

47. Barrett R., Berry M., Chan T.F., Demmel J., Donato J., Dongarra J., Eijkhout V., Pozo R., Romine C., and Van der Vorst. Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods, 2nd Edition. SIAM, Philadelphia, PA, 1994.

48. Buleev N.I. A numerical method for solution of two-dimensional and threedimensional equations of diffusion.// Math. Sb., 1960, № 51, p. 227−238.

49. Chan T.F., Galloloulos E., Simoncini V., Szeto Т., Tong C.H. A quasi-minimal residual variant of the BiCGSTAB algorithm for nonsymmetric systems.// SIAM J. Sci. Statist. Comput., 1994, № 15, p. 338−347.

50. Chikina L.G., Krukier B.L. Solution of linear equation systems with a dominant skew-symmetric part using the product triangular iterative method. Сотр. Methods in Appl. Math, V. 3, № 4, 2003, pp.647−650.

51. D’Sylva E., Miles G.A. The SSOR iteration scheme for equations with cforder-ings.// Computer J., 1963, № 6, p.271−273.

52. DeLong M. SOR as preconditioner, Doctor of Philosophy (Computer Science) Dissertation, University of Virginia, 1997.

53. Dongarra Jack., J. Duff Iain., S. Sorensen Danny C., Van der Vorst H. Numerical Linear Algebra for high-performance computers. SIAM, Philadelphia, 1998.

54. Elman H.C. Relaxed and stabilized incomplete factorizations for nonselfadjoint linear systems, BIT, 29(4), 1989, p.890−915.

55. Elman H.C. A stability analysis of incomplete LU factorization.// Math. Comp., 1986, № 47, p. 191−217.

56. Fisher B., Ramage A., Silvester D.J., Wathen A.J. Towards parameter-free streamline upwinding for advection-diffusion problems, Strathclyde Mathematics Research Report, № 37 (1996).

57. Fletcher R. Conjugate gradient methods for indefinite systems.// G.A. Watson (Ed.), Proceedings of the Dundee Biennal Conference on Numerical analysis, Springer, New York, 1975, p.73−89.

58. Frankel S.P. Convergence Rates of Iterative Treatment of Partial Differential equation, //Math. Tables Aids Comp., 1950, v.4, p.66−75.

59. Freund R.W., Nachtigal N.M. An implementation of the look-ahead Lanczos algorithm for non-Hermitian matrices.// Technical Report 90.46, Part2, RIACS, NASA Ames Center, 1990.

60. Golub G.H., Van der Vorst H. A. Closer to the solution: Iterative linear solvers.// in I.S. Duff and G.A.Watson (eds), The State of the Art in Numerical Analysis, Clarendon Press, Oxford, 1997, p. 63−92.

61. Golub G.H., Varga R.S. Chebychev semi-iterative methods, successive overrelaxation iterative methods and second order Richardson iterative methods.// Part I, Numer. Math., 1961, V.3, p. 147−156.

62. Golub G.H., Varga R.S. Chebychev semi-iterative methods, successive overrelaxation iterative methods and second order Richardson iterative methods.// Part II, Numer. Math, 1961, V.3, p. 157−166.

63. Golub Gene, Van Loan Ch. Matrix Computations, Oxford, North Oxford Academic Publishing, 1983.

64. Golub G, Vanderstraeten D. On the preconditioning of matrices with a dominant skew-symmetric component, Numer. Algorithms, 25, 2000, pp223−239.

65. Greenbaum A. Iterative methods for solving Linear Systems. SIAM, Philadelphia, PA, 1997.

66. Grote M, Huckle T. Parallel preconditioning with sparse approximate inverses.// SIAM J. Sci. Comput., 1997, № 18, p. 838−853.

67. Hadjidimos A. A survey of the iterative methods for the solution of linear systems by extrapolation, relaxation and other techniques.// J. Comput. Appl. Maths, 1987, № 20, p. 37−51.

68. Hadjidimos A. Accelerated Overrelaxation method.// Math. Comp, 1978, № 32, p. 149−157.

69. Hadjidimos A, Psirmani A, Yeyios A.K. On the convergence of the modified accelerated overrelaxation method (MAOR).// Applied Numerical Math, 1992, № 10, p. 115−127.

70. Hadjidimos A, Yeyios A.K. Symmetric accelerated overrelaxation method (SAOR).// Math. Comput. Simulation, 1982, № 24, p. 72−76.

71. Kaporin. I.E. Explicitly preconditioned conjugate gradient method for the solution of unsymmetric linear systems, Int.J.Comp. Math., 40, 1992, p. 169−187.

72. Kaporin. I.E. High quality preconditioning of a general symmetric positive matrix based on its UTU + UTR + RTU-decomposition.- Numer. Linear Algebra Appls., N 1, 1999.

73. Kaporin I.E., A practical algorithm for faster matrix multiplication, Numerical Linear Algebra Appl., 1999, v.6, 687−700.

74. Kaporin I.E. New convergence results and preconditioning strategies for the conjugate gradient method, Numer. Linear Algebra with Appls., v. l, N 2, 1994, pp. 179−210.

75. Karamzin Yu. N. Zakharova I.G. On new additive difference method for parabolic equations, Math. Mod. Meth. Appl. Science., 6 (1996), pp. 353−363.

76. Kototilina L. Yu., Yeremin A. Yu. Block SSOR preconditionings for high order 3D FE systems.// BIT., 1989, v. 29, № 4, p. 805−823.

77. Kototilina L. Yu., Yeremin A. Yu. Factorized sparse approximate inverse preconditionings.// SIAM J. Matrix Analysis and Applications, 1993, № 14, p. 45−58.

78. Krukier L.A., Chikina L.G., Belokon T.V. Triangular skew-symmetric iterative solvers for strongly nonsymmetric positive real linear system of equations.// Applied Numerical Mathematics, 2002, № 41, p. 89−105.

79. Krukier L.A., Convergence acceleration of triangular iterative methods based on the skew-symmetric part of the matrix.// Applied Numer. Math., 1999, v.30, N3−4, p.281−290.

80. Krukier L.A., Lapshina O., Krukier B.L. Special preconditioners for solution of transport-dominated convection-diffusion problem, PAMM, Proceedings Appl. Math.&Mech., Wiley InterScience publisher, 2003, v.3, № 1, 549 550.

81. Krukier L.A., Lapshina O., Krukier B.L. Special preconditioners for solution of transport-dominated convection-diffusion problems Annual Scientific Conger-ence GAMM 2003; Session 22, 2003, pp.234, Book of Abstracts. Abano TermePadua.

82. Kuznetsov Y.A. Matrix Iterative Methods in subspace.// Proceedings of the International Congress of Mathematicians, Warszawa, August 16−24, 1983, North Holland, Amsterdam.

83. Lanczos C. Chebyshev polynomials in the solution of large-scale linear systems.// Toronto Symposium on Computing Techniques, 1952, p. 124−133.

84. Lynn M.S. On the equivalence of SOR, SSOR and USOR as applied to aordered systems of linear equations.// Computer J., 1964, № 7, p.72−75.

85. Manteuffel T.A. Adaptive procedure for estimating parameters for the nonsym-metric Tchebychev iteration.//Numerical Math., 1978, v. 31, p 183−208.

86. Manteuffel T.A. An incomplete factorization technique for positive definite linear systems.// Math Comp., 1980, V. 34, p. 473−497.

87. Manteuffel T.A. The Tchebychev iteration for nonsymmetric linear systems.// Numerical Math., 1977, v. 28, p. 307−327.

88. McDowell Variable Successive Overrelaxation.// Report № 244, Dept. Computer Sciences, University of Illinois, Utbana.

89. Meijerink J.A., Van Der Vorst H.A. An iterative solution method for linear systems of which the coefficient matrix is symmetric M-matrix.// Math. Comp., 1977, № 31(137), p. 148−162.

90. Meurant G. Computer solution for large linear systems. Elsevier Science B.V., 1999.

91. Morton K.W. Numerical solution of convection-diffusion problems. Chap-man&Hall, 1996.

92. Nachtigal N. A look-ahead variant of the Lanczos algorithm and its application in quasi-minimal residual method for non-Hermitian linear systems, Ph. D. Dissertation, Massachusetts Institute of Technology, Cambridge MA, 1991.

93. Paige C.C., Saunders M.A. Solution of sparse indefinite systems of linear equations.// SIAM J. Numerical Anal., 1975, № 12, p. 617−629.

94. Parlett B.N., Taylor D.R., Lin Z.A. A look-ahead Lanczos algorithm for unsym-metric matrices.// Math. Comp., 1985, № 44, p. 105−124.

95. Raithby G.L., Skew upstream differencing schemes for problems involving fluid flow // Comput neths. Appl. Mech. Engrg., 1976. V.9. — P. 153−164.

96. Russell D.B. On obtaining Solutions to Navier-Stokes equations with automatic digital computers.// Aeronautical research council report R&M 3331 Engineering Laboratory, Oxford, 1963.

97. Saad Y. A flexible inner-outer preconditioned GMRES algorithm.// SIAM J. Scientific Computing., 1993, № 14, p. 461−469.

98. Saad Y. Iterative methods for Sparse Linear Systems. PWS Publishing Company, 1995.

99. Saad Y., Schultz M.H. GMRES: a generalized minimal residual algorithm for solving nonsymmetric linear systems.// SIAM J. Scientific and Statistical Computing., 1986, p. 856−869.

100. Saad Y., Van der Vorst H. A. Iterative solution of linear systems in the 20th century.// J. of Computanional and Applied Mathemetics, Elsevier Science, 2000, № 123, p. 1−33.

101. Sonnoveld P. CGS: a fast Lanzos-type solver for nonsymmetric linear systems.// SIAM J. Sci. Statist. Comput., 1989, № 10, p. 36−52.

102. Sturler E. De Truncation strategies for optimal Krylov subspace methods.// SIAM J. Numerical Anal., 1999, v. 36, № 3. p. 864−889.

103. Taussky O. Positive-definite matrices and their role in the study of the characteristic roots of general matrices.//Adv. Math., 1968, v.2, p. 175−186.

104. Taylor P.J. A generalization of Systematic Relaxation methods for consistently ordered matrices.// Num. Math., 1969, № 13, p. 377−395.

105. Van der Vorst H.A. Bi-CGSTAB: a fast and smoothly converging variant if Bi-CG for the solution of non-symmetric linear systems.// SIAM J. Sei. Statist. Comput., 1992, № 3, p. 631−644.

106. Van der Vorst H.A. Krylov Subspace Iteration.// Computing in Science and Engineering, Vol. 2(1) January/February 2000, p. 32−37.

107. Van Der Vorst H.A. Iterative solution methods for certain sparse linear systems with a non-symmetric matrix arising from PDE problems.// J. Comput. Phys., 1981, № 44, p. 1−19.

108. Van der Vorst, H.A. Vuik C. GMRESR: a family of nested GMRES methods.// Numerical linear Algebra with Applications, 1994, № 1, p. 369−386.

109. Varga R.S. Factorization and normalized iterative methods.// R.E. Langer (Ed), Boundary Problems in Differential equation, University of Wisconsin Press, Madison, 1960, p.121−142.

110. Varga R.S. Matrix iterative analysis, Aprentice-Hall, Englewood Cliffs, NJ, 1962.

111. Varga R.S., Eiermann M., Niethammer W. Acceleration of Relaxation Methods for Non-Hermitian linear systems.// SIAM J. Matrix Anal. Appl., 1991, № 13, p. 979−991.

112. Wang C-L, Bai Z-Z. Sufficient conditions for the convergent splittings of non-Hermitian positive definite matrices, Linear Alg. Appl. 330, 2001, 215−218.

113. Wang C-L, Bai Z-Z Skew-Hermitian triangular splitting iteration methods for non-Hermitian positive definite linear systems of strong skew-Hermitian parts, BIT Numerical Mathematics, 44, 2004, pp.363−386.

114. Weiss R. Parameter-Free linear solvers, Berlin: Akademie Verlag, 1996.

115. Woznicki Z.I. Matrix splitting principles.// International Journal of mathematics and mathematical sciences, № 28(5), 2001, p.251−284.

116. Woznicki Z.I. Nonnegative splitting theory.// Japan Journal of industrial and applied mathematics, 1994, V. 11, № 2, p. 289−342.

117. Woznicki Z.I. The sigma-SOR algorithm and the optimal strategy for the illustration of the SOR iterative method.// Math. Comp., 62, 1994, p. 619−644.

118. Young D.M. Iterative methods for solving partial differential equations of elliptic type, Doctoral Thesis, Harvard University, Cambridge, MA, 1950.

119. Young D.M. Iterative solution of large linear iterative systems.// Academic Press, New York, 1971.

120. Young D.M. On accelerated SSOR method for solving large linear systems.// Advances in Mathematic, V.23, 1977, p.215−271.

121. Zhang J. Preconditioned iterative methods and finite difference schemes for con-vection-diffiision.// Applied mathematics and computation, 109(2000) p. 11−30.