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

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

Захаров Петр Егорович

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

Специальность: 05.13.18 - Математическое моделирование, численное методы и комплексы программ

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

005541101 28ИОЯ2Ш

Якутск 2013

005541101

Работа выполнена на кафедре прикладной математики и в Центре вычислительных технологий Института математики и информатики Северо-Восточного федерального университета имени М. К. Аммосова

Научный руководитель: Вабищевич Петр Николаевич,

доктор физико-математических наук, профессор

Официальные оппоненты: Поляков Сергей Владимирович,

Защита состоится 20 декабря 2013 г. в Ю00 часов на заседании диссертационного совета Д 212.306.04 при Северо-Восточном федеральном университете имени М. К. Аммосова, расположенного по адресу: 677000, г. Якутск, ул. Белинского 58, зал заседаний Ученого совета.

С диссертацией можно ознакомиться в научной библиотеке Северо-Восточного федерального университета имени М. К. Аммосова. Автореферат разослан 19 ноября 2013 года.

доктор физико-математических наук, профессор, заведующий сектором Института прикладной математики им. М.В. Келдыша РАН, г. Москва Старостин Николай Павлович, доктор технических наук, профессор, заведующий лабораторией Института проблем нефти и газа СО РАН, г. Якутск

Ведущая организация: Институт вычислительной математики и

математической геофизики СО РАН

Ученый секретарь диссертационного совета, д.ф.-м.н.

Саввинова Н.А.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• Международная конференция International Conference on Domain Decomposition Methods (Швейцария, г. Лугано, 2013 г.);

• Международная конференция Суперкомпьютерные технологии математического моделирования (РФ, г. Якутск, 2013 г.);

• Международная конференция Суперкомпьютерные технологии математического моделирования (РФ, г. Якутск, 2011 г.);

• Международная конференция International Young Scientists Conference on Mathematical Modeling (КНР, г. Линьи, 2010 г.);

• Всероссийская конференция Математическое моделирование развития северных территорий Российской Федерации (РФ, г. Якутск, 2009 г.).

Диссертационная работа была выполнена при поддержке грантов:

• Грант ФЦП №2009-1.1-224-010-015 Научные и научно-педагогические кадры инновационной России на 2009-2013 гг., в рамках реализации мероприятия 1.1 Проведение научных исследований коллективами НОЦ, работа Разработка симуляторов экологически безопасных технологий разработки и мониторинга месторождений полезных ископаемых Арктики и регионов Севера;

• Государственный заказ Министерства образования РФ №5542 Разработка прикладного ПО для численного моделирования добычи углеводородного сырья на высокопроизводительных вычислительных системах.

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

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

Объем и структура работы. Диссертация состоит из введения, трех глав, заключения и литературы. Полный объем диссертации 132 страниц текста с 89 рисунками и 2 таблицами. Список литературы содержит 108 наименование.

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

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

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

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

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

(1)

где

Ва = Е + <ттхаА, а =1,2,

(2)

