авторефераты диссертаций БЕСПЛАТНАЯ  БИБЛИОТЕКА

АВТОРЕФЕРАТЫ КАНДИДАТСКИХ, ДОКТОРСКИХ ДИССЕРТАЦИЙ

<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ

Астрологический Прогноз на год: карьера, финансы, личная жизнь


Определяющие рациональные функции линейных

обыкновенных дифференциальных уравнений с

полиномиальными коэффициентами

С. А. Абрамов,

А. А. Рябенко

Вычислительный центр РАH

Москва, 119991, ГСП-1, ул. Вавилова, 40

sabramov@ccas.ru, ryabenko@cs.msu.ru

Аннотация

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

1 Введение Известно, что аналитическое решение дифференциального уравнения ad (x)y (d) (x) + · · · + a1 (x)y (x) + a0 (x)y(x) = 0, (1) где a0 (x), a1 (x),..., ad (x) суть полиномы над полем комплексных чисел, может иметь осо бенность, в частности полюс, в точке только в том случае, если ad () = 0 (предполага ется, что ad (x) не является нулевым полиномом). Hижнюю границу порядка полюса можно получить, найдя наименьший целый корень определяющего уравнения, которое является алгебраическим уравнением степени, не превосходящей d, сопоставляемым уравнению (1) и точке (см. [5, 6]). Если у определяющего уравнения нет целых корней, то у уравнения (1) нет таких ненулевых решений, которые либо регулярны, либо имеют полюс в. Пред положим, что каждое из определяющих уравнений, соответствующих корням полинома ad (x), имеет целые корни. Пусть 0, 1,..., k суть все комплексные корни полинома ad (x), и l0, l1,..., lk наименьшие целые корни соответствующих определяющих уравнений (ко торые могут быть произвольными не обязательно отрицательными целыми числами).

Тогда любое мероморфное во всей комплексной плоскости C решение уравнения (1) может быть представлено как произведение рациональной функции V (x) = (x 0 )l0 (x 1 )l1... (x k )lk (2) на некоторую целую функцию;

V (x) названа в этой статье определяющей рациональной функцией уравнения (1).

Задача распознавания существования определяющей рациональной функции для (1) и построения этой функции в случае ее существования может быть рассмотрена при менительно к (1) и в том случае, когда a0 (x), a1 (x),..., ad (x) являются полиномами над Частичная поддержка РФФИ, грант 07-01-00482-a.

произвольным полем K характеристики 0, в этом случае 0, 1,..., k принадлежат полю разложения K коэффициента ad (x). Подстановка y(x) = u(x)V (x), (3) где V (x) определяющая рациональная функция, u(x) новая неизвестная функция, сводит задачу поиска рациональных решений уравнения (1) к задаче поиска полиноми альных решений.

В разделе 3 мы распространяем понятие определяющей рациональной функции на случай неоднородного линейного уравнения с коэффициентами и правой частью, принад лежащими K[x].

В разделе 4 в предложении 6 показывается, что определяющая рациональ ная функция в известном смысле представляет собой оптимальный вариант рационального множителя для подстановки, сводящей поиск рациональных ре шений к поиску полиномиальных решений (алгоритм, позволяющий строить рациональный множитель такого рода для разностного случая, был предло жен в [8];

алгоритмы более простые, но дающие более грубые рациональные множители, для разностного случая ранее предлагались в [2], [3]).

В [11] описано, как, основываясь на разложении ad (x) на неприводимые над K множители и используя p-адические разложения рациональных функций, рациональная функция вида V (x) = (x 0 )m0 (x 1 )m1... (x k )mk, (4) где m0 l0, m1 l1,..., m k lk, может быть построена без вычислений в ал гебраических расширениях поля K. При этом получаемая функция имеет вид, где v(x) полином. То полезное для последующих вычислений обстоя v(x) тельство, что некоторые из неприводимых множителей полинома ad (x) можно включить в рациональную функцию V (x) с положительным показателем сте пени, не используется алгоритмом из [11]. В разделе 5 нашей статьи мы опи сываем в элементарных терминах основанный на полной факторизации ad (x) алгоритм построения определяющей рациональной функции V (x) несколько измененный вариант алгоритма из [11].

Предложенный в [2] алгоритм, который также позволяет получать некото рую рациональную функцию вида (4), был основан на вычислении наибольших общих делителей и результантов полиномов над K без использования полной факторизации полиномов и вычисления корней ad (x). В сообщении [4] указы валось, что алгоритм из [2] можно усовершенствовать так, что результатом его работы всегда будет определяющая функция (2). Подстановка (3) c опреде ляющей V (x) сводит поиск рациональных решений к поиску полиномиальных решений, имеющих в общем случае меньшие степени, чем при использовании V (x). В разделе 6 настоящей статьи детально описана эта усовершенствованная версия алгоритма из [2].

Уточним, что как алгоритмы из [11, 2], так и новые алгоритмы, используют нахождение целых корней полиномов из K[x].

В разделе 7 обсуждается реализация алгоритмов из разделов 5 и 6 в среде Maple, а также демонстрируются результаты некоторых экспериментов.

Статья носит в какой-то мере обзорный характер, и часть текста представляет собой сжатое изложение нескольких лекций спецкурса, читаемого первым автором студентам факультета вычислительной математики и кибернетики МГУ им. М.В.Ломоносова. При этом к новым результатам можно отнести предложение 6, процедуру подразбиения из раздела 6 и описанную в разделе 7 реализацию ряда алгоритмов.

