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

Введение. . .1

Глава 1. Некоторые квадратурные формулы, использующие значения производной подынтегральной Функции. . . . . . . . 8

1.1. Введение. . .8

1.2. Задача нахождения оетатеа квадратуры. . . . , . . . . . 11

1.3. Оценка ширины остатка. . . . . . . . . . .16

1.3.1. Класс функций с ограниченной производной.16

1.3.2. Класс функций, интервальные расширения которых удовлетворяют интервальному условию Липшица.17

1.4. Квадратура с коэффициентами, зависящими от параметра.

Ее ядро Пеано.18

1.5. Минимизация ширины локализатора остатка квадратуры. . 22

1.5.1. Случай одного интервала зналеоиостоянства. . . . . 23

1.5.2. Случай двух интервалов знакопостоянства. . 25

1.5.3. Нахождение минимума ширины локализатора остатка при р=3 и двух интервалах знакопостоянства. , . 9

1.5.4. Случай р=2. . . 33

1.6. Вывод. . .

Глава 2. Методы интегрирования ОДУ в одномерной случае. . . . . 47

2.1.Постановка задачи. Предварительная локализациярешения. . 47

2.2. Использование квадратурных формул для интегрирования ОДУ.51

2.3. Алгоритм с использованием производной на левом конце. . . 52

2.4. Алгоритм с использованием производной на правом конце. . 59

2.5. Алгоритм с использованием производной на обоих концах. .65

2.6. Метод наивысшего порядка точности. . . . . . . . . 71

2.7. Сравнение методов. . . 77

2.8. О раздельном получении границ локализатора решения ОДУ.

Глава 3. Программный комплекс для интегрирования ОДУ. . 5

3.1. Введение. Выбор модельных задач. . . . 85

3. 2. Общая компоновка программной системы.86

3.3. Файлы модельных задач и методов интегрирования. . . . . . 9

3.4. Функция предварительной локализации решения. . . . . . . 91

3.5. Головной модуль, реализующий совмещенное получение верхней и нижней границ решения. . , . , . . . . 92

3.6. Головной модуль, реализующий раздельное получение верхней и нижней границ решения. . . . 97

3.7. Заголовочные файлы INTEGR.H и МШЕ1. . Н . .103

3.8. Файл описания дисплея и принтера С.INI. . . . . . . . . .104

3.9. Файл управления компиляцией программного комплекса {MAKEFILE).105

3.10.Файлы методов интегрирования. .107

3.11.Файлы модельных задач. . . . . .112

Глава 4. Результаты численной проверки методов.116

4.1. Модельная задача 1. . . . . . . .116

4.1.1. Расчет с совмещенным получением границ решения.117

4.1.1.1. Первый метод. . . . . . . . . . .117

4.1.1.2. Второй метод. . . i . . . . . » .118

4.1.1.3. Третий метод. . . . . . . . . . . . . . 120

4.1.1.4. Четвертый метод. . .122

4.1.1.5. Метод Тейлора 5-го порядка точности. . . . . . .123

4.1.1.6. Метод Тейлора 6-го порядка точности. . .125

4.1.2. Расчет с раздельным получением границ решения.127

4.1.2.1. Первый метод. .127

4.1.2.2. Второй метод. . . . . . . . . . . . . . 128

4.1.2.3. Третий метод. . . ^ . , . v . .130

4.1.2.4. Четвертый метод. . . . . . . . . . . . . . . .132

4.1.2.5. Метод Тейлора 5-го порядка точноети.133

4.1.2.6. Метод Тейлора 6-го порядка Точности.135

4.2. Модельная задача 2. .137

4.2.1. Расчет с совмещенным получением границ решения.137

4.2.1.1. Первый метод. . . . .137

4.2.1.2. Второй метод. .139

4.2.1.3. Третий метод, . . .140

4.2.1.4. Четвертый метод. . .142

4.2.1.5. Метод Тейлора 5-го порядка точности.144

4.2.1.6. Метод Тейлора 6-го порядка точности.145

4.2.2. Расчет с раздельным получением границ решения.147

4.2.2.1. Первый метод» .147

4.2.2.2. Второй метод. . . . . . . . . .149

4.2.2.3. Третий метод. . . . .150

4.2.2.4. Четвертый метод. . . .152

4.2.2.5. Метод Тейлора 5-го порядка точности. . . . . . . . .154

4.2.2.6. Метод Тейлора 6-го порядка точности.155

4.3. Модельная задача 3. .157

4.3.1. Расчет с совмещенным получением границ решения.158

