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

• Шиндин, Сергей Константинович
• кандидат физико-математических наук
• 2002

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

Введение

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

1.1. Многошаговые методы решения обыкновенных дифференциальных уравнении.;.

1.1.1. Многошаговые методы с постоянным шагом интегрирования

1.1.2. Многошаговые методы с переменным шагом интегрирования

1.1.3. Представление Нордсика для многошаговых методов

1.2.- Адаптивные численные методы на основе оценки локальной ошибки

1.2.1. Способы оценки локальной ошибки.

1.2.2. Процедура выбора размера шага интегрирования.

1.3. Способы оценки глобальной ошибки и проблемы построения адаптивных методов на основе оценки глобальной ошибки.

1.3.1. Глобальная ошибка численных методов и смежные вопросы

1.3.2. Методы оценки глобальной ошибки.

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

1.4. Резюме

2. Оценка и контроль глобальной погрешности многошаговых методов с постоянным шагом интегрирования

2.1. Вычисление оценок локальной и глобальной ошибок на равномерной сетке.

2.1.1. Построение оценок локальной и глобальной ошибок.

2.1.2. Вычисление старшей производной численного решения

2.1.3. Обоснование метода оценки главного члена локальной ошибки

2.1.4. Обоснование метода оценки глобальной ошибки

2.2. Вычисление оценок локальной и глобальной ошибок на неравномерной сетке.

2.2.1. Многошаговые методы с постоянным шагом интегрирования на неравномерной сетке.

2.2.2. Обоснование метода оценки главного члена локальной ошибки

2.2.3. Обоснование метода оценки глобальной ошибки

2.3. Управление точностью численного решения и вычислительные эксперименты

2.3.1. Комбинированное локально-глобальное управление размером шага интегрирования.

2.3.2. Неявные методы.

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

2.4. Резюме.

3. Оценка и контроль глобальной погрешности многошаговых методов с переменным шагом интегрирования

3.1. Вычисление оценок локальной и глобальной ошибок

3.1.1. Построение оценок локальной и глобальной ошибок

3.1.2. Вычисление старшей производной численного решения.

3.1.3. Обоснование метода оценки главного члена локальной ошибки

3.1.4. Обоснование метода оценки глобальной ошибки

3.2. Управление точностью численного решения и вычислительные эксперименты

3.2.1. Комбинированное локально-глобальное управление размером шага интегрирования.

3.2.2. Неявные методы.

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

3.3. Резюме.

4. Оценка и контроль глобальной погрешности методов Нордсика

4.1. Вычисление оценок локальной и глобальной ошибок на равномерной сетке.

4.1.1. Построение оценок локальной и глобальной ошибок

4.1.2. Вычисление старшей производной численного решения

4.1.3. Обоснование метода оценки главного члена локальной ошибки

4.1.4. Обоснование метода оценки глобальной ошибки

4.2. Вычисление оценок локальной и глобальной ошибок на неравномерной сетке.

4.2.1. Методы Нордсика на неравномерной сетке

4.2.2. Обоснование метода оценки главного члена локальной ошибки

4.2.3. Обоснование метода оценки глобальной ошибки

4.3. Управление точностью численного решения и вычислительные эксперименты

4.3.1. Комбинированное локально-глобальное управление размером шага интегрирования.

4.3.2. Неявные методы.

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

4.4. Резюме.

А. Библиотека программ

А.1. Классы и функции для работы с матрицами.

А.1.1. Заголовочный файл matrix .h.

А.1.2. Шаблон класса matrix.

А.1.3. Шаблон класса imatrix

А.1.4. Создание объектов шаблона класса matrix.

А. 1.5. Операторы присваивания.

А.1.6. Операторы индексации.

А.1.7. Операторы сдвига.

А.1.8. Операции конкатенации

А.1.9. Служебные функции-члены.

А. 1.10.Элементарные функции для работы с матрицами.

А.1.11.Операторы сравнения.

А.1.12. Арифметические операторы.

А.1.13. Основные математические функции