с правой частью определенной в форме (рп = /(<т^+1 + (1 — сг)Ьп).

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

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

гп{х) = уп(х) - ип(х), хеш, где ип(х) = и(х, £п) точное решение дифференциальной задачи.

Рис. 1: Зависимость погрешности факторизованной схемы от шага по времени

при <7 = 1.

Теорема 1. Для погрешности факторизованной регионально-аддитивной разностной схемы (1), (2) при а > 0.5 для задачи имеем место оценка

\\В^п+1\\А < М(/г2 + г2 + {а - 0.5)т + а2т2\\АХ2\\А)- (4)

0.1 0.01 0.001

« 0.0001 1е-05 1е-06 1е-07

1е-07 1е-06 1е-05 0.0001 0.001 0.01

т

Рис. 2: Зависимость погрешности факторизованной схемы от шага по времени

при а = 0.5.

Дается сравнение результатов численных экспериментов при использовании различных схем декомпозиции области. Для выявления асимптотической зависимости погрешности от параметров задачи, вычисления проводились в большом диапазоне параметров. Например, на рис. 1, 2 представлены данные по точности (погрешность £ в Ь'Дш)) в зависимости от шага по времени т при различном числе подобластей (параметр К) для факторизованной схемы при а = 1 (рис. 1) и а = 0.5 (рис. 2). Полученные результаты погрешности решения для регионально-аддитивной факторизованной схемы соответствуют теоретической оценке.

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

к = 1,0е+00

подобластей

m

а = U na.

а=1

Каждое множество подобластей fla состоит из р отдельных подобластей:

v

0<*=|Jfi£, а =1,2,..., m,

/3=1

П*ЛПЛ = 0, Ат^А, 1 < А, А <Р, а = 1,2,...,т.

Тогда для каждого множества подобластей Î2a решаем р отдельных подзадач.

Декомпозиция разностной схемы строится на основе разбиения единицы для области fi:

( > 0, х е па, Ра{ х)=< а = 1,2,..., то, (5)

I О, х g fia,

где

^2ра(х) = 1, аз Є fi. (6)

Рассматривается класс схем декомпозиции области, в которых оператор А имеем следующее аддитивное представление:

тп

А = Х)А»> (7)

а=1

где каждый оператор Аа, а = 1,2, ...,т связан с множеством подобластей Па и разбиением (5), (6). Сравниваются три основные типа операторов декомпозиции:

Аа = раА,

Аа = Ара, А„ = А1'2 раА1'2, а = 1,2,.., р.

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

схема в общем виде рассматривается как факторизованная схема. Для сравнения дополнительно рассмотрены симметричная схема покомпонентного расщепления. Предложена факторизованная схема, для которой расщепление (7) не имеет места:

п+1 _ п

ВгВ2и--— + Ауп = (рп, (8)

т

в которой

Ва = Е + атАа, а = 1,2, (9)

Аі = Ар, А2 = (1-р)А, А^А!+А2, 0 < р < 1. (10)

10° Ю-1 ю-2 10"3 ю-4 ю-5

10'3 Ю"2 Х0'1 10°

I,

Рис. 3: Зависимость нормы погрешности факторизованных схем от шага по пространству для различных операторов декомпозиции.

Характерный результат проведенных численных экспериментов приведен на рис. 3. Здесь для модельной параболической задачи показана зависимость точности различных схем декомпозиции с минимальным наложением подобластей от расчетной сетки (шага К).

\

ч.ч

\ - ........... ....../.............: // — Explicit -- Implicit — АР„ -..... Р«А — G'paG

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

В третьей главе рассматривается прикладная задача смачивания грунта на примере увлажнения земляной плотины с противофильтрационным экраном (рис. 4). Для численного моделирования физического процесса строятся математи-

Рис. 4: Границы и подобласти земляной плотины с противофильтрационным

экраном.

Движение влаги в зоне аэрации происходит по законам ненасыщенной

фильтрации, которая описывается уравнением Ричардса

д3

т— - сИу grad(pc - рдг)) = 0, (11)

где т - пористость среды, в - доля водонасыщенности, к(з, х) - водопроницаемость, рс - капиллярное давление, р - плотность жидкости, д - ускорение свободного падения, г — вертикальная координата (г = х2 в двумерном случае и г = Хз — для трехмерного). Для решения задачи ненасыщенной фильтрации, уравнение (11) дополняется зависимостью доли воды от капиллярного давления

з(рс) = 1 - ехр(-арс), (12)

12

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

к(з) = к3за, (13)

где кв - водопроницаемость для насыщенной фильтрации, а - эмпирический параметр. Подставив формулу (12) в (13) получим зависимость водопроницаемости от капиллярного давления.

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

- сИу (к, grad(р - рдг)) = 0, (14)

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

др

те'— - с1пг(£ - рдг)) = 0, (15)

где рс = р — ра, а ра - атмосферное давление.

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

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

Рис. 5: Движение границы насыщенного грунта в 1-й, 2-й, 3-й день. Черная линия - без противофильтрационного экрана, белая - с экраном.

Рис. 6: Двухкомпонентная декомпозиция вычислительной сетки на 4 подобласти.

Рис. 7: Границы водонасьнценных зон в 1-й день решения факторизованной (серый) и неявной (черный) схемой.

Рис. 8: Границы водонасьнценных зон в 2-й день решения факторизованной (серый) и неявной (черный) схемой.

Рис. 9: Границы водонасыщенных зон в 3-й день решения факторизованной (серый) и неявной (черный) схемой.

Рис. 10: Границы водонасыщенных зон в 30-й день решения факторизованной (серый) и неявной (черный) схемой.

Основные результаты работы:

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

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

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

Публикации автора по теме диссертации

1. Захаров П. Е. Параллельные алгоритмы разделения области для параболической задачи / Захаров П. Е. // Мат. заметки ЯГУ. 2013. Т. 20, № 2. С. 256-270.

2. Захаров П. Е. Параллельное численное моделирование процесса заводнения нефтяного месторождения / Афанасьева Н. М., Васильева М. В., Захаров П. Е. // Математические заметки ЯГУ. 2011. Т. 18, № 1. С. 159172.

3. Захаров П. Е. Разработка пакета вСоге для численного моделирования на вычислительных кластерах / Борисов В. С., Вабищевич П. Н., Васильев В. И., Васильева М. В., Захаров П. Е., Казаков В. А. // Вестник ЦКР Роснедра. 2012. № 2. С. 36-39.

4. Zakharov P. E. Domain Decomposition Scheme for First-Order Evolution Equations with Nonselfadjoint Operators / Vabishchevich P. N., Zakharov P. E. // Numerical Solution of Partial Differential Equations: Theory, Algorithms, and Their Applications. Springer Proceedings in Mathematics & Statistics. 2013. Vol. 45. P. 279-302.

5. Zakharov P. E. Domain decomposition schemes without overlapping for parabolic problems / Zakharov P. E. // Тез. докл. Международной конференции: Суперкомпьютерные технологии математического моделирования. 2013. С. 76.

6. Захаров П. Е. Библиотека SCore для численного моделирования на высокопроизводительных вычислительных системах / Васильева М. В., Захаров П. Е. // Труды международных конференций по математическому моделированию / Под редакцией В.И. Васильева. 2012. С. 295-307.

7. Захаров П. Е. Реализация безитерационного метода декомпозиции области для параболической задачи / Захаров П. Е. II Тез. докл. Международной конференции: Суперкомпьютерные технологии математического моделирования. 2011. С. 80.

8. Захаров П. Е. Параллельное программирование на основе библиотек: учебн / Григорьев А.В., Васильева М.В., Захаров П. Е. П Якутск: Издательско-полиграфический комплекс СВФУ. 2011. 94 с.

9. Zakharov P. Е. Numerical solution of single phase flow in porous media using conjugate gradient method on graphics processors / Zakharov P. E. // Тез. докл. International Young Scientists Conference on Mathematical Modeling. 2010. C. 82-84.

10. Захаров П. E. Параллельный алгоритм реализации математической модели вытеснения нефти водой / Захаров П. Е. // Тез. докл. Математическое моделирование развития северных территорий. 2009. С. 38-39.

11. Захаров П. Е. Расчет потокораспределения в инженерных сетях / Захаров П. Е., Павлов H.H. // Математические заметки ЯГУ. 2007. Т. 14, № 1. С. 130-137.

МЕДОТЫ ДЕКОМПОЗИЦИИ ОБЛАСТИ ДЛЯ РЕШЕНИЯ НЕСТАЦИОНАРНЫХ ЗАДАЧ УВЛАЖНЕНИЯ ГРУНТА

АВТОРЕФЕРАТ

Подписано в печать 18.11.13. Формат 60x84/16. Гарнитура «Тайме». Печать офсетная. Печ. л. 1,25. Уч.-изд. л. 1,5. Тираж 100 экз. Заказ № 359 Издательский дом Северо-Восточного федерального университета, 677891, г. Якутск, ул. Петровского, 5.

Отпечатано в типографии ИД СВФУ

Министерство образования и науки Российской Федерации Северо-Восточный федеральный университет имени М. К. Аммосова

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

Захаров Петр Егорович

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

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

ДИССЕРТАЦИЯ на соискание учёной степени кандидата физико-математических наук

Научный руководитель: д. ф.-м. н., профессор Вабищевич Петр Николаевич

Якутск 2013

Содержание

Введение 4

1 Методы декомпозиции без налегания подобластей 13

1.1 Модельная задача........................................................13

1.1.1 Постановка задачи ..............................................13

1.1.2 Аппроксимация по пространству..............................15

1.1.3 Схема с весами..................................................16

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

1.2 Декомпозиция явной схемы..............................................21

1.2.1 Параллельный алгоритм........................................21

1.2.2 Сложность алгоритма............................................22

1.2.3 Эффективность параллельного алгоритма....................23

1.3 Явно-неявные схемы ....................................................26

1.3.1 Явно-неявная схема с коррекцией..............................26

1.3.2 Факторизованная схема..........................................27

1.3.3 Сходимость......................................................28

1.3.4 Численные эксперименты......................................30

2 Методы декомпозиции с налеганием подобластей 36

2.1 Модельная задача........................................................36

2.1.1 Постановка задачи ..............................................36

2.1.2 Аппроксимация по пространству..............................38

2.1.3 Схема с весами..................................................39

2.1.4 Операторы декомпозиции ......................................41

2.2 Двухкомпонентная декомпозиция......................................43

2.2.1 Схема Дугласа-Рэкфорда........................................43

2.2.2 Факторизованные схемы........................................44

2.2.3 Сходимость факторизованных схем............................46

2.2.4 Точность факторизованных схем ..............................48

2.2.5 Симметричная схема покомпонентного расщепления .... 56

2.2.6 Факторизованная схема с другими операторами..............59

2.3 Многокомпонентная декомпозиция....................................65

2.3.1 Схема покомпонентного расщепления........................65

2.3.2 Аддитивно-усредненные схемы................................71

2.3.3 Векторные аддитивные схемы..................................75

2.3.4 Асинхронные векторные схемы................................80

3 Моделирование увлажнения грунта 84

3.1 Двумерная задача увлажнения плотины................................84

3.1.1 Математическая модель ........................................84

3.1.2 Дискретизация....................................................86

3.1.3 Вычислительная реализация....................................88

3.1.4 Численное сравнение............................................90

3.2 Трехмерная задача увлажнения плотины..............................95

3.2.1 Математическая модель ........................................95

3.2.2 Дискретизация....................................................96

3.2.3 Вычислительная реализация....................................97

3.2.4 Численные результаты..........................................99

3.3 Схема декомпозиции области для задачи увлажнения........106

3.3.1 Схема декомпозиции......................106

3.3.2 Вариационная постановка...................107

3.3.3 Численное сравнение......................109

Заключение 116

Литература 117

Введение

В настоящее время сложилась новая технология научных исследований, которая базируется на исследовании прикладных математических моделей с помощью вычислительных средств (компьютеры и численные методы) [9, 17,32, 42,49,50,71,92]. Численное моделирование позволяет описать свойств исследуемого объекта с необходимой полнотой и детальностью на основе адекватных математических моделей.

Содержательные математические модели включают системы связанных друг с другом нестационарных нелинейных уравнений с частными производными, системы обыкновенных дифференциальных и алгебраических уравнений. Разработка вычислительных алгоритмов для прикладного математического моделирования базируется на глубокой теоретической и методической проработкой численных методов для базовых задач [23,51,61,68,75]. Для аппроксимации по пространству используются все основные технологии, связанные с разностной, конечно-объемной и конечно-элементной аппроксимацией [40,77,108]. Необходимо только иметь в виду, что, обычно, приходится решать задачи в многомерных областях со сложной геометрией. При приближенном решении нестационарных задач основное внимание должно уделяться разностным методам [24,36,46,52,54,57,62,72,78,84,93,95]. Проблемы применения конечно-элементных аппроксимаций при решении нестационарных задач обсуждаются в [47,96].

Теория численных методов решения краевых задач для уравнений с частными производными развивается в следующих основных направлениях:

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

• исследование устойчивости (корректности) разностной задачи;

• эффективная вычислительная реализация на современной вычислительной технике.

Исследование разностных схем для нестационарных задач базируется на использовании общей теории устойчивости (корректности) операторно-разностных

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

Расчетно-теоретическое исследование прикладных проблем требует решения задач в сложных многомерных областях, использования достаточно подробных расчетных сеток. Для нахождения приближенного решения приходится решать большие системы линейных или нелинейных алгебраических уравнений. С этой целью используются итерационные методы сеточных уравнений [24,30,79]. Особое внимание уделяется методам решения задач с несамосопряженными операторами.

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

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

мы ориентируемся на использование стандартных неявных аппроксимаций по времени и решение соответствующих сеточных задач на новом временном слое с использованием тех или иных вариантов методов декомпозиции области для стационарных задач. Учет особенностей нестационарных задач (смотри, например, реализацию на основе метода Шварца [38,39,48]) приводит к оптимальным итерационным методам декомпозиции области, когда число итераций не зависит от шагов дискретизации по времени и пространству.

Наиболее полно специфика нестационарных задач проявляется при использовании безитерационных методов декомпозиции области. Как отмечено в работах [64,65], в ряде случаев можно без потери точности приближенного решения ограничиться одной итерацией альтернирующего метода Шварца при приближенном решении краевых задач для параболического уравнения второго порядка. Безитерационные схемы декомпозиции области не обеспечивают близости приближенного решения к решению, которое получено с использованием стандартных неявных аппроксимаций. Поэтому безитерационные схемы естественно связать с теми или иными вариантами аддитивных схем (схемами расщепления), которые названы регионально-аддитивными схемами [80].

Различные схемы декомпозиции области для решения нестационарных краевых задач для уравнений с частными производными можно классифицировать по:

• способу декомпозиции области,

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

• используемой схеме расщепления.

При решении краевых задач для дифференциальных уравнений с частными

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

р

па = паидпа, а = 1,2 (1)

а=1

с налеганием подобластей = 0,а П Пр ф 0) и методы без налегания подобластей (ПаР = 0) [76,97].

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

С декомпозицией области (1) мы можем сопоставить соответствующее аддитивное представление оператора задачи

р а=1

В этом случае каждый отдельный оператор Ла связывается с решением некоторой задачи в своей подобласти Па, а = 1,2Наиболее общий подход для построения операторов декомпозиции при решении краевых задач для уравнений с частными производными базируется на использовании понятия разбиения единицы для расчетной области.

При декомпозиции (1) с отдельной подобластью £1а свяжем функцию г}а(х), а = 1,2, ...,р такую, что

