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

РОССИЙСКАЯ АКАДЕМИЯ НАУК Pfü Q[) С И Б И Р С К О Е ОТДЕЛЕНИЕ

ВЫЧИСЛИТЕЛЬНЫЙ ЦЕНТР

- 1 MaR 1393

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

МОЛОРОДОВ ЮРИИ ИВАНОВИЧ

УДК 519.633

РЕШЕНИЕ КРАЕВЫХ И НАЧАЛЬНО-КРАЕВЫХ ЗАДАЧ ОПРЕДЕЛЕННЫХ НА ГРАФЕ

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

Автореферат

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

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

Р.'Лугя н«;олпс|щ г< Институт« теоретической и прикладной механики ",1<-1ипг:ко1'(! »"'/дылиния Российской Академии наук.

НаучниЯ руноводитель: Сфициалъные оппоненты:

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

кандидат физико-математических наук Б.П.Колобов

доктор физико-математических наук А .Ф.В'">нБОДИН

кандидат физико-математических наук А.Г.Слепцов

Институт Теплофизики СО РАН

Защита диссертации состоится " ' л-" марта 19ЭЗ г. ь 14-30 чтов на заседании Специализированного совета К СП?.;п.01 Вычислительного центра Сибирского отделения РАН не- адресу: ГчЗПП90, г. КовосиПирск-ЭО, проспект Академика Лаврентьева, б.

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

Автореферат разослан ^Д— 1993 г.

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

Ю.И.Кузнецов

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

>

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

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

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

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

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

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

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

Апробация. Основные результаты диссертации докладывались на XII Всесоюзной школе по "Численным методам механики вязкой жидкости" (Абакан, 1990 г.); на международной конференции "Математические модели и численные методы механики сплошной среды" (Новосибирск, 1991 г.); на Школе-семинаре по комплексам программ математической физики (Новосибирск, 1992г.), а также на научных семинарах кафедры Вычислительных методов механики сплошной среды НГУ и Института Вычислительных Технологий (МВТ) СО РАН и на семинарах "Численные методы механики сплошной среды" ИТПМ СО АН России.

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

Объём диссертации. Диссертация состоит из введения, трёх глав, заключения, списка литературы и насчитывает 119 страниц, в том числе: 34 таблицы, 48 рисунков и 99 наименований библиографии на 10 страницах.

С0ДЕР1АНИЕ РАБОТЫ Во введении даётся обзор литературы, современного состояния и основных направлений развития методов и проблем решения краевых и начально-краевых задач, определённых на ориентированных графах. Обоснованы актуальность и важность вопросов, составляющих предмет исследования. Изложены основные результаты диссертации, описана её структура.

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

и. = a(x,t)-u + b(x,t)-u + c(x,t)-u + d(x,t)

u XX X

x t fa, bJ; t e [T0,TK]; (1)

с линейными краевыми условиями смешанного типа на границе

a0(t).u(a,t) * = Vf(t) ^

p0(t)-u(b,t) + PfiU-^g'^ = <ç2(t) и начальными условиями

u(x,t0) = %(х), (3)

с кусочно-непрерывными функциями a(x,t) и b(x,t), имеющими разрывы на некотором множестве линий = сot(t). Коэффициенты c(x,t), d(x,t) предполагаются ограниченными и достаточно гладкими по (x,t) функциями.

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

В используемом псевдогриновском методе с помощью проекционных методов, применяемых на каждом конечном элементе независимо, строится представление приближенного решения u(x,t) для (x,t) € выраженное через значения узловых параметров

и(г,а> в граничных узлах и линейно независимые координатные функции Ф(г,а)(х,t) и функции Q(r,a)(x,t) соответствующей решению неоднородной задачи в области с нулевыми граничными условиями на части границы Т(г>, общей с соседними элементами. Координатные функции выражаются через интерполяционный базис

P(r,a)(x,t) (построенный на множестве граничных и внутренних узлов конечного элемента), и последовательности ортогональных базисных функций.

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

Отыскивая базис в классе полиномов степени пони степени (ri/2) от i и используя продолженную систему для уравнения (1), с помощью локально-проекционных методов (коллокаций, метода Галёркина, наименьших квадратов) определяется решение для пространственно-временных конечых элементов с порядком аппроксимации

О (hxn~'+ hxn~3-h,r + ... +fixn~1 ~г ' ■ h^ÎT*, (4)

где С-) обозначает целую часть от деления (п-1) на 2.

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

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

На отрезке [а,Ъ] рассматривается краевая задача вида

Lu(x) = k(x)-u"(x) + р(х)-и' (х) + q(x)-u(x)= d(x), (5)

с краевыми условиями смешанного типа a0-u(a)+at-u.' (a)=<ç1 "I

р0.игь;+р,.ичьхр2 | • (б)

Коэффициенты k(x)>0, р(х) являются кусочно-непрерывными функциями, a q(x) и d(x) предполагаются ограниченными и достаточно гладкими по (х,t) функциями.

Приближенное решение задачи отыскивается в виде

(1) (2) (3)

и(х) = и(а)-Ф (х) + и(Ъ)-Ф (х) + Ф (х), (7)

где ' 1_Фп;= й(1)(х), I = 1,2,3,

а(1 = а(2)(х) = о, а(3)(х) *= а(х),

Ф(1)(а) = 1, Ф (П(Ъ) = О, Ф(г>(а)'= О, Ф(2)(Ь) = 1, Ф (3>(а) = О, Ф (3)(Ь) = О.

(8)

Решения Ф(1)(х1) = отыскивались методом локальной коллока-ции, используя базисные функции в виде полиномов Лагранжа. Узлы коллокаций совпадали с узлами квадратурной формулы Гаусса, которые ,как показали Де Бор и Шварц, являются наилучшими для обыкновенных дифференциальных уравнений.

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

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

Решения на рёбрах и производные решения в вершинах графа записываются в виде суммы решений однородной и неоднородной краевых задач, получаемых разностными схемами высокого порядка точности (0(1г для ОДУ и 0(.Ъ.6+Ъ.4-К +...+ТХ3) для УЧП.

а: х х х х

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

Рис.1

Пронумеруем вершины и ребра , входящие в граф независимо друг от друга. Величины, относящиеся к 1-тому отрезку, будем обозначать индексом I снизу, заключенным в круглые скобки. Величины, относящиеся к я-й вершине, будем обозначать индексом а сверху, заключенным в круглые скобки.

Для описания топологии используется целая функция Пг , которая устанавливает соотношения между ребрами и узлами (вершинами) графа (соотношения инцидентности):

+7 - ребро I входит в узел г,

О - ребро I не примыкает к узлу 5, (8)

-1 - ребро I выходит из узла Я.

На каждом из ребер графа приняты следующие обозначения: иг(хг) ~ распределение функции иг по длине ребра I;

х(1в} - координата узла^, связанного с ребром I;

Ы3(8) - множество рббер, связанных с узлом 5;

и(3)= и(г33= иг(х(г3)) для всех I с МЗ(3).

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

1) Условия примыкания, когда значения исследуемой физической величины одинаковы для всех концов рёбер, примыкающих к данному узлу

и(г3)= и(в), I е ИБ (9)

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

&] (х^3*) Л

а(е)исз)+ --) = в(8); СЮ;

гемз

5 = 1,..., Ш,

е кожчество уз

данные числа,

где Ш - общее кожчество узлов графа, а о^3>,7<з:),е(з; - за-

(о(3))2+ О.

Для всех рббер, связанных с узлом 3 (I е МБ(3)), решение уравнения (5) представим в виде

иг(хг) = и(3)Ф(г1 )(хг) + и(ЗТ(1)) Ф[2)(хг) + Ф<г3)(х1) , (11) где Б(1), БТ(I) - номера двух узлов, связанных с ребром Ъ.

(Бтси&а)).

Ф^3)(хг) представляет решение однородных и неоднородной краевых задач:

\_Ф\1)(хг) = 0 , \_Ф(гг)(хг) = О

(3)

1-®г = Ог(хг) ,

где |_ - линейный дифференциальный оператор 2 порядка, ф[1)(х[5)) = 1, Ф[1)(х(15Т(1)>) = О,

ф[2)(х{3^) = 0, ф[2)(х(ЗТ(1))) = 1, (12)

ф{3>(х[8}) = О, <й[э>(х{В1(г») = О.

Решения определяются элементно- коллока-

ционным методом, позволяющим строить трёхточечные разностные схемы произвольного порядка точности. Для этого ребро I разбивается на Ыг конечных элементов узлами х , включающих в себя возможные точки разрыва А1(хг):

а1 = Х11< Х12< •■•<ХШ = Й1.

На каждом конечном элементе [хг {> хг размером

пг,1 = хг.1-и~ хг.1 в качестве узлов коллокаций выбираются N узлов квадратур Гаусса

с весом 1 (корни полиномов Лежандра порядка У).

Из условий метода коллокаций в N узлах на каждом конечном элементе и условий непрерывности потока в узлах хг 1

*>1(х(1аЛ>

агТ

]

,1=2,..., М.

строится трёхточечндя разностная схема с порядком аппроксимации

Подставляя в ПО.) выражение

охг г г

+ Ф

(3) /-Сз)

где

*\Л)(*[В)) = ~ЗзГ *1Л)(*[В}) ■

получаем линейную систему уравнений для определения и(3)

г е из

+ 1(3)^[8)-А1(х(13)).Ц2)(Х(13>)

г е из

(Ъ)

,П<В(1» +

Т(ЗТ(1)) _

I { КЗ

или в матричной форме

(в)

Б=1,..., Ж/.

Н{и}.{г}.

(13)

(14)

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

Условия примыкания имеют вид

и[3-*>= и(зл\ (15)

а балансовые соотношения запишутся в виде

диг (хг)л(в.г> }

г е из

Б = 1.....ОТ, (16)

_ заданные числа, (а(В,±})2+ о.

Временной интервал решения задачи делится на Ш временных слобв размера йТ. Слой <37* разбивается линиями, параллельными оси ОХ,на три подслоя ширины йТ/3, и обозначаются точки деления переменными с индексами

I = t1,t2,t3 на нижней границе Г2, t = t4,t5,t6 на верхней границе ta = 3 = 1 >••■,б.

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

иг(х = ^1прш(х-г) + тгг(х'1:)' (17)

п=1

где и1п - функции, заданные краевыми условиями на соотвествущем ребре в точках ta , а Р1г1(х^) определяются разностными решениями однородных начально краевых задач (НКЗ), описанном в главе I,

= 0, (18)

удовлетворяющим начальным условиям

Р1п(х,0) = О, (19)

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

Р^харл^ = (20)

8 - ( 1' 1 = * ~ 1 О ( Ф 3

£ — 6, $ - 7,...,6, 71 =■

Р17(х, и опредляется разностным решением неоднородной начально-краевой задачи, представленным в главе I,

\_^17(х,г)= Гг(хЛ) (21)

с начальным условием

Рг7(т,0) = фг(х), (22)

и граничным условием Дирихле

Р17(х(1}),хр = О (23)

I = = 1,....,6.

Каждое из решений ?г(хЛ) и их производные дРг(хЛ)/дх на краях каждого из стержней графа определются с помощью псевдо-гриновского варианта метода конечных элементов высокого порядка точности, описанного в главе I для одного отрезка.

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

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

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ ДИССЕРТАЦИОННОЙ РАБОТЫ

1. Реализован новый коллокационно-сеточный алгоритм высокого порядка точности ОСЛ® + решения начально-краевой задачи для одномерных параболических уравнений второго порядка. Он относится к чисто неявным схемам и является абсолютно устойчивым.

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

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

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

5. Предложены алгоритмы, позволяющие находить решения сис-

тем дифференциальных уравнений (ОДУ и УЧП) определенных на конечных ориентированных графах, в том числе и уравнений, решения которых имеют внутренние и пограничные слои.

6.Разработан комплекс программ для решения указанных выше задач который написан на алгоритмическом языке FORTRAN для ЭВМ Эльбрус 1-КБ и IBM-PG/AT. Проведбнные расчбты модельных задач показали эффективность используемого метода и разработанного алгоритма, его абсолютную устойчивость, сходимость при фиксированном порядке аппроксимирующих полиномов в равномерной норме в любой точке расчбтной области.

1. Колобов Б.П..Молородов Ю.И. Численное решение краевых задач для параболических уравнений с разрывными коэффициентами псевдогриновскими схемами высокого порядка точности.-Новосибирск, 1985.-40 с. -(Препринт/АН СССР Сиб. отд-ние. Институт теорет. и прикл. мех.; .№5-85).

2. Колобов Б.П..Молородов Ю.И. Метод локальной коллокации и построение адаптивной сетки для краевых задач с пограничным слоем. //Моделирование в механике. -Новосибирск, 1989, т.3(20).- № 6 с.53-69

3. Колобов Б.П., Молородов Ю.И. Применение схем высокого порядка точности к решению задач на графах. //Моделирование в механике. -Новосибирск, 1990, т.4(21).5 с.Ш-123.

4. Колобов Б.П., Молородов Ю.И. Выбор узлов коллокаций в схемах высокого порядка точности для задач с пограничным слоем. -//Моделирование в механике.-Новосибирск, 1992, т.6(24)

6 с.80-94. .

5. Молородов Ю.И. Решение систем дифференциальных уравнений определённых на графе схемами высокого порядка точности.//Вычислительные технологии.- Новосибирск, 1993 .-Л6.-С.60-72.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ ДИССЕРТАЦИИ ОПУБЛИКОВАНЫ В СЛЕДУЮЩИХ РАБОТАХ