На правах рукописи
СТРОГАНОВ АНДРЕЙ ВАЛЕНТИНОВИЧ
МЕТОД РЕШЕНИЯ НЕЛИНЕЙНЫХ
ДИФФЕРЕНЦИАЛЬНЫХ УРАВНЕНИЙ С ПОМОЩЬЮ
ФОРМАЛИЗАЦИИ ОПЕРАЦИЙ КОМПЬЮТЕРА
Специальность 05.13.18 – Математическое моделирование,
численные методы и комплексы программ
АВТОРЕФЕРАТ
диссертации на соискание ученой степени кандидата физико-математических наук
Москва – 2012 2
Работа выполнена на кафедре Высшей математики Федерального государственного бюджетного образовательного учреждения высшего профессионального образования «Московский государственный технический университет радиотехники, электроники и автоматики»
(МГТУ МИРЭА)
Научный руководитель: доктор физико-математических наук, профессор Аристов Владимир Владимирович
Официальные оппоненты: Заведующий кафедрой прикладной математики МГТУ МИРЭА, доктор физико-математических наук, профессор Самохин Александр Борисович Заместитель заведующего отделом математики НИИСИ РАН кандидат физико-математических наук, Коганов Александр Владимирович
Ведущая организация: Механико-математический факультет Московского Государственного Университета им. М. В. Ломоносова.
Защита диссертации состоится « 23 » мая 2012г. в « 1300» на заседании диссертационного совета Д212.131.03 при МГТУ МИРЭА по адресу:
119454 г. Москва, проспект Вернадского, д. 78, ауд. Г-
С диссертацией можно ознакомиться в библиотеке МГТУ МИРЭА.
Отзывы на автореферат в двух экземплярах, заверенные печатью, просим отправлять по адресу: 119454 г. Москва, проспект Вернадского, д. 78, диссертационный совет Д212.131.03.
Автореферат диссертации разослан « 9 » апреля 2012 г.
Ученый секретарь диссертационного совета Д212.131. доктор технических наук, профессор О.А. Тягунов
ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ
Актуальность темы. Многие научные, технические, экономические и другие задачи приводят к необходимости решения дифференциальных уравнений, в том числе и нелинейных, большинство из которых аналитического решения не имеет. Поэтому приходится использовать численные подходы с применением вычислительных устройств (компьютеров). По сравнению с численным, явное решение предоставляет больше информации о задаче, позволяет увидеть решение в целом с его качественными особенностями, асимптотиками и т.д., что важно, например, для физического описания явлений. Также существенно, что аналитические решения, даже частные, могут являться тестами, играющими большую роль при разработке различных численных методов (численный и аналитические подходы дополняют друг друга). В классических численных методах используется вычислительное устройство, определяющее представление решения фактически в виде чисел.
При этом теряется общность, присущая явному представлению решения в аналитической форме. Отметим также вопросы выбора подходящей численной схемы, исследования ее на устойчивость, трудности, связанные с программированием. Поэтому поиск новых методов, которые приводили бы к получению явных аналитических решений является несомненно актуальной задачей.
Для построения решений в явном виде существуют различные методы, однако они не обладают достаточной общностью. Среди численных методов решения задач особое место принадлежит методу конечных разностей ввиду его универсальной применимости. Однако, конечно-разностные методы, представляющие собой рекуррентные формулы, требуют использования компьютеров для вычисления значения искомой функции на каждом слое.
В диссертационной работе предлагается новый метод решения дифференциальных уравнений (основной интерес представляют нелинейные, но он применим и к линейным уравнениям), основанный на математической модели компьютера, в которой формализуются и обобщаются фундаментальные свойства компьютера при работе с числами.
Заметим, что метод нацелен на получение именно аналитического представления решения, которое, в принципе, не требует применения вычислительной машины, то есть идеологически метод «направлен от компьютера к аналитике».
Заметим, что, например, в современном направлении компьютерной алгебры развиваются новые алгоритмы и аналитические методы с применением в вычислительных устройствах.
На основе предложенной модели разрабатывается метод для решения нелинейных дифференциальных уравнений и систем, в котором исключаются вычисления на промежуточных слоях в разностной схеме и тем самым получается явное представление решения, где выражение на последнем слое выражается через начальные условия (в задаче Коши). Для построения решения используется произвольная сходящаяся к решению исходного уравнения разностная схема, которую мы называем «руководящей». Решение ищется в виде отрезков ряда по степеням шага независимой переменной. При построении решения проводится математическая формализация основных операций над числами в компьютере, а именно, ограничения количества разрядов при задании числа и переноса значений из разряда в разряд. Поэтому данный метод может быть назван «методом компьютерной аналогии». В процедуре переноса разрядов также используются операции выделения остатка от деления чисел, старшие разряды фактически являются генераторами псевдослучайных чисел. С использованием вероятностных методов проводится осреднение и исключение промежуточных действий.
Цель работы состоит в создании новой математической модели компьютера и формализации представления чисел в классической вычислительной машине и разработке алгоритма, который в принципе может привести к получению явного вида решения нелинейных дифференциальных уравнений.
Методика исследования основана на общих методах вычислительной математики, математического моделирования, теории вероятностей, математической статистики и анализа. Для сравнения результатов и проверки гипотез производилось численное моделирование на компьютере, использовались язык программирования C++ и программа Gnuplot.
Научная новизна. Предлагаемый подход является принципиально новым. Строится математическая модель работы компьютера с числами, что при использовании разностных схем позволяет получить явное представление решения для нелинейных дифференциальных уравнений и систем дифференциальных уравнений.
Теоретическая и практическая значимость. Работа имеет теоретическое значение при решении дифференциальных уравнений и систем дифференциальных уравнений.
Разработанный метод может применяться в итерационных задачах приближения. Практическая значимость работы заключается в получении аналитических приближений для задач, не разрешимых в квадратурах. Метод может позволить получать тестовые решения, необходимые для отладки новых численных алгоритмов и решения сложных нелинейных уравнений и систем нелинейных уравнений. Представление численного решения в виде отрезка ряда по степеням шага независимой переменной допускает параллельное вычисление коэффициентов, может привести к ускорению вычислений даже в тех случаях, когда явный вид приближения выписать не удается. Явное представление решения также может быть вычислено быстрее и эффективнее по сравнению с традиционными методами.
докладывались на международной конференции «Тихонов и современная математика» в 2006 г.; на 14-й, 16-й, 17-й международной конференции «Математика, компьютер, образование» в Пущино и Дубне в 2007, 2009, 2010 г.;
международной конференции «Infinite and Infinitesimal in Mathematics, Computing and Natural Sciences» (Четраро, Италия, 2010); ежегодных научно-технических конференциях МИРЭА; на семинаре кафедры вычислительных методов ВМК МГУ под руководством профессора, д.ф.-м.н. А.В. Гулина; семинаре сектора информатики и биофизики сложных систем биологического факультета МГУ под руководством профессора, д.ф.-м.н, Г.Ю. Ризниченко; семинаре кафедры прикладной математики МИРЭА под руководством профессора, д.ф.-м.н. А.Б.
Самохина. Методологические аспекты метода обсуждались на конференциях «Философия математики. Актуальные проблемы»
в МГУ им. М.В.Ломоносова в 2007 и 2009 годах; конференции «Искусственный интеллект. Философия, методология, инновации», МИРЭА в 2010 году.
Публикации. Основные результаты диссертации опубликованы в работах [1-12] (из списка ВАК [1-4]), вклад соавторов в работу равный.
Структура и объем диссертации. Диссертация содержит 106 страниц и состоит из введения, пяти глав, заключения и списка литературы. В заключении сформулированы положения, выносимые на защиту.
СОДЕРЖАНИЕ РАБОТЫ
Во введении обсуждаются актуальность и новизна диссертационной работы, представлены общие идеи, на которых строится метод. Определяются задачи исследования и кратко описывается содержание работы по главам.
В главе 1 рассматривается задача Коши для дифференциального уравнения первого порядка в виде с начальным условием y t0 y0, где f t, y - некоторая, в общем случае, нелинейная функция двух переменных. Параметр t для краткости назовем «временем». Будем считать, что для данной задачи Коши выполняются требования, обеспечивающие существование и единственность на отрезке t0, T ее решения Уравнение (1) удается решить традиционными методами точно лишь для некоторых специальных типов функций f t, y.
Рассмотрим явную разностную схему задачи (1) в виде:
где - шаг по времени, а G t, y - некоторая функция, зависящая как от функции в правой части (1), так и от параметров t и y.
Будем считать, что вычисления проводятся с расчетным шагом b t0 / N, расчетными точками (узлами) служат точки tn t0 n, n 0,1,..., N промежутка t0, b. Фактически (2) определяет разностную схему, решение которой предполагается сходящимся к решению (1).
В простейшем случае точное решение можно получить непосредственно из разностного за счет последовательного раскрытия рекуррентной зависимости в (2) и предельного перехода при 0.
В качестве модели, иллюстрирующей основные этапы данного метода решения, рассматривается простая нелинейная задача Коши, на примере которой изучаются основные стороны алгоритма. Для этой задачи показывается, что решение в виде отрезка степенного ряда, где коэффициенты при степенях ничем не ограничены, не будет обеспечивать сходимость к точному решению.
В главе 2 вводится понятие «позиционной -системы счисления», в которой в качестве основания выбирается обратная величина к шагу разностной схемы (2), то есть 1.
Предполагается, что выбран так, что 0 1.
Сформулирована и доказана теорема.
Пусть для задачи Коши выбрана некоторая разностная схема вида (2) и допустим, что шаг выбран достаточно малым чтобы схема (2), аппроксимирующая задачу (3), была устойчивой. Если значение y0 может быть представлено в виде полинома степени p по степеням с действительными коэффициентами, тогда yn также может быть представлено в виде полинома степени p и некоторого остаточного члена.
В соответствии с этой теоремой будем выражать численное решение дифференциального уравнение с помощью -системы счисления, то есть в виде отрезка ряда по степеням с положительными коэффициентами am и определенным набором знаков между слагаемыми:
где i – коэффициенты, определяющие знаки перед коэффициентами, то есть m 1,1.
Для получения представления решения на n 1-м слое функция G yn раскладывается в ряд в окрестности y* 0 a0,n :
Здесь каждое k -е слагаемое содержит полином относительно степени pk. Следовательно выражение G yn может быть перегруппировано и записано в виде ряда по степеням. Представление решения по схеме (2) для автономного ОДУ на ( n 1)-м слое будет иметь вид:
где В общем случае нельзя обеспечить сходимость к решению, если на каждом слое удерживать фиксированное количество членов в (4). Без дополнительных условий представление решения в виде отрезка ряда по степеням с p (n) const приводит к расходящемуся ряду. Если коэффициенты ai,n при степенях в (4) превысят 1/, то приближение станет неэффективным, так как с ростом n придется вводить дополнительные слагаемые в (4) с более высокими степенями.
Введем процедуру переноса разрядов, которая будет гарантировать, что величины коэффициентов ai,n на каждом слое будут меньше 1/. Так, если коэффициент становится равным или большим величины 1/, его часть должна быть перенесена в младший коэффициент (то есть в коэффициент с меньшим индексом). Если абсолютное значение коэффициента меньше величины 1/, то коэффициент называется нормализованным, иначе – ненормализованным и отмечается волной (например:
ai,n ). Если на ( n 1)-м слое выписано нормализованное представление решения в виде (4), то, используя (5), и обрывая полученное выражение после p-го слагаемого, получается ненормализованное представление решения на n -м слое:
Выражения для нормализации коэффициентов будут иметь вид (квадратные скобки обозначают взятие целой части числа):
где значения ненормализованных коэффициентов находятся из предыдущего слоя с помощью формулы (6). Таким образом, процедура нормализации позволяет гарантировать, что при переходе от n -го шага к ( n 1)-му коэффициенты не превысят величину 1/ 1, а, следовательно, представление решения (4) будет отрезком сходящегося ряда.
Учитывая операцию переноса разрядов, выражение (4) можно записать следующим образом:
Локальное представление решения (на данном слое) и глобальное (на n слоях) в предлагаемом методе могут различаться количеством членов p представления решения, о чем говорит доказанная в диссертации теорема:
Пусть в качестве руководящей разностной схемы выбрана схема с точностью O r, и решение на данном шаге представляется в виде отрезка ряда (4). Тогда после применения операции переноса разрядов, в (4) достаточно удерживать члены до r включительно, то есть:
В (4) необходимо удерживать такое количество членов p, чтобы ошибка, вносимая при отбрасывании в (5) членов со степенями, превосходящими p, была порядка ошибки разностного решения (2), следовательно, представление (4) будет сходиться к решению задачи (1) с точностью выбранной разностной схемы.
Доказана следующая теорема:
Пусть решение на n-ом шаге представлено в виде (4). Для получения представления на (n+1) – ом шаге используется выражение (5), которое может быть перегруппировано по степеням. Затем члены со степенями, превосходящими p отбрасываются. Обозначим их сумму как s p1,n1. Тогда справедливо следующее неравенство:
В главе 3 описываются стохастические свойства старших разрядов решений в методе компьютерной аналогии.
Использование этих свойств позволяет избавляться от рекуррентной зависимости на промежуточных шагах по времени.
Выражение для коэффициентов представления решения (6) в общем виде соответствуют выражению для конгруэнтного генератора псевдослучайных чисел, который дается следующей рекуррентной формулой:
где a и c — некоторые целочисленные коэффициенты, причем коэффициентов a в (6) как отдельные линейные конгруэнтные генераторы, связанные между собой через операции переноса разрядов.
Такая зависимость приводит к сильно запутанному состоянию, что, однако, не гарантирует улучшение свойств генератора случайных чисел. С другой стороны, в зависимости от функции G в правой части (2), такой генератор может менять свои свойства с ростом n.
Можно рассматривать величины переноса разрядов m, 0 m r как случайные. Они определяются стохастическими свойствами коэффициентов ar 1, …, a p, где r – порядок точности разностного метода (2). На отрезках, где коэффициенты с номерами 0 m r не меняются, можно заменить m своим математическим ожиданием, обозначим его как M m. Тем самым будут исключены все промежуточные слои, на которых коэффициенты a0, a1, …, ar не меняют свои значения.
Рассматривается численное моделирование стохастического поведения коэффициентов и проверяется справедливость предположения о случайном распределении величин старших коэффициентов. Важнейшим критерием в изучаемом случае является приближенное совпадение математического ожидания и дисперсии с идеальными теоретическими аналогами, что подтверждается численными экспериментами.
Формулируется и проверяется в численных экспериментах следующее утверждение.
Если величины переноса разрядов 2 слабо коррелируют на последовательных слоях, то выполняется закон больших чисел:
В последнем неравенстве подразумевается сходимость в обычном смысле, поскольку принимается, что старшие разряды ведут себя как квазислучайные числа с равномерным заполнением соответствующей плоскости изменения, что подтверждают компьютерные эксперименты. Поэтому суммирование величин переноса заменяются суммированием соответствующих математических ожиданий. Фактически речь может идти о методе обратном к методу Монте-Карло: сумма реализаций случайной величины заменяется теоретически определяемым математическим ожиданием. Для простоты записи используем обозначение a a1. Удобно искать представление решения обратной зависимости, т.е. n a, которая ставит в соответствие некоторому значению оси ординат a значение на оси абсцисс (рассматривается система координат n, a ). Задаем приращение a 1, ему будет соответствовать приращение na na 1 na. Так как коэффициент линеаризации a1 постоянен на отрезке [na, na 1 ), вероятность переноса 2,n также постоянна во всех точках этого отрезка и равна P a.
При стремлении шага по времени к нулю статистические свойства алгоритма улучшаются, и можно ожидать, что данная аппроксимация обеспечивает сходимость к точному решению.
В главе 4 вначале приводятся основные этапы алгоритма решения задачи методом компьютерной аналогии.
1. С помощью выбранной сходящейся разностной схемы записывается представление в виде отрезка ряда по степеням шага аргумента.
2. Перенос разрядов: требуем, чтобы коэффициенты этого отрезка ряда были меньше 1/ ; если оказывается, что это не так, то берется целая часть произведения коэффициента на и прибавляется к младшему коэффициенту, а на прежнем месте остается остаток от деления коэффициента на 1/.
3. Выбор необходимого количества членов отрезка ряда.
4. Определение вероятности переноса разряда в коэффициент при r, где r - порядок выбранной разностной схемы.
5. Нахождение зависимости номера шага n от значения коэффициента линеаризации; используя закон больших чисел при уменьшении, определяем обратную зависимость для решения исходной задачи, восстанавливается и прямая зависимость на интервалах монотонности искомой функции.
6. Предельный переход к решению исходной задачи осуществляется при уменьшении шага.
дифференциальных уравнений методом компьютерной аналогии.
Решение получается в виде обратной зависимости t y.
Пример 1. Построение решения модельной задачи:
Представление решения в виде (4):
Полученное решение:
дифференциальных уравнений (система Карлемана):
Представление решения в виде (4):
Полученное решение:
В главе 5 приведены примеры построения решения методом компьютерной аналогии для задач, неразрешимых в квадратурах или не имеющих решения в элементарных функциях. Для задач из примеров 3 и 5 были проведены тесты с целью оценить производительность вычислений, которые показывают, что решение, полученное методом компьютерной аналогии, находится быстрее, чем решение, полученное по руководящей разностной схеме.
Пример 3. Решение задачи Коши, неразрешимой в элементарных функциях:
Представление решения в виде (4):
Получено решение в следующем явном виде:
Приводится сравнение, демонстрирующее близость полученного решения к разностному решению (рис. 1), здесь 0.01.
Рис. 1. Сравнение решений (верхний график) и оценка времени вычислений по двум алгоритмам (нижний график).
Пример 4. Решение задачи Коши для уравнения Риккати:
Рассматривается область, где y 0, тогда решение можно представить в виде отрезка ряда (4) с p 2 :
Полученное решение (на отрезке [0,1]):
Пример 5. Решение системы дифференциальных уравнений, не имеющей аналитического решения Представление решения в виде (4):
В качестве независимой переменной здесь будем использовать a, тогда n (номер слоя по времени) и b должны быть выражены через a:
Показано, что решение методом компьютерной аналогии может быть вычислено на компьютере быстрее, чем прямое вычисление с использованием разностного решения (см. рис. 2).
Далее показывается, что из анализа детерминированных коэффициентов (то есть в данной схеме – для коэффициентов a и b1 ) возможно получить простую асимптотику решения для начальных моментов времени:
Рис. 2. Сравнение решений (верхний график) и оценка времени вычисления по двум алгоритмам (нижний график).
ПОЛОЖЕНИЯ, ВЫНОСИМЫЕ НА ЗАЩИТУ
1. Построена модель вычислительного устройства, в которой формализуются важные свойства компьютера при работе с числами (компьютерная аналогия). С помощью этой модели можно исключать промежуточные слои в разностных схемах для решения дифференциальных уравнений.2. Разработан новый алгоритм, который может привести к явному виду решения нелинейных дифференциальных уравнений и систем. Выявлены вероятностные свойства старших коэффициентов в представлении решения в виде отрезка ряда по степеням шага аргумента, что дает возможность получать решение в явном виде.
3. Применение нового метода может быть сопряжено с достаточно большой аналитической работой. Но алгоритм обладает рядом достоинств, в частности – он может быть более быстрым по сравнению с традиционными численными методами, возможно эффективное распараллеливание, выявление качественных свойств решения, получение простых асимптотик.
4. Решение по предложенному алгоритму является приближением точного решения. Точное решение получается в предельном переходе при устремлении шага по времени к нулю.
Приведены многочисленные примеры построения решений для задач, не разрешимых в квадратурах или элементарных функциях. При этом показано, что при уменьшении шага по времени решения сходятся к предельному с ожидаемой точностью.
ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ
1. Аристов В.В. Строганов А.В. Построение решений дифференциальных уравнений с помощью метода «компьютерной аналогии» // Доклады академии наук РАН, том. 434, N2, 2010, с. 151-157.2. Аристов В.В. Строганов А.В. Вероятностные аспекты метода «компьютерной аналогии» для решения дифференциальных уравнений // Компьютерные исследования и моделирование, 2009, Т. 1, N 1, с. 21-31.
3. Аристов В.В. Строганов А.В. Перспективы метода решения дифференциальных уравнений на основе компьютерной аналогии // Прикладная информатика, 2008, 6(18), с. 91-99.
4. Aristov V.V., Stroganov A.V. A method of formalizing computer operations for solving nonlinear differential equations // Applied Mathematics and Computation, 2012, Vol. 218, p.8083-8098. doi:10.1016/ j.amc.2011.09.029.
дифференциальных уравнений на основе «компьютерной аналогии» // Тезисы докладов международной конференции «Тихонов и современная математика». М.: МГУ. 2006 г. — с26-27.
6. Аристов В.В. Строганов А.В. Новый метод решения дифференциальных уравнений с формализацией математических операций компьютера // Cб. научн. трудов. «Математика. Компьютер. Образование».
Ред. Г.Ю.Ризниченко. М.-Ижевск: НИЦ Регулярная и хаотич. динамика.
2006. т.2. с.295-307.
7. Аристов В.В. Строганов А.В. Полуаналитический подход для решения дифференциальных уравнений // 54-я Научно-техническая конференция МИРЭА: Сб.тр. — М.: МИРЭА, 2005. — Ч.2. — Физикоматематические науки. — с.35-40.
8. Аристов В.В. Строганов А.В. Развитие метода решения дифференциальных уравнений на основе «компьютерной аналогии» // 55-я Научно-техническая конференция МИРЭА: Сб. тр. — М.: МИРЭА, 2006.
— Ч.2. — Физико-математические науки. — с.92-95.
9. Аристов В.В. Строганов А.В. Решение дифференциальных уравнений на основе метода компьютерной аналогии // 56-я Научнотехническая конференция МИРЭА: Сб. тр. — М.: МИРЭА, 2007. — Ч.2. — Физико-математические науки. — с.51-56.
10. Аристов В.В., Строганов А.В. Развитие метода «компьютерной аналогии» для решения дифференциальных уравнений. «Математика.
Компьютер. Образование». Ред. Г.Ю. Ризниченко. М.-Ижевск: НИЦ Регулярная и хаотич. динамика. 2008. вып.12, т.2. с.110-120.
11. Аристов В.В., Строганов А.В. Развитие метода решения дифференциальных уравнений с формализацией математических операций компьютера // Cб. научн. трудов. «Математика. Компьютер. Образование».
Ред. Г.Ю. Ризниченко. М.-Ижевск: НИЦ Регулярная и хаотич. динамика.
2010. т.2. с.227-235.
12. Aristov V.V., Stroganov A.V. Method of formalizing computer operations for solving nonlinear differential equations // Intern. Conf. Infinite and Infinitesimal in Mathematics, Computing and Natural Sciences. Book of Abstracts. Cetraro. 2010, p.16.