ПРОГРАММИРОВАНИЕ, 2012, No 2, с. 11-28
КОМПЬЮТЕРНАЯ АЛГЕБРА -
УДК 512.77+531.36
РАЗРЕШЕНИЕ АЛГЕБРАИЧЕСКОЙ СИНГУЛЯРНОСТИ АЛГОРИТМАМИ СТЕПЕННОЙ ГЕОМЕТРИИ
© 2012 г. А.Д. Брюно, А.Б. Батхин
Институт прикладной математики им. М.В. Келдыша РАН 125047 Москва, Миусская пл., 4 E-mail: abruno@keldysh.ru, batkhin@gmail.com Поступила в редакцию 10.06.2011
Рассматривается многочлен от трех переменных вблизи его особой точки, в которой он сам и его частные производные равны нулю. Предлагается метод вычисления асимптотических разложений по параметрам для всех ветвей множества нулей этого многочлена вблизи указанной точки. Метод основан на пространственной степенной геометрии и существенно использует современные алгоритмы компьютерной алгебры: базис Грёбнера и алгоритмы работы с алгебраическими кривыми. Предлагается реализация этого метода на примере некоторого многочлена шестой степени от трех переменных вблизи бесконечности и вблизи его вырожденной особой точки.
1. АСИМПТОТИЧЕСКОЕ РЕШЕНИЕ АЛГЕБРАИЧЕСКОГО УРАВНЕНИЯ
1.1. Постановка задачи
Пусть д(^) — многочлен от 3-х переменных (комплексных или вещественных), т.е. ^=(хх,у,г).
Определение 1. Точка называется особой точкой порядка к многочлена д(Р), если в этой точке обращаются в ноль сам многочлен д и все его частные производные до порядка к включительно, но отлична от нуля хотя бы одна производная порядка к + 1. Если д^°) = 0, но в точке хотя бы одна частная производная многочлена д^) не равна нулю, то д° — простая точка многочлена д или множества
9 = Ш : д(д)=0}.
Пусть д(0°) = 0, наша задача — исследовать множество вблизи точки д°. Если д° — простая точка, то по теореме Коши о неявной функции вблизи этой точки на множестве 9 одна из локальных координат выражается в виде степенного ряда от других локальных координат, что и является локальным описанием множества 9. Содержательной такая задача является вблизи особой точки д°. Ниже
уточняется постановка задачи и описываются способы ее решения.
Задача 1. Вблизи особой точки д° = 0 для всех ветвей решений уравнения д(^) = 0 найти разложения одного из следующих трех типов: Тип 1:
те те те
х = ^ ькvk, у = ^2Скук,* = £ук, к=1 к=1 к=1
где V — локальный параметр, Ьк,Ск,йк — либо вещественные, либо комплексные постоянные коэффициенты. Тип 2:
х = ^2 ЬрдиРVя, У = ^2 СрчuPvq, * = ^2 upvq,
где и и V — локальные координаты, коэффициенты ЬР9, Ср9, г1Р9 постоянны, целочисленные показатели (р, д) лежат в некотором секторе раствора меньше п. Тип 3:
те те те
X = ^2 вк (и>к, У = ^2 7к (и>к, * = ^ 6к (и>к,
к=° к=° к=°
где в к (и), 7к (и), 5 к (и) либо рациональные функции от и, либо рациональные функции от
и и л/'ф(и), где 'ф(и) — многочлен. Здесь и — глобальная координата, а V — локальная.
Задача 2. Для всех кривых особых точек множества 0, примыкающих к точке Р°, найти разложения типа 1.
1.2. Объекты и алгоритмы степенной геометрии [1, гл. I, II]
Пусть задана конечная сумма (например, многочлен)
g(Q) = Е9RQR по R е S
(1)
(Q) = Е gR Q
R
по R е j П S(g).
Обобщенная грань Г^ имеет 3 — й линейно независимых нормальных векторов
Мк = ,п2к,п3к), направленных наружу
многогранника Г(д). Если все точки К
носителя Б(д) рациональны, то все нормальные
векторы Мк можно взять целочисленными.
Каждая укороченная сумма является
квазиоднородной, и число ее разных
квазиоднородностей равно 3 — й.
Пусть М^ - трехмерное вещественное пространство, двойственное пространству М3, и Б = (в^в2,в3) — точки этого пространства. Тогда для точек К е М3 и Б е М3 определено скалярное произведение
грани Г^ является точкой пространства М3. Для нее скалярное произведение (К, Мк) на носителе, т.е. по К е Б(д), достигает максимума ск = (К, Мк) на точках К е Г^ П Б, т.е. принадлежащих обобщенной грани Г^. Более того, множество всех тех точек Б е М3, для которых скалярное произведение (2) достигает максимума по всем точкам К е Б(д) именно на точках К е Г^, называется нормальным конусом обобщенной грани Г^ и обозначается
U
(d) k '
Пусть двумерные грани Г^2), ( = (ь...(т, примыкают к обобщенной грани Г^, т.е. Г^ = г(2) П ■ ■ ■ П Г(.2) . Тогда
.1 (т
где Q = (x,y,z) е R3, R = (ri,r2, r3) е R3 и Qr = xri y 2 z 3, gR = const е R. Каждому слагаемому суммы (1) ставится в соответствие его векторный показатель степени R, а всей сумме (1) — множество S всех векторных показателей ее слагаемых, которое называется носителем суммы (1) или многочлена g(Q) и обозначается S(g). Выпуклая оболочка носителя S(g) называется многогранник Ньютона суммы g(Q) и обозначается r(g). Граница дГ многогранника r(g) состоит из обобщенных граней r(d) разных размерностей d = 0,1,2.
Здесь j — номер грани. Каждой обобщенной -p(d)
грани 1 j ставится в соответствие укороченная сумма
U
(d)
= {S = Aij + ••• + Am^jm } , (3)
(2)
где Xj > 0, М^ — внешние нормали к граням Г^- . То есть нормальный конус обобщенной грани является выпуклой конической оболочкой внешних нормалей двумерных граней, примыкающих к ней.
Теорема 1. Если при £ ^ те кривая
x = btsi (1 + o(1)), y = cts2 (1 + o(1)), z = dts3 (1 + o(1)),
(4)
где Ь, с, й и вг — постоянные, лежит в множестве 0, и вектор Б = (в1,в2,в3) е и^, то первое приближение
х = Ыв1, у = с£в2, г = й£в3
кривой (4) удовлетворяет укороченному уравнению = 0.
Для вершины Г
(0)
(0)
(R, S) = risi + r2S2 + r3S3.
(2)
. j укороченная сумма дj• состоит из одного слагаемого. Такие укорочения нам не интересны и в дальнейшем не рассматриваются. Будем рассматривать лишь укорочения, т. е. укороченные суммы, соответствующие ребрам Г^ и граням ^2).
Введем степенные преобразования
В частности, внешняя нормаль Nk к обобщенной
ln Q = B ln Qi
(5)
k
j
где 1п д = (1п ж, 1п у, 1п *)т, 1п д1 = (1п Ж1,1п у1,1п *1)т, В — невырожденная квадратная 3 х 3 матрица (Ь^) с рациональными элементами Ь^ (зачастую они будут целыми). При степенном преобразовании (5) моном дд переходит в моном д^1, где Дт = Вт Дт. Действительно, справедлива цепочка равенств
дк = ехр (Д, 1п д) = ехр (Д, В 1п р1)
тт
ехр (ВтДт, 1п р1> = дВ Д
Степенное преобразование (5) в двойственном пространстве М^ индуцирует линейное преобра-
зование
5 т = В-15т
д^(д) = дГЬ(Р1),
где ^(д1) = ^(ж1), если d = 1, и ^(д1) = ^(ж1,у1), если d = 2. Здесь Д = (г1,г2,гз) € М3. При этом дополнительные координаты у1, при d = 1 и при d = 2 являются локальными, и для многочлена д^(д) сумма Л,(д1) также будет многочленом.
Умножению многочлена д(д) на др соответствует параллельный перенос носителя Б(д) и многогранника Г(д) на вектор Р. Поэтому если после степенного преобразования (5), примененного к многочлену д(д), получаем конечную сумму ^(д1), содержащую отрицательные степени координат Ж1, у1 или *1, то существует такой вектор Р, что произведение дрЛ,(д1) является многочленом, т. е. все показатели степени его мономов неотрицательны.
Назовем конусом задачи К множество таких векторов Б = («1,52,53) € М3, что кривые вида (4) заметают ту часть пространства (ж, у,*), которую надо исследовать. Так, задаче 1 соответсвует конус задачи
Матрица В называется унимодулярной, если все ее элементы целые и ёе! В = ±1. Очевидно, для унимодулярной матрицы В обратная матрица В-1 также унимодулярна.
Теорема 2. Для грани Г^ существует степенное преобразование (5) с унимодулярной матрицей В, которое переводит укороченную сумму д(й)(д) в сумму от d координат, т. е.
К = {5 = («1,52,53) : Б < 0}, ибо ж, у,* ^ те. Если ж ^ те, то «1 > 0 в конусе задачи К.
1.3. Решение задачи 1
Пусть известна особая точка д° или кривая Т, состоящая из особых точек, или поверхность 5, состоящая из особых точек, вблизи которой мы хотим исследовать строение нашего множества 9 = {Р : д(Р) = 0}. Тогда надо выполнить следующую последовательность шагов вычислений.
1. Делаем замену координат д = (ж,у, *) ^
д1 = (ж1,у1,*1), переводящую множество особенностей в координатное подпространство. То есть особая точка переводится в начало координат, особая кривая — в координатную ось, а особая поверхность — в координатную плоскость. Предпочтительны замены вида
Ж = С(р1), у = п(р1), * = С(р1), где £, п, ( — многочлены. Теперь получаем задачу:
исследовать корни многочлена д1(д1) = д(д) вблизи координатного подпространства д1 = 0 или ж1 = у1 = 0, или ж1 = 0. При этом в каждом из этих трех случаев в М3 будет свой конус задачи К: Б < 0, или «1,«2 < 0 или «1 < 0, соответственно.
2. Записываем многочлен д в координатах
р1, т.е. д1(р1) = д(д), вычисляем его носитель
Б(д1), многогранник Г(д1), его двумерные (2)
грани Г^ и их внешние нормали N. Согласно формуле (3) по нормалям N вычисляем нормальные конусы ик1) ребер гк1).
3. Отбираем все те ребра Г^ и грани Г^2),
тт(1) тт(2) нормальные конусы которых и к и и^
пересекаются с конусом задачи К. Зачастую, для этого достаточно отобрать все грани Г^2), у которых внешняя нормаль Nj пересекается с конусом задачи К, и добавить все ребра Г^ этих граней.
4. Для каждого отобранного ребра Гк1) или
грани Г(2) с нормальным конусом и^, или
тт(2)
и находим корни соответствующего укороченного многочлена д(1)(д1) или д^(2)(д1). Здесь возможны два случая.
Случай а). Если множество корней имеет вид
(1)
Ж1 = ^1(^1),
у1 = ^2(21), (6)
или
Ж1 = ^1(^1,21), (7)
где 'фi — многочлены, то делаем замену коорди-
нат
Х2 = Х1 - ^1(21), У2 = У1 - ^2(21), 22 = 21
или
Х2 = Х1 - ^1(У1, 21), У2 = У1, 22 = 21
и получаем в координатах р2 = (ж2,у2,22) задачу исследования окрестности оси ж2 = у2 = 0 или координатной плоскости ж2 = 0 с конусами задачи
К = = ^N1 + ^2^2 - А1(1,0,0)}
(8
или
или
к(ж2, у2) = 0, если ^ = 2,
(11)
а дополнительные координаты у2, 22 или 22, соответственно, будут локальными, т. е. малыми. Если х0 — простой корень уравнения (10), то справедлив аналог теоремы Коши о неявной функции, и решения полного уравнения $2(Р2) = 0 разлагаются в ряд вида
ж2 - ж0
Р Л
Если ж0 — кратный корень уравнения (10), то делаем замену, как в случае а), строим новый многогранник Ньютона и т. д.
Пусть решение уравнения (11) имеет вид
Х2 = ^Ы, (12)
где ^2 — многочлен. Если на этой кривой
(13)
дк def , ч, п ^ = а(У
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.