Содержание к диссертации
Введение
Глава 1. Предварительная 19
1. Многомерный логарифмический вычет 19
2. Алгоритмы исключения неизвестных 25
2.1. Классическая схема исключения неизвестных 25
2.2. Алгоритм Бухбергера 27
2.3. Метод исключения неизвестных, основанный на формуле многомерного логарифмического вычета 30
3. Системы компьютерной алгебры, используемые в диссертации 33
3.1. Система MAPLE 33
3.2. Система математика 42
Глава 2. Нахождение результанта для невырожденных систем с помощью матрицы перехода 50
4. Базис Гребнера 50
5. Алгоритм нахождения степенных сумм 56
6. Примеры 60
Глава 3. Формулы для нахождения степенных сумм корней систем мероморфных функций 65
7. Постановка задачи 65
8. Формулы для нахождения степенных сумм корней систем мероморфных функций 68
9. Нахождение сумм некоторых двойных рядов 76
10. Компьютерная реализация полученных формул 80
Приложения 84
Библиография 90
- Алгоритмы исключения неизвестных
- Системы компьютерной алгебры, используемые в диссертации
- Алгоритм нахождения степенных сумм
- Формулы для нахождения степенных сумм корней систем мероморфных функций
Введение к работе
і; Общая характеристика работы
1.1. Актуальность темы.
Формула многомерного логарифмического вычета хорошо известна в теории функций многих комплексных переменных (см., например, [2, 20, 21]). Она дает интегральное представление суммы значений - голоморфной функции в нулях некоторой системы голоморфных функций, заданных в областях пространства С Интеграл в этой формуле должен быть вычислен по циклам: (остовам аналитических полиэдров).действительной!размерности п. Для достаточно широких классов алгебраических отображений известны формулы; вычисления данного интеграла через коэффициенты полиномов, входящих в систему (см., например, [2, 6, 20; 26, 27]). Но эти формулы настолько сложны, что практически (без разработки алгоритмов вычисления) их невозможно применить даже для простых систем. Тем более, что часто в системы входят параметры.
Первые попытки в создании таких алгоритмов (и их компьютерная реализация) для: систем сзыделенной главной:частью, треугольных систем былиданы в работах В:И.Быкова, А.М.Кытманова, М:3;Лазмана, Т.А.Осетровой: [6, 5r7, 17,.8,126]- В -данных работах были рассмотрены;применение формулы многомерного логарифмического вычета s к исключению неизве стных из систем алгебраических уравнений. Этот модифицированный метод исключения неизвестных, предложенный Л.А.Айзенбергом:в?[1], был затем развит в [6^,26]. Но для невырожденных систем алгебраических уравпений (практически самых общих алгебраических систем) такие разработки отсутствовали.
Тематика диссертации также связана с активно развивающимся в послед нее время новым; направлением в> математике компьютерной алгеброй многочленов^ лежащей на стыке алгебры, математического анализа: и программирования. Многие нелинейные задачи в приложениях характеризуются множественностью стационарных состояний: Эти- запросы инициируют появление новых теоретических результатов в области анализа систем нелинейных алгебраических уравнений. Внедрение в практику научных исследований различных систем аналитических преобразований на ЭВМ>. сделало р аботоспо собными достаточно сложные алгоритмы теории исключения.
Нелинейные системы алгебраических уравнений возникают в различных областях знания. В = частности, в процессах, описываемых системами дифференциальных уравнений с-полиномиальными правыми частями, актуален вопрос об определении числа стационарных состояний в множествах определенного вида, (и их локализации); Эта проблема приводит к задачам компьютерной алгебры многочленов: построения алгоритмов для определения числа корней заданной системы; уравнений -в- разных. множествах, определения самих корней; исключения части неизвестных из системы, построения систем треугольного вида, эквивалентных данной системе. Такие-вопросы; естественно, требуют развития методов v работы с аналитическими: выражениями на ЭВМ.
В частности в монографиях [6v 26] приведены многочисленные примеры, из химической кинетики, где работают алгоритмы вычисления многомерного логарифмического, вычета,
1.2. Цель диссертации.
Целью диссертации является: разработка алгоритмов исключения неизвестных из; систем невырожденных алгебраических уравнений; основанных на формуле многомерного логарифмического вычета; получение формул для вычисления степенных сумм для некоторых типов систем мероморфных функций с бесконечным множеством корней, разработка алгоритмов вычисления таких степенных сумм; — применение найденных формул к.нахождению сумм некоторых крат ных рядов; — компьютерная реализация в системах компьютерной алгебры MAPLE и МАТЕМАТИКА полученных алгоритмов.
1.3. Методика исследования.
В основу исследования положены методы^ вычислительной математики, теории функций многих комплексных переменных, компьютерной алгебры:
1:4. Научная новизна.
Полученные формулы и алгоритмы являются новыми. Основные результаты диссертации: — разработаны алгоритмы исключения неизвестных из систем невырож денных алгебраических уравнений, основанные на формуле многомерного ло гарифмического вычета; —- доказаны формулы для вычисления степенных сумм для некоторых типов систем мероморфных функций с бесконечным множеством корней, разработаны алгоритмы вычисления таких степенных сумм; —- полученные формулы применены к нахождению сумм некоторых кратных рядов;: — дана компьютерная реализация полученных алгоритмов в системах компьютерной алгебры MAPLE и МАТЕМАТИКА.
1.5. Апробация работы.
Основные результаты диссертации докладывались на: — Международной конференции "Математические модели и методы их исследования, (задачи механики сплошной среды, экологии, технологических процессов, экономики) (Красноярск, 1999); —VIII, LX, XII Международных научно-технических семинарах " Современные технологии в задачах управления, автоматики и обработки информации" (Алушта, 1999, 2000, 2003); —Международной конференции "Комплексный; анализ, дифференциальные уравнения и смежные вопросы" (Уфа, 2000);
Международном конгрессе "Математика в XXI веке. Роль механико-математического факультета НГУ в науке, образовании и бизнесе " (Новосибирск, 2003); научном семинаре по теории управления (Москва, МАИ); научном семинаре кафедры высшей математики (Красноярск, КрасГУ); научном семинаре кафедры прикладной математики (Красноярск, КГ- — научном семинаре кафедры прикладной математики (Красноярск,
СГАУ).
1.6. Публикации.
По теме диссертации опубликовано 8 печатных работ [39, 40, 41, 42, 43, 44, 45, 46].
1.7. Структура и объем. работы.
Диссертация состоит из введения, трех глав, приложения с текстами программ и списка литературы из 46 наименований. Общее число страниц диссертационной работы:— 93:
2. Содержание работы
В первой главе приводятся математические сведения, теоремы и формулы, на которых основана диссертационная работа. Глава состоит из трех параграфов.
Первый параграф содержит теоретические сведения о многомерном логарифмическом вычете, а также формулы для вычисления логарифмического вычета для различных систем нелинейных уравнений.
Во втором параграфе приведены алгоритмы исключения неизвестных. Он содержит классическую схему исключения неизвестных.
Далее рассматривается алгоритм упрощения полиномиальных идеалов — алгоритм Бухбергера. Приведены определения идеала, понятие редукции полиномов, нормальной формы, стандартного базиса (базиса Гребнера), а также алгоритмы приведения множества полиномов к нормальной форме и базису Гребнера. С помощью этого алгоритма также можно свести исходную систему к треугольному виду. Алгоритм; Вухбергера используется во второй главе при построении матрицы Л — матрицы перехода, которая необходима в процессе вычисления степенных сумм координат корней рассматриваемой системы.
Во втором параграфе также приведен модифицированный метод исключения неизвестных, основанный на формуле многомерного логарифмического, вычета.
В третьем параграфе приведен обзор литературы по системам компьютерной алгебры и подробно описаны системы MAPLE и МАТЕМАТИКА, использовавшиеся для компьютерной реализации разработанных в диссертации алгоритмов.
Вторая глава состоит из трех параграфов и посвящена нахождению результанта для невырожденных систем с помощью матрицы перехода.
В четвертом параграфе рассматривается вопрос о нахождении результанта и построении матрицы перехода с помощью базисов Гребнера.
Рассматривается.система алгебраических уравненийв С*: /,--0,./=1,....,11, (0.1). где /у — полиномы степени Аг,-. Пусть /у = Pj.+ Qj} где Pj — старшая однородная часть /,, а степень Qj строго меньше kj. Наряду с системой (0.1), рассматривается система
Р,- = 0,./ = 1,...,».. (0.2)
Будем говорить, что система (0.1) невырождена, если система (0.2) имеет только одно решение — точку 0. Мы будем иметь дело с многочленами /у, коэффициенты которых зависят от каких-то параметров. В этом случае система (0.1) считается невырожденной, если система (0.2) имеет одно решение для почти всех значений в пространстве параметров.
Известно, что невырожденные системы вида (0.1) характеризуются тем, что они имеют в пространстве С" конечное число корней и не имеют корней на бесконечной гиперплоскости П.
Число корней для невырожденных систем дает теорема Везу: число корней (0.1) с учетом их кратностей равно произведению степеней / * кп.
Еслисистема вида (0.1) имеет конечное число корней в СР"^ то дробно — линейным преобразованием она может быть сделана невырожденнойj достаточно в QPn бесконечно удаленной плоскостью П сделать гиперплоскость, не содержащую корней системы (0.1). В CIP" это можно сделать линейным преобразованием, а, следовательно, в С" дробно-линейным. Следовательно, по сути невырожденные системы алгебраических уравнений — это самые общие системы алгебраических уравнений с конечным числом корней.
Основной вопрос данного параграфа — исключение из (0.1) всех переменных, кроме одного, т.е. нахождение результанта RES(zj) с помощью формулы многомерного логарифмического вычета. По теоремеТильберта о корнях (см. [9, с.490]) найдется матрица (которую назовем матрицей перехода)
А= |М|?4в1, составленная из однородных полиномов а^, такая, что
4i+l = EaJfc(*)A(*), 3 = 1,..., «і (0.3) причем степени JV,- можно выбирать, не превосходящие числа ki+k2 + * * + кп -п (по теореме Маколея [32], а также [20, с.193]). Для любого многочлена R = R(z) степени M (-l)'JeI ,J ft (E%*)! f W «fe* ЛД ft <#" П (Mr sR= =-=^ ш - .-.'/"- : to.4) где a,- = 5^ fc.j, /?, = E^'J» A — якобиан системы (0.1), a 97t— линей- ный функционал, сопоставляющий многочлену Лорана ^ ^ jn его свобод- ный член. Задаем фиксированный многочлен R = i?(z) и вычисляем степен ные суммы корней системы (0.1) 5д = #, г = 1, ,Xr, L — k\kf->kn.
Далее вычисляем коэффициенты результанта Gj, j — 1,... , по рекуррентным формулам Ньютона. Основная проблема в этом методе — нахождение элементов djk матрицы перехода. В [14] показано, что можно найти линейное представление полиномов базиса Гребнера (7 через полиномы Р}- исходного базиса F (и обратно). Пусть такое представление (0.5).- найдено. Решим следующую задачу [13]. Даны базис Гребнера G = д\...д* и некоторый полином / Є Ideal(F). Найти такие hi... hm, что / = ^i5i + ... + hmg„
Тогда получим / = f jtfjXfi) +.-+A» Г№»] =S (S.^J'/j. (0.6)-
Если выбрать / = z^+1, исходный базис F = Px{z)... Pn{z), G = Br(F), тогда элементы матрицы А можно найти как коэффициенты при /у в представлении (см.выше). Этой проблеме посвящен пятый параграф. Алгоритм вычисления матрицы А имеет вид:
1. Вычисляем G — базис Гребнера по алгоритму Бухбергера [14]. Пусть ді-Є-G. В процессе вычисления у,- строим S - полиномы 5(P»,Pj) по формуле
Гір r-jp где Pip, Pjp — старшие члены полиномов І>,-, Ру, которые получаются перемножением всех переменных, каждая в степени, равной максимуму ее степеней в старших мономах и их коэффициентов, К — их наименьшее общее кратное. p~t--p, суть мономы, поэтому 5(Pj,Pj) линейная комбинация полиномов Pi и Pj с полиномиальными коэффициентами и принадлежит идеалу, порожденному Рі-Ж.Ру
Известно, что базис G является стандартным тогда и только тогда, когда для любой пары полиномов / и д из множества G их S- пол ином. S( f,g) редуцируется к нулю относительно G [13].
Следовательно, достаточно вычислить все 5-полиномы и, проверить,. что все они редуцируются к нулю. Но если наш базис не стандартный, то это в точности потому,,что один из этих 5" - полиномов не редуцируется к нулю.. Поскольку его редукция является линейной комбинацией элементов множества G, можно добавить ее к G, не изменив при этом порождаемый идеал. После этого добавления S(f,g) редуцируется к нулю, но появляются новые S полиномы, которые также нужно рассматривать. Бухбергером доказано, что этот процесс всегда заканчивается.
При решении нашей задачи в процессе построения S(Pi,Pj) вычисляем коэффициенты ~- и записываем их в память: это Xji из (0.5). Процесс повторяем, пока не получим стандартный базис.
2. Редуцируем по модулю G — мономы Zyi+1 к нулю. Для этого составляем 5-полиномы % jvv+u h h ЛГ.-+1 mV ) =: —д - -j^^ ' , где ft — наименьшее общее кратное (НОК). Затем все.— суммируем. Вы- числения проводим до тех пор, пока все 5-полиномы станут равны нулю.-
Накопленные суммы дадут значения ft;.
3. Вычисляем djt,(z) = 2 ft* -Ху;. Очевидно, что на сложность алгоритма »=1 влияет порядок выбора пар полиномов, для которых строятся ^-полиномы. В данном параграфе рассмотрены некоторые возможности его улучшения.
В пятом параграфе приведен алгоритм нахождения степенных сумм, реализующий формулу 0.4.
1. Задаем систему алгебраических уравнений:
Л, =0, (0.7) Jn =0;
Где полиномы /, имеет вид П (4= Е &а> (0.8). а — (ai,..., a„) — мультииндекс, z" — z*1 z", а степень полинома (deg /,) равна kj, т. е. существует коэффициент са ф 0 в полиноме (1;1), с ||a|| = kj (здесь и в дальнейшем j|aj|'= Qi + ... + ап).
Задаем фиксированный полином R{z), например, г*, относительно которого будут вычисляться степенные суммы корней.
Рассматривая /у = Pj + Qj, где Pj — старшая однородная часть /у, а степень Qj строго меньше fcj, задаем Pj и Qj.
Вычисляем элементы матрицы А по алгоритму Бухбергера, исходя из соотношения fci+...+feft-n+l = Еа^Рі' І = 1,---n-
5. Вычисляем функционал RCTdetAJf П <'/ (0.9)
При этом сравниваем степени переменных, стоящих в числителе и в знаменателе выражения, стоящего под знаком функционала. Если эти степени совпадают, то выписываем полученный свободный член.
В силу линейности функционала, сопоставляющего многочлену Лорана его свободный член, степенная сумма S& корней системы относительно полинома
1М|=0 где К — степень полинома R, есть
IMI= где Sa.~ 5^,...,^ — степенная сумма монома za. Следовательно, для вычисления Sr достаточно вычислить 5а, т.е. степенные суммы соответствующих мономов. б. Полученный свободный член умножаем на константу П (*«)! и суммируем, согласно заданным ограничениям.
В конце параграфа приведено описание MAPLE-программы, реализующей данный алгоритм. В шестом параграфе рассмотрены примеры нахождения матрицы А и степенных сумм корней систем полиномиальных уравнений.
Работа алгоритма опробована на тестовых примерах (6).
Третья глава содержит формулы для нахождения степенных сумм корней систем мероморфных функций. Эти формулы позволяют найти суммы некоторых двойных рядов, неизвестные ранее.
В седьмом параграфе приводится постановка задачи и необходимые предварительные преобразования.
Рассматривается система функций Л(г), f2{z),... ,U{z), голоморфных в окрестности точки О Є С, z = (zi,Z2,... ,zn), и имеющих следующий вид /,-(*)=«"'+Qi(*), j = 1,2,..., п, (0.10) где /?J = G#i,/?2>--- >$1) — мультииндекс с целыми неотрицательными коор-дии«мга,^=^.^».^и||)9'|| = ^Ч^" + ... + Й = *і,-,і = 1,2,... ,п. Функции Qj разлагаются в окрестности нуля в ряд Тейлора, сходящийся абсолютно и равномерно, вида
1М1>о (0.11) где а = {аиа2,... ,ап), а; > 0, а,- Z, а га = г"1 г^ я«.
В дальнейшем считается, что степени всех мономов (по совокупности переменных), входящих в Qj, строго больше, чем &j, j = 1,2,... ,n (||а|| = ai +«з + -+«« > %).
Рассмотрим циклы 7(r)- = 7(гъг2> >^п), являющиеся остовами поли кругов:
7(^)=^6^:1^1=^,8 = 1,2,... ,п}, п>0,... ,г„>0.
В некоторой достаточно малой окрестности нуля система
Д(*)=0, (0.12) Ш = о может иметь корни только на координатных плоскостях {z : ze
1,2,.., ,п. = 0}, s =
Поэтому при достаточно малых г,, определены интегралы вида ч(0 т(гі,гі,.,.,гп) где А 5:0, j02 >0\... ,/3„ > 0, / eZ,/= (ІД,..- ,1). Обозначим
7 =_i_ /"-L- ' " (2тгг)" У ^+' ' /"
Заметим, что данный интеграл до виду является многомерным логарифмическим вычетом, но моном в отрицательной степени ^у не голоморфен в точке 0. Поэтому общая теорема о логарифмическом вычете к данному интегралу не применима и связь этого интеграла с какими-то степенными суммами корней системы необходимо доказывать.
В восьмом параграфе доказаны основные теоремы третьей главы.
Теорема 8.1, При сделанных предположениях для функции fj вида (0.10), (0.11) справедливы формулы: (_1)1М1 {/3 + (at + 1),51 +... + (an + 1)/?")! ]|a||<|]0|[+min(n,*l+...+*») g^+(o1+l)^l+...+(en.+t)/J« dk(A-Qa) ]Г (-1)ИІЯК-
1І«К11^|1+пші(пЛі+-.+*»)
Д-Q6 ^+(04+1)^^...+ (^+1)^- где k- \\0 + (аг +1)01 + ... + (ап + 1)/?"[|, (3\ - fal fcl */?„!, А — якобиан эш аїри системы (5^, - 0е = С??1 QJ? - - -, -^- = dzbdzb-.-dz?* U' НаН0НЄЧ' Ш — линейный функционал, сопоставляющий ряду Лорана его свободный член.
Отметим, что в указанные в теореме 8.1 формулы входит лишь конечное число коэффициентов функций Qj(z).
Следствие 8.1, Если все (3і ~ (0,0,... , 0), то интеграл imisiwii- Jp = y,. (-1),W,9« AQa" „, <-l)\MQ\\P\\
01 dz»
Далее рассмотренные интегралы связываются со степенными суммами корней системы (0.12). Для этого нужно сузить класс функций fj. Сначала в качестве функций Qj (j = 1,2,... , п) берутся многочлены вида Qj(z) - *ЯЛ (0.13) где Mj — конечное множество мультииндексов такое, что при а М> координаты а*. ^ ftl, к = 1,2,... ,гг, А: ф j. (Но по прежнему предполагается, что |]a|j > Щ для всех а Є 'Mj). Обозначим М 1
Данное выражение является степенной суммой корней z^) системы (0.12), не лежащих на координатных плоскостях, но в отрицательной степени (либо степенной суммой от обратных величин корней). Число таких корней (с учетом их кратностей) обозначается через М.
Теорема 8.2. Для системы (0.12) с многочленами fj вида (0.10) и многочленами Qj вида (0.13) справедливы формулы Jp = (-l)nffp+i,
2/5+l«»l+Wl+...-He.+W» ' ^ J *!>+' = Е (-1)»"!ЭТ І|аКІ^ІІ+«аІи(«^і+.-+*.ї
В восьмом параграфе рассматривается более общая ситуация. Пусть функции fj имеют вид /,(*) = -Ж-Г, J = 1,2 п, (0.15) где /j \z) и fj '(z) — целые функции вС, разлагающиеся в бесконечные произведения (равномерно и абсолютно сходящиеся в С). *=1 Л=1 причем каждый из сомножителей имеегформу zP' -\-Qj{z), a Qj(z) — функции вида (З.б).
Для каждого набора индексов л,... ,jn, где ju... ,jn Є N, и каждого набора чисел ily..., i„, где ti,... , гп равны 1 или 2, системы нелинейных алгебраических уравнений /{>(*) = о. /Й*W = «,., /&'(*) = о> (0-16) имеют конечное число корней, не лежащих на координатных плоскостях.
Корни всех таких систем (не лежащие на координатных плоскостях) составляют не более, чем счетное множество. Перенумеруем их (с учетом кратностей): -2(i), Z(2),... ,Z((),.... Будем предполагать, что ряд (0.17) J~{,1*1(1)1 ' 1^2(1)[ -*- kn(I)l сходится.
Обозначим через cp+i выражение
1=1 ^1(0 *з(0 ro(i). Здесь /Зі,... ,/?„, как и прежде, неотрицательные целые числа, а знак е^ равен +1, если в систему вида (3.11), корнем которой является 2(f), входит четное число функций /], , и равен —1, если в систему вида (3.11), корнем которой является 2(f), входит нечетное число функций п3.
Ряды, определяющие суммы <7p+i сходятся, в силу условия, наложенного на ряд (0.17).
Для системы (0.12), составленной из функций вида (0.15), точки гщ являются корнями или особыми точками (полюсами).
Теорема 8.3. Для системы (0.12) с функциями вида (0.15) справедливы равенства Jp = (-1)"0+/.
Отметим, что если fj(z) являются целыми функциями, разлагающимися в бесконечные произведения, то они сами имеют вид (3.1) с функциями Qj{z) вида (0.11). Поэтому интегралы Jp вычисляются по теореме 8.1.
В девятом параграфе приведены некоторые приложения полученных формул к нахождению сумм двойных рядов.
Рассмотрим ряд к,т=1 у '
Представляя его как степенную сумму корней для некоторой системы трансцендентных уравнений, получаем утверждение. Следствие 9.1 Справедливы формулы - 1 V* 1 _ 1 _ 1 ^-л fA-Qa" ffU«+i.i)- ^(зТЙГ Ъ ^(а-+і)/тз + Лз)- 2JV''Q) ~ 2 ^ zV г
Рассмотрим, например, і/г.оь Вычисления дают J/2,o) = -.,--, а <Т(з,і) v ' 56700 ^ 1. ІЗтт?
Следовательно, " kW+m2) 113400' k,m—l v ' что отличается от формулы 10 на с. 750 из [19] (где она приведена с ошибкой), но полностью совпадает с примером 1 из [15].
В последнем десятом параграфе приведена компьютерная реализация полученных формул. Приводятся алгоритмы, описания программ и приведены примеры.
Приложения содержат тексты программ.
Алгоритмы исключения неизвестных
Задачи компьютерной алгебры и ее приложений нередко сводятся к решению систем нелинейных алгебраических уравнений, В частности, в процессах, описываемых системами дифференциальных уравнений с полиномиальными правыми частями, актуален вопрос об определении числа стационарных состояний в множествах определенного вида (и их локализации). Эта проблема приводит к задачам алгебры многочленов: построения алгоритма для определения числа корней заданной системы уравнений в разных множествах, определения самих корней, исключения части неизвестных из системы, построения систем «треугольного» вида, эквивалентных данной системе. В этом параграфе приводится обзор по методам исключения неизвестных. Подробно описан метод нахождения степенных сумм, основанный на теории многомерных вычетов. Пусть P(z, ги), Q(ziw)— полиномы от двух комплексных неременных z и w: коэффициенты a3(ty), bj(w) — полиномы по ги; будем считать, что cto(w) ф О и bo{w) ф 0. Составим результант этих полиномов по переменной z При этом R(P}Q) F(w). Пусть (а,/Э) — корни системы Р(г,ш) = 0, Q(zi to) :=0-. (Г.8): Подставляя в эту систему значение w.— /?, получим два полинома P(z,ft)y Q(z,{3), являющиеся полиномами одного переменного 2. Они обладают общим корнем z = а. Следовательно, по теореме Сильвестра (см.,. например, [16]) F{0): = 0. Обратно, если результант полиномов R(Р, Q) обладает корнем # то по той же теореме либо полиномы P(z,/3) и Q(z,fi) имеют общий корень а, либо /3 является корнем полиномов aQ(w) и Ьо(ад), т.е. либо эти полиномы обладают общим корнем z = /3, либо оба их старших коэффициента равны нулю, т.е. ао = 0 и Ьо — 0.В.В частности, если эти полиномы общих корней не имеют, то любой корень F(w) является; второй координатой корня системы (1:8). Рассмотрим системы, содержащие несколько уравнений. ТЕОРЕМА 2,1. Для г полиномов Pi(z)t...,Pr{z) от одного переменногоz Є С существует система Нг,..., І2 . полиномов от коэффициентов Ри..., Рг, обладающая тем свойством, что условия R\ — 0,...,і?ь = 0 необходимы и достаточны для- того, чтобы либо система уравнений Ри = 0,,.., Рг — 0 имела общий корень, либо старшие коэффициенты всех полиномов Pi,,.. ,РГ одновременно обращались в нуль. Пусть нам задана система алгебраических уравнений где .г =. (zi7...,z„) е С ; Мы можем для;нее проделать следующее.
Предположим, что полином Pi содержит моном наибольшей степени по z\ вида za, и коэффициент при нем есть константа, отличнаяот нуля. Этого всегда можно добиться, делая линейную замену переменных. Тогда, применяя к системе (1.9) теорему 2.1 по переменной zi, запишем систему уравнений зависящую от 2,...,z„ и эквивалентную системе (1.9). В результате проведения $ шагов мы получим либо систему полиномов, тождественно равную нулю, либо систему констант, не все из которых равны нулю. Во втором случае первоначальная система (1.9) общих корней не имеет. В первом случае имеем треугольную систему вида где JJi,..., К — полиномы от Zj,...,„,.а применение следующего шага-(по zt) приводит к системе из полиномов, тождественно равной нулю. Тогда переменным zt+u..., zn можно придать любые значения ,+i, ...,«, из системы R\ = 0,..., Rk =0 найти общие решения ,, затем все эти решения подставить в следующую систему и т. д. пока мы не дойдем до системы (1.9). Вследствие быстрого роста размерности определителей матриц Сильвестра, вычисляемых в процессе исключения, этот метод неэффективен для компьютерной реализации, тем не менее в ряде работ этот метод использовался (см., например, [24, 33, 34]). О неэффективности данного метода говорит тот факт, что в первых изданиях монографии Ван дер Вардена (см., например, [10]) классическая схема исключения неизвестных приводится, а в последних изданиях данной монографии.(см., например, [9]) она исключена. 2.2. Алгоритм Бухбергера. В 1965 г. Б. Бухбергер предложил.метод упрощения полиномиальных идеалов, названный им в честь своего научного руководителя методом «базисов Гребнера» [4, 13, 23, 31, 37]. Начиная с 1976 года этот метод постоянно уточняется, применяется, обобщается и анализируется. Он представляет собой технику, дающую алгоритмические решения
Системы компьютерной алгебры, используемые в диссертации
Пакет MAPLE — совместное детище университета Ватерлоо (штат Онтарио, Канада) и Высшей технической:школы (ЕТН, Цюрих, Швейцария). Пакет широко распространен в университетах ведущих научных держав, исследовательских: центрах и компаниях. Первая : реализация версии:V состоялась в 1990 г., в настоящее время распространены седьмая и девятая версии. Примечательно включение символьного анализатор а MAPLE в і состав инженерного пакета: MathCad (компания; MathSoft Inc.) и пакета вычислительной математики MatLab (компании -. Math Works). Текс-ТОВЬІЙЇ редактор;Scientific. Word фирмы TCI Software Research в результате скрещивая с подвидом пакета MAPLE превратился в Scientific Workplace — рабочее место исследователя, где:совмещены операции написания!формул; проведения выкладок и численных расчетов, графического оформления результатов и подготовки статьи; в формате LaTeXa. Символьный анализатор MAPLE входит также в состав пакета подготовки научных публикаций Math Office. MAPLE состоит из ядра — процедур; написанных.на языке С и в высшей степени оптимизированных, библиотеки, написанной на MAPLE-языке, и интерфейса: Ядро выполняет большинство базисных операций. Библиотека.содержит множество команд — процедур, выполняемых в режиме интерпретации. Программируя собственные процедуры, пользователь может пополнять ими стандартный набор і и, таким образом, расширять возможности: MAPLE. Перечислим основные возможности; предоставляемые системой MAPLE пользователю. — целая и рациональная арифметика любой точности; — машинная арифметика с плавающей точкой и арифметика с плавающей; точкой «произвольной.точности»; — алгебра полиномов от одной и: нескольких1 переменных: — вычисление наибольшего общего делителя; — вычисление наименьшего общего кратного; — вычисление степени и коэффициентов полинома; — вычисление якобиана; — разложение на множители полиномов с целыми коэффициентами; — деление полиномов и т.д.; — алгебра матриц с полиномиальными или символьными коэффициентами: — вычисление определителей; — обращение матриц; — вычисление миноров; — построение гильбертовых матриц и матриц
Сильвестра; — построение эрмитовых матриц и канонических форм Смита; — вычисление ранга матрицы и т.д.; — математический анализ: — дифференцирование; — интегрирование; — вычисление суммы ряда; — нахождение пределов действительных и комплексных функций; — разложение функции.в.ряд.Тейлора.и.т.д.;. — решение уравнений: — решение нелинейных алгебраических уравнений; — решение систем линейных алгебраических уравнений; — решение обыкновенных дифференциальных уравнений; — решение дифференциальных уравнений в частных производных; — решение рекуррентных уравнений; — преобразование выражений: — упрощение; — подстановка; — евклидова геометрия; — пространственная геометрия; — статистика; — вычисление базисовТребнера; — дискретная математика и т.д; Работа пользователя в системе происходит в интерактивном режиме, поэтому программа;представляет собой последовательность команд; в порядке поступления команд система до; пер ехода к следующему этапу интерпретирует каждую команду и вычисляет ее значение.. Команды могут представлять собой выражения, вызовы процедур, циклы, условные операторы и т. д., оканчивающиеся:символом «;», если предполагается печать результатов, выполнения команды, либо символом «:» в противном случае. Выражения могут состоять из чисел, переменных, операторов, строк, зарезервированных слов и: разделителей. Эти синтаксические правила являются общими для большинства языков высокого уровня. Для записи конструкции языка системы MAPLE! используется стандартный набор:символов: — буквы - латинского алфавита: :A\...Z,.ay... z... причем система -, различает заглавные и прописные буквы; — цифры: :0,..., 9; Имена переменных и; процедур состоят из букв, цифр; подчеркиваний; и начинаются обязательно с. буквы,например сП, Dl, D А. Числа і системы — это целые числа с произвольным количеством цифр, а также числа с плаваю-щейточкой произвольной точности,. 5, —123457820, +99,, 3.1415926. Последовательность ключевых слов языка состоит из следующих слов: by, do, done, eiif, ebe, end, fi,. for, from, if, local, in, od option, options, proc, quit, read, save, stop, then, to,.while. Любая часть: строки,. начинающаяся знаком # . воспринимается системой: как комментарий. Знак \ в конце строки означает, что следующая строка является продолжением данной. Знак в начале строки служит для вызова help.
Алгоритм нахождения степенных сумм
Опишем алгоритм нахождения степенных сумм, реализующий формулу (1.7). 1. Зададим систему алгебраических уравнений: I Л =о, (2.8) U =0. Здесь полиномы /у имеет вид 1Н№ (2.9) а = (о(і,..., а„) — мультииндекс, z" = г"1 г", а степень полинома (deg fj) равна fcj, т.е. существует коэффициент са ф 0 в полиноме (1.1), с ЦлЦ = kj (здесь и в дальнейшем а) = х\ +... + ап). 2. Зададим фиксированный полином R(z), например, z\, относительно которого будут вычисляться степенные суммы корней. 3. Рассматривая /_,- = Pj + Qj, где Pj — старшая однородная часть /,-,..а. степень Qj строго меньше kj, задаем Pj и Qj. Вычисляем элементы матрицы А по алгоритму Бухбергера, исходя из соотношения При этом сравниваем степени переменных, стоящих в числителе и в знаменателе выражения, стоящего под знаком функционала. Бели эти степени совпадают, то выписываем полученный свободный член. В силу линейности функциона на кафедре теории функций Красноярского государственного университета: пакет Standard, реализующий алгоритмы вычисления нормальной формы и построения стандартного базиса, пакет AlgSyst для работы с системами алгебраических уравнений. Также создан пакет программ Мураск, реализующий вычисление старших мономов (функция Sen_Monom) и младших мономов (функция Jr„Monom) данной системы полиномов, функция vec pow_vec ("вектор в степени вектор"). В пакет включена процедура Pokaz представления n-ричной системы счисления в виде списка. Например, для двоичной системы счисления эти списки выглядят следующим образом : [0,0,0,0],[0,0,0,1], п Такие списки необходимы для вычисления сумм ktfj или произведений л П (к,j) применительно к формуле 1,7. Пакет также включает процедуру coefficient, вычисляющую функционал сопоставляющий ряду Лорана его свободный член..
Эта программа выбирает коэффициенты числителя, стоящего под знаком функционала, при степенях +&+ fm Программа может работать с системами полиномов произвольной размерности и произвольных степеней старшей однородной части. Вводим список переменных var, список полиномов F и фиксированный полином И. Используя: функцию Sen_Monom, составляем список старших мономов Р. Находим полиномы Qj, степень которых строго меньше kj. Далее определяем степень М полинома R и вычисляем якобиан Jf (в программе это Delta), стоящий под знаком функционала 2Я. Затем вычисляем показатели степеней р, применительно к формуле 1.7 это Nj. Далее, обращаясь к функции red_NFBjex, входящей в пакет Standard, находим матрицу А. Теперь необходимо вычислить коэффициент t стоящий перед функционалом ЯЯ, а также показатели степеней аія. (3. Здесь мы используем функцию Pokaz. При вычислении степенных сумм необходимо соблюдать ограничения п ktj Ои 2k„j -Af» поэтому следующие действия производим, соблюдая эти условия суммирования. Числитель ла, сопоставляющего многочлену Лорана его свободный член, степенная сумма SR корней системы относительно полинома где 5а = Sair„fb — степенная сумма монома 2а. Следовательно, для вычисления SR достаточно вычислить Sa, т.е. степенные суммы соответствующих мономов. 6. Полученный свободный член умножаем на константу и суммируем, согласно заданным ограничениям. Работа алгоритма-опробована на нескольких примерах (см.6). Описание MAPLE-программы. Опишем программу, с помощью которой можно вычислять степенные суммы корней полиномов по формуле 1:7. Для ее работы использовались встроенные пакеты программ Linalg, Linear Algebra, ListTools, пакеты программ М.В.Потехшюй [18]; разработанные на кафедре теории функций Красноярского государственного университета: пакет Standard, реализующий алгоритмы вычисления нормальной формы и построения стандартного базиса, пакет AlgSyst для работы с системами алгебраических уравнений. Также создан пакет программ Мураск, реализующий вычисление старших мономов (функция Sen_Monom) и младших мономов (функция Jr„Monom) данной системы полиномов, функция vec pow_vec ("вектор в степени вектор"). В пакет включена процедура Pokaz представления n-ричной системы счисления в виде списка. Например, для двоичной системы счисления эти списки выглядят следующим образом : [0,0,0,0],[0,0,0,1], п Такие списки необходимы для вычисления сумм ktfj или произведений л П (к,j) применительно к формуле 1,7. Пакет также включает процедуру coefficient, вычисляющую функционал сопоставляющий ряду Лорана его свободный член.. Эта программа выбирает коэффициенты числителя, стоящего под знаком функционала, при степенях +&+ fm Программа может работать с системами полиномов произвольной размерности и произвольных степеней старшей однородной части. Вводим список переменных var, список полиномов F и фиксированный полином И. Используя: функцию Sen_Monom, составляем список старших мономов Р. Находим полиномы Qj, степень которых строго меньше kj. Далее определяем степень М полинома R и вычисляем якобиан Jf (в программе это Delta), стоящий под знаком функционала 2Я. Затем вычисляем показатели степеней р, применительно к формуле 1.7 это Nj. Далее, обращаясь к функции red_NFBjex, входящей в пакет Standard, находим матрицу А. Теперь необходимо вычислить коэффициент t стоящий перед функционалом ЯЯ, а также показатели степеней аія. (3. Здесь мы используем функцию Pokaz. При вычислении степенных сумм необходимо соблюдать ограничения п ktj Ои 2k„j -Af» поэтому следующие действия производим, соблюдая эти условия суммирования. Числитель функционала вычисляем, используя функцию vec_pow_vec, и заносим в NOM. Оператору POW присваиваем значение ftjNj + / + Nj показателей степеней, стоящих в знаменателе функционала ЯЛ. Вычисляем значение функционала и присваиваем его оператору МММ. Затем находим степенные суммы и присваиваем их оператору S1. Коэффициенты результанта вычисляем по рекуррентным формулам Ньютона, в программе обозначаем их д[г].
Формулы для нахождения степенных сумм корней систем мероморфных функций
Пусть для системы (3.4) выполнены условия предыдущего параграфа. Первое утверждение имеет вид. Покажем, что в этой сумме лишь конечное число слагаемых отлично от нуля. Для этого подсчитаем степени (по совокупности переменных) мономов, входящих в числитель и знаменатель подынтегрального выражения. Степень мономов, входящих в Д {deg Д), не меньше, чем maxfll/?1!! +... + \\(Зп\\ — п, 0) = maxffci + ... + кп — щ 0). Для степени мономов, входящих в Qai получаем оценку: Поэтому степень числителя не меньше, чем Степень знаменателя равна Поэтому в сумме (3.5) все слагаемые, для которых степень числителя больше степени знаменателя на п, равны нулю. Таким образом, могут быть отличными от нуля лишь слагаемые, для которых Последнее неравенство эквивалентно следующему Отметим, что (как показывает доказательство) в указанные в теореме 8.1 формулы входит лишь конечное число коэффициентов функций Qi{z). J IMKIWI И - a( Qa) г=0 Наша дальнейшая цель — связать рассмотренные интегралы со степенными суммами корней системы (3.4). Для этого нужно сузить класс функций /,-. Сначала возьмем в качестве функций ?,- (j = 1,2,... ,п) многочлены вида (3.6) где Mj — конечное множество мультииндексов такое, что при а Є -My координаты ak Pi, к = 1,2,... , п, Аг j. (Но по прежнему предполагается, что (aj kj для всех а Є М,). Сделаем замену Zj = —, j = 1,2,... ,п. При такой замене получим где Sj наибольшая степень многочлена Qj(z) по переменной z e1 = (1,0,... , 0), е2 = (0,1,... , 0), ..., en = (0,0,..., 1), а многочлен имеет степень (по совокупности переменных) строго меньшую, чем-ay (в силу условий, наложенных на многочлены Qj{z)). По теореме Везу система нелинейных алгебраических уравнений имеет конечное число корней, равное (с учетом их кратностей) si -s2 - sn, и не имеет корней на бесконечной гиперплоскости GP" \ О . Обозначим корни системы (3.7), не лежащие на координат Степень мономов, входящих в Д {deg Д), не меньше, чем maxfll/?1!! +... + \\(Зп\\ — п, 0) = maxffci + ... + кп — щ 0). Для степени мономов, входящих в Qai получаем оценку: Поэтому степень числителя не меньше, чем Степень знаменателя равна Поэтому в сумме (3.5) все слагаемые, для которых степень числителя больше степени знаменателя на п, равны нулю. Таким образом, могут быть отличными от нуля лишь слагаемые, для которых Последнее неравенство эквивалентно следующему Отметим, что (как показывает доказательство) в указанные в теореме 8.1 формулы входит лишь конечное число коэффициентов функций Qi{z). J IMKIWI И - a( Qa) г=0 Наша дальнейшая цель — связать рассмотренные интегралы со степенными суммами корней системы (3.4). Для этого нужно сузить класс функций /,-. Сначала возьмем в качестве функций ?,- (j = 1,2,... ,п) многочлены вида (3.6) где Mj — конечное множество мультииндексов такое, что при а Є -My координаты ak Pi, к = 1,2,... , п, Аг j. (Но по прежнему предполагается, что (aj kj для всех а Є М,). Сделаем замену Zj = —, j = 1,2,... ,п.
При такой замене получим где Sj наибольшая степень многочлена Qj(z) по переменной z e1 = (1,0,... , 0), е2 = (0,1,... , 0), ..., en = (0,0,..., 1), а многочлен имеет степень (по совокупности переменных) строго меньшую, чем-ay (в силу условий, наложенных на многочлены Qj{z)). По теореме Везу система нелинейных алгебраических уравнений имеет конечное число корней, равное (с учетом их кратностей) si -s2 - sn, и не имеет корней на бесконечной гиперплоскости GP" \ О . Обозначим корни системы (3.7), не лежащие на координатных плоскостях и с учетом их кратностей, через ц)(Ь) - (u;i(i.),u?2{fe},... ,«Ц )), к = 1,2,... ,М, М $i -s2 -"Sn. Тогда точки zin = I ——, ——,... , - - У и только они являются корнями системы (3.4), не лежащими на координатных плоскостях. ЛЕММА 8.1. Система (8-4) с многочленами fj вида (3.1) и многочленами Qj вида (3.6) имеет конечное число корней (с учетом их кратностей) 2(1)»2(2) -.- ,z{M)rHe лежащих, на координатных плоскостях {z,..= 0}, 5 = 1,2,... A=l zl{k) z2(h) "zti{k) Данное выражение является степенной суммой корней, не лежащих на координатных плоскостях, системы (3.4), но в отрицательной степени (либо степенной суммой от обратных величин корней). ТЕОРЕМА 8.2. Для системы (3.4) с многочленами fj вида (3.1) и многочленами Qj вида (3.6) справедливы формулы
ных плоскостях и с учетом их кратностей, через ц)(Ь) - (u;i(i.),u?2{fe},... ,«Ц )), к = 1,2,... ,М, М $i -s2 -"Sn. Тогда точки zin = I ——, ——,... , - - У и только они являются корнями системы (3.4), не лежащими на координатных плоскостях. ЛЕММА 8.1. Система (8-4) с многочленами fj вида (3.1) и многочленами Qj вида (3.6) имеет конечное число корней (с учетом их кратностей) 2(1)»2(2) -.- ,z{M)rHe лежащих, на координатных плоскостях {z,..= 0}, 5 = 1,2,... A=l zl{k) z2(h) "zti{k) Данное выражение является степенной суммой корней, не лежащих на координатных плоскостях, системы (3.4), но в отрицательной степени (либо степенной суммой от обратных величин корней). ТЕОРЕМА 8.2. Для системы (3.4) с многочленами fj вида (3.1) и многочленами Qj вида (3.6) справедливы формулы