А.1.14. Функции и операции для решения систем линейных уравнений

А.1.15. Логические операторы и функции.

А.2. Функции и структуры для численного решения обыкновенных дифференциальных уравнений.,.

А.2.1. Заголовочный файл numerics .h.

А.2.2. Структура odestruct.

А.2.3. Структура solveropt.

А.2.4. Структура statistics

А.2.5. Заголовочный файл bdf. h.

А.2.6. Заголовочный файл adams. h.

А.2.7. Пример использования функций библиотеки.

Введение диссертации (часть автореферата) на тему «Автоматическое управление точностью численного решения обыкновенных дифференциальных уравнений линейными многошаговыми методами»

Математическое моделирование, как инструмент научного исследования, появилось в 40х — 50х годах XX столетия. Становление нового метода было, в первую очередь, связано с исследованиями в ядерной и космической областях. Однако первые математические модели появились задолго до середины XX века (например, модель хищник-жертва Лотки-Вольтерра, описывающая динамику популяций [16]). Но несмотря на это, в определенном смысле можно сказать, что математическое моделирование продукт холодной войны и гонки вооружений. В настоящее время аппарат математического моделирования с успехом применяется в таких областях фундаментальной и прикладной науки как физика, химия, экономика, социология, геология, экология и т.д. Более того, ни одно серьезное управленческое или техническое решение не обходится без достаточного математического обоснования.

Причина успеха метода математического моделирования заключается в его гибкости и универсальности. Процесс математического моделирования можно условно разделить на два больших этапа. На первом этапе строится математическая модель исследуемого явления. Как правило, модель и объект не тождественны друг другу вследствие несущественности части факторов для качественного исследования предмета и неполноты наших знаний о нем. Модель отражает лишь некоторые частные характеристики объекта. Явления, изучаемые различными областями науки, часто приводят к сходным математическим моделям. Так, например, многие реальные объекты в физике, механике, химии, биологии и т.д. адекватно описываются дифференциальными уравнениями [16, 50, 88, 89].

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

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

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

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

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

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

В настоящее время в области вычислительной математики достигнут существенный прогресс. Проблемам вычислительной математики целиком посвящены такие фундаментальные работы как [1, 9, 14, 15, 36, 37, 42, 45, 48, 50, 52, 57, 65, 88, 89, 97, 112]. Особенно впечатляющие результаты получены в области численного решения задачи Коши для систем обыкновенных дифференциальных уравнений (ОДУ) [1,3, 4, 5, 6, 9, 43, 45, 50, 57, 64, 65, 68, 69, 70, 71,80, 81, 83, 84, 85, 87, 88, 89, 91, 92, 97, 124].

Устойчивый интерес к решению систем ОДУ связан в первую очередь с огромным количеством прикладных задач, описываемых подобными системами. Уже имеются в наличии высокоэффективные численные многошаговые и одношаговые методы для решения ОДУ [13, 43, 45, 50, 57, 60, 61, 63, 65, 66, 69, 82, 83, 84, 88, 89, 92, 97, 116, 118, 124, 127], построена стройная математическая теория таких методов, развиты подходы, обобщающие указанные два класса численных методов [43, 50, 82, 88, 89]. Кроме того, исследованы также такие фундаментальные свойства численных методов как аппроксимация, устойчивость и сходимость [3, 4, 50, 57, 65, 68, 70, 71, 80, 81, 85, 88, 89, 91, 92, 97, 117]. Разработаны и детально исследованы численные методы для решения ОДУ, обладающие специальными свойствами, например, неявные методы для решения "жестких" задач

45, 60, 69, 71, 89, 92].

Помимо, классической математической теории численных методов для ОДУ огромное количество работ посвящено их практической реализации. Один из основных механизмов, обеспечивающих эффективность численного решения, заключается в выборе в том или ином смысле оптимальной сетки. Понятно, что варьируя размер шага интегрирования можно существенно экономить ресурсы вычислительной системы, что чрезвычайно важно для реальных приложений. В связи с чем большое распространение в наше время получили методы с автоматическим выбором размера шага. В таких методах процесс построения оптимальной сетки идет параллельно с решением исходной задачи [1, 40, 43, 50, 67, 72, 73, 77, 78, 79, 86, 88, 89, 93, 94, 95, 96, 98, 115, 128,129].

