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

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

УНИВЕРСИТЕТ

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

Олемской Игорь Владимирович

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

05.13.18 - Математическое моделирование, численные методы и комплексы программ

Автореферат

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

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

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

Официальные оппоненты:

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

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

доктор физико-математических наук, профессор Овсянников Дмитрий Александрович.

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

Петрозаводский государственный университет

Защита состоится " 2,6 " СлЛ^р&А-^ 2006 г. в |Р часов на заседании диссертационного совета Д.212.232.50 по защите диссертаций на соискание ученой степени доктора наук при Санкт-Петербургском государственном университете по адресу: Санкт-Петербург, Университетская наб., 7/9. Менделеевский цент р.

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

Автореферат разослан "2Х) "^Ч&Р^Л 2006 г.

Ученый секретарь Р^*---

диссертационного совета Д.212.232.50 доктор физико-математических наук,

профессор Г.И. Курбатова

ДОО£!\

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

Актуальность темы диссертации. В последние сорок лет Дж. Батчером, Э. Фельбергом, Э. Хайрером, Г. Ваннером были выполнены фундаментальные исследования по теории конструирования и реализации методов численного интегрирования ОДУ.

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

В середине 60-х Дж. Батчер доказал ряд соотношений между минимальным числом этапов тп(д) явного метода Рунге-Кутты (РК) и его порядком <7 (барьеры Батчера). Первый барьер — для (? > 5 не существует явных методов РК порядка ц с числом этапов т = д.

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

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

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

этом все у тверждения о соотношении порядка метода q и минимального числа этапов m(q), справедливые для скалярного случая, нерпы и для векторного: m(q) — q, q < 4; m(5) = 6. Причем эти соотношения верны и для явного составного метода Э. Хай-рера. Надо отметить, что наличие структурных особенностей в правых частях интегрируемых систем (отсутствие зависимости от некоторого числа компонент искомой вектор-функции) также не изменяет этого соотношения для упомянутых методов.

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

Зависимость эффективности метода от структурных особенностей уже была отмечена в практике конструирования одно-шаговых методов. Так для численного интегрирования дифференциальных уравнений второго порядка у" = f(x, у. у') X. Ню-стрём предложил прямой метод Рунге-Кутты. Р. Цурмюль распространил его на дифференциальные уравнения п—го порядка у{п) _ у, у',..., Причем при независимости его правой

части от эффективность этих методов возрастает.

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

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

Актуальность работы обусловлена тремя основными моментами:

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

- во-вторых, новые явные методы интегрирования систем специального вида должны существенно повысить эффективность

интегрирования по сравнению с классическими одношаговыми аналогами (преодоление барьеров Батчера);

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

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

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

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

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

- предложен подход в построении высокоэффективных явных одношаговых методов для каждого класса структурно разделяющихся СОДУ;

- получены условия порядка предложенных методов интегрирования классов СОДУ и методика использования упрощающих предположений их исследования;

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

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

Основные результаты диссертации, выносимые на защиту.

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

2. Построены и математически строго обоснованы алгоритмы выделении структурных особенностей нужного типа.

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

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

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

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

Апробация результатов диссертации. Результаты диссертации докладывались и обсуждались на следующих конференциях и семинарах: Механико-математического факультета МГУ (рук. академик РАН Н.С.Бахвалов)-1983 г.; СПбГУ (семинары кафедр теории управления, рук. чл.-корр. РАН Зубов В.И., и информационных систем, рук. д.ф.-м.н., проф. Кирин Н.Е., неоднократно); Всесоюзном семинаре «Вопросы оптимизации вычислений»,в Ин-ге кибернетики АН УССР, 1987; на Международной конфе-

ррнции «International Congress on Computer System and Applied Mathematics » St. Petersburg, 1993; на Международной конференции «Interval94»,St. Petersburg, 1994; на 1-й, II-й, Ш-й Международных конференциях «Beam dynamics and optimization», St. Petersburg, 1994,1995, 1996; Международная конференция «Еругин-ские чтения-Х», Могилев, 2005; Совещание-семинар «От спутников до галактик», Санкт-Петербург, 2005.

Публикации. По теме диссертации опубликована 31 работа. Основные результаты содержатся в работах [1| - [17].

Структура и объем диссертации Диссертация изложена на 300 страницах. Она содержит введение, 7 глав, заключение, список литературы, включающий 152 наименования, 1 приложение, 49 таблиц и 7 рисунков.

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

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

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

Первый класс — 2t(n) (системы разделяющихся ОДУ с перекрестной структурой связей)

У\ = fl(x,Vn),

У', = fAx>Vj-1)> j = 2,...,n,

(1)

здесь у3,/ц — функции размерности г8. Необходимость в интегрировании систем класса 21(г)=51(п) при п= 2

У'} = Мх,у2) }

2/2 = /2(3,01)

возникает достаточно часто в задачах моделирования механических и физических систем, задачах управления и оптимизации.

Например: при анализе динамики частиц в линейном ускорителе — уравнения, описывающие продольное движение электронов; в задачах небесной механики — задача двух Iел. Системы класса 21(п) при п> 3

у[ = Мх,Уп),

У3 = 1), j = 2,... ,п, п> 3, '

на прак тике встречаются несколько реже, чем системы (2). Например, задача оптимального быстродействия или дифференциальное уравнение п—го порядка у(п) = /(х, у).

Следующий, второй класс — 53 (системы структурно разделяющихся ОДУ)

Ж = Мх,у1,...,у{-\,у1+1,...,уп) , г = 1,2,...,;, . .

У] = ■■■,У]-\) , з=1 + 1,...,п,

где — функции размерности г3. К системам такого клас-

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

Последний, третий класс — <£ (системы структурно разделяющихся ОДУ общего вида)

Уо = Мх,Уо,У1,...,Уп), (5)

у'г = /г(х,У0, ■ ■ ■ ,Уг-\,У1+1, ■ ■ ■ ,Уп), ¿= 1,2,...,1, (6) У] = ЛС^.УО,---.^-!), з = 1 + 1,...,п, (7)

х€[Х0,Хк]С Я, I € {0} и И, пв {0} и IV, I < п,

п

= Уз-\Хо, Хк] 5 = 0,1,...,П,

5=0

I П

£г„=г*( /о:[Хо,Хк}х

и : [Хо, Хк) X ЛГ-^ — г = 1,2,..., I,

/,:[Х0= Л-1,...,п, го > 0.

Необходимость в интегрировании систем класса (Г возникает, например, в задачах анализа и синтеза различных систем ускорения и транспортировки пучков заряженных частиц.

В первой главе в рамках структурного подхода рассматривается явный метод интегрирования систем (5)-(7) класса (£ — метод класса <£. Приближение г3 к точному решению у3(х+к), з = 0,1,..., п в точке х + И € [Хо, Хк] ищем в виде:

Шя

у3(х + Н)ы г3 = у3{х) + ^ Ьзшкзи1(И), 8 = 0,1,... ,п, (8)

Ш=1

причем кзи, = кзт(Н) вычисляются в строгой последовательности ко1, кп,..., кп 1, к02, км,..., кп2, к0з, к^,... (9)

по схеме

Ко

кш (Тг1ц], У^ц^О) ■ • • > —1! 1; ■ • • ) ^г,и>,п) > ' = 1 > • • • > ^

кущ — И/^Ту^, У^щ^О) ■ • ■ , — 1)? 3 = I ■ ■ ■

где

г _ / х, если {(го = 1 Лй < пт

_ \ х + сзшк, если {(го = 1Лв > /) V (и; > 1)}, 1 и;

У Л*)

если {(w — 1) Л (s < /)}, если{(ги > 1) A (s < i/)}, kvfti если {(ги > 1) A (s > г/)} V{(w = 1) А (в > I)}.

(И)

Здесь Ьзш, саи>, ази}1/ц — параметры метода (8)-(11), /г — шаг метода.

Причем в общем случае т3 (число этапов) и (порядок метода) по .5-ой компоненте искомой функции — могут быть различны по каждой из компонент. Поэтому при построении расчетных схем метода их характеристикой могут выступать как векторы числа этапов М = (то,..., тп) и порядка С? = (до, • • •, <7п) , если хотя бы одна из компонент соответствующих векторов отлична от остальных, так и скаляры т и q , если компоненты соответствующих векторов равны между собой: то — •. ■ = тп — т ,

90 - • • • = Яп = Ч-

Замечание 1.1. В соответствии с требованием (9) алгоритма для компонент вектора числа этапов структурного метода (8)—(11) характерными являются соотношения

Определение 1.1. Пусть для некоторого вектора числа этапов в рамках одношагового метода существует расчетная схема порядка <5 = («¡»о, • ■ •, Яп)- Будем называть такой вектор числа этапов минимальным и обозначать М(С?) :

{тпо(яо),......,гпп{Яп)), если для любой М ~ (шо,...,тп)-

этапной расчетной схемы порядка <5 = (^о,.. -, Яп) этого же метода справедливы неравенства та > тя(д5), в = 0,1,... , п.

Приведем наиболее значимые новые результаты проведенных исследований в данной главе, представленные в виде следующих утверждений:

Теорема 1.1. Компоненты минимального вектора числа этапов М(2) метода (8)-(11) второго порядка численного интегрирования системы (5)-(7) класса С удовлетворяют равенствам: то = 2, тг = 2, тп} = 1, (г = 1,2,..., I, ] = I 4- 1,..., п).

то — т\ = ... = ms_i > mg = ... = тп,

(12)

Теорема 1.2. Компоненты минимального вектора числа этапов М{3) метода (8)—(11) третьего порядка численного интегрирования системы (5)-(7) класса (Г удовлетворяют равенствам: то = 3, т, = 2, т} = 2, (г = 1,2,..., I, з = I 4- 1,..., п).

