Содержание к диссертации
Введение
1 Моделирование процессов распространения в средах с сильным течением 12
1.1 Некоторые подходы к построению математических моделей . 12
1.2 Моделирование процессов в движущихся средах 14
1.3 Уравнение конвекции-диффузии и его свойства 19
1.4 Обзор математических моделей процессов конвективно-диффузионного переноса в средах с преобладающей конвекцией 23
1.5 Аппроксимация 27
1.6 Описание тестовых задач 31
2 Методы решения системы линейных алгебраических уравнений 34
2.1 Общие сведения 34
2.1.1 Линейное пространство 34
2.1.2 Линейные операторы и матрицы 35
2.1.3 Специальные матрицы и их свойства 37
2.1.4 Скалярные произведения и нормы 38
2.1.5 Базис 41
2.2 Классические итерационные методы 42
2.2.1 Общая теория итерационных методов 42
2.2.2 Метод простой итерации (Якоби) 47
2.2.3 Метод Гаусса-Зейделя 48
2.2.4 Методы SORH SSOR 49
2.2.5 Треугольные и попеременно-треугольные методы . 51
2.2.6 Ускорение классических итерационных методов . 53
2.2.7 Методы неполной факторизации 56
2.3 Проекционные итерационные методы 58
2.3.1 Общий подход к построению проекционных методов . 58
2.3.2 Подпространства Крылова 62
2.3.3 Базис подпространства Крылова 65
2.4 Методы крыловского типа 70
2.4.1 Методы подпространства Крылова 70
2.4.2 GMRES 77
2.4.3 BiCG 81
2.5 Переобуславливание 84
2.5.1 Переобуславливатели Якоби и Гаусса-Зейделя . 88
2.5.2 SOR- и SSOR-переобуславливание 88
2.5.3 Неполное LU-разложение 90
2.5.4 Полиномиальное переобуславливание 91
2.5.5 Минимизация функционала 92
2.5.6 Декомпозиция области 95
3 Современные методы решения сильно несимметричных систем 97
3.1 Вариационные методы 97
3.2 Метод симметрического и кососимметрического расщепления 106
3.3 Кососимметрические методы 107
3.3.1 Базовые кососимметрические методы 108
3.3.2 Ускорение базовых кососимметических методов . 110
3.3.3 Беспараметрические кососимметрические методы . 112
3.3.4 Модифицированные кососимметрические методы . ИЗ
3.4 Треугольные и попеременно-треугольные кососимметриче-ские переобуславливатели 115
3.5 Сравнение треугольных и попеременно-треугольных кососим-метрических переобуславливателей 119
4 Программный комплекс 135
4.1 Структура и описание программного комплекса 135
4.2 Описание интерфейса с пользователем 140
Литература
- Моделирование процессов в движущихся средах
- Специальные матрицы и их свойства
- Метод симметрического и кососимметрического расщепления
- Описание интерфейса с пользователем
Введение к работе
Невозможно представить себе современную науку без широкого применения математического моделирования. Сущность этой методологии состоит в замене исходного объекта его "образом" - математической моделью -и в дальнейшем изучении модели с помощью реализуемых на компьютерах вычислительно-логических алгоритмов. Такой подход сочетает в себе многие достоинства, как теории, так и эксперимента. Работа не с самим объектом, а с его моделью дает возможность безболезненно, относительно быстро и без существенных затрат использовать его свойства и поведение в любых мыслимых ситуациях (преимущества теории). В тоже время вычислительные эксперименты с моделями объектов позволяют, опираясь на мощь современных вычислительных и технических инструментов информатики, подробно и глубоко изучать объекты в достаточной полноте, недоступной чисто теоретическим подходам (преимущества эксперимента). Неудивительно, что методология математического моделирования бурно развивается, охватывая все новые сферы.
В настоящее время сложилась вполне определенная технологическая цепочка математического моделирования: объект исследования - физическая модель - математическая (непрерывная) модель - численная (дискретная) модель - алгоритмическая модель - компьютерная модель (программа) -расчет (вычислительный эксперимент) - интерпретация результатов (анализ, сравнение с экспериментальными и другими данными).
Первые три этапа - построение собственно математической модели. Основное требование, предъявляемое к математической модели, - адекватное описание физических процессов, протекающих в исследуемых системах. Однако охватить все многообразие явлений чрезвычайно трудно. Необходи- мо упростить проблему и рассмотреть только основные процессы. Какие из них являются основными, а какие второстепенными определяется в первую очередь свойствами изучаемой системы и тем кругом задач, для решения которых она предназначена. Таким образом здесь проводится математическая формализация явления (выбор характеристик, которые поддаются математическому описанию, нахождение математического выражения соотношений между характеристиками и т.п.), развивается математический аппарат, позволяющий построить математическую модель, проводится ее упрощение и т.д.
На следующих этапах строится дискретная задача и численный метод решения этой дискретной задачи. Проводятся строгие доказательства существования и единственности решения дискретной задачи, получают теоретические оценки погрешности приближенного решения, сходимости итерационного процесса. Модель представляется в форме, удобной для применения численных методов, определяется последовательность вычислительных и логических операций, которые нужно произвести, чтобы найти искомые величины с заданной точностью. Используемые вычислительные алгоритмы не должны искажать основные свойства модели и, следовательно, исходного объекта, быть экономичными и адаптирующимися к особенностям решаемых задач.
На последних этапах создается программное обеспечение для реализации модели и алгоритма на компьютере, а так же выполняется анализ результатов, сопоставление их с теоретическими выводами и с данными натурного эксперимента. При необходимости математические модели и вычислительные алгоритмы уточняются, так что вычислительный эксперимент повторяется на более совершенной основе. Отсюда следует, что программный продукт должен учитывать важнейшую специфику математического моделирования, связанную с использованием иерархии математических моделей, а так же многовариантностью расчетов. Это подразумевает широкое использование комплексов и пакетов прикладных программ. Комплексы программ предназначены для решения близких по своей математической природе задач из одной предметной области. Они включают в себя библиотеку программных модулей (в большей или меньшей степени независимых), из которых комплектуются рабочие программы.
Математическое моделирование широко используется при описании процессов в движущихся средах. Значительная сложность явлений вынуждает ученых не ограничиваться теоретическими исследованиями, но также использовать при изучении процессов методы математического моделирования.
Математические модели в движущихся средах, которые включают в себя конвективный и диффузионный перенос, описывают самые различные процессы и явления в физике, механике, биологии и экономике [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 в тезисах докладов всероссийских и международных конференций.
Структура и объем диссертации Диссертация состоит из введения, четырех глав и списка литературы.
Во введении раскрывается актуальность темы диссертации, изложены основные цели и задачи диссертации, показана их практическая значимость, представлена структура диссертации и сформулированы основные положения, выносимые на защиту.
Первая глава посвящена математическому моделированию процессов конвекции и диффузии в средах с сильным течением. В первом разделе приведены некоторые подходы к построению математических моделей. Второй раздел содержит физическое описание процессов конвекции и диффузии. В третьем разделе дано описание решаемой задачи и основных ее свойств. Отмечены особенности формы записи оператора конвективного переноса. В четвертом разделе сделан краткий обзор существующих математических моделей различных процессов (физических, экономических, химических), в основе которых лежит уравнение конвекции-диффузии с преобладающей конвекцией. В пятом разделе приведены некоторые понятия метода сеток. Рассмотрены различные способы аппроксимации операторов конвективного и диффузионного переноса. В шестом разделе первой главы дается описание задач, на которых были протестированы предложенные численные методы.
Во второй главе диссертации анализируются существующие классические и современные численные методы решения систем линейных алгебраических уравнений, а так же методы решения сильно несимметричных систем линейных алгебраических уравнений.
В первом разделе приводятся основные понятия и определения из тео- рий матриц и фунционального анализа, необходимые при проводимом исследовании. Второй раздел посвящен общей теории итерационных методов. Даны основные определения и формулировки теорем. Описываются два основных подхода к исследованию итерационных методов релаксационного типа - операторный, при котором исследуется норма оператора перехода, и спектральный, при котором исследуется спектральный радиус оператора перехода. Представлен обзор классических и современных итерационных методов решения систем линейных алгебраических уравнений, условия их сходимости. Сделан краткий обзор методов их ускорения.
В третьем параграфе второй главы рассматриваются проекционные итерационные методы. Приведен общий подход к построению проекционных методов. Даны необходимые определения. Вводится понятие подпространств Крылова. Приводятся три важнейших подхода к выбору подпространств. Рассматриваются два основных способа построения базиса в подпространствах Крылова: ортогонализация Арнольди, метод построения ортонормированного базиса; и биортогонализация Ланцоша - алгоритм, основанный на трехчленном рекуррентном соотношении. Обсуждаются достоинства и недостатки каждого из приведенных алгоритмов.
Четвертый раздел посвящен методам подпространства Крылова. Приведены некоторые исторические факты относительно возникновения и развития методов крыловского типа, сделан их краткий обзор с привязкой к выбору подпространств. Подробное описание, теоретические выкладки и практическая реализация приведены для двух методов подпространства Крылова: GMRES(m) и BiCG. Кроме того описаны достоинства и недостатки каждого из этих методов, проведен сравнительный анализ. Даны ссылки на интересные источники, посвященные теории итерационных методов.
Пятый параграф второй главы посвящен описанию ускорения методов подпространства Крылова с помощью переобуславливания (или иначе пре-добусловливания). Основная идея этой методики заключается в том, что исходная система линейных алгебраических уравнений трансформируется в другую систему с матрицей, которая обладает лучшими свойствами, и итерационный метод сходится быстрее. Описаны правый, левый и двухсторонний способы переобуславливания. Приведены основные требования к выбору "хорошего" переобуславливателя. Дан обзор основных методик переобуславливания и наиболее распространенных переобуславливателей.
Третья глава посвящена методам решения сильно несимметричных систем линейных алгебраических уравнений, в ней систематизированы уже существующие методы и предложены новые. Здесь содержатся основные теоретические и практические результаты диссертации.
В первом разделе исследуется эффективность методов вариационного типа для решения систем с сильно несимметричной матрицей. Сравнительный анализ проводился на примере двух методов. Среди методов, строящих ортонормированный базис подпространства Крылова, был выбран" GMRES(m), а из методов, основанных на построении биортогонального базиса, взят BiCG. Обоснован выбор именно этих представителей своих классов, как наиболее известных и часто используемых. Дано описание достоинств и недостатков каждого из этих подходов, проведено численное-исследование, сделаны выводы о целесообразности их использования для решения сильно несимметричных систем линейных алгебраических уравнений.
Следующие разделы содержат описание кососимметрических итерационных алгоритмов, специально созданных для решения сильно несимметричных задач. Базовый алгоритм, лежащий в основе этого класса методов, был предложен Л.А. Крукиером и развит в трудах его учеников. Для данного класса методов приводятся достаточные условия сходимости, описываются способы ускорения треугольных и попеременно-треугольных косо-симметрических итерационных методов.
Далее более подробно рассматривается треугольные и попеременно- треугольные кососимметрические переобуславливатели, специально предложенные для решения сильно несимметричных СЛАУ. Приведены результаты теоретического исследования кососимметрических переобуславлива-телей для метода GMRES(m). Доказана лемма о локализации спектра переобусловленной матрицы в случае попеременно-треугольного кососимметри-ческого переобуславливателя. На основании леммы получена оценка асимптотической скорости сходимости переобусловленного метода GMRES(m) с использованием ПТКМ-переобуславливателя.
В завершении подводятся основные итоги проведенных в данной главе исследований. Отражены результаты численного исследования предложенных методов на модельных задачах, проведено их сравнение, даны рекомендации о целесообразности и эффективности использования тех или иных итерационных методов и переобуславливателей в зависимости от особенностей решаемой задачи.
В четвертой главе описывается программный комплекс, реализующий методы GMRES(m) и BiCG с предложенными переобуславливателя-ми. Обосновывается выбор Web-интерфейса, как платформо- и машинно-независимого, дается его описание, а также описание тех данных, которые ' необходимо ввести. Приводится подробное описание интерфейса с пользователем.
К защите представлены следующие результаты:
Для численной реализации математических моделей конвективно-диффузионного переноса в средах с преобладающей конвекцией предложены и теоретически обоснованы эффективные переобуславливатели методов подпространства Крылова.
Доказана лемма о локализации спектра переобусловленной матрицы для попеременно-треугольного кососимметрического переобуславливателя.
Получена оценка асимптотической скорости сходимости переобусловленного метода GMRES с использованием ПТКМ-переобуславливателя.
Создан программный комплекс, реализующий математические модели конвективно-диффузионного переноса в средах с преобладающей конвекцией с использованием предложенных алгоритмов пере-обуславливания.
Проведена серия расчетов, позволяющих сравнить предложенные пе-реобуславливатели и оценить эффективность и область применимости каждого из них.
Автор глубоко признателен своему научному руководителю д.ф.-м.н., проф. Крукиеру Л.А., благодарен коллективу ЛВЭ ЮГИНФО РГУ за внимание к работе, оказанную помощь и полезные советы, а так же своей семье за поддержку и понимание.
Моделирование процессов в движущихся средах
Математические модели, о которых пойдет речь в дальнейшем описывают процессы, происходящие в движущихся средах и строятся на основе фундаментальных законов природы, в частности на основе законов сохранения. Закон сохранения - это скорее схема рассуждения, а не конкретный математический аппарат. Если последовательность рассуждений можно записать в виде йФ „ — = F dt ад то будем говорить, что сформулирован закон сохранения. Здесь t - незави симая переменная, характеризующая время.
Последнее равенство - это количественная характеристика некоторого свой ства к-то элемента системы (масса, энергия и т.п.), Х{ (г = 1,2, ...,п) признаки индивидуальности элемента системы (например координаты, фа зовые переменные), которые должны быть заданы. Причина изменения F , \ называется воздействием.
Сами изучаемые объекты могут быть совершенно различными по своей природе и назначению - физические, биологические или социальные явления, технологические процессы, механизмы или конструкции. Однако даже различные по своей природе явления могут быть описаны по сути одними и теми же моделями. И хотя в дальнейшем мы будем рассматривать достаточно конкретные физические явления, подобные рассуждения могут быть применены и в других областях знания.
Остановимся на моделировании в механике жидкостей и газов. Процессы, которые мы будем рассматривать, обусловлены двумя физическими явлениями: конвекцией и диффузией. Нужно отметить, что задачи конвекции-диффузии являются типичными для этой области исследования.
Диффузия - это взаимное проникновение соприкасающихся веществ друг в друга вследствие теплового движения частиц вещества. Диффузия происходит в направлении падения концентрации вещества и ведет к равномерному распределению вещества по всему занимаемому им объему (к выравниванию химического потенциала вещества). Смещение частицы меняется со временем случайным образом, но его средний квадрат за большое число столкновений растет пропорционально времени.
Скорость диффузии определяется величиной коэффициента диффузии, который возрастает с повышением температуры, когда тепловое движение частиц становится более быстрым. С наибольшей скоростью диффузия протекает в газах. Скорость диффузии в газах определяется как скоростью теплового движения молекул, так и длиной их свободного пробега, т.е. средней длиной тех прямолинейных отрезков пути, которые проходят молекулы газа от столкновения к столкновению.
Первый закон Фика определяет количество вещества, диффундирующего в направлении убывания концентрации. Если градиент концентрации с вдоль направления х равен dc/dx, то этот закон определяет для массы вещества dm, диффундирующего за время dt через площадку S, перпендикулярную направлению х, следующую зависимость: dc dm = -D-S- —dt. (1.2.1) ах
Знак минус показывает, что диффузия происходит в сторону умень JU шения концентрации; D - коэффициент диффузии, численно измеряемый массой вещества, диффундирующего через единичную площадку за время t = 1 при градиенте концентрации, равном 1 (имеет размерность cm2-с 1). Коэффициент диффузии определяет скорость процесса и зависит от природы частиц и состояния диффундирующего вещества и растворителя (в растворах).
Из выражения (1.2.1) при условии постоянства коэффициента диффузии получается соотношение, называемое вторым законом Фика:
Из соотношения (1.2.2) в частном случае, когда dc/dt = О (стационарный поток), следует, что концентрация диффундирующего вещества должна линейно уменьшаться вдоль направления диффузионного потока. Формулы (1.2.1) и (1.2.2) приведены для случая, когда диффузия протекает в одном направлении, однако они обобщаются и на случай двух и трех измерений.
В случае двумерной диффузии изменение концентрации с течением времени при постоянной температуре и отсутствии внешних сил описывается дифференциальным уравнением диффузии в частных производных: дЛ - JL (D—\ — (D—\ dt дх \ дх) ду \ ду) Если D не зависит от концентрации с, то уравнение приводится к виду: де = D(Pc D(Pc dt дх2 ду2 В качестве еще одного примера диффузионного процесса можно рассмотреть распространение тепла в неподвижной изотропной среде [37]. Считаем, что известно начальное распределение температуры и источники тепла, требуется найти распределение температуры в последующие моменты времени. Если распределение в некоторый момент времени t обозначить через Т = Т(х, t), где Т - температура, ах- вектор, характеризующий положение точки в пространстве, то закон распространения тепла можно сформулировать следующим образом: существует положительная скаляр ная величина к = к(х, Т), называемая коэффициентом теплопроводности материала и такая, что для любого распределения тепла плотность потока тепла равна: F(x,T) = -k(x,T(x,t))VT(x,t) или F = -fcVT. (1.2.3)
Физический смысл векторного поля F состоит в том, интеграл от нор мальной составляющей вектора F по какой-либо поверхности равен потоку тепла через эту поверхность в единицу времени. Закон (1.2.3) гласит, что для заданной температуры Т и заданной точки х вектор плотности потока тепла пропорционален градиенту температуры в этой точке и имеет про тивоположное направление. Коэффициент пропорциональности к может также зависеть и от времени, если происходят химические реакции.
Специальные матрицы и их свойства
Определение 11. Матрица А Є Rn,n с элементами а,;- называется: диагональной, если ац = О при і j; нижней (верхней) треугольной, если ац = 0 при j і (i j); нижней (верхней) унитреугольной, если она нижняя (верхняя) треугольная и а,ц = 1; ленточной, если а ;- = 0 при \ъ — j\ I, I п; нижней (верхней) хессенберговой, если a,-j = 0 при j і -f 1 (і j + 1); трехдиагональной, если a - = 0, при г — j\ 1; унитарной или ортогональной, если ЛГА = #, где JE7- единичная матрица;
Определение 12. Матрица называется разреженной, если большинство ее элементов равны нулю.
Определение 13. Портретом РА разреженной матрицы А называется множество пар индексов (i,j), таких что aij 0.
Определение 14. Матрица А Є Rn n с элементами ац называется матрицей со строгим диагональным преобладанием, если модуль диагонального элемента больше суммы модулей всех остальных элементов в строке.
Определение 15. Матрица А Є Rn n с элементами ац называется положительной (неотрицательной), если а 0 (ац 0), для Vi, j.
Определение 16. [54] Симметричная матрица А Є Rn,n линейного оператора А, называется полоэюительно определенной (положительно полу определенной), если для V#, кроме х = 0, (Ах,х) 0 (если для Ух (Ах,х) 0).
Определение 17. Матрица А называется симметричной, если А = А и кососимметричной, если А = —А Любую матрицу А можно представить в виде A = AQ + А\, где Ло -симметричная матрица, а А\ - кососимметричная матрица.
Определение 18. [86] Матрица А называется диссипативной, если ее симметричная составляющая положительно определена.
Определение 19. Матрица А Є Rn,n называется М-матрицей, если она невырожденная, а 0 при і ф j и обратная матрица А-1 поэлементно неотрицательна.
Определение 20. Матрица М Є Rn n называется матрицей сравнения матрицы А 6 Rn n, если тц = \сщ\ і = 1,..., п, т,;- = — аг-;- і = 1,...,п іфз Определение 21. Матрица А Є Rn,n называется Н-матрицей если ее матрица сравнения является М-матрицей.
Определение 22. Матрица обладает свойством-А, если она диагональная или существует матрица перестановок Р, такая что PAP =(Dl Л, \С D2J где Di,D2 - невырожденные диагональные матрицы необязательно одного порядка.
Определение 23. Скалярным произведением в называется отображение (, ): V х V — R, удовлетворяющее слудующим аксиомам: а) (Я У) = (У»Я); b) (x + y,z) = (x,z) + (y,z); c) (ах,у)=а{х,у); d) (x,x) 0; если (x,x) = 0, то x — 0. Вещественное n-мерное векторное пространство со скалярным произведением называется Евклидовым.
Пусть линейный оператор А, заданный соответствующей матрицей, действует в пространстве Rn. Тогда скалярное произведение в нем п 1=1 Если матрица А - симметричная и положительно определенная, тогда можно ввести скалярное А-произведение: (Х,У)А = (Ах,у) = (х, Ату) = утАх = хтАту.
Определение 24. [58, 54] Векторной нормой для данного линейного пространства V называется функция : V — R+, такая, что для Vrc, у Є V а) И 0, \\х\\ = 0&х = 0; b) 1М1 = М1М; c) + у 1М1 +
Наиболее часто используются следующие векторные нормы: жІ2 = у/(х,х) = уХл=1 \ХІ\ - евклидова норма; жоо = тахж - /«з норма; IWIi - E"=i Ы - і норма. Так же мы будем использовать А-норму: \\х\\А = у/(х, х)А = VxTAx Линейное пространство называется Гильбертовым, если в нем введено скалярное произведение, а норма определяется как квадратный корень из скалярного квадрата.
Определение 25. [58, 54] Нормой матрицы называется функция : Rn n — R+ со следующими свойствами: a) Л 0, \\А\\ = 0&х = 0; b) И = СИ; c) А+В М + В. Определение 26. [58, 54] Пусть - векторная норма, определим матричную норму формулой: U = max \\Ах\\ x=i" " Такая норма называется подчиненной, или операторной или индуцированной по отношению к векторной норме . Определение 27. [58, 54] Векторная норма а и матричная норма Н называются согласованными, если выполняется неравенство Лжа ИІ/М. Операторная норма является согласованной с векторной нормой. Обычно используют следующие нормы.
Метод симметрического и кососимметрического расщепления
Еще один способ решения сильно несимметричных систем линейных уравнений, метод симметрического и кососимметрического расщепления HSS (Hermtian/skew-Hermitian splitting method), был предложен Голубом (Golub) и Баи (Bai) [79]. Для решения системы использовалось кососимметричной составляющих. А = Ан + As t где Ан = \(А + АТ), As = \(А - Ат). Каждый шаг метода состоит из двух шагов: {aE + AH)xk+1/2 = {aE-As)xk + b, (o.Z.ll (аЕ + As)xk+i = (аЕ - Ан)хш/2 + Ь, где а - итерационный параметр. Метод аналогичен методу переменных направлений, для решения уравнений в частных производных [107]. В работе [79] приведено достаточное условие сходимости метода и приблизительные оценки для выбора итерационного параметра. Для каждой итерации стандартное представление матрицы в виде суммы симметричной и требуется точное решение системы такого же порядка, что и исходная матрица, с матрицами аЕ + As и аЕ + Ан Для вычислительного процесса это достаточно дорого, поэтому авторами предложено использовать метод сопряженных градиентов для решения системы с симметричными коэффициентами и любой другой метод пространства Крылова для решения системы aE+As- Этот метод называется неявным методом симметрического и кососимметрического расщепления IHSS (inexact Hermtian/skew-Hermitian splitting method). Данный вариант ускорения метода является нестационарным итерационным процессом, так как количество итераций на каждом внутреннем шаге может быть различным и изменяться в зависимости от внешнего шага.
Еще один метод решения сильно несимметричных систем линейных алгебраических уравнений был предложен Крукиером Л.А. в 1979г [19]. Его главной отличительной чертой является то, что в качестве обращаемых матриц берется треугольная часть кососимметричной составляющей исходной системы. Такой подход позволил получить класс итерационных методов, которые имеют достаточно простую структуру и в то же время предназначены для эффективного решения именно сильно несимметричных систем. Вычисление кососимметричной составляющей исходной матрицы не требует большого количества операций и предварительных аналитических действий. В большинстве случаев она получается явно еще при построении дискретной модели и ее использование в обращаемом операторе метода позволяет учесть структуру изменений именно этой части матрицы. Это особенно важно, когда кососимметрическая часть матрицы преобладает. Единственным ограничением этих методов является требование диссипа-тивности исходной матрицы.
Позднее были предложены попеременно-треугольный [20, 21], двуциклический [26, 48, 50] и двухпараметрический треугольный и попеременно-треугольный кососимметрические методы, метод кососимметрического треугольного расщепления [124], а так же их модификации не содержащие итерационного параметра [87, 5]. Для всех методов были получены условия сходимости, предложены способы выбора оптимального параметра [18, 86, 60]. Для данного класса методов были разработаны процедуры ускорения, использующие специальный выбор диагональной составляющей метода [17, 49, 25]. Данные идеи являются базовыми для предлагаемых переобуславливателей, поэтому рассмотрим их подробнее.
Вернемся к системе линейных алгебраических уравнений (1.5.8). Без потери общности, будем считать, что Diag(A) = Е, (3.3.1) здесь и далее Е обозначает единичную матрицу. Для решения системы (1.5.8) используется неявная двухслойная итерационная схема, записанная в канонической форме (2.2.3).
Известно [8], что любой линейный оператор (матрицу) можно представить в виде суммы симметричного и кососимметричного операторов (матриц), причем это представление единственно. Оператор А из (2.2.3) представим следующим образом A = A0 + Ah (3.3.2) где (3.3.3) А0 = ±(А + АТ) и АХ = \(А-АТ). Здесь AQ - симметричная матрица, А\ - кососимметричная. Представим кососимметричную часть А\ матрицы А в виде (3.3.4) где KL И Кц строго нижне- и верхнетреугольная матрицы соответственно. Очевидно, что KL = -Kl (3.3.5) Аналогично можно представить оператор В в виде суммы его самосопряженной и несамосопряженной частей.
Описание интерфейса с пользователем
Кнопка "Отправить" отправляет задачу с указанными параметрами на счет или добавляет в очередь. При успешном выполнении операции появляется стандартное окошко с уведомлением.
Полученные от пользователя данные через HTTP-запрос передаются на сервер, где после их анализа запускается соответствующая счетная программа.
Следующая HTML-форма называется "Задачи на сервере", на нее можно попасть выбрав соответствующую ссылку меню в верхней части страницы. Здесь отображаются и те задачи, которые в данный момент выполняются и те, которые находятся в очереди (Рис. 4.4). Список задач выдается в виде таблицы с полями: номер задачи; статус задачи (выполняется или в очереди); время добавления (отображается дата и время, когда задача была отправлена на счет); Ре (число Пекле); v (вектор скорости); размер сетки; метод (итерационный метод, используемый для расчета); переобуславливатель (переобуславливатель, используемый для ускорения итерационного метода); параметр (параметр выбранного переобуславливателя, если есть); итерация (номер итерации на момент обновления); невязка (величина логарифма отношения невязок на момент обновления); удалить (нажатие на крестик удаляет соответствующую задачу).
Интервал обновления выбирается пользователем из выпадающего списка над таблицей. Обновление может происходить автоматически через 5, 10, 30 секунд, 1 минуту, 10 минут или в ручную, после нажатия кнопки "Обновить".
На третьей странице "Готовые задачи" отображается список последних выполненных задач и реализована возможность поиска нужной задачи из множества всех посчитанных задач (Рис. 4.5). Список готовых задач выдается в виде таблицы с полями: номер задачи; время добавления; Ре; размер сетки; метод; переобуславливатель; число итераций (номер итерации на которой достигнута требуемая точность); длительность (время, затраченное на выполнение расчета); текстовый файл и график (в соответствующие ячейки помещены две пиктограммы при нажатии на которые появляется либо текстовый файл, в который занесены параметры и результаты расчета (Рис. 4.6) либо запускается программа GnuPlot в которой на основании этого текстового файла строится график зависимости номера итерации от логарифма отношения невязок (Рис. 4.7)).
На этой же HTML-странице реализован поиск готовых задач. Он осуществляется среди всех задач, посчитанных пользователем. Отбор задач происходит по дате; числу итераций затраченному времени числу Пекле Ре; размеру сетки; вектору скорости гг, итерационному методу; переобуславливателю;
Пользователь может заполнить любые из перечисленных выше полей. Если поле не заполнено, считается, что соответствующее ему значение может быть любым. Кнопка "Отобрать" отправляет полученные от пользователя данные через HTTP-запрос на сервер, где они анализируются, а результаты заносятся в таблицу готовых задач (Рис. 4.8).
Похожие диссертации на Использование эффективных переобуславливателей для численной реализации математических моделей конвективно-диффузионного переноса