2 Определяющие уравнения Для введения понятий определяющего уравнения и определяющей рациональной функции нам будет удобно использовать формальные ряды. Если K некоторое поле, то, как обычно, через K[[x]] обозначается кольцо формальных степенных (тейлоровых) рядов над K, т.е. рядов вида c0 + c1 x + c2 x2 +..., c0, c1, c2, · · · K. Поле отношений этого кольца, обозначаемое через K((x)), есть поле (лорановых) рядов вида cm xm + cm+1 xn+1 + cm+2 xm+2 +..., (5) cm, cm+1, cm+2, · · · K. Число m произвольное (не обязательно неотрицательное) це лое. Hаименьшее m, для которого для ряда s(x) коэффициент при xm отличен от нуля называется порядком ряда по x (или просто порядком) и обозначается через (s);



для нулевого ряда полагаем (0) =. Через tc(s) мы обозначаем коэффициент при x(s), полагая tc(0) = 0.

Производная ряда s(x) = i i= ci x (в нашем случае лишь конечное число коэффи циентов ci с отрицательными индексами может быть отлично от нуля) определяется как D(s(x)) = s (x) = i i= di x, где di = (i + 1)ci+1 для всех i. Из этого определения следует, что коэффициент d1 всегда равен нулю.

Пусть K поле характеристики 0. Пусть L дифференциальный оператор ad (x)Dd + · · · + a1 (x)D + a0 (x), (6) где a0 (x), a1 (x),..., ad1 (x) K[[x]], ad (x) K[[x]] \ {0}. Мы будем рассматривать уравне ния вида L(y) = f (x), (7) где f (x) K[[x]]. Основной вопрос, который нас сейчас будет интересовать, это какова нижняя граница для порядков рядов s(x) K ((x)) таких, что L(s(x)) = f (x).

Свяжем с оператором L и с уравнением (7) целое число b = min ((aj ) j) (8) 0jd и алгебраическое уравнение I(t) = 0, где tc(aj )tj, I(t) = (9) 0jd (aj )j=b tj = t(t 1) · · · (t j + 1). Уравнение I(t) = 0 называется определяющим уравнением, сопоставленным оператору L и уравнению L(y) = f (x).

Пусть N множество всех целых корней определяющего уравнения. Введем обозна чение min N, если N =, = (10), если N =.

Легко проверить, что если s(x) K[[x]], (s) = m, то (L(s(x))) m+b, и коэффициент при xm+b ряда L(s(x)) равен sm I(m), где sm = tc(s). Таким образом, этот коэффициент равен нулю если и только если I(m) = 0. Отсюда выводится Предложение 1. Пусть L имеет вид (6), f (x) K[[x]]. Пусть s(x) K((x)) и L(s) = f (x). Тогда выполнено неравенство (s) min((f ) b, ), (11) где b и определены посредством (8) и (10).

(Детальное доказательство может быть проведено разбором возможностей m+b = (f ) и m + b (f );

неравенство m + b (f ) невозможно при L(s(x)) = f (x).) В качестве следствия получаем, что если оператор L таков, что определяющее уравне ние I(t) = 0 не имеет целых корней, то однородное дифференциальное уравнение L(y) = не имеет ненулевых решений в поле K((x)).

Значение правой части неравенства (11) будем обозначать через l:

l = min((f ) b, ). (12) Если f (x) нулевой ряд, т.е. уравнение (7) однородное, то l =. Значения и l не зависят от того, рассматриваются ли решения дифференциального уравнения (7) в виде рядов над K или же над каким-либо его расширением.

Если (ad ) = 0 в уравнении (6), и L(s(x)) = f (x), то (s) 0. Это выводится из того, что при (ad ) = 0 ряд ad (x) обратим в K[[x]]. Добавим, что при (ad ) = 0 мы имеем b = d и I(t) = t(t 1) · · · (t d + 1).

Остановимся на вопросе точности оценки (11). В следующем предложении под реше ниями уравнений вида (7), имеющих коэффициенты и правые части в K[[x]], понимаются решения, принадлежащие K((x)).

Предложение 2. Пусть уравнение L(y) = f (x), где L оператор вида (6) и f (x) K[[x]], имеет частное решение, и при этом уравнение L(y) = 0 имеет d линейно неза висимых решений. Тогда уравнение L(y) = f (x) имеет решение, порядок которого совпа дает с l.

Доказательство. Покажем вначале, что определяющее уравнение имеет d различных целых корней, и для каждого из них существует решение уравнения L(y) = 0, порядок которого совпадает с этим корнем. В самом деле, взяв d линейно независимых решений уравнения L(y) = 0, можно, используя гауссовы исключения, построить новые d решений, имеющие попарно различные порядки. Эти порядки должны быть корнями определяю щего уравнения, а степень определяющего уравнения не может превосходить d, поэтому у определяющего уравнения не может быть лишних корней.

Теперь перейдем к доказательству самого утверждения предложения. При этом мы бу дем доказывать несколько более сильное утверждение: уравнение L(y) = f (x) обязательно обладает решением, порядок которого равен (f ) b, а если (f ) b, то и решени ем порядка. Пусть v(x) решение уравнения L(y) = f (x). Используя те d решений уравнения L(y) = 0, построение которых было описано выше, мы с помощью гауссовых исключений можем найти решение v (x) уравнения L(y) = f (x), порядок которого не сов падает ни с одним из корней определяющего уравнения. Для v (x) имеем () = (f ) b.





