Балансные разностные методы решения трехмерных краевых задач тема автореферата и диссертации по математике, 01.01.07 ВАК РФ

Российская академия наук Сибирское отделение Вычислительный центр

На правах рукописи УДК 519.968

Туракулов Азамбек Абдуллаевич

Балансные разностные методы решения трехмерных краевых задач

01.01.07 - вычислительная математика

Автореферат

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

Новосибирск - 1994

Работа выполнена в Новосибирском государственном университете

Научный руководитель — доктор физико - математических

наук, профессор Ильин В.П.

Официальные оппоненты — доктор физико-математических

наук, профессор Мацокин A.M. / кандидат физико-математических

наук Слепцов А.Г.

Ведущая организация — Институт гидродинамики СО

РАН.

Защита состоится 23 февраля 1994 г. в /л?.; час. на заседании специализированного совета К 002.10.01 по присуждению ученой степени кандидата физико -математических наук в Вычислительном центре СО РАН по адресу: 630090, Новосибирск 90, просп. Академика

Лаврентьева, 6 С диссертацией можно ознакомиться в читальном зале библиотеки ВП СО РАН (пр. Академика Лаврентьева, 6).

Автореферат разослан 1994 г.

Ученый секретарь Специализированного совета, доктор физико- / /

-математических наук } / / Ю. И. Кузнецов.

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

Актуальность темы. Метод конечных разностей решения задач математической физики является одним из самых распространенных и развитых в области вычислительной математики. В основе этого метода лежит переход от непрерывной среды к некоторой ее дискретной модели — множеству точек, которое обычно называют сеткой. Решение задачи 'ищется только в точках этого множества, называемых узлами сетки. При таком переходе естественно требовать, чтобы разностные схемы (совокупность уравнений, аппроксимирующих исходную задачу) выражали в узлах сетки соответствующие интегральные законы сохранения, которыми характеризуются различные физические процессы. Разностные схемы с таким свойством называются консервативными [1,2].

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

В результате применения балансных методов (интегро-интерполяционный метод [2}, метод контрольных объемов [3], метод конечных объемов [4], "Ьох"-метод [5] и др.) почти всегда получаются консервативные схемы. Но эти методы, к сожалению, мало изучены в многомерном случае. Развитие таких методов и их применение к решению различных трехмерных задач математической физики является одной из немаловажных целей вычислительной математики.

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

для машинной реализации некоторых предложенных алгоритмов.

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

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

Апробация работы. Результаты диссертации неоднократно докладывались и обсуждались в объединенных семинарах кафедры вычислительной математики НГУ и ВЦ СО РАН.

Публикации. Основные результаты диссертации опубликованы в работах [7] - [10].

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

II. Краткое содержание работы.

Диссертационная работа состоит из введения, трех глав и заключения.

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

Первая глава состоит из двух параграфов и посвящена вопросу разбиения многомерных областей на конечные объемы.

В §1.1 описывается алгоритм разбиения п-мерных замкнутых областей с кусочно-гладкими границами.

Пусть задано множество Р = {Р1,Р2,Р3, ...,Рлг},.№ > п + 1, точек внутри некоторой ограниченной замкнутой области Г2 С Ип.

Введем в К" прямоугольную декартову систему координат и обозначим через </(Р;, Р;) евклидово расстояние между точками Р; и Ру.

гдеp,k и Pjk,k = 1 ,п- координаты точек Р, и Pj соответственно.

Определение 1. Ячейкой Дирихле (или многоугольником Вороного), связанной с точкой Pj относительно множества точек Р, называется область

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

Определение 2. Ячейки Дирихле, удовлетворяющие условию Д- Л П = D¡, называются внутренними, а остальные - околограничными.

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

