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

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

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

2 7 АЫ 21шз

Еремин Алексей Сергеевич

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

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

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

Санкт-Петербург - 2009

003475860

Работа выполнена на кафедре информационных систем факультета прикладной математики — процессов управления Санкт-Петербургского государственного университета.

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

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

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

доктор физико-математических наук, профессор Летавин Михаил Иванович

кандидат физико-математических наук, доцент Королев Владимир Степанович

Институт прикладных математических исследований Карельского научного центра Российской Академии Наук (ИПМИ КарНЦ РАН)

Защита состоится « >•> ¿-ё///*^З^-Р 2009 г. в £?^Г~часов на заседании совета Д.212.232.59 по защите докторских и кандидатских диссертаций при Санкт-Петербургском государственном университете по адресу: 199004, Санкт-Петербург, Средний пр. В. О., д. 41/43, аудитория 513.

С диссертацией можно ознакомиться в Научной библиотеке Санкт-Петербургского государственного университета по адресу: 199034, Санкт-Петербург, Университетская наб., д. 7/9.

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

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

доктор физ.-мат. наук, профессор ' Ногин В. Д.

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

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

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

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

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

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

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

Разработанная Дж. Бутчером абстрактная алгебраическая теория методов Рунге — Кутты открыла большие возможности для теоретического исследования их свойств и для конструирования новых высокоэффективных одношаговых алгоритмов.

В ходе исследования свойств численных методов решения СОДУ были установлены некоторые ограничения, связывающие максимально достижимый порядок получаемого приближения и количество обращений к вычислению правой части системы уравнений, или число этапов, используемых методом. Для методов типа Рунге —Кутты эти соотношения получили наименование «барьеров Бутчера». Однако в дальнейшем И. В. Олемским было обнаружено, что в случае наличия определённых структурных особенностей систем ОДУ удаётся построить методы, позволяющие получить более высокий порядок, чем это установлено упомянутыми ограничениями, по крайней мере, для некоторой части компонентов.

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

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

ственно упростить процесс их разработки.

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

Целями диссертационной работы являются:

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

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

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

Методы исследования. Для решения поставленных задач использова-

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

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

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

Основные положения, выносимые на защиту:

1. Построение явного одношагового пятиэтапного метода пятого порядка для автономного обыкновенного дифференциального уравнения — эффективный вариант использования структурных особенностей ОДУ.

2. Модификация теории помеченных деревьев Дж. Бутчера и Э. Хайрера для расширений явных методов типа Рунге — Кутты на случай систем ОДУ со структурным особенностями.

3. Построение нового экономичного явного вложенного метода типа Дор-

манда — Принса пятого порядка точности, по своим характеристикам превосходящего, чем существующие методы того же класса.

Апробация работы. Основные результаты диссертации докладывались и обсуждались на XXXVIII, XXXIX и XL научных конференциях «Процессы управления и устойчивость» факультета прикладной математики — процессов управления (г. Санкт-Петербург, апрель 2007, 2008 и 2009 гг.) и на международной конференции «Conference on Scientific Computing», посвященной 60-летию профессора Э. Хайрера (г. Женева, Швейцария, июнь 2009 г.).

Публикации. Материалы диссертации опубликованы в 5 печатных работах, из них 1 статья в журнале из списка рекомендуемых ВАК [1], 3 статьи в сборниках трудов конференций [2-4] и тезисы докладов [5, 6].

Структура и объем диссертации. Диссертация состоит из введения, 4 глав, 13 параграфов, заключения и списка литературы. Объём диссертации составляет 91 страницу. Список литературы включает 25 наименований.

Основное содержание работы

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

В первой главе рассмотрен случай автономного обыкновенного дифференциального уравнения. Описывается идея, позволяющая преодолеть так называемый «первый барьер Бутчера» и построить явный одношаговый пяти-этапный метод типа Рунге —Кутты пятого порядка точности. Формулируется теорема о существовании такого метода и приводится её доказательство. Приводятся численные примеры решения начальных задач, подтверждающие эффективность построенного метода.