v Если (f ) b, то в качестве решения, существование которого доказывается, возьмем v (x) + w(x), где w(x) такое решение однородного уравнения, что (w) =.

3 Определяющие рациональные функции Вернемся к случаю, когда коэффициенты оператора L и правая часть уравнения L(y) = f (x) являются полиномами. Здесь и всюду далее будем без оговорок считать, что в этом уравнении L = ad (x)Dd + · · · + a1 (x)D + a0 (x), (13) и a0 (x), a1 (x),..., ad1 (x) K[x], ad (x) K[x] \ {0}. Предполагается также, что f (x) K[x].

Переходя от поля K к какому-нибудь его расширению K, содержащему все корни полинома ad (x), мы можем для каждого такого корня построить уравнение Lx+ (y(x)) = f (x + ), (14) где Lx+ = ad (x + )Dd + · · · + a1 (x + )D + a0 (x + ). (15) Полиномы могут рассматриваться как (тейлоровы) ряды, поэтому для этого уравнения мы можем определить величину l посредством (12). Hам будет удобно обозначать эту величину через l (аналогично можно говорить о величине ). Рациональная функция (x )l (16) ad ()= и будет называться определяющей рациональной функцией (кратко: определяющей функ цией) уравнения L(y) = f (x). Если хотя бы один показатель l равен бесконечности, то определяющая функция (16) не существует.

Покажем, что для нахождения значений l не обязательно прибегать к сдвинутым уравнениям вида (14). Прежде всего, для f (x), p(x) K[x], где p(x) неприводимый, определим величину p(x) (f ), положив ее для ненулевого полинома f (x) равной макси мальному k N, такому, что pk (x) | f (x), и положив ее равной для случая нулевого f (x). Пусть фиксировано такое, что ad () = 0. В рассматриваемом случае f (x) и aj (x), j = 0, 1,..., d, суть полиномы. Мы имеем x (f (x + )) = x (f (x)), и значение tc(f (x + )) может быть найдено с помощью формулы Тейлора, которая справедлива для полиномов над любым полем характеристики 0:

f (m) () tc(f (x + )) =, m!

где порядок m производной равен x (f (x)). Аналогичные соотношения можно получить для aj (x), j = 0, 1,..., d. С обозначениями m,j = x (aj (x)), j = 0, 1,..., d, формула (8) заменится на b = min (m,j j), (17) 0jd формула (9) перепишется в виде (m,j ) aj () j I (t) = t;

(18) m,j !

0jd m,j j=b наконец, (f (x)) заменяется на x (f (x)) в формуле (11). Итак, из предложения (1) сле дует Предложение 3. Для каждого корня полинома ad (x) показатель l в (16) есть min(x (f (x)) b, ), (19) где есть наименьший целый корень определяющего уравнения I (t) = 0 (если целых корней нет, то = ).

Предложение 4. Пусть для уравнения L(y) = f (x) существует определяющая функция V (x). Тогда V (x) K(x).

Доказательство. Пусть неприводимый над K полином p(x) является делителем ad (x), и K некоторое расширение поля K, содержащее все корни полинома ad (x). При фикси рованном j, 0 j d, значения x (aj (x)) совпадают для всех таких, что p() = 0:

над полем K мы имеем x (aj (x)) = p(x) (aj (x)). Отсюда видно, что и определенные посредством (17) значения b совпадают между собой для этих значений. Аналогично, x (f (x)) = p(x) (f (x)). Очевидно, что значения тоже совпадают между собой, так как уравнения I (t) = 0 имеют одинаковые множества целых корней. Поэтому и определенные посредством (19) значения l совпадают между собой для всех таких, что p() = 0. Если обозначить эти совпадающие значения l через lp(x), то выражение (16) для определяющей функции можно переписать в виде plp(x) (x), (20) p(x)Irr(K) p(x)|ad (x) где Irr(K) множество нормированных неприводимых полиномов над K. Отсюда следует требуемое. 4 Рациональные решения Предложение 5. Пусть уравнение L(y) = f (x) имеет решение F (x) K(x). Тогда (i) для уравнения L(y) = f (x) существует определяющая функция;

(ii) F (x) = q(x)V (x), где q(x) K[x] и V (x) определяющая функция уравнения.

Доказательство. Пусть K некоторое расширение поля K, содержащее все корни по g(x) линома ad (x). Положим для произвольной рациональной функции G(x) = h(x) p(x) (G(x)) = p(x) (g(x)) p(x) (h(x)).

Последнее определение корректно (не зависит от выбора конкретных g(x), h(x)).

Так как каждый полином от x над K можно рассматривать как (тейлоров) ряд, то в этом смысле K[x] K[[x]]. Рациональную функцию, представленную отношением двух полиномов g(x) и h(x), можно рассматривать как лоранов ряд, получающийся умножени ем g(x) на h1 (x) в K((x)). Этот ряд не зависит от конкретного представления исходной рациональной функции. При рассматриваемом сопоставлении поле K(x) изоморфно вкла дывается в поле K((x)). Если при этом сопоставлении рациональной функции G(x) отве чает ряд G(x), то x (G(x)) = (G(x)), и производной рациональной функции G(x) будет сопоставлена производная ряда G(x). Из этого сразу следует, что рациональное решение может иметь полюс только в такой точке, в которой ad () = 0. Последнее остается в силе и при рассмотрении рациональных функций над произвольным расширением поля K.

