автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Вычислительная технология метода конечных объемов

« »* Г" Л 1

1 В МЛР 19РЯ

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

ГУРЬЕВА Яна Леонидовна

Вычислительная технология метода конечных объемов

05.13,11 - математическое и программное обеспечение вычислительных машин, комплексов, систем и сетей

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

Работа выполнена в Институте вычислительной математики и математической геофизики СО РАН.

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

доктор физико-математических наук профессор Ильин В.П.

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

доктор физико-математических наук профессор Мацокин A.M. доктор технических наук профессор Рычков А.Д.

Ведущая организация: Новосибирский государственный технический университет.

"Зашита состоится иилртги^ 1998 Г. в и ча-

сов на заседании диссертационного совета Д 002.10.02 в Институте вычислительной математики и математической геофизики СО РАН но адресу: Новосибирск, 630090, проспект Лаврентьева, 6, Институт вычислительной математики и математической геофизики.

С диссертацией можно ознакомиться в библиотеке Института вычислительной математики и математической геофизики СО РАН.

Автореферат разослан " б " с^е^Ь1998 г.

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

Г.И.Забиняко

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

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

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

Повсеместное применение ЭВМ с различным программным обеспечением и окружением привело к тому, что математическая постановка некоторого класса задач и программное обеспечение для его решения стали очень взаимосвязаны.

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

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

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

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

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

Апробация работы. Основные результаты диссертации докладывались на международной конференции АМСА-95 ("Современные проблемы прикладной и вычислительной математики"), г. Новосибирск, 1995; конференции молодых ученых Вычислительного Центра СО РАН, 1997; семинаре математического факультета Католического университета г.Неймегена (Нидерланды), 1997; научных семинарах Вычислительного Центра СО РАН.

Публикации. По тем« диссертации опубликовано пять работ.

Структура и объем работы. Диссертационная работа состоит m введения, трех глав, заключения, списка литературы и приложения. Объем работы - 123 машинописных страницы. Список литературы содержит 85 наименований.

СОДЕРЖАНИЕ РАБОТЫ

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

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

В §1.3 рассматривается этап аппроксимации вычислительной технологии МКО для двумерного случая. Рассматривается следующая

задача: найти решение уравнения

с? Ôxi с? dit

= f(x,y), [х,у)еп, (1)

в ограниченной области П, состоящей из подобластей Г!;.. к = 1,..., N,, в каждой из которых заданы свои положительная константа А* и гладкие функции ¡х > 0, /. Граница области состоит

из внешней и внутренней границ: ЗП = Г и б. На внешней границе области Г = Г^иГп заданы граничные условия в форме

ди

где д, ге, 7 - некоторые заданные функции, п - внешняя нормаль к Г. Внутренняя граница состоит из частей: <? = иС?ц, есть линия раздела подобластей С1к и Пь т.е. линия разрыва функции А. На внутренних границах выполняются условия сопряжения

«к = = (3)

где две стороны границы обозначены через С к и С). Будем рассматривать такую геометрию области П, когда ее граница многосвяз-иа и все участки границы параллельны осям координат. Для дискретизации задачи строится неравномерная прямоугольная объемлющая расчетную область Я. сетка

гж = .г; + Щ. 1 = щ + Щ, г = 1, ■ • •, М + 1, 1 = +

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

1= {•<•, - /<;-:/2 < ж < х-, + Л.-/2, у, - < у < Щ + ^/2},

Г;.; = {./•,_| < .Г < Х,+ |. .{/>-1 < У < У}+1 }•

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

.1 ,,[ -А '^,1.4 + (1 - Р) / = р/(/ - ци)М + (1 -р) ¡(1- Н<1У, (4)

■>■ 5 у V

где 5 и § поверхности объемов V и V соответственно, п - внешняя нормаль к поверхности. Для построения аппроксимаций соотношения (4) используются квадратурные формулы центральных прямоугольников и трапеций. Каждый из объемов Ц^ и для узла

{¡,]), не лежащего на границе области, делится координатными линиями л' = .г,- и у — у] на четыре подобъема \ н 1 'к соответственно, в каждом !П которых функция А - постоянная. При рассмотрении аппроксимации балансного соотношения в одной четверти большого и маленького объемов, добавляя квадратуры по пх внутренним границам, главные члены квадрату]) аннулируются при суммировании по соседним подобъемам, а порядок погрешности аппроксимации интегралов повышается с 0(Л3) до О (к4) за счет остаточных членов. Принимая во внимание вид остаточных членов при последующей аппроксимации производных, устанавливается, что при р = 8/9 порядок аппроксимации есть 0(к4), а при других значениях весового параметра на неравномерной сетке - 0(к3). После рассмотрения балансов по четырем большим и четырем маленьким подобъемам. опирающимся на узел (г,.;), и их суммирования получается 9-точечное уравнение:

8

(Лин)о = /)()«о - Е = /о- <

А = 1

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

А) = Е ри = (1 - + л,/;;/', + а ,вч-; + А Д

Р1 = \iHfXi-i + ^Щи п = + ^Ми,

Ря = Х2н]_\л + \iHff, Р4 = А3Я,?/ + \iHfiij,