Таблица 1. Соотношение порядка метода q и минимального числа этапов т, необходимого для его достижения

ч 1 2 3 4 5 6 7 8

т 1 2 3 4 ■ 6 7 9 11

В § 1.1 ставится задача на рассмотрение особенностей автономного обыкновенного дифференциального уравнения с точки зрения построения явных одношаговых методов. Приводится таблица соотношений минимально необходимого числа этапов метода для обеспечения определённого порядка точности для неавтономных уравнений — так называемые «барьеры Бутче-ра» (табл. 1).

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

Таким образом для пятого порядка получилось не 21 ограничение на 19 параметров (доказательство неразрешимости данной системы было престав-лено Дж. Бутчером в 1964 году), а всего 16, что позволило сформулировать и доказать следующее утверждение.

Теорема 1. Для автономного обыкновенного дифференциального уравнения

У'(х) = /(г/(я)), х, уеа1,

Таблица 2. Явный одношаговый пятиэтапный метод пятого порядка для автономного уравнения

0

2 10

0.475427346024 1.682585608914 -1.207158262890

2 10 -0.627218871461 1.611014223644 -0.260188554433

1 2.102235685463 -3.166734792190 0.912584612982 1.151914493745

1 5 5 1

12 12 0 12 12

существует пятиэтапный явный одношаговый метод численного интегрирования типа Рунге — Кутты, имеющий пятый порядок.

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

Приведённую систему уравнений удалось разрешить численно. Параметры полученной схемы (с 12-ю знаками после запятой) представлены в таблице 2.

Для подтверждения пятого порядка полученной расчётной схемы (в дальнейшем ЕК55) приводится её сравнение с шестиэтапным методом пятого порядка, обозначенным как Г1К56, при решении трёх тестовых задач Коши. Например, решалась задача

на интервале (0; 20) с постоянным шагом Л, а критерием точности служило точное значение глобальной погрешности е на конце интервала решения,