Рассмотрим произвольный корень полинома ad (x). Дифференциальное уравнение Lx+ (y) = f (x + ) (см. (14), (15)) имеет рациональное решение G(x) = F (x + ) и со ответственно решение в виде ряда G(x), откуда определяющее уравнение I (t) = 0 имеет целые корни. Это доказывает (i). Наименьший из целых корней не превосходит (G(x)), т.е. не превосходит x (F (x)), откуда следует (ii). Предложение 5 сводит задачу поиска рациональных решений уравнений рассматрива емого вида к поиску полиномиальных решений того же вида. Хорошо известно (см., на пример, [1], [10]), что для данного линейного дифференциального уравнения L(y) = f (x) рассматриваемого вида можно априори дать верхнюю оценку для степеней его возможных полиномиальных решений. Hайдем c = max (deg aj (x) j) 0jd и построим алгебраическое уравнение I (t) = 0, где lc(aj )tj I (t) = 0jd deg aj (x)j=c (lc, как обычно, обозначает старший коэффициент полинома). Тогда если q(x) K[x] и L(q(x)) = f (x), то deg q(x) max(deg f (x) c, µ), (21) где µ наибольший целый корень уравнения I (t) = 0, а если целых корней нет, то µ =.

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

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

Рациональную функцию U (x) K(x) такую, что любое рациональное решение исход ного уравнения может быть представлено в виде u(x)U (x), u(x) K[x], мы будем называть универсальным множителем рассматриваемого уравнения. Из предложения 5(ii) следует, что определяющая функция является универсальным множителем.

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

Предложение 6. Пусть для уравнения L(y) = f (x) существует определяющая функ ция V (x), имеющая вид (20). Пусть p1 (x), p2 (x),..., pk (x) все различные неприводимые множители старшего коэффициента ad (x) оператора L. Пусть уравнение L(y) = 0 име ет d линейно независимых решений в K(x), и пусть U (x) K(x) его универсальный sk s1 s2 множитель. Тогда U (x) = p1 (x)p2 (x)... pk (x)r (x), где r(x) K[x], r(x) не делится на p1 (x), p2 (x),..., pk (x), и s1 lp1 (x), s2 lp2 (x),..., sk lpk (x).

Как следствие, если F (x) K(x), L(F (x)) = f (x) и F (x) = u(x)U (x) = v(x)V (x), u(x), v(x) K[x], то deg v(x) deg u(x).

Доказательство. Возможность представления рационального решения исходного урав нения как решения в виде ряда и использование предложения 2 дают нам pi (x) (U (x)) lpi (x), i = 1, 2,..., k, а также q(x) (U (x)) 0 для любого неприводимого q(x), не являюще гося делителем ad (x) (в этом случае lq(x) = 0). Итак, используя подстановку с каким-то универсальным множителем, мы приходим к задаче поиска полиномиальных решений. Здесь можно найти верхнюю границу для степеней всех возможных полиномиальных решений и прибегнуть, например, к методу неопределенных коэффициентов. В том случае, который рассматривается в предложении 6, мы получим уравнение, которое имеет много полиномиальных решений, и оценка ви да (21) будет точной в смысле наших обсуждений. Поэтому порядок системы линейных алгебраических уравнений, которую надо будет решать в ходе применения метода неопре деленных коэффициентов, будет достигать минимума при использовании определяющей функции в роли универсального множителя.

5 Построение определяющей рациональной функции с использованием полной факторизации Пусть нам известны все различные неприводимые множители p1 (x), p2 (x),..., pk (x) старшего коэффициента ad (x) оператора L. Пусть p(x) один из этих множителей. Мы можем найти mp(x),j = p(x) (aj (x)), j = 0, 1,..., d, и bp(x) = min (mp(x),j j), 0jd а затем построить полином двух переменных (mp(x),j ) aj (x) j Jp(x) (t, x) = t. (22) mp(x),j !

0jd mp(x),j j=bp(x) По построению этот полином таков, что при подстановке в него вместо x любого корня полинома p(x) мы получаем I (t). Как уже отмечалось в доказательстве предложения 4, при всех таких, что p() = 0, множества целых корней уравнений I (t) = 0 одинаковы.

Обозначим множество таких корней через Np(x) и укажем два способа его нахождения.

Первый способ. Уравнение Jp(x) (t, x) = 0 запишем в виде uv (x)tv + uv1 (x)tv1 + · · · + u0 (x) = 0, (23) где u0 (x),..., uv1 (x), uv (x) полиномы от x степени меньшей, чем deg p(x) (каждый по лином от x можно заменить остатком от деления этого полинома на p(x)), при этом uv (x) ненулевой полином. Это уравнение перепишем по степеням x:

wk (t)xk + wk1 (t)xk1 + · · · + w0 (t) = 0, (24) где k deg p(x) 1, wi (t) K[t], i = 0, 1,..., k, wk (t) K[t] \ {0}. После подстановки вместо x некоторого корня полинома p(x) это уравнение имеет целый корень n0 если и только если все wi (t), входящие в (24), обращаются в 0 при t = n0 (так как элемент поля K(), p() = 0, записанный в виде полинома от степени меньшей, чем deg p(), равен нулю если и только если все коэффициенты этого полинома равны нулю). Множество общих целых корней полиномов wi K[t], i = 0, 1,..., k, будет конечным, поскольку wk (t) K[t] \ {0}. Это множество есть Np(x).