Теорема 1.3. Компоненты минимального вектора числа этапов М{4) метода (8)- (11) четвертого порядка численного интегрирования системы (5)-(7) класса (Г удовлетворяют равенствам: то = 4, т* = 3, т3 = 3, (г = 1,2,..., I, 2 = / + 1,..., п).

Теорема 1.4. Компоненты минимального вектора числа этапов М{Ъ) метода (8)—(11) четвертого порядка численного интегрирования системы (5)-(7) класса (Г удовлетворяют равенствам: то = 6, т, = 5, т3 = 5, (г = 1,2,..., I, ^ = I -I-1,..., п).

Эффективность полученных М = (то(д),..., тп(д))-этапных методов д-ого порядка (по отношению к методу Рунге-Кутты) тем выше, чем больше отношение (коэффициент сравнительной

эффективности) Кд = (т(д) Е"=о Е"=о М?) ~ тз(?)] и>8> где т(д) - минимальное число этапов метода РК д-ого порядка, гия - весовые коэффициенты, либо задаваемые пользователем, либо вычисляемые как относительные доли затрат (число арифметических операций, время) на вычисления правой части /., от общего числа вычислений всех компонент вектор функции / = (/о,/ь-..,/п), 5 = о,...,п. Его значение для построенных здесь методов определяется равенствами =

кч = (дЕ^Г'Е^, 9 = з,4,

Кь = (6 Е"=0 И*,)"1 Е"=1 «V

Естественно, что в случае отсутствия групп уравнений (6), (7) в рассмотренной системе (5)(7) метод (8)—(11) тождествен традиционному методу Рунге-Кутты интегрирования систем (5).

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

Ее содержание тесно связано с развитием методов и алгоритмов современной теории комбинаторного программирования. Один из общих подходов исчерпывающего поиска оптимизационной задачи при ответе на вопрос «выбрать лучшую из всех возможных...» - поиск с возвращением. Непосредственное его применение приводит к алгоритмам, время работы которых недопу-

стимо велико. Хорошо известный вариант поиска с возвращением — метод ветвей и границ является специальным типом поиска с ограничениями.

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

z'k = <pk(x,z i,...,zm), к — 1,... ,т, (13)

предполагает, что существует преобразование, приводящее систему (13) к какому-либо из классов: 21(п), 23, (Г. В качестве такого преобразования выбираем перестановку (переобозначение) уравнений системы (13) и компонент искомой функции.

Задача состоит в том, чтобы указать такой порядок следования уравнений и нумерации переменных исходной системы (13), при котором для преобразованной системы

irz' — Ttip(x, 7Гz) (14)

с выделенными особенностями (5)-(7) эффект от применения структурного подхода будет максимальным, т.е. максимально отношение £Пго+1 W7r(s)/i2?= 1 W7r(s) ■

Здесь и в дальнейшем ttz = (z,r(i), zw(2), •.., ¿^(m)) , nip =

(Vtt(i)i <Лг(2)>- • • ,¥57r(m))T. ^ = (тг(1),тг(2),..., ..., тг(ш)) - перестановка элементов множества 1т = {1,2,..., т}, определяющая порядок следования уравнений системы (13). Причем здесь (для наглядности изложения алгоритма и постановки задачи) равенство 7г(г) = j — означает, что j — ое уравнение системы (13) будет занимать i - ое место в системе (14). Далее, w3 - весовые коэффициенты, либо задаваемые пользователем, либо вычисляемые как относительные доли затрат (число арифметических операций, время) вычисления правой части <ps от общего числа вычислений всех компонент вектор-функции <р = (<р\,<р2, ■ ■ ■ ,<fm), s = 1,2, ...,т. Обозначим через Р = {п} множество всех перестановок из т элементов 1т = {1,2,..., т].

Определение 2.1. Матрицу А = {%}"=! будем называть структурной матрицей системы обыкновенных дифференци-

альных уравнений (13) и обозначать А{ф), если её элементы

_ Го, если ¡рг не зависит от

ац ~~ 1 1, если <р{ зависит от

Определение 2.2. Множество, элементами которого являются номера компонент искомой вектор-функции г — {21, .... • • •, гт}, от которых не зависит правая часть г—ого уравнения СОДУ (13), будем называть 1-ым горизонтальным структурным множеством СОДУ (13) и обозначать Ег((р), т.е.

= {З € 1т ■■ <4? = 0, А{ф) = {аиц}™^}-

Определение 2.3. Множество, элементами которого являются номера уравнений СОДУ (13) с правыми частями не зависящими от j-oй компоненты вектор-функции г = {21,... ,гт}, будем называть ]-ым вертикальным структурным множеством СОДУ (13) и обозначать Н3(ср) :

= {г € 1т ■ а13 = 0, А(<р) =

Пусть г = (го,гь ... ,гп) € ({0} и х ТУ". Введем в рассмотрение 6(г, к) = Х^Го1 ¿(г>°) — 0. <*(г> п + 1) — т.

Определение 2.4. Будем говорить, что СОДУ (13) имеет нуль-структуру с параметрами I € {0} и Ы, п £ ЛГ, I < п, г - (г0 , Г\,... ,г„) € ({0} илг) х Мп, и обозначать ее ZS™[l,n,r], если для горизонтальных множеств справедливы включения:

{¿(г,») + 1,. -., 5(г, 1 + 1)} С ЕцгА+1,м{<р), * = 1 п>1> 0 ,

{<5(г, ;)+!>• ••.<5(^^+1)} С Е6[Т ¿)+ж){<р), г = 2+1,...,п, п>1> 0,

где /ф) = 1,... ,гя; в = 1,... ,п.

Определение 2.6. Будем говорить, что нуль-структура п, г] СОДУ (13) — предельная и обозначать ее 28т{р[1, п, г], если справедливы невключения:

{6(г11),...,б(г,1 + 1)}£Е61г1ф); I > 0, и {¿(г, 1 + 1),..., 8{г, п + \)} <£ Е6[гНф) ■ 1> 0.

Определение 2.7. Под объемом нуль-структуры Е3™[1,п, г] СОДУ (13) будем понимать величину 1и обозначать

ее где - весовые коэффициенты.

Можно показазать, что |2'5тп7Г¥,[^п,г]| > |, тт £ Р.

Сформулируем с использованием введенных понятий две рассматриваемые здесь задачи.

Задача 1. Найти перестановку 7г* £ Р такую, для которой справедливо неравенство ¡ЕЯ™к-<р[0,п,г]\ > п, г]| , У7г £

Р.

Задача 2. Найти перестановку п* £ Р такую, для которой справедливо неравенство \ZSтnn^v?[l,n,r]\ > \23т7Г^[1,п,г]\ , \Лг £ Р.

Определение 2.8. Множество ДДа^шг, •.. , и^) С 1т будем называть элементным нуль-структурным основанием СОДУ (13), если для В9 = — 0» 3 Ф Ч справедливы

включения [£ С Ек{<р), Ук 6 и)3, з = 1,..., й.

Определение 2.9. Для любого множества С! С 1щ величину Егес шг будем называть весом множества С? и обозначать V [С]:

V [С] = ][>,.

гбС

Пусть множество IV С 1т• Перенумеруем элементы этого множества с использованием чисел натурального ряда IV = ^гЛг, ■ ■ ■ Здесь и в дальнейшем |И^ = д — мощность множества IV. Введем в рассмотрение

Нг, я) = X)М', °) = <0 = г = (гь »-2, ■ • •, и) £ N4.

1=1

Теорема 2.1. Для того, чтобы множество В = {¿1, ¿2,..., гЛ было элементным нуль-структурным основанием 1,..., ш^), (<^1 = г3; .ч = 1,..., <1, СОДУ (13), необходимо и достаточно, чтобы

{V Ч(г4)+1~р) с Е*Р П нгНг,ы)+1-р

и

1)+1j ^/i(r,s—1)+2i • • • > ih(r,s—l)+k} С Elh(r s_1)ik(ip),

к = l,...,rs, s = l,...,d. 1 '

Здесь [а] - целая часть числа а € Я.

Теорема 2.2. Для того, чтобы на множестве перестановок Р = {7г} существовала такая п* € Р, что СОДУ (14) имела бы нуль-структуру ZS"i [0,п,г], необходимо и достаточно, чтобы существовало элементное нуль-структурное основание 1,...,и}п), для которого lüq = Im\B2 (toi,.. .,шп), а |ws| = г.9, s = 0,..., п. Причем n, г]| = V [В%] .

Теорема 2.3. Для того, чтобы на множестве перестановок Р = {я-} существовала такая перестановка ж* € Р, что СОДУ (14) имела бы нуль-структуру ZSJJl^Z.n.r], необходимо и достаточно, чтобы существовали два взаимно непересекающиеся множества — элементные нуль-структурные основания . ■. ,иц) и Bp(u)i+i,..., и>п), для которых и>о =

Лп\ , 1^1 = rSi s = о,...,п.

Причем |ZS$v[l, п,г]| = V [Bß + V {В*} .

Алгоритм решения задач 1,2.

Строим множество П^1-0) = {i Im : i £ Ег((р)}. Если множество fi(1'0) = 0, то V7r € Р, \ZSmvtp[l,n,r\\ = 0. Это значит, что никакое изменение порядка следования уравнений исходной системы не может обеспечить выделения групп уравнений, имеющих структурные особенности. Представляет интерес случай, когда П*1-0) ф 0.

I. Полагаем значение уровня дерева перебора р. — 0 и вводим в рассмотрение пару множеств В1 0 и В2 := 0. Для определенности будем именовать их рекордными. В них будут храниться лучшие по суммарному весу на момент прохождения по дереву перебора упорядоченные множества, построенные в результате работы алгоритма.

II. При сформированном множестве необходимо рассматривать два случая.

H.A. Если множество f^1'^ ф 0, то строим множества

Dft§{4>) = Et(<p) n #» n i € j е

и множество возможных продолжений

$0.«) = {7 = € х : {г,Л С

На каждом уровне дерева перебора вводим в рассмотрение пару вспомогательных множеств .Р^1'*1' := 0 и := 0.

Н.А.1. При - 0 переходим на пп.П.АЛ.Ь алго-

ритма.

Если же ^ 01 То ищем претендента г* £

на роль центрального элемента:

к;,. — тах и>г.

Причем, если

то переходим на пп.П.А.1.с. В противном случае, при ^ 0 ищем очередного

претендента (3* = 3£) € на роль узлового элемен-

та на д-ом уровне,

>

Далее сравниваем веса претендентов на роль узлового и центрального элементов

U0'

> 11V.

(17)

Если неравенство (17) не выполняется, то переходим на пп.И.АЛ.с.

В противном случае, при выполнении неравенства (17) элемент ¡3* становится узловым = /3* на /г-ом уровне перебора, но только при выполнении неравенства

М-1

i=o

+ V

0-

>

^(v^j+v^2]), (18)

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

/?*, выбранный в качестве узлового на ц—м уровне, запоминаем как использованный := С^^1^) и {/З^-1'^}. Формируем множе-

ство = /З^1'^} и, увеличивая номер уровня

у. := (1 + 1, переходим на nn.II алгоритма.

В случае, если неравенство (18) не выполняется, то переходим на пп.Н.А.1.Ь.

Н.А.1.Ь. Если уровень дерева перебора нулевой (/х = 0), то переходим на пп. V алгоритма (переборная часть алгоритма закончена). Рекордные упорядоченные множества В1 и В2, определенные на этот момент, и являются искомыми.

В противном случае (при ц > 0), очищаем рабочие множества и, понижая уровень дерева перебора ц ц — переходим на пп. И.А.1.

П.А.1.С. Элемент г* становится центральным на ц-ом уровне перебора только при выполнении неравенства

Ги^.^^^^^+У^]). (19)

+ V

"¿=0

В случае, если справедливо неравенство (19), элемент г* включаем в список использованных в качестве центральных на //-ом уровне .Р^) := и {г*}, а затем строим упорядоченное мно-

жество В1. Количество элементов множества В1 = {¿1, ¿2,..., г^} нечетно (к = 2/г + 1) и сформировано по правилу

= = £ = 0,1,. . - 1;, ¿м+1 = г*.

После построения множества В1 поднимаемся вверх по дереву перебора для построения второго упорядоченного множества В , переходя на пп.Ш алгоритма.

В случае бесперспективности продвижения по этой ветви (неравенство (19) не выполняется) переходим на пп. Н.А.1.Ь.

Н.В. Если множество = 0, при ц > 0, то построе-

ние возможного варианта упорядоченного множества В\ — {¿1, ..., г*;} закончено. Оно будет содержать к — 2ц элементов, которые определяются по правилу: = ~ £ =

О,1,... ,/w —1. Для построения второго упорядоченного множества В2 переходим на пп.111 рассматриваемого алгоритма.

Если множество П'1^ = 0, при р = 0, то в рамках рассматриваемых преобразований не существует перестановки, приводящей систему к нужному виду.

III. Перебор при решении задачи 1 начинается с этого пункта алгоритма. Причем полагаем именно в этом случае В1 := 0, В1 := 0, В2 := 0.

Для решения задачи 1,2 строим множество П^2,0) = П^^^В1 при сформированном упорядоченном множестве В1. Вводим вспомогательное множество — 0. Значение номера уровня на втором дереве перебора полагаем и = 0.

