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

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

Пичугина Ольга Александровна

ИСПОЛЬЗОВАНИЕ ЭФФЕКТИВНЫХ ПЕРЕОБУСЛАВЛИВАТЕЛЕЙ ДЛЯ ЧИСЛЕННОЙ РЕАЛИЗАЦИИ МАТЕМАТИЧЕСКИХ МОДЕЛЕЙ КОНВЕКТИВНО-ДИФФУЗИОННОГО ПЕРЕНОСА.

05.13.18 — Математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

г. Ростов-на-Дону 2006г.

Работа выполнена на кафедре информатики и вычислительного эксперимента механико-математического факультета Ростовского Государственного Университета

Научный руководитель:

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

Ведущая организация:

доктор физико-математических наук, профессор КРУКИЕР Лев Абрамович

доктор физико-математических наук, доцент ЕРЕМЕЕВ Виктор Анатольевич

кандидат физико-математических наук, доцент СУРКОВ Федор Алексеевич

Институт математического моделирования РАН, г.Москва

Защита состоится " /2" оК7>>ЗрЯ 2006г. в /У часов на заседании диссертационного совета К.212.208.04 по физико-математическим и техническим наукам в Ростовском Государственном Университете по адресу: 344090, Ростов-на-Дону, пр.Стачки 200/1, корпус 2, ЮГИНФО РГУ, к.206.

С диссертацией можно ознакомиться в научной библиотеке РГУ по адресу: г.Ростов-на-Дону, ул.Пушкинская, 148.

Автореферат разослан СХА&2006г.

Ученый секретарь диссертационного Совета,