ръ = А | ,.! - ~р). р<; = ,<1 - ~р).

Рт = .(1 - ¿Р), Р* = - ^р).

(П)

Я,7 = (1 - §р)л?/л? - (1 - в,7 = л?/л* +

При р = 8/7 получается пятпточечная схема первого порядка на неравномерной сетке (второго порядка на равномерной). Приведен-

ные выражения для коэффициентов в случае равномерной сетки при Л = 1 и ¡> = 16/15 совпадают с коэффициентами левой части известной схемы Мнкеладзе четвертого порядка с точностью до множителя ■Иг^Ьц/о. Из формул (11) следует, что коэффициенты есть величины порядка 0(1) в случае равномерной сетки, в то время как обычно эти величины имеют порядок 0(/г~2). Поэтому при применении соответствующей нормировки получается погрешность аппроксимации О (И1). Объемные интегралы правой части балансного соотношения аппроксимируются по формуле центральных прямоугольников в каждой четверти объемов. Суммирование по четырем подобъемам дает правую часть уравнения (10) в следующем виде:

/о = (Л,- + Л.-- 1)(Л> + ¡ч-^к + ^^{шл+и + Лу+1) (12) + + Ля- О + + /.',.м)

+ 1 + /;+и)) + 0(Л4), /у = /(х,-,^-).

Построенная п]>авая часть совпадает с правой частью схемы Мнкеладзе с точностью до множителя Л,-Л;(4 - Зр). При р = 16/15 значение множителя есть 4/г,-^/5, что совпадает с указанным ранее множителем для левой чисти. Далее рассматривается аналогичная аппроксимация объемного интеграла от члена /ш:

/««Л "+ (1 - />) ^/шг/Г = (Л,- + Ь,-_1)(Лу + (13)

Н--('<//'¡+1/2,7+1/2 +

+ ('«¡/'¡+1/2.7+1/2+ '11-1/|>-1/2,;+1/2)^"|,7+1 + ('47/'<-1/2,7+1/2 + '17-1/Х1-1/2,7-1/2)'г1-1Ы1-1,7 + (/|;-1/<;-)/2,7-1/2 + '»¡/Л+1/2,7-1/2)'Ъ-1"м-1] +0(/г4),

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

границе подобъемов х = х;. С учетом условий (2) и применения симметризации члена ер и она проводится таким образом, что не вносит никаких дополнительных погрешностей в случае постоянного коэффициента а', п погрешность имеет на единицу меньший порядок в случае переменного коэффициента.