| > 0, х <Е С1а,

Г)а(х) = < а = 1,2 ,...,р, (3)

^ 0, х ф

причем

р

Х>а(®) = 1, хеП. (4)

а=1

Рассмотрим характерный пример. Пусть, например, оператор задачи А есть оператор диффузии:

Л = — сНу к(х) grad, х £ О,. (5)

Тогда для операторов декомпозиции можно задать следующим три основные конструкции:

Аа = 77« Л, (6)

А* = - к{х)г]а(х) grad, (7)

Лп=Лг](у, а = 1,2,...,р. (8)

Эта общая технология используется начиная с работ [20,22,66] (декомпозиция (7)), [7] (декомпозиция (6)-(8)), результаты более поздних работ суммированы в книгах [31,80]. Различные варианты операторов декомпозиции соответствуют использованию различных обменных граничных условий и обеспечивают сходимость приближенного решения в разных пространствах сеточных функций. Отдельного внимания заслуживают вопросы построения операторов декомпозиции при решении нестационарных задач с несамосопряженными операторами [6,27,82].

При построении регионально-аддитивных схем (схем декомпозиции области) для решения нестационарных задач на основе расщепления (2) используются различные схемы расщепления. В теории аддитивных операторно-разностных схем, схем расщепления [24,31,35,69] необходимо выделить случай простейшего двухкомпонентного расщепления. В этом простейшем случае строятся безусловно устойчивые факторизованные схемы расщепления, к которым, в частности, относятся классические схемы переменных направлений, схемы предиктор-корректор. Двухкомпонентные регионально-аддитивные схемы построены и исследованы в работах [7,8,66,67], а также в отмеченных выше работах [6,27,82] для задач конвекции-диффузии.

Для вычислительной практики, в том числе и при применении методов декомпозиции области, большой интерес представляет расщепление оператора задачи на сумму трех и более попарно некоммутативных операторов (р > 2 в (2)). Классические [24,35,69] схемы многокомпонентного расщепления строятся на основе понятия суммарной аппроксимации. Аддитивно-усредненные схемы суммарной аппроксимации [18,31] более явно ориентированы на параллельную организа-

цию вычислений. Регионально-аддитивные схемы покомпонентного расщепления исследуются в работе [12]. Вариант двухкомпонентного расщепления при использовании схемы Кранка-Николсона для отдельных подзадач при минимальном наложении и операторах декомпозиции (7) рассмотрен в статье [41].

В настоящее время получили распространение схемы полной аппроксимации для общего многокомпонентного расщепления. В этой связи отметим регуляри-зованные аддитивные схемы [28], в которых условия устойчивости достигаются за счет возмущений операторов разностной схемы. В векторных аддитивных схемах [1,5]. вместо одного уравнения решается система однотипных уравнений. Такие схемы строятся также для эволюционных уравнений второго порядка [2,81]. Векторные регионально-аддитивные схемы исследуются в работах [11,26]. Отметим также работу [99], в которой предложены более общие регуляризованные схемы декомпозиции области с различными конструкциями для операторов расщепления и для операторов сеточной задачи на новом временном слое.

Отдельного упоминания заслуживают явные схемы для нестационарных задач математической физики. Явные схемы имеют несомненные преимущества перед неявными в плане вычислительной реализации. Особенно это достоинство сильно проявляется при построении вычислительных алгоритмов, которые ориентированы на вычислительные системы параллельной архитектуры. Хорошо также известен основной недостаток явных схем, который связан с жесткими ограничениями на допустимый шаг по времени. Для параболических уравнений условие устойчивости [24,29] имеет вид г < то = 0(к2), где т — шаг сетки по времени, а к — шаг сетки по пространству.

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

ся проблемы с аппроксимацией. Дополнительный член погрешности для таких условно сходящимися схем есть 0(т2/гГ2).

Впервые явные схемы бегущего счета для параболических уравнений второго порядка предложены в книге [33]. С учетом организации явно-неявной неоднородности аппроксимаций по времени эти схемы названы автором asymmetric schemes. Следующий принципиальный результат получен A.A. Самарским в работе [25], где эти схемы рассматриваются как факторизованные операторно-разностные схемы с аддитивным расщеплением оператора задачи (матрицы) на сопряженные друг другу слагаемые. Применительно к системам обыкновенных дифференциальных уравнений мы имеем расщепление матрицы на нижнюю и верхнюю треугольные матрицы — ПТМ (попеременно-треугольный метод). При решении стационарных задач на основе таких расщеплений мы имеем попеременно-треугольный итерационный метод [30].

Более поздний этап использования явных схем бегущего счета при решении параболических краевых задач можно связать с работами [43,44]. С учетом возможностей организации вычислений выделяются явные схемы Group Explicit (Alternating Group Explicit) method. Активно (смотри, например, [105,106]) обсуждаются возможности рассматриваемых явных схем при построении вычислительных алгоритмов решения краевых задач для параболических уравнений на параллельных компьютерах. Отметим также работы по использованию явных схем бегущего счета для нестационарных задач конвекции-диффузии [45,102].

Среди других методов декомпозиции области при решении краевой задачи для параболических уравнений отметим явно-неявные методы, которые с небольшими вариациями рассматриваются во многих работах (смотри, например, [21,58-60,94,98,104,107]). Декомпозиция области проводится без наложения подобластей, и переход на новый временной слой организуется следующим образом. Сначала с использованием явной схемы делается прогноз приближенного решения на общих границах подобластей, после этого с этими граничными условиями находится приближенное решение внутри отдельных подобластей, на

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

Из приведенного обзора литературы можно сделать вывод, что существует достаточно большое многообразие регионально-аддитивных схем. Актуальной проблемой является не только построение каких-то новых схем декомп