IV. При сформированном множестве необходимо рассматривать два случая.

IV.А. Если множество П^2'"' ф 0, то строим множества

и множество возможных продолжений S^2'^ на и—ом шаге алгоритма при выбранных узловых элементах: ..., а^-1^.

SM = {7 = (i,j) е SlM х nф j : {i,j} с

Причем на каждом уровне при обновлении fii2'") находим претендента j* на роль центрального = maxten(2,„) wt.

IV.А.0. При рассмотрении построенного множества S^2^ необходимо рассматривать два случая.

IV.A.l.a. Если = 0, то переходим на nn.IV.A.l.c

алгоритма. В противном случае, при Ф 0 ищем пре-

тендента на роль узлового элемента а* € S^'^XQ^2^. Среди не рассматривавшихся ранее в качестве узловых на i/-om шаге ему отвечает множество Da-, имеющее наибольший вес:

V [£Ы = шах V [£>„].

Далее проводим сравнение весов

У[Д*.] >у)У. (20)

Если неравенство (20) не выполняется, то переходим на nn.IV.А.1.с.

В противном случае, необходимо провести проверку на целесообразность дальнейшего продвижения по ветви а^, ..., а*_ Если неравенство

у[в*] +v[Di2;l')] >у[вг] + У[В2] (21)

€=о

не выполняется, то переходим на nn.IV.А.1.Ь.

При выполнении неравенства (21) элемент а* становится узловым: аМ = а* на г/-ом уровне алгоритма.

Для перехода на следующий верхний уровень дерева перебора дополняем множество использованных в качестве узловых элементов ф^2'") := С}^ и {<*(1/)}, формируем множество П(2'"+1) = ^мЧ> }• Затем, увеличивая номер уровня (и := и + и

вводя множество := 0, переходим на nn.IV.

ГУ.АЛ.Ь. При и > 0 необходимо вернуться на предыдущий (нижний) уровень. Для этого очищаем множество С^2-") := 0, уменьшаем номер уровня второго дерева перебора на единицу (и := и — 1) и переходим на пп. IV.А.0 данного алгоритма.

Если же и = 0, то работа алгоритма по поиску наилучшего упорядоченного множества В2 при фиксированном В1 закончена.

При решении задачи 1 найденное рекордное множество В2 и есть искомое. Для продолжения решения этой задачи требуется перейти на пп.У алгоритма.

При решении задачи 2 необходимо перейти на пп.И.А.1 для построения нового упорядоченного множества В1.

1У.А.1.С. Элемент ]* становится центральным на и—ом уровне перебора только при выполнении неравенства

У^1] + У^а^а?0}] > V [в1] + V [в2]. (22)

,х=0

В этом случае необходимо сформировать упорядоченное множество В2 = {¿1, ¿2,..., и}. Количество его элементов нечетно (к = 2и + 1) и определяется по правилу

= гк_( = а£\ £ = 0,1,..., и - 1; г„+1=у*.

При сформированном В2 необходимо перейти на nn.IV.В.1.а.

Если же неравенство (22) не выполняется, то переходим на ппЛУ.А 1 Ь

IV.В. Если множество = 0, то возможны два случая.

IV.В.1. При V ф 0 проход По этой ветви закончен. Причем В2 = {¿1, ¿2,..., будет содержать к = 2ь> элементов, которые определяются по правилу: = а^, = £ — 0,1,...,!/- 1.

1У.В.1.а. Следует провести замену рекордных упорядоченных множеств В1 := Вх и В2 := В2. Причем, если справедливо равенство

v[s1]+v[JB2]=v[fi(1'0>]) (23)

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

Если равенство (23) не выполняется, то следует продолжить перебор. Для этого надо перейти на nn.IV.А.1.Ь.

IV.В.2. При V = 0 на множестве /т\Вг не существует упоря-дочрнного непустого множества В2 с заданными свойствами. При В1 ф $ рекордными становятся В1 = В1, В2 = 0. После этого переходим на пп.У.

Работа алгоритма по пп. 1-1У будет закончена естественным образом на нулевом уровне дерева перебора при бесперспективности продолжения перебора с построенными упорядоченными множествами В1 и В2. Только после этого выполняется следующий пункт алгоритма.

Замечание 2.1 Элементы любого упорядоченного множества В* = {¿ъ ¿2> • • •) я = 1,2, построенного по пп. I-IV' данного алгоритма, удовлетворяют условию (15) теоремы 2.1.

\

1

Замечание 2.2 Для любого упорядоченного множества В" — {¿1, ¿2, • • • , н}, в = 1,2, построенного по пп.ЫУ, можно провести разбиение на классы.

V. Руководствуясь правилом замечания 2.2, проведем поочередно разбиение рекордных множеств на классы. Сначала сделаем это для упорядоченного множества В2 = В2(и>1,Ш2,. ■ ■ а

затем для В1 = Д* (1^+1,04+2, ■ ■ -,шп).

Замечание 2.3 Результатом работы алгоритма является построение двух взаимно непересекающихся элементных нуль-структурных оснований В1, В2 — пары, имеющей максимальный суммарный вес.

Замечание 2.4 Руководствуясь утверждениями теоремы 2.2 (для решения задачи 1) и теоремы 2.3 (для решения задачи 2), для любой пары Вф(и)1+1,Ш1+2,... ,шп) и В2(ш 1,и>2, • • • элементных нуль-структурных оснований (полученной в результате работы пп. 1-У алгоритма) можно построить перестановку 7г € Р, на которой СОДУ (14) имеет нуль-структуру гБ^Ц^^г], I € N.

VI. Руководствуясь замечанием 2.4, на базе рекордных элементных нуль-структурных оснований В1, В2 строим искомую перестановку 7г*, которая является решением задачи 1 или задачи 2.

Отдельно следует отметить, что для использования алгоритма при решении задачи 1 необходимо считать постоянно В1 = 0 и В1 = 0. Начать работу алгоритма следует с пп.Ш и ограничить только перебором по верхнему дереву, т.е. требование спуститься по дереву перебора на поиск нового упорядоченного множества В1 означает (при решении задачи 1) окончание перебора с переходом на пп. V.

В третьей главе в рамках структурного подхода рассматривается явный метод интегрирования систем (2) класса 21(2) — метод класса 21(2). Отсутствие общей группы уравнений дает дополнительные алгоритмические возможности при конструировании эффективных методов вида

т.

уя{X + К) « ¿а = У„(х) + ^2ьз1/к*и(Ь), я = 1,2, (24)

1/=1

где функции кЯ1/ = кЯ1/(К) вычисляем в строгой последователь-

ности кц, к2\, ¿12, ¿22, • • • по схеме

к _ Г к/1(х,у2(х)), ^ и = 1,

V

к2и = Ь/2(х + с2и}г, ух (х) + а21П)ки,), с2х ф 0. (26)

т/=1

Здесь ть - число этапов (количество вычислений в-ой правой части системы (2) на шаге интегрирования, причем т\ > т2 в соответствии с замечанием 1.1 ), Ьа1/,сви,,а$1/Г)- параметры метода (24)-(26), Н - шаг метода.

Алгоритмический учет структурных особенностей интегрируемой системы (5) -(7) класса £ дал возможность в первой главе получить расчетные схемы интегрирования систем (2) класса 21(2), для которых при Ш1 = т2 справедливы равенства тп8 = <7, - 1, <ь < 4 . В начале этой главы рассматриваются возможности структурного подхода для разноэтапного метода (24)-(26) При 7711=7712 + 1-

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

Во втором параграфе третьей главы этот вопрос изучается для числа этапов т\ = 3, т2 = 2.

Теорема 3.1. В рамках М = (3,2)-этпапного метода (24)-(26) численного интегрирования систем (2) класса 21(г) не существует расчетной схемы с порядком ф = (4,3).

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

В основе первого — идея минимизации количества слагаемых г лавного члена погрешности по первой компоненте. Для построенной в соответствии с этим требованием расчетной схемы третьего порядка характерно, что вычислительная схема по второй компоненте базируется на двухточечной квадратурной формуле Гаусса-Лежандра. Ее абсциссами являются нули сдвинутого полинома Лежандра второй степени, определенного на отрезке [0,1].

В основе второго — идея минимизации фактического количества этапов. Это достигается тем, что последний третий этап по первой компоненте на текущем шаге является первым этапом на следующем (принцип FSAL — First Same As Last).

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

Теорема 3.2. В рамках М = (4,3)-этапного метода (24)-(26) численного интегрирования систем (2) класса 21(2) не существует расчетной схемы с порядком Q = (5,4).

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

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

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

Четвертый параграф третьей главы посвящен рассмотрению следующего этапа в изучении возможностей структурного подхода при интегрировании системы (2) класса 21(2).

Теорема 3.3. В рамках метода (24)-(26) численного интегрирования систем (2) класса 21(2) существует четырехэтапная расчетная схема пятого порядка.

Доказательство этого утверждения потребовало поиска частного решения условий порядка, которые (при выполнении ограничений aspt — csp) представляют собой систему 41 нелинейно-

го алгебраического уравнения с 31 неизвестными с^, ачз. Коэффициент сравнительной эффективности полученной здесь че-тырехэтапной расчетной схемы пятого порядка определяется равенством Къ = 1/3.

В четвертой главе для систем (3) класса 21(п), п > 2 рассматриваются методы их интегрирования — методы класса 21(п), П > 2.

Приближение гг, г = 1,..., п к точному решению уг(х + К) в точке х + к при известном точном решении у, (х) ищем в виде

ш,

уг{х + /г) « гг = уг{х) + ^^^(/1), г = 1,...,п, (27)

.7=1

где функции кг] = кг](Н) вычисляем но схеме

{И/1(х,уп(х)) , если ] = 1,

(28)

/1/1 (х + С1]Н,уп(х) + а^зкпз) , если 3 > 1,

з

кг)] - к/^х + ^Н, 2/^-1 (х)-I-77 = 2, ...,п, (29)

3=1

в строгой последовательности /сц, к21, ■ ■ ■, кп\, к 12, &22, - • ■; гп{ - число этапов (количество вычислений г-ой правой части системы (3) на шаге ин тегрирования). Здесь Ьч, с^, агзз - параметры метода (27)—(29); /г - шаг метода.

Теорема 4.1. В рамках метода (27)-(29) численного интегрирования системы (3) класса 51(п) при П> 3 существует расчетная схема четвертого порядка с числом этапов т\ = 3,... ,ш„_1 = 3, тпп = 2.

Доказательство этого утверждения потребовало поиска решения условий порядка, которые (при выполнении ограничений = Су) образуют систему 8п нелинейных алгебраических уравнений с 12тг — 9 неизвестными Ъг], с^, ачз. Причем при доказательстве использован как аппарат упрощающих предположений (для получения частного решения), так и вывод общего решения

условий порядка. Выписаны два семейства расчетных схем четвертого порядка для систем (3) класса 21(п), П > 3 Коэффициент сравнительной эффективности построенных расчетных схем определяется равенством К4 — (1 + иоп/ /4-

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

Приближенное решение при интегрировании системы (4) ищется в виде

4

уа(х + Н) и га = уа(х) + ^Ьцркцр^), в = 1,...,п, (30)

р= 1

где функции кзр = кзр(К) вычисляем в строгой последовательности кп,к21,--.,кП1,к12,к22,---, по схеме

р

кгр = И,/г(х + сгрН, у\(х) + У * агр\^к\^,...,

4=1

р р-1

77=1 >7=1

р-1

Огрпг]кпт7)1 (31)