Второй способ основывается на том, что Np(x) является множеством целых корней урав нения Resx (Jp(x) (t, x), p(x)) = (написанный в левой части уравнения результант является полиномом от t).

После того, как Np(x) найдено одним из этих способов, положим p(x) равным мини мальному элементу этого множества, если само это множество не пусто, и равным в противном случае. Далее мы легко находим показатель lp(x) степени полинома p(x) в (20):

lp(x) = min(p(x) (f (x)) bp(x), p(x) ).

Если показатель lp(x) равен бесконечности хотя бы для одного неприводимого множи теля p(x) полинома ad (x), то определяющая функция не существует.

Пример 1. Пусть p(x), q(x) неприводимы над Q, m, n N+. Рассмотрим дифференци альное уравнение p(x)q(x)y (mp(x)q (x) nq(x)p (x))y = 0. (25) Беря множитель q(x) старшего коэффициента, мы получаем bq(x) = 0 и Jq(x) (t, x) = p(x)q (x)t mp(x)q (x). Это дает lq(x) = q(x) = m. Беря теперь p(x), аналогичным образом получаем lp(x) = p(x) = n. Отсюда V (x) = pn (x)q m (x). Подстановка y(x) = u(x)V (x) в (25) приводит к уравнению u = 0, откуда получаем, что общее рациональное решение m (x) исходного уравнения есть C q n (x), где C произвольная постоянная.

p Займемся теперь неоднородным уравнением p(x)q(x)y (mp(x)q (x) nq(x)p (x))y = (26) p(x)q(x)q (x) mp(x)q(x)q (x) + nq 2 (x)p (x).

Левая часть уравнения не изменилась, поэтому bp(x), bq(x), Jp(x) (t, x), Jq(x) (t, x), p(x) и q(x) остаются прежними. Обозначив правую часть уравнения (26) через f (x), мы имеем q(x) (f (x)) = 1, p(x) (f (x)) = 0. Поэтому получаем lp(x) = n, lq(x) = 1 и V (x) = pn (x)q(x).

После подстановки y(x) = u(x)V (x) придем к уравнению, имеющему полиномиальное решение Cq m1 (x) + pn (x). Это соответствует тому, что общим рациональным решением m уравнения (26) будет Cq (x)+q(x)p(x).

pn (x) 6 Построение определяющей рациональной функции с использованием уравновешенной факторизации с подразбиением Алгоритм из раздела 5 предполагает предварительное нахождение всех неприводимых делителей p1 (x), p2 (x),..., ps (x) полинома ad (x). Если по какой-то причине нежелательно прибегать к полной факторизации, то можно использовать другой вариант этого алгорит ма, который основывается на уравновешенной факторизации ([2]). Приведем необходимые определения.

Пусть f (x), g(x) K[x], deg f (x) 0. Полином f (x) называется уравновешенным по отношению к g(x), если либо g(x) нулевой полином, либо g(x) = f l (x)(x), g (x) K[x], g l 0, и полиномы f (x), g (x) взаимно просты. Разложение f (x) = u1 (x)u2 (x)... uk (x), deg ui (x) 0, i = 1, 2,..., k, называется уравновешенной факторизацией f (x) по отноше нию к g(x), если каждый полином ui (x) уравновешен по отношению к g(x). Пусть S конечное множество полиномов из K[x], пусть f (x) K[x], deg f (x) 0. Тогда f (x) назы вается уравновешенным по отношению к S, если он уравновешен по отношению к каждому элементу S. Представление f (x) в виде произведения уравновешенных по отношению к S сомножителей называется уравновешенной факторизацией полинома f (x) по отношению к S.

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

Мы можем освободить полином ad (x) от квадратов, взяв частное от деления ad (x) на gcd(ad (x), ad (x)). Обозначим результат через A(x). Пусть уравновешенная факторизация A(x) по отношению к множеству полиномов f (x), a0 (x), a1 (x),..., ad (x) (27) имеет вид h1 (x)h2 (x) · · · hk (x). (28) Пусть g(x) это один из полиномов (27), и h(x) один из множителей произведения (28). Будем обозначать через h(x) (g(x)) наибольший показатель степени, с которым h(x) делит g(x). Из определения уравнове шенной факторизации следует, что для любого неприводимого делителя p(x) полинома h(x) мы имеем p(x) (g(x)) = h(x) (g(x)).

Это говорит о том, что подход, описанный в разделе 5, может использоваться и для де лителей, не являющихся, возможно, неприводимыми, но являющихся уравновешенными в указанном смысле. Однако необходимы уточнения, касающиеся поиска целых корней уравнения (24), так как теперь мы уже не можем считать, что для равенства нулю выра жения в левой части уравнения все wi (t) должны обращаться в нуль. Поэтому первый из рассмотренных в разделе 5 способов вычисления множества целых корней в данном слу чае не подойдет. Hо формальное применение второго способа не вызывает затруднений.

Hайдем полином Jh(x) (t, x) по аналогии с (22), используя h(x) вместо p(x), и рассмотрим множество целых корней уравнения Resx (Jh(x) (t, x), h(x)) = 0.

