Содержание к диссертации
Введение
Глава 1. Использование структурных особенностей обыкновенного дифференциального уравнения 9
1.1. Использование независимости правой части от переменной интегрирования 9
1.2. 5-этапная схема 5-го порядка точности 15
Глава 2. Расширение явного одношагового метода типа Рунге — Кутты на случай систем структурно разделяющихся обыкновенных дифференциальных уравнений 21
2.1. Структурные особенности систем обыкновенных дифференциальных уравнений 21
2.2. Метод интегрирования 23
2.3. Вложенные методы в рамках структурного подхода 25
Глава 3. Модификация теории помеченных деревьев для структурного метода решения систем ОДУ 30
3.1. Производные точного решения 31
3.2. Производные приближения к решению по структурному методу 33
3.3. Помеченные деревья 38
3.4. Алгоритм записи условия порядка по помеченному дереву . 40
3.5. Условия пятого порядка структурного метода 43
Глава 4. Вложенный метод пятого порядка типа Дорманда — Принса 68
4.1. Упрощение системы условий порядка 68
4.2. Разрешение системы-следствия 76
4.3. Тестирование построенной расчётной схемы 82
Заключение 87
Литература 89
- Использование независимости правой части от переменной интегрирования
- Структурные особенности систем обыкновенных дифференциальных уравнений
- Производные приближения к решению по структурному методу
- Тестирование построенной расчётной схемы
Введение к работе
Актуальность темы. Практически все процессы в природе и жизни общества описываются с помощью дифференциальных уравнений. Сложность возникающих в математических моделях начальных и краевых задач не позволяет получать их аналитические решения. Численные методы интегрирования систем обыкновенных дифференциальных уравнений востребованы в любой области математики, имеющей дело с моделированием процессов — физических или социальных.
Последние пятьдесят лет можно охарактеризовать как период, в течение которого классические методы численного решения обыкновенных дифференциальных уравнений (методы Адамса и другие многошаговые методы, методы Рунге—Кутты (РК), методы экстраполяции), приспособленные и развитые для ручного счета, пересматривались в соответствии с требованиями и новыми возможностями, продиктованными бурно развивающимися технологиями машинного счета.
Постоянному наращиванию мощностей ЭВМ соответствовала и общая тенденция расширения классов решаемых задач. Новые возможности решения более трудоёмких и сложных задач породили и массу проблем, связанных с устойчивостью и аппроксимацией разрабатываемых высокоэффективных и надежных алгоритмов численного интегрирования систем обыкновенных дифференциальных уравнений (СОДУ).
В этот период были выполнены фундаментальные исследования по устойчивости численного решения обыкновенных дифференциальных уравнений (ОДУ), теории конструирования и реализации методов интегрирования.
Так, в классе одношаговых методов за это время и способ вывода условий порядка (с помощью графического представления производных точного решения и приближения к нему в виде помеченных деревьев), и конструиро-
вание (с использованием глубоко проработанной методики применения упрощающих соотношений) расчетных схем эволюционировали в основном под влиянием работ Дж. Бутчера, Э. Хайрера, Г. Ваннера.
Разработанная Дж. Бутчером абстрактная алгебраическая теория методов Рунге — Кутты открыла большие возможности для теоретического исследования их свойств и для конструирования новых высокоэффективных одношаговых алгоритмов.
В ходе исследования свойств численных методов решения СОДУ были установлены некоторые ограничения, связывающие максимально достижимый порядок получаемого приближения и количество обращений к вычислению правой части системы уравнений, или число этапов, используемых методом. Для методов типа Рунге —Кутты эти соотношения получили наименование «барьеров Бутчера». Однако в дальнейшем И. В. Олемским было обнаружено, что в случае наличия определённых структурных особенностей систем ОДУ удаётся построить методы, позволяющие получить более высокий порядок, чем это установлено упомянутыми ограничениями, по крайней мере, для некоторой части компонентов.
Такой структурной особенностью является разделение уравнений в группы по признаку зависимости производных от искомых функций. Полученные для подобных систем методы по части, а в некоторых случаях по всем структурным группам имеют преимущество перед классическими методами интегрирования СОДУ по количеству затрат на получение численного приближения к решению на одном шаге. Системы, подобного вида встречаются в математических моделях многих процессов — в небесной механике (например, ограниченная задача трёх тел), в физике высоких энергий и т. д.
Применение имеющихся способов конструирования методов типа Рунге — Кутты к этим методам по ряду причин невозможно, и модификация теории помеченных деревьев на случай структурного метода позволила бы суще-
ственно упростить процесс их разработки.
Впервые в работах Р. Мерсона, Ф. Ческино, Дж. Зонневельда была использована идея, которая легла в основу нового семейства одношаговых методов — вложенных. Ими занимались Р. Ингланд, Д. Сарафян и особенно глубоко Э. Фельберг. Впоследствии первоначальная идея оценки погрешности с помощью расчётных схем разных порядков была пересмотрена Дж. Р. Дормандом и П. Дж. Принсом. Методы, построенные последними, показали превосходные результаты при реализации алгоритмов с автоматическим выбором длины шага интегрирования. Весьма логичным расширением нового класса методов, использующих структурные особенности СОДУ, было бы построение вложенных методов, обладающих теми же преимуществами и вследствие этого являющихся более экономичными по сравнению с имеющимися на данный момент вложенными одношаговыми методами.
Целями диссертационной работы являются:
исследование структурных особенностей обыкновенных дифференциальных уравнений и систем обыкновенных дифференциальных уравнений на предмет возможности построение новых экономичных численных методов интегрирования,
модификация теории помеченных деревьев для применения к расширениям классических методов типа Рунге — Кутты на случай интегрирования систем, имеющих структурные особенности,
построение явного одношагового вложенного метода типа Дорманда — Принса пятого порядка интегрирования систем специального вида, более экономного с точки зрения вычислительных затрат, чем классический метод Дорманда —Принса того же порядка точности.
Методы исследования. Для решения поставленных задач использова-
лись методы численного анализа, решения систем алгебраических уравнений, как численные, так и аналитические, применялась методика упрощающих предположений построения методов типа Рунге —Кутты, методы теории графов и алгоритмы на графах.
Научная новизна диссертационной работы состоит в получении явного одношагового пятиэтаппого метода пятого порядка для скалярного ОДУ с особенностью; в разработке алгоритма формирования условий порядка для расширений методов решения СОДУ типа Рунге — Кутты на случай систем со структурной особенностью; в конструировании явного одношагового вложенного метода типа Дорманда—Принса пятого порядка, по своим качествам превосходящего имеющиеся методы того же порядка.
Практическая ценность диссертационной работы состоит в том, что полученный алгоритм формирования условий порядка структурных методов может быть использовании для разработки новых методов, использующих эту идею, в особенности, методов высоких порядков (6-го и выше). Кроме того, построенный метод типа Дорманда —Принса является вполне конкурентоспособным и может быть с успехом применён для решения многих практически интересных задач, структура которых позволяет записать их в том виде, для которого разработан данный метод.
Основные положения, выносимые на защиту:
Построение явного одношагового пятиэтаппого метода пятого порядка для автономного обыкновенного дифференциального уравнения — эффективный вариант использования структурных особенностей ОДУ.
Модификация теории помеченных деревьев Дж. Бутчера и Э. Хайрера для расширений явных методов типа Рунге — Кутты на случай систем ОДУ со структурным особенностями.
Построение нового экономичного явного вложенного метода типа Дор-
манда —Принса пятого порядка точности, по своим характеристикам превосходящего, чем существующие методы того же класса.
Апробация работы. Основные результаты диссертации докладывались и обсуждались на 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. исследование структурных особенностей обыкновенных дифференциальных уравнений и систем обыкновенных дифференциальных уравнений на предмет возможности построение новых экономичных численных методов интегрирования, 2. модификация теории помеченных деревьев для применения к расширениям классических методов типа Рунге — Кутты на случай интегрирования систем, имеющих структурные особенности, 3. построение явного одношагового вложенного метода типа Дорманда — Принса пятого порядка интегрирования систем специального вида, более экономного с точки зрения вычислительных затрат, чем классический метод Дорманда —Принса того же порядка точности. Научная новизна диссертационной работы состоит в получении явного одношагового пятиэтапного метода пятого порядка для скалярного ОДУ с особенностью; в разработке алгоритма формирования условий порядка для расширений методов решения СОДУ типа Рунге — Кутты на случай систем со структурной особенностью; в конструировании явного одношагового вложенного метода типа Дорманда —Принса пятого порядка, по своим качествам превосходящего имеющиеся методы того же порядка. Практическая ценность. Практическая ценность диссертационной работы состоит в том, что полученный алгоритм формирования условий порядка структурных методов может быть использовании для разработки новых методов, использующих эту идею, в особенности, методов высоких порядков (6-го и выше). Кроме того, построенный метод типа Дорманда —Принса является вполне конкурентоспособным и может быть с успехом применён для решения многих практически интересных задач, структура которых позволяет записать их в том виде, для которого разработан данный метод. Основные положения, выносимые на защиту: 1. Построение явного одношагового пятиэтапного метода пятого порядка для автономного обыкновенного дифференциального уравнения — эффективный вариант использования структурных особенностей ОДУ. 2. Модификация теории помеченных деревьев Дж. Бутчера и Э. Хайрера для расширений явных методов типа Рунге —Кутты на случай систем ОДУ со структурным особенностями. 3. Построение нового экономичного явного вложенного метода типа Дорманда—Принса пятого порядка точности, по своим характеристикам превосходящего, чем существующие методы того же класса. Апробация работы. Основные результаты диссертации докладывались и обсуждались на XXXVIII, XXXIX и XL научных конференциях «Процессы управления и устойчивость» факультета прикладной математики — процессов управления (г. Санкт-Петербург, апрель 2007, 2008 и 2009 гг.) и на международной конференции «Conference on Scientific Computing», посвященной 60-летию профессора Э. Хайрера (г. Женева, Швейцария, июнь 2009 г.). Публикации. Материалы диссертации опубликованы в 5 печатных работах, из них 1 статья в журнале из списка рекомендуемых ВАК [1], 3 статьи в сборниках трудов конференций [2-4] и тезисы 1 доклада [5]. Личный вклад автора Структура и объем диссертации. Диссертация состоит из введения, 4 глав, 13 параграфов, заключения и списка литературы. Объём диссертации составляет 91 страницу. Список литературы включает 25 наименований.
Структурные особенности систем обыкновенных дифференциальных уравнений
Здесь и в дальнейшем индексы і {1,...,/}, j {/ + l,...,n}, г {1,..., і - 1}, j {/ + 1,..., j - 1} параметров метода aw, cJW, biw, bJW, diwiwi, aiwjWl, djwiwi, ajw3wi носят характер признака, Так, индекс на первой позиции является признаком принадлежности параметров к структурно разделённым группам уравнений системы (2.1)—(2.3): 0 — к нулевой (2.1), і — к первой (2.2), j — ко второй (2.3). Принадлежность же к группам аргументов вектор-функции, стоящей в правой части системы, определяется индексом на третьей позиции: 0 — к нулевой, i: г — к первой, j, j — ко второй соответственно. Использование ограничений (2.10) существенно упрощает (не в ущерб экономичности) построение условий порядка, вывод, представление и реализацию расчетных схем. Руководствуясь этими соображениями, изначально будем предполагать выполнение равенств (2.10).
Практическая реализация полученных в [12-15] экономичных схем интегрирования требует для их использования эффективного алгоритма автоматического выбора шага, Одним из вариантов оценки локальной погрешности является использование правила Рунге, то есть ведение расчёта на двух разных сетках [16], однако это гораздо более трудоёмкий процесс, чем использование так называемых вложенных методов.
Одним из вариантов вложенных методов являются так называемые методы типа Фельберга [10, 17]. Их идея заключается в том, что в точке х + h получаются два приближения разных порядков, и в качестве итогового значения берётся результат меньшего порядка, а результат большего служит для оценки локальной погрешности. Однако, забегая вперёд, скажем, что в нашем случае будут построены методы пятого и третьего порядков, а поэтому для увеличения точности получаемых приближений мы изначально использовали другой подход.
Для вложенных методов типа Дорманда — Принса [18-20] характерно, что члены погрешности для результата старшего порядка минимизированы и он принимается в качестве искомого приближения, а результат младшего порядка используется в алгоритме управления величиной шага.
Параметры М = (то,..., тп)-этапного вложенного q{p) метода интегрирования системы (2.1)—(2.3) должны обеспечивать вычисление приближения к решению zs, s = 0,... , п, по расчетной схеме порядка q (ys(x + h) — zs = 0(hq+1)), а для оценки погрешности полученного приближения вычисление по схеме порядка р: именуемой «оценщик погрешности». Причем здесь рассматриваются «оценщики погрешности», для которых р q7 то есть, разница двух приближений zs — zs используется для оценки величины контрольного члена ряда Тейлора для погрешности (формально это не является оценкой погрешности, но позволяет судить о поведении решения и эффективно управлять длиной шага).
Один из наиболее известных вложенный метод пятого порядка такого типа — семиэтапный метод Дорманда — Принса [10] с оценщиком «погрешности» четвертого порядка — DORPRI5(4)7F. Аббревиатура метода сообщает о типе метода (DORPRI — Дорманда —Принса), о порядке метода для вычисления приближения к решению — «5», о порядке оценщика «погрешности» — «(4)», о числе этапов — «7», а также об использовании идеи FSAL(First Same As Last) «F»: последний этап на текущем шаге используется в качестве первого на следующем.
Для вложенных методов используем уже устоявшуюся (см. [10, 18, 19]) форму их табличного покомпонентного представления, несколько её видоизменив.
Мы же будем строить метод, вектор числа этапов которого М = (7,6,..., 6). то есть, метод будет иметь 7 этапов по основной группе (2.1), и по 6 этапов по компонентам групп (2.2) и (2.3). При этом, мы потребуем, чтобы данный метод имел пятый порядок, а также, чтобы в него был вложен метод-оценщик третьего порядка точности. Дополнительно, попробуем реализовать в этом методе идею FSAL. Теорема 2.1. Существует явный М = (7 ,6,... ,6) -этапный вложенный метод типа Дорманда — Принса интегрирования системы вида (2.1)-(2.3) пятого порядка точности с .оценщиком погрешности» третьего порядка, реализующий технологию FSAL. Схема данного метода представлена в таблице 2.2 в общем виде. Доказательству данной теоремы по сути посвящены две следующие главы диссертационной работы, в которых строится указанный метод. Стоит сказать несколько слов об особенностях реализации вложенного метода, имеющего разные по числу этапов вычислительные схемы для разных компонентов. В методе, схема которого дана в таблице 2.2, приближение пятого порядка строится по (6,5,... , 5) этапам, а после этого для получения оценки строятся ко7, kiQ и kjQ строго в указанном порядке. В добавок к этому, использование идеи FSAL из-за неравенства Cj\ нулю также несколько отличается от классического метода. Именно поэтому в последних строках блоков (ijwOni Ujwi/л и djwj/л на один параметр больше, чем в последних строках двух верхних подтаблиц. Следующая глава посвящена выводу тех ограничений, которым должны удовлетворять коэффициенты метода для обеспечения пятого порядка точности.
Производные приближения к решению по структурному методу
Порядком р(т) дерева г называют количество его вершин. Эта величина совпадает с порядком, который может быть достигнут методом при выполнении всех условий, соответствующих деревьям данного порядка. На рис. 3.1 изображено дерево четвёртого порядка, которое соответствует элементарному дифференциалу
По дереву однозначно выписывается одно условие порядка. Оригинальная теория [10, 21, 22] присваивала вершинам индекс, соответствующий индексу суммирования той части элементарного дифференциала, которой отвечала вершина графа.
Однако мы будем понимать «помеченность» вершин деревьев несколько иначе. Во-первых, индексы суммирования взаимозаменяемы, и сами по себе не влияют на форму элементарного дифференциала и связанного с ним условия порядка, поэтому необходимости в такой индексации вершин нет. Во-вторых, в случае структурного метода мы сталкиваемся с тремя группами уравнений, и каждой группе соответствуют свои индексы параметров метода. Именно индексами 0, і и j будем «помечать» вершины. Используя термины «отец», «сын», «потомок» для вершин древовидных графов, удобно назвать индекс, помечающий вершину, её «именем», а «имя отца» назвать «отчеством».
Определение 3.2. Назовём дифференцированием, дерева получение деревьев, соответствующих всем возможным, элементарным, дифференциалам, входящим, в полную производную элементарного дифференциала, отвечающего данному дереву.
Применительно к структурному методу мы должны рассмотреть три возможных «имени» вершин и ещё один тип вершины, соответствующий дифференцированию по независимой переменной х. Такую вершину назовём «безымянной». Безымянные вершины могут быть только конечными, то есть, не могут иметь «сыновей». Это следует из свойств дифференцирования. Кроме того, корень, даже без «сыновей», тоже всегда имеет «имя».
Таким образом, при дифференцировании дерева можно получить от 4 до 4 х р(т) новых деревьев. На рисунке 3.2 приведён пример дифференцирования дерева четвёртого порядка, дающего 12 различных производных деревьев. «Безымянной» вершине соответствует точка, остальным — их «имена». Отметим особо, что при использовании стандартных упрощающих предположений вида (3.17) деревья, различающиеся только «именами» конечных вершин, дают одинаковые условия порядка (количество условий в таблице приведено с учётом выполнения этих соотношений). Соответственно, первым этапом конструирования структурного метода порядка q является получение всех различных помеченных деревьев до по На втором этапе по полученным деревьям выписывается система условий порядка конструируемого метода. В принципе условия порядка для всех структурных групп имеют похожую структуру. Различия наблюдаются только в границах изменения индексов суммирования, что вызвано априорным равенством нулю некоторых параметров метода. Условия порядка любого метода, будь то явный, полуявный или метод более сложной конструкции, могут быть получены из условий порядка неявного метода. Алгоритм записи условий порядка тем самым может быть разбит на последовательные этапы: 1. Запись выражения на параметры метода без расстановки границ изменения индексов суммирования — часть общая для всех методов типа Рунге — Кутты; 2. Расстановка границ изменения индексов суммирования — индивидуальная для каждой расчётной схемы. Первый этап заключается в последовательной записи сумм параметров метода по следующему правилу: корню соответствует суммирование параметров bSW7 s = О,..., n, w — индекс суммирования, все остальные суммы вложены в эту сумму; вершине, имеющей «имя» е, соответствует суммирование параметров (i-swewi-, где s — «отчество» данной вершины, w — индекс суммирования «отцовской» суммы, W\ — индекс суммирования данной суммы; «безымянной» вершине соответствует включение в качестве множителя в «отцовскую» сумму параметра csw, где sw — последние (или единственные) два индекса параметра объемлющей суммы. Пример. Рассмотрим два дерева (рис. 3.3). Они соответствуют элементарным дифференциалам пятого порядка.
Тестирование построенной расчётной схемы
По своим характеристикам (число этапов, порядок точности на шаге) полученная в рамках структурного подхода схема PC5(3)MF экономичнее DORPRI5(4)7F [10]. Следует отметить, однако, что на практике реализация схемы PC5(3)MF на базе стандартного алгоритма формирования шага в ряде случаев приводит к отказу от использования на следующем шаге вычисленных на последнем этапе текущего значений kjQ. Данный недостаток несколько снижает эффективность предложенной схемы, но даже с учётом этого он по своим характеристикам превосходит DORPRI5(4)7F. Кроме того, стоит иметь в виду, что существуют две возможности модификации алгоритма реализации схемы PC5(3)MF, повышающие рентабельность её применения.
Первая — кардинальная. Так как вычисленные kjQ фактически (в силу изменения шага) не могут быть использованы в качестве первого этапа на следующем шаге (не реализуется в полной мере идея FSAL), то возникает желание отказаться от их вычисления и формировать величину следующего шага только на основе оценки «погрешности» по общей и по і-й группам (возможность контроля величины шага по части компонентов обсуждалась, например, в [23]). Формально это означает, что число этапов схемы изменится на М = (7, б,..., б, 5 ..., 5), то есть, составит 7 по общей группе, 6 — по і-й, и 5 — j -й группе.
Вторая — компромиссная. Имея в виду повышение эффективности работы рассматриваемого метода, можно модифицировать стандартный алгоритм формирования величины шага интегрирования путём введения интервала постоянства шага: текущий шаг остаётся неизменным для продолжения интегрирования при выполнении неравенства а (tol/err)1/(- +1 ) /3, где tol — допустимая погрешность на шаге, a err — оценка полученной на данном шаге погрешности.
Для подтверждения большей экономичности построенного метода по сравнению с формальным распространением метода DORPRI5(4)7F на систему обыкновенных дифференциальных уравнений со структурной особенностью (2.1)—(2.3) решались две задачи Коши с системами, приводимыми к рассматриваемому виду.
С точки зрения структурных особенностей эта задача содержит одно уравнение общей группы (уі), одно уравнение группы і (2/2) и два уравнения Сравнительный анализ результатов по критерию «общее количество обращений к правой части (Л пр) / глобальная погрешность (егг5/0ь)» представлен на рисунке 4.2.
Итак, на основе сравнения видно, что при одном и том же количестве вычислительных затрат схема PC5(3)MF даёт большую точность, или, что то же самое, обеспечивает ту же точность при меньших затратах. Соответственно, при решении задач, допускающих применение явных методов, использование нового разработанного в диссертационной работе метода позволяет ускорить вычислительный процесс. При этом, алгоритм, изложенный в [11], позволяет привести любую систему к виду, подходящему для применения нового метода, который в худшем случае будет считать так же, как и стандартный метод Дорманда — Принса.
Рассмотренные в диссертационной работе обыкновенные дифференциальные уравнения и системы ОДУ специального вида не исчерпывают, конечно, всех практически интересных и важных задач, однако, достаточно часто встречаются системы, правые части которых не зависят от некоторых из искомых функций. Применение к ним алгоритма, описанного в [11], позволяет эффективно использовать для их решения структурные методы, и в том числе разработанный в четвёртой главе настоящей диссертационной работы метод с автоматическим управлением длиной шага. Явность построенных методов не позволяет применять их для решения жёстких задач или систем дифференциально-алгебраических уравнений (см. напр. [24, 25]). Но в некоторых случаях системы ОДУ удаётся разделить на жёсткую и нежёсткую части. Для интегрирования последней может использоваться разработанный метод.
В первой главе строится пятиэтапный метод пятого порядка. Основанные на той же идее выкладки дадут для шестого порядка систему из 19 уравнений (относительно 21 неизвестного параметра в случае шестиэтапного метода), а для седьмого — из 28 уравнений (при 28 неизвестных для семиэтапного метода). Найти решения этих систем пока не удалось, но и доказательства их отсутствия также нет. И хотя область применение таких методов весьма узка, получение такого результата дало более глубокое понимание теоретических аспектов методов типа Рунге —Кутты, их конструирования и особенностей формирования условий порядка.