4.3.1.1. Первый метод. . . .158

4.3.1.2. Второй метод. . . .159

4.3.1.3. Третий метод. * . .161

4.3.1.4. Четвертый метод. .163

4.3.1.5. Метод Тейлора 5-го порядка точности.164

4.3.1.6. Метод Тейлора 6-го порядка точности.166

4.3.2. Расчет с раздельным получением границ решения.168

4.3.2.1. Первый метод. . .168

4.3.2.2. Второй метод. . . . . .169

4.3.2*3. Третий метод. . . . . . . . . .171

4.3.2.4. Четвертый метод. . . . . . . . . . . . . . . . . . .173

4.3.2.5. Метод Тейлора 5-го порядка точности. . . .174

4 .3.2. 6. Метод Тейлора 6-го порядка точности. .176

4.4. Выводы по результатам расчетов. .178

Глава 5. Интегрирование систем ОДУ. . . . . .182

5.1. Постановка задачи. Предварительная локализация решения. .182

5.2. Построение процесса интегрирования ОДУ. . . .183

5.3. Оценка ширины получаемых локализаторов. . . . . . . . . .187

5.4. Ирограммный комплекс для интегрирования систем ОДУ. . . .189

5.5. Головной модуль XMAIN.С. .193

5.6. Модуль предварительной локализации решения. .195

5.7. Заголовочный файл XINT.H. .196

5.8. Файлы методов интегрирования. . .197

5.9. Файл модельной задачи. . . . . . . . . .199

5.10.Результаты расчетов. .202

5.10.1. Неявный метод 6-го порядка. . .202

5.10.2. Метод Тейлора 6-го порядка. . v . . . . . . . . . .203

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

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

Как научное направление интервальные вычисления сложились в 1960-е годы. Первой монографией по интервальному анализу была вышедшая в 1966 году книга Р. Е. Мура CR.Е.МоогеЭ под названием "Интервальный анализ" С "Interval Analysis":). Однако и до него в данном направлении велись работы, например польским математиком М. Вармусом СМ. WarmusD в первой половине 1950-х годов. Еще раньше, в 1927 году, принципы интервальных вычислений были изложены в работе Брадиса, хотя и под другим названием - "Метод границ".

Существенно большая по сравнению с обычным расчетом сложность интервального расчета и недоступность ЭВМ помешали развитию этих работ и применению интервальных винислений на практике в те времена. Сам термин "интервальный" был предложен Сунагой [34].

В настоящее время интервальный анализ достаточно интенсивно развивается. Выпущены [6,7,8,9] и продолжают издаваться книги как по фундаментальным вопросам интервального анализа, так и по его применению для решения конкретных задач. Выпускается специальный журнал, посвященный интервальным вычислениям - "Reliable Computing" С"Надежные вычисления"D.

Суть интервальной математики состоит в том, что вместо конкретных вещественных чисел Скоторые вообще могут быть непредставимы с помощью машинных чисел, как например число п или число еЭ операции проводятся над заключающими их интервалами С отрезками!), определенными двумя машинными числами, являющимися ЬерхнеИ и. нижн&И зрамиисипи. Далее, каждой функции fCx>, отображающей множество вещественных чисел R в себя, сопоставляется ее интервальное расширение FCXD - отображение множества интервалов в себя. Если из X£Y следует FCX3SFCYD, то такое отображение F называется /монотонным по Ьключ&них» СМПВЭ. Понятие монотонности по включению является одним из базовых в интервальной математике.

Существует несколько вариантов определения интервального расширения. Первый вариант был предложен Муром в 1966г. [S3. В нем от FCXD требуется выполнение двух условий: fCX} 2 FCXD, где fCXD = С ГСхЗ : х е X > С13

С это условие называется осноЬньш Ьключ.ени.елй и. fCxD = FCx5 = FC Ex,хЗ Э. С8Э

Второе определение дано Шокиным в С63, в нем требуется выполнение только условия CID. В третьем варианте определения Е73 требуется выполнение только условия С2Э, из которого, если отображение F монотонно по включению, следует выполнение условия CID.

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