Следует иметь в виду, что в отличие от одношаговых построение многошаговых методов с автоматическим выбором шага интегрирования наталкивается на дополнительные трудности, для преодоление которых разработаны три основных подхода к реализации методов с переменным шагом интегрирования. Во-первых, применяют многошаговые формулы для равномерной сетки и при изменении шага используют интерполяцию численного решения. Во-вторых, применяют многошаговые формулы с переменными коэффициентами. И, наконец, используют представление Нордсика для многошаговых методов. Кроме того, серьезное ограничение на изменение шага накладывает нуль-устойчивость многошаговых методов [50, 68, 80, 81, 85, 88].

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

• нахождение приближенного решения в очередной точке сетки;

• вычисление некоторой характеристики ошибки в этой точке сетки;

• определение оптимального размера для шага интегрирования.

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

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

За последние 30 лет появилось довольно большое количество работ, посвященных данной тематике [8, 26, 30, 31, 33, 34, 35, 41, 53, 54, 58, 67, 72, 75, 76, 99,102, 104,106, 107,108,109,113, 114,115,121, 122, 123, 125, 126, 130] (подробный обзор литературы по вопросу оценивания глобальной ошибки будет дан в следующей главе). Однако несмотря на разнообразие предлагаемых методов, их математическое обоснование опирается на гипотезу о существовании специального вида асимптотического разложения глобальной ошибки. Вопрос же о корректном управлении размером шага интегрирования для получения численного решения с заданной точностью практически не исследован. Можно перечислить лишь небольшое число работ, так или иначе затрагивающих данную тематику [30, 35, 53, 72, 102,104, 106,107, 108,109, 113, 123].

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

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

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

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

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

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

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

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

ОДУ с любой разумной наперед заданной точностью. Теоретические результаты главы подтверждены экспериментальными данными.

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

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

В параграфе 2.3 предложена новая процедура управления размером шага интегрирования для многошаговых методов с интерполяцией численного решения. В отличие от стандартного локального подхода этот алгоритм контроля точности численного решения основан на вычислении как локальной, так и глобальной ошибок многошагового метода, что позволяет нам (в отсутствии ошибок округления) решать задачу Коши для системы ОДУ с любой разумной наперед заданной точностью. Опираясь на работы [23, 101], выведены оценки достаточного количества итераций для метода простой итерации, а также метода Ньютона (полного и модифицированного), обеспечивающие корректное использование локально-глобального алгоритма управления точностью численного решения в случае неявных методов. Результаты вычислительных экспериментов, приведенные в заключительной части параграфа показывают, что в отличие от стандартного локального контроля точности новый способ действительно позволяет контролировать реальную ошибку многошагового метода.

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

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

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

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

В параграфе 3.2 предложена модификация комбинированного локально-глобального алгоритма управления точностью численного решения для многошаговых методов с переменными коэффициентами, позволяющая (в отсутствии ошибок округления) решать задачу Коши для системы ОДУ с любой разумной наперед заданной точностью. Опираясь на работы [23, 101], здесь также обоснованы оценки достаточного количества итераций для метода простой итерации, а также метода Ньютона (полного и модифицированного), обеспечивающие корректное использование этого алгоритма в случае неявных методов. Результаты вычислительных экспериментов, приведенные в конце параграфа показывают, что в отличие от стандартного локального контроля точности новый алгоритм действительно позволяет контролировать реальную ошибку многошагового метода.

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

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

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

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

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