( \ 20

вычисленное, исходя из знания точного решения у{х) — -- ...

На рисунке 1 видно, что для рассмотренной задачи Коши схема М<55 оказывается даже несколько точнее, чем Ш<56.

£ КГ"

1ГГ*. 11К55 V— НК5Г, о—о—о- -+—н---►

1(1-"1 10-".

10-ч

,0-1«

к í СЦ1Т2 ОЯИ 0.128 а. 256 0.512 1.021

Рис. 1. Сравнение методов КК55 и 11X56 при решении задачи (1)

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

В § 2.1 представлен вид системы, для которого И. В. Олемским разрабо-

таны экономные методы интегрирования:

г/о = 1о{х,уо, ■.. ,у„),

у[ = Мх,Уо, ■ ■ ■ ,У1-1,У1+ъ ■ ■ ■ ,Уп), г = 1,... ,1 У', = Мх,уа, ■ ■ ■ 3 = I + 1, • ■ •

5

(2 (3 (4

хе [Х^Хк] С К, Уе- \Х0,Хк} —>НР-, в = 0,...,п.

п

/о :[*„,**] XК» —$>« = 5.

5—г п

Даны ссылки на работы, демонстрирующие различные методы в рамка: рассматриваемого подхода и их эффективность по сравнению с классически ми методами интегрирования систем ОДУ.

В § 2.2 приводится общая схема так называемого структурного метода. В предположении достаточной гладкости правой части рассматриваемо! системы приближение гя к точному решению г/,(з: + /г), я = 0,... ,п в точю х + И 6 [Хо,^.] ищется в виде:

та„

ув(х + Н) и 2а = уа(х) + в = О,..., п,

«1=1

причем кзи, ~ кзи1(к) вычисляются в строгой последовательности

¿01, ¿11, ..., ¿„1, ¿02, ¿12: •••, ¿п2, •••

по формулам

и

где

х, если {(u> = 1) A (s ^ I)},

x + cswh, если {(u> = 1) Л (s > I)} V {(u) > 1)},

/

уЛх)> если {(^ = 1) Л (s < I)},

Ys

yv(?) + если {(ад > 1) Л (s < и},

W

yv(x) + ОчптцКр, если {(ш > 1) Л (s > I/)} V {(го = 1) Л (s > I)},

ц=1

hsw, csw, Usmuii — параметры метода, h — шаг интегрирования.

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

В § 2.3 даётся описание идеи вложенных методов типа Дорманда — Прин-са. Предлагается обобщение метода на случай систем вида (2)-(4) аналогичное обобщению, рассмотренному в предыдущем параграфе. На основе анализа полученных ранее результатов касательно необходимого для достижения пятого порядка числа этапов по разным компонентам предлагается утверждение:

Теорема 2. Существует явный вложенный метод типа Дорманда — Принса интегрирования системы вида (2)-(4) пятого порядка точности с оценщиком погрешности третьего порядка, имеющий число этапов М — (7,6,... ,6), то есть, 7 этапов по основной группе (2), и по 6 этапов по компонентам групп (3) и (4), и реализующий технологию FSAL (-«First same as last», то есть использование последнего этапа текущего шага в качестве первого этапа на следующем шаге).

В третьей главе излагается теория помеченных деревьев конструирования условий порядка методов типа Рунге — Кутты применительно к системам вида (2)-(4).

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

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

Определение 1. Для СОДУ общего вида у'(х) = f(x,y) элементарным дифференциалом порядка р назовём каждое из слагаемых, входящее в р-ю производную функции у(х), выраженное через функцию f и её производные.

В § 3.3 вводится понятие помеченного дерева применительно к рассматриваемым в диссертационной работе методам.

Определение 2. Помеченными деревьями (no-англ. labelled trees) называются древовидные графы, вершины которых маркированы тем или иным образом, однозначно сопоставляемые с элементарными дифференциалами.

Описываются особенности данной реализации теории помеченных деревьев. Вводится понятие дифференцирования помеченного дерева (рис. 2).

Определение 3. Назовём дифференцированием дерева получение деревьев, соответствующих всем возможным элементарным дифференциалам, входящим в полную производную элементарного дифференциала, отвечающего данному дереву.

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

Рис. 2. Дифференцирование помеченного дерева для структурного метода

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

Наконец в § 3.5 приведена система условий пятого порядка обобщения 1етода типа Рунге — Кутты на системы вида (2)-(4).

В четвёртой главе демонстрируется преобразование полученной в предыдущей главе системы условий порядка к более простой системе с помощью прощающих предположений — дополнительных равенств, при выполнении ;оторых некоторые уравнения исходной системы становятся тождественны (руг другу. Представлен алгоритм разрешения полученной системы след-твия. Приводится частное решение системы. Полученная расчётная схема га вычислительных примерах сравнивается с классическим методом Дорман-1,а —Принса пятого порядка точности.

В § 4.1 вводятся упрощающие предположения

М/

V

)

УЗ

т,

^ ] 65ша8шег1,1 = 1 сСШ1), Й, е = 0,..., п, и/1 = 1,..., 6,

ы—ти 1

ш 1

^ ' О-зшеш^еуц — 5, в = 0, . . . , 71, и> — 2, ... ,6,

№1 = 1

Ь(>2 = = О,

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

С использованием указанных лемм, задача о поиске частного решения ис ходной системы условий порядка сведена к поиску частного решения системы следствия достаточно простой структуры связей, состоящей из 230 уравнение с 231 неизвестным.

-ь

С "> « о РС5(3)МР/

0 ' 1 /' /

Ь " У / /Ю011РШ5(4)7Е

1

1 4.1 !. Я 6 л, ¡ОЙ10 11 р

Рис. 3. Сравнительный анализ схем РС'5(3)МГ и ЕЮ11РШ5(4)7К для задачи (5)

В § 4.2 излагается алгоритм решения полученной системы следствия I общем виде. Показывается, что решение системы-следствия существует и об разует 29-параметркческое семейство. Кроме того, параллельно выводите?

конкретная расчётная схема при некотором наборе свободных параметров, обозначенная, как РС5(3)МР. В данной аббревиатуре 5 показывает порядок метода, 3 — порядок «оценщика погрешности», М — число этапов (теорема 2), Р — реализация в данной схеме идеи РБАЬ.

В § 4.3 после некоторых рассуждений о реализации построенной схемы приводится результат сравнений её вычислительных характеристик с классическим методом Дорманда — Принса пятого порядка (Б011РШ5(4)7Р) на примере решения линейной и нелинейной задач.

В частности, для задачи Коши

у[ = 2ху±у1, у'2 = 2ху3, у'з = -2х(Уг-1), у'4=Юху3у1, (5)

2/1 (0) = №(0) = у3(0) = 2/4(0) = 1,

решавшейся на интервале х € (0; 5) сравнительный анализ результатов по критерию «общее количество обращений к правой части (^пр) / глобальная погрешность (еггд10ь)-> представлен на рисунке 3.

Делается вывод о большей экономичности построенной расчётной схемы по отношению к классическому семиэтапному методу.

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

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

[1] Еремин А. С. Модификация теории помеченных деревьев для структурного метода интегрирования систем ОДУ // Вестник СПбГУ. Сер. 10.— 2009. Вып. 2.- С. 15-21.

[2] Еремин А. С. Программная реализация метода помеченных деревьев // Процессы управления и устойчивость: Труды 38-й международной научной конференции аспирантов и студентов / Под ред. А. В. Платонова, Н. В. Смирнова. - СПб —Издат С.-Петерб. ун-та-2007,- С. 159-161.

[3] Еремин А. С. Использование помеченных деревьев для вывода условий порядка структурного метода // Процессы управления и устойчивость: Труды 39-й международной научной конференции аспирантов и студентов / Под ред. Н. В. Смирнова, Г. Ш. Тамасяна. — СПб — Издат. Дом С. Петерб. гос. ун-та-2008.- С. 313-316.

[4] Еремин А. С. Вложенный метод типа Дормана — Принса для структурно разделённых систем // Процессы управления и устойчивость: Труды 40-й международной научной конференции аспирантов и студентов / Под ред. Н. В. Смирнова, Г. Ш. Тамасяна. — СПб — Издат. Дом С. Петерб. гос. ун-та-2009,- С. 160-165.

[5] Еремин А. С. Об одном вложенном методе типа Дормана — Принса. Тезисы // Системы компьютерной математики и их приложения: материалы международной конференции. — Смоленск — Изд-во СмолГУ — 2009. - С. 180-182.

[6] Eremin A. Economic Dormand-Prince type embedded fifth order method for systems of special structure. Abstract // Conference on Scientific Com-

puting, Geneva, Université de Genève, Faculté des sciences, Section de Mathématiques, June 17-20, 2009.—P. 22.

Отпечатано с готового оригинал-макета в ЦНИТ «АСТЕРИОН» Заказ № 218. Подписано в печать 11.08.2009 г. Бумага офсетная. Формат 60x84'/i6 Объем 1,25 п. л. Тираж 100 экз. Санкт-Петербург, 191015, а/я 83, (812) 275-73-00, 970-35-70

Введение

Глава 1. Использование структурных особенностей обыкновенного дифференциального уравнения

1.1. Использование независимости правой части от переменной интегрирования

1.2. 5-этанная схема 5-го порядка точности

Глава 2. Расширение явного одношагового метода типа Рун-ге — Кутты на случай систем структурно разделяющихся обыкновенных дифференциальных уравнений

2.1. Структурные особенности систем обыкновенных дифференциальных уравнений.

2.2. Метод интегрирования

2.3 Вложенные методы в рамках структурного подхода.

Глава 3. Модификация теории помеченных деревьев для структурного метода решения систем ОДУ

3.1. Производные точного решения.

3.2. Производные приближения к решению по структурному методу

3.3. Помеченные деревья

3.4. Алгоритм записи условия порядка по помеченному дереву

3.5. Условия пятого порядка структурного метода

Глава 4. Вложенный метод пятого порядка типа Дорманда —

Принса

4.1. Упрощение системы условий порядка.

4.2. Разрешение системы-следствия

4.3. Тестирование построенной расчётной схемы

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

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

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

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

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

Разработанная Дж. Бутчером абстрактная алгебраическая теория методов Рунге —Кутты открыла большие возможности для теоретического исследования их свойств и для конструирования новых высокоэффективных одношаговых алгоритмов.

В ходе исследования свойств численных методов решения СОДУ были установлены некоторые ограничения, связывающие максимально достижимый порядок получаемого приближения и количество обращений к вычислению правой части системы уравнений, или число этапов, используемых методом. Для методов типа Рунге — Кутты эти соотношения получили наименование «барьеров Бутчера». Однако в дальнейшем И. В. Олемским было обнаружено, что в случае наличия определённых структурных особенностей систем ОДУ удаётся построить методы, позволяющие получить более высокий порядок, чем это установлено упомянутыми ограничениями, по крайней мере, для некоторой части компонентов.

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

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

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

Целями диссертационной работы являются:

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

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

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

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

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

Основные положения, выносимые на защиту:

1. Построение явного одношагового пятиэтапного метода пятого порядка для автономного обыкновенного дифференциального уравнения — эффективный вариант использования структурных особенностей ОДУ.

2. Модификация теории помеченных деревьев Дж. Бутчера и Э. Хайрера для расширений явных методов типа Рунге — Кутты на случай систем ОДУ со структурным особенностями.

3. Построение нового экономичного явного вложенного метода типа Дорманда—Принса пятого порядка точности, по своим характеристикам превосходящего, чем существующие методы того же класса.

Апробация работы. Основные результаты диссертации докладывались и обсуждались на XXXVIII, XXXIX и ХЬ научных конференциях «Процессы управления и устойчивость» факультета прикладной математики — процессов управления (г. Санкт-Петербург, апрель 2007, 2008 и 2009 гг.) и на международной конференции «Conference on Scientific Computing», посвящённой 60-летию профессора Э. Хайрера (г. Женева, Швейцария, июнь 2009 г.).

Публикации. Материалы диссертации опубликованы в 5 печатных работах, из них 1 статья в журнале из списка рекомендуемых ВАК [1], 3 статьи в сборниках трудов конференций [2-4] и тезисы 1 доклада [5].

Личный вклад автора

Структура и объем диссертации. Диссертация состоит из введения, 4 глав, 13 параграфов, заключения и списка литературы. Объём диссертации составляет 91 страницу. Список литературы включает 25 наименований.

Заключение

Рассмотренные в диссертационной работе обыкновенные дифференциальные уравнения и системы ОДУ специального вида не исчерпывают, конечно, всех практически интересных и важных задач, однако, достаточно часто встречаются системы, правые части которых не зависят от некоторых из искомых функций. Применение к ним алгоритма, описанного в [11], позволяет эффективно использовать для их решения структурные методы, и в том числе разработанный в четвёртой главе настоящей диссертационной работы метод с автоматическим управлением длиной шага. Явность построенных методов не позволяет применять их для решения жёстких задач или систем дифференциально-алгебраических уравнений (см. напр. [24, 25]). Но в некоторых случаях системы ОДУ удаётся разделить на жёсткую и нежёсткую части. Для интегрирования последней может использоваться разработанный метод.

В первой главе строится пятиэтапный метод пятого порядка. Основанные на той же идее выкладки дадут для шестого порядка систему из 19 уравнений (относительно 21 неизвестного параметра в случае шестиэтапного метода), а для седьмого — из 28 уравнений (при 28 неизвестных для семиэтапного метода). Найти решения этих систем пока не удалось, но и доказательства их отсутствия также нет. И хотя область применение таких методов весьма узка, получение такого результата дало более глубокое понимание теоретических аспектов методов типа Рунге — Кутты, их конструирования и особенностей формирования условий порядка.

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

1. Еремин А. С. Модификация теории помеченных деревьев для структурного метода интегрирования систем ОДУ // Вестник СПбГУ. Сер. 10.— 2009. Вып. 2. — С. 15-21.

2. Еремин,А. С. Программная реализация метода помеченных деревьев // Процессы управления и устойчивость: Труды 38-й международной научной конференции аспирантов и студентов / Под ред. А. В. Платонова, Н. В. Смирнова. — 2007.— С. 159-161.

3. Еремин А. С. Об одном вложенном методе типа Дормана — Принса. Тезисы // Системы компьютерной математики и их приложения: материалы международной конференции. — 2009. — С. 180-182.

4. Крылов В. И. Приближенное вычисление интегралов. — Москва: Наука, 1967.

5. Butcher J. С. On Runge Kutta processes of high order // J. Austral. Math. Soc. - 1964. - Vol. IV, part. 2. — Pp. 179-194.

6. Butcher J. С. On the attainable order of Runge Kutta methods // Math, of Сотр. - 1965. - Vol. 19. - Pp. 408-417.

7. Butcher J. C. The non-existance of ten stage eight order explicit Runge -Kutta methods // BIT. 1985. - Vol. 25. - Pp. 521-540.

8. Хайрер Э., Нерсётт С., Ваннер Г. Решение обыкновенных дифференциальных уравнений. Нежёсткие задачи / Пер. с англ. И. А. Кульчицкой, С. С. Филиппова под ред. С. С. Филиппова. — Москва: Мир, 1990.

9. Олемской И. В. Модификация алгоритма выделения структурных особенностей // jВести. С.-Петерб. ун-та, Сер. 10.— 2006.— Т. 2.— С. 46-54.

10. Олемской И. В. Численный метод интегрирования систем обыкновенных дифференциальных уравнений // Математические методы анализа управляемых процессов. Л.,.— 1986.— С. 157-160.

11. Олемской И. В. Экономичная расчетная схема четвертого порядка точности численного интегрирования систем специального вида // Процессы управления и устойчивость. Тр. XXX научн. конф. СПб.: НИИ Химии СПбГУ. 1999. - С. 134-143.

12. Олемской И. В. Структурный подход в задаче конструирования явных одношаговых методов // Журнал вычислительной математики и математической физики. — 2003. — Т. 43. №7. — С. 961-974.

13. Олемской И. В. Четырехэтапный метод пятого порядка точности численного интегрирования систем специального вида // Журнал вычислительной математики и математической физики. — 2002. — Т. 42. №8. — С. 1179-1190.

14. Бахвалов Н. С. Численные методы. — Москва: Наука, 1975.

15. Fehlberg Е. Calssical fifth-, sixth-, seventh- anci eighth order Runge Kutta formulas with step size control // NASA Technical Report 287. — 1968.

16. Dormand J. R., Prince P. J. New Runge Kutta algorithms for numerical simulation in dynamical astronomy // Celestial Mechanics. — 1978. — Vol. 18. - Pp. 223-232.

17. Dormand J. R., Prince P. J. A family of embedded Runge Kutta formulae Ц J. Comput. Appl Math. — 1980. — Vol. 6. — Pp. 19-26.

18. Dormand J. R., El-Mikkawy M. E. A., Prince P. J. Families of Runge -Kutta Nystrom formulae // Journal of Numerical Analysis. — 1987. — Vol. 7. - Pp. 235-250.

19. Butcher J. C. Coefficients for the study of Runge Kutta integration processes 11 J. Austral. Math. Soc. — 1963. - Vol. 3. — Pp. 185-201.

20. Hairer E. Order conditions for numerical methods for partitioned ordinary differential equations // Numer. Math. — 1981. —Vol. 36. — Pp. 431-445.

21. Арушанян А. Б., Залеткип С. Ф. Численное решение обыкновенных дифференциальных уравнений на Фортране. — Москва: Изд-во МГУ,

22. Хайрер Э., Ваннер Г. Решение обыкновенных дифференциальных уравнений. Жёсткие и дифференциально-алгебраические задачи / Пер. с англ. под ред. С. С. Филиппова. — Москва: Мир, 1999.

23. Вгепап К. Е., Campbell S. L., Petzold L. R. Numerical solution of initial-val1990.ue problems in differential-algebraic equations. — Philadelphia: SIAM, 1996.