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

на правах рукописи 004613606 . 1

Хрусталева Екатерина Юрьевна

КОЛЛОКАЦИОННЫЕ МЕТОДЫ СО СТАРШИМИ ПРОИЗВОДНЫМИ И НЕЯВНАЯ ЭКСТРАПОЛЯЦИЯ ЧИСЛЕННОГО РЕШЕНИЯ

Специальность: 05.13.18 — математическое моделирование, численные методы и комплексы программ

Автореферат

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

2 5 НОЯ 2010

Ульяновск - 2010

004613606

Работа выполнена на кафедре «Информационных технологий» в Государственном образовательном учреждении высшего профессионального образования Ульяновский государственный университет.

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

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

доктор физико-математических наук, доцент Куликов Геннадий Юрьевич

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

доктор физико-математических наук, профессор Кузнецов Евгений Борисович

ГОУ ВПО Ульяновский государственный технический университет

Защита состоится «24» ноября 2010 года в

пзо

часов на заседании

диссертационного совета Д 212.278.02 при Ульяновском государственном университете по адресу: г. Ульяновск, ул. Набережная р. Свияги, 106, корп. 1, ауд. 703.

С диссертацией можно ознакомиться в научной библиотеке Ульяновского государственного университета, с авторефератом - на сайте ВУЗа http://www. uni. ulsu. ru.

Автореферат разослан « 2.2. » О I^TQ^? ^ 2010 года.

Просьба направлять отзыв на автореферат в одном экземпляре, заверенном печатью организации по адресу: 432000, г.. Ульяновск, ул. Л.Толстого, д. 42, УлГУ, Управление научных исследований.

\

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

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

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

x'(t) = g(t,x(t)), te{0,T], (la)

z(0) = x\ (16)

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

В настоящее время к наиболее перспективным алгоритмам численного решения задачи Коши для ОДУ можно отнести экстраполяци-онные методы. Общая теория экстраполяционных методов, использующих неявные одношаговые схемы, была впервые предложена Куликовым Г.Ю.1 Наряду с хорошо изученными стандартными одношаговыми методами Рунге-Кутты в качестве опорных для построения экстраполяционных схем, можно предложить сравнительно новые одношаговые методы Рунге-Куттьг, использующие старшие производные (см., например, Аульченко С.М., Латыпов А.Ф., Никуличев Ю.В.2, Куликов Г.Ю.,

'Kulikov G.Yv. On implicit extrapolation methods for ordinary differential equations// Russian Journal of Numerical Analysis and Mathematical Modelling. — 2002. — V. 17, № 1. - P. 41-69.

2Аульченко C.M., Латыпов А.Ф., Никуличев Ю.В. Метод численного интегрирования систем обыкновенных дифференциальных уравнений с использованием интерполяционных полиномов Эрмита// Журнал вычислительной математики и математической физики. - 1998. - Т. 38, № 10. - С. 1665-1670.

Меркулов А.И.3, Fehlberg Е. 4, Kastlunger К.Н.'\ N0rsett S.P.G). Однако, исследования в этой области пока достаточно ограничены, а определение условий симметричности таких методов и использование их в качестве базовых для построения экстраполяции не изучалось вовсе.

Далее следует отмстить, что важнейшим этапом в эффективной реализации любого численного метода для интегрирования обыкновенных дифференциальных уравнений является разработка механизма автоматического управления размером шага с целью обеспечения требуемой точности вычисления за минимальное (или приемлемое) время. Дополнительным преимуществом экстраполяционных методов является возможность автоматического подбора оптимальных размера шага и порядка в каждой точке сетки. Вопрос о надежной и достоверной оценке точности численного решения ОДУ неразрывно связан с проблемой оценки глобальной ошибки, которой посвящено достаточно большое число работ. В то время как обсуждению алгоритмов автоматического контроля глобальной ошибки уделено значительно меньше внимания. Можно указать лишь относительно небольшое количество статей, так или иначе затрагивающих эту тематику: Новиков Е.А.7, Dahlquist G.8, Lindberg В.9, Skeel R.D.10, Stetter H.J.n. А важное преимущество экстраполяционных методов, позволяющее управлять не только размером шага, но и порядком самого

'Куликов Г.Ю., Меркулов А.И. Об одношаговых коллокационных методах со старшими производными для решения обыкновенных дифференциальных уравнений// Журнал вычислительной математики и математической физики. — 2004. — Т. 44, № 10. - С. 1782-1807.

4Fehlberg Е. New high-order Runge-Kutta formulas with step size control for systems of first and second order differential equations// ZAMM. 1964. — V. 44, Sonderheft — P.T17-T19.

5Kastuinc;er K.H., Wanner G. Runge-Kutta processes with multiple nodes// Computing. - 1972. - V. 9. - P. 9-24.

6N0rsrtt S.P. One-slep methods of Hermite type for numerical integration of stiff systems,// BIT. - 1974. - V. 14. - R 63-77.

'Новиков Е.Л. Оценка глобальной ошибки Л-устойчивых методов решения жестких систем// Доклады академии наук. — 1995. — Т. 343, № 4. — С. 452-455.

"Dahlquist G. On the control of the global error in stiff initial value problems// Lecture Notes in Mathematics. — Berlin-New York: Springer, 1982. - V. 912. — P. 38-49.

sLwdberc B. Characterization of optimal stepsize sequences for methods for stifi differential equations// SIAM Journal on Numerical Analysis. — 1977. — V. 14, Xs 5. — P. 859-887.

10Skeel R.D. Thirteen ways to estimate global error// Numerischc Mathematik. — 1986. - V. 48. - P. 1-20.

"Stetter H.j. Local estimation of the global discretization error// SIAM Journal on Numerical Analysis. - 1971. - V. 8. - P. 512-523.

метода, практически не используется.

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

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

• разработка алгоритмов неявного локально-глобального управления порядком и шагом экстраполяционных методов;

• исследование свойств одношаговых методов Рунге-Кутты, использующих старшие производные;

• эффективная реализацию разработанных в диссертации алгоритмов с использованием новых упрощенных итераций Ньютона;

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

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

Научная новизна. Все основные результаты настоящей диссертации являются новыми и состоят в следующем:

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

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

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

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

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

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

1. Методика построения присоединенных и симметричных коллокаии-онных методов со старшими производными, формулы для вычисления коэффициентов таких методов.

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

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

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

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

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

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

Апробация работы. Результаты диссертации докладывались и обсуждались: на пятой международной научно-технической конференции «Математическое моделирование физических, экономических, технических, социальных систем и процессов» (Ульяновск, 2003), на XXVI конференции молодых ученых механико-математического факультета МГУ им. М.В. Ломоносова (Москва, 2004), на 4th International Conference on Computer Science (Krakow, Poland, 2004).

Личный вклад автора. Постановка задач осуществлялась совместно с научным руководителем, д.ф.-м.н. Г.Ю. Куликовым, теоретические положения, проведение расчетов и анализ полученных результатов выполнены автором самостоятельно.

Публикации. По теме диссертации опубликовано 10 работ, в том числе 3 в рецензируемых научных изданиях, рекомендованных ВАК, их список помещен в конце автореферата.

Структура диссертации. Диссертация объемом 118 страниц состоит из введения, четырех глав, заключения, списка литературы (162 наименования) и приложения. Работа включает 49 таблиц и 20 рисунков.

Содержание работы

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

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

В параграфе 2.1 рассматривается модификация известного алгоритма,

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

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

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

12Хайрер Э., Нерсетт С., Ваннер Г. Решение обыкновенных дифференциальных уравнений. Нежесткие задачи. —М.: Мир, 1990.

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

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

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

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

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

Итак, введем на отрезке [О, Т] произвольную неравномерную сетку

wT = {ffc+i =tk + n,k = 0,1,K-l,t0 = 0,tK = T}

и обозначим через т диаметр сетки wT, т.е. г = {тк}-

Тогда одношаговый метод вида

"Kulikov G.Yu. A local-global version of a stepsize control for Runge-Kutta methods// Korean Journal of Computational and Applied Mathematics. — 2000. — V. 7, № 2. — P. 289-318

Находим Хк+иФн-д-гМ,

Находим тк+ихм,Фз+я-2^к+Ц,Ф,+,-1^к+1>

Вычисляем фв+д~ 3(^+1)

Вычисляем Д

Вычисляем ^+,-2(^+1)

Вычисляем &Ф,+д-2(Ък+1)

9 + +; Вычисляем Л^

Принимаем х/ь+ь т/с+ь Вычисляем А^г

Т/к+Ъ-Л^ег

Рис. 1: Схема неявного локально-глобального контроля точности переменного порядка

hi = tjt + Tkd, (2a)

s*« = z/fc+ Eoy^ifcj.zy), г = 1,2,..., i, (26)