Третий вариант определения неприменим к немонотонным по включению интервальным процессам. Поэтому далее, как и в [1,2,3,43 используется второй вариант определения интервального расширения, то есть для FCXD имеется единственное условие CID. При этом выполнены две следующие теоремы С 3 3.

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

Теорема 2. Если отображения монотонны по включению, то их композиция будет также монотонна по включению.

Ни.нима.льньш ЬещестЬеннъш расширение/» непрерывной функции f называется отображение FCXD множества интервалов в себя:

FCXD = С inf fCx5, sup fСхЭ 3. xeX х«=Х

Рассмотрим некоторую функцию f: R-+R. Рассмотрим множество интервалов М, границами которых являются машинные числа.

Отображение F этого множества в себя, для которого выполнено условие fCXD 2 FCXD, где fCXD = < fCxD : х <= X >, называется машинным интербальньш расширением функции f.

Шириной. инт&рЬала называется величина wC [х, х] D = |х - х|. Пусть S - множество машинных чисел определенного формата. Неограбленным округлением 66ерос вещественного числа х называется операция

ТСхЗ = min у . y«=S, у>х

Напра&леннъш округлением Ьниз вещественного числа х называется операция

4-Сх> = max у . y«=S, у<х

Отображение F множества М в себя

FCX5 = С 4-С inf fCX> Э, tC sup fCx> ) ] x<=X xeX называется минимальным машинным интербальным расширением. Здесь под минимальностью имеется в виду то, что из всех машинных интервальных расширений функции f данное интервальное расширение дает отрезки наименьшей возможной ширины. К сожалению, получение именно минимальных машинных расширений затруднено для ряда функций таких, как многие элементарные функции.

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

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

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

Основная задача, которой посвящена данная работа, это задача численного интервального С локализующего!) интегрирования обыкновенных дифференциальных уравнений первого порядка. Рассматриваются неявные итерационные одношаговые методы, использующие значения производных от решения в силу дифференциального уравнения. Подобный способ численного интегрирования С в неинтервальном виде!) имеется в работах Милна СЮ] и Хемминга С123: у' = ГСх,уЭ

Ь - - ь2 - - ь5

У+1 = У + - У' + У' + — -уп+1 + Уп + - у<5>с$э. п+1 Г. 2 ^ п+1 П J 12 I п У 720

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

Как уже упоминалось выше, интервализация классических методов вычислений представляет собой самостоятельную достаточно сложную задачу. В рассматриваемой области имеется работа Меньшикова Г. Г. С4], в которой на основе квадратурной формулы трапеций получен неявный метод интервального численного интегрирования ОДУ первого порядка, имеющий четвертый порядок точности и использующий кроме значения функции значение третьей производной от решения в силу ОДУ у' = ГСх.у):

Ь ь3

У,1+1 = У + - с РСх, + РСх, ,У,Ь ) } - — Ф СХ, ,ДУ, к к к к к+1 к+1 . 3 к к

2 12 где X, =Сх, >х, 3, Y, - локализатор решения ОДУ при х = х . ДУ, к к к+± к к к локализатор решения ОДУ на отрезке F - интервальное расширение функции fCx,y), - интервальное расширение третьей производной от решения ОДУ в силу уравнения.

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

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

Хотя основная часть работы посвящена рассмотрению одномерных ОДУ вида y'=fCx,y5, также рассмотрено обобщение полученных методов для систем уравнений размерностью 2 и более, а также приведен пример интегрирования системы размерности 2.

3 л к а ю ч е н и е

В данной работе получены одношаговые неявные С итерационные!) методы интервального С лок ализующего!) численного интегрирования обыкновенных дифференциальных уравнений 1-го порядка и произведена теоретическая оценка достигаемого порядка точности. Проведены также проверочные расчеты на ряде модельных задач, предназначенных для обнаружения особенностей поведения рассматриваемых методов, а также сравнение результатов, полученных данными методами, с известными методами интегрирования по Тейлору аналогичного порядка точности. Результаты проверки показывают, что наиболее подходящим для практического применения является метод 4 С6-го порядка точности с использованием значений производных на обоих концах интервала> и способ расчета с раздельным получением верхней и нижней границ лок ализатора решения. По сравнению с методом интегрирования по Тейлору того же 6-го порядка точности данный метод требует вычисления производной на единицу меньшего порядка.

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

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

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

1. Меньшиков Г.Г. Интервальный анализ и методы вычислений: Конспект лекций. Выпуск 3. Интервализация приближенных формул. Численное суммирование рядов. СПб, 19 96.

2. Меньшиков Г.Г. Интервальный анализ и методы вычислений: Конспект лекций. Выпуск 6. Локализующее вычисление интегралов. СПб, 1998.

3. Меньшиков Г.Г. Интервальный анализ и методы вычислений: Конспект лекций. Выпуск 1. Введение в интервальную организацию вычислений. СПб, 1996.

4. Меньшиков Г.Г. Интервальный анализ и методы вычислений: Конспект лекций. Выпуск 9. Элементы локализующего интегрирования дифференциальных уравнений. СПб,1938.

