ПРОГРАММИРОВАНИЕ, 2011, No 2, с. 9-19
КОМПЬЮТЕРНАЯ АЛГЕБРА -
УДК 681.3.06
ПАРАМЕТРИЧЕСКИЕ РЕШЕНИЯ НЕДООПРЕДЕЛЕННЫХ ЛИНЕЙНЫХ ОБЫКНОВЕННЫХ ДИФФЕРЕНЦИАЛЬНЫХ
УРАВНЕНИЙ
© 2011 г. Т. Вольф Department of Mathematics, Brock University 500 Glenridge Avenue, St.Catharines, Ontario, Canada L2S 3A1 E-mail: twolf@brocku.ca Поступила в редакцию 14.10.2010 г.
Данная статья преследует две цели. Во-первых, возможно непосредственно прикладное использование полученного нами алгоритма для получения параметрического решения недоопределенных линейных обыкновенных дифференциальных уравнений с коэффициентами, являющимися произвольными аналитическими функциями одной переменной. Второй важной целью служит построение алгоритма, в определенном смысле двойственного к фундаментальному алгоритму Евклида и, как следствие, альтернативного алгоритму построения дифференциального базиса Гребнера в данном специальном случае. В статье сравниваются алгоритм Евклида и его <дуальная> версия, анализируется их вычислительная мощность на примере решения недоопределенных линейных обыкновенных дифференциальных уравнений. Реализация описанного в статье алгоритма доступна в интерактивном режиме по ссылке [7].
1. ВВЕДЕНИЕ
Недоопределенные линейные обыкновенные дифференциальные уравнения (ОДУ) и аналогичные уравнения с частными производными (УЧП) часто возникают в теории оптимального управления. Недоопределенные уравнения зачастую появляются также в процессе решения определенных или переопределенных систем уравнений (в которых число уравнений изначально больше числа неизвестных функций). Примерами могут служить системы, задающие условия на точечные симметрии (и симметрии Ли-Беклунда) или законы сохранения линеаризуемых дифференциальных уравнений. Получаемые при этом переопределенные системы часто имеют решения, содержащие произвольные функции одной или нескольких переменных. Это показывает, что в процессе решения таких систем встречаются недоопределенные системы.
Известны некоторые алгоритмы для решения
недоопределенных линейных уравнений и систем таких уравнений (ОДУ, УЧП, многомерные дискретные системы и т.п., см. [1],[2],[3]). Существуют также эффективные программные пакеты (Д.Робертц и др., [4], [5]). Цель данной статьи — описание альтернативного алгоритма, по нашему мнению, элегантного, эффективного и в некотором смысле дополнительного к фундаментальному алгоритму Евклида, который служит концептуальной базой для алгоритмов Гребнера, использующегося в других реализациях, упомянутых выше. Вопрос, может ли наш алгоритм быть обобщен на случай УЧП и тем самым послужить альтернативой не только для некоммутативного алгоритма нахождения дифференциальных базисов Гребнера при решении ОДУ, но также и для решения УЧП, остается открытым.
Программная реализация описанного в данной статье алгоритма доступна по ссылке [7] и является частью пакета Crack ([8]) решения переопределенных систем. Как описано далее, новой чертой этих пакетов являются
флаги, позволяющие предотвратить появление знаменателей, а также сократить число членов в получаемом решении. Это достигается включением дополнительных множителей, зависящих от ж, в новые функции, вводимые в процессе вычисления.
Рассмотрим линейное ОДУ
г
0 = 5] А/г + Ооо(ж), Г> 1, (1.1)
А = а.(ж)
.7=0
^7
~т I , Щ > 0,
аж
на функции /!,...,/ независимого переменного ж. Уравнение может быть однородным (а00 = 0) или неоднородным (а00 = 0). Под условием, что данное уравнение является недоопределенным, мы понимаем лишь тот факт, что оно включает по крайней мере две функции /¿, т.е. г > 1. Дифференциальный порядок каждой / обозначим за щ. Для простоты мы предполагаем, что все коэффициенты а. дифференцируемы достаточное для работы алгоритма число раз (по крайней мере ^I щ раз). Верхний индекс в круглых скобках обозначает порядок производной, т.е.
= /1'4 > производные низких порядков также
,2 £
обозначаются апострофами, например = /'.
Задача состоит в нахождении общего решения ОДУ (1.1) в форме явных дифференциальных выражений /
/ = ^¿(ж,Ь1(ж),...,Ьг-1(ж)), i = 1,...,г, (1.2)
через параметрические функции
^1(ж),..., Нг-1(ж), которые либо все произвольны, либо одно из них, например, Н^ж), должно удовлетворять линейному ОДУ, в то время как все остальные Н. (ж) произвольны. Например, общее решение ОДУ
0 = /''ж2 + д''ж - д'ж2 + / + 3ж
на / = /(ж), д = д(ж) может быть записано в форме / = ж((ж5 — ж3 + 3ж)Н'' — (ж6 + ж4 + 3ж2 — 6)Н' + (зж5 + 3ж3 + 17ж)Н — 3ж8 + 3ж6 — 16ж4 + 9ж2)/(ж8 — 2ж6 + 7ж4 — 6ж2 + 9), д = ж( (—2ж6 + 2ж4 — 6ж2)Н'' + (8ж5 — 4ж3)Н' — (14ж4 + 14ж2 + 6)Н + 4ж7 + ж5 + 3ж3 — 27ж) /(2(ж8 — 2ж6 + 7ж4 — 6ж2 + 9)), где Н = Н(ж) — произвольная функция. Эта запись решения не единственно
г(п).
возможная. Поскольку Н(ж) произвольна, заменяя Н на линейное дифференциальное выражение от одной или нескольких новых произвольных функций, мы получим также общее решение, но это решение будет более высокого дифференциального порядка и с большим количеством произвольных функций, не являясь, однако, более общим. Естественно стремиться получить решение с наименьшим возможным числом произвольных функций и наименьшим порядком производных от них. Но даже это требование не обеспечивает однозначности решения. Разумно потребовать, например, достигнуть наименьшего порядка наивысшей производной у каждой произвольной функции либо наименьшей суммы порядков этих производных по всем произвольным функциям.
Более того, встречающиеся в ответе произвольные функции могут быть умножены на некоторые фиксированные переменные множители для модификации ответа, к примеру, для уничтожения знаменателей. Заменяя в приведенном выше примере Н(ж) на (ж8 — 2ж6 + 7ж4 — 6ж2 + 9)3р(ж) с произвольной функцией р(ж), получим полиномиальное выражение, но большего размера, т.е. с большим числом слагаемых в коэффициентах при параметрической функции в правой части.
В слудующем разделе мы описываем алгоритм и обсуждаем его характеристики. В разделах и алгоритм приводится полностью, вместе с алгоритмом Евклида. Оба даются в векторных обозначениях с целью их детального сравнения в разделе (5). Мы показываем их существенное отличие, а также дополнительность по отношению друг к другу, в том смысле, что возможно дать критерий, при каких обстоятельствах один из них лучше другого. Другой возможностью может служить комбинация обоих алгоритмов в гибридной версии.
Наконец, в разделе описано приложение алгоритма к одной задаче, возникающей при классификации гиперболических эволюционных уравнений.
2. АЛГОРИТМ
2.1. Схема алгоритма
По существу алгоритм состоит из:
• разделения заданного ОДУ на полную производную и алгебраический остаток,
п
• введения новой функции /г+1, такой, что часть ОДУ с полной производной равна d/r+i/dx, и, тем самым, представления данного ОДУ как системы двух уравнений: одного, определяющего /г+1, и второго, переформулирующего ОДУ в терминах
fr+1,
• использования таким образом записанного ОДУ для исключения одной из исходных функций и получения тем самым снова одного ОДУ на то же самое число неизвестных функций, которое в некотором смысле более близко к чисто алгебраическому разрешению, чем предыдущее.
Эти шаги повторяются до тех пор, пока ОДУ либо будет включать только одну функцию и, тем самым, перестанет быть недоопределенным, либо пока одна из входящих в нее функций не станет входить чисто алгебраически и тем самым ОДУ сможет быть разрешено по отношению к этой функции. Ниже приведем более детальное описание в виде псевдокода.
2.2. Псевдокод
Входные данные:
• список функций /1,..., /г от X,
• линейное ОДУ 0 = ш относительно /¿ вида (1.1)
Тело алгоритма
L := {} % L будет списком подстановок s := r
while (ОДУ 0 = ш содержит по крайней мере две /¿) and
(порядки производных n¿ > 0 V/¿) do • Выделять dx из ш пока возможно, вводя новую функцию /s+1(x) и вычисляя выражения b¿:
s
0 = ш = /s+1 + Е /jbi + fleo, (2.1)
í=1
где /s+1,bi заданы как
s ra¿-1 j
/s+1 = E Е/^-1-)Е (-i)(j+k)a(j-k)(2.2) i=1 j=0 fc=0
if bi = 0 для всех i then ОДУ 0 = ш есть полная производная (кроме члена а00), т.е. переходим к рассмотрению нового ОДУ 0 = ш := fs+i + / аоо dx, где fs+1 есть лишь сокращенное обозначение, определенное в (2.2) else
о рассматривать fs+1 как новую
неизвестную функцию, о решить (2.1) относительно одной fj из fi,.., /8, для которой:
— коэффициент bi в (2.1) ненулевой и
— она имеет наименьший порядок в ш и тем самым в (2.2):
Л- = - j I /s+1 + Е ^ + aoo I ;
(2.4)
í=j
bi = Е(-1)(гаг+к)а(:ПЙ)-
(2.3)
fc=0
о использовать (2.4) для подстановки / в (2.2) и получения нового ОДУ
0 = ш := —fs+i + £S=i En— • • •
на функции fl, ••, /,-ъ fj+b ••, fs, fs+i; о обновить ш := ш, s := s + 1, L := {fj = ••} U L. end while
if ОДУ содержит функцию fj чисто алгебраически then
решить его относительно fj и добавить ее к L : L := {f = ..}U L
h(x) := fs(x) % запомнить последнюю
введенную функцию P := L % запомнить полный список
подстановок L % далее подстановка, записанная в первом % элементе P, выполняется в остатке P: while s > r do
p : Test(p)|fs=... % как задано в first(P)
s := s — 1 end_while
end % конец Тела алгоритма
Выходные данные:
• I % список новых функций
• £ % полный список подстановок
• Р % все исходные /1,.., /г — либо парамет-
% рические, либо заданы в P в терминах h • 0 = ш(х, h(x)) % только если первый цикл % заканчивается в силу того, % что ш более не является % недоопределенной.
2.3. Замечания
Прежде чем сравнивать описанный выше алгоритм с алгоритмом Евклида, необходимо сделать несколько замечаний:
• Все шаги нашего алгоритма требуют лишь алгебраических операций и дифференцирования за одним исключением: если однородная часть ОДУ есть полная производная, необходимо найти первообразную неоднородной части. Однако этот интеграл не обязательно должен быть явно вычислен, т.е. записан в терминах элементарных функций. Он может быть оставлен в символьном необработанном виде, а алгоритм будет продолжать работу.
• Коэффициенты a¿j ОДУ могут быть произвольными явными функциями от x и содержать, например, sin или log с
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.