В параграфе 4.3 предложена версия комбинированного локально-глобального алгоритма управления точностью численного решения, рассчитанная на сильно устойчивые методы Нордсика и позволяющая (в отсутствии ошибок округления) решать задачу Коши для системы ОДУ с любой разумной наперед заданной точностью. Опираясь на работы [23, 101], выведены оценки достаточного количества итераций для метода простой итерации, а также метода Ньютона (полного и модифицированного), обеспечивающие корректное использование этого алгоритма в случае неявных методов. Результаты вычислительных экспериментов, приведенные в заключительной части параграфа показывают, что в отличие от стандартного локального контроля точности новый алгоритм действительно позволяет контролировать реальную ошибку метода Нордсика.

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

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

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

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

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

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

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

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

3) Способы оценки и контроля локальной и глобальной ошибок сильно устойчивых методов Нордсика для систем обыкновенных дифференциальных уравнений.

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

Основные результаты диссертации доложены: на VII-VIII научно-практических конференциях студентов и аспирантов Ульяновского государственного университета (Ульяновск, 1998-1999), на seventh international colloquium on numerical analysis and computer science with applications (Plovdiv, Bulgaria, 1998), на third european conference on numerical mathematics and advanced applications (ENUMATH-99) (Juvaskyla, Finland, 1999), на четвертой международной научно-технической конференции "Математическое моделирование физических, экономических, технических, социальных систем и процессов" (Ульяновск, 2001), на XXIV конференции молодых ученых механико-математического факультета МГУ им. М.В. Ломоносова (Москва, 2002), на международной конференции по вычислительной математике (МКВМ-2002) (Новосибирск, 2002), на научно-исследовательских семинарах Вычислительного центра РАН, механико-математического факультета МГУ им. М.В. Ломоносова и механико-математического факультета УлГУ.

По теме диссертации опубликовано 14 работ, в том числе [26, 31, 33, 34, 35, 53, 54, 55, 56, 104, 106, 107, 109, 111]. При этом результаты из работ, подготовленных в соавторстве, либо использованы частично, в соответствии с личным вкладом каждого автора ([33, 34, 106, 109, 111]), либо приведены в переработанном виде ([26, 31, 35, 104, 107]).

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

Кроме того, необходимо отметить, что исследования в рамках диссертационной работы были бы невозможны без финансовой поддержки со стороны: научной программы "Университеты России — фундаментальные исследования" (проект № 230, 1998-1999), Российского фонда фундаментальных исследований (проект № 98-01-00006, 1998-2000; проект № 01-01-00006, 2001-н.вр.).

Заключение диссертации по теме «Математическое моделирование, численные методы и комплексы программ», Шиндин, Сергей Константинович

чис;юниого м е т о д а . В разделе 4.2.3 м ы показали , ч т о к о н т р о л и р о в а т ь глобальную ошибку м е т о д а Н о р д с и к а м ы м о ж е м только в т о м случае, если его порядок не м е н ь ш е т р е х . Д е й с т в и т е л ь н о , в э т о м разделе м ы п ы т а л и с ь использовать к а к Н Ф Д Н - м е т о д ы , т а к и Н Н А - м е т о д ы в т о р о г о п о р я д к а с локально-глобальным к о н т р о л е м т о ч н о с т и для р е ш е н и я и первой, и в т о р о й т е с т о в о й з а д а ч и . Однако в о всех случаях м ы т е р пели неудачу . К о м п ь ю т е р н ы е п р о г р а м м ы , к о т о р ы е р а б о т а л и для м е т о д о в п о р я д к а т р и и в ы ш е , в э т о м случае з а к а н ч и в а л и свою р а б о т у аварийно, ч т о п о д т в е р ж д а е т а к т у а л ь н о с т ь э т о г о ограничения .4.4. Резюме Основной з а д а ч е й данной г л а в ы было п о с т р о е н и е п р о ц е д у р ы а в т о м а т и ч е с к о г о кон троля т о ч н о с т и численного р е ш е н и я систем обыкновенных д и ф ф е р е н ц и а л ь н ы х урав нений в и д а (1.1) м е т о д а м и Нордсика .С э т о й целью в п а р а г р а ф е 4.1 были предложены и обоснованы э ф ф е к т и в н ы е способы для вычисления главных членов локальной и глобальной ошибок м е т о д о в Н о р д с и к а (1.6) н а равномерной с е т к е . З а т е м в п а р а г р а ф е 4.2 э т и способы были обобщены н а случай неравномерной с е т к и и н т е г р и р о в а н и я . Наконец , в п а р а г р а ф е