----------— х-----..вмиошипа^ну (^/С" * ^ Муоатова Г.В.

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

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

Несмотря на то, что сейчас существует огромное множество итерационных методов, позволяющих эффективно решать даже те СЛАУ, которые раньше считались "тяжелыми" для решения, проблемы в этой области еще остались. Решение СЛАУ с сильно несимметричными матрицами - одна из таких проблем. Для этого класса матриц большинство классических итерационных методик мало эффективны. Методы либо вообще не работают, либо обладают очень медленной скоростью сходимости. Поэтому создание и исследование новых итерационных методов решения определенных классов задач остается актуальной проблемой для математического моделирования и численных методов.

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

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

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

• разработан новый класс эффективных переобуславливателей методов подпространства Крылова для решения сильно несимметричных систем линейных алгебраических уравнений;

• проведено теоретическое исследование и численная проверка предложенных переобуславливателей;

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

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

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

Достоверность. Представленные в диссертации леммы и теоремы имеют строгое математическое обоснование, предложенные методы теоретически исследованы и численно проверены. '

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

Апробация работы. Основные результаты диссертации докладывались на X и XI Всероссийских школах-семинарах молодых ученых "Современные проблемы математического моделирования" (п. Абрау-Дюрсо 2003г., 2005г.); на IX Всероссийском совещании по проблемам построения сеток для решения задач математической физики, посвященном памяти А.Ф. Сидорова (п. Абрау-Дюрсо, 2002г.); на Международной конференции "Iterative methods and matrix computations" (г. Ростов-на-Дону, 2002г.); на II Всероссийской молодежной научной школе-конференции "Численные методы решения линейных и нелинейных краевых задач" (г. Казань, 2003г.); на Международной конференции GAMM (г.Падуя, Италия, 2003г.); на XII Международной конференции по вычислительной механике и современным прикладным программным системам (г.Владимир, 2003г.); на I Международной конференции "Computational methods in applied mathematics"

(г.Минск(,2003г.); на I и II Всероссийских конференциях "Актуальные проблемы прикладной математики и механики" (г. Екатеринбург, 2003г., п. Абрау-Дюрсо, 2004г.); на Всероссийской научно-технической конференции "Параллельные вычисления в задачах математической физики" (г. Ростов-на-Дону, 2004г.).

В полном объеме диссертационная работа докладывалась на научном семинаре "Методы решения краевых задач" лаборатории вычислительного эксперимента ЮГИНФО РГУ.

Публикации. Общее число публикаций - 19. По теме диссертации опубликовано 14 печатных работ, в том числе 7 в соавторстве. Из них 3 статьи в реферируемых отечественных и зарубежных журналах, 5 статей в сборниках трудов и 6 в тезисах докладов всероссийских и международных конференций. В работах, опубликованных в соавторстве, автору принадлежат теоретическое исследование предложенных переобуславливателей, проведение вычислительных экспериментов и анализ всех исследуемых численных методов.

Структура и объем диссертации Диссертация состоит из введения, четырех глав и списка литературы. Общий объем диссертации - 161 страница, в том числе 9 рисунков, 36 графиков, 11 таблиц, 16 диаграмм. Список литературы содержит 129 наименований.

Автор глубоко признателен своему научному руководителю д.ф.-м.н., проф. Крукиеру Л.А., благодарен коллективу ЛВЭ ЮГИНФО РГУ за внимание к работе, оказанную помощь и полезные советы, а так же своей семье за поддержку и-лонимание.

Содержание работы

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

Первая глава посвящена описанию математических моделей процессов конвекции и диффузии в средах с сильным течением. Приведены некоторые общие подходы к построению этих моделей. Дан краткий обзор существующих математических моделей различных процессов (физических, экономических, химических), в основе которых лежит уравнение конвекции-диффузии. Акцент'сделан на задачи, в которых преобладающим является конвективный перенос.

В качестве основной модельной задачи рассматривается стационарное уравнение конвекции-диффузии в ограниченной области П. Она дополнена

однородными граничными условиями Дирихле и условием несжимаемости среды:

¡-Ре-1Ди + + у2и„ + {ьги)х + (г'ги)^} = /, и|да = 0, ¿»'и (5) = 0, (х,у) еП = [0,1]х [0,1}, (1)

/ = « = и(х,у), V - {и1(х,у),иг(х,у)},

где Ре - безразмерная величина, называемая числом Пекле, а С - вектор скорости. Первое слагаемое в уравнении (1) соответствует диффузионному переносу, а остальные - конвективному, причем конвективные члены уравнения записаны в симметричной форме. В той или иной ситуации может преобладать конвективный или диффузионный перенос. Для оценки вклада конвективного переноса служит число Пекле. Если Ре « 1 мы имеем процесс с доминированием диффузии, если Ре » 1, то наоборот, доминирует конвекция.

Для аппроксимации задачи (1) использовался метод конечных разностей. Для этого в рассматриваемой области строилась равномерная сетка ин = {(гЬ^Ь), i,j = 0,1, ...Лг, ИИ = 1}, где Н, - шаг сетки, а N - число точек разбиения. Рассмотрены различные способы аппроксимации конвективных членов. Обоснован выбор центрально-разностной аппроксимации. Для симметричной формы записи конвективных слагаемых такой способ дискретизации позволил сохранить свойство их кососимметрии при любых значениях коэффициентов уравнения.

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

Аи — Ь. (2)

Представим матрицу А в виде А — Ао + Аг, где Ао — |(Л + -4*) — Ао* -симметричная составляющая исходной матрицы и Аг = ^(А — А*) — —.А1* - кососимметричная. Ао - разностный аналог оператора диффузионного переноса, А\ - конвективного. В нашем случае матрица А будет диссипа-тивной, т.е. Ао > О

Если параметр при старшей производной мал, то мы получаем СЛАУ с сильно несимметричной матрицей.

Определение 1. Матрица А называется сильно несимметричной, если В некоторой матричной норме выполняется неравенство ||/1о||, <<

В диссертационной работе этому классу матриц уделено особое внимание. ..-'■.

В завершении первой главы даны описания задач, на которых были протестированы предложенные численные методы. В Таблице 1 приведены четыре варианта задания коэффициентов при конвективных членах для задачи (1) - постоянные, с разделяющимися переменными, линейные и быстроменяющиеся. Правая часть уравнения конвекции-диффузии выбиралась таким образом, чтобы аналитическим решением задачи была функция и (х, у) = еху зт(тга) зт(я-у). Для аппроксимации использовался метод конечных разностей с центрально-разностной аппроксимацией первых производных на сетках 32х32, 64х 64, 128 х 128, 256 х 256, 512 х 512. Число Пекле изменялось в пределах от 103 до 10е.

№ Задачи щ{х,у)

. 1 - 1 -1 .

2 1-2х 2у-1

3 х+у х-у

4 81п(27гх) —2яшу соз(27га:)

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

В первом разделе приводятся основные понятия и определения из теории матриц'и фунционального анализа, необходимые при проводимом исследовании.

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

В третьем разделе рассматривается класс проекционных итерационных методов. Эти методы проецируют решение на некоторое подпространство К таких! образом, чтобы невязка была в каком-то смысле минимальной. Самый распространенный прием заключается в аннулировании невязки на

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

• выбор Ь = К, приводит к методам, для которых невязка ортогональна текущему подпространству Крылова;

• выбор Ь = АК - к методам, в которых минимизируется невязка;

• если построить Ь = К(АТ, го), то мы получаем методы, для которых невязка ортогональна подпространству Крылова транспонированной матрицы;

Рассматриваются два основных способа построения базиса в подпространствах Крылова: ортогонализация Арнольди - метод построения ортогонального базиса; и биортогонализация Ланцоша - алгоритм, основанный на трехчленном рекуррентном соотношении. Обсуждаются достоинства и недостатки каждого из приведенных' алгоритмов.

Четвертый раздел посвящен методам подпространства Крылова. Приведены некоторые исторические факты относительно возникновения и развития методов этого типа, сделан их краткий обзор с привязкой к выбору подпространств. Подробное описание, теоретические выкладки и практическая реализация приведены для двух методов подпространства Крылова: обобщенного метода минимальных невязок (СМКЕЗ(т)) и метода бисо-пряженных градиентов (ВЮС). Даны ссылки на интересные источники, посвященные теории итерационных методов.

Пятый раздел второй главы посвящен описанию ускорения методов подпространства Крылова с помощью переобуславливания (или иначе предо-бусловливания). Основная идея этой методики заключается в том, что исходная система линейных алгебраических уравнений трансформируется в другую систему с матрицей, которая обладает "лучшими" свойствами, и итерационный метод сходится быстрее.

Пусть В - некоторая невырожденная матрица. Домножив (2) на В~1 получаем систему

В~1Аи = В~\ (3)

Описаный способ переобуславливания называется левым, поскольку домно-жение на матрицу происходит слева. В работе также рассмативается правое и двустороннее переобуславливание. Приведены основные требования

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

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

Таблица 2: Количество итераций (1М) [время счета (Т)] методов.

Ре 32 х 32 128 X 128

СМНЕЗ(Ю) ВЮв СМ11Е8(10) ВЮв

Задача 1

1Сг 28 [0.125] 183 [0.063] 38 [7.140] 39 [0.228]

10й 10542 [44.719] 877 [0.312] 4526 [822.546] 1287 [7.594]

Ь' "• > Задача 2

10а 33 [0.140] 146 [0.047] 82 [15.828] 215 [1.390]

10ь 9877 [42.797] 479 [0.140] 5626 [1036.219] 5118 [32.172]

Задача 3

10^ 39 [0.187] .366 [0.125] 12988 [56.735] 2566 [0.875]

10ь 62 [11.641] 212 [1.309] 5241 [966.485] 35752 [220.953]

Задача 4

10а 77 [0.797] 601 0.781] 15492 [174.187] 1708 [2.156]

10ь 129 [36.156] 1676 35.671] 15690 [4329.890] 16926 [359.469]

Б первом разделе исследуется эффективность методов вариационного типа для решения систем с сильно несимметричной матрицей. Сравнительный анализ проводился на примере двух методов. Среди методов, строящих ортонормированный базис подпространства Крылова, был выбран СМ11Е8(т), а из методов, основанных на построении биортогонального базиса, взят ВЮС. Обоснован выбор именно этих представителей своих классов, как наиболее известных и часто используемых. Дано описание достоинств и недостатков каждого из" этих подходов, сделаны выводы о целесообразности их использования для решейия сильно несимметричных систем линейных алгебраических уравнений.

Некоторые результаты проведенного исследования отражены в Таблице 2 и на Рис. 1. Для всех численных тестов, приведенных в данной главе, начальное приближение методов бралось нулевым, а итерационный процесс прекращался, если выполнялось условие для соотношения норм невязок

]М 10_6 1М<1и '