i=i !

= 3:k + TkY,big(tki,xki), к = 0,1,.... fiT - 1, (2в)

i=l

где xo = a a^, bi и Cj - вещественные коэффициенты, называется /-стадийным методом Рунге-Кутты (РК-методом).

Известно, что если интегрирование исходной задачи (1) велось с постоянным шагом то глобальная ошибка метода (2) имеет следующее асимптотическое представление в виде ряда по степеням размера этого шага:

x{tk+1) - хк+1 = ф8(гш)т3к + ip$+i{tk+1)Tsk^ + ... + + Vs(tfc+i)7* + A*, ft = 0,1.....ЛГ- 1,

где Ак = 0(тк+1) и ipi(t), г = s, s + 1,...,S, суть решения задач Коши

ф[{1) = dxg{t, x{t))il>i(t) + фм(t), 0) = 0, (4)

в которых ipi+i(t) означает коэффициент главного члена локальной ошибки некоторого одношагового метода. При г = s этот член, т.е. VVn(i), совпадает с коэффициентом главного члена локальной ошибки исходного РК-метода (2).

Суть представленного на рисунке 1 контроля точности заключается в следующем. Допустим, что мы уже вычислили два главных члена глобальной ошибки с необходимой точностью и выяснили, что размер шага тк является слишком большим и не позволяет найти численное решение с оценкой глобальной ошибки, не превосходящей установленного предела Egiob- Тогда новая концепция оптимального порядка состоит в том, чтобы поднять точность интегрирования за счет увеличения порядка экстрапо-ляционного метода для фиксированного размера шага тк. Поэтому, если возможно, мы поднимаем порядок экстраполяционного метода на единицу (или на два в случае квадратичной экстраполяции) и вычисляем коэффициенты старших членов локальной ошибки i(h+i) и ips+q_i(tk+x) (после численного интегрирования исходной задачи экстраполяционным методом порядка s + q — 1 на локальном интервале [tbit+i]). Здесь необходимо отметить, что члены асимптотического разложения глобальной

ошибки базового РК-метода (2), могут интерпретироваться как компоненты, содержащие главный член локальной ошибки экстраполяционного метода при соответствующем выборе числа экстраполяций, при условии, конечно, что глобальная ошибка в предыдущей точке сетки ^ равна нулю (в пределах установленной точности). В итоге, величины ■¡/>«+5-2(^+1) и означают приближенные значения для неоднородных членов в уравнении (4) при г = в + д — Зvíi = s + q — 2, т.е. для /ф8+д_2^к+1) и ^5+5-1(^+1), найденные с точностью по крайней мере 0(т>). Далее, если найденные величины удовлетворяют локальному контролю точности (не превосходят установленного предела е1ос), численно интегрируем дифференциальное уравнение (4) неявным методом Эйлера с целью нахождения достаточно точных оценок для коэффициентов двух первых членов в разложении глобальной ошибки (3). Проверив погрешность этого интегрирования, мы осуществляем контроль точности приближенного решения с помощью двух последних членов в разложении глобальной ошибки, исключенных в результате применения экстраполяции. Контроль точности численного решения задачи (4), особенно необходимый при решении жестких дифференциальных уравнений вида (1), осуществляется за счет повторного вычисления оценок для коэффициентов двух главных членов в разложении глобальной ошибки (3), но только методом второго порядка (рекомендуется применять либо неявное правило средней точки, либо правило трапеций). Разности этих коэффициентов, найденных численными методами первого и второго порядков, дают нам оценки локальных ошибок для решений уравнения (4) при г = з+д—З и г = з+д—2, полученных неявным методом Эйлера. Эти оценки обозначены как и на рисунке 1. Затем, если вычисление двух главных чле-

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

невозможно, то мы достигаем необходимую точность за счет уменьшения размера шага.

Подчеркнем, что мы контролируем глобальную ошибку численного метода порядка в + д — 3, а интегрирование ведем на самом деле численным методом порядка й + д — 1. Поэтому мы имеем некоторый запас точности для ошибок округления, ошибок итерационных методов, вовлеченных в неявную экстраполяцию, и ошибок, возникающих из-за усечения разложения (3) (мы пренебрегаем членами порядка й + д — 1 и выше). В квадратичной экстраполяции такой запас прочности составляет четыре порядка, что плодотворно сказывается на точности вычислений. Обратим внимание, что текущий порядок экстраполяционного метода, а значит и значение параметра устанавливающего количество численных решений исходной задачи (1) на локальном интервале [^-,^-+1], определяется в каждой точке сетки автоматически. Естественным ограничением сверху на порядок неявного экстраполяционного метода является число итераций, которое мы выполняем при интегрировании неявным РК-методом (2). Поэтому, в случае если поднять точность интегрирования экстраполя-ционным методом уже нельзя из-за погрешности итерационного процесса, вовлеченного в реализацию базового РК-метода (2), а обеспечить заданную точность вычислений для размера шага т^ еще не удалось, то мы проводим повторное интегрирование исходной задачи (1) на локальном интервале [^,^+1], увеличив число итераций ЛГЙ{Т на единицу.

Заметим, что приведенный выше алгоритм автоматического управления размером шага и порядком экстраполяции будет работать и в явных методах, рассмотренных в параграфе 2.1. Однако контроль глобальной ошибки в таким методах будет приводить к значительным дополнительным затратам машинного времени. Для неявных же экстраполяционных методов дополнительные затраты компьютерного времени будут относительно небольшими, так как реализация неявной экстраполяции и вычисление оценки глобальной ошибки требуют решения линейных систем с матрицами коэффициентов, задаваемыми матрицей Якоби исходной задачи (1). Таким образом, информация, необходимая для вычисления глобальной ошибки, доступна (и не требует дополнительных затрат) при использовании итераций ньютоновского типа.

Итак, улучшенный локально-глобальный контроль точности численного решения требует от пользователя задания максимального количества экстраполяции (дтах), а также трех параметров: Е1ос — допуск на локаль-

ную ошибку численного метода, £9ы, — допуск на глобальную ошибку численного метода и е/9 — допуск на локальную ошибку неявного метода Эйлера, примененного для приближенного решения уравнения (4) относительно коэффициентов двух главных членов разложения глобальной ошибки (3).

Далее, в параграфе 3.2 представлено всестороннее тестирование разработанной процедуры управления размером шага и порядком на дифференциальных уравнениях с известным решением и анализ результатов экспериментов. Во всех экспериментах установлена следующую связь между вышеуказанными допусками: £;ос = ед10ь и = е5ы,/10. Эти соотношения используются для того, чтобы показать какую пользу можно извлечь из дополнительного контроля глобальной ошибки при условии, что ограничения наложенные на локальную и глобальную погрешности численного решения идентичны. Таким образом, достаточно задать один из этих допусков, чтобы определить их все.

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

В параграфе 4.1 обсуждаются свойства присоединенное™ и симметрии для РК-методов со старшими производными общего вида. Определение 1 Одношаговый метод вида

tki = Ь + <кТк, (5а)

I Р]