Мы можем определить h(x) по аналогии с p(x), а затем показатель степени для h(x), положив его равным lh(x) = min(h(x) (f (x)) bh(x), h(x) ).

Hайдя произведение всех уравновешенных множителей с такими показателями степеней, мы получим рациональную функцию V (x).

Подстановка y(x) = u(x)V (x) позволяет переходить, например, от задачи поиска ра циональных решений исходного дифференциального уравнения к задаче поиска полино миальных решений нового уравнения того же порядка ([2]), но V (x) не является в общем случае определяющей функцией, описанная подстановка может оказаться более грубой в смысле предложения 6, чем подстановка y(x) = u(x)V (x) с определяющей функцией V (x).

Однако V (x) будет определяющей функцией, если каждый уравновешенный множи тель h(x) является плоским с конечным показателем, т.е. для всех корней,,... поли нома h(x) определяющие уравнения I (t) = 0, I (t) = 0,... (29) имеют целые корни и при этом наименьшие целые корни всех этих уравнений равны одному и тому же числу n. Тогда n показатель множителя h(x) в V (x). Если же все уравнения (29) не имеют целых корней, то уравновешенный множитель h(x) считаем плос ким с показателем. Hаличие плоского множителя с показателем говорит о том, что определяющая функция не существует.

Пусть Nh(x) множество всех целых корней уравнения Resx (Jh(x) (t, x), h(x) = 0. Исходя из h(x), Jh(x) (t, x), Nh(x) разложение h(x) на плоские множители может быть выполнено несложной процедурой, основанной на gcd-технике. Эта процедура называется подразбиением. Опишем ее, исполь зуя для простоты обозначение J(t, x) вместо Jh(x) (t, x).

Пусть N = {n0, n1,..., n } и n0 n1 · · · n. Тогда для n0 мы найдем h[n0 ] (x) = gcd(J(n0, x), h(x)) и изменим h(x), заменив его частным от деления h(x) на h[n0 ] (x). Затем проделаем тоже самое с J(t, x), с измененным h(x) и с n1, это даст нам полином h[n1 ] (x) и т.д. В итоге мы разложим h(x) на множители h[n0 ] (x), h[n1 ] (x),..., h[n ] (x). (30) Если после вычисления h[n ] (x) и соответствующего изменения h(x) мы получаем deg h(x) 0, то определяющая функция не существует. Если этого не произошло, то, те из полиномов (30), которые оказались равными единице, можно исключить из даль нейшего рассмотрения, при этом каждый из оставшихся полиномов вида h[ni ] (x), 0 i, является плоским с показателем ni.

Пример 2. Вернемся к уравнению (25). Старший коэффициент (обозначим его через a1 (x)) является бесквадратным, и его возможная уравновешенная факторизация состоит из единственного множителя h(x), равного a1 (x). Получаем bh(x) = 0 и Jh(x) (t, x) = (p(x)q(x)) t (mp(x)q (x) nq(x)p (x)).

Множеством целых корней уравнения Resx (Jh(x) (t, x), h(x)) является N = {n, m}. Ес ли не прибегать к подразбиению, то получим V (x) = (p(x)q(x))n. Выполним подраз биение. Имеем gcd(Jh(x) (n, x), h(x)) = p(x). Изменяя h(x), получаем h(x) = q(x) и gcd(Jh(x) (m, x), q(x)) = q(x). Получаем определяющую функцию V (x) = pn (x)q(x)m.

Подстановка y(x) = u(x)V (x) приводит к уравнению q(x)u (x) (n + m)q (x)u(x) = 0, имеющему полиномиальное решение Cq n+m (x). Подстановка y(x) = u(x)V (x) приводит к уравнению u (x) = 0, его полиномиальные решения константы.

Сходным образом для уравнения (26) мы получим (p(x)q(x))n до подразбиения, и pn (x)q(x) после.

В этом примере не обязательно считать p(x) и q(x) неприводимыми. Уравновешенная факторизация, как и уравновешенная факторизация с подразбиением, будет выполняться точно так же и при более слабом предположении о том, что p(x), q(x), а также p(x), p (x) и q(x), q (x) взаимно просты.

7 Реализация и эксперименты В среде Maple (см. [9]) алгоритм построения универсального множителя уже был ре ализован как вспомогательная процедура, используемая при поиске рациональных ре шений дифференциального уравнения с полиномиальными коэффициетами процедурой DEtools[ratsols]. Существует даже две таких процедуры. Одна из них реализована на основе полной факторизации и строит определяющую функцию для однородного уравне ния, другая на основе уравновешенной факторизации (без подразбиения), строит уни версальный знаменатель (т.е. U (x) из предложения 6 с s1 0,..., sk 0).

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

Таким образом, в среде Maple 11 был создан пакет IndicialFunction. Продемонстри руем работу главной процедуры пакета на уравнении из примера 1. Уравнение (25) запи сывается обычным в Maple образом:

ode := p(x)*q(x)*diff(y(x),x)-m*p(x)*diff(q(x),x) n*q(x)*diff(p(x), x))*y(x):

Зададим p(x) = x5 + 2, m = 5, q(x) = x3 + x 3, n = 7:

ode1 := eval(ode=0, {p(x) = x^5+2, m = 5, q(x) = x^3+x-3, n = 7}):

Вычислим определяющую функцию:

IndicialFunction(ode1, y(x));