»7=1

Р

кур = Н/у (х -(- с3рк, у\ (х) + ^ ^ &}р\г)к\т}) ■ ■ - 1

77=1

р 77=1

Су, = о, г = 1,2,..., г, з = 1 + \,...,п.

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

0>spvT/5 йр : Csp ■

C\p = . . . = Clp Cip, bip = ... — bip —'. bip, а2рЬ, ~ Û3pl?j = а3р2т; = • • • - typlr, = • • • = Щ,р,1-l.r, =: %lr;, Ûi + 1,P,1,T/ — . . . — û/+l,p,i,JJ — . . . = Ûnpl»J ~ - ■ • — &пр1т) =" ûjpjjj,

Н,р — • • • — Cnp =: cjp> ^¿+1,р — • • ■ — &np =: bjp, (32)

®l,JJ,i+l,7J • • • pnjj — • • • — — . . . = QlpniJ O'tpjrjl

o-t+2,p,111,77 = ai+3iPi/+ijT) = а/+з,р,;+2,?7 = • • • ... = Qn,p,i+i,rç — • • - = о.ПрП-\%у =: о, ~ .

Здесь и в дальнейшем индексы г € {1,...,/}, j £ {/ + 1,... , п}, г € {1,..., г - 1}, j € {/ + 1,..., j — 1} параметров метода с,р, cJP, bip, bjp.

агргту> amv ajw ûjpjr) носят признанный характер. Так индекс на первой позиции является признаком принадлежности параметров к структурно разделенным группам уравнений системы (4): «г» — к первой, «j» - ко второй. Принадлежность же к группам компонент искомой вектор-функции определяется индексом на третьей позиции: «г», «г» — к первой, «j», «j» — ко второй соответственно.

Условия порядка для метода (30)—(31 ) пятого порядка даже с использованием равенств (32) и стандартных предположений o-spgt = csp представляют собой систему 102 нелинейных алгебраических уравнений с пятьюдесятью неизвестными.

Теорема 5.1. В рамках четырехэтапного метода (30) (31) существует расчетная схема пятого порядка численного интегрирования систем (4) класса 05.

При доказательстве построена четырехэтапная расчетная схема пятого порядка — РСЪ, превосходящая первый барьер Батче-ра по каждой из компонент на две единицы. Коэффициент сравнительной эффективности построенной РСЪ определяется равенством — 1/3.

В качестве одного из оппонентов всем полученным в работе расчетным схемам {PC) использовался метод DP5(4)7F. Аббревиатура метода сообщает о типе метода {DP — Дормана-Принса), о порядке приближения («5»), оценщика «погрешности» («4»), о числе этапов («7»), а также об использовании идеи F SAL.

Анализ результатов численного тестирования (зависимость нормы максимальной глобальной погрешности от величины шага

интегрирования) полученной здесь расчетной схемы пятого порядка, классического метода Рунге-Кутты четвертого порядка (RK4) и метода Дормана-Принса (DP5(4)7F) подтвердил теоретическое ожидание. При равных вычислительных затратах с RK4 построенная схема PC5 на порядок точнее. При равных же порядках погрешности схем DPb{4)lF и РСЪ последняя на трегь экономичнее.

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

Параметры т = (mi,...,тп)-этапного вложенного p(q) метода (24) (26) интегрирования систем (2), (4) должны обеспечивать для величин zs, s = 1,..., тг, порядок точности р (ys(x + h) — zs = 0(hp+l)), а для (оценщиков «погрешности»)

ТПя

zs = уа{х) + ^2dsl/ksl/, уа(х + h) - zs = 0(hq+1), s = 1,..., n, (33)

порядок q. Причем здесь рассматриваются методы, для которых Р > Я-

Приведем наиболее значимые новые результаты проведенных исследований в данной главе.

Теорема 6.1. В рамках М = (4,3)-этпапного метода (24)-(26) численного интегрирования систем (2) класса 21(2) существует вложенный метод четвертого порядка с оценщиком «погрешности* порядка Q = (3,2) - РС4((3,2))(4,3)F.

Условия порядка для метода (24)-(26) при стандартных предположениях aspt - csp в этом случае представляют собой систему 32 нелинейных алгебраических уравнений с 32 неизвестными.

Теорема 6.2. В рамках пятиэтапного метода (24)-(26) численного интегрирования систем (2) класса 21(2) существует вложенный метод пятого порядка с оценщиком <tпогрешности» четвертого — PC 5(4)5.

Условия порядка для метода (24)-(26) при стандартных предположениях 1 аарг — сяр в этом случае представляют собой систему 59 нелинейных алгебраических уравнений с 52 неизвестными. При доказательстве этой теоремы было построено шести-параметрическое семейство методов с требуемыми характеристиками. Любой метод из этого семейства имеет очевидное преимущество перед существующими. Для получения приближения к решению пятого порядка с возможностью автоматического выбора шага требуется всего пять этапов. В некоторых частных случаях (например, при интегрировании дифференциального уравнения специального вида у" — /(х,у)) порядок основного метода и оценщика «погрешности» один и тот же (пятый) для любого метода из этого семейства. Это делает практическое использование полученного метода ограниченным и является основанием для построения вложенного метода пятого порядка с менее жесткими требованиями на порядок оценщика.

Теорема 6.3. В рамках пятиэтапного метода (24)-(26) численного интегрирования систем (2) класса 21(2) существует вложенный метод пятого порядка с оценщиком «погрешности» третьего — РС5(3)5Р.

Вложенный структурный метод РС5(3)5Р использует пять этапов по каждой компоненте, но фактически в случае удовлетворительного соотношения между оценкой «погрешности» и максимально допустимой заданной ее величиной последние вычисленные на текущем шаге коэффициенты Жг^Л), используемые в оценщике, являются первыми на следующем шаге.

Условия порядка для метода (24)-(26) при стандартных предположениях 1 азрг = с»р в этом случае представляют собой систему 60 нелинейных алгебраических уравнений с 52 неизвестными. Реализованный в работе в рамках структурного подхода алгоритм РБАЬ позволил построить расчетную схему РС5(3)5Р. Тестирование полученной схемы показало, что РС5(3)5Р на треть экономичнее метода 1)Р5(4)7Р, что согласуется с теоретическими ожиданиями.

Теорема 6.4. В рамках пятиэтапного метода (30)—(31) существует расчетная схема вложенного метода с характеристиками 5(3) бЁ численного интегрирования систем (4) класса

Условия порядка для вложенного метода (30)-(31) при стандартных предположениях аардг — сар в этом случае представ-

лягат гобой систему 138 нелинейных алгебраических уравнений с 81 неизвестными. Найдено ее частное решение — грехпараметри-ческое семейство расчетных схем PC5(3)5F.

Анализ результатов численного эксперимента показал, что PC5(3)5F на треть экономичнее схемы DP5(4)7F, что согласуется с теоретическими ожиданиями.

Второй параграф седьмой главы посвящен установлению связи методов интегрирования дифференциальных уравнений в торого порядка, правая часть которых не зависит от первой производной у" = f{t,y) (типа Нюстрёма), и полученных в работе методов интегрирования систем (2) класса 2t( z) (включая и вложенные типа Дормана-Принса). Отмечено, что в силу несимметричности вычислительного алгоритма (24)-(26) относительно номера компоненты после его приведения к виду экономичному и алгоритмически простому для непосредственного интегрирования дифференциального у" = f(t,y) он допускает две формы представления. Причем одна из них совпадает с методом Нюстрёма, а вторая — расширяет его в постановочной части.

В третьем параграфе седьмой главы демонстрируется использование методов интегрирования систем (4) класса 03 и построение на их базе эффективных прямых методов интегрирования (включая и вложенные типа Дормана-Принса) системы дифференциальных уравнений второго порядка с перекрестной зависимостью правых частей от первых производных