хы = хк + тк £ £ тгка%]д{т){^, х^), i = l,2,...,l, (56)

¿=1 г-О

хк+1 =хк + ткЕ ЕфУдМ^хц), к = 0,1,.. ■, К — 1, (5в)

1т=О

где = х°, обозначает г-ую производную правой части за-

дачи (1) по независимой переменной вычисленную в точке

Tk - размер к-го шага, а коэффициенты b^ и Cj заданы таблицей:

cl аи Jp,) ■ all jo) • au au . Api) ■ all

с2 а21 «Й* ■ Jp,) ■ a21 ■ ¿21 21 ■ ■ a2l

с; п{0) а11 «&> . Jp,) ■ all . a<?> ai» . ■

Ь'[0) . b^ . . 6{°) . If)

в которой А — вещественная матрица размера lx(pi+p2 +.. ,+pi + l), а bue — вещественные вектора размера (pi +Р2 + • • • +Р1 + 0 и I соответственно, г, j = 1, 2,..., l, г = 0,1,... ,pj, причем (Cj € [0,1]), называется l-стадийным методом Рунге-Кутты со старшими производными.

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

Теорема 1 Пусть метод (5) представляет собой l-стадийный РК-метод со старшими производными, коэффициенты которого заданы таблицей (6). Тогда присоединенным для метода (5) будет также I-стадийный РК-метод со старшими производными и коэффициентами bj<~г\ с~ вида

с~ = 1 - ci+(7а) = (76) 6"(г) = (-1)Г6Й_;, г = 0,1,...,pj, t,j = 1,2.....i. (7e)

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

й = 1 ~ Q+1-ti (8а)

aj^i-ir^-aa.^.), (86)

Ъ{р = г = 0,1,...,й, 1,3 = 1,2,... ,1. (8в)

Подчеркнем, что формулы (8) необходимы для симметрии несократимого РК-метода со старшими производными. Кроме того, условия (8) подразумевают выполнение следующего равенства:

Р]=Р1+1Ч> .7 = 1.2,...,/. (9)

Таким образом, условие (9) становится естественным требованием для симметричных РК-формул со старшими производными.

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

**+1/2 = а* + п £ т£(4г)<?£г) + 4°^ГЛ) + 7*4О)0Й?1/2. (Юа)

г=0

= ** + г, £ гДьГ»^» + ь^«) + т*гМ1/2, (Юб)

г—0

А: = 0,1,...,.К - 1, где жо = х°, д\^ = г = 0,1/2,1 и

tk+i = tk + iT|c.

Чтобы Е-метод сходился с максимальным порядком 2р + 4, коэффициенты метода (10) должны удовлетворять следующим соотношениям:

М = Р+1 ^ ^ 1 (-!)'(* +0!_