А={1€ R" : d(X,Pi) < d(X,Pj),j = l,n}

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

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

Рассмотрим алгоритм определения вершин ячейки Дирихле для точки Р0 € Р. Пусть Р; € Р,г = 1,п + 1 - близкие к Ро точки, не лежащие на одной плоскости, и многогранник, образованный из этих точек, содержит внутри себя точку Р0. Определим вершины ячейки Дирихле относительно выбранных точек следующим образом:

— соединим точки Р0 и Р,,г = 1,п+ 1, отрезками прямых;

— проведем гиперплоскости, перпендикулярные к этим отрезкам и проходящие через их середины;

— определим их точки пересечения.

Найденные п +1 точки составляют вершины п-симплекса, который является ячейкой Дирихле относительно выбранных точек Р{, { — 1,п + 1.

Далее, построим п-мерные гиперсферы с центрами на вершинах полученной ячейки и радиусами, равными расстояниям от вершин до точки Р0. Если эти гиперсферы содержат внутри себя точки множества Р, отличные от ранее выбранных Р;,г = 1,п+ 1, то корректируем полученную ячейку следующим образом. Пусть Рк,к = п + 2, ...,п + 1 + К, точки, лежащие внутри гиперсфер. Определим вершины ячейки по следующему алгоритму:

— соединим точки Ро и Р*, к — п + 2,..., п + 1 + К, отрезками

прямых;

— проведем гиперплоскости, перпендикулярные к этим отрезкам и проходящие через их середины;

— определим точки пересечения всевозможных сочетаний по п + 1 из всех п + 1 + К гиперплоскостей;

— исключим из набора полученных точек те вершины первоначальной ячейки, соответстующие гиперсферы которых не пусты(так как они не могут быть вершинами новой ячейки);

— определим точки из набора, которые лежат в одном полупрострнстве относительно всех n+1+K гиперплоскостей.

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

Теорема 1.1. Пусть U - замкнутая область, ограниченная п-мерным многогранником, V - множество его вершин, О - произвольная точка пространства, S(X) - n-мерный шар, с центром в точке Х{х1,х2,—,хя), содержащий точку О на своей поверхности. Тогда

U 5wc U

хе и xzv

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

Теорема 1.2. Пусть (I - n-мерная замкнутая область с кусочно -гладкой границей, Р — {Р\, Рг> •••! Pn} — множество точек, заданных в ней. Тогда разбиение Вороного области Я, связанное с множеством Р, можно построить, потратив 0(JVlogB_1 N) логических (сравнение двух действительных чисел), 0(nM+iN) арифметических, 0(nN) функциональных (извлечение из квадратного корня) операций, где М — постоянная, не зависящая от количества точек N.

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

В §1.2 предлагается алгоритм локальной модификации параллелепипедоидальной сетки.

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

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

Теорема 1.3. Разбиение Вороного, связанное с узлами локально -

модифицированной сетки, можно построить за время 0{Ы — + 1+1

использовав для этого память обеемом О(Ы) + 1) + 0(№) без предварительной обработки множества узлов, где N1 — количество "нестандартных" узлов сетки.

"Нестандартными" называются узлы, для которых первичные элементарные ячейки не являются ячейкой Дирихле.

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

Пусть требуется найти функцию и(х,у,г), удовлетворяющую уравнению

- = О,

в некоторой ограниченной области Об Д3 с кусочно-гладкой границей Г = Г1 и Г2, на различных частях которой задано одно из краевых условий

и 91(х,у,г), (2)

яПд|г 1=92(х,у,г). (3)

о тг

Функция А(х,р,г) предполагается кусочно-постоянной для различных подобластей из П. На границах Гз разделов сред задаются условия сопряжения

" !г?= " 1г3-> (4)

где знаки "+" и относятся к разным подобластям.

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

В §2.1 рассматривается аппроксимация уравнения (1) и граничных условий (2) - (4) с помощью ячеек Дирихле, построенных в §1.2.

Получаемая система разностных уравнений

= Д (5)

в "стандартных" узлах сетки, где ячейки Дирихле регулярные, аппроксимирует задачу (1) - (4) с погрешностью 0{Ь?) на равномерной, 0{к) — на неравномерной первоначальной сетке. Граничные условия (3) и (4) удовлетворяются автоматически, но при этом в предположении того, что участки границы, где заданы эти условия, состоят из плоскостей, параллельных координатным, погрешность аппроксимации будет 0{Н) как для равномерной, так и для неравномерной первоначальной сетки. А участок границы, где задано условие

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

Для погрешности решения = (и)/, - v^¡, где (и)/, — проекция функции и на сетке, справедлива следующая оценка в равномерной норме.

Теорема 2.1. При сделанных выше предположениях погрешность решения полученной балансной разностной задачи есть величина 0(Ь), где И, — максимальный из всех шагов сетки.

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

Рис.1

Объединения соответствующих частей тетраэдров, для которых данный узел является общей вершиной, образуют некоторые ячейки. Система разностных уравнений типа (5) получается путем интегрирования уравнения (1) по объему

*

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

В частном случае, когда точки ф ь С^, фз, Q^ (см. рис.1) расположены в центрах тяжестей граней тетраэдра, а точки Ль Лг, Лз, Л4, Л5, Лб лежат на серединах его ребер, локальные матрица баланса и матрица жесткости в известном методе конечных элементов совпадают. Если точка О выбирается в барицентре тетраэдра, то совпадают и вектора правых частей соответствующих систем линейных алгебраических уравнений.

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

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

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

Третья глава посвящена особенностям программной реализации некоторых предложенных алгоритмов на ЭВМ. Глава состоит из трех параграфов.

В §3.1 приводится общая схема организации программы, что изображена на рис.2.

Управляющей программой модули вызываются с следующем порядке: модуль обработки геометрии области; модуль локальной модификации сетки; модуль формирования

Рис.2

коэффициентов системы разностных уравнений; итерационы-ый модуль.

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

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

В §3.3 подробо описываются принципы работы основных модулей в последовательности их выполнения при работе

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

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

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

/. Разработан алгоритм построения ячеек Дирихле в Л". Приведена асимптотическая оценка количества операций.

2. Разработан алгоритм локальной модификации трехмер-

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

3. Предложен алгоритм дискретизации трехмерных краевых

задач для уравнения Пуассона на разбиении Вороного. Получена оценка погрешности решения.

4. Предложен алгоритм аппроксимации таких же краевых

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

5. Разработаны программные модули для машинной реали-

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

Литература

1. Марчук Г.И. Методы вычислительной математики. -М.:

Наука, 1977.

2. Самарский А.А. Введение в теорию разностных схем. -М.:

Наука, 1971.

3. Андерсон Д. Вычислительная гидромеханика и теплооб-

мен. -М.: Мир, 1990, т.1.

4. Cai Z. On the finite volume element method // Numer. Math. -

1991, -Vol.58, pp. 713-735.

5. Hackbush W. On first and second order box schems // Computing.

-1989. -Vol.41, pp.277-296.

6. Лаевский Ю.М. Построение системы m-мерных барицен-

трических множеств. //В сб. "Численные методы и математическое моделирование". -Новосибирск, 1990. -С.112-120.

7. Юдин А.Н., Ильин В.П., Туракулов A.A. Быстрая аппрок-

симация уравнения Пуассона в трехмерных областях на модифицированной сетке. //В сб. "Вычислительный эксперимент в задачах математической физики". -Новосибирск, 1991. -36с.

8. Ильин В.П., Туракулов A.A. Об интегро-балансных ап-

проксимациях трехмерного уравнения Пуассона. -Новосибирск, 1993, -22с. (Препринт /РАН. Сиб. отд-ние. ВЦ 986).

9. Туракулов A.A. Об одном алгоритме построения ячейки

Дирихле в Rn. -Новосибирск, 1993, -19с. (Препринт /РАН. Сиб. отд-ние. ВЦ 1005).

10. Туракулов A.A. Программная реализация метода конеч-

ных объемов для решения трехмерного уравнения Пуассона. -Новосибирск, 1993, -30с. (Препринт /РАН. Сиб. отд-ние. ВЦ 1009).

Работы автора по теме диссертации