х" = f{t,x,y,i/), у" = g(t,x,y,x'). (34)

В силу перекрестной зависимости правой части рассматриваемой системы (34) от первых производных использование существующих вложенных прямых методов интегрирования дифференциальных уравнений второго порядка специального вида (типа Нюстрёма) для ее интегрирования невозможно.

Применение же для интегрирования (34) вложенного метода (30)—(31) и последующее приведение его к виду алгоритмически простому даег1 вычислительную схему пятиэтапного метода третьего порядка прямого интегрирования системы (34) и вложенную в нее четырехэтапную схему пятого порядка. Получены расчетные схемы пятого порядка прямого интегрирования системы (34): РСНЪ чегырехэтапного метода типа Нюстрёма и PC#5(3)5F

— вложенного метода типа Нюстрёма Дормана-Принса. Причем РСНЬ, PCH5(3)5F на треть экономичнее существующих аналогов.

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

Основные результаты диссертации опубликованы в следующих работах:

1. Олемской И. В. Об одном методе численного интегрирования систем дифференциальных уравнений, описывающих динамику заряженных частиц в линейном ускорителе//Вопросы атомной науки и техники. Вып. 1(7), серия: техника физического эксперимента. 1981, С. 17.

2. Олемской И. В. О модификации метода Рунге-Кутты // Некоторые вопросы качественной теории дифференциальных уравнений и теории управления движением. Саранск,1983, С. 99104.

3. Олемской И. В. О численном методе интегрирования систем обыкновенных дифференциальных уравнений// Оптимальное управление в механических системах. Jl.,1983. С. 178-185.

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

5. Олемской И. В. Структурный метод интегрирования систем обыкновенных дифференциальных уравнений/ Межд.конф. "International Congress on Computer System and Applied Mathematics".St.Petersburg, 1993. C. 52.

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

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

2000. С. 218-220.

8. Олемской И. В. Расчетные схемы третьего порядка точности. Процессы управления и устойчивость. //Тр. XXXII научн. конф. СПб: ООП НИИ Химии СПбГУ. 2001. С.85-88.

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

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

11. Олемской И. В. Алгоритм выделения структурных особенностей //Николай Ефимович Кирин: Сб. стат., 2003. С. 234-251.

12. Олемской И. В. Методы типа Рунге-Кутты интегрирования систем и дифференциальных уравнений второго порядка специального вида // Вычисл. технологии. 2004. Т.9, №2. С. 67-81.

13. Олемской И. В. Вложенные методы пятого порядка // Вестн. С.-Петерб. ун-та. 2004. Сер. 10, вып. 2. С. 82-93.

14. Олемской И. В. Конструирование явных методов типа Рунге- Кутта интегрирования систем специального вида// Изв. Вуз. Математика. 2005. №2 (513). С. 75-80.

15. Олемской И. В. Явный метод типа Рунге-Кутты пятого порядка // Вычисл. технологии. 2005. Т.10, №2. С. 87-105.

16. Олемской И. В. Вложенный пятиэтапный метод пятого порядка типа Дормана-Принса //Журн. вычисл. математики, и мат. физики. 2005. Т. 45, №7. С. 1181-1191.

17. Олемской И. В. Метод пятого порядка типа Рунге-Кутты интегрирования систем структурно разделенных дифференциальных уравнений // Вестн. С.-Петерб. ун-та. 2005. Сер. 10, вып. 1. С. 39-48.

I

6?93

Отпечатано копировально-множительным участком отдела обслуживания учебного процесса физического факультета СП6ГУ. Приказ № 571/1 от 14.05.03. Подписано в печать 12.01.06 с оригинал-макета заказчика. Ф-т 30x42/4, Усл. печ. л. 2. Тираж 120 экз., Заказ № 279/с 198504, СПб, Ст. Петергоф, ул. Ульяновская, д. 3, тел. 428-43-00.

1 МЕТОДЫ КЛАССА (£

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

1.2. Условия порядка.

1.3. Метод второго порядка.

1.4. Метод третьего порядка.

1.5. Метод четвертого порядка.

1.6. Метод пятого порядка.

1.6.1 Условия порядка.

1.6.2 Алгоритм построения явного метода пятого порядка.

2 ВЫДЕЛЕНИЕ СТРУКТУРНЫХ ОСОБЕННОСТЕЙ

2.1. Постановка задачи.

2.2. Основные понятия.

2.3. Алгоритм решения задач 1,2.

2.4. Пример применения алгоритма выделения структурных особенностей

2.4.1 Равноправные правые части.

2.4.2 Неравноправные правые части.

3 МЕТОДЫ КЛАССА 21(2) 104 3.1. Метод интегрирования.

3.2. Методы третьего порядка.

3.2.1 Расчетные схемы третьего порядка на базе квадратурных формул Гаусса-Лежандра.

3.2.2 Двухэтапные расчетные схемы третьего порядка . ИЗ

3.3. Методы четвертого порядка.

3.3.1 Исследование условий порядка разноэтапного метода

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

3.3.3 Трехэтапный метод четвертого порядка на базе квадратур Лобатто.

3.3.4 Вычислительная схема на базе трёхточечного квадратурного правила Гаусса-Лежандра

3.4. Четырехэтапный метод пятого порядка.

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

3.4.2 Условия порядка.

3.4.3 Расчетная схема пятого порядка.

4 МЕТОДЫ КЛАССА 21 (п)

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

4.2. Метод четвертого порядка.

4.2.1 Исследование условий порядка.

4.2.2 Расчетные схемы четвертого порядка, коэффициенты которых зависят от размерности системы

4.2.3 Расчетные схемы четвертого порядка, коэффициенты которых не зависят от порядка системы.

4.3. Частное решение.

5 МЕТОДЫ КЛАССА

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

5.2. Условия порядка.

5.3. Тестирование.

6 ВЛОЖЕННЫЕ МЕТОДЫ КЛАССОВ 2l(z) и

6.1. Методы типа Дормана-Принса.

6.2. Вложенный метод класса

6.2.1 Метод четвертого порядка.

6.2.2 Методы пятого порядка.

6.2.3 Тестирование.

6.3. Вложенный метод класса 03.

6.3.1 Метод пятого порядка.

6.3.2 Тестирование.

7 СВЯЗЬ МЕТОДОВ НЮСТРЕМА И СТРУКТУРНОГО ПОДХОДА

7.1. Методы интегрирования дифференциальных уравнений второго порядка.

7.2. Метод класса 21(2) и его реализация при интегрировании дифференциальных уравнений второго порядка специального вида.

7.2.1 Методы типа Нюстрёма.

7.2.2 Вложенные структурные методы типа Нюстрёма-Дормана-Принса

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

7.3.1 Структурные методы типа Нюстрёма интегрирования систем специального вида

7.3.2 Вложенные структурные методы типа Нюстрёма интегрирования систем специального вида.

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

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

В этот период были выполнены фундаментальные исследования по устойчивости численного решения ОДУ , теории конструирования и реализации методов интегрирования [8, 16, 17, 19, 18, 22, 24, 25, 26, 27, 45, 114, 148].

Так в классе одношаговых методов за это время и способ вывода условий порядка [13,104, 137] (с помощью помеченных деревьев), и конструирование [15, 31, 106, 135] (с использованием упрощающих соотношений) расчетных схем эволюционировали в основном под влиянием работ Дж. Батчера, Э. Хайрера, Г. Ваннера [107, 109, 110, 111, 125, 129]. Разработанная Дж. Батчером абстрактная алгебраическая теория методов Рунге-Кутты [12, 14, 105, 108, 110] открыла большие возможности для теоретического исследования их свойств и для конструирования [2, 5, 92, 93, 94, 138, 141] новых высокоэффективных алгоритмов. Следует обратить особое внимание на то, что для предложенного Э. Хайрером составного метода типа Рунге-Кутты интегрирования систем разделяющихся обыкновенных дифференциальных уравнений (СРОДУ) первого порядка была создана [129] теория условий порядка, обобщающая идеи Батчера. Это обеспечило подход к условиям порядка для широкого класса методов. Обобщение теории условий порядка на случай СОДУ высоких порядков произвел Хебзакер [131].

В начале 60-х Дж. Батчером [105, 108] и Г. Шанксом [151] был установлен первый барьер (Батчера [90]): для q > 5 не существует явных методов РК порядка q с числом этапов т = q. Следующие два барьера — для методов седьмого и восьмого порядков — также были получены Дж. Батчером [108, 112].

В этот период развивались и способы оценки погрешности численного интегрирования: полной и локальной. [9,11, 28, 42, 77, 99, 103, 123, 152].

Впервые в работах Р. Мерсона, Ф. Ческино, Дж. Зонневельда [ИЗ, 137, 149, 153] была использована идея, которая легла в основу нового семейства одношаговых методов — вложенных. Свое развитие эти методы получили в серии работ Р. Ингланда, Е. Фельберга [78, 118, 119, 120, 145,148]. На сегодняшний день используются два типа вложенных методов. Для первого типа (Фельберга) характерно, что определение главного члена погрешности метода интегрирования на одном щаге осуществляется по двум формулам Рунге-Кутты разных порядков р и q (р < q) соответственно. Причем в качестве искомого приближения в случае принятия такого решения берется приближение порядка р. Разница приближений разного порядка позволяет оценить локальную погрешность полученного приближения. Для вложенных же методов второго типа (Дормана-Принса) в качестве приближения к решению выбирается приближение старшего порядка q, а разница двух приближений используется лишь в алгоритме выбора шага [115, 116].

Параллельно с разработкой вложенных методов для уравнений первого порядка велись работы [117, 121, 122] по конструированию аналогичных методов типа Нюстрёма [97,102, 117, 121,122,126,127,130,140] для дифференциальных уравнений второго порядка.

В 60-ые годы возникло понятие жестких систем, которое к концу 70-ых оформилось в отдельный класс. Проблемы, связанные с жесткостью, потребовали создания новых методов, новых подходов [19, 23, 29, 79, 82, 83, 91, 106, 139, 142, 143, 144, 146, 147, 150], рассчитанных на решение задач этого класса.

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

Наиболее общая схема явного метода Рунге-Кутты численного интегрирования СОДУ fs(x,yo,.--,yn), s = 0,1,. ,п, ys(X0)=ysо, s = 0,1,., п, хе[Хо,Хк]с R, ys:[X0,Xk]—*R,

0.0.1) (0.0.2) fs:{X0,Xk}xRn+l -+R, s = 0,1,.,n дана в [39] ys(x + z8 = ys(x) + bswksw(h), s = 0,1,., n,

0.0.3) где функции ksw = ksw(h) вычисляются по схеме w-i ksw = hfs(x + cswh, y0(x) + asw0gk0g,.

5=1

0.0.4)

9=1 csi = 0, aswti = 0, t = 0,l,., n.

Здесь ys(x + h),zs — соответственно точное и приближенное значение s—ой компоненты в точке х + h 6 [Xo,Xk], ys(x) ~ точное значение s-ой компоненты в точке х 6 h - шаг метода. Причем в общем случае ms (число этапов) и qs (порядок метода) по s-ой компоненте искомой функции могут быть различны по каждой из компонент. Поэтому при построении расчетных схем метода их характеристикой могут выступать как векторы числа этапов М = (то,., тп) и порядка точности q — (?о> • • • ? Qn) , если хотя бы одна из компонент соответствующих векторов отлична от остальных, так и скаляры т и q , если компоненты соответствующих векторов равны между собой: то = . = тп = т , qo = . = qn = q. Введем понятие, необходимое для сравнения методов интегрирования систем обыкновенных дифференциальных уравнений.

Определение 0.1 Пусть для некоторого вектора числа этапов в рамках одношагового метода существует расчетная схема порядка Q = (qo,.,qn). Будем называть такой вектор числа этапов минимальным и обозначать M(Q) = (mo(<?o),.>^n(?n))> если для любой М = (то,.,тп)-этапной расчетной схемы порядка Q = (#о, • • - ,Яп) этого же метода справедливы неравенства ms > s = О, 1, . ,71.

В скалярном случае минимальное число этапов метода порядка q будем обозначать m(q).

При построении расчетных схем в рамках метода (0.0.3), (0.0.4) традиционно, в силу равноправности уравнений системы [4, 6, 8, 9, 10, 20, 39], параметры метода полагают bw = bSW) Cw = Caw, йщ = Q>swtgi ТП = TTlSi независящими от номера компоненты s . Такой способ распространения метода интегрирования уравнений на системы (назовем его формальным), с одной стороны, сужает возможности метода (0.0.3), (0.0.4), а с другой стороны, значительно упрощает задачу конструирования методов интегрирования систем. В этом случае методы строятся для скалярных уравнений, а распространение на системы осуществляется простой заменой скалярных функций у, /, ks на соответствующие векторные. При этом все утверждения о соотношении порядка точности метода q и числа этапов т, справедливые для скалярного случая, верны и для векторного.

В связи с этим напомним [4, 6, 8, 9, 10, 20, 39, 84, 90], что для явного метода Рунге-Кутты q-го порядка численного интегрирования дифференциального уравнения минимальное число этапов удовлетворяет равенствам m{q) = q, q < 4; m(5) = 6, m(6) = 7, m(7) = 9. (0.0.5)

Причем равенства (0.0.5) справедливы не только для формального метода интегрирования системы (0.0.1), но и для общей схемы метода (0.0.3), (0.0.4).

На сегодняшний день формальный метод Рунге-Кутты является самым распространенным. Пожалуй, единственный известный метод, ориентированный на интегрирование СОДУ (0.0.1) — составной неявный метод [129] для разделяющихся дифференциальных уравнений. Приближение zs к решению ys(x + h) при известных значениях точного решения ys(x) в рамках составного метода вычисляется по схеме т ys(x + h)ttzs= ys(x) + Y, bswksw(h), s = 0,1,., n, (0.0.6) w=1 где функции ksw = ksw(h) вычисляются по схеме m ksw = hfs(x + cjl, Уо(х) + Y, <hvOghg, • • •

9=1 m

• • • , 2/n M + £ Uwngkng)• (0.0.7)

9=1

Идейное наполнение составного метода (0.0.6),(0.0.7) — применение к разным частям СОДУ различных вычислительных схем. Причем в качестве признаков, по которым происходит выделение частей, могут выступать: линейная и нелинейная части (И7"—методы [91]), «жесткая» и «нежесткая» компоненты (разделяющиеся методы).

Теория условий порядка Батчера ориентирована на конструирование методов Рунге-Кутты ОДУ с последующим формальным распространением их на СОДУ. Для разделяющихся дифференциальных уравнений Хайреру потребовалось создание (обобщение теории Батчера) новой теории Р-рядов [90, 129], следствием которой является общая структура условий порядка для методов Фельберга и Нюстрёма.

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

Первый класс — 21(п) (системы разделяющихся ОДУ с перекрестной структурой связей) у'г = Л(*,И0, (008) y'j = fj(x,yj-1), j = 2,.,n, здесь ys,fs — функции размерности rs. Необходимость в интегрировании систем класса 21(2) = 2l(ri), при п = 2 возникает достаточно часто в задачах моделирования механических и физических систем, управления и оптимизации. Например, при анализе динамики частиц в линейном ускорителе представляет большой интерес зависимость энергии частиц от пройденного расстояния. Уравнения, описывающие продольное движение электронов, имеют [49] вид

Здесь £ = z/\ — безразмерное расстояние, Л = 27rc/w — длина волны в свободном пространстве, 7 = Wp/Wo — приведенная энергия, а;(£) — амплитуда напряженности ускоряющей волны, — приведенная фазовая скорость ускоряющей волны.

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

Системы класса 21(п) при п > 3

У2 = /2 (я, </i)

0.0.9)

У\ = /i(z,2/n), y'j = 2/7-1), j = 2,., n, n> 3,

0.0.10) на практике встречаются несколько реже, чем системы (0.0.9). Например, задача классического оптимального линейного быстродействия или дифференциальное уравнение п—го порядка у^ = f{x,y).