(x3 + x 3) (x5 + 2) Аналогично, для неоднородного уравнения (26) f := p(x)*q(x)*diff(q(x),x)-(m*p(x)*diff(q(x),x) n*q(x)*diff(p(x), x))*q(x):

ode2 := eval(ode=f, {p(x) = x^5+2, m = 5, q(x) = x^3+x-3, n = 7}):

получим IndicialFunction(ode2, y(x));

x3 + x (x5 + 2) Пакет содержит три процедуры построения определяющей функции:

• IndicialFunction:-ByFactors: использование полной факторизации старшего коэф фициента с помощью стандартной Maple процедуры factors;

• IndicialFunction:-ByFactorsAndResultant: полная факторизация и вычисление Np(x) с помощью результанта;

• IndicialFunction:-BySubpartition: использование уравновешенной факторизации с последующим подразбиением.

Имеющаяся в Maple процедура уравновешенной факторизации ‘DEtools/balancedfacts‘ также была модифицирована и помещена в пакет IndicialFunctions. Процедура ‘DEtools/balancedfacts‘ возвращает уравновешенную факторизацию полинома f (x) = p0 ps1 (x) · · · psk (x) по отношению к g(x) 1 k в виде списка [p0, [p1 (x), s1 ],..., [pk (x), sk ]]. Например, для f := x^13+x^11-3*x^10+4*x^8+4*x^6-12*x^5+4*x^3+4*x-12:

g := x^4+x^2-2*x+x^3-3:

мы получаем ‘DEtools/balancedfacts‘(f, [g], x);

Такие двух- (и даже трех-) сложные имена с кавычками давались в старых версиях Maple вспомогательным процедурам пакетов до тех пор, пока не ввели структуру module. Процедура ‘DEtools/balancedfacts‘ не имеет своей хелп-страницы, но доступна для использования.

[1, [[x5 + 2, 2], [x3 + x 3, 1]]] Это значит, что f (x) = (x5 + 2)2 (x3 + x 3).

В процессе такой факторизации становится известно и представление g(x) = pi (x)i gi (x).

Поскольку эта информация необходима при построении определяющей функции, мы за программировали процедуру IndicialFunction:-BalancedFactorization так, чтобы она передавала ее во втором списке вида [g0 (x), p1 (x) (g(x)),..., pk (x) (g(x))] :

IndicialFunction:-BalancedFactorization(f, [g], x);

[1, [[x5 + 2, 2], [x3 + x 3, 1]]], [[x + 1, 0, 1]] То есть g(x) = (x + 1)(x5 + 2)0 (x3 + x 3)1.

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

st := time();

IndicialFunction:-BySubpartition(ode1, y(x)):

time()-st;

0. st := time();

IndicialFunction:-ByFactors(ode1, y(x)):

time()-st;

0. st := time();

IndicialFunction:-ByFactorsAndResultant(ode1, y(x)):

time()-st;

0. Время работы всех процедур достаточно мало, и примерно одинаково. Будем повы шать степень полинома p(x) в уравнении (25). Используем стандартную Maple процедуру randpoly для генерации случайного полинома нужной нам степени:

randpoly(x, degree = 10);

56x10 62x7 + 97x6 73x3 4x Мы провели тестирование уравнения при 50 deg p(x) 100. Приведем время счета для степеней 50, 60, 70, 80, 90, 100:

deg p(x) 50 60 70 80 90 ByFactors 0.036 0.032 0.040 0.072 0.104 0. ByFactorsAndResultant 0.052 0.044 0.052 0.096 0.148 0. BySubpartition 0.328 0.380 0.732 2.360 2.464 3. Эти эксперименты показали, что, как правило, ByFactors и ByFactorsAndResultant работают одинаково, существенно быстрее, чем BySubpartition. Вероятно, это является следствием того, что в системе Maple факторизация полиномов реализована значительно более тщательно, чем поиск наибольшего общего делителя.

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

V := IndicialFunction(ode2, y(x));

x3 + x V := (x5 + 2) Выполним замену y(x) = V (x)u(x):

ode3 := eval(ode2, y(x) = V*u(x));

35(x3 + x 3) u(x) x ode3 := (x5 + 2)(x3 + x 3) + (x5 + 2) d (3x2 + 1) u(x) (x3 + x 3) dx u(x) + (x5 + 2)7 (x5 + 2) (5 (x5 + 2) (3x2 + 1) 35 (x3 + x 3) x4 ) (x3 + x 3) u(x) = (x5 + 2) (x5 + 2) (x3 + x 3) (3x2 + 1) (5 (x5 + 2) (3x2 + 1) 35 (x3 + x 3) x4 ) (x3 + x 3) и построим для нового уравнения полиномиальное решение с помощью процедуры DEtools[polysols]:

Psol := DEtools[polysols](ode3, u(x));

P sol := [[81 108x + 54x2 120x3 + 109x4 36x5 + 58x 36x7 + 6x8 12x9 + 4x10 + x12 ], 128 + 448x5 + 560x15 + 280x20 + 84x25 + 14x30 + x35 + 672x10 ] Полученный ответ означает, что общее полиномиальное решение уравнения ode3 вы глядит следующим образом:

Psol[1][1]*C+Psol[2];

(81 108x + 54x2 120x3 + 109x4 36x5 + 58x 36x7 + 6x8 12x9 + 4x10 + x12 ) C + 128 + 448x5 + 560x15 + 280x20 + 84x25 + 14x30 + x35 + 672x где C произвольная постоянная. Домножим его на V (x) и получим общее рациональное решение уравнения ode2:

V*Psol[1][1]*C+V*Psol[2];

x3 + x 81 108x + 54x2 120x3 + 109x4 36x5 + 5 + 2) (x 58x6 36x7 + 6x8 12x9 + 4x10 + x12 C+ x3 + x 128 + 448x5 + 560x15 + 280x20 + 84x25 + 14x30 + x35 + 672x 5 + 2) (x С помощью процедуры DEtools[ratsols] мы тоже получим общее рациональное решение (в другой форме):

DEtools[ratsols](ode2, y(x));

(x3 + x 3)5 (71339352 + 118898408 + 79557752x5 + [[, 5 + 2)7 (x + 2) (x 145320248x3 79265520x2 162934680x4 + 2936432x11 + 1468552x13 + 560x16 + 560x18 + 280x21 + 280x23 + 84x26 + 84x28 + 14x31 + 14x33 + x36 + x38 26421392x8 96879632x6 + 80733400x7 17616576x10 + 291896x15 4403640x12 + 29357600x9 840x20 252x25 42x30 3x35 )] Теперь сравним время счета с помощью новой процедуры:

st := time();

V := IndicialFunction(ode2, y(x)):

ode3 := eval(ode2, y(x) = V*u(x)):

Psol := DEtools[polysols](ode3, u(x)):

[Psol[1][1]*V, Psol[2]*V]:

time()-st;

0. и с помощью DEtools[ratsols]:

st := time():

DEtools[ratsols](ode2, y(x)):

time()-st;

0. Новая программа работает быстрее.

В пакете IndicialFunction для дифференциального уравнения со старшим коэффи циентом ad (x) программа сначала получает его факторизацию (полную или уравновешен ную) ad (x) = ps1 (x)... psk (x), 1 k затем последовательно строит определяющие уравнения для всех множителей, ищет их целые корни и вычисляет показатели lpi. Из тех множителей pi (x), для которых показатель конечен, составляет произведение lp lp V = pi1i1 (x) · · · pit it (x), которое не всегда будет определяющей функцией. Tе множители, для которых lpi =, запоминает в списке B = [pj1 (x),..., pjr (x)].

В итоге процедура возвращает пару (V, B). Например, для уравнения ode4 := (2+2*x^3+2 x)*y(x)+(x^3+x^4)*diff(y(x), x):

получим IndicialFunction(ode4, y(x));

, [x] (1 + x) Этот ответ означает, что данное уравнение не может иметь рациональных решений, что в точке x = 1 оно имеет решения в виде формального ряда (лоранова), а в x = 0 таких решений нет. Применив замену y(x) = u(x)/(x + 1)2 к ode4, затем домножив на общий знаменатель, мы получим уравнение с коэффициентами меньшей степени:

ode5 := numer(normal(eval(ode4, y(x) = u(x)/(1+x)^2)));

d ode5 := x3 u(x) + 2u(x) dx для которого V = 1:

IndicialFunction(ode5, u(x));

1, [x] Если поставлена задача поиска только рациональных решений, время работы можно сократить, прекратив ее, как только программа получит lpi =. Это будет сделано, если задан дополнительный аргумент ’ratsols’:

IndicialFunction(ode4, y(x), ’ratsols’);

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

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

15. Вычисл. матем. и кибернетика, No. 3, 53–60 (1989).

[2] Абрамов С.А., Рациональные решения линейных дифференциальных и разностных уравнений с полиномиальными коэффициентами, Журнал вычисл. матем. и матем.

физ., 29, No. 11, 1611–1620 (1989).

[3] Абрамов С.А., Рациональные решения линейных разностных и q-разностных уравне ний с полиномиальными коэффициентами, Программирование, No. 6, 3–11 (1995).

[4] Абрамов С.А., Построение определяющих рациональных функций линейных обыкно венных дифференциальных уравнений с полиномиальными коэффициентами, Меж дународная конференция Дифференциальные уравнения и топология, посвящен ная 100-летию со дня рождения Л.С. Понтрягина. Тезисы докладов, 86–87 (2008).

[5] Камке Э., Справочник по обыкновенным дифференциальным уравнениям, М: Изда тельство Hаука, Главная редакция физико-математической литературы (1965).

[6] Коддингтон Э.А., Левинсон Н., Теория обыкновенных дифференциальных уравнений, M: Издательство иностранной литературы (1958).

[7] Bronstein M., Integration and Dierential Equations in Computer Algebra, Программи рование, No. 5, 26–44 (1992).

[8] van Hoeij M., Rational Solutions of Linear Dierence Equations, ISSAC’98 Proceedings, 120–123 (1998).

[9] Monagan M.B., Geddes K.O., Heal K.M., Labahn G., Vorkoetter S.M., McCarron J., DeMarco P., Maple 11 introductory programming guide Waterloo Maple Inc., Waterloo, Ontario, Canada, 2007.

[10] Petkovek M., H.S. Wilf, D. Zeilberger, A = B, Peters, 1996.

s [11] Singer M.F., Liouvillian Solutions of nth Order Homogeneous Linear Equations, American Journal of Mathematics, 103, No. 4, 661–682 (1981).



 

Похожие работы:





 
2013 www.netess.ru - «Бесплатная библиотека авторефератов кандидатских и докторских диссертаций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.