где гт - невязка на т-ом шаге.

р»»т ооооо. птмв

у-<1.гх^у-1>,Рв-юоом.плгв

.......* «со "

............омякощ.

........ Х-*»!! У-Ы|..... .............

V-................

4 чм

600 1 000 1500 2000 2500 3000 у-{>Ц2рх);-2руС0|(2рк)), Р»-100000. п-12»

10000 12000

Рис. 1: Графики зависимости логарифма отношения невязок овоыиы!)) от числа итераций (Я) методов БЮв и СМ11Е8(10)

Следующие разделы содержат описание кососимметрических итерационных алгоритмов - треугольного кососимметрического метода (ТКМ) и попеременно-треугольного кососимметрического метода (ПТКМ), специально созданных для решения сильно несимметричных задач. Базовый алгоритм, лежащий в основе этого класса методов был предложен Л.А. Крукиером1 и развит в трудах его учеников. Ключевой идеей было использование в операторе метода информации о поведении кососимметрич-ной части исходной матрицы. Это обеспечивало устойчивый итерационный процесс и быструю сходимость методов в случаях, когда нет диагонального преобладания, и матрица системы является сильно несимметричной. Единственным ограничением этих методов является требование диссипа-тивности исходной матрицы. Для данного класса методов приводятся достаточные условия сходимости, описываются способы ускорения. ;

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

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

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

Переобуславливатели, построенные на основе ТКМ и ПТКМ, имеют простую структуру. Определим ТКМ-переобуславливатель как

В (и) = Вс + шКь (4)

и ПТКМ-переобуславливатель как

" В{и) = {Вс + иК£)В£1(Вс + иКи). (5)

Здесь Вс, -диагональная матрица, имеющая различную форму, Кь и Кц -соответственно строго нижне- и верхнетреугольные составляющие кососим-метрич'ной части А1 исходной матрицы А, ы - итерационный параметр.

В*-работе показано, что выбор диагональной составляющей Вр существенно'^влияет на скорость сходимости предложенных переобуславливателей.

Элементы диагональной матрицыВс для ТКМ- и ПТКМ-переобуславливателей определяются как

Ъсн = 1, ¿=1, ...,п, (6)

1 "

ЬСН = о-Е (\аоц\ + 1а1у 1)>. » = !»•••» п, (7)

■Г" - /=1

.. / I п

'' Ьсн = -{тахУ^(1аоц| + |ац,|)}, г = 1, (8)

• ' ¿-1

где аоу - элементы матрицы Ао, а ищ - соответствующие элементы матрицы (Ки — Кх,). Обозначим эти модификации ТКМО, ТКМ1, ТКМ2 и ПТКМО, ПТКМ1, ПТКМ2 соответственно.

В диссертации также рассматриваются беспараметрические аналоги вышеперечисленных переобуславливателей. Они получаются, если в (4) и (5) параметр и> положить. равным 1. Обозначим их БТКМ- и БПТКМ-переобуславливателями. Элементы матрицы Вс в этом случае определялись выражениями (7) и (8). И мы приходили к БТКМ1, БТКМ2 и БПТКМ1, БПТКМ2 соответственно.

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

Рассмотренные выше переобуславливатели применяются для двух методов крыловского типа: СМГ1ЕЗ(т) и В1СС. При этом используется методика левого переобуславливания.

Таблица 3: Количество итераций (И) [время счета (Т)] методов. Сетка 128 х

Ш

Pe GMRES{ 10) GMRES(10) +БТКМ1 GMRES( 10) +БПТКМ1- GMRES( 10) +SSOR

Задача 1

l(r 38 [7.140] 30 5.734] 18 [3.735] 23 [5.259]

104 71 [13.141] 35 6.672] 21 [4.360] 28 [5.656]

105 617 [114.859] 245 46.750] 100 [20.718] 241 [48.922]

10й 4526 [822.546] 1560 297.355] 709 [147.062] 1759 [347.078]

Задача 2

10J 82 [15.828] 20 [3.500 10 [2.172] 45 [9.950]

104 179 [33.062] 25 [4.860 17 [3.641] 67 [13.985]

10s 609 [115.187] 98 [19.047] 40 [8.563] 245 [51.328]

10ti 5626 [1036.219] 971 [188.255] 223 [44.672] 2294 [445.109]

Задача 3

10J 62 [11.641] 23 4.469 13 2.797 35 7.390]

104 117 [21.766] 44 8.532 19 4.047 48 9.953]

10b 657 [122.594] 240 46.538] 40 8.515 231 47.953]

10tí 5241 [966.485] 1703 330.277] 277 58.750] 1833 357.000]

Задача 4

103 129 36.156 . 44 [13.078 11 [3.563] 61 [19.172]

104 225 63.734 60 [17.953 17 [5.485] 129 40.250]

lO6 1776 488.656] 561 [167.832] 58 [18.625] 1153 357.519]

10tí 15690 4329.890] 3841 [1149.099] 255 [82.015] 11064 3174.906]

Приводятся результаты теоретического исследования кососимметриче-ских переобуславливателей для метода GMRES. Доказана лемма о локализации спектра переобусловленной матрицы для попеременно-треугольного кососимметрического переобуславливателя. При доказательстве были использованы результаты из работы Вонг и Баи2.

Введем некоторые обозначения. Представим оператор B(gj) в виде суммы симметричной и кососимметричной частей

В{ш) = В„ H + Bi{üj).

2 Wang £., Bai Z.-Z. Skew-Hermitian triangular splitting iteration methods for non-Hermitian positive definite linear systems oí strong skew-Hermitian parts // BIT Numer. Math., 2004, V.44, p.S63-386.