5. R.E.Moore. Interval Analysis. Englewood Cliffs, N.J.:1. Prentice-Hal 1, 1966.

6. Ю.И.Шокин. Интервальный анализ. Новосибирск: Наука, 1981.

7. Калмыков С.А. и др. Методы интервального анализа. Новосибирск, 1986.

8. Алефельд Г., Херцбергер Ю. Введение в интервальные вычисления/ Пер. с англ. под ред. Ю.В.Матияс<эвича. М. , 1987.

9. R.E.Moore. Methods and Applications of Interval Analysis. 1979.

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

11. В.И.Крылов, Л.Т.Шульгина. Справочная« книга по численному интегрированию. М., Наука, 1966.

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

13. B.C.Добронец, В.В.Шайдуров. Двусторонние численные методы. Новосибирск: Наука. Сиб. отделение. 1990.

14. Р.Клатте и др. PASCAL-XSC. Руководство по языку и учебный курс. М.: ТЕРЕВИНФ, 1997.

15. H.Bauch u.a. Intervallmathematikv Theorie und Anwendungen. Leipzig: Teubner, 1987.

16. A.Neumaier. Interval methods for systems of equations. -Cambridge, and oth.: Cambridge University Press, 1990.

17. R. Baker Kearfott. Rigorous Global Search: Continuous Problems. Dordrecht: Кluwer Academic Press, 1996.

18. R. Hammer, and oth. Numerical Toolbox for Verified Computing. I. Basic Numerical Problems. Theory, Aigorithms, and Pascal-XSC-Programs. •«- Ber l in, and oth.: Springer, 1993.

19. Unicalc решатель математических задач. Руководство пользователя. Версия 2.1. - М. - Новосибирск: Российский НИИ искусственного интеллекта, 1995.

20. К.L.E.Nickel. Using ■interval Methods for the Numerical Solutions of ODE's. Zeitschrift f r Angewandte Mathematik und Mechanik, v.66, 1986, No.*»-, pp. 514-523.

21. G.F.Corliss. Where Is Validated ODE Solving Going? Numerical Methods and Error Bounds. Proceedings of the IMACS-GAMM Int. Symp. on Numerical Methods and Error Bounds held in Oldenburg, Germany, July 9-12, 1995. pp. 48-57.

22. R.Rihm. Problems in Enclosing Solutions of ODEs. Numerical Methods and Error Bounds. Proceedings of the IMACS-GAMM Int. Symp. on Numerical Methods and Error Bounds held in Oldenburg, Germany, July 9-12, 1995. pp. 297-302.

23. Меньшиков Г.Г. Предварительная локализация интегральных кривых обыкновенных дифференциальных уравнений на основе тождества Коши-Дюамеля. Дифференциальные уравнения и прикладные задачи. Тула: Тульский гос. университет, 1999. с.126-131.

24. R.Lohner. EinschliеВ und der Losung gewohnlicher Anfangs- und Randwertaufgaben und Anwendungen. Dissertation. Karlsruhe: Uni ver s i tat, 1988.

25. С.М.Никольский. Квадратурные формулы. М. : Наука, 1988.

26. С.Л.Романов. О быстрой сходимости процесса предварительной локализации решения ОДУ. СПб, 1998, депонировано в ВИНИТИ 3866—В98 от 25.12.98г.

27. Г.Корн, Т.Корн. Справочник по математике для научных работников и инженеров. М., 1977г.

28. Г.Г.Меньшиков. Предварительная локализация интегральных кривых на основе тождества Коши-Диамеля.2 9. Э.Камке. Справочник по обыкновенным дифференциальнымуравнениям. М. , 1971.

29. Нестеров В.М. Вычисление интервальных расширений функций с использованием обобщенных интервальных арифметик, В кн.: Международная конференция по интервальным и стохастическим методам науки и теэшики. М. , 1992. с.119-120.

30. Нестеров В.М. Интервальные арифметики и оценка множества значений Функции. В кн.: Р.Н.Йсунов (ред.). Теоретические основы и прикладные задачи интеллектуальных информационных технологий. СПб, 1998.

31. Нестеров В.М. Автоматическое символьное решение уравнений. Кандидатская диссертация (к.ф.-м.н.). 31ИИАН, 1988. 144с.

32. Nesterov V.M. Interval and Twin Arithmetics. Reliable Computing. 3(4) (1997), p.369-380.

33. Theory of an interval algebra and its applications to numerical analysis. RAAG Mamoirs, 1958, v.2, p.547-564.