ПРОГРАММИРОВАНИЕ, 2014, No 2, с. 69-74
КОМПЬЮТЕРНАЯ АЛГЕБРА
ЛОКАЛЬНЫЕ УТОЧНЕНИЯ НИЖНИХ ГРАНИЦ ВАЛЮАЦИЙ РЕШЕНИЙ ЛИНЕЙНЫХ РАЗНОСТНЫХ СИСТЕМ С МЕРОМОРФНЫМИ КОЭФФИЦИЕНТАМИ
© 2014 г. М.И. Баранов МГУ им. М.В. Ломоносова, факультет вычислительной математики и кибернетики 119991 Москва, ГСП-1, Ленинские горы, МГУ, д. 1, стр. 52 E-mail: mix-baranov@yandex.ru Поступила в редакцию 24.09.2013
Предлагается алгоритм уточнения нижних границ валюаций компонент мероморфного решения линейной разностной системы с мероморфными коэффициентами. Система может иметь любой порядок. Алгоритм основан на сопоставлении валюаций коэффициентов уравнений с заданными границами валюаций решений.
1. ВВЕДЕНИЕ
Оценивание порядков полюсов решений разностных уравнений и систем уравнений возникает в компьютерной алгебре как этап построения самих решений. Классическим примером служит построение рациональных решений (т.е. решений в виде рациональных функций) линейных разностных уравнений и систем с полиномиальными коэффициентами. Многие известные алгоритмы на первом этапе находят так называемый универсальный знаменатель всех рациональных решений ([1, 2, 3, 4, 5]), т.е. полином и (ж), зная который, можно сделать подстановку у(х) = щу)' гДе У (ж) _ неизвестная функция в случае одного уравнения или вектор-столбец неизвестных функций в случае системы, а затем применить какой-либо из известных алгоритмов поиска полиномиальных решений ([1, 2, 6]). Несколько иной подход при рассмотрении систем первого порядка использован в работе [7], где при подстановке, позволяющей перейти к поиску полиномиальных решений, для разных компонент вектора у(ж) используются, вообще говоря, разные рациональные множители.
Более общей является задача оценивания валюаций мероморфных решений линейных разностных уравнений и систем (понятие валюации
обсуждается ниже в разделе 2). Эта задача рассматривалась, например, в [8]. В нашей работе тоже речь идет о валюациях мероморфных решений линейных разностных уравнений вида
ai3 (х)у^(х+j ) = °>
(1)
O^j^r 1
а также систем, состоящих из любого конечного числа таких уравнений. При этом коэффициенты уравнений и систем предполагаются мероморфными. Собственно задача, которая нами рассматривается, состоит в уточнении известных нижних границ валюаций компонент некоторых (не обязательно всех) решений системы. Первоначальные границы считаются известными. Они могут быть построенными предварительно какими-то известными алгоритмами или просто задавать условие, которому должны удовлетворять интересующие нас решения системы. Требуется по возможности уточнить эти границы, исходя из того, что они являются нижними границами решений заданной конкретной системы.
Предлагаемый нами алгоритм использует свойство валюаций, которое в разделе 2 нашей статьи названо свойством неединственности минимума. На этом свойстве также основан предложенный в [9] подход, который позволяет
понизить степени универсального знаменателя скалярного разностного уравнения, что в свою очередь позволяет уменьшить степени коэффициентов в уравнении, полученном в результате подстановки у(ж) = щХ)' В [10] был предложен так называемый алгоритм балансировки, применяемый для уточнения границ порядков полюсов компонент решения дифференциальных и разностных систем первого порядка. Наш алгоритм применим к системам уравнений любого порядка, и система может содержать любое число уравнений, в частности, меньшее или большее числа компонент вектора у(ж). Этот алгоритм в отличие от алгоритма балансировки уточняет не только отрицательные валюации (случай полюса), но и произвольные неотрицательные валюации. Показано, что однократное рассмотрение уравнений и тех точек, в которых заданы нижние границы валюаций, может дать границы валюаций, допускающие дальнейшее уточнение этим же алгоритмом. Обнаруживается, что последовательность таких уточнений может оказаться бесконечной. Вместе с этим в статье доказывается, что если yi(x),..., ут(ж) — компоненты решения у(ж) системы, и система такова, что для каждого i, 1 ^ i ^ m, имеется мероморфное решение, для которого компонента Уг(ж) не равна тождественно нулю, то заданные границы не могут допускать бесконечного числа таких уточнений.
2. ВАЛЮАЦИИ МЕРОМОРФНЫХ ФУНКЦИЙ
Для мероморфной функции f (ж) и точки а таких, что разложение функции f (ж) в окрестности точки а в ряд Лорана имеет вид f (ж) =
Аг(ж — а)г, положим валюацию функции f (ж) в а
ж—а
эффициентом: valx-af (ж) = min {i : a» = 0}. По определению valx-a0 = те.
Для произвольных ненулевых мероморфных функций f (ж) $(ж) и точк и а выполняются следующие соотношения:
valx-a(f (ж)^(ж)) = valx-af (ж) + valx-ag^),
При этом
valx-af (x) < valx-ag(x) —^ valx-a (f (x) + g(x)) = val x—a f (x).
Следующее свойство валюаций (назовем его свойством неединственности минимума) легко выводится из (2): если сумма fi(x) + f2(x) + ■ ■ ■ + fn(x) мероморфных функций тождественно равна нулю и а — некоторая точка комплексной плоскости, то найдутся два таких целых значения i, j, 1 ^ i < j ^ n, что
valx-afi(x) = valx-afj(x) = min valx-affc(x).
i^fc^n
В дальнейшем это свойство мы будем использовать в несколько иной форме:
Предложение 1. Пусть сумм,a g1 (x) + g2(x) + ■ ■ ■ + gn(x) мероморфных функций тождественно равна, нулю и в некоторой точке а для целых чисел w1, w2,..., wn т,аких, ч,m,о wi ^ w2 ^ ... ^ wn; выполнено valx-agi(x) ^ wi; i — 1,..., n. Тогда, valx-agl (x) ^ W2-
Доказательство. Рассмотрим два случая: valx-agi(x) > mini^j^n valx-agi(x) и valx-agi(x) = minien valx-agi(x). в первом случае мы сразу получаем требуемое. Во втором случае valx-agi(x) в силу свойства неединственности минимума совпадает с valx-agi(x) при некотором i ^ 2, и valx-agi(x) ^ w^ ^ w2. □
3. ЛОКАЛЬНЫЕ УТОЧНЕНИЯ
Пусть фиксирована точка xo комплексной плоскости и целые d Г d ^ r Пусть при этом известны нижние границы Vis валюаций мероморфных функций yi(x),..., ym(x) в точках xo + s:
valx-xo-syi(x) = valx-xoyi(x + s) ^
i = 1,...,m, s = 0,1, ...,d, и пусть известно линейное разностное уравнение вида (1) с меро-морфными коэффициентами, которому удовлетворяют yi(x),..., ym(x). Мы будем использовать валюации
valx-a(f (x)+g(x)) ^ min {valx-ar(x), valx-as(x)}
öijs — valx-xo-s (x) — valx-xo (x + s)
коэффициентов уравнения в точках ж0 + s, s = 0,1,..., d — r
(3)
(кроме чисел мы не будем использовать никакой другой информации о мероморфных коэффициентах уравнения). Выбрав некоторое в такое, что 0 ^ в ^ d — г, находим
ßs = min (äijs + Vi,j+s) .
(4)
Если существует только одна пара индексов
i0, J0, ДЛЯ КОТОрОЙ ßs = äiÜ,jÜs + ViÜ,jÜ+s, то в
силу предложения 1 значение ViÜ,jÜ+s можно заменить на большее значение
min (äijs + vi,j+s) — ai0,j0s. (5)
Ü^j^r l^i^m (i,j) = (iÜ,jÜ)
s
ства {0,..., d — r}, для каждого из них находится ßs и выполняется, если возможно, описанное уточнение значения ViÜ,jÜ+^. Однако то, что все s из указанного множества рассмотрены, не гарантирует, что дальнейшие уточнения невозможны.
Пример 1. Рассмотрим уравнение:
(Ж + 1)(Ж + 2)y2(x + 2) + (Ж + 2)V(x + 1) + +У2(Ж + 1) — Ж(Ж + 1)yi(x) = 0.
Зафиксируем Жо = —3. Выпишем нижние границы валюаций коэффициентов уравнений для Жо + s, s = 0
äi,2,o = те, ä2,2,o = 0, äi,i,o = 0,
02,1,0 = 0, äi,o,0 = 0, ¿2,0,0 = те.
Пусть известны следующие нижние границы валюаций компонент решения: vi,2 = —1,V2,2 = — 1,vi,i = 0,V2,i = 0,vi,0 = 0, V2,0 = 0.
Рассмотрим границы валюаций слагаемых s=0
ß0 = min (äi,j,0 + Vi,j) = ¿2,2,0 + V2,2 = —1 <
< min (äi,j,0 + Vi,j). (i,j) = (2,2)
Как видим, здесь нарушается свойство неединственности минимума валюации. Используя предложение 1, можно утверждать, что V2,2 = 0
Если изначально дана система из уравнений
у(ж)
же самый процесс уточнения можно провести, используя все уравнения. Потребуются валюации коэффициентов всех уравнений в точках (3). Вновь возможно, что перебор всех этих точек и уточнение валюаций функций У1(х), у2(х),..., ут(х) с помощью всех имеющихся уравнений приводят к таким границам валюаций этих функций, для которых возможно дальнейшее уточнение с помощью такого же использования имеющихся уравнений. Выбрав уравнение системы и взяв точку из (3), можно попытаться уточнить значение одной из границ валюаций, переходом к значению (5). Если попытка оказалась успешной, то ее результат будем называть локальным уточнением.
Предложение 2. Пусть фиксирована конечная система из уравнении вида (1), точка жо, целое неотрицательное d ^ г и границы валюаций г^ для функций у1(х),..., ут(х) в точках ж0 + в г = 1,..., т в = 0,1,..., d. Пусть дополнительно известно, что для каждого г = 1,..., т существует такое решение у* (ж) = (у*(ж),... ,ут(ж)) системы, что у*(ж) ф 0. Тогда возможно лишь конечное число локальных уточнений.
Доказательство. Предположим противное. Допустим, алгоритм не завершает свою работу, производя бесконечное количество локальных уточнений. Тогда бесконечное подмножество локальных уточнений будет приходиться, по крайней мере, на одну из нижних границ валюаций г^.^. Поскольку при каждом локальном уточнении граница повышается на натуральную величину, большую нуля, то можно сделать вывод, что г^^ = те. Это означает, что для всех решений исходной системы уравнений у^0 (ж) ф 0. Получили противоречие с условиями предложения. □
Покажем важность условий, сформулированных в предложении 2.
Пример 2. Рассмотрим систему
Г у1 (ж + 1)+ у2(ж) =0
|у1(ж + 1) — жу2(ж) = 0
Эта система уравнений не имеет ненулевых решений.
Зафиксируем хо = 0. Выпишем нижние границы валюаций коэффициентов уравнений для точек хо + в, в = 0. Для первого уравнения системы:
а^ = 0, а^ = те, а^О = те, а^О = 0.
Для второго уравнения системы:
~(2) п ~(2) ~(2) ~(2) 1 =0, а 21 = те, 0 = те, а 20 = 1.
Пусть заданы следующие нижние границы валюаций компонент решения:
VI д = 0, ^2 ,о = -1.
На каждой нечетной итерации возможно повысить границу ^2 , о, применяя предложение 1 для границ валюаций слагаемых первого уравнения системы. Аналогично на каждой четной итерации возможно повысить границу ыд, применяя то же предложение для границ валюаций слагаемых вт
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.