Таблица 4: Количество итераций (1^) [время счета (Т)] методов. Сетка 128 х

Ре В1Св В1Св + БТКМ1 ВгС<2+ БПТКМ0 5гС<2+ ЗБСЖ

Задача 1

103 39 [0.228] 39 [0.325] 15 [0.152] 13 [0.116]

104 523 3.172 501 [4.182] 519 5.281] 314 [2.844]

10ь 815 4.813 783 [6.525] 1018 10.344] 813 [7.453]

106 1287 [7.594] 1565 [13.041] 1281 13.000] 1285 [11.640]

Задача 2

10^ 215 1.390] 230 2.500 150 [1.687] 135 [1.406]

104 903 5.844] 484 5.213 480 [5.469] 396 [4.125]

10ь 3342 20.906] 714 6.797 3149 [35.765] 3444 [35.734]

10« 5118 32.172] 2023 19.141] 5088 [57.235] 5174 [55.391]

Задача 3

10^ 212 [1.309] 201 2.328] 128 [1.420] 140 1.484]

104 1525 [9.421] 3112 30.125] 358 [4.141] 334 3.500]

10ь 5750 [35.750] 3727 35.234] 1637 [18.828] 1750 18.219]

10й 35752 [220.953] 26889 253.234] 11669 [133.234] 12464 130.047]

Задача 4

10л 1676 [35.671] 352 [9.493] 648 [18.759] 404 11.453]

104 2535 [53.688] 482 [13.297] 829 [24.344 ] 671 18.984]

10ь 12314 [266.843] 2424 [69.157] 5344 [157.141] 4653 133.172]

10ь 16926 [359.469] 5328 [146.687 ] 14070 [409.453] 9181 260.235]

Предположим, что

О < акЕ <Аа< РнЕ, акЕ < Ва(ы) <

Поскольку Ао самосопряженный положительно определенный оператор, ¿?о(ш) самосопряженный оператор, то границы щ и £ — Л,Л легко вычисляются.

Лемма 1. Пусть матрицы А и В(ш) диссипативны. Тогда спектр матрицы В(и>)~1А содержится е одном из следующих трех кругов:

<*: ■("" (& + ЬУ) +У* = (к ~ ЬУ. ^и % > I, (*-1 (£■+ +^ = - «*« £ < Н

13

. Используя Лемму 1 и результаты исследования метода GMR.ES из монографии Саада3, получим оценку асимптотической скорости сходимости переобусловленного метода GMR.ES с использованием ПТКМ-переобуславливателя.

Теорема 1. Пусть операторы А и В(ш) диссипативны. Т(В(и)~1А) - множество, содержащее спектр матрицы В(и))~1А. Тогда асимптотическая скорость сходимости переобусловленного метода САШЕ Б с использованием ПТКМ-переобуславливателя для решения СЛАУ (3) определяется величиной

в (г (В(ш)-1А))=.

f 1h__¿Л / (Jk--L если ""-24. > 1

. 2oj, и) / \2ah + и) ' еСЛи ' Зк — ы>

= + если

I ы 2Рк) \ы 2P'h J ah ш

^-ТП / I^ + TA , если

Ott Dt ß t \ Ott ' 0t / ? — U) — Qt

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

В качестве переобуславливателей использовались параметрические методы ТКМО, ТКМ1, ТКМ2, ПТКМО, ПТКМ1, ПТКМ2 и их беспараметрические аналоги БТКМ1, ВТКМ2, ВПТКМ1, БПТКМ2, а также, для оценки эффективности предложенных методов, метод симметричной верхней релаксации SSOR. В Таблицах 3, 4 представлены лучшие из протестированных переобуславливателей (например, для метода GMRES(m) лучший треугольный и лучший попеременно-треугольный переобуславливатель и т.д.): Эффективность предложенных методов оценивалась по количеству итераций и затраченному времени (расчеты производились на одной вычислительной машине). Все значения числа итераций для параметриче-. ских переобуславливателей даны для оптимального значения итерационного параметра, когда наблюдалась максимальная скорость сходимости. Если параметрический и беспараметрический переобуславливатели давали сравнимые результаты, то лучшим считался беспараметрический переобуславливатель.

Представлены диаграммы сравнения эффективности различных переобуславливателей (Рис. 2-5), каждый столбец которых показывает, во сколько раз соответствующий переобуславливатель улучшает работу метода. •

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

s Sa ad У. Iterative methods for Sparse Linear Systems. PWS Publishing Company, 1995.

0СМ(?Е5+бЖМ1

■ смкез+6ПГКМ1

■ ОМКЕЗ+ЗЭСШ

Рис. 2: Диаграммы отношения временных затрат непереобусловленого метода ОМ11ЕЗ(10) к переобусловленному для Задачи 1. Ре = 103 (слева) и Ре = Ю6 (справа)

25

м. 11 ■ Ц 4- г

32x32

£12x512 ре

126x126

I

512x512 Ре

□ 8МКЕ5+еТХМ1

■ ОМЯЕЕ+ЬПТКМ!

■ ЗМВЕЗ+БК®

Рис. 3: Диаграммы отношения временных затрат непереобусловленого метода СМ11ЕЗ(10) к переобусловленному для Задачи 1. Ре = 103 (слева) и Ре = 106 (справа)

□ СМРЕЭ+еЖМ! ■ еМ1}ЕЗ+БПГКМ1

■омкеб+ЗЗОН

Рис. 4: Диаграммы отношения временных затрат непереобусловленого метода СМИЕЗ(10) к переобусловленному для Задачи 1. Ре = 103 (слева) и Ре = 106 (справа)

ш

□ СМЯЕЭ+БТКМ! ЦВМКЕЗ+БГТГКМ!

512x512 Ро

Рис. 5: Диаграммы отношения временных затрат непереобусловленого метода СМ11ЕЗ(10) к переобусловленному для Задачи 1. Ре — 103 (слева) и Ре = 10е (справа)

итерационных методов и переобуславливателей в зависимости от особенностей решаемой задачи.

В четвертой главе описывается программный комплекс, реализующий методы GMRES(m) и BiCG с предложенными переобуславливателями. Обосновывается выбор Web-интерфейса, как платформо- и машиннонеза-висимого, дается его описание, а также описание необходимых входных данных.

ДАя пользователя Web-интерфейс реализован в виде DHTML-форм (Рис. 6). В процессе рабЬты пользователь вводит туда данные, правильность заполнения которых проверяет JavaScript на компьютере пользователя. Создание скриптов для постановки задания на счет осуществляют CGI-сценарии, написанные на языке Perl и расположенные на Web-cepBepe, они Же формируют входные данные для счетных модулей комплекса и HTML-страницу для вывода результатов счета. Во время счета эта страница обновляется и позволяет увидеть степень прохождения задания, причем обновление происходит без перезагрузки страницы. Итоговые данные в виде графического и текстового файла помещаются на этой же страни-

5 Файл Праиа Вцд заалвд« Иисвдмаиты' Спраака

<й' Ф 4P Й? . ¿Г Ш~Мр«мало» "

ja Ю Пписг Goopla

Новая задача'

-¿¿»♦¿['v. ♦vi">

"I, - 0. oüv(v) • 0. (*.>),е О-[0.1]*[0.4

Размер сетей |

КЗЗИВВжйШШ» яаияюя ® в,со

О GUFES(m)

^Ш/згЯвёвШ&БШ^ЩШ

С Без переобусдавлнвапля ® ТреутодьныЯ метод (ТКМ) О Поперемеино-треугоямшй метод ШТКМ) О С»мметржчны4 метод верхнеИ релаюацин (SSOB) ОТКМО ОХЕМ1 ®ТКМ2 О без параметра © С Параметром Параметр |D.S)