4.3 было р а з р а б о т а н о комбинированное локально-глобальное управление р а з м е р о м ш а г а численного и н т е г р и р о в а н и я и обосновано е г о к о р р е к т н о с т ь д л я неявных ме тодов (1.6). В ы ч и с л и т е л ь н ы е э к с п е р и м е н т ы , приведенные в разделе 4.3.3, полностью подтвердили к а к работоспособность нового а л г о р и т м а управления р а з м е р о м ш а г а и н т е г р и р о в а н и я , т а к и его п р е и м у щ е с т в о перед с т а н д а р т н ы м л о к а л ь н ы м к о н т р о л е м т о ч н о с т и численного решения .

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

1. арушанян О.Б., ЗаЛЕТКИН С.Ф. Численное решение обыкновенных дифференциальных уравнений на Фортране. М.: Изд-во МГУ, 1990.

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

3. БАХВАЛОВ Н.С. К оценке ошибки при численном интегрировании дифференциальных уравнений экстраполяционным методом Адамса// ДАН СССР. 1955. Т. 104. № 5. С. 683-686.

4. БАХВАЛОВ Н.С. Некоторые замечания к вопросу о численном интегрировании дифференциальных уравнений методом конечных разностей// ДАН СССР. 1955. Т. 104. № 6. С. 805-808.

5. БАХВАЛОВ Н.С. Численные методы: Учебное пособие. М.: Наука, 1975.

6. Бахвалов Н.С., Жидков Н.П., Кобельков Г.М. Численные методы: Учебное пособие. М.: Наука, 1987.7. беллман Р. Введение в теорию матриц. М.: Наука, 1969.

7. БерезанскиЙ JI.M., Идельс Л.В. Метод Чаплыгина численного решения дифференциальных уравнений с запаздывающим аргументом// Ж. вычисл. матем. матем. физ. 1990. Т. 30. № 6. С. 945-951.

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

9. Булычев Ю.Г., БурлаЙ И.В., Погонышев С.А. Численно-аналитический метод дифференцирования функций с ограниченным спектром на основе формулы Котельникова// Ж. вычисл. матем. матем. физ. 1992. Т. 32. № 3. С. 396407.

10. БУЛЫЧЕВ Ю.Г. Математический аппарат iV-кратного дифференцирования функций с финитным спектром и его приложения// Ж. вычисл. матем. матем. физ. 1994. Т. 34. № 5. С. 643-657.

11. БУЛЫЧЕВ Ю.Г., БурлаЙ И.В. Дифференцирование функций с финитным спектром на неравномерной сетке интерполяции// Ж. вычисл. матем. матем. физ. 1996. Т. 36. № 5. С. 159-160.

12. Воеводин В.В, Кузнецов Ю.А. Матрицы и вычисления. М.: Наука, 1984.16. вольтерра в. Математическая теория борьбы за существование. М.: Наука, 1976.

13. Гантмахер Ф.Р. Теория матриц. 4-е изд. М.: Наука, 1988.

14. ИБРАГИМОВ В.Р. Об одной связи между порядком и степенью для устойчивой формулы с забеганием вперед// Ж. вычисл. матем. матем. физ. 1990. Т. 30. № 7. С. 1045-1056.

15. Канторович JI.B, Акилов Г.П. Функциональный анализ. М.: Наука, 1977.20. корн г., Корн т. Справочник по математике для научных работников и инжененров. Определения, теоремы, формулы. М.: Наука, 1974.

16. Кочетков К.А., Широков П.Д. L-затухающие ДОИ^-методы третьего порядка точности// Ж. вычисл. матем. матем. физ. 1997. Т. 37. № 6. С. 699-710.