Для определенности, явный одношаговый метод типа Рунге-Кутты, ориентированный на интегрирование систем класса 21(п) , будем называть методом класса 21(п).

Следующий, второй класс — 03 (системы структурно разделяющихся оду) y'i = fi(x, 2/1, —, yi-h У1+1, • • •:Уп) , i = 1,. •, (ООН)

У'з = fj(x, 2/i,., Уз-1) , j = I + 1, • • •, n, где ys,fs — функции размерности rs. К системам такого класса приводится плоская ограниченная задача трех тел или задача о крупномасштабных колебаниях ротационно симметричных систем. Например, при рассмотрении крупномасштабных колебаний ротационно симметричных систем [43] задача сводится к интегрированию системы: d2x х df=K~(2x + z)V d2z z dt2~ "(2 x + z)V

0.0.12) dK 1 dx ~dt ~ ~(2x + z)lTt' dL 1 dz dt=~( 2х + г)Ш

Здесь x - безразмерный момент инерции системы относительно оси вращения, z - безразмерный момент инерции относительно экваториальной плоскости, К - кинетическая энергия движений параллельно экваториальной плоскости, L - кинетическая энергия движений в вертикальном направлении. На первый взгляд приведенная система имеет мало общего с выделенным классом. Однако, использование новых переменных 2/1 = У2 = z', Уз = х, г/4 = z, у$ = К, у§ = L позволит привести систему (0.0.12) к виду (0.0.11).

Явный одношаговый метод типа Рунге-Кутты, ориентированный на интегрирование систем класса 03 , будем называть методом класса ЯЗ.

Последний, третий класс — С (системы структурно разделяющихся ОДУ общего вида)

Уо = Мх,у0,у1,.,уп), (0.0.13) y'i = fi(x, Уо,.--, Vi-uVi+h ■•■,Уп), г = 1,., I, (0.0.14) y'j = /j(®,yo,.-.,yj-i), j = / + l,.,n, (0.0.15)

I 6 {0} U N, n<E{0}UiV, I < n, xe[X0,Xk]c R, ys:[XQ,Xk]->Rr°, s = 0,l,.,n, /о: [X0, Xk] x Rr —» iT°, E^o ^ = fi: [X0,Xk] x Rr~^ i = l,.,l, fj: IX0, Xk] x j = I + l,., n, r0 > 0.

Необходимость в интегрировании систем класса С возникает, в частности, в задачах различных систем ускорения и транспортировки пучков заряженных частиц. Например, в задачах оптимизации динамики пучка электронов в ускорителе на бегущей волне [49] движение электронов в волновом группирователе описывается уравнениями вида dz -\Pf(& щ = п = 13«,«), (0.0.16) dn ya(£) sin<p 1 /тга({)(у - V72 - 1/3/(Q) cosy?

Здесь £ = z/X — безразмерное расстояние, Л = 2itс/ш — длина волны в свободном пространстве, 7 = Wp/Wq — приведенная энергия, а(£) — амплитуда напряженности ускоряющей волны, /?/(£) — приведенная фазовая скорость ускоряющей волны, — напряженность фокусирующего магнитного поля.

Изменение порядка следования уравнений в системе (0.0.16) (замена переменных, уо = к, у\ = (р, yi = 7, уз = rj) приводит ее к рассматриваемому виду (0.0.13)—(0.0.15).

Явный одношаговый метод типа Рунге-Кутты, ориентированный на интегрирование систем класса С, будем называть методом класса С.

Причем любой из методов класса С может быть использован для интегрирования систем классов 21(п) и а любой из методов класса 03 — для интегрирования систем класса 21(п).

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

Зависимость эффективности метода от структурных особенностей уже отмечена в практике конструирования одношаговых методов. Так для численного интегрирования дифференциальных уравнений второго порядка у" = f(x,y,y') Нюстрём предложил прямой метод Рунге-Кутты (названный в его честь методом Нюстрёма), ошибочно утверждая, что при одном и том же количестве этапов порядок прямого метода выше порядка метода Рунге-Кутты интегрирования систем первого порядка. Позже Цурмюль распространил прямой метод Рунге-Кутты для уравнений п—го порядка и показал [140], что утверждение Нюстрёма справедливо только в том случае, если правая часть уравнения у^ = f{x,y,. не зависит от производной порядка п — 1. Уравнение п—го порядка, приведенное к системе первого порядка при п = 2, принадлежит классу систем (0.0.9), при п > 2 — классу (0.0.11). Ни в рамках общей схемы явного метода Рунге-Кутты, ни тем более в рамках формального нельзя построить вычислительные схемы численного интегрирования систем первого порядка (0.0.9), (0.0.11) столь же эффективные, как и методы Нюстрёма и Цурмюля.

Дальнейший возможный путь повышения эффективности явных одношаговых методов интегрирования нежестких систем обыкновенных дифференциальных уравнений с учетом барьеров Батчера — это путь конструирования методов для классов систем ОДУ (0.0.9), (0.0.10), (0.0.11), (0.0.13)-(0.0.15) с активным использованием структурных особенностей на алгоритмической стадии метода.

Приведенная выше классификация систем по структурным признакам потребует рассмотрения методов и алгоритмов быстро развивающейся теории комбинаторного программирования [80]. Лишь в последние три десятилетия из совокупности искусственных приемов и разрозненных методов сформировалась система знаний о разработке, реализации и анализе алгоритмов. В отличие от некоторых других разделов математики комбинаторные вычисления [35, 36, 37, 133] не имеют «ядра», т.е. некоторого количества «фундаментальных теорем», составляющих суть предмета, из которых выводится большинство результатов. Один из общих подходов исчерпывающего поиска при ответе на вопрос «перечислить все возможные.» — поиск с возвращением. Непосредственное его применение приводит к алгоритмам, время работы которых недопустимо велико. Хорошо известный вариант поиска с возвращением — метод ветвей и границ — является специальным типом поиска с ограничениями. Он успешно применяется в оптимизационных задачах уже более четырех десятилетий, хотя был известен еще с конца 19-го века. Разнообразные применения этого метода можно найти в [48, 80,134,136].

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

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

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

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

Рунге-Кутты интегрирования дифференциальных уравнений высшего порядка.

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

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

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

- выполнена структурная классификация СОДУ и построены алгоритмы, реализующие разделение дифференциальных уравнений в рамках предложенной классификации;

- предложен подход в построении высокоэффективных явных одно-шаговых методов для каждого класса структурно выраженных СОДУ;

- получены условия порядка предложенных методов интегрирования классов СОДУ и методика использования упрощающих предположений, их исследования;

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

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

Основные результаты диссертации, выносимые на защиту.

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

2. Построены и математически строго обоснованы алгоритмы выделения структурных особенностей нужного типа.

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

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

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

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

Апробация результатов диссертации. Результаты диссертации докладывались и обсуждались на следующих конференциях и семинарах: Механико-математического факультета МГУ (рук. академик РАН Н.С.Бахвалов)-1983 г.; СПбГУ (семинары кафедр теории управления, рук. чл.-корр. РАН Зубов В.И., и информационных систем, рук. д.ф.-м.н., проф. Кирин Н.Е., неоднократно); Всесоюзном семинаре «Вопросы оптимизации вычислений»,в Ин-те кибернетики АН УССР, 1987; на Международной конференции «International Congress on Computer System and Applied Mathematics » St. Petersburg, 1993; на Международной конференции «Interval94»,St. Petersburg, 1994; на 1-й, II-й, III-й Международных конференциях «Beam dynamics and optimization», St. Petersburg, 1994, 1995, 1996; Международная конференция «Еругин-ские чтения-Х», Могилев, 2005; Совещание-семинар «От спутников до галактик», Санкт-Петербург, 2005.

Структура и объем диссертации Диссертация изложена на 300 страницах. Она содержит введение, 7 глав, заключение, список литературы, включающий 152 наименования, 1 приложение, 49 таблиц и 7 рисунков.

ЗАКЛЮЧЕНИЕ

В результате проведенных в диссертации исследований:

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

2. Построены на базе метода ветвей и границ и математически строго обоснованы (теоремы 2.1 - 2.3) алгоритмы выделения структурных особенностей систем рассматриваемых классов.

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

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

5. Исследовано влияние структурных особенностей на характеристики методов рассматриваемого подхода. Доказаны утверждения, позволяющие конструировать явные одношаговые методы интегрирования систем выделенного класса, преодолевающие барьер Батчера: теоремы 1.1 - 1.4, теоремы 3.1 - 3.3, теоремы 4.1, теоремы 5.1.

6. В рамках построенных методов получены высокоэффективные явные расчетные схемы одношагового метода для всех рассмотренных классов: а) для интегрирования систем (1.1,1)—(1.1.3) класса С разделяющихся обыкновенных дифференциальных уравнений общего вида это схемы второго, третьего, четвертого и пятого порядков — (1.3.2), (1.4.26), (1.5.62), таблица 1.4; б) для интегрирования систем (3.1.1) класса 21(г) разделяющихся дифференциальных уравнений с перекрестной структурой связей это схемы с третьего по пятый порядок включительно — (3.2.40), (3.2.60), (3.2.61), табл. 3.6, табл. 3.7, (3.4.67); в) для интегрирования систем (4.1.2) класса 21(п) разделяющихся дифференциальных уравнений построены схемы четвертого порядка двух типов. Первый характеризуется зависимостью коэффициентов от порядка системы (4.2.144), (4.2.145), второй тип расчетных схем не имеет этого недостатка — (4.2.146). г) для интегрирования систем (5.1.1) класса 05 структурно разделяющихся дифференциальных уравнений схема пятого порядка — табл. 5.2.

7. Построены вложенные методы типа Дормана-Принса пятого порядка для интегрирования систем (3.1.1) класса 21(г) разделяющихся обыкновенных дифференциальных уравнений с перекрестной структурой связей и систем (5.1.1) класса 25 структурно разделяющихся обыкновенных дифференциальных уравнений. Их сравнительная теоретическая эффективность подтверждена результатами численного эксперимента.

8. Установлена связь структурного подхода для интегрирования систем разделяющихся обыкновенных дифференциальных уравнений и методов типа Нюстрёма и Цурмюля — прямого интегрирования дифференциальных уравнений n-го порядка.

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

1. Абрамовиц М., Стиган И. Справочник по специальным функциям.-М.:Наука, 1979.

2. Артемьев С. С., Шкурко И. О. Алгоритм переменного порядка и шага основанный на методах типа Розенброка. //Журн. вычисл. математики и мат. физики, т.26, N5, 1986. С. 1256-1258.

3. Арушанян О. Б., Залеткин С. Ф. Пакет прикладных программ решения типовых задач для обыкновенных дифференциальных уравнений //Вопросы конструирования библиотек программ. М.: Изд-во Моск. ун-та, 1985.