0 Добаамтг а очередь

1 Оттеавотъ.|

Рис. 6: Стартовая страница программного комплекса.

це по окончании расчета. При повторном обращении к странице состояние формы и последние введенные данные восстанавливаются, этот механизм реализован с помощью Cookies. Счетные модули комплекса написаны на языке С++. т

Все. используемые на сервере программы, а именно компилятор языка С++, итрерпретатор Perl, графический редактор GnuPlot являются свободно распростроняемыми.

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

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

1. Для численной реализации математических моделей конвективно-диффузионного переноса в средах с преобладающей конвекцией предложены и теоретически обоснованы эффективные переобуславливате-ли методов подпространства Крылова.

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

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

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

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

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

1. Krukier L.A., Lapshina О. Skew-symmetric iterative methods for solution of nonlinear steady convection-diffusion equation // Nonlinear analysis and nonlinear modeling, Part 1, Nonlinear differential equations, 2001, p.283-291.

2. Lapshina O.A. Numerical comparison of BiCG and GMRES methods for solution of steady convection-diffusion problems // Iterative methods and matrix computations, Lectures of Instructors and Abstracts of Young Scientists, Rostov-on-Don, Russia, RSU CC, 2002, p.424-427.

3. Лапшина O.A. Методы подпространства Крылова для решения несимметричных систем линейных алгебраических уравнений // Тезисы докладов IX Всероссийского совещания по проблемам построения сеток для решения задач математической физики, посвященного памяти академика А.Ф. Сидорова, Дюрсо, 2002, с.36-37.

4. Лапшина О.А. Использование вариационных итерационных методов для решения систем с сильно несимметричной матрицей // Тезисы докладов Всероссийской конференции "Актуальные проблемы прикладной математики и механики" посвященной 70-летию со дня рождения академика А.Ф. Сидорова, Екатеринбург, УрО РАН, 2003, с.51-52

5. Лапшина О.А. Использование треугольных и попеременно-треугольных переобуславливателей для методов вариационного типа. // Труды Всероссийской молодежной школы-семинара "Численные методы решения линейных и нелинейных краевых задач" Казань: Изд. Казанского математического общества, 2003, с.191-199.

6. Lapshina О.А. Trangular skew-symmetric iterative solvers as preconditioners for solving system of linear equations // Book of Abstracts First International Conference "Computational methods in applied mathematics" Minsk, 2003, p.35-36.

7. Krukier L.A., Lapshina O.A., Krukier B,L. Special preconditioners for solution of transport-dominated convection-diffusion problem // PAMM. v3, No 1, 2003. p.549-550.

8. Крукиер Л.А., Лапшина О.А. Использование метода BiCG с различными переобуславливателями при решении сильно несимметричных систем линейных уравнений // Тезисы докладов XII Международной конференции по вычислительной механике и современным прикладным программным системам (ВМСППС'2003), 2003, с.36-37.

9. Крукиер Л.А., Лапшина О.А. Численное сравнение вариационных методов решения СЛАУ, получаемых при конечно-разностной аппроксимации уравнения конвекции-диффузии // Математическое Моделирование т. 16, №4, 2004г, с.23-32.

10. Лапшина О.А. Практические рекомендации к решению сильно несимметричных систем линейных уравнений вариационными методами с переобуславливанием // Сборник трудов X Всероссийской Школы-семинара "Современные проблемы математического моделирования" Ростов-на-Дону: Изд. РГУ, 2004, с.134-150.

11. Лапшина О.А. Использование технологии переобуславливания при решении систем с сильно несимметричной матрицей // Тезисы докладов Всероссийской конференции "Актуальные проблемы прикладной математики и механики" посвященной памяти академика А.Ф. Сидорова, Абрау-Дюрсо, 2004, с.65-66.

12. Чикина JI.Г., Пичугина О.А. Крукиер Б.Л. Решение сильно несимметричных систем линейных алгебраических уравнений вариационными методами с переобуславливателями специального вида // Всероссийская научно-техническая конференция '.'Параллельные вычисления в задачах математической физики" Ростов-на-Дону: Изд. РГУ, 2004, с.159-17.0.

13. Мартынова Т.С., Пичугина О.А. Использование попеременно-треугольных итерационных методов для переобуславливания методов вариационного типа // Сборник трудов XI Всероссийской школы-семинара "Современные проблемы математического моделирования" Ростов-на-Дону: Изд. РГУ, 2005, с.258-268.

