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

• Еремин, Алексей Сергеевич
• кандидат физико-математических наук
• 2009

Оглавление диссертации кандидат физико-математических наук Еремин, Алексей Сергеевич

Введение

Глава 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 неизвестных для семиэтапного метода). Найти решения этих систем пока не удалось, но и доказательства их отсутствия также нет. И хотя область применение таких методов весьма узка, получение такого результата дало более глубокое понимание теоретических аспектов методов типа Рунге — Кутты, их конструирования и особенностей формирования условий порядка.

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

Список литературы диссертационного исследования кандидат физико-математических наук Еремин, Алексей Сергеевич, 2009 год

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.