4. Арушанян О.В., Залеткин С.Ф. Численное решение обыкновенных дифференциальных уравнений на Фортране./ М.: Изд-во МГУ, 1990, 336 с.

5. Ассюй К.Р. Семистадийные методы Рунге-Кутты порядка шесть// Вестник РУДН. Серия Прикладная и компьютерная математика. Т. 2. №2. 2003. С. 61-76.

6. Бабенко К. И. Основы численного анализа. М.: Наука, 1986.

7. Бабушка И., Витасек Э., Прагер М. Численные процессы решения дифференциальных уравнений. М.: Мир, 1979.

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

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

10. Березин И. С., Жидков Н. П. Методы вычислений. Т. 2. М.: Физ-матгиз, 1962.

11. И. Бордовицына Т. В. Обзор современных способов повышения точности численного интегрирования дифференциальных уравнений движения небесных тел// Астрономия и геодезия, N8, 1980. С .5475.

12. Бордовицына Т. В. Метод Рунге-Кутты высоких порядков и стабилизирующие преобразования в задачах прогнозирования движения ИСЗ//Космич. исследования, т.19,№6, 1981. С. 941-943.

13. Бордовицына Т. В. Современные численные методы задачах небесной механики. М.: Наука. 1984. 136 с.

14. Бордовицына Т. В., Федяев Ю. А. Построение методов Рунге-Кутты высоких порядков на ЭВМ/ Агоритмы небесной механики. Рига:Изд-во Латв.ун-та, 1980. С .36-38.

15. Воеводин В. В. Вычислительные основы линейной алгебры. М.: Наука, 1977.

16. Годунов С. К., Рябенький В. С. Разностные схемы. М.: Наука, 1977.

17. Горбунов А. Д. Разностные уравнения и разностные методы решения задачи Коши для системы обыкновенных дифференциальных уравнений М.: Изд. ВЦ МГУ, 1967.

18. Горбунов А. Д. ,3веркина Т. С., Соколихин В. Н. Два экономичных метода численного интегрирования обыкновенных дифференциальных уравнений, использующих сетку// Журн. вычисл. математики, и мат. физики., 1974. Т. 14, №1. С. 99-112.

19. Деккер К., Вервер Я., Устойчивость методов Рунге-Кутты для жестких нелинейных дифференциальных уравнений. М.: Мир, 1988. 334 с.

20. Дьяченко В. Ф. Основные понятия вычислительной математики. М.: Наука, 1977.

21. Едаменко Н. С., Олемской И. В. Эффективное интегрирование динамической системы специального вида/ Вопросы механики и процессов управления. СПб. 1996. С. 63-66 .

22. Жоголев Е. А. Программа интегрирования систем обыкновенных дифференциальных уравнений 2-го порядка методом Штер-мера//Вычислительные методы и программирование. Вып. I. М.: Изд-во Моск. ун-та, 1962.

23. Заворин А. Н., Хесина И. Я., О некоторых численных методах решения жестких систем обыкновенных дифференциальных уравнений// Журн. вычисл. математики, и мат. физики., Т. 13, №1, 1973. С. 71-79.

24. Залеткин С. Ф. О численном решении задачи Коши для обыкновенных линейных однородных дифференциальных уравнений на больших отрезках интегрирования //Вычислительные методы и программирование. Вып. XXVI. М.: Изд-во Моск. ун-та, 1977.

25. Залеткин С. Ф. Полиалгоритм автоматизированного решения обыкновенных дифференциальных уравнений//Автоматизация конструирования библиотек программ. М.: Изд-во Моск. ун-та, 1979.

26. Залеткин С. Ф. Коллекция дифференциальных уравнений для тестирования вычислительных алгоритмов и программ/Вопросы конструирования библиотек программ. М.: Изд-во Моск. ун-та, 1983.

27. Залеткин С. Ф. Численное решение обыкновенных дифференциальных уравнений многошаговыми методами //Конструирование библиотек программ. М.: Изд-во Моск. ун-та, 1986.

28. Захаров А. Ю. Некоторые результаты сравнения эффективности решения систем обыкновенных дифференциальных уравнений/ Препринт ИПМ АН СССР № 125. М., 1979.

29. Захаров А. Ю., Калиткин Н. Н. Информация о работах по жестким системам дифференциальных уравнений// Дифференц. уравнения, т. 19, № 10. 1983. с.1831-1832.

30. Зверкина Т. С. Модификация конечно-разностных методов для интегрирования обыкновенных дифференциальных уравнений с негладкими решениями.//Журн. вычисл. математики, и мат. физики., т.4,№4, 1964. С. 149-160.

31. Ильин В. П., Кузнецов Ю. И. Алгебраические основы численного анализа. Новосибирск: Наука, 1986.

32. Калиткин Н. Н. Численные методы. М.: Наука, 1978.

33. Карпов И. И., Платонов А. К. Ускорение численного интегрирования уравнений движения в небесной механике//Космические исследования, т.Х,Вып. 6, 1972. С. 811-827.

34. Киселев Ю. М., Орлов М. В. Численные алгоритмы линейных быстродействий //Журн. вычисл. математики и мат. физики, Т. 31, №12, 1991. С. 1763-1771.

35. Кнут Д. Искусство программирования для ЭВМ, т. 1. М.: Мир,1976.

36. Кнут Д. Искусство программирования для ЭВМ, т. 2. М.: Мир,1977.

37. Кнут Д. Искусство программирования для ЭВМ, т. 3. М.: Мир,1978.

38. Коллатц JI. Численные методы решения дифференциальных уравнений. М.: ИЛ, 1953.

39. Крылов В. И., Бобков В. В., Монастырный П. И. Начала теории вычислительных методов. Дифференциальные уравнения.-Минск: Наука и техника. 286 с.

40. Крылов В. И., Бобков В. В., Монастырный П. И. Вычислительные методы. Т. 2. М.: Наука, 1977.

41. Крылов В. И., Бобков В. В., Монастырный П. И. Вычислительные методы высшей математики. Т.2. Под ред. И. П. Мысовских. Минск,"Вышэйш. школа", 1975.

42. Куликов Г. Ю. Об одном способе контроля ошибки для методов Рунге-Кутты//Журн. вычисл. математики, и мат. физики., т.38, №10, 1998. С. 1651-1653.

43. Кутузов С. А., Олемской И. В., Осипков J1. П., Старков В. Н. Математические методы исследования космических систем/ Учебное пособие, СП6ГУ,2003. 203 с.

44. Лоусон Дж. Физика пучков заряженных частиц. Под ред. А. А. Коломенского. М, Мир, 1980.

45. Мак-Кракен Д., Дорн У. Численные методы и программирование на Фортране. М.: Мир, 1977.

46. Милн В. Э. Численное решение дифференциальных уравнений. М.: ИЛ, 1955.

47. Некрасов С. А. Двусторонний метод решения задачи Коши //Журн. вычисл. математики и мат. физики, 1986, Т. 26, №5. С. 771-776.

48. Нильсон Н. Дж. Искусственный интеллект. Методы поиска решений.-М.: Мир, 1973.

49. Овсянников Д. А., Егоров Н. В. Математическое моделирование систем формирования электронных и ионных пучков.- СПб: СПбГУ, 1998. 276 с.

50. Олемской И. В. Об одном методе численного интегрирования систем дифференциальных уравнений, описывающих динамику заряженных частиц в линейном ускорителе// Вопросы атомной науки и техники. Вып. 1(7), серия: техника физического эксперимента. 1981. С. 17.

51. Олемской И. В. О численном методе интегрирования систем обыкновенных дифференциальных уравнений/ Оптимальное управление в механических системах. Л.,1983. С. 178-185.

52. Олемской И. В. Метод численного интегрирования систем обыкновенных дифференциальных специального вида/ (Деп.ВИНИТИ

53. N5942-83) Управление динамическими системами. Л., 1983. С .8994.

54. Олемской И. В. О модификации метода Рунге-Кутты/ Некоторые вопросы качественной теории дифференциальных уравнений и теории управления движением. Саранск,1983. С. 99-104.

55. Олемской И. В. Распространение метода Рунге-Кутты на системы обыкновенных дифференциальных уравнений специального вида/ (Деп.ВИНИТИ N1421-83) Проблемы управления. JI.,1983. С. 12-19.

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

57. Олемской И. В. Модификация метода Рунге-Кутта по структуре систем обыкновенных дифференциальных уравнений: Автореф. дисс. .канд. физ.-матем. наук. Л.: ЛГУ, 1987.

58. Олемской И. В. О структурном методе типа Рунге-Кутта/ IX Все-союз.семинар "Вопросы оптимизации вычислений". Киев: Ин-т кибернетики АН УССР, 1987, С.242.

59. Олемской И. В. Структурный метод интегрирования систем обыкновенных дифференциальных уравнений/ Межд.конф. "International Congress on Computer System and Applied Mathematics".St.Petersburg, 1993. C. 52.

60. Олемской И. В., Рубцова И. Д. Моделирование и оптимизация динамики пучка частиц в группирователе/ Межд.конф. "Beam dynamics and optimization".St.Petersburg, 1994. C. 143-153.

61. Олемской И. В. Численный метод расчета галактических орбит звездных скоплений/Межд.конф. "Beam dynamics and optimization".St.Petersburg, 1996. C.27.

62. Олемской И. В., Симонова Т. A. Error estimation for the modification of the Runge-Kutta method with embedded methods 4(3)/Межд.конф. "Beam dynamics and optimization".St.Petersburg,1996,ISBN 5-7997-0045-7, 1997. P. 214217.

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

64. Олемской И. В. Экономичный метод численного интегрирования систем специального вида/ Процессы управления и устойчи-вость:Труды XXXI научной конференции ПМ-ПУ. СПб: ООП НИИ Химии СПбГУ, 2000. С. 218-220.

65. Олемской И. В. Расчетные схемы третьего порядка точности// Процессы управления и устойчивость-.Труды XXXII научной конференции ПМ-ПУ. СПб, 2001. С. 85-88.

66. Олемской И. В. Структурный подход в задаче конструирования и реализации явных одношаговых методов/Учебное пособие. СПбГУ. 2002. 65 с.

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

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

69. Олемской И. В. Алгоритм выделения структурных особенностей /Николай Ефимович Кирин: Сб. стат. под ред.В.В.Жука, В.Ф.Кузютина, 2003. С. 234-251.

70. Олемской И. В. Методы типа Рунге-Кутты интегрирования систем и дифференциальных уравнений второго порядка специального вида // Вычисл. технологии, 2004. Т.9, №2. С. 67-81.

71. Олемской И. В. Конструирование явных одношаговых методов/ Часть I.Структурный метод: Учебное пособие.- СПбГУ. 2004. 36 с.

72. Олемской И. В. Конструирование явных одношаговых методов/ Часть II.Структурный подход и метод Нюстрёма : Учебное пособие.- СПбГУ. 2004. 36 с.

73. Олемской И. В. Вложенные методы пятого порядка // Вестн. С.-Петерб. ун-та. 2004. Сер. 10, вып. 2. С. 82-93.

74. Олемской И. В, Конструирование явных методов типа Рунге-Кутты интегрирования систем специального вида// Изв. Вуз. Математика. 2005. №2(513). С. 75-80.

75. Олемской И. В. Явный метод типа Рунге-Кутты пятого порядка // Вычисл. технологии, 2005. Т.10, №2. С. 87-105.