14. Krukier L.A., Pichugina О.А. and Sokolov V.O. Numerical investigation of Krylov subspacc methods for solving non-symmetric systems of linear equations with dominant skew-symmetric part // Numerical Analysis and Modeling, V.3, N.l, 2006, p.115-124.

Издательство ООО «ЦВВР». Лицензия ЛР № 65-36 от 05.08.99 г. Сдано в набор 5.09.06 г. Подписано в печать 5.09.06 г. Формат 60*84 1/16 Заказ № 754. Бумага офсетная. Гарнитура «Тайме». Оперативная печать. Тираж 100 экз. Печ. Лист 1,0. Усл.печ.л. 1,0. Типография: Издательско-полиграфический комплекс « Биос» РГУ 344091, г. Ростов-на-Дону, ул. Зорге, 28/2, корп. 5 «В», тел (863) 247-80-51. Лицензия на полиграфическую деятельность № 65-125 от 09.02.98 г.

Введение

1 Моделирование процессов распространения в средах с сильным течением

1.1 Некоторые подходы к построению математических моделей

1.2 Моделирование процессов в движущихся средах.

1.3 Уравнение конвекции-диффузии и его свойства

1.4 Обзор математических моделей процессов конвективно-диффузионного переноса в средах с преобладающей конвекцией

1.5 Аппроксимация.

1.6 Описание тестовых задач.

2 Методы решения системы линейных алгебраических уравнений

2.1 Общие сведения

2.1.1 Линейное пространство.

2.1.2 Линейные операторы и матрицы.

2.1.3 Специальные матрицы и их свойства.

2.1.4 Скалярные произведения и нормы.

2.1.5 Базис

2.2 Классические итерационные методы.

2.2.1 Общая теория итерационных методов.

2.2.2 Метод простой итерации (Якоби).

2.2.3 Метод Гаусса-Зейделя.

2.2.4 Методы SOR и SSOR

2.2.5 Треугольные и попеременно-треугольные методы

2.2.6 Ускорение классических итерационных методов

2.2.7 Методы неполной факторизации.

2.3 Проекционные итерационные методы.

2.3.1 Общий подход к построению проекционных методов

2.3.2 Подпространства Крылова.

2.3.3 Базис подпространства Крылова.

2.4 Методы крыловского типа.

2.4.1 Методы подпространства Крылова.

2.4.2 GMRES.

2.4.3 BiCG.

2.5 Переобуславливание.

2.5.1 Переобуславливатели Якоби и Гаусса-Зейделя

2.5.2 SOR- и SSOR-переобуславливание.

2.5.3 Неполное LU-разложение.

2.5.4 Полиномиальное переобуславливание.

2.5.5 Минимизация функционала.

2.5.6 Декомпозиция области.

Современные методы решения сильно несимметричных систем

3.1 Вариационные методы.

3.2 Метод симметрического и кососимметрического расщепления

3.3 Кососимметрические методы.

3.3.1 Базовые кососимметрические методы.

3.3.2 Ускорение базовых кососимметических методов

3.3.3 Беспараметрические кососимметрические методы

3.3.4 Модифицированные кососимметрические методы . ИЗ

3.4 Треугольные и попеременно-треугольные кососимметриче-ские переобуславливатели.

3.5 Сравнение треугольных и попеременно-треугольных кососим-метрических переобуславливателей.

4 Программный комплекс

4.1 Структура и описание программного комплекса.

4.2 Описание интерфейса с пользователем.

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

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

Первые три этапа - построение собственно математической модели. Основное требование, предъявляемое к математической модели, - адекватное описание физических процессов, протекающих в исследуемых системах. Однако охватить все многообразие явлений чрезвычайно трудно. Необходимо упростить проблему и рассмотреть только основные процессы. Какие из них являются основными, а какие второстепенными определяется в первую очередь свойствами изучаемой системы и тем кругом задач, для решения которых она предназначена. Таким образом здесь проводится математическая формализация явления (выбор характеристик, которые поддаются математическому описанию, нахождение математического выражения соотношений между характеристиками и т.п.), развивается математический аппарат, позволяющий построить математическую модель, проводится ее упрощение и т.д.

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

На последних этапах создается программное обеспечение для реализации модели и алгоритма на компьютере, а так же выполняется анализ результатов, сопоставление их с теоретическими выводами и с данными натурного эксперимента. При необходимости математические модели и вычислительные алгоритмы уточняются, так что вычислительный эксперимент повторяется на более совершенной основе. Отсюда следует, что программный продукт должен учитывать важнейшую специфику математического моделирования, связанную с использованием иерархии математических моделей, а так же многовариантностью расчетов. Это подразумевает широкое использование комплексов и пакетов прикладных программ. Комплексы программ предназначены для решения близких по своей математической природе задач из одной предметной области. Они включают в себя библиотеку программных модулей (в большей или меньшей степени независимых), из которых комплектуются рабочие программы.

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

Математические модели в движущихся средах, которые включают в себя конвективный и диффузионный перенос, описывают самые различные процессы и явления в физике, механике, биологии и экономике [101, 72, 44, 91]. В тех случаях, когда мы имеем дело со средами с сильным течением, а значит процесс конвекции является преобладающим, применение стандартных численных методов становится весьма проблематичным, с математической точки зрения это объясняется наличием малого параметра при старшей производной. При некоторых дополнительных условиях - несогласованности правой части дифференциального уравнения с краевыми условиями - в таких задачах может возникать явление пограничного слоя, т.е. резкое изменение решения в очень малой области расчета [111]. Для таких задач очень важно правильно выбрать метод разностной аппроксимации. При различных методах разностной аппроксимации дифференциального уравнения конвекции-диффузии получаем системы линейных алгебраических уравнений, обладающие различными свойствами. В случае преобладающей конвекции использование противопотоковых схем приводит к системе линейных алгебраических уравнений с монотонной матрицей (М-матрицей) и сильному сглаживанию решения за счет появления в разностных уравнениях искусственной вязкости. Поэтому при решении данных задач эффективнее использовать центрально-разностную аппроксимацию, при которой сохраняется характер поведения решения, но в результате получается система линейных алгебраических уравнений с несимметричной матрицей, не имеющей диагонального преобладания. В этом случае большинство классических и современных итерационных методов либо вообще не работают, либо обладают очень медленной скоростью сходимости. Поэтому так актуальна проблема создания эффективных численных методов для решения задач конвекции-диффузии с преобладающей конвекцией [90, 18, 42, 48].

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

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

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

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