Предлагается проводить построение коэффициентов уравнения (10) при иоячеечном подходе. В четверти большого объема вокруг каждого узла сетки, т.е. в каждой ячейке сетки, вводятся лок<1Льные векторы решения, потока п правой части и''' = {<4''}.

= /"' = {/Г). МО. 3. 8} - локальные номера узлов

сеточной ячейки. Компонента есть поток вокруг к—то узла под-объема, и она является линейной формой неизвестных значений и{К поэтому левая часть балансного соотношения в сеточной ячейке представляется в векторной форме = А/и-''. Это представление получено после аппроксимации балансного соотношения в одной ячейке сетки, т.е."локально", поэтому матрица .4./ называется локальной матрицей баланса. Матрица .4/ = есть симметричная квадратная матрица четвертого порядка со следующими элементами (с учетом симметричности матрицы):

т = А:,(1 - |Ри> = А,(1 - '!. (10)

= Аая;/'. т = А;,//'/.

1>:и = Ра -- Ры = Рои-. Ри = Ра» = Рм- Ра» — Роз-

где используются обозначения из (11). и А.) есть значение функшш А в ячейке сетки. Локальную матрацу баланса можно представить в аддитивной форме:

.4/ = Л[ + А'1 + (18)

где .4/ есть потоковый член матрицы баланса, и ее элементы определяются формулами (16). .4^ — {¡»'/Л отвечает аппроксимации (131

слагаемого ци из уравнения (1) и А^

1( — {р^} соответствует аппроксимации граничных условий третьего рода. Элементы матрицы А'1 определяются из (13) и аналогичных представлений для трех остальных узлов сеточной ячейки:

§ _. ур

1>!!л = Рил = РзУ8 = р"а = - 16" # = Мл>/8-

Для рассмотренного случая граничных условий третьего рода получены следующие ненулевые значения элементов матрицы А^ и добавки в правую часть уравнения (10) для узлов номер 0 и 4:

Рио = }Ч

7/\

Р44 = А;

+ (1 -

/Ли = -/«+ = А,-

(1 - т)7о + (1 - -¿-Г/4

Аддитивное представление (18) локальной матрицы баланса является важным с технологической точки зрения, а именно, дает возможность экономии вычислений: потоковый член матрицы вычисляется всегда, я матрицы Л/' и А? - только если ц ф 0 и ее ф 0 соответственно.

Результирующая матрица системы линейных уравнений (глобальная матрица баланса) собирается из всех локальных матриц баланса .4/ (их количество равно количеству ячеек сетки): Л = £/Л/ = Е/ Р' А/Р. Здесь Л/ - расширенная локальная N х Д*-матрнца с теми же ненулевыми элементами, что и в Ль N - общее число узлов. Матрица Р ортогональная 4 х Д:-матрица только с четырьмя ненулевыми элементами, определяемая преобразованием к"' = ]" и. Глобальная матрица баланса, как и локальная, симме-I рпчная. Результирующая система уравнений представляется в виде

Аи = /.

(19)

Коэффициенты щ In уравнения (10) для сеточного узла (i.j). т.е. элементы глобальной матрицы баланса .4, вычисляются через элементы ~~~ /)['' четырех локальных матриц баланса .4; сеточных ячеек, у которых узел (/, j) является опорным, по следующим формулам:

J'J) — „(«'•/) i „(«'-W) . „<»J-') i „('-'■■>'-') J'J _ „'V-1 (ЯП)

Po — Poo + Рзз + Pn +P$s ■ Pi — Pw • UU)

J'.J) __ n(í.i) , ..('J-n (i.j) _ (i.j) , U-lj) ¡j __ i.j

Pii —P 03 +PlS • Л — J'Ol + Рзч • Px — Pili-

где (»'. j) - сеточные индексы нижнего левого узла подобъсма. Учет условий Дирихле осуществляется после завершения формирования системы (19) путем исключения известных значений, соответствующих узлам Дирихле, из уравнений для соседних к узлам Дирихле узлов.

В §1.4 рассматривается построение аппроксимаций трехмерной задачи. Приводится постановка задачи, аналогичная двумерному случаю. Вокруг узла сетки вводится два элементарных объема, каждый из которых делится координатными плоскостями .г = ,r¡. у = ijj. : = Zk на восемь подобъемов. Каждый интеграл в балансном соотношении может быть представлен как сумма восьми интегралов по подобъ-8

емам .7 = У. ■/„,. ./,„ = ./,',"" + J°" . где ./„, - полный поток через поверхность ш-го нодобъема. включающий интегралы по внутренним и внешним частям его границы, прпчсм интегралы по внутренним частям границ всех суммируемых подобье.мов взаимно аннулируются благодаря условиям сопряжения. Приводится подробный вывод аппроксимаций в одной восьмой части большого и маленького объемов, которая обозначена номером 3. Аппроксимация балансных соотношений в подобъемах проводится, как и в двумерном случае, в два этапа: приближения интегралов квадратурными формулами и последующей аппроксимации производных, осуществляемых при помощи формул центральных прямоугольников и трапеций. Приводится подробный вывод аппроксимаций для х-составляющсй ./¡' левой части балансного соотношения по третьему подобъему. Для значений производных в центрах граней используются различные интерполяционные выражения через их значения в узлах сетки, при этом в аппроксимации

./( погрешность имеет порядок О (к4). Можно построить всего двенадцать способов аппроксимации компоненты потока которые дают двенадцать различных дискретных выражений при любом фиксированном весовом параметре р. Аналогичные рассуждения проводятся и для проекций потока , . При этом имеется только одна аппроксимация из всех возможных, не использующая значения производных функции и в вершинах большого объема V^к- Далее рассматривается именно такая аппроксимация. При аппроксимации производных в квадратурах конечными разностями, в результате чего дискретный аналог балансного соотношения будет иметь коэффициенты при неизвестных порядка 0{к), в то время как в непосредственной разностной аппроксимации уравнения диффузии величина коэффициентов есть О (Л-2). Для приведения получаемых аппроксимаций к такой стандартной нормировке квадратуры надо поделить на "взвешенный объем ячейки" + и тогда погрешность аппроксимации

будет иметь только первый порядок. Для достижения еще одного порядка на данном этапе аппроксимации, проводится учет условий сопряжения на внутренних границах раздела соседних подобъемов при рассмотрении полного потока через поверхность подобъема. Устанавливается. что при весовом параметре р = 16/17 погрешность аппроксимации есть величина порядка 0(Ь5). Левая часть баланса по большому и маленькому подобъемам номер три имеет вид:

Л = ¿¡[('^.(«.¿Л- - «ни.») + ~ Щ,>+1,1=) + гцк(ии* ~ "¡.¿.(с+1)] (34)

+ (1 - - «¡+и+1Л + им,*+1 -

+ ''.(.Д "iti-j.it - ».ti-jti.it + "¡.Мч-1 ~ "|,>+1,*+1)

+ tij.it - + "о+м - + О(А'),

Ы

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

(-4'/')0 = р<>и0 - = /о, (35)

где и1' = /о есть аппроксимация правой части балансного со-

отношения, а суммирование проводится по совокупности соседних уз-

лов вокруг точки (i.j.k). В рассматриваемом случае используется 19-точечный шаблон. Явный вид коэффициентов дискретного уравнения. который получается при суммировании выражений типа (34) для остальных семи подобъемов. не приводится в силу громоздкости. При р = 16/15 схема переходит в 7-точечную.

Аппроксимация объемных интегралов по 1 з и V3 правой части балансного соотношения проводится аналогично построениям в двумерном случае. Вклад /ц от подобъемов номер три в правую часть /о уравнения (35) имеет вид

л ... г17р — 16 , 16—15»,, ,

/о = hihjh[ '32 fiji: + 32 Ч/ж.д- + Ai+I,t + fiJMl)]. (3/ )

Полное выражение для правой части /о получается после выполнения

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

Далее рассматривается трехпараметрическая квадратура с параметрами qi, (¡2 и весовым параметром р. приводящая к 27-точечной аппроксимации. При qi — (¡2 = 1 /2 разностный аналог полного потока через третий подобьем представляется в следующем виде:

J'i = '>*[£(«;.j,к - '4+\j,k) + C(u,.lM - ¡(,-H.jjki (40)

+ "ij+l,(i - Ui+lJ+Uk) + *D("0'+U+1 - "i+lJ+l.Hl)] + rikj[B(ui^k - Uij+ i,t) + C(Uijit+i - U;.J+1,H1 + «i+i,j,к - Ui+ij+i.k) + D(ui+I,j,k+1 ~ u»+i.j+U+i)j + rijk[B(ui jt - iiij.k+i) + C{uiJ+ i k - uiJ+lMi + «»+1 ~ "¡+],M'+i) + ~ «;+ij+i,i'+i)]-

Здесь введены обозначения

в-зцзе. с-гца:, о-®^. («)

64 64 64

Из выражении (40) следует, что 27-точечная схема при р = 32/31 переходит в 19-точечную, причем сравнение коэффициентов при неизвестных значениях функции и в узлах сетки в данной аппроксимации с соответствующими коэффициентами в разностном выражении (34) при указанном значении весового параметра р показывает их совпадение. Таким образом, построены два семейства разностных схем: 19- и 27-точечное.

Учет краевых условий Неймана или Ньютона рассматривается на примере, когда левая грань подобъема Уз с координатой х — .г,- является граничной, и на ней задано условие третьего рода с а? ф 0. В случае 19-точечной аппроксимации квадратура, которая не аннулируется при при рассмотрении соседних больших и маленьких подобъемов вокруг {г,], к)-го узла, имеет следующий вид:

л \ ; ; ¡Рц \ , (геи - 7),>ц,е + {геи - -у Фз.х = Лз^Пк[-((геи - +-^->

+ (1 - р)((геи - + (геи - 7).\./\*+1)],

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

Далее рассматривается вычисление коэффициентов системы (35) при поячеечном подходе. Как и в двумерном случае, в подобъеме 1 '¡ определяются векторы локального решения, локального потока и локальный вектор правой части, и выписывается представление вклада в левую часть балансного соотношения в виде линейной комбинации А/и'. где .4; - квадратная матрица восьмого порядка, которая называется локальной матрицей баланса. Ее элементы в случае 27-точечной аппроксимации вычисляются по следующим формулам:

Ро,о = B{Tjki + Tikj + r¡jk) = Ра,

pis - Brjki - C{rikj + rijk) = £>4,8 = P6,9 = P\0,U,

Po,4 = Br<k] - C{rjki + Гф) - Рзя ' Рб.Ю = Р9Л1-

Pü.b = Dr>jk - C(rjkl + rlkj) = p:u} = р.ш = pSM. ^^

= -Dr,)k + C(rjk, + r,kj) = ¡),]A = p6M = p!U(j. P(¡,, = -Drlkj + C'(r}k; + rijk) = pi£ = Pi,,10 = рл, и. Pi'.W = -Drjk, + C{rikj + /•;д.) - />;U4 = рм = p. 1,(5, PÍu = D(rljk 4- rjk, + rjkj) = p3J0 = plk8 = p.V). Здесь rnm¡ определяется из (34), a B,C,D - из (41). В случае 19-точечной аппроксимации элементы матрицы вычисляются по этим же формулам, но при В — p¡8, С = 1 — 15/>/16, D = 0, что следует из выражения (34). Локальный вектор правой части /3 имеет восемь элементов, выражения для вычисления которых можно получить из выражения (37) и аналогичных ему выражений при рассмотрении подобъемов вокруг остальных семи вершин сеточной ячейки.

Локальную матрицу баланса, как и в двумерном случае, можно представить в виде суммы трех слагаемых (18). Элементы матрицы А{ вычисляются по формулам (43). Выписывается вид ненулевых элементов локальной матрицы Af и матрицы Ajv в случае с условием третьего рода на левой грани для 19- и 27-точечной аппроксимации и

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

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

Для равномерной сетки, А,д. = 1, р = 0 и р = 32/31 полученные коэффициенты и локальный вектор правой части пропорциональны с точностью до множителя 1/(8 — 7р) коэффициентам и правой части схемы Микеладзе четвертого порядка точности. На основе семейства 27-точечных схем можно построить аппроксимацию шестого порядка на кубической сетке: при = 1/2, = —4/15, р = 32/31 коэффициенты разностной аппроксимации пропорциональны коэффициентам известного уравнения, аппроксимирующего уравнение — Ли = / с шестым порядком.

В §1.5 получены условия стилтьесовости матрицы А системы линейных уравнений (19). В двумерном случае они имеют вид

В трехмерном случае 27-точечной аппроксимации условия следующие:

32

<*<\Уцк<(3, а < \Vjik < /3, р < —, (47)

32

< /3, \Vjik < Р, \Vkji < /3, р=—.

и/ (^^(Ь^2 32 - 31р 32 - 23р а = 32~—29р'

Для 27-точечной аппроксимации не существует абсолютно монотонной схемы второго порядка. Аналогичные условия для 19-точечного

случая выглядят следующим образом:

wijk < ßu Wjik < А, Wkji <ßu О < p <

1 о

Здесь ßi = 2/>/(lG — 15^). При весовом параметре р = 16/15 схема с 7-точечным шаблоном является абсолютно монотонной.

Далее приводятся известные теоремы для оценок нормы погрешности решения системы (19) в равномерной и евклидовой нормах.

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

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

В §2.2 в рамках поячеечной технологии МКО, основанной на вычислении локальных матриц баланса и локальных векторов правой части, предлагается поячеечный алгоритм построения результирую-

щей системы линейных алгебраических уравнений. Преимущества иоячеечного подхода - простота алгоритма в смысле используемых данных и расчетных формул; выделение в коэффициентах трех составляющих - потоковых, от члена ци и от граничных условий третьего рода и Неймана, которое позволяет не проводить вычисления "ненужного" слагаемого: не вычисляется А{, если в ячейке А = 0; не вычисляется А(', если в ячейке р = 0; не вычисляется Ак, если ни на одной стороне ячейки не задано условие третьего рода или Неймана. Кроме того, возможность распараллеливания вычислений на данном этапе в силу независимости расчета одной локальной матрицы от другой. И, наконец, возможность экономии вычислений: если ввести дополнительный признаковый массив для одинаковых ячеек сетки, то можно не проводить повторно локальные вычисления при условии, что признаковые значения для ячеек совпадают.

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

Трехмерную сеточную структуру составляют четыре массива. Это трехмерный массив номеров подобластей в сеточных ячейках med (вычислительные затраты на его построение пропорциональны количеству ячеек в подобластях, т.е. размерности задачи), и трехмерные массивы iface, j/acc, kface, которые обозначают соответственно номера граней подобластей на перпендикулярных осям Л', Y и Z гранях ячеек сетки. Массивы номеров граней используются для вычисления ненулевых элементов матрицы AN, когда требуется определить, задано ли на некоторой грани сеточной ячейки условие Неймана пли Ньютона. Как грани подобластей, так и граничные условия пронумерованы подряд натуральными числами, и на каждой грани каждой подобласти-параллелепипеда задан номер граничного условия. Хотя массивы трехмерные, тип их элементов описан как ко-

\

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

В двумерном случае сеточная структура данных аналогична трехмерной с естественным отличием в размерности массивов: в данном случае массивы двумерные. Сеточную структуру составляют массив номеров подобластей в ячейках med и аналоги массивов сеточных гранен два массива сеточных ребер hedge и vedge. Первый содержит номер граничного ребра для каждого горизонтального сеточного ребра, а второй - номер граничного ребра для каждого вертикального сеточного ребра. Приводятся описания алгоритмов построения массивов. Количество необходимых операций алгоритма построения массива med есть величина, пропорциональная размерности задачи, а алгоритма построения массивов hedije, vedge - на порядок меньшая размерности задачи величина.

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

В главе 3 представлены принципы программной реализации мето-

да конечных объемов, описаны созданные на основе рассмотренных технологических особенностей МКО программы для решения двумерных и трехмерных краевых задач, и содержатся результаты и анализ численных экспериментов, проведенных при помощи разработанных программ. В качестве языка программирования выбран стандарт Фортрана-77, что обеспечивает хорошую переносимость программ на различные ЭВМ. Каждая из программ Ь'к<1е2 и Ь"Бс1еЗ (двумерный и трехмерный случаи) численного расчета краевой задачи реализована в виде одной подпрограммы, внутри которой управление вычислительным процессом представляет собой последовательный вызов подпрограмм для ввода информации о задаче, построения сетки и сеточной структуры данных, аппроксимации и решения системы линейных алгебраических уравнений. Данные меладу подпрограммами передаются через параметры и общие блоки. Программы основаны на алгоритмах и структурах данных, описанных в главе 2.

В ''¡3.1 излагается модульный анализ программ при рассмотрении общей схемы вычислительного процесса решения задачи. Описывается структура программ £уьс!е2 и Ь'н(1еЗ для решения уравнения диффузии в областях с прямоугольной геометрией. Ввод исходных данных осуществляется через входной файл. Для дискретизации задачи используется регулярная неравномерная прямоугольная сетка. Преимущества применения регулярных сеток - простота и экономичность представления и расчета. В описываемых программах сетка может быть как равномерной, так и неравномерной с изменением шагов сетки по арифметической или геометрической прогрессии. Результатом работы блока построения сетки являются два или три массива сеточных координат в зависимости от размерности задачи. Блок построения сеточных структур данных реализует приведенные в главе 2 алгоритмы. Имея на входе заполненные массивы (■«•точной структуры данных, подпрограмма вычисления коэффици-

ентов выполняет последовательный обход ячеек сетки, и для текущей ячейки сетки вычисляет локальные матрицу баланса и вектор правой части и добавляет их в глобальные, т.е. реализует поячееч-ный алгоритм получения глобальной матрицы баланса, и заполняет матричную структуру данных, которая, в свою очередь, является входной информацией для блока, решающего систему уравнении. С точки зрения технологии вычислений, на этом этапе важными факторами являются возможность настройки подпрограмм на работу с вещественными переменными простой или двойной точности, динамическое размещение массивов в памяти в зависимости от применяемой аппроксимации и метода решения системы уравнений и сама программная реализация алгоритмов решения системы. В созданных программах все вещественные перс менные описаны с двойной точностью из-за требований программной реализации метода непо 1-ной факторизации с ускорением сопряженными градиентами. Объем арифметических операций на одну сеточную ячейку в подпрограмме 180 в двумерном случае и 400 в трехмерном, и эти константы суть константы пропорциональности для общего объема действий, прямо пропорционального размерности задачи. Учет условий Дирихле, проводимый после формирования глобальной матрицы, также1 реализован в виде подпрограммы, выполняющей обход только тех участков границы, на которых задано это условие. Для получения решения задачи используются разработанные в ВЦ СО РАН итерационные модули, реализующие метод неполной факторизации с ускорением сопряженными градиентами.

Числовые характеристики разработанных программ следующие. Объем двумерной программы - около 2900 строк Фортрана; трехмерной - 3900. При этом подпрограмма вычисления локальных матриц, являющаяся реализацией предложенного поячеечного алгоритма, имеет объем около 500 строк в двумерном случае и около 1150

строк в трехмерном с учетом 19- и 27-точечной аппроксимации. Объем требуемой опреративной памяти в двумерном случае определяется двенадцатью вещественными массивами с двойной точностью с размерностью, равной числу узлов сетки: пять коэффициентов системы, решение, правая часть и пять дополнительных массивов для итерационного модуля. В трехмерном случае количество вещественных массивов с размерностью, равной числу узлов сетки, - тридцать один: четырнадцать коэффициентов системы, решение, правая часть, и массив размером (15 х число узлов сетки) для итерационного модуля. Программы выполнены в безавостной манере. Для проверки приведенных оценок числа операций проведено измерение времени этапов построения структур данных, расчета коэффициентов и получения решения на примере задачи Дирихле в квадрате на последовательности равномерных сеток с числом шагов сетки 20, 40, 80. Результаты экспериментов позволяют сделать следующие выводы. Во-первых, подтверждается теоретическая оценка вычислительных затрат этапов построения структуры данных и расчета коэффициентов: вычислительные затраты на этапах построения структур данных и расчета коэффициентов системы прямо пропорциональны числу узлов сетки. Во-вторых, общие затраты на выполнение предлагаемых алгоритмов построения структуры данных и расчет коэффициентов занимают меньше десяти процентов от времени решения задачи, что является важным показателем экономичности алгоритмов и их программной реализации. Для трехмерной задачи получаются аналогичные результаты. Приводятся рекомендации по использованию программ {увс1е2 и Л^еЗ, которые задают связь между требуемым порядком аппроксимации, типом сетки и весовым параметром.

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

задач: двумерные и трехмерные эллиптические уравнения с кусочно-постоянными коэффициентами Л, постоянными и переменными функциями /; граничные условия Дирихле, Неймана и Ньютона с постоянными и переменными коэффициентами аэ, 7; равномерные и неравномерные прямоугольные сстки. Эксперименты подтверждают порядок построенных балансных аппроксимаций.

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

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

3. на основе предложенных алгоритмических подходов и структур данных созданы программы для численного расчета уравнения

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

По теме диссертации опубликованы следующие работы:

1. Гурьева Я. JI. Вопросы технологии численного решения смешанных краевых задач методом конечных объемов. - В кн.: Труды конф. молодых ученых. - Новосибирск, ВЦ СО РАН, 1997, с. 51-64.

2. Гурьева Я.Л. Технологические аспекты численного решения смешанных краевых задач методом конечных объемов. - Автометрия, 1997, №5, с. 100-109.

3. Gurieva Y., Il'in V. Finite volume approached for 2-D BVPs: algorithms, data structures, software and experiments. - Univ. of Nijmegen, 1997. - 24 p. - ( Univ. of Nijmegen, Dep. of Math. Rep. No. 9715).

4 Gurieva Y.L., Il'in V.P. On second order finite-volume approximations for 3D mixed boundary value problems. - Bull, of the Novosibirsk Computing Center. Series: Numerical Analysis, 1996, Issue 7, p. 51-70.

5. Gurieva Y.L., Il'in V.P. On the finite volume technology for mixed boundary value problems. - In: Advanced Mathematics, Computations and Applications: Proc. of the International Conf. AMCA-95, Novosibirsk, Russia, 20-24 June, 1995. Novosibirsk, NCC Publisher, 1995, p. 650-655.

РОССИЙСКАЯ АКАДЕМИЯ НАУК СИ Б ИРСКОЕ ОТДЕЛ ЕН ИЕ ИНСТИТУТ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ И МATEMАТИЧЕСКОЙ ГЕОФИЗИКИ

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

ГУРЬЕВА Яна Леонидовна

ВЫЧИСЛИТЕЛЬНАЯ ТЕХНОЛОГИЯ . МЕТОДА КОНЕЧНЫХ ОБЪЕМОВ

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

Специальность - 05.13.11 математическое и программное обеспечение вычислительных машин, комплексов, систем и сетей

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

Новосибирск 1999

Содержание

Введение. Понятие вычислительной технологии 4

Глава 1. Конечно-объемные аппроксимации краевых задач 10

1.1. .Метод конечных объемов ............................................13

1.2. Аппроксимации двумерной краевой задачи........................16

1.2.1. Постановка задачи ............................................16

1.2.2. Построение аппроксимаций ..................................17

1.2.3. Поячеечный подход. Матрицы баланса......................28

1.3. Аппроксимации трехмерной краевой задачи........................33

1.3.1. Постановка задачи и подход к аппрокисмашш..............33

1.3.2. Аппроксимация балансных соотношений....................36

1.3.3. Поячеечный подход. Матрицы баланса......................50

1.4. Некоторые свойства матрицы системы и оценки ошибок .... 56

Глава 2. Структуры данных и алгоритмы метода

конечных объемов 61

2.1. Геометрическое моделирование......................................62

2.1.1. Описание трехмерной области................................64

2.1.1. Описание двумерной области ................................65

2.2. Сеточные и матричная структуры данных........................66

2.3.1. Трехмерная сеточная структура данных....................67

2.3.2. Двумерная сеточная структура данных......................70

2.3.3. Матричная структура данных................................72

2.3. Поячеечный алгоритм................................................73

2.4. Учет граничных условий ............................................74

2.5. Объектно-ориентированный подход ................................76

Глава 3. Программная реализация и численные эксперименты 83

3.1. Модульный анализ....................................................84

3.1.1. Задание исходной информации....................84

3.1.2. Дискретизация области и построение сеточной структуры данных.....................................86

3.1.3. Формирование и решение алгебраической системы уравнений ........................'.............8;>

3.1.4. Числовые характеристики программ........................90

3.2. Примеры решения модельных задач................................94

3.2.1. Примеры двумерных задач....................................94

3.2.2. Примеры трехмерных задач.................100

Заключение 107

Литература 108

Введение. Понятие вычислительной технологии

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

В становлении понятия "вычислительная технология" можно выделить несколько направлений, которые привели к современному его пониманию.

В начале 70-х годов технологические вопросы в прикладной математике обсуждались советскими учеными в связи с бурным развитием пакетов прикладных программ для решения различных задач моделирования реальных физических явлений. Технологические основы принципов модульного конструирования при решении задач матема тической физики изложены в работах Н.Н.Яненко и А.Н.Коновалова [22], [47 - 48]. Эти принципы заключаются в следующем:

- каждый алгоритм может быть разбит на совокупность более мелких частей - алгоритмических модулей:

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

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

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

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

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

о

нпю ,/L.ï>i решения многих задач. В качество примера можно назвать третий семинар по комплексам программ математической физики, который был полностью посвящен модульной тематике, и его труды [4Сj. Развитие модульных принципов нашло отражение в более поздних работах А.П.Ершова и В.Г1.И льика fil ~ 12]. В.И.Карначука и А.H.Коновалова [20].

Модульное программирование является одной из четырех технологий программирования. сформировавшихся в конце 60-х - начале 70-х гг. И если в становлении модульного программирования огромная роль принадлежит советским ученым, то за рубежом появились такие технологии, как структурное программирование [10], в котором работа программиста есть суперпозиция фиксированных допустимых структур, программирование сверху-вниз ¡79] - многоуровневая дисциплина написания программ, когда описание системы на верхнем уровне не зависит от описания блоков более низких уровней, и HГРО-технология [89]. являющаяся многоуровневой дисциплиной проектирования и документирования программ с использованием типовых диаграмм.

К середине 70-х гг. группой киевских ученых была, разработана и начала широко применяться технология программирования, известная как R-тохнология N1. Основой R-техиолопш является новый взгляд на семантику обработки данных, когда структура данных рассматривается не только как информационная структура, но и как логическая схема соответствующего алгоритма ее обработки и как некоторая схема работы коллектива программистов по доопределению исходной структуры. Результатом доопределения является R-программа, которая с оомошыо автоматической генерации на технологическом комплексе H ! h преврашаеiся в готовый программный' продукт. Автооы указанной книги называют следующие отличительные особенности R-технологии: организация коллективного труда программистов и возможность создания эффективных проблемно-ориентированных комплексов производства программных систем.

В конце 60-х гг. развивалось также тех ко лог и чес кое направление, связанное с автоматическим построением вычислительных алгоритмов и автоматизацией всего процесса программирования. Основные положения новой технологии моделирования представлены в работах Р.И.Марчука и А.П.Ершова [26]. [28], [77]. В традиционной схеме математического моделирования с помощью ЭВМ автоматизация затрагивала в основном лишь программирование алгоритмов (см.. например. (I3j). оставляя в стороне остальные его папы: выбор подходящей математической модели, выбор методов и алгоритмов ре-

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

- автоматизацию построения алгоритмов по заданной постановке исходной задачи:

- активный диалог исследователя с ЭВМ;

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

- способность ЭВМ достигать "пиковой" производительности при решении определенного класса задач.

На основе этой технологии можно повысить общую эффективность моделирования. которая, согласно В.Е.Котову [23]. '"...определяется степенью автоматизации всех его этапов, переходов от одного этапа к другому, а также возможностью ах интерактивного совмещения''. В этой статье указываются такие средства ее достижения, как создание сверхпронзводнтельных процессоров для решения отдельных классов задач (специализация вычислительных средств), открытость архитектуры вычислительного комплекса (модульность компонентов, стандартные внутренние и внешние интерфейсы, переносимость) н разработка механизмов конструирования развитых вычислительных н программных комплексов из специализированных и универсальных модулей, включающая средства развитого человеко-машинного ин герфейса. накопления и обработки знаний, синтез алгоритмов и программ.

Неотъемлемой чертой вычислительной технологии является ее связь с программированием и пакетами прикладных программ, а ее применение должно было привести к "...переходу прикладного программирования от кустарного производства к индустриальному'' [12]. Понятие технологии программирования охватывает весь процесс реализации программного продукта "...от появления в нем потребности и определения его основных функций до прекращения его эксплуатации" /[31] , с.95/, т.е. весь жизненный цикл программы.

Одной из компонент современной технологии программирования является объектно-ориентированное программирование (ООП), которое, как и объектно-ориентированная методология в целом, имеет следующие характерные особенности (см.. например. [1)0]. стр.411). Для построения модели некоторой задачи необходимо определить объекты и классы объектов, которые различаются данными и функциями (методами); еслп классы имеют общие

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

Таким образом, развитие технологии вычислений с применением ЭВМ выразилось в том.-что в единой технологической цепочке были выделены следующие этапы: определение "физической"' модели, формулировка математической модели, разработка численных алгоритмов, их программирование 11 отладка, тестирование полученной программы, проведение методических численных экспериментов п. наконец, решение практических задач.

Кроме аспекта, связанного с программированием, в определении понятия "вычислительная технология' можно выделить также и математическое направление, которое внесло свой вклад в современное содержание этого понятия. Сюда относятся применение в расчетах априорных и апостериорных оценок решения и расчеты на последовательности сеток для уточнения получаемого решения, расчеты на неструктурных сетках в областях сложной конфигурации. С технологи ческой точки зрения все эти подходы нашли свое воплощение в методе конечных элементов (МКЭ). Теоретические основы метода были разработаны в конце 60-х - начале 70-х годов и отражены во многих фундаментальных работах того времени (см.. например, |38;). За несколько последних десятилетий метод конечных элементов претерпел значительное развитие. Это выразилось, во-первых, в создании общей теории методов решения различных порядков точности для широкого класса задач с помощью адаптивных сеток [81], принципов декомпозиции и многосеточных алгоритмов [74|, что, в свою очередь, позволило создать робастные адаптивные численные алгоритмы и программы. Во-вторых, широкое и эффективное применение МЬ.Э обусловлено созданием унифицированного вычислительного подхода, базирующегося на автоматическом построении сеток [69]. определении локальных матриц жесткости и масс, сборки глобальной матрицы, формирования специальных структур данных и т.д. (см., например. [90] п цитируемую там литературу). В рамках подобной технологии такие вариации метода, как Ь-, р- или Ь-р-верскн [49], поузловая или поэлементная сборка матрицы системы находят свое отражение в соответствующих структурах данных п алгоритмах расчета матрицы.

Таким образом, современное понятие вычислительной технологии реше-

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

Кроме понятия вычислительной технологии, в последнее время можно встретить употребление термина "информационно-вычислительная технология'". Например, в работе [17] дается следующее его определение: "Под 11нформацнонно-вычнелительными технологиями будем понимать совокупное гь соглашений, правил, организационных мероприятий, технических и программных средств для решения определенного класса задач определенным кругом пользователей". Примечательно то. что рассмотрение "... требований и некоторых спецификаций к составу и характеристикам базовых вычислительных модулей, а также используемым ими структур данных" в указанной работе называется "ядром1" технологии.

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

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

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

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

Одним 1п способов аппроксимации дифференциальных уравнений, которыми описывается математическая постановка задачи, является, наряду с методом конечных разностей и методом конечных элементов, метод конечных объемов (МКО), который широко применяется для многих задач математической физики, и. в частности, для аппроксимации уравнения Гельмгольца. Необходимо отметить, что большинство научных публикаций по МКО содержат или только исследование математических свойств метода, или описание его практического применения, а в лучшем случае - сравнение с другими методам и а 11 проксимацн!I.

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

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

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

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