76. Олемской И. В. Вложенный пятиэтапный метод пятого порядка типа Дормана-Принса // Журн. вычисл. математики, и мат. физики., 2005. Т. 45, №7. С. 1181-1191.

77. Олемской И. В. Метод пятого порядка типа Рунге-Кутты интегрирования систем структурно разделенных дифференциальных уравнений // Вестн. С.-Петерб. ун-та. 2005. Сер. 10, вып. 1. С. 39-48.

78. Ортега Дж., Пул У. Введение в численные методы решения дифференциальных уравнений. М.: Наука, 1986.

79. Платонов А. К., Власова 3. П., Степанянц В. А. Многоточечный метод интегрирования с переменным шагом для обыкновенных дифференциальных уравнений.- М.: 1976, 18 с. (Препринт/ИПМ:72).

80. Ракитский Ю. В., Устинов С. М., Черноруцкий И. Г. Численные методы решения жестких систем. М.: Наука, 1979.

81. Рейнгольд Е. М., Нивергельд Ю., Део Н. Комбинаторные алгоритмы. Теория и практика.- Пер. с англ. Е.П.Липатова, под ред. В.Б.Алексеева М.: Мир, 1980. 476 с.

82. Самарский А. А. Введение в численные методы. М.: Наука, 1982.

83. Скворцов Л. М. О повышении точности явных методов Рунге-Кутты при решении умеренно жестких задач// Докл. Акад. наук, 2001. Т. 378, М. С. 602-604.

84. Скворцов Л. М. Диагонально неявные FSAL—методы Рунге-Кутты для жестких и дифференциально-алгебраических систем// Мат. модел., 2002. Т. 14, №2. С. 3-17.

85. Современные численные методы решения обыкновенных дифференциальных уравнений. Под ред. Дж. Холла, Дж. Уатта, М.: Мир, 1979.

86. Тихонов А. Н., Горбунов А. Д., Гайсарян С. С. Об особенностях графика полной погрешности приближенного решения задачи Коши для обыкновенного дифференциального уравнения /Вычислительные методы и программирование. Вып. V. М.: Изд-во Моск. ун-та, 1966.

87. Федоренко Р. П. Приближенное решение задач оптимального управления. М.: Наука, 1978.

88. Форсайт Дж., Мол ер К. Численное решение систем линейных алгебраических уравнений. М.: Мир, 1969.

89. Форсайт Дж., Малькольм М., Моулер К. Машинные методы математических вычислений. М.: Мир, 1980.

90. Шевченко Г. В. Численный алгоритм решения линейной задачи оптимального быстродействия //Журн. вычисл. математики и мат. физики, 2002, Т. 42, №8. С. 1166-1178.

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

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

93. Хаммуд Г. М., Хашин С. И. Шестимерное семейство 6-шаговых методов Рунге-Кутты порядка 5//Научные труды ИвГУ. Математика. Вып. 4. - 2001. С. 114-122.

94. Хаммуд Г. М. 3-х мерное семейство 7-шаговых методов Рунге-Кутты порядка б//МГУ, Вычислительные методы и программирование. 2001. Т. 2. С. 159-166.

95. Хашин С. И. Численнон решение уравнений Бутчера// Вестник Ив-ГУ. № 3. 2000. С. 155-164.

96. Хемминг Р. В. Численные методы для научных работников и инженеров. М.: Мир, 1977.

97. Штеттер X. Анализ методов дискретизации для обыкновенных дифференциальных уравнений. М.: Мир, 1978.

98. Яров-Яровой М. С. О применении уточненных методов численного интегрирования в небесной механике/Труды ГАИШ,- М. Мир, 1974, т.45, С. 179-200.

99. R. Aid, Richardson estimator with variable step-size// C. R. Acad. Sci. Paris, 1999. V.329, Serie I, P. 833-837.

100. R. H. Battin, Resolution of Runge-Kutta-Nystrom condition equations through eighth order// AIAA J., V. 14, 1963, P. 1012-1021.

101. D. G. Bettis, A Runge-Kutta-Nystrom algorithm// Celestial Mechanics, 1973. V.8, P. 229-233.

102. P. A. Beentjes, W. J. Gerritsen Higher order Runge-Kutta methods for the numerical solution of second order differential equations without first derivatives/ Report NW 34/76, Math. Centrum, Amsterdam, 1976.

103. R. Bulirsch, J.Stoer Numerical treatment of ordinary differential equations by extrapolation methods// Num. Math., V. 8,1966, P. 113

104. J.C. Butcher, Coefficients for the study of Runge-Kutta integration processes// J. Austral. Math. Soc., 1963. V. 3. P. 185-201.

105. J.C. Butcher, On Runge-Kutta processes of high order // J. Austral. Math. Soc., 1964. V. 4. P. 179-194.

106. J.C. Butcher, Implicit Runge-Kutta process// Math.Сотр., V. 18, 1965. P. 50-64.

107. J.C. Butcher, On the attainable order of Runge-Kutta methods// Math. Сотр. V. 19, 1965. P. 408-417.

108. J.C. Butcher, A modified multistep method for the numerical integration of ordinary differential equations// J. Ass. comput. Mach., 12, 1965. P. 124-135.

109. J.C. Butcher, On the convergence of numerical solutions to ordinary differetial equations// Math. Сотр. V. 20, 1966, P. 1-10.

110. J.C. Butcher, An algebraic theory of integration methods// Math. Сотр., V. 26, 1972, P. 79-106.

111. J.C. Butcher, An order bound for Runge-Kutta methods// SIAM J.Num. Anal, V. 12, 1975, P. 304-315.

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

113. F. Ceschino Evaluation de l'erreur par pas dans les problemes differentiels// Chiffres. V. 5, 1962. P. 223-229.

114. G. Dahlquist, Convergence and stability in the numerical integration of ordinary differential equations // Math. Scand., 1956. V. 4, P. 33-53.

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

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

117. J.R. Dormand, M.E.A. El-Mikkawy, P.J. Prince, Families of Runge-Kutta-Nystrom formulae// IMA J. of Numerical Analysis, 1987. V. 7. P. 235-250.

118. R. England, Error estimates for Runge-Kutta typesolutions to systems of ordinary differential equations// The Computer J., 1969. V. 12. P. 166-170.

119. E. Fehlberg, Lower-order classical Runge-Kutta formulas with step size control and their application to somei heat transfer problems// Computing, V. 6,1970. P. 61-71.

120. Fehlberg E., Classical fifth-,sixth-,seventh-, and eighth order Runge-Kutta formulas with step size control// Computing, V. 4, 1969, P. 93106.

121. Fehlberg E., Klassische Runge-Kutta-Nystrom formeln mit schrittweiten control fur differentialgleichungen x" = f(t,x)// Computing, V. 10, 1972. P. 305-315.

122. S. Filippi, J. Graf, New Runge-Kutta-Nystrom formula-pairs of order 8(7), 9(8), 10(9) and 11(10) for differential equations of the form y" = f(x,y)// J.Comput. and Applied Math., 1986. V. 14, P. 361-370.

123. W.B. Gragg Repeated extrapolation to the limit in the numerical solution of differential equations// SIAM J.Numer.Anal., V. 2, 1965, P. 384-403.

124. E. Hairer, G. Wanner, Multistep-multistage-multiderivative methods for ordinary differential equations// Computing, V. 11, 1973. P. 287303.

125. E. Hairer, G. Wanner On the Butcher group and General multi-value methods// Computing, V. 13, 1974. P. 1-15.

126. E. Hairer, G. Wanner A theory for Nystrom methods// Numer. Math., 1976, V. 25, P. 383-400.

127. E. Hairer Methodes de Nystrom pour 1'equation differentielle y" = !{х,у)ЦNumer. Math., V. 27, 1977. P. 283-300.

128. E. Hairer A Runge-Kutta method of order 10// J. Inst. Maths. Applies, V. 21, 1978. P. 47-59.

129. E. Hairer, Order conditions for numerical methods for partitioned ordinary differential equations// Numer. Math., 1981. V. 36, P. 431445.

130. E. Hairer, A one-step method of order 10 for y" = f(x,y)// IMA J. Numer. Anal., 1982. V 2, P. 83-94.

131. H.M. Hebsacker, Conditions for the coefficients of Runge-Kutta method for systems of n-th order differential equations// J.Comput. Appl., vol. 8, 1982. V 8, P. 3-14.

132. Т. E. Hull, W. H. Enright, В. M. Fellen, A. E. Sedgwick Comparing numerical methods for ordinary differential equations// SIAM J. Numer. Anal., 1972. V 9, P. 603-637.

133. Knuth D. E. Estimating the efficiency of backtrack programs// Math. Сотр., 1975. V. 29, P. 121-136.

134. Knuth D. E., Moore R. W. An analysis of alpha-beta pruning// Artificial Intelligence, V. 6, 1975. P. 293-326.

135. Lapidus L., Seinfeld J. H., Numerical solution of ordinary differential equations/ New York; London: Acad. Press, 1971, 299 p.

136. Lawler E. L., Wood D. E., Branch-and-bound methods: a survey// Operations Research, V. 14, 1966. P. 699-719.

137. Merson R. H., An operational method for study of integration processes/ Proc. Symp. Data Processing, Weapons Research

138. J. Oliver A curiosity of low-order exlicit Runge-Kutta methods//Mathematics of computation, 1975. V. 29, №132, P. 10321036.

139. W. R. Richert, Implicit Runge-Kutta formulae with built-in estimates of the accumulated truncation error//Computing, 1987. V. 39, P. 353362.

140. R. Zurmuhl, Runge-Kutta Verfahren zur numerischen Integration von Differentialgleichungen n-ter Ordnung// ZAMM, 1948. V. 28, P. 173182.

141. A.G. Werschulz Computational complexity of one-step methods for systems of differential equations// Mathematics of computation, V. 34,№ 149,1980. P. 155-174.

142. Gear C. W. Numerical initial value problems in ordinary differential equations/ Englewood Cliffs, N. J.: Prentice-Hall, 1971.

143. Gear C. W. The automatic integration of ordinary differential equations//Communications of the ACM. 1971. V. 14. №3.

144. Henrici P. Discrete-variable methods in ordinary differential equations/ New York : Wiley, 1962.

145. Verner J.H. Explicit Runge-Kutta methods with estimates of the local truncation error// SIAM J. Numer. Anal., 1978, V. 15. P. 772-790.

146. L. F. Shampine, H. A. Watts. A-stable block implicit one-step methods//BIT, 1972. №12, P. 252-266.

147. E. B. Shanks Solutions of differential equations by evaluations of functions//Math. of Сотр., 1966. V. 20. P. 21-38.

148. H. Shintani, Eight-stage block one-step methods with two step-points// Bull. Fac. Sch. Educ. Hiroshima Univ., Part II, 1987. V. 10, P. 63-71.

149. Scraton R. E. Estimation of the truncation error in Runge-Kutta and allied processes//The Computer Journal. 1964. V. 7, №3.

150. Shampine L. F., Gordon M. K. Computer solution of ordinary differential equations. San-Francisco: W. H. Freeman, 1975.

151. H. B. Shanks Solutions of differential equations by evaluations of functions//Math, of Сотр., 1966. V. 20. P. 21-38.

152. H.J. Stetter, Symmetric two-step algorithms for ordinary differential equations, Computing, V. 5, 1970. P. 267-280.

153. J.A. Zonneveld Automatic integration of ordinary differential equations/ Report R743, Mathematisch Centrum, Postbus 4079Д009АВ Amsterdam. Appeared in book form 1964.