• определен и исследован класс систем линейных алгебраических уравнений, к которым сводятся после аппроксимации рассматриваемые дифференциальные задачи;

• разработан новый класс эффективных переобуславливателей методов подпространства Крылова для решения сильно несимметричных систем линейных алгебраических уравнений;

• проведено теоретическое исследование и численная проверка предложенных переобуславливателей;

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

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

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

Достоверность. Представленные в диссертации леммы и теоремы имеют строгое математическое обоснование, предложенные методы теоретически исследованы и численно проверены.

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

Апробация работы. Основные результаты диссертации докладывались на X и XI Всероссийских школах-семинарах молодых ученых "Современные проблемы математического моделирования" (п. Абрау-Дюрсо 2003г., 2005г.); на IX Всероссийском совещании по проблемам построения сеток для решения задач математической физики, посвященном памяти А.Ф. Сидорова (п. Абрау-Дюрсо, 2002г.); на II Всероссийской молодежной научной школе-конференции "Численные методы решения линейных и нелинейных краевых задач" (г. Казань, 2003г.); на Международной конференции "Iterative methods and matrix computations" (г. Ростов-на-Дону, 2002г.); на I и II Всероссийских конференциях "Актуальные проблемы прикладной математики и механики" (г. Екатеринбург, 2003г., п. Абрау-Дюрсо, 2004г.); на Международной конференции GAMM (г.Падуя, Италия, 2003г.); на XII Международной конференции по вычислительной механике и современным прикладным программным системам (г.Владимир, 2003г.); на I Международной конференции "Computational methods in applied mathematics" (г.Минск, 2003г.); на Всероссийской научно-технической конференции "Параллельные вычисления в задачах математической физики" (г. Ростов-на-Дону, 2004г.).

В полном объеме диссертационная работа докладывалась на научном семинаре "Методы решения краевых задач" лаборатории вычислительного эксперимента ЮГИНФО РГУ.

Публикации. Общее число публикаций -19. По теме диссертации опубликовано 14 печатных работ, в том числе 7 в соавторстве. Из них 3 статьи в реферируемых отечественных и зарубежных журналах, 5 статей в сборниках трудов и 6 в тезисах докладов всероссийских и международных конференций.

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

1. Амосов А.А., Дубинский Ю.А., Копченова Н.В. Вычислительные методы для инженеров М: Высшая школа, 1994

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

3. Баландин М.Ю., Шурина Э.П. Методы решения СЛАУ большой размерности. Новосибирск: Изд. НГТУ, 2000.

4. Белоконь Т. В. Использование эффективных численных методов при моделировании конвективно-диффузионных процессов в средах с преобладающей конвекцией. Диссертация на соискание уч. ст. канд. ф.-м. Наук, РГУ, б-ка ЛВЭ ЮГИНФО РГУ, 2003

5. Богачев К.Ю. Практикум на ЭВМ. Методы решения линейных систем и нахождения собственных значений. М: Изд. МГУ, 1998.

6. Вабищевич П.Н. Численное моделирование. М.: Изд. МГУ, 1993.

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

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

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

10. Дуллан Э., Миллер Дж., Шилдерс У. Равномерные численные методы решения задач с пограничным слоем М.: Мир, 1983.

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

12. Ильин В.П. Методы конечных разностей и конечных объемов для эллиптических уравнений Новосибирск: Издательство института мате-митики, 2000.

13. Крукиер Л.А. Математическое моделирование гидрофизических процессов в мелких водоемах. Диссертация на соискание ученой степени док-тора ф.-м. наук, РГУ, б-ка ЛВЭ ЮГИНФО РГУ, 1994

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

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

16. Крукиер Л.А., Лапшина О.Л.Численное сравнение вариационных методов решения СЛАУ, получаемых при конечно-разностной аппроксимации уравнения конвекции-диффузии. // Математическое Моделирование т. 16, №4, 2004г. с. 23-32.

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

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

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

20. Марчук Г.И. Методы расчета ядерных реакторов. М.: Атомиздат, 1958.

21. Математическое моделирование / Под редакцией Эндрюса Дж., Мак-Лоурена Р.; пер. с англ. М.: Мир, 1979.

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

23. Рихтмайер Р., Мортон К. Разностные методы решения краевых задач. М.: Мир, 1972, 418с.

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

25. Самарский A.A. Введение в теорию разностных схем, М: Наука, 1971

26. Самарский A.A. Введение в численные методы. М: Наука, 1987

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

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

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

30. Федоренко Р. П. Введение в вычислительную физику. М: Изд. Физтеха, 1994.

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

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

33. Чикина Л. Г. Решение уравнения конвекции-диффузии с преобладающей конвекцией в областях сложной формы. Диссертация на соискание уч. ст. канд. ф.-м. Наук, РГУ, б-ка ЛВЭ ЮГИНФО РГУ, 1997

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

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

36. Arnoldi W.E. The principle of minimized iteration in the solution of the ma-trix eigenproblem. // Quart. Appl. Math., 1951, №9, p. 17-29

37. Ashby S.F. Minimax polynomial preconditioning for Hermitian linear systems. // SIAM J. Matrix. Fnal. Applic. 12, 1991, p. 766-789.

38. Axelsson 0. On preconditioning And convergence acceleration for spase matrix problems // Peport 74-10, CERN, 1974.

39. Axelsson 0. Iterative solution Methods. Cambridge University Press, Cam-bridge, 1994