17. Куликов Г.Ю., Шиндин С.К. Об одном способе управления глобальной ошибкой многошаговых методов// Жур. вычисл. матем. матем. физ. 2000. Т. 40. № 9. С. 1308-1329.

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

19. МАРЧУК Г.И. Методы вычислительной математики: Учебное пособие. М.: Наука. Гл. ред. физ.-мат. лит., 1989.

20. МАРЧУК Г.И. Математические методы в иммунологии. Вычислительные методы и эксперименты. 3-е изд. М.: Наука. Гл. ред. физ,- мат. лит., 1991.

21. НЕКРАСОВ С.А. О построении двухсторонних приближений к решению задачи Коши// Жур. вычисл. матем. матем. физ. 1988. Т. 28. № 5. С. 660-668.

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

23. DaHLQUIST G. A special stability problem for linear multistep methods// BIT. 1963. V. 3. P. 27-43.

24. DaHLQUIST G. On the control of the global error in stiff initial value problems. Lecture Notes in Math. V. 912, Springer, Berlin-New York, 1982, P. 38-49.

25. DeUFLHARD P. Order and stepsize control in extrapolation methods// Numer. Math. 1983. V. 41. P. 399-422.74. deuflhard p. Recent progress in extrapolation methods for ordinary differential equations// SIAM Review. 1985. V. 27. P. 505-535.

26. ENRIGHT W.H. Analysis of error control strategies for continuous Runge-Kutta methods// SIAM J. Numer. Analys. 1989. Y. 26. № 3. P. 588-599.

27. Gear C.W., Tu K.W. The effects of variable mesh size on the stability of multi-step methods// SIAM J. Numer. Analys. 1974. V. 11. P. 1025-1043.

28. Gear C.W., Watanabe D.S. Stability and convergence of variable order multi-step methods// SIAM J. Numer. Analys. 1974. V. 11. P. 1044-1058.

29. Gear C.W., Walls D.E. Multiratelinear multistep methods// BIT. 1984. V. 24. P. 484-502.

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

31. Gragg W.B. On extrapolation algorithms for ordinary initial value problems// SIAM J. Numer. Anal. 1965. V. 2, Ser. B. P. 384-403.85. grigorieff R.D. Stability of multistep methods on variable grids// Numer. Math. 1983. V. 42. P. 359-377.

32. Gustavson K., Lundh M., sodelrind G. A PI stepsize control for the numerical solution of ordinary differential equations// BIT. 1988. V. 28. P. 270-287.

33. HAIRER E. Backward error analysis for multistep methods// Numer. Math. 1999. V. 84. P. 199-232.92. hairer E., Wanner G. Order stars and stiff integrators// J. Comput. Appl. Math. 2000. У. 125. P. 93-105.

34. Hall G. Equilibrium states of Runge-Kutta schemes// ACM Trans. Math. Software. 1985. V. 11. P. 289-301.94. hall G. Equilibrium states of Runge-Kutta schemes, part II// ACM Trans. Math. Software. 1986. V. 12. P. 183-192.

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

36. BEDEV V.I. An introduction to functional analysis and computational mathematics. Basel-Boston-Berlin: Birkhauser, 1997.

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

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

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

40. WANNER G. Runge-Kutta- met hods with expansion in even powers of h// Computing. 1973. V. 11. P. 81-85.

41. WlLLE D.R. New stepsize estimators for linear multistep methods. Numerical Analysis Report № 247, University of Manchester/UMIST, Manchester Centre for Computational Mathematics, Manchester, 1994.

42. WlLLE D.R. Experiment in stepsize control for Adams linear multistep methods. Numerical Analysis Report № 253, University of Manchester/UMIST, Manchester Centre for Computational Mathematics, Manchester, 1994.

43. ZaDUNAISKY P.E. On the estimation of errors propagated in the numerical integration of ordinary differential equations// Numer. Math. 1976. V. 27. P. 21-39.