(р + ЧУ 1 '

о(0) _ (Р+М'у (-1)' Шб)

а2 - 2 1\(р + I ~ 1)\(21 + гу (11б)

(г) = (-1Г'(Р+1) _(-1)^(1 +г)!_

з г,2Р+г+2 + +

(Ив)

6" = аГ + (-1ГаГ, 40) = 240), ^ = (-!)'«'" + (Пг)

В настоящей работе предлагается некоторое упрощение выражений для вычисления коэффициентов Е-методов вида (10).

Теорема 2 Коэффициенты а^' и а'р коллокационного метода (10) со старшими производными вычисляются по формулам

{г) _ р+ 1 РГ!*1 (г 4- г)!(г -+-1) ' (Р + д)\

1 Г!2Р+Г+2 ¿¡^ ¡Го (р + 1 — ¡)!(1 + г + / + 2)! 9=о ?!2» ' ^

,(г)_ (~1)Г+1(р+1)£Г*Г (г + »")!(/ + 1) ' (р + д)}

3 Г!2Р+г+2 ¿о|ео(г + г-0!(р + г + 3)!Й № ' 1 ]

гс?е г = 0,1,... ,р.

Важным следствием параграфа 4.1 является доказательство того, что все Е-методы со старшими производными симметричны, а значит — пригодны для квадратичной экстраполяции.

Теорема 3 Е-метод (10) с коэффициентами (11)—(12) является симметричным для любого целого р> 0.

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

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

Итак, введем следующие обозначения: 2(^+1) — значение точного решения задачи (1) в точке ¿^+1, х^+1 — значение точного решения нелинейной задачи (10), а хк+1 = Хк+^Ы) — значение приближенного решения задачи (10) в точке t)c+l, полученное после N итераций некоторого итерационного процесса. Очевидно, что применение Е-методов со старшими производными приводит на практике к следующей дискретной задаче:

хш = СГкХк+и к = 0,1,..., А--1 (13)

относительно вектора неизвестных

= ((х*+1/2)т, € И2"\

а отображение : И2"1 —> 112т задано формулой

2 т

2т

(хк + гк£ гКа^дР + аРдПг) +

(

\

\

+ П± тК^д? + ЬРЦ) + гкЪ^Су2

г—О

/

где р означает наперед заданное неотрицательное целое число, а коэффициенты а[\ I,] = 1,2,3, г = 0,1,... ,р, удовлетворяют соотношениям (11)—(12). Упрощенные итерации Ньютона для нелинейной задачи (13) запишем следующим образом:

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

Теорема 4 Пусть правая часть задачи (1) достаточное число раз дифференцируема в окрестности решения на отрезке [0,Г]. Тогда при диаметре сетки т —> 0 приближенное решение этой задачи хк(И), к = 1,2,..., К, полученное с помощью комбинированного алгоритма (14), построенного на основе коллокационного метода (10) с коэффициентами (11) — (12), существует и сходится к точному решению х{{). Кроме того, для сеток с достаточно малым диалктром т справедлива оценка ошибки

\\х(1к)-хк(Ы)\\<С^, к = 1,2,..., К, (15)

где ц — тт{2Лг, 2р + 4}, т = тах {тк}, а С,, — константа.

Формула (15) имеет важное практическое значение, поскольку позволяет оценить минимальное число упрощенных итераций Ньютона, которые необходимо выполнить для достижения максимального порядка сходимости 2р + 4. Итак, из (15) получаем, что число упрощенных итераций Ньютона (14) в каждой точке сетки следует подчинить условию

М>р + 2. (16)

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

В параграфе 4.3 процедура автоматического управления длиной шага и порядком, разработанная для одношаговых экстраполяционных методов Рунге-Кутты в главе 3, обобщена на Е-методы со старшими производными. При построении этого управления, необходимо учитывать некоторые нюансы, связанные с использованием Е-методов со старшими производными. Обсуждаемый локально-глобальный контроль точности базируется на экстраполяционной технике, а значит — порядок численного решения, вычисляемого в каждой точки сетки ¿¿+1, будет меняться в зависимости от числа д интегрирований на локальном интервале [¿ь ¿ьи]-Очевидно, что минимальное число упрощенных итераций (14), которое ограничивалось снизу условием (16), должно теперь соответствовать точности численного решения и тоже зависеть от параметра, д. Принимая во внимание, что Е-методы (10) с коэффициентами (11)—(12) являются симметричными, а значит, могут быть использованы для построения квадратичной экстраполяции, приходим к выводу, что порядок экстраполяционной схемы, основанной на Е-методах со старшими производными, вычисляется по формуле 2(р + д — 1) + 4. Тогда из оценки ошибки (15) можно получить условие для достаточного числа упрощенных итераций Ньютона. А затем, чтобы обеспечить максимальную точность вычислений, полностью исключив влияние ошибки итерационного процесса на ошибку комбинированного метода, и сделать контроль точности асимптотически корректным, мы увеличиваем количество итераций в каждой точке сетки на единицу, т.е. в дальнейшем будем вычислять достаточное число итераций (14) по формуле

Ы=р + д + 2. (17)

Отметим, что условие (17) является ключевым для надежного функционирования всей процедуры локально-глобального контроля точности пе-

ременного порядка. Как и в главе 3, работоспособность обсуждаемой процедуры контроля локальной и глобальной ошибок Е-методов со старшими производными зависит от трех параметров, устанавливаемых пользователем, а именно от £;ос — допуска на локальную ошибку комбинированного Е-метода, ед10ь — допуска на глобальную ошибку комбинированного Е-метода и — допуска на локальную ошибку неявного метода Эйлера, примененного для приближенного решения уравнения (4) относительно коэффициентов двух главных членов разложения глобальной ошибки (3). Для вычислительных экспериментов мы выбираем следующее соотношение между ними:

Таким образом, достаточно задать один из этих допусков, чтобы определить их все.

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

В Заключении кратко описаны основные направления диссертационного исследования и перечислены следующие основные результаты:

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

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

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

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

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

Автор выражает глубокую благодарность своему научному руководителю доктору физико-математических наук, доценту Куликову Геннадию Юрьевичу за постоянное внимание и помощь в работе.

Список публикаций по теме диссертации.

Публикации в изданиях, входящих в перечень ВАК:

1. ХРУСТАЛЕВА, Е.Ю. Об автоматическом управлении размером шага и порядком в явных одношаговых экстраполяционных методах / Г.Ю. Куликов, Е.Ю. Хрусталева// Журнал вычислительной математики и математической физики. — 2008. — Т. 48, № 8. — С. 1392-1405.

2. ХРУСТАЛЕВА, Е.Ю. Об автоматическом управлении размером шага и порядком в неявных одношаговых экстраполяционных методах / Г.Ю. Куликов, Е.Ю. Хрусталева// Журнал вычислительной математики и математической физики. - 2008. — Т. 48, № 9. - С. 1580-1606.

3. ХРУСТАЛЕВА, Е.Ю. Об автоматическом управлении длиной шага и порядком в одношаговых коллокационных методах со старшими производными ! Г.Ю. Куликов, Е.Ю. Хрусталева/'/ Журнал вычислительной математики и математической физики. — 2010. — Т. 50, № 6. - С. 1060-1077.

Публикации в прочих изданиях:

4. ХРУСТАЛЕВА, Е.Ю. Реализация и тестирование алгоритма управления порядком и шагом явных экстраполяционных методов// Фундаментальные проблемы математики и механики. — Ульяновск: УлГУ, 2002. - Вып. 11. - С. 146-153.

5. хрусталева, Е.Ю. о квадратичной экстраполяции, основанной коллокационных методах со старшими производными /Г.Ю. Куликов, А.И. Меркулов, Е.Ю. Хрусталева// Фундаментальные проблемы математики и механики. — Ульяновск: УлГУ, 2003. — Вып. 1(13). - С. 48-62.

6. Хрусталева, Е.Ю. О различных способах управления порядком и шагом явных экстраполяционных методов// Труды пятой международной конференции «Математическое моделирование физических, экономических, технических, социальных систем и процессов». — Ульяновск: УлГУ, 2003. - С. 200-202.

7. хрусталева, Е.Ю. Симметричные коллокационные одношаговые методы со старшими производными и квадратичная экстраполяция /Г.Ю. Куликов, А.И. Меркулов, Е.Ю. Хрусталева// Материалы XXVI конференции молодых ученых механико-математического факультета МГУ им. М.В. Ломоносова. — Москва: Механико-математический факультет МГУ, 2004. — С. 133-134.

8. Хрусталева, Е.Ю. Симметричные коллокационные одношаговые методы со старшими производными и квадратичная экстраполяция /Г.Ю. Куликов, А.И. Меркз'лов, Е.Ю. Хрусталева// Труды XXVI конференции молодых ученых механико-математического факультета МГУ им. М.В. Ломоносова. — Москва: Механико-математический факультет МГУ, 2004. - Т. 2. - С. 145-148.

9. khrustaleva, E.Yu. On a family of A-stable collocation methods with high derivatives /G.Yu. Kulikov, A.I. Merkulov, E.Yu. Khrustaleva// In: Bubak M. et al (eds.): Computational Science — ICCS 2004. 4th International Conference, Krakow, Poland, June 6-9 2004. — Proceedings, Part II. Lecture Notes in Computer Science, 2004. — V. 3037. - P. 73-80.

10. khrustaleva, E.YU. Symmetric Runge-Kutta methods with higher derivatives and quadratic extrapolation / G.Yu. Kulikov, E.Yu. Khrustaleva, A.I. Merkulov// In: Alexandrov V.N. et al (eds.): Computational Science — ICCS 2006. 6th International Conference, Reading, UK, May 28-31, 2006. — Proceedings, Part I. Lecture Notes in Computer Science, 2006. - V. 3991. - P. 117-123.

Подписано в печать 19.10.10. Формат 60x84/16. Усл. печ. л. 1. Тираж 100 экз. Заказ 1001$66

Отпечатано в Издательском центре Ульяновского государственного университета 432000, г. Ульяновск, ул. Л. Толстого, 42

Введение

1 Обзор литературы

1.1 Одношаговые методы.

1.2 Экстраполяционные методы.

1.3 Автоматический контроль точности вычислений

2 Неявные экстраполяционные методы и локальный контроль точности

2.1 Автоматическое управление размером шага и порядком в явных одно-шаговых экстраполяционных методах.

2.2 Автоматическое управление размером шага и порядком в неявных од-ношаговых экстраполяционных методах.

2.3 Вычислительные эксперименты.

3 Неявные экстраполяционные методы и глобальный контроль точности

3.1 Локально-глобальное управление размером шага и порядком экстраполяционных методов.

3.2 Вычислительные эксперименты.

4 Коллокационные методы со старшими производными и глобальный контроль точности 81 4.1' Присоединенные и симметричные РК-методы со старшими производными

4.2 Эффективная реализация E-методов и упрощенные итерации Ньютона

4.3 Локально-глобальное управление размером шага и порядком в одногаа-говых коллокационных методах со старшими производными

4.4 Вычислительные эксперименты.

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

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

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

Основу математического моделирования составляет триада "модель — алгоритм — программа". На первом этапе строится математическая модель исследуемого объекта. Математическая модель является приближенным представлением реальных процессов или систем, выраженным в математических терминах и сохраняющим наиболее существенные черты оригинала. Явления, изучаемые различными областями науки, часто приводят к сходным математическим моделям. Так, например, многие реальные объекты физики, механики, химии, биологии и т.д. адекватно описываются дифференциальными уравнениями [7, 8, 34, 44, 45, 100, 101].

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

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

В настоящее время одношаговые методы считаются хорошо изученными и можно найти большое количество работ, посвященных исследованию данных алгоритмов (см., например, [1, 3, 4, 5, 32, 33, 41, 42, 43, 44, 45, 51, 59, 61, 65, 71, 75, 98, 100, 101, 102, 108, 113, 114, 132, 135, 139, 145]). Среди них следует особо выделить труды, посвященные изучению фундаментальных свойств одношаговых методов таких как аппроксимация, устойчивость, сходимость и т.д. [3, 44, 45, 51, 65, 75, 100, 101, 102, 108, 114].

Что же касается экстраполяционных методов, то до последнего времени исследования в этой области ограничивались явными одношаговыми экстраполяционны-ми методами [44, 57, 78, 93, 94, 100, 156]. Однако слабая устойчивость таких методов позволяет использовать их лишь для ограниченного круга задач. Поэтому были предприняты попытки улучшить устойчивость экстраполяционных алгоритмов путем введения некоторой неявности [45, 51, 79, 101]. Общая же теория экстраполяционных методов, использующих неявные одношаговые схемы, была впервые предложена в [21, 22, 119, 121], как для дифференциальных уравнений, так и для более общего случая дифференциально-алгебраических систем. Кроме этого, существует ряд работ, в которых отмечена особая эффективность использования симметричных методов в качестве базовых для построения экстраполяционных алгоритмов [44, 45, 51, 55, 57, 78, 79, 93, 94, 101, 156]. Однако, как показывают полученные ранее результаты [44, 117, 156, 160], большинство таких методов имеет неявный вид. Более того, среди явных формул Рунге-Кутты, на которых в основном и базируются экстраполяционные алгоритмы, вообще нет симметричных методов [19, 117]. По этой причине в настоящее время известен только один численный метод, основанный на квадратичной экстраполяции, — ГБШ-алгоритм [44, с. 244-247], [51], [156]. Опять же в силу своей явности он обладает весьма неудовлетворительной устойчивостью, что обусловило развитие линейно неявного аналога ГБШ-алгоритма [55].

Рассматривая различные одношаговые методы для использования их в качестве базы при построения экстраполяции, нельзя не упомянуть о методах, использующих старшие производные, которые получили серьезное развитие во второй половине XX и в начале XXI века [26, 87, 88, 113, 114, 123, 143]. Отличительной чертой этих методов является высокая скорость сходимости и возможность объединения в рамках одного алгоритма достоинств методов Рунге-Кутты и методов, основанных на рядах Тейлора. Однако большинство перечисленных исследований имеют чисто теоретическую ценность и не предлагают способов практической реализации данных методов. РГсследования в этой области достаточно ограничены, а определение условий симметричности таких методов и использование их в качестве базовых для построения экстраполяции не проводились вовсе.

Важнейшим этапом в эффективной реализации любого численного метода для интегрирования дифференциальных уравнений является разработка механизма автоматического управления размером шага с целью обеспечения требуемой точности вычисления за минимальное (или приемлемое) время. Дополнительным преимуществом экстраполяционных методов является возможность автоматического подбора оптимальных размера шага и порядка в каждой точке сетки. Варьируя размер шага интегрирования, а также порядок метода, можно существенно экономить ресурсы вычислительной системы, что чрезвычайно важно для реальных приложений. Однако сами алгоритмы выбора шага и порядка достаточно сложны (см., например, [29], [44, с. 244-247], [57], [78]). Другой проблемой является то, что все эти алгоритмы, за исключением процедуры, предложенной в [29], ориентированы на использование исключительно в явных экстраполяционных методах и их адаптация к неявной экстраполяции требует значительных усилий. К тому же практически все известные в настоящее время численные методы с автоматическим выбором шага интегрирования основаны на вычислении главного члена локальной ошибки и последующем выборе такого размера для очередного шага, который является максимальным для заданного предела локальной ошибки (см., например, [1, 4, 5, 44, 45, 51, 66, 77, 78, 84, 86, 96, 100, 101, 103, 104, 105, 106, НО]). Таким образом, процитированные выше алгоритмы комбинированного управления шагом и порядком экстраполяционных процессов не способны находить численное решение, удовлетворяющее наперед заданным требованиям к точности, в автоматическом режиме.

Вопрос о надежной и достоверной оценке точности численного решения и эффективной организации процесса автоматического управления погрешностью численных методов для обыкновенных дифференциальных уравнений неразрывно связан с проблемой оценки глобальной ошибки, которой посвящено достаточно большое число работ (см., например, [38, 53, 66, 77, 81, 82, 111, 116, 118, 137, 138, 140, 153, 154, 157, 158, 161]). В то время как обсуждению алгоритмов автоматического контроля глобальной ошибки уделено значительно меньше внимания. Можно указать лишь относительно небольшое количество статей, так или иначе затрагивающих эту тематику [18, 21, 26, 38, 77, 116, 118, 121, 137, 154, 157].

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

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

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

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

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

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

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

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

Вторая глава работы, состоящая из трех параграфов, посвящена неявным экстра-поляционным методам и проблеме локального контроля точности. В параграфе 2.1 рассматривается модификация известного алгоритма управления порядком и шагом в явных экстраполяционных методах ( см. [44, с. 244-247]). Предлагается улучшить производительность процедуры управления за счет более точного учета трудоемкости экстраполяции. Новая концепция «работы на шаге» базируется на подсчете реальных затрат процессорного времени, что позволяет проводить численное интегрирование максимально эффективно. К тому же указанный способ оценки дает более правильное представление и о трудоемкости неявных экстраполяционных методов. Поэтому далее, в параграфе 2.2 производится адаптация процедуры управления для неявных экстраполяционных методов и показывается, что модифицированный алгоритм достаточно работоспособен и в этом случае. Результаты практической реализации указанной процедуры контроля приведены в параграфе 2.3. Здесь же отмечается, что, учитывая только величину локальной ошибки интегрирования, невозможно получить численное решение с наперед заданной точностью в автоматическим режиме, что является наиболее важным при решении задачи.

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

Четвертая глава, состоящая из 4 параграфов, также занимает важное место в диссертации, так как в ней теория комбинированного управления порядком и шагом расширена для использования в коллокационных методах со старшими производными. В параграфе 4.1 обсуждаются свойства присоединенностн и симметрии для РК-методов со старшими производными общего вида. Важным следствием параграфа 4.1 является доказательство того, что все Е-методы, построенные Куликовым и Меркуловым в [26] симметричны, а значит — пригодны для квадратичной экстраполяции. Особое внимание уделено сокращению дополнительных вычислительных затрат, возникающих при использовании неявной экстраполяции. Этому вопросу посвящен параграф 4.2. Разработана новая схема упрощенного метода Ньютона, построены комбинированные схемы неявных экстраполяционных методов с использованием нового итерационного процесса. Представлено доказательство сходимости этого метода. В параграфе 4.3 предлагается эффективная реализации алгоритмов автоматического управления длиной шага и порядком, разработанных для одношаговых экстраполяционных методов Рунге-Кутты в главе 3, для Е-методов со старшими производными. Далее, в параграфе 4.4 представлено всестороннее тестирование разработанной вычислительной техники на дифференциальных уравнениях с известным решением и анализ результатов экспериментов.

В Заключении кратко описаны основные направления диссертационного исследования и перечислены полученные результаты.

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

Итак, основные результаты диссертации заключаются в следующем:

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

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

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

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

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

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

Основные результаты диссертации доложены: на пятой международной научно-технической конференции "Математическое моделирование физических, экономических, технических, социальных систем и процессов" (Ульяновск, 2003), на XXVI конференции молодых ученых механико-математического факультета МГУ им. М.В. Ломоносова (Москва, 2004), на 4th International Conference on Computer Science (Krakow, Poland, 2004).

По теме диссертации опубликовано 10 работ ( [25, 27, 28, 29, 30, 31, 47, 48,123, 125]), в том числе 3 в рецензируемых научных изданиях, рекомендованных ВАК ([29, 30, 31]). При этом результаты из работ, подготовленных в соавторстве, либо использованы частично, в соответствии с личным вкладом каждого автора ([25, 27, 28, 29, 30, 31]), либо приведены в переработанном виде ([123, 125]).

Автор выражает глубокую благодарность своему научному руководителю д.ф.-м.н., доценту Куликову Г.Ю. за постоянное внимание и помощь в работе.

Заключение

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

В первую очередь, в главе 2, мы рассмотрели традиционный и наиболее простой контроль с использованием оценки локальной ошибки одношагового метода. В качестве примера был представлен известный алгоритм комбинированного управления выбором порядка и длины шага предложенный Хайрером с соавт. (подробнее см. параграф 1.3). Он основан на концепции минимизации вычислительной работы за единичный шаг. Эта концепция означает, что оптимальный порядок экстраполяционного метода в данной точке численного интегрирования должен минимизировать вычислительную работу на шаге, под которой Хайрер и др. понимают число вычислений правой части исходной задачи (1.1.1а). Этот подход весьма популярен, но имеет ряд серьезных недостатков. К недостаткам следует отнести вычисление работы на шаге, т.к. описанный подход не дает реального представления о вычислительной работе при интегрировании дифференциальных уравнений. Более того, если формулы (1.3.15) и (1.3.16), которые подсчитывают число вызовов функции для вычисления правой части задачи (1.1.1а) за единичный шаг, являются приемлемыми оценками трудоемкости явной экстраполяции, то для неявных экстраполяционных методов это уже не так. Дело в том, что при использовании неявных одношаговых методов, не можем вычислить точно приближенное решение, даваемое этим методом, за исключением линейного случая, и вынуждены ограничиться некоторым итерационным приближением. Но тогда возникает необходимость в применении итерационных методов. И в этом случае, особенно применяя итерации ньютоновского типа, более важное значение приобретает решение возникающих линейных систем. Но с другой стороны, вычисление правой части задачи (1.1.1а) тоже может быть очень трудоемким и вносить существенных вклад в затраты машинного времени. Поэтому, в существующем виде данный алгоритм управления выбором порядка и длины шага предложенный Хайрером с соавт. не может быть применен к неявных методам. В связи с этим, в параграфе 2.1 была предложена другая концепция подсчета вычислительной работы за единичный шаг, в равной степени применимая и к явным, и к неявным одноша-говым методам. Новая концепция работы базируется не на числе вызовов функции для вычисления правой части исходной задачи, а на учете реальных затрат процессорного времени, что позволяет проводить численное интегрирование максимально эффективно. В параграфе 2.1 приведен ряд сравнительных экспериментов, наглядно демонстрирующих значительное увеличение эффективности вычислений за счет более точного учета трудоемкости экстраполяции. Далее, в параграфе 2.2 мы успешно адаптировали предложенную модификацию алгоритма Хайрера с соавт. для явных экстраполяционных процессов к неявным одношаговым экстраполяционным методам. Результаты численных экспериментов из параграфа 2.3 однозначно подтверждают работоспособность рассмотренного способа автоматического управления длиной шага и порядком неявных экстраполяционных методов. Но с другой стороны, экспериментальные данные, приведенные в параграфах 2.1 и 2.3 наглядно демонстрируют, что локальный контроль точности (т.е. контроль только локальной ошибки) не способен обеспечить заданную пользователем точность вычислений в автоматическом режиме.

Чтобы разрешить подобную проблему, в главе 3 мы предложили другую методику управления размером шага и порядком, которая основана на контроле как локальной так и глобальной ошибок численного решения. Конечно, управление глобальной ошибкой требует дополнительных затрат машинного времени, но зато позволяет находить численное решение, удовлетворяющее наперед заданным требованиям к точности, в автоматическом режиме. В параграфе 3.1 мы представили улучшенную версию алгоритма устойчивого неявного локально-глобального контроля точности, основанную на контроле двух главных членов в асимптотическом разложении глобальной ошибки (1.2.1) (см. блок-схему на рисунке 3.1). Нам удалось адаптировать указанный алгоритм контроля локальной и глобальной ошибок к неявным экстраполяционным методам и повысить его эффективность за счет вычисления большего числа членов в разложении глобальной ошибки. В параграфе 3.2 мы проиллюстрировали на примерах высокую практическую работоспособность локально-глобального управления размером шага и порядком неявных экстраполяционных методов. Особое внимание было уделено практической реализации процедуры управления, использующей симметричные одношаговые методы, т.е. методы обладающие квадратичным асимптотическим разложением глобальной ошибки. В этом случае мы имеем квадратичную экстраполяцию. Данные, полученные в параграфе 3.2, однозначно подтверждают теоретические выводы о преимуществе квадратичной экстраполяции над обычной: численные решения найдены с большей точностью и за более короткое время.

Далее, в главе 4, мы рассмотрели одношаговые численные методы, использующие старшие производные (в частности семейство E-методов со старшими производными, предложенное Куликовым и Меркуловым в [26]). В параграфе 4.1 были доказаны теоремы о присоединенных и симметричных РК-методах со старшими производными. А также предложен более простой вид выражений для вычисления коэффициентов Е-методов (4.1.11). Основываясь на доказанных свойствах, мы показали, что все Е-методы (1.1.6) с коэффициентами (4.1.11) (или (1.1.7)) симметричны, а значит — пригодны для квадратичной экстраполяции, которая зарекомендовала себя наилучшим образом. Параграф 4.2 посвящен эффективной реализации E-методов. Являясь неявными, E-методы требуют привлечения дополнительных итерационных процессов для практического нахождения численного решения, а число и тип итераций существенным образом влияют как на порядок сходимости, так и на эффективность вычислений. В параграфе 4.2 мы разработали наиболее эффективные упрощенные итерации Ньютона для систем нелинейных уравнений (в смысле затрат машинного времени) с тем, чтобы получить вычислительные процедуры, пригодные для практического применения. Представили доказательство сходимости нового метода, а также и вывели условие, гарантирующие сходимость максимального порядка комбинированного метода (4.2.2). Теоретические результаты подтверждены численными примерами. В следующем параграфе 4.3, мы представили адаптацию устойчивого неявного локально-глобального контроля точности из 3.1 к комбинированным Е-методам со старшими производными. Эксперименты параграфа 4.4 подтвердили высокую эффективность Е-методов с управлением длиной шага и порядком из 3.1 для достижения заданной точности интегрирования в автоматическом режиме.

1. Арушанян о.В., Залеткин С.Ф. Численное решение обыкновенных дифференциальных уравнений на Фортране. — М.: МГУ, 1990.

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

3. Бахвалов Н.С., Жидков Н.П., Кобельков Г.М. Численные методы. — М.: Наука, 1987, 2003.

4. Березин И.е., Жидков Н.П. Методы вычислений. — М.: ГИФМЛ, 1962. — Т. 1.

5. Бояринцев Ю.Е., Данилов В.А., Логинов A.A., Чистяков В.Ф. Численные методы решения сингулярных систем. — Новосибирск: Наука, 1989.

6. БояРНИЦЕВ Ю.Е. Методы решения непрерывных и дискретных задач для сингулярных систем уравнений. — Новосибирск: Наука, 1996.

7. ГаЙТОН А. Физиология кровообращения: Минутный объем сердца и его регуляция. — М.: Медицина, 1969.

8. ГРОДИНЗ Ф. Теория регулирования и биологические системы. — М.: Мир, 1966.11. деккер К., Вервер я. Устойчивость методов Рунге-Кутты для жестких нелинейных дифференциальных уравнений. — М.: Мир, 1988.

9. КАЛИТКИН H.H. Численные методы. — М.: Наука, 1978.

10. КОЛЛАТЦ Л. Численные методы решения дифференциальных уравнений. — М.: ИЛ, 1953.

11. КУЛИКОВ Г.Ю. Об использовании итерационных методов ньютоновского типа для решения систем дифференциально-алгебраических уравнений индекса 1// Журнал вычислительной математики и математической физики. — 2001. — Т. 41, № 8. С. 1180-1189.

12. КУЛИКОВ Г.Ю. Численные методы с контролем глобальной ошибки для решения дифференциальных и дифференциально-алгебраических уравнений индекса 1: Дис. . докт. физ.-мат. наук. — Ульяновск: УлГУ, 2002. — 315 с.

13. Куликов Г.Ю., Меркулов А.И. Об асимптотической оценке погрешности методов ньютоновского типа и ее практическом применении// Фундаментальные проблемы математики и механики. — Ульяновск: УлГУ, 2003. — Вып. 1(13). — С. 36-47.

14. Куликов Г.Ю., Меркулов А.И., Хрусталева Е.Ю. О квадратичной экстраполяции, основанной коллокационных методах со старшими производными// Фундаментальные проблемы математики и механики. — Ульяновск: УлГУ, 2003.- Вып. 1(13). С. 48-62.

15. Куликов Г.Ю., Меркулов А.И. Об одношаговых коллокационных методах со старшими производными для решения обыкновенных дифференциальных уравнений// Журнал вычислительной математики и математической физики.- 2004. Т. 44, № 10. - С. 1782-1807.

16. Куликов Г.Ю., Хрусталева Е.Ю. Об автоматическом управлении размером шага и порядком в явных одношаговых экстраполяционных методах// Журнал вычислительной математики и математической физики. — 2008. — Т. 48, К0 8. — С. 1392-1405.

17. Куликов Г.Ю., Хрусталева Е.Ю. Об автоматическом управлении размером шага и порядком в неявных одношаговых экстраполяционных методах// Журнал вычислительной математики и математической физики. — 2008. — Т. 48, № 9. С. 1580-1606.

18. Куликов Г.Ю., Хрусталева Е.Ю. Об автоматическом управлении длиной шага и порядком в одношаговых коллокационных методах со старшими производными // Журнал вычислительной математики и математической физики. — 2010. Т. 50, № 6. - С. 1060-1077.

19. ЛЕБЕДЕВ В.И. Функциональный анализ и вычислительная математика. — М.: Наука. Гл. ред. физ.-мат. лит., 2000.

20. МАРЧУК Г.И. Методы вычислительной математики. — М.: Наука, 1989.

21. Нерретер В. Расчет электрических цепей на персональной ЭВМ. — М.: Энер-гоатомиздат, 1991.

22. Новиков В.А., Новиков Е.А. О повышении эффективности алгоритмов интегрирования обыкновенных дифференциальных уравнений за счет контроля устойчивости// Журнал вычислительной математики и математической физики. 1985. - Т. 25, № 7. - С. 1023-1030.

23. ОРТЕГА Дж., ПУЛ У. Введение в численные методы решения дифференциальных уравнений. — М.: Наука, 1986.

24. РакитскиЙ Ю.В., Устинов С.М., ЧЕРНОРУЦКИЙ И.Г. Численные методы решения жестких систем. — М.: Наука. Гл. ред. фнз.- мат. лит., 1979.

25. Самарский А.А., Гулин А.В. Численные методы. — М.: Наука, 1989.

26. ХаЙРЕР Э., Нерсетт е., Ваннер Г. Решение обыкновенных дифференциальных уравнений. Нежесткие задачи. — М.: Мир, 1990.

27. ХаЙРЕР Э., Ваннер Г. Решение обыкновенных дифференциальных уравнений. Жесткие и дифференциально-алгебраические задачи. — М.: Мир, 1999.

28. ХОВАНСКИЙ А.Н. Приложения цепных дробей и их обобщений к вопросам приближенного анализа. — М.: Гостехиздат, 1956.

29. Шалашилин В.И., Кузнецов Е.Б. Метод продолжения решения по параметру и наилучшая параметризация в прикладной математике и механике. — М.: Эдиториал УРСС, 1999.

30. Шин дин С. К. Автоматическое управление точностью численного решения обыкновенных дифференциальных уравнений линейными многошаговыми методами : Дис. . канд. физ.-мат. наук. Ульяновск: УлГУ, 2003. — 193 с.

31. ШТЕТТЕР X. Анализ методов дискретизации для обыкновенных дифференциальных уравнений. — М.: Мир, 1978.52. эйлер Л. Интегральное исчисление// М.: Гостехиздат, 1956 — Т. 1. — С. 415

32. Ai'd R., levacher L. Numerical investigations on global error estimation for ordinary differential equations// Journal of Computational and Applied Mathematics. — 1997. — V. 82. — P. 21-39.

33. Aitken A.C. On interpolation by iteration of proportional parts, without the use of differences// Proceedings of the Edinburgh Mathematical Society (Series 2). — 1932 V. 3. - P. 56-76.

34. Butcher J.C. Implicit Runge-Kutta processes// Math Comput. V. 18, P. 50-64.

35. Butcher J.C. On Runge-Kutta processes of high order// J. Austral. Math Soc. V. IV, part 2, P. 179-194.

36. Butcher J.C. Integration processes based on Radau quadrature formulas// Math Coinput. V. 18, P. 233-244.

37. Butcher J.C. On the attainable order of Runge-Kutta methods // Math, of Comp. V. 19, P. 408-417.

38. Butcher J.C. The non-existence of ten stage eighth order explicit Runge-Kutta methods // BIT V. 25, P. 521-540.

39. Butcher J.C., Chan R.P.K. On symmetrizers for Gauss methods// Numer. Math.- 1992. V. 60. - P. 465-476.

40. Butcher J.C. Numerical methods for ordinary differential equations. — Chichester: John Wiley and Son, 2003.

41. CESCHINO F. Evalutaion de l'erreur par pas dans les problems différentiels// Chiffres, 1962. V. 5 - P. 223-229.

42. Ceschino F., Kuntzmann Numerical solutions of initial value problems// Prentice Hall, 1966. P. 372.

43. CHAN R.P.K. Generalized symmetric Runge-Kutta methods// Computing. — 1993.- V. 50. P. 31-49.

44. CURTIS A.R. High-order explicit Runge-Kutta formulae, their uses, and limitations// J. Inst. Maths Applies, 1975. — V. 16. — P. 35-55.

45. Dormand J.R., Prince P.J. A family of embedded Runge-Kutta formulae // J. Comp. Appl. Math. 1980. - V. 6. - P. 19-26.

46. Dormand J.R., Duckers R.R., Prince P.J. Global error estimation with Runge-Kutta methods// IMA J. Numer. Anal. 1984. - V. 4. - P. 169-184.

47. Dormand J.R., Prince P.J. Global error estimation with Runge-Kutta methods II// IMA J. Numer. Anal. 1985. - V. 5. - P. 481-497.

48. Eich E., Führer C., Yen J. On the error control for xnultistep methods applied to ODEs with invariants and DAEs in multibody dynamics// Mech. Struct, and Mach.- 1995. V. 23(2). - P. 159-179.

49. Endresen L.P., Myrheim J. A formula for steplength control in numerical integration// J. Comp. Appl. Math. — 1998. — V. 90. — P. 263-264.

50. ENGLAND R. Error estimation for Runge-Kutta typesolutions to systems of ordinary differential equations// The Computer J. — V. 12. — P. 166-170.

51. Fehlberg E. New high-order Runge-Kutta formulas with step size control for systems of first and second order differential equations// ZAMM. — 1964. — V. 44, Sonderheftm — P.T17-T19.

52. Fehlberg E. Classical fifth-,sixth-,seventh-, and eighth order Runge-Kutta formulas with step-size control// Computing. — V. 4. — P. 93-106.

53. FEHLBERG E. Low order classical Runge-Kutta formulas with step-size control and their application to somei heat transfer problems// Computing. — V. 6. — P. 61-71.

54. Franzer R.A., Jones W.P., Skan S.W. Approximations to functions and to the solutions of the differential equations // Reports and Memoranda Nr.l 1799, (2913): Aeronautical Research Committee, P. 33. — P. 1025-1043.

55. Gear C.W. Numerical initial value problems in odinary differential equations. // Prentice Hall. 1971.

56. Gragg W.B. Repeated extrapolation to the limit in the numerical solution of ordinary differential equations. — Thesis. Univ. of California. — 1964.

57. Gragg W.B. On extrapolation algorithms for ordinary initial value problems// SIAM J. Numer. Anal. Ser. B. 1965. - V. 2, - P. 384-403.

58. Hairer E., Wanner G. Solving ordinary differential equations II: Stiff and differential-algebraic problems. — Berlin: Springer-Verlag, 1991, 1996.

59. Hairer E., Wanner G. Stiff differential equations solved by Radau methods// J. Comput. Appl. Math. 1999. - V. 111. - P. 93-111.

60. Hall G. Equilibrium states of Runge-Kutta schemes// ACM Trans. Math. Software. 1985. - V. 11. - P. 289-301.

61. Hall G. Equilibrium states of Runge-Kutta schemes, part II// ACM Trans. Math. Software. 1986. - V. 12. - P. 183-192.

62. Hall G., Higham D.J. Analisys of stepsize selection schemes for Runge-Kutta codes// IMA J. Numer. Anal. 1988. - V. 8. - P. 305-310.

63. Hall G. A New stepsize strategy for Runge-Kutta codes. Numerical Analysis Report № 245, 1994. — University of Manchester/UMIST, Manchester Centre for Computational Mathematics, Manchester, 1994.

64. Hammer P.C., Hollingsworth Trapezoidal methods of approximating solutions of differential equations // MTAC. — 1955. — V. 9. — P. 92-96.

65. Henrici P. Discrete variable methods in ordinary differential equations. — New York-London: John Wiley and Sons, 1962.

66. Heun K. Neue methode zur approximativen integration der differentialgleichungen einer unabhängigen veründerlichen // Zeitschr. für Math. u. Phys. — 1900. — V. 45.- P. 23-88.

67. Higham D.J. Robust defect control with Runge-Kutta schemes// SIAM J. Numer. Analys. 1989. - V. 26, № 5. - P. 1175-1183.

68. Higham D.J. Global error versus tolerance for explicit Runge-Kutta methods// IMA J. Numer. Anal. 1991. - V. 11. - P. 457-480.

69. Hulme B.L. One-step piecewise polynomial Galerkin methods for initial value problems// Math, of Comput. 1972. - V. 26. - P. 415-426.

70. Kastlunger K.H., Wanner G. Runge-Kutta processes with multiple nodes// Computing. — 1972. V. 9. - P. 9-24.

71. Kulikov G.Yu. Symmetric Runge-Kutta methods and their stability// Russian Journal of Numerical Analysis and Mathematical Modelling. — 2003. — V. 18, № 1.- P. 13-41.

72. Kulikov G.Yu. One-step methods and implicit extrapolation technique for index 1 differential-algebraic systems// Russian Journal of Numerical Analysis and Mathematical Modelling. 2004. - V. 19, № 6. — P. 527-553.

73. Kulikov G.Yu., Shindin S.K. One-leg integration of ordinary differential equations with global error control// Comput. Methods Appl. Math. — 2005. — V. 5, № 1. P. 86-96.

74. Kulikov G.Yu., Shindin S.K. One-leg variable-coefficient formulas for ordinary differential equations and local-global step size control// Numer. Algorithms. — 2006.- V. 43. P. 99-121.

75. Kulikov G.Yu., Merkulov A.I., Shindin S.K. Asymptotic error estimate for general Newton-type methods and its application to differential equations// Russian J. Numer. Anal. Math. Modelling. 2007. - V. 22, № 6. - P. 567-590.

76. Kulikov G.Yu., Shindin S.K. Adaptive nested implicit Runge-Kutta formulas of Gauss type// Appl. Numer. Math. 2009. - V. 59. - P. 707-722.

77. Kuntzmann J. Neuere entwickelungen der methode von Runge-Kutta// ZAMM. — 1961. V. 41. - P. 28-31.

78. KllTTA W. Beitrag zur naherungsweisen integration totaler differentialgleichungen // Zeitschr. fur Math. u. Phys. 1901. - V. 46. - P. 435-453.

79. LlNDBERG B. On smoothing and extrapolation for the trapezoidal rule// BIT. — 1971. V. 11. - P. 29-52.

80. LlNDBERG B. Characterization of optimal stepsize sequences for methods for stiff differential equations// SIAM J. Numer. Analys. 1977. - V. 14, № 5. - P. 859-887.

81. LlNDBERG B. Error estimation and iterative improvement for discretization algorithms// BIT. 1980. - V. 20. — P. 486-500.

82. Lobatto R. Lessen over differential- en Integraal-rekening// La Haye, 1851-1852. -V. 2.

83. Merluzzi P., Brosilow C. Runge-Kutta integration algorithms with built-in estimates of the accumulated truncation error// Computing. — 1978. — V. 20. — P. 1-16.

84. MERSON R.H. An operational method for the study of integration processes// Pore. Symp. Data Processing, Weapons Research Establishment, Salisbury, Australia, 1957. P. 110-1 to 110-25.

85. Richardson L.F. The deffered approach to the limit// Phil. Trans. A. 1927. — V. 226. P. 299-349.

86. Robertson H.H. The solution of a set of reaction rate equations// J. Walsh ed.: Numer. Anal., an Introduction, Academ. Press. — 1966. — P. 178-182.

87. RUNGE C. Ueber die numerische auflosung von differentialgleichungen// Math. Ann.- 1895. V. 46. - P. 167-178.

88. Runge C. Separation und approximation der wurzeln von gleichungen// Enzykl. d. Mathem. Wissensch, Teubner, Leipzig, 1899. — V. 1 — P. 405-449.

89. Sanugi B. B. and Evans D. J. A new fourth order Runge-Kutta formula for y' = Ay with stepsize control// Computers & Mathematics with Applications. — 1988. Volume 15, Issue 12. - P. 991-995.

90. SARAFYAN D. Error estimation for Runge-Kutta methods through pseudo-iterative formulas // Techn. Rep. No. 14, Louisiana State Univ. — New Orleans, 1966, May.

91. Shampine L.F. Global error estimation for stiff ODEs. Lecture Notes in Math. V. 1066. Berlin: Springer, 1984. - P. 159-168.

92. SKEEL R.D. Thirteen ways to estimate global error// Numer. Math. — 1986. — V. 48- P. 1-20.

93. SKEEL R.D. Global error estimation and the backward differentiation formulas// Appl. Math. Comput. 1989. - V. 31. - P. 197-208.

94. STETTER H.J. Symmetric two-step algorithms for ordinary differential equations// Computing. — 1970. V. 5. — P. 267-280.

95. STETTER H.J. Local estimation of the global discretization error// SIAM J. Numer. Analys. 1971. - V. 8. - P. 512-523.

96. STETTER H.J. The defect correction principle and discretization methods// Numer. Math. 1978. - V. 29. - P. 425-443.

97. Stroud A.H., Stancu D.D. Quadrature formules with multiple Gaussian nodes // SIAM J. Numer. Anal., ser. B., 1965. — V. 2. P. 129-143.

98. ZONNEVELD J.A. Automatic integration of ordinary diffential equations// Matliematisch Centrum. — Amsterdam, 1963.