40. Bai Z. Error Analysis of the Lanczos algorithm for the nonsymmetric eigenvalue problem. // Math. Сотр., V.62, N.205, p.209-226.

41. Bai Z.Z., Krukier L.A., Martynova T.S. Two step iterative methods for solution of steady convection-diffusion equation with small parameter at the higher derivatives on regular mesh // ЖВМ и МФ, 2006, N2, с.

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

43. Benson M.W. Iterative Solution of Large Scale Linear Systems, M.Sc. thesis (Lakehead University, Thunder Bay, Ontario, 1973).

44. Benzi M. and Tuma M. A comparative study of sparse approximate inverse preconditioners. // Appl. Numer. Math. V.30, 305, 1999.

45. Benzi M. and Tuma M. A sparse approximate inverse preconditioner for nonsymmetric linear systems. // SIAM J. Sci. Comput. v.19, 968 (1998).

46. Bjorch A. and Elfving T. Accelerated projection methods for computing pseudoinverse solutions of system linear equation. BIT, 19, 145-163, 1979.

47. Chan T.F., Galloloulos E., Simoncini V., Szeto T., Tong C.H. A quasiminimal residual variant of the BiCGSTAB algorithm for nonsymmetric sys-tems.// SIAM J. Sci. Statist. Comput., 1994, №15, p. 338-347

48. Chikina L.G., Krukier B.L. Solution of linear equation systems with dominant skew-symmetric part using the product triangular iterative method. // Computational methods in applied mathematics, 2003, v.3, №, p. 447-450.

49. Cosgrove J. D. F., Diaz J. C., and Griewank A. Approximate inverse preconditioning for sparse linear systems, Int. J. Comput. Math. 44, 91 (1992).

50. Eisenstat S., Efficient implementation of a class of conjugate gradient methods // SIAM J. Sci. Stat. Comput. 2, 1 (1981).

51. Edwards D. A. Estimating rate constants in a convection-diffusion system with a boundary reaction // IMA J. Applied Math., 1999, v.63, p.89-112.

52. Dubois P.F., Greenbaum A. and Rodrigue G.H. Aproximating the inverse of matrix for use in iterative algorithms on vector processors. Computing, 22. 1979. pp.257-268.

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

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

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

56. 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 Numeri-cal Analysis, Clarendon Press, Oxford, 1997, p. 63-92

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

58. Johnson O.G., Micheli C.A. and Paul G. Polynomial preconditioning for conjugate gradient calculations // SIAM J. Numer. Anal., 20, 1983, p. 363-376.

59. Kolotilina L. Yu., Yeremin A. Yu. Factorized sparse approximate inverse pre-conditionings.// SIAM J. Matrix Analysis and Applications, 1993, №14, p. 45-58

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

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

62. Krukier L.A., Lapshina 0. Skew-symmetric iterative methods for solution of nonlinear steady convection-diffusion equation. // Nonlinear analysis and nonlinear modeling. Part 1, Nonlinear differential equations. 2001. -P. 283-291.

63. Krukier L.A., Lapshina O.A., Krukier B.L. Special preconditioners for solution of transport-dominated convection-diffusion problem. // Annual Scientific Congerence GAMM 2003. Book of Abstracts. Abano Terme -Padua, 2003. - Session 22. - P. 234.

64. Krukier L.A., Pichugina O.A. and Sokolov V. Numerical investigation of Krylov subspace methods for solving non-symmetric systems of linear equations with dominant skew-symmetric part // Numerical Analysis and Modeling, V.3, N.l, 2006, pp. 115-124.

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

66. Lapshina O.A. Trangular skew-symmetric iterative solvers as preconditioners for solving system of linear equations. // First International Conference "Computational methods in applied mathematics". Abstracts. Minsk, 2003. - C. 35-36.

67. Manteuffel T.A. Adaptive procedure for estimating parameters for the non-symmetric Tchebychev iteration.// Numerical Math., 1978, v. 31, p 183-208

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

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

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

71. Morton K.W. Numerical solution of convection-diffusion problems. Chapman and Hall, 1996

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

73. Paige C.C., Saunders M.A. LSQR: An algorithm for sparse linear equations and sparse least squares// ACM Trans. Math. Soft., №8,19826 43-71.

74. Parlett B.N., Taylor D.R., Lin Z.A. A look-ahead Lanczos algorithm for un-symmetric matrices.// Math. Comp., 1985, №44, p. 105-124

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

76. Saad Y. ILUT: A dual threshold incomplete LU factorization, Numer. Linear Algebra Appl. 1, 387 (1994).

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

78. Saad Y. Practical use of polynomial preconditionings for the conjugate gradient method. SIAM J. Sci. Statist. Comput., 6, 1985, p. 865-881.

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

80. Schlichting H. Boundary-Layer Theory. New-York. McGraw-Hill. 1968.

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

82. Sonnoveld P. CGS: a fast Lanzos-type solver for nonsymmetric linear sys-tems.// SIAM J. Sei. Statist. Comput., 1989, №10, p. 36-52

83. Stewart G. W. A Survey of Matrix Algorithms. Vol.1: Basic Decompositions.University of Maryland, 1995.

84. Tang W.P. Generalized Schwarz splitting. SIAM J. Sei. Statist. Comput., 13,1992, p.573-595.

85. Tong C.E., Ye Q. Analysis of the finite precision biconjugate gradient algorithm for nonsymmetric linear systems // Report SCCM 95-11, Computer Science Dept., Stanford University, 1995.

86. 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. Sta-tist. Comput., 1992, №13, p. 631-644

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

88. Van der Vorst H.A. Iterative Krylov Methods for Large Linear System. Cambridge University, 2003.

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

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

91. Wang L., Bai Z.-Z. Skew-Hermitian triangular splitting iteration methods for non-Hermitian positive definite linear systems of strong skew-Hermitian parts // BIT Numer. Math. 2004. V.44. P.363-386.

92. Watts J. W. A conjugate gradient truncated direct method for the iterative solution of the reservoir simulation pressure equation, Soc. Petrol. Eng. J. 21, 345 (1981).

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

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

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

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